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
34#define ltdbg(fmt,...) \
35 printf("LT[%s]: " fmt "\n", __func__, ## __VA_ARGS__)
36#else
37#define ltdbg(fmt,...) do { } while (0)
38#endif
39
40#ifdef LTABLE_VERBOSE_DEBUG
41#define ltdbg_v(fmt,...) \
42 printf("LT[v:%s]: " fmt "\n", __func__, ## __VA_ARGS__)
43#else
44#define ltdbg_v(fmt,...) do { } while (0)
45#endif
46
47#define ltinfo(fmt,...) \
48 printf("LT[%s]: " fmt "\n", __func__, ## __VA_ARGS__)
49
50#define lterr(fmt,...) \
51 printf("LT[%s] ERROR: " fmt "\n", __func__, ## __VA_ARGS__)
52
53
54
55/* ----------------------------------------------------------------------
56 *
57 * Lockless Link Table Interface
58 *
59 * ---------------------------------------------------------------------- */
60
61struct 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 */
70 generation:46;
71 };
72 };
73};
74
75/* this _must_ match the idx bitfield definition in struct ltable_id */
76#define LT_IDX_MAX (0x3ffff)
77
78extern vm_size_t g_lt_max_tbl_size;
79
80
81struct 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 */
88#define LT_BITS_REFCNT_MASK (0x1FFFFFFF)
89#define LT_BITS_REFCNT_SHIFT (0)
90#define LT_BITS_REFCNT (LT_BITS_REFCNT_MASK << LT_BITS_REFCNT_SHIFT)
91
92#define LT_BITS_TYPE_MASK (0x3)
93#define LT_BITS_TYPE_SHIFT (29)
94#define LT_BITS_TYPE (LT_BITS_TYPE_MASK << LT_BITS_TYPE_SHIFT)
95
96#define LT_BITS_VALID_MASK (0x1)
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
109enum lt_elem_type {
110 LT_FREE = 0,
111 LT_ELEM = 1,
112 LT_LINK = 2,
113 LT_RESERVED = 3,
114};
115
116struct link_table;
117typedef 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 */
129struct 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 */
172extern void ltable_bootstrap(void);
173
174
175/**
176 * ltable_init: initialize a link table with given parameters
177 *
178 */
179extern void ltable_init(struct link_table *table, const char *name,
180 uint32_t max_tbl_elem, uint32_t elem_sz,
181 ltable_poison_func poison);
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 */
191extern 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 */
206extern __attribute__((noinline))
207struct lt_elem *ltable_alloc_elem(struct link_table *table, int type,
208 int nelem, int nattempts);
209
210
211#if DEVELOPMENT || DEBUG
212/**
213 * ltable_nelem: returns how many elements are used in this
214 * table.
215 */
216extern
217int ltable_nelem(struct link_table *table);
218#endif
219
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 */
228extern void ltable_realloc_elem(struct link_table *table,
229 struct lt_elem *elem, int type);
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 */
242extern 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 */
253extern 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 */
261extern 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 */
269extern 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 */
290extern int lt_elem_list_link(struct link_table *table,
291 struct lt_elem *parent, struct lt_elem *child);
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 */
303extern 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 */
311extern struct lt_elem *lt_elem_list_next(struct link_table *table,
312 struct lt_elem *elem);
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 */
322extern struct lt_elem *lt_elem_list_break(struct link_table *table,
323 struct lt_elem *elem);
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 */
335extern struct lt_elem *lt_elem_list_pop(struct link_table *table,
336 uint64_t *id, int type);
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 */
346extern int lt_elem_list_release(struct link_table *table,
347 struct lt_elem *head,
348 int __assert_only type);
349
350static inline int lt_elem_list_release_id(struct link_table *table,
351 uint64_t id, int type)
352{
353 return lt_elem_list_release(table, lt_elem_list_first(table, id), type);
354}
355
356#endif /* XNU_KERNEL_PRIVATE */
357