[apple/xnu.git] / osfmk / kern / ltable.h

/*
 * Copyright (c) 2016 Apple Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 *
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * unlawful or unlicensed copies of an Apple operating system, or to
 * circumvent, violate, or enable the circumvention or violation of, any
 * terms of an Apple operating system software license agreement.
 *
 * Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this file.
 *
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
 */
#ifdef XNU_KERNEL_PRIVATE

#include <kern/kern_types.h>
#include <machine/locks.h>

#if CONFIG_LTABLE_DEBUG
#define ltdbg(fmt, ...) \
	printf("LT[%s]:  " fmt "\n", __func__, ## __VA_ARGS__)
#else
#define ltdbg(fmt, ...) do { } while (0)
#endif

#ifdef LTABLE_VERBOSE_DEBUG
#define ltdbg_v(fmt, ...) \
	printf("LT[v:%s]:  " fmt "\n", __func__, ## __VA_ARGS__)
#else
#define ltdbg_v(fmt, ...) do { } while (0)
#endif

#define ltinfo(fmt, ...) \
	printf("LT[%s]: " fmt "\n", __func__,  ## __VA_ARGS__)

#define lterr(fmt, ...) \
	printf("LT[%s] ERROR: " fmt "\n", __func__, ## __VA_ARGS__)


/* ----------------------------------------------------------------------
 *
 * Lockless Link Table Interface
 *
 * ---------------------------------------------------------------------- */

struct ltable_id {
	union {
		uint64_t id;
		struct {
			/*
			 * this bitfield is OK because we don't need to
			 * enforce a particular memory layout
			 */
			uint64_t idx:18, /* allows indexing up to 8MB of 32byte objects */
			    generation:46;
		};
	};
};

/* this _must_ match the idx bitfield definition in struct ltable_id */
#define LT_IDX_MAX  (0x3ffff)

extern vm_size_t     g_lt_max_tbl_size;


struct lt_elem {
	struct ltable_id lt_id;
	uint32_t lt_bits;
	uint32_t lt_next_idx;
};

/* reference count bits should _always_ be the low-order bits */
#define LT_BITS_REFCNT_MASK  (0x1FFFFFFFU)
#define LT_BITS_REFCNT_SHIFT (0)
#define LT_BITS_REFCNT       (LT_BITS_REFCNT_MASK << LT_BITS_REFCNT_SHIFT)

#define LT_BITS_TYPE_MASK    (0x3U)
#define LT_BITS_TYPE_SHIFT   (29)
#define LT_BITS_TYPE         (LT_BITS_TYPE_MASK << LT_BITS_TYPE_SHIFT)

#define LT_BITS_VALID_MASK   (0x1U)
#define LT_BITS_VALID_SHIFT  (31)
#define LT_BITS_VALID        (LT_BITS_VALID_MASK << LT_BITS_VALID_SHIFT)

#define lt_bits_refcnt(bits) \
	(((bits) >> LT_BITS_REFCNT_SHIFT) & LT_BITS_REFCNT_MASK)

#define lt_bits_type(bits) \
	(((bits) >> LT_BITS_TYPE_SHIFT) & LT_BITS_TYPE_MASK)

#define lt_bits_valid(bits) \
	((bits) & LT_BITS_VALID)

enum lt_elem_type {
	LT_FREE     = 0,
	LT_ELEM     = 1,
	LT_LINK     = 2,
	LT_RESERVED = 3,
};

struct link_table;
typedef void (*ltable_poison_func)(struct link_table *, struct lt_elem *);

/*
 * link_table structure
 *
 * A link table is a container for slabs of elements. Each slab is 'slab_sz'
 * bytes and contains 'slab_sz/elem_sz' elements (of 'elem_sz' bytes each).
 * These slabs allow the table to be broken up into potentially dis-contiguous
 * VA space. On 32-bit platforms with large amounts of physical RAM, this is
 * quite important. Keeping slabs like this slightly complicates retrieval of
 * table elements, but not by much.
 */
struct link_table {
	struct lt_elem **table;   /* an array of 'slabs' of elements */
	struct lt_elem **next_free_slab;
	struct ltable_id free_list __attribute__((aligned(8)));

	uint32_t         elem_sz;  /* size of a table element (bytes) */
	uint32_t         slab_shift;
	uint32_t         slab_msk;
	uint32_t         slab_elem;
	uint32_t         slab_sz;  /* size of a table 'slab' object (bytes) */

	uint32_t         nelem;
	uint32_t         used_elem;
	zone_t           slab_zone;

	ltable_poison_func poison;

	lck_mtx_t        lock;
	uint32_t         state;

#if CONFIG_LTABLE_STATS
	uint32_t         nslabs;

	uint64_t         nallocs;
	uint64_t         nreallocs;
	uint64_t         npreposts;
	int64_t          nreservations;
	uint64_t         nreserved_releases;
	uint64_t         nspins;

	uint64_t         max_used;
	uint64_t         avg_used;
	uint64_t         max_reservations;
	uint64_t         avg_reservations;
#endif
} __attribute__((aligned(8)));


/**
 * ltable_bootstrap: bootstrap a link table
 *
 * Called once at system boot
 */
extern void ltable_bootstrap(void);


/**
 * ltable_init: initialize a link table with given parameters
 *
 */
extern void ltable_init(struct link_table *table, const char *name,
    uint32_t max_tbl_elem, uint32_t elem_sz,
    ltable_poison_func poison);


/**
 * ltable_grow: grow a link table by adding another 'slab' of table elements
 *
 * Conditions:
 *	table mutex is unlocked
 *	calling thread can block
 */
extern void ltable_grow(struct link_table *table, uint32_t min_free);


/**
 * ltable_alloc_elem: allocate one or more elements from a given table
 *
 * The returned element(s) will be of type 'type', but will remain invalid.
 *
 * If the caller has disabled preemption, then this function may (rarely) spin
 * waiting either for another thread to either release 'nelem' table elements,
 * or grow the table.
 *
 * If the caller can block, then this function may (rarely) block while
 * the table grows to meet the demand for 'nelem' element(s).
 */
extern __attribute__((noinline))
struct lt_elem *ltable_alloc_elem(struct link_table *table, int type,
    int nelem, int nattempts);


#if DEVELOPMENT || DEBUG
/**
 * ltable_nelem: returns how many elements are used in this
 * table.
 */
extern
int ltable_nelem(struct link_table *table);
#endif

/**
 * ltable_realloc_elem: convert a reserved element to a particular type
 *
 * This funciton is used to convert reserved elements (not yet marked valid)
 * to the given 'type'. The generation of 'elem' is incremented, the element
 * is disconnected from any list to which it belongs, and its type is set to
 * 'type'.
 */
extern void ltable_realloc_elem(struct link_table *table,
    struct lt_elem *elem, int type);


/**
 * ltable_get_elem: get a reference to a table element identified by 'id'
 *
 * Returns a reference to the table element associated with the given 'id', or
 * NULL if the 'id' was invalid or does not exist in 'table'. The caller is
 * responsible to release the reference using ltable_put_elem().
 *
 * NOTE: if the table element pointed to by 'id' is marked as invalid,
 *       this function will return NULL.
 */
extern struct lt_elem *ltable_get_elem(struct link_table *table, uint64_t id);


/**
 * ltable_put_elem: release a reference to table element
 *
 * This function releases a reference taken on a table element via
 * ltable_get_elem(). This function will release the element back to 'table'
 * when the reference count goes to 0 AND the element has been marked as
 * invalid.
 */
extern void ltable_put_elem(struct link_table *table, struct lt_elem *elem);


/**
 * lt_elem_invalidate: mark 'elem' as invalid
 *
 * NOTE: this does _not_ get or put a reference on 'elem'
 */
extern void lt_elem_invalidate(struct lt_elem *elem);


/**
 * lt_elem_mkvalid: mark 'elem' as valid
 *
 * NOTE: this does _not_ get or put a reference on 'elem'
 */
extern void lt_elem_mkvalid(struct lt_elem *elem);


/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
 *
 * API: lt_elem_list_*
 *
 * Reuse the free list linkage member, 'lt_next_idx' of a link table element
 * in a slightly more generic singly-linked list. All members of this list
 * have been allocated from a table, but have not been made valid.
 *
 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

/**
 * lt_elem_list_link: link a child onto a parent
 *
 * Note that if 'parent' is the head of a list, this function will follow that
 * list and attach 'child' to the end of it. In the simplest case, this
 * results in: parent->child
 * however this could also result in: parent->...->child
 */
extern int lt_elem_list_link(struct link_table *table,
    struct lt_elem *parent, struct lt_elem *child);


/**
 * lt_elem_list_first: obtain a pointer to the first element of a list.
 *
 * This function converts the head of a singly-linked list, 'id', into a real
 * lt_elem object and returns a pointer to the object.
 *
 * It does _not_ take an extra reference on the object: the list implicitly
 * holds that reference.
 */
extern struct lt_elem *lt_elem_list_first(struct link_table *table, uint64_t id);


/**
 * lt_elem_list_next: return the item subsequent to 'elem' in a list
 *
 * Note that this will return NULL if 'elem' is actually the end of the list.
 */
extern struct lt_elem *lt_elem_list_next(struct link_table *table,
    struct lt_elem *elem);


/**
 * lt_elem_list_break: break a list in two around 'elem'
 *
 * This function will reset the next_idx field of 'elem' (making it the end of
 * the list), and return the element subsequent to 'elem' in the list
 * (which could be NULL)
 */
extern struct lt_elem *lt_elem_list_break(struct link_table *table,
    struct lt_elem *elem);


/**
 * lt_elem_list_pop: pop an item off the head of a list
 *
 * The list head is pointed to by '*id', the element corresponding to '*id' is
 * returned by this function, and the new list head is returned in the in/out
 * parameter, '*id'.  The caller is responsible for the reference on the
 * returned object.  A realloc is done to reset the type of the object, but it
 * is still left invalid.
 */
extern struct lt_elem *lt_elem_list_pop(struct link_table *table,
    uint64_t *id, int type);


/**
 * lt_elem_list_release: free an entire list of reserved elements
 *
 * All elements in the list whose first member is 'head' will be released back
 * to 'table' as free elements. The 'type' parameter is used in development
 * kernels to assert that all elements on the list are of the given type.
 */
extern int lt_elem_list_release(struct link_table *table,
    struct lt_elem *head,
    int __assert_only type);

static inline int
lt_elem_list_release_id(struct link_table *table,
    uint64_t id, int type)
{
	return lt_elem_list_release(table, lt_elem_list_first(table, id), type);
}

#endif /* XNU_KERNEL_PRIVATE */
Commit	Line	Data
39037602 A	1	/*
	2	* Copyright (c) 2016 Apple Inc. All rights reserved.
	3	*
	4	* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
	5	*
	6	* This file contains Original Code and/or Modifications of Original Code
	7	* as defined in and that are subject to the Apple Public Source License
	8	* Version 2.0 (the 'License'). You may not use this file except in
	9	* compliance with the License. The rights granted to you under the License
	10	* may not be used to create, or enable the creation or redistribution of,
	11	* unlawful or unlicensed copies of an Apple operating system, or to
	12	* circumvent, violate, or enable the circumvention or violation of, any
	13	* terms of an Apple operating system software license agreement.
	14	*
	15	* Please obtain a copy of the License at
	16	* http://www.opensource.apple.com/apsl/ and read it before using this file.
	17	*
	18	* The Original Code and all software distributed under the License are
	19	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
	20	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
	21	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
	22	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	23	* Please see the License for the specific language governing rights and
	24	* limitations under the License.
	25	*
	26	* @APPLE_OSREFERENCE_LICENSE_HEADER_END@
	27	*/
	28	#ifdef XNU_KERNEL_PRIVATE
	29
	30	#include <kern/kern_types.h>
	31	#include <machine/locks.h>
	32
	33	#if CONFIG_LTABLE_DEBUG
0a7de745	34	#define ltdbg(fmt, ...) \
39037602 A	35	printf("LT[%s]: " fmt "\n", __func__, ## __VA_ARGS__)
39037602 A	36	#else
0a7de745	37	#define ltdbg(fmt, ...) do { } while (0)
39037602 A	38	#endif
	39
	40	#ifdef LTABLE_VERBOSE_DEBUG
0a7de745	41	#define ltdbg_v(fmt, ...) \
39037602 A	42	printf("LT[v:%s]: " fmt "\n", __func__, ## __VA_ARGS__)
39037602 A	43	#else
0a7de745	44	#define ltdbg_v(fmt, ...) do { } while (0)
39037602 A	45	#endif
39037602 A	46
0a7de745	47	#define ltinfo(fmt, ...) \
39037602 A	48	printf("LT[%s]: " fmt "\n", __func__, ## __VA_ARGS__)
39037602 A	49
0a7de745	50	#define lterr(fmt, ...) \
39037602 A	51	printf("LT[%s] ERROR: " fmt "\n", __func__, ## __VA_ARGS__)
	52
	53
	54
	55	/* ----------------------------------------------------------------------
	56	*
	57	* Lockless Link Table Interface
	58	*
	59	* ---------------------------------------------------------------------- */
	60
	61	struct ltable_id {
	62	union {
	63	uint64_t id;
	64	struct {
	65	/*
	66	* this bitfield is OK because we don't need to
	67	* enforce a particular memory layout
	68	*/
	69	uint64_t idx:18, /* allows indexing up to 8MB of 32byte objects */
0a7de745	70	generation:46;
39037602 A	71	};
	72	};
	73	};
	74
	75	/* this _must_ match the idx bitfield definition in struct ltable_id */
	76	#define LT_IDX_MAX (0x3ffff)
	77
	78	extern vm_size_t g_lt_max_tbl_size;
	79
	80
	81	struct lt_elem {
	82	struct ltable_id lt_id;
	83	uint32_t lt_bits;
	84	uint32_t lt_next_idx;
	85	};
	86
	87	/* reference count bits should _always_ be the low-order bits */
cb323159	88	#define LT_BITS_REFCNT_MASK (0x1FFFFFFFU)
39037602 A	89	#define LT_BITS_REFCNT_SHIFT (0)
	90	#define LT_BITS_REFCNT (LT_BITS_REFCNT_MASK << LT_BITS_REFCNT_SHIFT)
	91
cb323159	92	#define LT_BITS_TYPE_MASK (0x3U)
39037602 A	93	#define LT_BITS_TYPE_SHIFT (29)
	94	#define LT_BITS_TYPE (LT_BITS_TYPE_MASK << LT_BITS_TYPE_SHIFT)
	95
cb323159	96	#define LT_BITS_VALID_MASK (0x1U)
39037602 A	97	#define LT_BITS_VALID_SHIFT (31)
	98	#define LT_BITS_VALID (LT_BITS_VALID_MASK << LT_BITS_VALID_SHIFT)
	99
	100	#define lt_bits_refcnt(bits) \
	101	(((bits) >> LT_BITS_REFCNT_SHIFT) & LT_BITS_REFCNT_MASK)
	102
	103	#define lt_bits_type(bits) \
	104	(((bits) >> LT_BITS_TYPE_SHIFT) & LT_BITS_TYPE_MASK)
	105
	106	#define lt_bits_valid(bits) \
	107	((bits) & LT_BITS_VALID)
	108
	109	enum lt_elem_type {
	110	LT_FREE = 0,
	111	LT_ELEM = 1,
	112	LT_LINK = 2,
	113	LT_RESERVED = 3,
	114	};
	115
	116	struct link_table;
	117	typedef void (ltable_poison_func)(struct link_table , struct lt_elem *);
	118
	119	/*
	120	* link_table structure
	121	*
	122	* A link table is a container for slabs of elements. Each slab is 'slab_sz'
	123	* bytes and contains 'slab_sz/elem_sz' elements (of 'elem_sz' bytes each).
	124	* These slabs allow the table to be broken up into potentially dis-contiguous
	125	* VA space. On 32-bit platforms with large amounts of physical RAM, this is
	126	* quite important. Keeping slabs like this slightly complicates retrieval of
	127	* table elements, but not by much.
	128	*/
	129	struct link_table {
	130	struct lt_elem *table; / an array of 'slabs' of elements */
	131	struct lt_elem **next_free_slab;
	132	struct ltable_id free_list __attribute__((aligned(8)));
	133
	134	uint32_t elem_sz; /* size of a table element (bytes) */
	135	uint32_t slab_shift;
	136	uint32_t slab_msk;
	137	uint32_t slab_elem;
	138	uint32_t slab_sz; /* size of a table 'slab' object (bytes) */
	139
	140	uint32_t nelem;
	141	uint32_t used_elem;
	142	zone_t slab_zone;
	143
	144	ltable_poison_func poison;
	145
	146	lck_mtx_t lock;
	147	uint32_t state;
	148
	149	#if CONFIG_LTABLE_STATS
	150	uint32_t nslabs;
	151
	152	uint64_t nallocs;
	153	uint64_t nreallocs;
	154	uint64_t npreposts;
	155	int64_t nreservations;
	156	uint64_t nreserved_releases;
	157	uint64_t nspins;
	158
	159	uint64_t max_used;
	160	uint64_t avg_used;
161	uint64_t max_reservations;
162	uint64_t avg_reservations;
163	#endif
164	} __attribute__((aligned(8)));
165
166
167	/**
168	* ltable_bootstrap: bootstrap a link table
169	*
170	* Called once at system boot
171	*/
172	extern void ltable_bootstrap(void);
173
174
175	/**
176	* ltable_init: initialize a link table with given parameters
177	*
178	*/
179	extern void ltable_init(struct link_table table, const char name,
0a7de745 A	180	uint32_t max_tbl_elem, uint32_t elem_sz,
0a7de745 A	181	ltable_poison_func poison);
39037602 A	182
	183
	184	/**
	185	* ltable_grow: grow a link table by adding another 'slab' of table elements
	186	*
	187	* Conditions:
	188	* table mutex is unlocked
	189	* calling thread can block
	190	*/
	191	extern void ltable_grow(struct link_table *table, uint32_t min_free);
	192
	193
	194	/**
	195	* ltable_alloc_elem: allocate one or more elements from a given table
	196	*
	197	* The returned element(s) will be of type 'type', but will remain invalid.
	198	*
	199	* If the caller has disabled preemption, then this function may (rarely) spin
	200	* waiting either for another thread to either release 'nelem' table elements,
	201	* or grow the table.
	202	*
	203	* If the caller can block, then this function may (rarely) block while
	204	* the table grows to meet the demand for 'nelem' element(s).
	205	*/
	206	extern __attribute__((noinline))
	207	struct lt_elem ltable_alloc_elem(struct link_table table, int type,
0a7de745	208	int nelem, int nattempts);
39037602 A	209
39037602 A	210
d9a64523 A	211	#if DEVELOPMENT \|\| DEBUG
	212	/**
	213	* ltable_nelem: returns how many elements are used in this
	214	* table.
	215	*/
	216	extern
	217	int ltable_nelem(struct link_table *table);
	218	#endif
	219
39037602 A	220	/**
	221	* ltable_realloc_elem: convert a reserved element to a particular type
	222	*
	223	* This funciton is used to convert reserved elements (not yet marked valid)
	224	* to the given 'type'. The generation of 'elem' is incremented, the element
	225	* is disconnected from any list to which it belongs, and its type is set to
	226	* 'type'.
	227	*/
	228	extern void ltable_realloc_elem(struct link_table *table,
0a7de745	229	struct lt_elem *elem, int type);
39037602 A	230
	231
	232	/**
	233	* ltable_get_elem: get a reference to a table element identified by 'id'
	234	*
	235	* Returns a reference to the table element associated with the given 'id', or
	236	* NULL if the 'id' was invalid or does not exist in 'table'. The caller is
	237	* responsible to release the reference using ltable_put_elem().
	238	*
	239	* NOTE: if the table element pointed to by 'id' is marked as invalid,
	240	* this function will return NULL.
	241	*/
	242	extern struct lt_elem ltable_get_elem(struct link_table table, uint64_t id);
	243
	244
	245	/**
	246	* ltable_put_elem: release a reference to table element
	247	*
	248	* This function releases a reference taken on a table element via
	249	* ltable_get_elem(). This function will release the element back to 'table'
	250	* when the reference count goes to 0 AND the element has been marked as
	251	* invalid.
	252	*/
	253	extern void ltable_put_elem(struct link_table table, struct lt_elem elem);
	254
	255
	256	/**
	257	* lt_elem_invalidate: mark 'elem' as invalid
	258	*
	259	* NOTE: this does _not_ get or put a reference on 'elem'
	260	*/
	261	extern void lt_elem_invalidate(struct lt_elem *elem);
	262
	263
	264	/**
	265	* lt_elem_mkvalid: mark 'elem' as valid
	266	*
	267	* NOTE: this does _not_ get or put a reference on 'elem'
	268	*/
	269	extern void lt_elem_mkvalid(struct lt_elem *elem);
	270
	271
	272	/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
	273	*
	274	* API: lt_elem_list_*
	275	*
	276	* Reuse the free list linkage member, 'lt_next_idx' of a link table element
	277	* in a slightly more generic singly-linked list. All members of this list
	278	* have been allocated from a table, but have not been made valid.
	279	*
	280	* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
	281
	282	/**
	283	* lt_elem_list_link: link a child onto a parent
	284	*
	285	* Note that if 'parent' is the head of a list, this function will follow that
	286	* list and attach 'child' to the end of it. In the simplest case, this
	287	* results in: parent->child
	288	* however this could also result in: parent->...->child
	289	*/
	290	extern int lt_elem_list_link(struct link_table *table,
0a7de745	291	struct lt_elem parent, struct lt_elem child);
39037602 A	292
	293
	294	/**
	295	* lt_elem_list_first: obtain a pointer to the first element of a list.
	296	*
	297	* This function converts the head of a singly-linked list, 'id', into a real
	298	* lt_elem object and returns a pointer to the object.
	299	*
	300	* It does _not_ take an extra reference on the object: the list implicitly
	301	* holds that reference.
	302	*/
	303	extern struct lt_elem lt_elem_list_first(struct link_table table, uint64_t id);
	304
	305
	306	/**
	307	* lt_elem_list_next: return the item subsequent to 'elem' in a list
	308	*
	309	* Note that this will return NULL if 'elem' is actually the end of the list.
	310	*/
	311	extern struct lt_elem lt_elem_list_next(struct link_table table,
0a7de745	312	struct lt_elem *elem);
39037602 A	313
	314
	315	/**
	316	* lt_elem_list_break: break a list in two around 'elem'
	317	*
	318	* This function will reset the next_idx field of 'elem' (making it the end of
	319	* the list), and return the element subsequent to 'elem' in the list
	320	* (which could be NULL)
	321	*/
	322	extern struct lt_elem lt_elem_list_break(struct link_table table,
0a7de745	323	struct lt_elem *elem);
39037602 A	324
	325
	326	/**
	327	* lt_elem_list_pop: pop an item off the head of a list
	328	*
	329	* The list head is pointed to by 'id', the element corresponding to 'id' is
	330	* returned by this function, and the new list head is returned in the in/out
	331	* parameter, '*id'. The caller is responsible for the reference on the
	332	* returned object. A realloc is done to reset the type of the object, but it
	333	* is still left invalid.
	334	*/
	335	extern struct lt_elem lt_elem_list_pop(struct link_table table,
0a7de745	336	uint64_t *id, int type);
39037602 A	337
	338
	339	/**
	340	* lt_elem_list_release: free an entire list of reserved elements
	341	*
	342	* All elements in the list whose first member is 'head' will be released back
	343	* to 'table' as free elements. The 'type' parameter is used in development
	344	* kernels to assert that all elements on the list are of the given type.
	345	*/
	346	extern int lt_elem_list_release(struct link_table *table,
0a7de745 A	347	struct lt_elem *head,
0a7de745 A	348	int __assert_only type);
39037602	349
0a7de745 A	350	static inline int
	351	lt_elem_list_release_id(struct link_table *table,
	352	uint64_t id, int type)
39037602 A	353	{
	354	return lt_elem_list_release(table, lt_elem_list_first(table, id), type);
	355	}
	356
	357	#endif /* XNU_KERNEL_PRIVATE */