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 | |
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 */ |
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 | |
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 */ |
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 | |
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, |
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 | */ |
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, |
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 | */ |
216 | extern |
217 | int 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 | */ |
228 | extern 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 | */ |
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, |
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 | */ |
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, |
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 | */ |
322 | extern 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 | */ |
335 | extern 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 | */ |
346 | extern int lt_elem_list_release(struct link_table *table, |
347 | struct lt_elem *head, |
348 | int __assert_only type); |
349 | |
350 | static 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 | |