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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
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:
26 The above copyright notice and this permission notice shall be
27 included in all copies or substantial portions of the Software.
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.
38 #ifndef included_mem_mheap_h
39 #define included_mem_mheap_h
41 /* Bootstrap include so that #include <vppinfra/mem.h> can include e.g.
42 <vppinfra/mheap.h> which depends on <vppinfra/vec.h>. */
44 #include <vppinfra/vec_bootstrap.h>
45 #include <vppinfra/error_bootstrap.h>
46 #include <vppinfra/os.h>
47 #include <vppinfra/vector.h>
49 /* Each element in heap is immediately followed by this struct. */
52 /* Number of mheap_size_t words of user data in previous object.
53 Used to find mheap_elt_t for previous object. */
55 u64 prev_n_user_data:63;
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)
61 /* Set if previous object is free. */
64 /* Number of mheap_size_t words of user data that follow this object. */
67 /* Set if this object is on free list (and therefore following free_elt
72 u32 prev_n_user_data:31;
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)
78 /* Set if previous object is free. */
81 /* Number of mheap_size_t words of user data that follow this object. */
84 /* Set if this object is on free list (and therefore following free_elt
92 /* For allocated objects: user data follows.
93 User data is allocated in units of typeof (user_data[0]). */
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. */
102 u64 next_uoffset, prev_uoffset;
105 /* For allocated objects: user data follows.
106 User data is allocated in units of typeof (user_data[0]). */
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. */
115 u32 next_uoffset, prev_uoffset;
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))
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
127 /* Number of byte in user data "words". */
128 #define MHEAP_USER_DATA_WORD_BYTES STRUCT_SIZE_OF (mheap_elt_t, user_data[0])
132 /* Address of callers: outer first, inner last. */
135 /* Count of allocations with this traceback. */
142 /* Count of bytes allocated with this traceback. */
145 /* Offset of this item */
151 mheap_trace_t *traces;
153 /* Indices of free traces. */
154 u32 *trace_free_list;
156 /* Hash table mapping callers to trace index. */
157 uword *trace_by_callers;
159 /* Hash table mapping mheap offset to trace index. */
160 uword *trace_index_by_offset;
161 } mheap_trace_main_t;
163 /* Without vector instructions don't bother with small object cache. */
164 #ifdef CLIB_HAVE_VEC128
165 #define MHEAP_HAVE_SMALL_OBJECT_CACHE 1
167 #define MHEAP_HAVE_SMALL_OBJECT_CACHE 0
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)
177 #define MHEAP_LOG2_N_SMALL_OBJECT_BINS 0
178 #define MHEAP_N_SMALL_OBJECT_BINS 0
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))
189 u64 n_search_attempts;
190 u64 n_objects_searched;
194 u64 n_vector_expands;
196 u64 n_small_object_cache_hits;
197 u64 n_small_object_cache_attempts;
200 u64 n_clocks_get, n_clocks_put;
203 /* For objects with align == 4 and align_offset == 0 (e.g. vector strings). */
208 #ifdef CLIB_HAVE_VEC128
209 u8x16 as_u8x16[BITS (uword) / 16];
212 /* Store bin + 1; zero means unused. */
213 u8 as_u8[BITS (uword)];
216 uword offsets[BITS (uword)];
218 u32 replacement_index;
219 } mheap_small_object_cache_t;
221 /* Vec header for heaps. */
224 /* User offsets for head of doubly-linked list of free objects of this size. */
226 u64 first_free_elt_uoffset_by_bin[MHEAP_N_BINS];
228 u32 first_free_elt_uoffset_by_bin[MHEAP_N_BINS];
231 /* Bitmap of non-empty free list bins. */
232 uword non_empty_free_elt_heads[(MHEAP_N_BINS + BITS (uword) - 1) /
235 mheap_small_object_cache_t small_object_cache;
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)
244 /* Lock use when MHEAP_FLAG_THREAD_SAFE is set. */
246 volatile u32 owner_cpu;
249 /* Number of allocated objects. */
252 /* Maximum size (in bytes) this heap is allowed to grow to.
253 Set to ~0 to grow heap (via vec_resize) arbitrarily. */
256 uword vm_alloc_offset_from_header;
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. */
264 mheap_trace_main_t trace_main;
269 always_inline mheap_t *
270 mheap_header (u8 * v)
272 return vec_aligned_header (v, sizeof (mheap_t), 16);
276 mheap_vector (mheap_t * h)
278 return vec_aligned_header_end (h, sizeof (mheap_t), 16);
282 mheap_elt_uoffset (void *v, mheap_elt_t * e)
284 return (uword) e->user_data - (uword) v;
287 always_inline mheap_elt_t *
288 mheap_user_pointer_to_elt (void *v)
290 return v - STRUCT_OFFSET_OF (mheap_elt_t, user_data);
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. */
296 mheap_offset_is_valid (void *v, uword uo)
298 return uo >= MHEAP_ELT_OVERHEAD_BYTES && uo <= vec_len (v);
301 always_inline mheap_elt_t *
302 mheap_elt_at_uoffset (void *v, uword uo)
304 ASSERT (mheap_offset_is_valid (v, uo));
305 return (mheap_elt_t *) (v + uo - STRUCT_OFFSET_OF (mheap_elt_t, user_data));
309 mheap_elt_data (void *v, mheap_elt_t * e)
311 return v + mheap_elt_uoffset (v, e);
315 mheap_elt_data_bytes (mheap_elt_t * e)
317 return e->n_user_data * sizeof (e->user_data[0]);
321 mheap_data_bytes (void *v, uword uo)
323 mheap_elt_t *e = mheap_elt_at_uoffset (v, uo);
324 return mheap_elt_data_bytes (e);
327 #define mheap_len(v,d) (mheap_data_bytes((v),(void *) (d) - (void *) (v)) / sizeof ((d)[0]))
329 always_inline mheap_elt_t *
330 mheap_next_elt (mheap_elt_t * e)
332 ASSERT (e->n_user_data < MHEAP_N_USER_DATA_INVALID);
333 return (mheap_elt_t *) (e->user_data + e->n_user_data);
336 always_inline mheap_elt_t *
337 mheap_prev_elt (mheap_elt_t * e)
339 ASSERT (e->prev_n_user_data < MHEAP_N_USER_DATA_INVALID);
341 - e->prev_n_user_data * sizeof (e->user_data[0])
342 - MHEAP_ELT_OVERHEAD_BYTES);
345 /* Exported operations. */
350 return v ? mheap_header (v)->n_elts : 0;
354 mheap_max_size (void *v)
356 return v ? mheap_header (v)->max_size : ~0;
359 /* Free previously allocated offset. */
360 void mheap_put (void *v, uword offset);
362 /* Allocate object from mheap. */
363 void *mheap_get_aligned (void *v, uword size, uword align, uword align_offset,
364 uword * offset_return);
366 #endif /* included_mem_mheap_h */
369 * fd.io coding-style-patch-verification: ON
372 * eval: (c-set-style "gnu")