← Back to branch summary

~mmach/netext73/mesa-haswell

« back to all changes in this revision

Viewing changes to src/util/u_idalloc.c

  • Committer: mmach
  • Date: 2022-09-22 19:56:13 UTC
  • Revision ID: netbit73@gmail.com-20220922195613-wtik9mmy20tmor0i
2022-09-22 21:17:09

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/util/u_idalloc.c
1
 
/**************************************************************************
2
 
 *
3
 
 * Copyright 2017 Valve Corporation
4
 
 * All Rights Reserved.
5
 
 *
6
 
 * Permission is hereby granted, free of charge, to any person obtaining a
7
 
 * copy of this software and associated documentation files (the
8
 
 * "Software"), to deal in the Software without restriction, including
9
 
 * without limitation the rights to use, copy, modify, merge, publish,
10
 
 * distribute, sub license, and/or sell copies of the Software, and to
11
 
 * permit persons to whom the Software is furnished to do so, subject to
12
 
 * the following conditions:
13
 
 *
14
 
 * The above copyright notice and this permission notice (including the
15
 
 * next paragraph) shall be included in all copies or substantial portions
16
 
 * of the Software.
17
 
 *
18
 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
19
 
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20
 
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
21
 
 * IN NO EVENT SHALL THE AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR
22
 
 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
23
 
 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
24
 
 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
25
 
 *
26
 
 **************************************************************************/
27
 
 
28
 
/**
29
 
 * @file
30
 
 * A simple allocator that allocates and release "numbers".
31
 
 *
32
 
 * @author Samuel Pitoiset <samuel.pitoiset@gmail.com>
33
 
 */
34
 
 
35
 
#include "util/u_idalloc.h"
36
 
#include "util/u_math.h"
37
 
#include <stdlib.h>
38
 
 
39
 
static void
40
 
util_idalloc_resize(struct util_idalloc *buf, unsigned new_num_elements)
41
 
{
42
 
   if (new_num_elements > buf->num_elements) {
43
 
      buf->data = realloc(buf->data, new_num_elements * sizeof(*buf->data));
44
 
      memset(&buf->data[buf->num_elements], 0,
45
 
             (new_num_elements - buf->num_elements) * sizeof(*buf->data));
46
 
      buf->num_elements = new_num_elements;
47
 
   }
48
 
}
49
 
 
50
 
void
51
 
util_idalloc_init(struct util_idalloc *buf, unsigned initial_num_ids)
52
 
{
53
 
   memset(buf, 0, sizeof(*buf));
54
 
   assert(initial_num_ids);
55
 
   util_idalloc_resize(buf, DIV_ROUND_UP(initial_num_ids, 32));
56
 
}
57
 
 
58
 
void
59
 
util_idalloc_fini(struct util_idalloc *buf)
60
 
{
61
 
   if (buf->data)
62
 
      free(buf->data);
63
 
}
64
 
 
65
 
unsigned
66
 
util_idalloc_alloc(struct util_idalloc *buf)
67
 
{
68
 
   unsigned num_elements = buf->num_elements;
69
 
 
70
 
   for (unsigned i = buf->lowest_free_idx; i < num_elements; i++) {
71
 
      if (buf->data[i] == 0xffffffff)
72
 
         continue;
73
 
 
74
 
      unsigned bit = ffs(~buf->data[i]) - 1;
75
 
      buf->data[i] |= 1u << bit;
76
 
      buf->lowest_free_idx = i;
77
 
      return i * 32 + bit;
78
 
   }
79
 
 
80
 
   /* No slots available, resize and return the first free. */
81
 
   util_idalloc_resize(buf, MAX2(num_elements, 1) * 2);
82
 
 
83
 
   buf->lowest_free_idx = num_elements;
84
 
   buf->data[num_elements] |= 1;
85
 
   return num_elements * 32;
86
 
}
87
 
 
88
 
static unsigned
89
 
find_free_block(struct util_idalloc *buf, unsigned start)
90
 
{
91
 
   for (unsigned i = start; i < buf->num_elements; i++) {
92
 
      if (!buf->data[i])
93
 
         return i;
94
 
   }
95
 
   return buf->num_elements;
96
 
}
97
 
 
98
 
/* Allocate a range of consecutive IDs. Return the first ID. */
99
 
unsigned
100
 
util_idalloc_alloc_range(struct util_idalloc *buf, unsigned num)
101
 
