/*
* Copyright (c) 2015 Cisco and/or its affiliates.
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at:
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/*
Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
Permission is hereby granted, free of charge, to any person obtaining
a copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:
The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/
#ifndef included_mem_mheap_h
#define included_mem_mheap_h
/* Bootstrap include so that #include <vppinfra/mem.h> can include e.g.
<vppinfra/mheap.h> which depends on <vppinfra/vec.h>. */
#include <vppinfra/vec_bootstrap.h>
#include <vppinfra/error_bootstrap.h>
#include <vppinfra/os.h>
#include <vppinfra/vector.h>
/* Each element in heap is immediately followed by this struct. */
typedef struct
{
/* Number of mheap_size_t words of user data in previous object.
Used to find mheap_elt_t for previous object. */
#if CLIB_VEC64 > 0
u64 prev_n_user_data:63;
/* Used to mark end/start of of doubly-linked list of mheap_elt_t's. */
#define MHEAP_N_USER_DATA_INVALID (0x7fffffffffffffffULL)
#define MHEAP_GROUNDED (~0ULL)
/* Set if previous object is free. */
u64 prev_is_free:1;
/* Number of mheap_size_t words of user data that follow this object. */
u64 n_user_data:63;
/* Set if this object is on free list (and therefore following free_elt
is valid). */
u64 is_free:1;
#else
u32 prev_n_user_data:31;
/* Used to mark end/start of of doubly-linked list of mheap_elt_t's. */
#define MHEAP_N_USER_DATA_INVALID (0x7fffffff)
#define MHEAP_GROUNDED (~0)
/* Set if previous object is free. */
u32 prev_is_free:1;
/* Number of mheap_size_t words of user data that follow this object. */
u32 n_user_data:31;
/* Set if this object is on free list (and therefore following free_elt
is valid). */
u32 is_free:1;
#endif
union
{
#if CLIB_VEC64 > 0
/* For allocated objects: user data follows.
User data is allocated in units of typeof (user_data[0]). */
u64 user_data[0];
/* For free objects, offsets of next and previous free objects of this size;
~0 means end of doubly-linked list.
This is stored in user data (guaranteed to be at least 8 bytes)
but only for *free* objects. */
struct
{
u64 next_uoffset, prev_uoffset;
} free_elt;
#else
/* For allocated objects: user data follows.
User data is allocated in units of typeof (user_data[0]). */
u32 user_data[0];
/* For free objects, offsets of next and previous free objects of this size;
~0 means end of doubly-linked list.
This is stored in user data (guaranteed to be at least 8 bytes)
but only for *free* objects. */
struct
{
u32 next_uoffset, prev_uoffset;
} free_elt;
#endif
};
} mheap_elt_t;
/* Number of bytes of "overhead": e.g. not user data. */
#define MHEAP_ELT_OVERHEAD_BYTES (sizeof (mheap_elt_t) - STRUCT_OFFSET_OF (mheap_elt_t, user_data))
/* User objects must be large enough to hold 2 x u32 free offsets in free elt. */
#define MHEAP_MIN_USER_DATA_BYTES MHEAP_ELT_OVERHEAD_BYTES
/* Number of byte in user data "words". */
#define MHEAP_USER_DATA_WORD_BYTES STRUCT_SIZE_OF (mheap_elt_t, user_data[0])
typedef struct
{
/* Address of callers: outer first, inner last. */
uword callers[12];
/* Count of allocations with this traceback. */
#if CLIB_VEC64 > 0
u64 n_allocations;
#else
u32 n_allocations;
#endif
/* Count of bytes allocated with this traceback. */
u32 n_bytes;
/* Offset of this item */
uword offset;
} mheap_trace_t;
typedef struct
{
mheap_trace_t *traces;
/* Indices of free traces. */
u32 *trace_free_list;
/* Hash table mapping callers to trace index. */
uword *trace_by_callers;
/* Hash table mapping mheap offset to trace index. */
uword *trace_index_by_offset;
} mheap_trace_main_t;
/* Without vector instructions don't bother with small object cache. */
#ifdef CLIB_HAVE_VEC128
#define MHEAP_HAVE_SMALL_OBJECT_CACHE 1
#else
#define MHEAP_HAVE_SMALL_OBJECT_CACHE 0
#endif
/* Small object bin i is for objects with
user_size > sizeof (mheap_elt_t) + sizeof (mheap_elt_t) * (i - 1)
user_size <= sizeof (mheap_elt_t) + sizeof (mheap_size_t) * i. */
#if MHEAP_HAVE_SMALL_OBJECT_CACHE > 0
#define MHEAP_LOG2_N_SMALL_OBJECT_BINS 8
#define MHEAP_N_SMALL_OBJECT_BINS (1 << MHEAP_LOG2_N_SMALL_OBJECT_BINS)
#else
#define MHEAP_LOG2_N_SMALL_OBJECT_BINS 0
#define MHEAP_N_SMALL_OBJECT_BINS 0
#endif
#define MHEAP_N_BINS \
(MHEAP_N_SMALL_OBJECT_BINS \
+ (STRUCT_BITS_OF (mheap_elt_t, user_data[0]) - MHEAP_LOG2_N_SMALL_OBJECT_BINS))
typedef struct
{
struct