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 #include <machine/endian.h>
33
34 #if CONFIG_LTABLE_DEBUG
35 #define ltdbg(fmt, ...) \
36 printf("LT[%s]: " fmt "\n", __func__, ## __VA_ARGS__)
37 #else
38 #define ltdbg(fmt, ...) do { } while (0)
39 #endif
40
41 #ifdef LTABLE_VERBOSE_DEBUG
42 #define ltdbg_v(fmt, ...) \
43 printf("LT[v:%s]: " fmt "\n", __func__, ## __VA_ARGS__)
44 #else
45 #define ltdbg_v(fmt, ...) do { } while (0)
46 #endif
47
48 #define ltinfo(fmt, ...) \
49 printf("LT[%s]: " fmt "\n", __func__, ## __VA_ARGS__)
50
51 #define lterr(fmt, ...) \
52 printf("LT[%s] ERROR: " fmt "\n", __func__, ## __VA_ARGS__)
53
54
55
56 /* ----------------------------------------------------------------------
57 *
58 * Lockless Link Table Interface
59 *
60 * ---------------------------------------------------------------------- */
61
62 #define LTABLE_ID_GEN_SHIFT 0
63 #define LTABLE_ID_GEN_BITS 46
64 #define LTABLE_ID_GEN_MASK ((1ull << LTABLE_ID_GEN_BITS) - 1)
65 #define LTABLE_ID_IDX_SHIFT (LTABLE_ID_GEN_BITS)
66 #define LTABLE_ID_IDX_BITS 18
67 #define LTABLE_ID_IDX_MASK ((1ull << LTABLE_ID_IDX_BITS) - 1)
68
69 #define LT_IDX_MAX LTABLE_ID_IDX_MASK
70
71 struct ltable_id {
72 union {
73 uint64_t id;
74 struct {
75 #if BYTE_ORDER == LITTLE_ENDIAN
76 uint64_t generation : LTABLE_ID_GEN_BITS;
77 uint64_t idx : LTABLE_ID_IDX_BITS;
78 #else
79 uint64_t idx : LTABLE_ID_IDX_BITS;
80 uint64_t generation : LTABLE_ID_GEN_BITS;
81 #endif
82 };
83 };
84 };
85
86 extern vm_size_t g_lt_max_tbl_size;
87
88
89 struct lt_elem {
90 struct ltable_id lt_id;
91 uint32_t lt_bits;
92 uint32_t lt_next_idx;
93 };
94
95 /* reference count bits should _always_ be the low-order bits */
96 #define LT_BITS_REFCNT_MASK (0x1FFFFFFFU)
97 #define LT_BITS_REFCNT_SHIFT (0)
98 #define LT_BITS_REFCNT (LT_BITS_REFCNT_MASK << LT_BITS_REFCNT_SHIFT)
99
100 #define LT_BITS_TYPE_MASK (0x3U)
101 #define LT_BITS_TYPE_SHIFT (29)
102 #define LT_BITS_TYPE (LT_BITS_TYPE_MASK << LT_BITS_TYPE_SHIFT)
103
104 #define LT_BITS_VALID_MASK (0x1U)
105 #define LT_BITS_VALID_SHIFT (31)
106 #define LT_BITS_VALID (LT_BITS_VALID_MASK << LT_BITS_VALID_SHIFT)
107
108 #define lt_bits_refcnt(bits) \
109 (((bits) >> LT_BITS_REFCNT_SHIFT) & LT_BITS_REFCNT_MASK)
110
111 #define lt_bits_type(bits) \
112 (((bits) >> LT_BITS_TYPE_SHIFT) & LT_BITS_TYPE_MASK)
113
114 #define lt_bits_valid(bits) \
115 ((bits) & LT_BITS_VALID)
116
117 enum lt_elem_type {
118 LT_FREE = 0,
119 LT_ELEM = 1,
120 LT_LINK = 2,
121 LT_RESERVED = 3,
122 };
123
124 struct link_table;
125 typedef void (*ltable_poison_func)(struct link_table *, struct lt_elem *);
126
127 /*
128 * link_table structure
129 *
130 * A link table is a container for slabs of elements. Each slab is 'slab_sz'
131 * bytes and contains 'slab_sz/elem_sz' elements (of 'elem_sz' bytes each).
132 * These slabs allow the table to be broken up into potentially dis-contiguous
133 * VA space. On 32-bit platforms with large amounts of physical RAM, this is
134 * quite important. Keeping slabs like this slightly complicates retrieval of
135 * table elements, but not by much.
136 */
137 struct link_table {
138 struct lt_elem **table; /* an array of 'slabs' of elements */
139 struct lt_elem **next_free_slab;
140 struct ltable_id free_list __attribute__((aligned(8)));
141
142 uint32_t elem_sz; /* size of a table element (bytes) */
143 uint32_t slab_shift;
144 uint32_t slab_msk;
145 uint32_t slab_elem;
146 uint32_t slab_sz; /* size of a table 'slab' object (bytes) */
147
148 uint32_t nelem;
149 uint32_t used_elem;
150 zone_t slab_zone;
151
152 ltable_poison_func poison;
153
154 lck_mtx_t lock;
155 uint32_t state;
156
157 #if CONFIG_LTABLE_STATS
158 uint32_t nslabs;
159
160 uint64_t nallocs;
161 uint64_t nreallocs;
162 uint64_t npreposts;
163 int64_t nreservations;
164 uint64_t nreserved_releases;
165 uint64_t nspins;
166
167 uint64_t max_used;
168 uint64_t avg_used;
169 uint64_t max_reservations;
170 uint64_t avg_reservations;
171 #endif
172 } __attribute__((aligned(8)));
173
174 /**
175 * ltable_init: initialize a link table with given parameters
176 *
177 */
178 extern void ltable_init(struct link_table *table, const char *name,
179 uint32_t max_tbl_elem, uint32_t elem_sz,
180 ltable_poison_func poison);
181
182
183 /**
184 * ltable_grow: grow a link table by adding another 'slab' of table elements
185 *
186 * Conditions:
187 * table mutex is unlocked
188 * calling thread can block
189 */
190 extern void ltable_grow(struct link_table *table, uint32_t min_free);
191
192
193 /**
194 * ltable_alloc_elem: allocate one or more elements from a given table
195 *
196 * The returned element(s) will be of type 'type', but will remain invalid.
197 *
198 * If the caller has disabled preemption, then this function may (rarely) spin
199 * waiting either for another thread to either release 'nelem' table elements,
200 * or grow the table.
201 *
202 * If the caller can block, then this function may (rarely) block while
203 * the table grows to meet the demand for 'nelem' element(s).
204 */
205 extern __attribute__((noinline))
206 struct lt_elem *ltable_alloc_elem(struct link_table *table, int type,
207 int nelem, int nattempts);
208
209
210 #if DEVELOPMENT || DEBUG
211 /**
212 * ltable_nelem: returns how many elements are used in this
213 * table.
214 */
215 extern
216 int ltable_nelem(struct link_table *table);
217 #endif
218
219 /**
220 * ltable_realloc_elem: convert a reserved element to a particular type
221 *
222 * This funciton is used to convert reserved elements (not yet marked valid)
223 * to the given 'type'. The generation of 'elem' is incremented, the element
224 * is disconnected from any list to which it belongs, and its type is set to
225 * 'type'.
226 */
227 extern void ltable_realloc_elem(struct link_table *table,
228 struct lt_elem *elem, int type);
229
230
231 /**
232 * ltable_get_elem: get a reference to a table element identified by 'id'
233 *
234 * Returns a reference to the table element associated with the given 'id', or
235 * NULL if the 'id' was invalid or does not exist in 'table'. The caller is
236 * responsible to release the reference using ltable_put_elem().
237 *
238 * NOTE: if the table element pointed to by 'id' is marked as invalid,
239 * this function will return NULL.
240 */
241 extern struct lt_elem *ltable_get_elem(struct link_table *table, uint64_t id);
242
243 /**
244 * ltable_elem_valid: returns whether an element ID looks valid.
245 */
246 extern bool ltable_elem_valid(struct link_table *table, uint64_t id);
247
248
249 /**
250 * ltable_put_elem: release a reference to table element
251 *
252 * This function releases a reference taken on a table element via
253 * ltable_get_elem(). This function will release the element back to 'table'
254 * when the reference count goes to 0 AND the element has been marked as
255 * invalid.
256 */
257 extern void ltable_put_elem(struct link_table *table, struct lt_elem *elem);
258
259
260 /**
261 * lt_elem_invalidate: mark 'elem' as invalid
262 *
263 * NOTE: this does _not_ get or put a reference on 'elem'
264 */
265 extern void lt_elem_invalidate(struct lt_elem *elem);
266
267
268 /**
269 * lt_elem_mkvalid: mark 'elem' as valid
270 *
271 * NOTE: this does _not_ get or put a reference on 'elem'
272 */
273 extern void lt_elem_mkvalid(struct lt_elem *elem);
274
275
276 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
277 *
278 * API: lt_elem_list_*
279 *
280 * Reuse the free list linkage member, 'lt_next_idx' of a link table element
281 * in a slightly more generic singly-linked list. All members of this list
282 * have been allocated from a table, but have not been made valid.
283 *
284 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
285
286 /**
287 * lt_elem_list_link: link a child onto a parent
288 *
289 * Note that if 'parent' is the head of a list, this function will follow that
290 * list and attach 'child' to the end of it. In the simplest case, this
291 * results in: parent->child
292 * however this could also result in: parent->...->child
293 */
294 extern int lt_elem_list_link(struct link_table *table,
295 struct lt_elem *parent, struct lt_elem *child);
296
297
298 /**
299 * lt_elem_list_first: obtain a pointer to the first element of a list.
300 *
301 * This function converts the head of a singly-linked list, 'id', into a real
302 * lt_elem object and returns a pointer to the object.
303 *
304 * It does _not_ take an extra reference on the object: the list implicitly
305 * holds that reference.
306 */
307 extern struct lt_elem *lt_elem_list_first(struct link_table *table, uint64_t id);
308
309
310 /**
311 * lt_elem_list_next: return the item subsequent to 'elem' in a list
312 *
313 * Note that this will return NULL if 'elem' is actually the end of the list.
314 */
315 extern struct lt_elem *lt_elem_list_next(struct link_table *table,
316 struct lt_elem *elem);
317
318
319 /**
320 * lt_elem_list_pop: pop an item off the head of a list
321 *
322 * The list head is pointed to by '*id', the element corresponding to '*id' is
323 * returned by this function, and the new list head is returned in the in/out
324 * parameter, '*id'. The caller is responsible for the reference on the
325 * returned object. A realloc is done to reset the type of the object, but it
326 * is still left invalid.
327 */
328 extern struct lt_elem *lt_elem_list_pop(struct link_table *table,
329 uint64_t *id, int type);
330
331
332 /**
333 * lt_elem_list_release: free an entire list of reserved elements
334 *
335 * All elements in the list whose first member is 'head' will be released back
336 * to 'table' as free elements. The 'type' parameter is used in development
337 * kernels to assert that all elements on the list are of the given type.
338 */
339 extern int lt_elem_list_release(struct link_table *table,
340 struct lt_elem *head,
341 int __assert_only type);
342
343 static inline int
lt_elem_list_release_id(struct link_table * table,uint64_t id,int type)344 lt_elem_list_release_id(struct link_table *table,
345 uint64_t id, int type)
346 {
347 return lt_elem_list_release(table, lt_elem_list_first(table, id), type);
348 }
349
350 #endif /* XNU_KERNEL_PRIVATE */
351