FD.io VPP  v19.04.1-1-ge4a0f9f
Vector Packet Processing
mheap_bootstrap.h
Go to the documentation of this file.
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 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 
38 #ifndef included_mem_mheap_h
39 #define included_mem_mheap_h
40 
41 /* Bootstrap include so that #include <vppinfra/mem.h> can include e.g.
42  <vppinfra/mheap.h> which depends on <vppinfra/vec.h>. */
43 
44 #include <vppinfra/vec_bootstrap.h>
46 #include <vppinfra/os.h>
47 #include <vppinfra/vector.h>
48 
49 /* Each element in heap is immediately followed by this struct. */
50 typedef struct
51 {
52  /* Number of mheap_size_t words of user data in previous object.
53  Used to find mheap_elt_t for previous object. */
54 #if CLIB_VEC64 > 0
55  u64 prev_n_user_data:63;
56 
57  /* Used to mark end/start of of doubly-linked list of mheap_elt_t's. */
58 #define MHEAP_N_USER_DATA_INVALID (0x7fffffffffffffffULL)
59 #define MHEAP_GROUNDED (~0ULL)
60 
61  /* Set if previous object is free. */
62  u64 prev_is_free:1;
63 
64  /* Number of mheap_size_t words of user data that follow this object. */
65  u64 n_user_data:63;
66 
67  /* Set if this object is on free list (and therefore following free_elt
68  is valid). */
69  u64 is_free:1;
70 
71 #else
72  u32 prev_n_user_data:31;
73 
74  /* Used to mark end/start of of doubly-linked list of mheap_elt_t's. */
75 #define MHEAP_N_USER_DATA_INVALID (0x7fffffff)
76 #define MHEAP_GROUNDED (~0)
77 
78  /* Set if previous object is free. */
79  u32 prev_is_free:1;
80 
81  /* Number of mheap_size_t words of user data that follow this object. */
82  u32 n_user_data:31;
83 
84  /* Set if this object is on free list (and therefore following free_elt
85  is valid). */
86  u32 is_free:1;
87 #endif
88 
89  union
90  {
91 #if CLIB_VEC64 > 0
92  /* For allocated objects: user data follows.
93  User data is allocated in units of typeof (user_data[0]). */
94  u64 user_data[0];
95 
96  /* For free objects, offsets of next and previous free objects of this size;
97  ~0 means end of doubly-linked list.
98  This is stored in user data (guaranteed to be at least 8 bytes)
99  but only for *free* objects. */
100  struct
101  {
102  u64 next_uoffset, prev_uoffset;
103  } free_elt;
104 #else
105  /* For allocated objects: user data follows.
106  User data is allocated in units of typeof (user_data[0]). */
107  u32 user_data[0];
108 
109  /* For free objects, offsets of next and previous free objects of this size;
110  ~0 means end of doubly-linked list.
111  This is stored in user data (guaranteed to be at least 8 bytes)
112  but only for *free* objects. */
113  struct
114  {
115  u32 next_uoffset, prev_uoffset;
116  } free_elt;
117 #endif
118  };
119 } mheap_elt_t;
120 
121 /* Number of bytes of "overhead": e.g. not user data. */
122 #define MHEAP_ELT_OVERHEAD_BYTES (sizeof (mheap_elt_t) - STRUCT_OFFSET_OF (mheap_elt_t, user_data))
123 
124 /* User objects must be large enough to hold 2 x u32 free offsets in free elt. */
125 #define MHEAP_MIN_USER_DATA_BYTES MHEAP_ELT_OVERHEAD_BYTES
126 
127 /* Number of byte in user data "words". */
128 #define MHEAP_USER_DATA_WORD_BYTES STRUCT_SIZE_OF (mheap_elt_t, user_data[0])
129 
130 typedef struct
131 {
132  /* Address of callers: outer first, inner last. */
133  uword callers[12];
134 
135  /* Count of allocations with this traceback. */
136 #if CLIB_VEC64 > 0
137  u64 n_allocations;
138 #else
139  u32 n_allocations;
140 #endif
141 
142  /* Count of bytes allocated with this traceback. */
143  u32 n_bytes;
144 
145  /* Offset of this item */
146  uword offset;
147 } mheap_trace_t;
148 
149 typedef struct
150 {
151  mheap_trace_t *traces;
152 
153  /* Indices of free traces. */
154  u32 *trace_free_list;
155 
156  /* Hash table mapping callers to trace index. */
157  uword *trace_by_callers;
158 
159  /* Hash table mapping mheap offset to trace index. */
160  uword *trace_index_by_offset;
162 
163 /* Without vector instructions don't bother with small object cache. */
164 #ifdef CLIB_HAVE_VEC128
165 #define MHEAP_HAVE_SMALL_OBJECT_CACHE 1
166 #else
167 #define MHEAP_HAVE_SMALL_OBJECT_CACHE 0
168 #endif
169 
170  /* Small object bin i is for objects with
171  user_size > sizeof (mheap_elt_t) + sizeof (mheap_elt_t) * (i - 1)
172  user_size <= sizeof (mheap_elt_t) + sizeof (mheap_size_t) * i. */
173 #if MHEAP_HAVE_SMALL_OBJECT_CACHE > 0
174 #define MHEAP_LOG2_N_SMALL_OBJECT_BINS 8
175 #define MHEAP_N_SMALL_OBJECT_BINS (1 << MHEAP_LOG2_N_SMALL_OBJECT_BINS)
176 #else
177 #define MHEAP_LOG2_N_SMALL_OBJECT_BINS 0
178 #define MHEAP_N_SMALL_OBJECT_BINS 0
179 #endif
180 
181 #define MHEAP_N_BINS \
182  (MHEAP_N_SMALL_OBJECT_BINS \
183  + (STRUCT_BITS_OF (mheap_elt_t, user_data[0]) - MHEAP_LOG2_N_SMALL_OBJECT_BINS))
184 
185 typedef struct
186 {
187  struct
188  {
192  } free_list;
193 
195 
198 
199  u64 n_gets, n_puts;
200  u64 n_clocks_get, n_clocks_put;
201 } mheap_stats_t;
202 
203 /* For objects with align == 4 and align_offset == 0 (e.g. vector strings). */
204 typedef struct
205 {
206  union
207  {
208 #ifdef CLIB_HAVE_VEC128
209  u8x16 as_u8x16[BITS (uword) / 16];
210 #endif
211 
212  /* Store bin + 1; zero means unused. */
213  u8 as_u8[BITS (uword)];
214  } bins;
215 
216  uword offsets[BITS (uword)];
217 
220 
221 /* Vec header for heaps. */
222 typedef struct
223 {
224  /* User offsets for head of doubly-linked list of free objects of this size. */
225 #if CLIB_VEC64 > 0
226  u64 first_free_elt_uoffset_by_bin[MHEAP_N_BINS];
227 #else
228  u32 first_free_elt_uoffset_by_bin[MHEAP_N_BINS];
229 #endif
230 
231  /* Bitmap of non-empty free list bins. */
232  uword non_empty_free_elt_heads[(MHEAP_N_BINS + BITS (uword) - 1) /
234 
236 
238 #define MHEAP_FLAG_TRACE (1 << 0)
239 #define MHEAP_FLAG_DISABLE_VM (1 << 1)
240 #define MHEAP_FLAG_THREAD_SAFE (1 << 2)
241 #define MHEAP_FLAG_SMALL_OBJECT_CACHE (1 << 3)
242 #define MHEAP_FLAG_VALIDATE (1 << 4)
243 
244  /* Lock use when MHEAP_FLAG_THREAD_SAFE is set. */
245  volatile u32 lock;
246  volatile u32 owner_cpu;
248 
249  /* Number of allocated objects. */
251 
252  /* Maximum size (in bytes) this heap is allowed to grow to.
253  Set to ~0 to grow heap (via vec_resize) arbitrarily. */
255 
258 
259  /* Each successful mheap_validate call increments this serial number.
260  Used to debug heap corruption problems. GDB breakpoints can be
261  made conditional on validate_serial. */
263 
265 
267 } mheap_t;
268 
271 {
272  return vec_aligned_header (v, sizeof (mheap_t), 16);
273 }
274 
277 {
278  return vec_aligned_header_end (h, sizeof (mheap_t), 16);
279 }
280 
283 {
284  return (uword) e->user_data - (uword) v;
285 }
286 
289 {
290  return v - STRUCT_OFFSET_OF (mheap_elt_t, user_data);
291 }
292 
293 /* For debugging we keep track of offsets for valid objects.
294  We make sure user is not trying to free object with invalid offset. */
297 {
298  return uo >= MHEAP_ELT_OVERHEAD_BYTES && uo <= vec_len (v);
299 }
300 
303 {
304  ASSERT (mheap_offset_is_valid (v, uo));
305  return (mheap_elt_t *) (v + uo - STRUCT_OFFSET_OF (mheap_elt_t, user_data));
306 }
307 
308 always_inline void *
310 {
311  return v + mheap_elt_uoffset (v, e);
312 }
313 
316 {
317  return e->n_user_data * sizeof (e->user_data[0]);
318 }
319 
321 mheap_data_bytes (void *v, uword uo)
322 {
323  mheap_elt_t *e = mheap_elt_at_uoffset (v, uo);
324  return mheap_elt_data_bytes (e);
325 }
326 
327 #define mheap_len(v,d) (mheap_data_bytes((v),(void *) (d) - (void *) (v)) / sizeof ((d)[0]))
328 
331 {
333  return (mheap_elt_t *) (e->user_data + e->n_user_data);
334 }
335 
338 {
340  return ((void *) e
341  - e->prev_n_user_data * sizeof (e->user_data[0])
343 }
344 
345 /* Exported operations. */
346 
348 mheap_elts (void *v)
349 {
350  return v ? mheap_header (v)->n_elts : 0;
351 }
352 
354 mheap_max_size (void *v)
355 {
356  return v ? mheap_header (v)->max_size : ~0;
357 }
358 
359 /* Free previously allocated offset. */
360 void mheap_put (void *v, uword offset);
361 
362 /* Allocate object from mheap. */
363 void *mheap_get_aligned (void *v, uword size, uword align, uword align_offset,
364  uword * offset_return);
365 
366 #endif /* included_mem_mheap_h */
367 
368 /*
369  * fd.io coding-style-patch-verification: ON
370  *
371  * Local Variables:
372  * eval: (c-set-style "gnu")
373  * End:
374  */
#define MHEAP_ELT_OVERHEAD_BYTES
uword vm_alloc_offset_from_header
unsigned long u64
Definition: types.h:89
static uword mheap_offset_is_valid(void *v, uword uo)
u64 n_small_object_cache_hits
u64 n_small_object_cache_attempts
static mheap_t * mheap_header(u8 *v)
#define STRUCT_OFFSET_OF(t, f)
Definition: clib.h:65
static uword mheap_max_size(void *v)
unsigned char u8
Definition: types.h:56
mheap_trace_main_t trace_main
#define always_inline
Definition: clib.h:98
static uword mheap_elt_data_bytes(mheap_elt_t *e)
static mheap_elt_t * mheap_prev_elt(mheap_elt_t *e)
unsigned int u32
Definition: types.h:88
volatile u32 lock
mheap_stats_t stats
static uword mheap_elts(void *v)
u64 validate_serial
#define MHEAP_N_USER_DATA_INVALID
void mheap_put(void *v, uword offset)
Definition: mheap.c:771
static uword mheap_elt_uoffset(void *v, mheap_elt_t *e)
static void * vec_aligned_header(void *v, uword header_bytes, uword align)
mheap_small_object_cache_t small_object_cache
void * mheap_get_aligned(void *v, uword size, uword align, uword align_offset, uword *offset_return)
Definition: mheap.c:643
#define ASSERT(truth)
volatile u32 owner_cpu
uword vm_alloc_size
static void * mheap_elt_data(void *v, mheap_elt_t *e)
static mheap_elt_t * mheap_elt_at_uoffset(void *v, uword uo)
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
u64 uword
Definition: types.h:112
static mheap_elt_t * mheap_next_elt(mheap_elt_t *e)
struct clib_bihash_value offset
template key/value backing page structure
static void * vec_aligned_header_end(void *v, uword header_bytes, uword align)
int recursion_count
Vector bootstrap header file.
static uword mheap_data_bytes(void *v, uword uo)
static u8 * mheap_vector(mheap_t *h)
#define BITS(x)
Definition: clib.h:61
#define MHEAP_N_BINS
static mheap_elt_t * mheap_user_pointer_to_elt(void *v)