{
102
 
   if (num == 1)
103
 
      return util_idalloc_alloc(buf);
104
 
 
105
 
   unsigned num_alloc = DIV_ROUND_UP(num, 32);
106
 
   unsigned num_elements = buf->num_elements;
107
 
   unsigned base = find_free_block(buf, buf->lowest_free_idx);
108
 
 
109
 
   while (1) {
110
 
      unsigned i;
111
 
      for (i = base;
112
 
           i < num_elements && i - base < num_alloc && !buf->data[i]; i++);
113
 
 
114
 
      if (i - base == num_alloc)
115
 
         goto ret; /* found */
116
 
 
117
 
      if (i == num_elements)
118
 
         break; /* not found */
119
 
 
120
 
      /* continue searching */
121
 
      base = !buf->data[i] ? i : i + 1;
122
 
   }
123
 
 
124
 
   /* No slots available, allocate more. */
125
 
   util_idalloc_resize(buf, num_elements * 2 + num_alloc);
126
 
 
127
 
ret:
128
 
   /* Mark the bits as used. */
129
 
   for (unsigned i = base; i < base + num_alloc - (num % 32 != 0); i++)
130
 
      buf->data[i] = 0xffffffff;
131
 
   if (num % 32 != 0)
132
 
      buf->data[base + num_alloc - 1] |= BITFIELD_MASK(num % 32);
133
 
 
134
 
   if (buf->lowest_free_idx == base)
135
 
      buf->lowest_free_idx = base + num / 32;
136
 
 
137
 
   /* Validate this algorithm. */
138
 
   for (unsigned i = 0; i < num; i++)
139
 
      assert(util_idalloc_exists(buf, base * 32 + i));
140
 
 
141
 
   return base * 32;
142
 
}
143
 
 
144
 
void
145
 
util_idalloc_free(struct util_idalloc *buf, unsigned id)
146
 
{
147
 
   assert(id / 32 < buf->num_elements);
148
 
   unsigned idx = id / 32;
149
 
   buf->lowest_free_idx = MIN2(idx, buf->lowest_free_idx);
150
 
   buf->data[idx] &= ~(1 << (id % 32));
151
 
}
152
 
 
153
 
void
154
 
util_idalloc_reserve(struct util_idalloc *buf, unsigned id)
155
 
{
156
 
   if (id / 32 >= buf->num_elements)
157
 
      util_idalloc_resize(buf, (id / 32 + 1) * 2);
158
 
   buf->data[id / 32] |= 1u << (id % 32);
159
 
}
160
 
 
161
 
void
162
 
util_idalloc_mt_init(struct util_idalloc_mt *buf,
163
 
                     unsigned initial_num_ids, bool skip_zero)
164
 
{
165
 
   simple_mtx_init(&buf->mutex, mtx_plain);
166
 
   util_idalloc_init(&buf->buf, initial_num_ids);
167
 
   buf->skip_zero = skip_zero;
168
 
 
169
 
   if (skip_zero) {
170
 
      ASSERTED unsigned zero = util_idalloc_alloc(&buf->buf);
171
 
      assert(zero == 0);
172
 
   }
173
 
}
174
 
 
175
 
/* Callback for drivers using u_threaded_context (abbreviated as tc). */
176
 
void
177
 
util_idalloc_mt_init_tc(struct util_idalloc_mt *buf)
178
 
{
179
 
   util_idalloc_mt_init(buf, 1 << 16, true);
180
 
}
181
 
 
182
 
void
183
 
util_idalloc_mt_fini(struct util_idalloc_mt *buf)
184
 
{
185
 
   util_idalloc_fini(&buf->buf);
186
 
   simple_mtx_destroy(&buf->mutex);
187
 
}
188
 
 
189
 
unsigned
190
 
util_idalloc_mt_alloc(struct util_idalloc_mt *buf)
191
 
{
192
 
   simple_mtx_lock(&buf->mutex);
193
 
   unsigned id = util_idalloc_alloc(&buf->buf);
194
 
   simple_mtx_unlock(&buf->mutex);
195
 
   return id;
196
 
}
197
 
 
198
 
void
199
 
util_idalloc_mt_free(struct util_idalloc_mt *buf, unsigned id)
200
 
{
201
 
   if (id == 0 && buf->skip_zero)
202
 
      return;
203
 
 
204
 
   simple_mtx_lock(&buf->mutex);
205
 
   util_idalloc_free(&buf->buf, id);
206
 
   simple_mtx_unlock(&buf->mutex);
207
 
}