Blender  V3.3
BLI_memiter.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
26 #include <stdlib.h>
27 #include <string.h>
28 
29 #include "BLI_asan.h"
30 #include "BLI_utildefines.h"
31 
32 #include "BLI_memiter.h" /* own include */
33 
34 #include "MEM_guardedalloc.h"
35 
36 #include "BLI_strict_flags.h" /* keep last */
37 
38 /* TODO: Valgrind. */
39 
40 typedef uintptr_t data_t;
42 
43 /* Write the chunk terminator on adding each element.
44  * typically we rely on the 'count' to avoid iterating past the end. */
45 // #define USE_TERMINATE_PARANOID
46 
47 /* Currently totalloc isn't used. */
48 // #define USE_TOTALLOC
49 
50 /* pad must be power of two */
51 #define PADUP(num, pad) (((num) + ((pad)-1)) & ~((pad)-1))
52 
53 typedef struct BLI_memiter_elem {
57 
58 typedef struct BLI_memiter_chunk {
68 
69 typedef struct BLI_memiter {
70  /* A pointer to 'head' is needed so we can iterate in the order allocated. */
74  /* Used unless a large element is requested.
75  * (which should be very rare!). */
78 #ifdef USE_TOTALLOC
79  uint totalloc;
80 #endif
82 
84 {
85  return (PADUP(size, (uint)sizeof(data_t))) / (uint)sizeof(data_t);
86 }
87 
89 {
91 
92  BLI_asan_unpoison(elem, sizeof(BLI_memiter_elem));
93 
94  elem->size = (offset_t)(((data_t *)mi->tail) - mi->data_curr);
95  BLI_assert(elem->size < 0);
96 }
97 
98 static void memiter_init(BLI_memiter *mi)
99 {
100  mi->head = NULL;
101  mi->tail = NULL;
102  mi->data_curr = NULL;
103  mi->data_last = NULL;
104  mi->count = 0;
105 #ifdef USE_TOTALLOC
106  mi->totalloc = 0;
107 #endif
108 }
109 
110 /* -------------------------------------------------------------------- */
115 {
116  BLI_memiter *mi = MEM_mallocN(sizeof(BLI_memiter), "BLI_memiter");
117  memiter_init(mi);
118 
119  /* Small values are used for tests to check for correctness,
120  * but otherwise not that useful. */
121  const uint slop_space = (sizeof(BLI_memiter_chunk) + MEM_SIZE_OVERHEAD);
122  if (chunk_size_min >= 1024) {
123  /* As long as the input is a power of 2, this will give efficient sizes. */
124  chunk_size_min -= slop_space;
125  }
126 
127  mi->chunk_size_in_bytes_min = chunk_size_min;
128  return mi;
129 }
130 
131 void *BLI_memiter_alloc(BLI_memiter *mi, uint elem_size)
132 {
133  const uint data_offset = data_offset_from_size(elem_size);
134  data_t *data_curr_next = mi->data_curr + (1 + data_offset);
135 
136  if (UNLIKELY(mi->data_curr == NULL) || (data_curr_next > mi->data_last)) {
137 
138 #ifndef USE_TERMINATE_PARANOID
139  if (mi->data_curr != NULL) {
141  }
142 #endif
143 
144  uint chunk_size_in_bytes = mi->chunk_size_in_bytes_min;
145  if (UNLIKELY(chunk_size_in_bytes < elem_size + (uint)sizeof(data_t[2]))) {
146  chunk_size_in_bytes = elem_size + (uint)sizeof(data_t[2]);
147  }
148  uint chunk_size = data_offset_from_size(chunk_size_in_bytes);
150  sizeof(BLI_memiter_chunk) + (chunk_size * sizeof(data_t)), "BLI_memiter_chunk");
151 
152  if (mi->head == NULL) {
153  BLI_assert(mi->tail == NULL);
154  mi->head = chunk;
155  }
156  else {
157  mi->tail->next = chunk;
158  }
159  mi->tail = chunk;
160  chunk->next = NULL;
161 
162  mi->data_curr = chunk->data;
163  mi->data_last = chunk->data + (chunk_size - 1);
164  data_curr_next = mi->data_curr + (1 + data_offset);
165 
166  BLI_asan_poison(chunk->data, chunk_size * sizeof(data_t));
167  }
168 
169  BLI_assert(data_curr_next <= mi->data_last);
170 
172 
173  BLI_asan_unpoison(elem, sizeof(BLI_memiter_elem) + elem_size);
174 
175  elem->size = (offset_t)elem_size;
176  mi->data_curr = data_curr_next;
177 
178 #ifdef USE_TERMINATE_PARANOID
180 #endif
181 
182  mi->count += 1;
183 
184 #ifdef USE_TOTALLOC
185  mi->totalloc += elem_size;
186 #endif
187 
188  return elem->data;
189 }
190 
191 void *BLI_memiter_calloc(BLI_memiter *mi, uint elem_size)
192 {
193  void *data = BLI_memiter_alloc(mi, elem_size);
194  memset(data, 0, elem_size);
195  return data;
196 }
197 
198 void BLI_memiter_alloc_from(BLI_memiter *mi, uint elem_size, const void *data_from)
199 {
200  void *data = BLI_memiter_alloc(mi, elem_size);
201  memcpy(data, data_from, elem_size);
202 }
203 
205 {
206  BLI_memiter_chunk *chunk = mi->head;
207  while (chunk) {
208  BLI_memiter_chunk *chunk_next = chunk->next;
209 
210  /* Unpoison memory because MEM_freeN might overwrite it. */
211  BLI_asan_unpoison(chunk, MEM_allocN_len(chunk));
212 
213  MEM_freeN(chunk);
214  chunk = chunk_next;
215  }
216 }
217 
219 {
220  memiter_free_data(mi);
221  MEM_freeN(mi);
222 }
223 
225 {
226  memiter_free_data(mi);
227  memiter_init(mi);
228 }
229 
231 {
232  return mi->count;
233 }
234 
237 /* -------------------------------------------------------------------- */
242 {
243  if (mi->head != NULL) {
244  BLI_memiter_chunk *chunk = mi->head;
245  BLI_memiter_elem *elem = (BLI_memiter_elem *)chunk->data;
246  return elem->data;
247  }
248  return NULL;
249 }
250 
252 {
253  if (mi->head != NULL) {
254  BLI_memiter_chunk *chunk = mi->head;
255  BLI_memiter_elem *elem = (BLI_memiter_elem *)chunk->data;
256  *r_size = (uint)elem->size;
257  return elem->data;
258  }
259  return NULL;
260 }
261 
264 /* -------------------------------------------------------------------- */
276 {
277  iter->elem = mi->head ? (BLI_memiter_elem *)mi->head->data : NULL;
278  iter->elem_left = mi->count;
279 }
280 
282 {
283  return iter->elem_left != 0;
284 }
285 
287 {
288  BLI_assert(iter->elem->size < 0);
289  BLI_memiter_chunk *chunk = (BLI_memiter_chunk *)(((data_t *)iter->elem) + iter->elem->size);
290  chunk = chunk->next;
291  iter->elem = chunk ? (BLI_memiter_elem *)chunk->data : NULL;
292  BLI_assert(iter->elem == NULL || iter->elem->size >= 0);
293 }
294 
296 {
297  if (iter->elem_left != 0) {
298  iter->elem_left -= 1;
299  if (UNLIKELY(iter->elem->size < 0)) {
300  memiter_chunk_step(iter);
301  }
302  BLI_assert(iter->elem->size >= 0);
303  uint size = (uint)iter->elem->size;
304  *r_size = size; /* <-- only difference */
305  data_t *data = iter->elem->data;
307  return (void *)data;
308  }
309  return NULL;
310 }
311 
313 {
314  if (iter->elem_left != 0) {
315  iter->elem_left -= 1;
316  if (UNLIKELY(iter->elem->size < 0)) {
317  memiter_chunk_step(iter);
318  }
319  BLI_assert(iter->elem->size >= 0);
320  uint size = (uint)iter->elem->size;
321  data_t *data = iter->elem->data;
323  return (void *)data;
324  }
325  return NULL;
326 }
327 
#define BLI_asan_unpoison(addr, size)
Definition: BLI_asan.h:28
#define BLI_asan_poison(addr, size)
Definition: BLI_asan.h:23
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_INLINE
static void memiter_set_rewind_offset(BLI_memiter *mi)
Definition: BLI_memiter.c:88
void * BLI_memiter_iter_step(BLI_memiter_handle *iter)
Definition: BLI_memiter.c:312
void * BLI_memiter_calloc(BLI_memiter *mi, uint elem_size)
Definition: BLI_memiter.c:191
void BLI_memiter_clear(BLI_memiter *mi)
Definition: BLI_memiter.c:224
uintptr_t data_t
Definition: BLI_memiter.c:40
struct BLI_memiter_chunk BLI_memiter_chunk
void BLI_memiter_iter_init(BLI_memiter *mi, BLI_memiter_handle *iter)
Definition: BLI_memiter.c:275
#define PADUP(num, pad)
Definition: BLI_memiter.c:51
void * BLI_memiter_iter_step_size(BLI_memiter_handle *iter, uint *r_size)
Definition: BLI_memiter.c:295
void * BLI_memiter_elem_first_size(BLI_memiter *mi, uint *r_size)
Definition: BLI_memiter.c:251
static void memiter_init(BLI_memiter *mi)
Definition: BLI_memiter.c:98
void BLI_memiter_alloc_from(BLI_memiter *mi, uint elem_size, const void *data_from)
Definition: BLI_memiter.c:198
BLI_memiter * BLI_memiter_create(uint chunk_size_min)
Definition: BLI_memiter.c:114
uint BLI_memiter_count(const BLI_memiter *mi)
Definition: BLI_memiter.c:230
bool BLI_memiter_iter_done(const BLI_memiter_handle *iter)
Definition: BLI_memiter.c:281
struct BLI_memiter BLI_memiter
BLI_INLINE void memiter_chunk_step(BLI_memiter_handle *iter)
Definition: BLI_memiter.c:286
static void memiter_free_data(BLI_memiter *mi)
Definition: BLI_memiter.c:204
struct BLI_memiter_elem BLI_memiter_elem
void * BLI_memiter_alloc(BLI_memiter *mi, uint elem_size)
Definition: BLI_memiter.c:131
void BLI_memiter_destroy(BLI_memiter *mi)
Definition: BLI_memiter.c:218
BLI_INLINE uint data_offset_from_size(uint size)
Definition: BLI_memiter.c:83
void * BLI_memiter_elem_first(BLI_memiter *mi)
Definition: BLI_memiter.c:241
intptr_t offset_t
Definition: BLI_memiter.c:41
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
unsigned int uint
Definition: BLI_sys_types.h:67
#define UNLIKELY(x)
Read Guarded memory(de)allocation.
#define MEM_SIZE_OVERHEAD
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
size_t(* MEM_allocN_len)(const void *vmemh)
Definition: mallocn.c:26
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
static const int chunk_size
_W64 unsigned int uintptr_t
Definition: stdint.h:119
_W64 int intptr_t
Definition: stdint.h:118
struct BLI_memiter_chunk * next
Definition: BLI_memiter.c:59
data_t data[0]
Definition: BLI_memiter.c:66
data_t data[0]
Definition: BLI_memiter.c:55
struct BLI_memiter_elem * elem
Definition: BLI_memiter.h:57
data_t * data_last
Definition: BLI_memiter.c:73
uint chunk_size_in_bytes_min
Definition: BLI_memiter.c:76
struct BLI_memiter_chunk * tail
Definition: BLI_memiter.c:71
data_t * data_curr
Definition: BLI_memiter.c:72
struct BLI_memiter_chunk * head
Definition: BLI_memiter.c:71