FD.io VPP  v16.06
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  /* Number of mheap_size_t words of user data in previous object.
52  Used to find mheap_elt_t for previous object. */
53  u32 prev_n_user_data : 31;
54 
55  /* Used to mark end/start of of doubly-linked list of mheap_elt_t's. */
56 #define MHEAP_N_USER_DATA_INVALID (0x7fffffff)
57 
58  /* Set if previous object is free. */
59  u32 prev_is_free : 1;
60 
61  /* Number of mheap_size_t words of user data that follow this object. */
62  u32 n_user_data : 31;
63 
64  /* Set if this object is on free list (and therefore following free_elt
65  is valid). */
66  u32 is_free : 1;
67 
68  union {
69  /* For allocated objects: user data follows.
70  User data is allocated in units of typeof (user_data[0]). */
71  u32 user_data[0];
72 
73  /* For free objects, offsets of next and previous free objects of this size;
74  ~0 means end of doubly-linked list.
75  This is stored in user data (guaranteed to be at least 8 bytes)
76  but only for *free* objects. */
77  struct {
78  u32 next_uoffset, prev_uoffset;
79  } free_elt;
80  };
81 } mheap_elt_t;
82 
83 /* Number of bytes of "overhead": e.g. not user data. */
84 #define MHEAP_ELT_OVERHEAD_BYTES (sizeof (mheap_elt_t) - STRUCT_OFFSET_OF (mheap_elt_t, user_data))
85 
86 /* User objects must be large enough to hold 2 x u32 free offsets in free elt. */
87 #define MHEAP_MIN_USER_DATA_BYTES MHEAP_ELT_OVERHEAD_BYTES
88 
89 /* Number of byte in user data "words". */
90 #define MHEAP_USER_DATA_WORD_BYTES STRUCT_SIZE_OF (mheap_elt_t, user_data[0])
91 
92 typedef struct {
93  /* Address of callers: outer first, inner last. */
94  uword callers[12];
95 
96  /* Count of allocations with this traceback. */
98 
99  /* Count of bytes allocated with this traceback. */
101 
102  /* Offset of this item */
104 } mheap_trace_t;
105 
106 typedef struct {
108 
109  /* Indices of free traces. */
111 
112  /* Hash table mapping callers to trace index. */
114 
115  /* Hash table mapping mheap offset to trace index. */
118 
119  /* Small object bin i is for objects with
120  user_size > sizeof (mheap_elt_t) + sizeof (mheap_elt_t) * (i - 1)
121  user_size <= sizeof (mheap_elt_t) + sizeof (mheap_size_t) * i. */
122 #define MHEAP_LOG2_N_SMALL_OBJECT_BINS 8
123 #define MHEAP_N_SMALL_OBJECT_BINS (1 << MHEAP_LOG2_N_SMALL_OBJECT_BINS)
124 
125 #define MHEAP_N_BINS \
126  (MHEAP_N_SMALL_OBJECT_BINS \
127  + (STRUCT_BITS_OF (mheap_elt_t, user_data[0]) - MHEAP_LOG2_N_SMALL_OBJECT_BINS))
128 
129 typedef struct {
130  struct {
134  } free_list;
135 
137 
140 
141  u64 n_gets, n_puts;
142  u64 n_clocks_get, n_clocks_put;
143 } mheap_stats_t;
144 
145 /* Without vector instructions don't bother with small object cache. */
146 #ifdef CLIB_HAVE_VEC128
147 #define MHEAP_HAVE_SMALL_OBJECT_CACHE 1
148 #else
149 #define MHEAP_HAVE_SMALL_OBJECT_CACHE 0
150 #endif
151 
152 /* For objects with align == 4 and align_offset == 0 (e.g. vector strings). */
153 typedef struct {
154  union {
155 #ifdef CLIB_HAVE_VEC128
156  u8x16 as_u8x16[BITS (uword) / 16];
157 #endif
158 
159  /* Store bin + 1; zero means unused. */
160  u8 as_u8[BITS (uword)];
161  } bins;
162 
163  uword offsets[BITS (uword)];
164 
167 
168 /* Vec header for heaps. */
169 typedef struct {
170  /* User offsets for head of doubly-linked list of free objects of this size. */
171  u32 first_free_elt_uoffset_by_bin[MHEAP_N_BINS];
172 
173  /* Bitmap of non-empty free list bins. */
174  uword non_empty_free_elt_heads[(MHEAP_N_BINS + BITS (uword) - 1) / BITS (uword)];
175 
177 
179 #define MHEAP_FLAG_TRACE (1 << 0)
180 #define MHEAP_FLAG_DISABLE_VM (1 << 1)
181 #define MHEAP_FLAG_THREAD_SAFE (1 << 2)
182 #define MHEAP_FLAG_SMALL_OBJECT_CACHE (1 << 3)
183 #define MHEAP_FLAG_VALIDATE (1 << 4)
184 
185  /* Lock use when MHEAP_FLAG_THREAD_SAFE is set. */
186  volatile u32 lock;
187  volatile u32 owner_cpu;
189 
190  /* Number of allocated objects. */
192 
193  /* Maximum size (in bytes) this heap is allowed to grow to.
194  Set to ~0 to grow heap (via vec_resize) arbitrarily. */
196 
199 
200  /* Each successful mheap_validate call increments this serial number.
201  Used to debug heap corruption problems. GDB breakpoints can be
202  made conditional on validate_serial. */
204 
206 
208 } mheap_t;
209 
211 { return vec_aligned_header (v, sizeof (mheap_t), 16); }
212 
214 { return vec_aligned_header_end (h, sizeof (mheap_t), 16); }
215 
217 { return (uword)e->user_data - (uword)v; }
218 
220 { return v - STRUCT_OFFSET_OF (mheap_elt_t, user_data); }
221 
222 /* For debugging we keep track of offsets for valid objects.
223  We make sure user is not trying to free object with invalid offset. */
225 { return uo >= MHEAP_ELT_OVERHEAD_BYTES && uo <= vec_len (v); }
226 
228 {
229  ASSERT (mheap_offset_is_valid (v, uo));
230  return (mheap_elt_t *) (v + uo - STRUCT_OFFSET_OF (mheap_elt_t, user_data));
231 }
232 
234 { return v + mheap_elt_uoffset (v, e); }
235 
237 { return e->n_user_data * sizeof (e->user_data[0]); }
238 
240 {
241  mheap_elt_t * e = mheap_elt_at_uoffset (v, uo);
242  return mheap_elt_data_bytes (e);
243 }
244 
245 #define mheap_len(v,d) (mheap_data_bytes((v),(void *) (d) - (void *) (v)) / sizeof ((d)[0]))
246 
248 {
250  return (mheap_elt_t *) (e->user_data + e->n_user_data);
251 }
252 
254 {
256  return ((void *) e
257  - e->prev_n_user_data * sizeof (e->user_data[0])
259 }
260 
261 /* Exported operations. */
262 
264 { return v ? mheap_header (v)->n_elts : 0; }
265 
267 { return v ? mheap_header (v)->max_size : ~0; }
268 
269 /* Free previously allocated offset. */
270 void mheap_put (void * v, uword offset);
271 
272 /* Allocate object from mheap. */
273 void * mheap_get_aligned (void * v, uword size, uword align, uword align_offset,
274  uword * offset_return);
275 
276 #endif /* included_mem_mheap_h */
always_inline uword mheap_offset_is_valid(void *v, uword uo)
always_inline mheap_elt_t * mheap_user_pointer_to_elt(void *v)
always_inline uword mheap_elts(void *v)
always_inline uword mheap_elt_uoffset(void *v, mheap_elt_t *e)
always_inline void * mheap_elt_data(void *v, mheap_elt_t *e)
always_inline mheap_elt_t * mheap_prev_elt(mheap_elt_t *e)
#define MHEAP_ELT_OVERHEAD_BYTES
always_inline uword mheap_max_size(void *v)
uword vm_alloc_offset_from_header
always_inline uword mheap_data_bytes(void *v, uword uo)
u64 n_small_object_cache_hits
u64 n_small_object_cache_attempts
#define STRUCT_OFFSET_OF(t, f)
Definition: clib.h:62
always_inline void * vec_aligned_header(void *v, uword header_bytes, uword align)
mheap_trace_main_t trace_main
#define always_inline
Definition: clib.h:84
unsigned long u64
Definition: types.h:89
volatile u32 lock
always_inline mheap_t * mheap_header(u8 *v)
mheap_stats_t stats
mheap_trace_t * traces
u64 validate_serial
#define MHEAP_N_USER_DATA_INVALID
void mheap_put(void *v, uword offset)
Definition: mheap.c:728
always_inline uword mheap_elt_data_bytes(mheap_elt_t *e)
mheap_small_object_cache_t small_object_cache
always_inline mheap_elt_t * mheap_next_elt(mheap_elt_t *e)
void * mheap_get_aligned(void *v, uword size, uword align, uword align_offset, uword *offset_return)
Definition: mheap.c:621
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
always_inline mheap_elt_t * mheap_elt_at_uoffset(void *v, uword uo)
volatile u32 owner_cpu
uword vm_alloc_size
u32 size
Definition: vhost-user.h:74
always_inline u8 * mheap_vector(mheap_t *h)
u64 uword
Definition: types.h:112
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
unsigned char u8
Definition: types.h:56
u32 user_data[0]
always_inline void * vec_aligned_header_end(void *v, uword header_bytes, uword align)
int recursion_count
Vector bootsrap header file.
#define BITS(x)
Definition: clib.h:58
#define MHEAP_N_BINS