1 /**
2 * Copyright (C) Mellanox Technologies Ltd. 2001-2013. ALL RIGHTS RESERVED.
3 * Copyright (C) Huawei Technologies Co., Ltd. 2020. ALL RIGHTS RESERVED.
4 *
5 * See file LICENSE for terms.
6 */
7
8 #ifndef PTR_ARRAY_H_
9 #define PTR_ARRAY_H_
10
11 #include <ucs/sys/math.h>
12 #include <ucs/debug/memtrack.h>
13 #include <ucs/type/spinlock.h>
14 #include <ucs/debug/assert.h>
15
16 /*
17 * Array element layout:
18 *
19 * 64 32 1 0
20 * +-----------------+----------------+---+
21 * free: | free_ahead | next index | 1 |
22 * +-----------------+----------------+---+
23 * used: | user pointer | 0 |
24 * +-----------------+----------------+---+
25 *
26 *
27 * free_ahead is the number of consecutive free elements ahead.
28 *
29 * The remove / insert algorithm works as follows:
30 * On remove of an index: If start[index+1] is free ==>
31 * start[index].free_elements_ahead = start[index+1].free_elements_ahead+1
32 * Then, the removed index is pushed to the HEAD of the freelist.
33 * NOTE, that if start[index+1] is free ==> It's already in the freelist !!!
34 *
35 * On insert, we fetch the first entry of the freelist and we rely on the
36 * fact that the remove/insert mechanism effectively implements a LIFO
37 * freelist, i.e. the last item pushed into the freelist will be fetched
38 * first ==> There is no chance that index+1 will be fetched before index,
39 * since index+1 was already in the list before index was put into the list.
40 *
41 * Therefore, we can rely on the free_size_ahead field to tell how many free
42 * elements are from any index in the freelist.
43 *
44 * To clarify, "free_ahead" is a best-effort optimization, so when it is not
45 * updated on removal - the for-each code runs slower, but still correctly.
46 * This decision was made in order to preserve the O(1) performance of
47 * ucs_ptr_array_remove() - at the expense of ptr_array_for_each() performance.
48 * If we wanted to favor ptr_array_for_each() we had to update "free_ahead"
49 * values in all the empty cells before the changed one, a noticeable overhead.
50 * Instead, the for-each checks if the cell is empty even if it's indicated as
51 * such by "free_ahead". As for insert() - a new cell can be either inserted
52 * right after an occupied cell (no need to update "free_ahead") or instead of
53 * a removed cell (so that "free_ahead" already points to it). The resulting
54 * effect is that "free_ahead" may have "false positives" but never "false
55 * negatives". Set() is different, because it "messes" with this logic - and
56 * can create that "false negative". This is why it requires such a complicated
57 * update of the "free_ahead" (unless the set overwrites an occupied cell).
58 *
59 */
60 typedef uint64_t ucs_ptr_array_elem_t;
61
62
63 /**
64 * A sparse array of pointers.
65 */
66 typedef struct ucs_ptr_array {
67 ucs_ptr_array_elem_t *start;
68 unsigned freelist;
69 unsigned size;
70 #ifdef ENABLE_MEMTRACK
71 char name[64];
72 #endif
73 } ucs_ptr_array_t;
74
75
76 /* Flags added to lower bits of the value */
77 #define UCS_PTR_ARRAY_FLAG_FREE ((unsigned long)0x01) /* Slot is free */
78
79 #define UCS_PTR_ARRAY_FREE_AHEAD_SHIFT 32
80 #define UCS_PTR_ARRAY_FREE_AHEAD_MASK (((ucs_ptr_array_elem_t)-1) & ~UCS_MASK(UCS_PTR_ARRAY_FREE_AHEAD_SHIFT))
81 #define UCS_PTR_ARRAY_NEXT_SHIFT 1
82 #define UCS_PTR_ARRAY_NEXT_MASK (UCS_MASK(UCS_PTR_ARRAY_FREE_AHEAD_SHIFT) & ~UCS_MASK(UCS_PTR_ARRAY_NEXT_SHIFT))
83 #define UCS_PTR_ARRAY_SENTINEL (UCS_PTR_ARRAY_NEXT_MASK >> UCS_PTR_ARRAY_NEXT_SHIFT)
84
85 #define __ucs_ptr_array_is_free(_elem) \
86 ((uintptr_t)(_elem) & UCS_PTR_ARRAY_FLAG_FREE)
87
88
89 /**
90 * Initialize the array.
91 *
92 * @param [in] ptr_array Pointer to a ptr array.
93 * @param [in] name The name of the ptr array.
94 */
95 void ucs_ptr_array_init(ucs_ptr_array_t *ptr_array, const char *name);
96
97
98 /**
99 * Cleanup the array.
100 *
101 * @param ptr_array Pointer to a ptr array.
102 *
103 * @note All values should already be removed from it.
104 */
105 void ucs_ptr_array_cleanup(ucs_ptr_array_t *ptr_array);
106
107
108 /**
109 * Insert a pointer to the array.
110 *
111 * @param [in] ptr_array Pointer to a ptr array.
112 * @param [in] value Pointer to insert. Must be 8-byte aligned.
113 *
114 * @return The index to which the value was inserted.
115 *
116 * Complexity: amortized O(1)
117 *
118 * @note The array will grow if needed.
119 */
120 unsigned ucs_ptr_array_insert(ucs_ptr_array_t *ptr_array, void *value);
121
122
123 /**
124 * Set a pointer in the array, overwriting the contents of the slot.
125 *
126 * @param [in] ptr_array Pointer to a ptr array.
127 * @param [in] element_index Index of slot.
128 * @param [in] new_val Value to put into slot given by index.
129 *
130 * Complexity: O(n)
131 */
132 void ucs_ptr_array_set(ucs_ptr_array_t *ptr_array, unsigned element_index,
133 void *new_val);
134
135
136 /**
137 * Remove a pointer from the array.
138 *
139 * @param [in] ptr_array Pointer to a ptr array.
140 * @param [in] element_index Index to remove from.
141 *
142 * Complexity: O(1)
143 */
144 void ucs_ptr_array_remove(ucs_ptr_array_t *ptr_array, unsigned element_index);
145
146
147 /**
148 * Replace pointer in the array, assuming the slot is occupied.
149 *
150 * @param [in] ptr_array Pointer to a ptr array.
151 * @param [in] element_index Index of slot.
152 * @param [in] new_val Value to put into slot given by index.
153 *
154 * @return Old value of the slot
155 */
156 void *ucs_ptr_array_replace(ucs_ptr_array_t *ptr_array, unsigned element_index,
157 void *new_val);
158
159
160 /**
161 * Get the current size of the ptr array
162 *
163 * @param [in] ptr_array Pointer to a ptr array.
164 *
165 * @return Size of the ptr array.
166 */
167 static UCS_F_ALWAYS_INLINE unsigned
ucs_ptr_array_get_size(ucs_ptr_array_t * ptr_array)168 ucs_ptr_array_get_size(ucs_ptr_array_t *ptr_array)
169 {
170 return ptr_array->size;
171 }
172
173
174 /**
175 * Retrieve a value from the array.
176 *
177 * @param [in] _ptr_array Pointer to a ptr array.
178 * @param [in] _index Index to retrieve the value from.
179 * @param [out] _var Filled with the value.
180 *
181 * @return Whether the value is present and valid.
182 *
183 * Complexity: O(1)
184 */
185 #define ucs_ptr_array_lookup(_ptr_array, _index, _var) \
186 (((_index) >= (_ptr_array)->size) ? \
187 (UCS_V_INITIALIZED(_var), 0) : \
188 !__ucs_ptr_array_is_free(_var = (void*)((_ptr_array)->start[_index])))
189
190
191 /**
192 * For-each user function: Calculates how many free elements are ahead.
193 *
194 * @param [in] ptr_array Pointer to a ptr array.
195 * @param [in] element_index Index of slot
196 *
197 * @return size_elem - The number of free elements ahead if free, if not 1.
198 */
199 static UCS_F_ALWAYS_INLINE uint32_t
__ucs_ptr_array_for_each_get_step_size(ucs_ptr_array_t * ptr_array,unsigned element_index)200 __ucs_ptr_array_for_each_get_step_size(ucs_ptr_array_t *ptr_array,
201 unsigned element_index)
202 {
203 uint32_t size_elem;
204 ucs_ptr_array_elem_t elem = ptr_array->start[element_index];
205
206 if (ucs_unlikely(__ucs_ptr_array_is_free((ucs_ptr_array_elem_t)elem))) {
207 size_elem = (elem >> UCS_PTR_ARRAY_FREE_AHEAD_SHIFT);
208 } else {
209 size_elem = 1;
210 }
211
212 /* Prefetch the next item */
213 ucs_prefetch(&ptr_array->start[element_index + size_elem]);
214 ucs_assert(size_elem > 0);
215
216 return size_elem;
217 }
218
219
220 /**
221 * Check if element is free.
222 *
223 * @param [in] _elem An element in the ptr array.
224 *
225 * @return 1 if the element is free and 0 if it's occupied.
226 */
227 #define __ucs_ptr_array_is_free(_elem) ((uintptr_t)(_elem) & UCS_PTR_ARRAY_FLAG_FREE)
228
229
230 /**
231 * Iterate over all valid elements in the array.
232 *
233 * @param [out] _var Pointer to current array element in the foreach.
234 * @param [out] _index Index variable to use as iterator (unsigned).
235 * @param [in] _ptr_array Pointer to a ptr array.
236 */
237 #define ucs_ptr_array_for_each(_var, _index, _ptr_array) \
238 for ((_index) = 0; ((_index) < (_ptr_array)->size); \
239 (_index) += __ucs_ptr_array_for_each_get_step_size((_ptr_array), (_index))) \
240 if ((ucs_likely(!__ucs_ptr_array_is_free( \
241 (ucs_ptr_array_elem_t)((_var) = (void *)((_ptr_array)->start[(_index)]))))))
242
243
244 /**
245 * Locked interface
246 */
247
248
249 /* Locked ptr array */
250 typedef struct ucs_ptr_array_locked {
251 ucs_ptr_array_t super;
252 ucs_recursive_spinlock_t lock;
253 } ucs_ptr_array_locked_t;
254
255
256 /**
257 * Locked array init
258 *
259 * @param [in] locked_ptr_array Pointer to a locked ptr array.
260 * @param [in] name The name of the ptr array.
261 *
262 * @return Success or failure.
263 */
264 ucs_status_t
265 ucs_ptr_array_locked_init(ucs_ptr_array_locked_t *locked_ptr_array,
266 const char *name);
267
268
269 /**
270 * Cleanup the locked array.
271 *
272 * @param [in] locked_ptr_array Pointer to a locked ptr array.
273 *
274 * @note All values should already be removed from it.
275 */
276 void ucs_ptr_array_locked_cleanup(ucs_ptr_array_locked_t *locked_ptr_array);
277
278
279 /**
280 * Insert a pointer to the locked array.
281 *
282 * @param [in] locked_ptr_array Pointer to a locked ptr array.
283 * @param [in] value Pointer to insert. Must be 8-byte aligned.
284 *
285 * @return The index to which the value was inserted.
286 *
287 * Complexity: Amortized O(1)
288 *
289 * @note The array will grow if needed.
290 */
291 unsigned ucs_ptr_array_locked_insert(ucs_ptr_array_locked_t *locked_ptr_array,
292 void *value);
293
294
295 /**
296 * Set a pointer in the array, overwriting the contents of the slot.
297 *
298 * @param [in] locked_ptr_array Pointer to a locked ptr array.
299 * @param [in] element_index Index of slot.
300 * @param [in] new_val Value to put into slot given by index.
301 *
302 * Complexity: O(n)
303 */
304 void ucs_ptr_array_locked_set(ucs_ptr_array_locked_t *locked_ptr_array,
305 unsigned element_index, void *new_val);
306
307
308 /**
309 * Remove a pointer from the locked array.
310 *
311 * @param [in] locked_ptr_array Pointer to a locked ptr array.
312 * @param [in] element_index Index to remove from.
313 *
314 * Complexity: O(1)
315 */
316 void ucs_ptr_array_locked_remove(ucs_ptr_array_locked_t *locked_ptr_array,
317 unsigned element_index);
318
319
320 /**
321 * Replace pointer in the locked array, assuming the slot is occupied.
322 *
323 * @param [in] locked_ptr_array Pointer to a locked ptr array.
324 * @param [in] element_index Index of slot.
325 * @param [in] new_val Value to put into slot given by index.
326 *
327 * @return Old value of the slot
328 *
329 * Complexity: O(1)
330 */
331 void *ucs_ptr_array_locked_replace(ucs_ptr_array_locked_t *locked_ptr_array,
332 unsigned element_index, void *new_val);
333
334
335 /**
336 * Acquire the ptr_array lock.
337 *
338 * @param [in] _locked_ptr_array Pointer to a locked ptr array.
339 */
340 #define ucs_ptr_array_locked_acquire_lock(_locked_ptr_array) \
341 ucs_recursive_spin_lock(&(_locked_ptr_array)->lock)
342
343
344 /**
345 * Release the ptr_array lock.
346 *
347 * @param [in] _locked_ptr_array Pointer to a locked ptr array.
348 */
349 #define ucs_ptr_array_locked_release_lock(_locked_ptr_array) \
350 ucs_recursive_spin_unlock(&(_locked_ptr_array)->lock)
351
352
353 /**
354 * Retrieves a value from the locked array.
355 *
356 * @param [in] locked_ptr_array Pointer to a locked ptr array.
357 * @param [in] element_index Index to retrieve the value from.
358 * @param [out] var Filled with the value.
359 *
360 * @return Whether the value is present and valid.
361 *
362 * Complexity: O(1)
363 */
364 static UCS_F_ALWAYS_INLINE int
ucs_ptr_array_locked_lookup(ucs_ptr_array_locked_t * locked_ptr_array,unsigned element_index,void ** var)365 ucs_ptr_array_locked_lookup(ucs_ptr_array_locked_t *locked_ptr_array,
366 unsigned element_index, void **var)
367 {
368 int present;
369
370 ucs_ptr_array_locked_acquire_lock(locked_ptr_array);
371 present = ucs_ptr_array_lookup(&locked_ptr_array->super, element_index,
372 *var);
373 ucs_ptr_array_locked_release_lock(locked_ptr_array);
374
375 return present;
376 }
377
378
379 /**
380 * Get the current size of the locked ptr array
381 *
382 * @param [in] locked_ptr_array Pointer to a locked ptr array.
383 *
384 * @return Size of the locked ptr array.
385 */
386 static UCS_F_ALWAYS_INLINE unsigned
ucs_ptr_array_locked_get_size(ucs_ptr_array_locked_t * locked_ptr_array)387 ucs_ptr_array_locked_get_size(ucs_ptr_array_locked_t *locked_ptr_array)
388 {
389 return ucs_ptr_array_get_size(&locked_ptr_array->super);
390 }
391
392
393 /**
394 * If foreach locked ptr_array is finalized, releases lock.
395 *
396 * @param [in] locked_ptr_array Pointer to a locked ptr array.
397 * @param [in] element_index The current for loop index.
398 *
399 * @return is_continue_loop for the for() loop end condition.
400 */
401 static UCS_F_ALWAYS_INLINE int
__ucx_ptr_array_locked_foreach_finalize(ucs_ptr_array_locked_t * locked_ptr_array,uint32_t element_index)402 __ucx_ptr_array_locked_foreach_finalize(ucs_ptr_array_locked_t *locked_ptr_array,
403 uint32_t element_index)
404 {
405 if (element_index < locked_ptr_array->super.size) {
406 return 1;
407 }
408
409 ucs_ptr_array_locked_release_lock(locked_ptr_array);
410 return 0;
411 }
412
413
414 /**
415 * Iterate over all valid elements in the locked array.
416 *
417 * Please notice that using break or return are not allowed in
418 * this implementation.
419 * Using break or return would require releasing the lock before by calling,
420 * ucs_ptr_array_locked_release_lock(_locked_ptr_array);
421 *
422 * @param [out] _var Pointer to current array element in the foreach.
423 * @param [out] _index Index variable to use as iterator (unsigned).
424 * @param [in] _locked_ptr_array Pointer to a locked ptr array.
425 */
426 #define ucs_ptr_array_locked_for_each(_var, _index, _locked_ptr_array) \
427 for ((_index) = 0, \
428 ucs_ptr_array_locked_acquire_lock(_locked_ptr_array); \
429 __ucx_ptr_array_locked_foreach_finalize(_locked_ptr_array, (_index)); \
430 (_index) += __ucs_ptr_array_for_each_get_step_size((&(_locked_ptr_array)->super), (_index))) \
431 if ((ucs_likely(!__ucs_ptr_array_is_free( \
432 (ucs_ptr_array_elem_t)((_var) = \
433 (void *)((&(_locked_ptr_array)->super)->start[(_index)]))))))
434
435 #endif /* PTR_ARRAY_H_ */
436
437