vppinfra: refactor address sanitizer
[vpp.git] / src / vppinfra / pool.h
1 /*
2  * Copyright (c) 2015 Cisco and/or its affiliates.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at:
6  *
7  *     http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 /*
16   Copyright (c) 2001, 2002, 2003, 2004 Eliot Dresselhaus
17
18   Permission is hereby granted, free of charge, to any person obtaining
19   a copy of this software and associated documentation files (the
20   "Software"), to deal in the Software without restriction, including
21   without limitation the rights to use, copy, modify, merge, publish,
22   distribute, sublicense, and/or sell copies of the Software, and to
23   permit persons to whom the Software is furnished to do so, subject to
24   the following conditions:
25
26   The above copyright notice and this permission notice shall be
27   included in all copies or substantial portions of the Software.
28
29   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
30   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
31   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
32   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
33   LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
34   OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
35   WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
36 */
37 /** @file
38  * @brief Fixed length block allocator.
39    Pools are built from clib vectors and bitmaps. Use pools when
40    repeatedly allocating and freeing fixed-size data. Pools are
41    fast, and avoid memory fragmentation.
42  */
43
44 #ifndef included_pool_h
45 #define included_pool_h
46
47 #include <vppinfra/bitmap.h>
48 #include <vppinfra/error.h>
49
50
51 typedef struct
52 {
53   /** Bitmap of indices of free objects. */
54   uword *free_bitmap;
55
56   /** Vector of free indices.  One element for each set bit in bitmap. */
57   u32 *free_indices;
58
59   /* The following fields are set for fixed-size, preallocated pools */
60
61   /** Maximum size of the pool, in elements */
62   u32 max_elts;
63
64 } pool_header_t;
65
66 /** Get pool header from user pool pointer */
67 always_inline pool_header_t *
68 pool_header (void *v)
69 {
70   return vec_header (v);
71 }
72
73 void _pool_init_fixed (void **pool_ptr, uword elt_sz, uword max_elts,
74                        uword align);
75
76 /** initialize a fixed-size, preallocated pool */
77 #define pool_init_fixed(P, E)                                                 \
78   _pool_init_fixed ((void **) &(P), _vec_elt_sz (P), E, _vec_align (P, 0));
79
80 /** Validate a pool */
81 always_inline void
82 pool_validate (void *v)
83 {
84   pool_header_t *p = pool_header (v);
85   uword i, n_free_bitmap;
86
87   if (!v)
88     return;
89
90   n_free_bitmap = clib_bitmap_count_set_bits (p->free_bitmap);
91   ASSERT (n_free_bitmap == vec_len (p->free_indices));
92   for (i = 0; i < vec_len (p->free_indices); i++)
93     ASSERT (clib_bitmap_get (p->free_bitmap, p->free_indices[i]) == 1);
94 }
95
96 /** Number of active elements in a pool.
97  * @return Number of active elements in a pool
98  */
99 always_inline uword
100 pool_elts (void *v)
101 {
102   uword ret = vec_len (v);
103   if (v)
104     ret -= vec_len (pool_header (v)->free_indices);
105   return ret;
106 }
107
108 /** Number of elements in pool vector.
109
110     @note You probably want to call pool_elts() instead.
111 */
112 #define pool_len(p)     vec_len(p)
113
114 /** Number of elements in pool vector (usable as an lvalue)
115
116     @note You probably don't want to use this macro.
117 */
118 #define _pool_len(p)    _vec_len(p)
119
120 /** Memory usage of pool header. */
121 always_inline uword
122 pool_header_bytes (void *v)
123 {
124   pool_header_t *p = pool_header (v);
125
126   if (!v)
127     return 0;
128
129   return vec_bytes (p->free_bitmap) + vec_bytes (p->free_indices);
130 }
131
132 /** Memory usage of pool. */
133 #define pool_bytes(P) (vec_bytes (P) + pool_header_bytes (P))
134
135 /** Local variable naming macro. */
136 #define _pool_var(v) _pool_##v
137
138 /** Number of elements that can fit into pool with current allocation */
139 #define pool_max_len(P) vec_max_len (P)
140
141 /** Number of free elements in pool */
142 static_always_inline uword
143 _pool_free_elts (void *p, uword elt_sz)
144 {
145   pool_header_t *ph;
146   uword n_free;
147
148   if (p == 0)
149     return 0;
150
151   ph = pool_header (p);
152
153   n_free = vec_len (ph->free_indices);
154
155   /* Fixed-size pools have max_elts set non-zero */
156   if (ph->max_elts == 0)
157     n_free += _vec_max_len (p, elt_sz) - vec_len (p);
158
159   return n_free;
160 }
161
162 #define pool_free_elts(P) _pool_free_elts ((void *) (P), _vec_elt_sz (P))
163
164 /** Allocate an object E from a pool P (general version).
165
166    First search free list.  If nothing is free extend vector of objects.
167 */
168
169 static_always_inline void
170 _pool_get (void **pp, void **ep, uword align, int zero, uword elt_sz)
171 {
172   uword len = 0;
173   void *p = pp[0];
174   void *e;
175
176   if (p)
177     {
178       pool_header_t *ph = pool_header (p);
179       uword n_free = vec_len (ph->free_indices);
180
181       if (n_free)
182         {
183           uword index = ph->free_indices[n_free - 1];
184           e = p + index * elt_sz;
185           ph->free_bitmap =
186             clib_bitmap_andnoti_notrim (ph->free_bitmap, index);
187           vec_set_len (ph->free_indices, n_free - 1);
188           clib_mem_unpoison (e, elt_sz);
189           goto done;
190         }
191
192       if (ph->max_elts)
193         {
194           clib_warning ("can't expand fixed-size pool");
195           os_out_of_memory ();
196         }
197     }
198
199   len = vec_len (p);
200
201   /* Nothing on free list, make a new element and return it. */
202   p =
203     _vec_realloc_inline (p, len + 1, elt_sz, sizeof (pool_header_t), align, 0);
204   e = p + len * elt_sz;
205
206   _vec_update_pointer (pp, p);
207
208 done:
209   ep[0] = e;
210   if (zero)
211     clib_memset_u8 (e, 0, elt_sz);
212 }
213
214 #define _pool_get_aligned_internal(P, E, A, Z)                                \
215   _pool_get ((void **) &(P), (void **) &(E), _vec_align (P, A), Z,            \
216              _vec_elt_sz (P))
217
218 /** Allocate an object E from a pool P with alignment A */
219 #define pool_get_aligned(P,E,A) _pool_get_aligned_internal(P,E,A,0)
220
221 /** Allocate an object E from a pool P with alignment A and zero it */
222 #define pool_get_aligned_zero(P,E,A) _pool_get_aligned_internal(P,E,A,1)
223
224 /** Allocate an object E from a pool P (unspecified alignment). */
225 #define pool_get(P,E) pool_get_aligned(P,E,0)
226
227 /** Allocate an object E from a pool P and zero it */
228 #define pool_get_zero(P,E) pool_get_aligned_zero(P,E,0)
229
230 always_inline int
231 _pool_get_will_expand (void *p, uword elt_sz)
232 {
233   pool_header_t *ph;
234   uword len;
235
236   if (p == 0)
237     return 1;
238
239   ph = pool_header (p);
240
241   if (ph->max_elts)
242     len = ph->max_elts;
243   else
244     len = vec_len (ph->free_indices);
245
246   /* Free elements, certainly won't expand */
247   if (len > 0)
248     return 0;
249
250   return _vec_resize_will_expand (p, 1, elt_sz);
251 }
252
253 #define pool_get_will_expand(P) _pool_get_will_expand (P, sizeof ((P)[0]))
254
255 always_inline int
256 _pool_put_will_expand (void *p, uword index, uword elt_sz)
257 {
258   pool_header_t *ph = pool_header (p);
259
260   if (clib_bitmap_will_expand (ph->free_bitmap, index))
261     return 1;
262
263   if (vec_resize_will_expand (ph->free_indices, 1))
264     return 1;
265
266   return 0;
267 }
268
269 #define pool_put_will_expand(P, E) _pool_put_will_expand (P, (E) - (P), sizeof ((P)[0])
270
271 /** Use free bitmap to query whether given element is free. */
272 static_always_inline int
273 pool_is_free_index (void *p, uword index)
274 {
275   pool_header_t *ph = pool_header (p);
276   return index < vec_len (p) ? clib_bitmap_get (ph->free_bitmap, index) : 1;
277 }
278
279 #define pool_is_free(P, E) pool_is_free_index ((void *) (P), (E) - (P))
280
281 /** Free an object E in pool P. */
282 static_always_inline void
283 _pool_put_index (void *p, uword index, uword elt_sz)
284 {
285   pool_header_t *ph = pool_header (p);
286
287   ASSERT (index < ph->max_elts ? ph->max_elts : vec_len (p));
288   ASSERT (!pool_is_free_index (p, index));
289
290   /* Add element to free bitmap and to free list. */
291   ph->free_bitmap = clib_bitmap_ori_notrim (ph->free_bitmap, index);
292
293   /* Preallocated pool? */
294   if (ph->max_elts)
295     {
296       ph->free_indices[_vec_len (ph->free_indices)] = index;
297       vec_inc_len (ph->free_indices, 1);
298     }
299   else
300     vec_add1 (ph->free_indices, index);
301
302   clib_mem_poison (p + index * elt_sz, elt_sz);
303 }
304
305 #define pool_put_index(P, I) _pool_put_index ((void *) (P), I, _vec_elt_sz (P))
306 #define pool_put(P, E)       pool_put_index (P, (E) - (P))
307
308 /** Allocate N more free elements to pool (general version). */
309
310 static_always_inline void
311 _pool_alloc (void **pp, uword n_elts, uword align, void *heap, uword elt_sz)
312 {
313   pool_header_t *ph = pool_header (pp[0]);
314   uword len = vec_len (pp[0]);
315
316   if (ph && ph->max_elts)
317     {
318       clib_warning ("Can't expand fixed-size pool");
319       os_out_of_memory ();
320     }
321
322   pp[0] = _vec_realloc_inline (pp[0], len + n_elts, elt_sz,
323                                sizeof (pool_header_t), align, heap);
324   _vec_set_len (pp[0], len, elt_sz);
325   clib_mem_poison (pp[0] + len * elt_sz, n_elts * elt_sz);
326
327   ph = pool_header (pp[0]);
328   vec_resize (ph->free_indices, n_elts);
329   vec_dec_len (ph->free_indices, n_elts);
330   clib_bitmap_vec_validate (ph->free_bitmap, len + n_elts - 1);
331 }
332
333 #define pool_alloc_aligned_heap(P, N, A, H)                                   \
334   _pool_alloc ((void **) &(P), N, _vec_align (P, A), H, _vec_elt_sz (P))
335
336 #define pool_alloc_heap(P, N, H)    pool_alloc_aligned_heap (P, N, 0, H)
337 #define pool_alloc_aligned(P, N, A) pool_alloc_aligned_heap (P, N, A, 0)
338 #define pool_alloc(P, N)            pool_alloc_aligned_heap (P, N, 0, 0)
339
340 static_always_inline void *
341 _pool_dup (void *p, uword align, uword elt_sz)
342 {
343   pool_header_t *nph, *ph = pool_header (p);
344   uword len = vec_len (p);
345   void *n;
346
347   if (ph && ph->max_elts)
348     {
349       clib_warning ("Can't expand fixed-size pool");
350       os_out_of_memory ();
351     }
352
353   n = _vec_realloc_inline (0, len, elt_sz, sizeof (pool_header_t), align, 0);
354   nph = pool_header (n);
355   clib_memset_u8 (nph, 0, sizeof (vec_header_t));
356
357   if (len)
358     {
359       u32 *fi;
360       vec_foreach (fi, ph->free_indices)
361         clib_mem_unpoison (p + elt_sz * fi[0], elt_sz);
362
363       clib_memcpy_fast (n, p, len * elt_sz);
364
365       nph->free_bitmap = clib_bitmap_dup (ph->free_bitmap);
366       nph->free_indices = vec_dup (ph->free_indices);
367
368       vec_foreach (fi, ph->free_indices)
369         {
370           uword offset = elt_sz * fi[0];
371           clib_mem_poison (p + offset, elt_sz);
372           clib_mem_poison (n + offset, elt_sz);
373         }
374     }
375
376   return n;
377 }
378
379 /**
380  * Return copy of pool with alignment
381  *
382  * @param P pool to copy
383  * @param A alignment (may be zero)
384  * @return copy of pool
385  */
386
387 #define pool_dup_aligned(P, A)                                                \
388   _pool_dup (P, _vec_align (P, A), _vec_elt_sz (P))
389
390 /**
391  * Return copy of pool without alignment
392  *
393  * @param P pool to copy
394  * @return copy of pool
395  */
396 #define pool_dup(P) pool_dup_aligned(P,0)
397
398 /** Low-level free pool operator (do not call directly). */
399 always_inline void
400 _pool_free (void **v)
401 {
402   pool_header_t *p = pool_header (v[0]);
403   if (!p)
404     return;
405
406   clib_bitmap_free (p->free_bitmap);
407
408   vec_free (p->free_indices);
409   _vec_free (v);
410 }
411 #define pool_free(p) _pool_free ((void **) &(p))
412
413 static_always_inline uword
414 pool_get_first_index (void *pool)
415 {
416   pool_header_t *h = pool_header (pool);
417   return clib_bitmap_first_clear (h->free_bitmap);
418 }
419
420 static_always_inline uword
421 pool_get_next_index (void *pool, uword last)
422 {
423   pool_header_t *h = pool_header (pool);
424   return clib_bitmap_next_clear (h->free_bitmap, last + 1);
425 }
426
427 /** Optimized iteration through pool.
428
429     @param LO pointer to first element in chunk
430     @param HI pointer to last element in chunk
431     @param POOL pool to iterate across
432     @param BODY operation to perform
433
434     Optimized version which assumes that BODY is smart enough to
435     process multiple (LOW,HI) chunks. See also pool_foreach().
436  */
437 #define pool_foreach_region(LO,HI,POOL,BODY)                            \
438 do {                                                                    \
439   uword _pool_var (i), _pool_var (lo), _pool_var (hi), _pool_var (len); \
440   uword _pool_var (bl), * _pool_var (b);                                \
441   pool_header_t * _pool_var (p);                                        \
442                                                                         \
443   _pool_var (p) = pool_header (POOL);                                   \
444   _pool_var (b) = (POOL) ? _pool_var (p)->free_bitmap : 0;              \
445   _pool_var (bl) = vec_len (_pool_var (b));                             \
446   _pool_var (len) = vec_len (POOL);                                     \
447   _pool_var (lo) = 0;                                                   \
448                                                                         \
449   for (_pool_var (i) = 0;                                               \
450        _pool_var (i) <= _pool_var (bl);                                 \
451        _pool_var (i)++)                                                 \
452     {                                                                   \
453       uword _pool_var (m), _pool_var (f);                               \
454       _pool_var (m) = (_pool_var (i) < _pool_var (bl)                   \
455                        ? _pool_var (b) [_pool_var (i)]                  \
456                        : 1);                                            \
457       while (_pool_var (m) != 0)                                        \
458         {                                                               \
459           _pool_var (f) = first_set (_pool_var (m));                    \
460           _pool_var (hi) = (_pool_var (i) * BITS (_pool_var (b)[0])     \
461                             + min_log2 (_pool_var (f)));                \
462           _pool_var (hi) = (_pool_var (i) < _pool_var (bl)              \
463                             ? _pool_var (hi) : _pool_var (len));        \
464           _pool_var (m) ^= _pool_var (f);                               \
465           if (_pool_var (hi) > _pool_var (lo))                          \
466             {                                                           \
467               (LO) = _pool_var (lo);                                    \
468               (HI) = _pool_var (hi);                                    \
469               do { BODY; } while (0);                                   \
470             }                                                           \
471           _pool_var (lo) = _pool_var (hi) + 1;                          \
472         }                                                               \
473     }                                                                   \
474 } while (0)
475
476 /** Iterate through pool.
477
478     @param VAR A variable of same type as pool vector to be used as an
479                iterator.
480     @param POOL The pool to iterate across.
481     @param BODY The operation to perform, typically a code block. See
482                 the example below.
483
484     This macro will call @c BODY with each active pool element.
485
486     It is a bad idea to allocate or free pool element from within
487     @c pool_foreach. Build a vector of indices and dispose of them later.
488     Or call pool_flush.
489
490
491     @par Example
492     @code{.c}
493     proc_t *procs;   // a pool of processes.
494     proc_t *proc;    // pointer to one process; used as the iterator.
495
496     pool_foreach (proc, procs, ({
497         if (proc->state != PROC_STATE_RUNNING)
498             continue;
499
500         // check a running proc in some way
501         ...
502     }));
503     @endcode
504
505     @warning Because @c pool_foreach is a macro, syntax errors can be
506     difficult to find inside @c BODY, let alone actual code bugs. One
507     can temporarily split a complex @c pool_foreach into a trivial
508     @c pool_foreach which builds a vector of active indices, and a
509     vec_foreach() (or plain for-loop) to walk the active index vector.
510  */
511
512 #define pool_foreach(VAR,POOL)                                          \
513   if (POOL)                                                             \
514     for (VAR = POOL + pool_get_first_index (POOL);                      \
515          VAR < vec_end (POOL);                                          \
516          VAR = POOL + pool_get_next_index (POOL, VAR - POOL))
517
518 /** Returns pointer to element at given index.
519
520     ASSERTs that the supplied index is valid.
521     Even though one can write correct code of the form
522     @code
523         p = pool_base + index;
524     @endcode
525     use of @c pool_elt_at_index is strongly suggested.
526  */
527 #define pool_elt_at_index(p,i)                  \
528 ({                                              \
529   typeof (p) _e = (p) + (i);                    \
530   ASSERT (! pool_is_free (p, _e));              \
531   _e;                                           \
532 })
533
534 /** Return next occupied pool index after @c i, useful for safe iteration. */
535 #define pool_next_index(P,I)                                            \
536 ({                                                                      \
537   pool_header_t * _pool_var (p) = pool_header (P);                      \
538   uword _pool_var (rv) = (I) + 1;                                       \
539                                                                         \
540   _pool_var(rv) =                                                       \
541     (_pool_var (rv) < vec_len (P) ?                                     \
542      clib_bitmap_next_clear (_pool_var (p)->free_bitmap, _pool_var(rv)) \
543      : ~0);                                                             \
544   _pool_var(rv) =                                                       \
545     (_pool_var (rv) < vec_len (P) ?                                     \
546      _pool_var (rv) : ~0);                                              \
547   _pool_var(rv);                                                        \
548 })
549
550 #define pool_foreach_index(i,v)         \
551   if (v)                                        \
552     for (i = pool_get_first_index (v);          \
553          i < vec_len (v);                       \
554          i = pool_get_next_index (v, i))        \
555
556 /**
557  * @brief Remove all elements from a pool in a safe way
558  *
559  * @param VAR each element in the pool
560  * @param POOL The pool to flush
561  * @param BODY The actions to perform on each element before it is returned to
562  *        the pool. i.e. before it is 'freed'
563  */
564 #define pool_flush(VAR, POOL, BODY)                     \
565 {                                                       \
566   uword *_pool_var(ii), *_pool_var(dv) = NULL;          \
567                                                         \
568   pool_foreach((VAR), (POOL))                          \
569   {                                                     \
570     vec_add1(_pool_var(dv), (VAR) - (POOL));            \
571   }                                                     \
572   vec_foreach(_pool_var(ii), _pool_var(dv))             \
573   {                                                     \
574     (VAR) = pool_elt_at_index((POOL), *_pool_var(ii));  \
575     do { BODY; } while (0);                             \
576     pool_put((POOL), (VAR));                            \
577   }                                                     \
578   vec_free(_pool_var(dv));                              \
579 }
580
581 #endif /* included_pool_h */
582
583 /*
584  * fd.io coding-style-patch-verification: ON
585  *
586  * Local Variables:
587  * eval: (c-set-style "gnu")
588  * End:
589  */