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#include <kern/cpu_data.h>
29#include <kern/kern_types.h>
30#include <kern/locks.h>
31#include <kern/ltable.h>
32#include <kern/zalloc.h>
33#include <libkern/OSAtomic.h>
34#include <pexpert/pexpert.h>
35#include <vm/vm_kern.h>
36
37
38#define P2ROUNDUP(x, align) (-(-((uint32_t)(x)) & -(align)))
39#define ROUNDDOWN(x,y) (((x)/(y))*(y))
40
41/* ----------------------------------------------------------------------
42 *
43 * Lockless Link Table Interface
44 *
45 * ---------------------------------------------------------------------- */
46
47vm_size_t g_lt_max_tbl_size;
48static lck_grp_t g_lt_lck_grp;
49
50/* default VA space for link tables (zone allocated) */
51#define DEFAULT_MAX_TABLE_SIZE P2ROUNDUP(8 * 1024 * 1024, PAGE_SIZE)
52
53#if DEVELOPMENT || DEBUG
54/* global for lldb macros */
55uint64_t g_lt_idx_max = LT_IDX_MAX;
56#endif
57
58
59/* construct a link table element from an offset and mask into a slab */
60#define lt_elem_ofst_slab(slab, slab_msk, ofst) \
61 /* cast through 'void *' to avoid compiler alignment warning messages */ \
62 ((struct lt_elem *)((void *)((uintptr_t)(slab) + ((ofst) & (slab_msk)))))
63
64#if CONFIG_LTABLE_STATS
65/* version that makes no assumption on waste within a slab */
66static inline struct lt_elem *
67lt_elem_idx(struct link_table *table, uint32_t idx)
68{
69 int slab_idx = idx / table->slab_elem;
70 struct lt_elem *slab = table->table[slab_idx];
71 if (!slab)
72 panic("Invalid index:%d slab:%d (NULL) for table:%p\n",
73 idx, slab_idx, table);
74 assert(slab->lt_id.idx <= idx && (slab->lt_id.idx + table->slab_elem) > idx);
75 return lt_elem_ofst_slab(slab, table->slab_msk, (idx - slab->lt_id.idx) * table->elem_sz);
76}
77#else /* !CONFIG_LTABLE_STATS */
78/* verion that assumes 100% ultilization of slabs (no waste) */
79static inline struct lt_elem *
80lt_elem_idx(struct link_table *table, uint32_t idx)
81{
82 uint32_t ofst = idx * table->elem_sz;
83 struct lt_elem *slab = table->table[ofst >> table->slab_shift];
84 if (!slab)
85 panic("Invalid index:%d slab:%d (NULL) for table:%p\n",
86 idx, (ofst >> table->slab_shift), table);
87 assert(slab->lt_id.idx <= idx && (slab->lt_id.idx + table->slab_elem) > idx);
88 return lt_elem_ofst_slab(slab, table->slab_msk, ofst);
89}
90#endif /* CONFIG_LTABLE_STATS */
91
92static int __assert_only
93lt_elem_in_range(struct lt_elem *elem, struct link_table *table)
94{
95 struct lt_elem **base = table->table;
96 uintptr_t e = (uintptr_t)elem;
97 assert(base != NULL);
98 while (*base != NULL) {
99 uintptr_t b = (uintptr_t)(*base);
100 if (e >= b && e < b + table->slab_sz)
101 return 1;
102 base++;
103 if ((uintptr_t)base >= (uintptr_t)table->table + PAGE_SIZE)
104 return 0;
105 }
106 return 0;
107}
108
109
110/**
111 * lt_elem_invalidate: mark 'elem' as invalid
112 *
113 * NOTE: this does _not_ get or put a reference on 'elem'
114 */
115void lt_elem_invalidate(struct lt_elem *elem)
116{
117 uint32_t __assert_only old = OSBitAndAtomic(~LT_BITS_VALID, &elem->lt_bits);
118 OSMemoryBarrier();
119 assert(((lt_bits_type(old) != LT_RESERVED) && (old & LT_BITS_VALID)) ||
120 ((lt_bits_type(old) == LT_RESERVED) && !(old & LT_BITS_VALID)));
121}
122
123/**
124 * lt_elem_mkvalid: mark 'elem' as valid
125 *
126 * NOTE: this does _not_ get or put a reference on 'elem'
127 */
128void lt_elem_mkvalid(struct lt_elem *elem)
129{
130 uint32_t __assert_only old = OSBitOrAtomic(LT_BITS_VALID, &elem->lt_bits);
131 OSMemoryBarrier();
132 assert(!(old & LT_BITS_VALID));
133}
134
135static void lt_elem_set_type(struct lt_elem *elem, int type)
136{
137 uint32_t old_bits, new_bits;
138 do {
139 old_bits = elem->lt_bits;
140 new_bits = (old_bits & ~LT_BITS_TYPE) |
141 ((type & LT_BITS_TYPE_MASK) << LT_BITS_TYPE_SHIFT);
142 } while (OSCompareAndSwap(old_bits, new_bits, &elem->lt_bits) == FALSE);
143 OSMemoryBarrier();
144}
145
146
147/**
148 * ltable_bootstrap: bootstrap a link table
149 *
150 * Called once at system boot
151 */
152void ltable_bootstrap(void)
153{
154 static int s_is_bootstrapped = 0;
155
156 uint32_t tmp32 = 0;
157
158 if (s_is_bootstrapped)
159 return;
160 s_is_bootstrapped = 1;
161
162 g_lt_max_tbl_size = DEFAULT_MAX_TABLE_SIZE;
163 if (PE_parse_boot_argn("lt_tbl_size", &tmp32, sizeof(tmp32)) == TRUE)
164 g_lt_max_tbl_size = (vm_size_t)P2ROUNDUP(tmp32, PAGE_SIZE);
165
166 lck_grp_init(&g_lt_lck_grp, "link_table_locks", LCK_GRP_ATTR_NULL);
167}
168
169/**
170 * ltable_init: initialize a link table with given parameters
171 *
172 */
173void ltable_init(struct link_table *table, const char *name,
174 uint32_t max_tbl_elem, uint32_t elem_sz,
175 ltable_poison_func poison)
176{
177 kern_return_t kr;
178 uint32_t slab_sz, slab_shift, slab_msk, slab_elem;
179 zone_t slab_zone;
180 size_t max_tbl_sz;
181 struct lt_elem *e, **base;
182
183#ifndef CONFIG_LTABLE_STATS
184 /* the element size _must_ be a power of two! */
185 if ((elem_sz & (elem_sz - 1)) != 0)
186 panic("elem_sz:%d for table:'%s' must be a power of two!",
187 elem_sz, name);
188#endif
189
190 /*
191 * First, allocate a single page of memory to act as the base
192 * for the table's element slabs
193 */
194 kr = kernel_memory_allocate(kernel_map, (vm_offset_t *)&base,
195 PAGE_SIZE, 0, KMA_NOPAGEWAIT, VM_KERN_MEMORY_LTABLE);
196 if (kr != KERN_SUCCESS)
197 panic("Cannot initialize %s table: "
198 "kernel_memory_allocate failed:%d\n", name, kr);
199 memset(base, 0, PAGE_SIZE);
200
201 /*
202 * Based on the maximum table size, calculate the slab size:
203 * we allocate 1 page of slab pointers for the table, and we need to
204 * index elements of 'elem_sz', this gives us the slab size based on
205 * the maximum size the table should grow.
206 */
207 max_tbl_sz = (max_tbl_elem * elem_sz);
208 max_tbl_sz = P2ROUNDUP(max_tbl_sz, PAGE_SIZE);
209
210 /* system maximum table size divided by number of slots in a page */
211 slab_sz = (uint32_t)(max_tbl_sz / (PAGE_SIZE / (sizeof(void *))));
212 if (slab_sz < PAGE_SIZE)
213 slab_sz = PAGE_SIZE;
214
215 /* make sure the slab size is a power of two */
216 slab_shift = 0;
217 slab_msk = ~0;
218 for (uint32_t i = 0; i < 31; i++) {
219 uint32_t bit = (1 << i);
220 if ((slab_sz & bit) == slab_sz) {
221 slab_shift = i;
222 slab_msk = 0;
223 for (uint32_t j = 0; j < i; j++)
224 slab_msk |= (1 << j);
225 break;
226 }
227 slab_sz &= ~bit;
228 }
229 slab_elem = slab_sz / elem_sz;
230
231 /* initialize the table's slab zone (for table growth) */
232 ltdbg("Initializing %s zone: slab:%d (%d,0x%x) max:%ld",
233 name, slab_sz, slab_shift, slab_msk, max_tbl_sz);
234 slab_zone = zinit(slab_sz, max_tbl_sz, slab_sz, name);
235 assert(slab_zone != ZONE_NULL);
236
237 /* allocate the first slab and populate it */
238 base[0] = (struct lt_elem *)zalloc(slab_zone);
239 if (base[0] == NULL)
240 panic("Can't allocate a %s table slab from zone:%p",
241 name, slab_zone);
242
243 memset(base[0], 0, slab_sz);
244
245 /* setup the initial freelist */
246 ltdbg("initializing %d links (%d bytes each)...", slab_elem, elem_sz);
247 for (unsigned l = 0; l < slab_elem; l++) {
248 e = lt_elem_ofst_slab(base[0], slab_msk, l * elem_sz);
249 e->lt_id.idx = l;
250 /*
251 * setting generation to 0 ensures that a setid of 0 is
252 * invalid because the generation will be incremented before
253 * each element's allocation.
254 */
255 e->lt_id.generation = 0;
256 e->lt_next_idx = l + 1;
257 }
258
259 /* make sure the last free element points to a never-valid idx */
260 e = lt_elem_ofst_slab(base[0], slab_msk, (slab_elem - 1) * elem_sz);
261 e->lt_next_idx = LT_IDX_MAX;
262
263 lck_mtx_init(&table->lock, &g_lt_lck_grp, LCK_ATTR_NULL);
264
265 table->slab_sz = slab_sz;
266 table->slab_shift = slab_shift;
267 table->slab_msk = slab_msk;
268 table->slab_elem = slab_elem;
269 table->slab_zone = slab_zone;
270
271 table->elem_sz = elem_sz;
272 table->nelem = slab_elem;
273 table->used_elem = 0;
274 table->elem_sz = elem_sz;
275 table->poison = poison;
276
277 table->table = base;
278 table->next_free_slab = &base[1];
279 table->free_list.id = base[0]->lt_id.id;
280
281#if CONFIG_LTABLE_STATS
282 table->nslabs = 1;
283 table->nallocs = 0;
284 table->nreallocs = 0;
285 table->npreposts = 0;
286 table->nreservations = 0;
287 table->nreserved_releases = 0;
288
289 table->max_used = 0;
290 table->avg_used = 0;
291 table->max_reservations = 0;
292 table->avg_reservations = 0;
293#endif
294}
295
296
297/**
298 * ltable_grow: grow a link table by adding another 'slab' of table elements
299 *
300 * Conditions:
301 * table mutex is unlocked
302 * calling thread can block
303 */
304void ltable_grow(struct link_table *table, uint32_t min_free)
305{
306 struct lt_elem *slab, **slot;
307 struct lt_elem *e = NULL, *first_new_elem, *last_new_elem;
308 struct ltable_id free_id;
309 uint32_t free_elem;
310
311 assert(get_preemption_level() == 0);
312 assert(table && table->slab_zone);
313
314 lck_mtx_lock(&table->lock);
315
316 free_elem = table->nelem - table->used_elem;
317
318 /*
319 * If the caller just wanted to ensure a minimum number of elements,
320 * do that (and don't just blindly grow the table). Also, don't grow
321 * the table unnecessarily - we could have been beaten by a higher
322 * priority thread who acquired the lock and grew the table before we
323 * got here.
324 */
325 if (free_elem > min_free) {
326 lck_mtx_unlock(&table->lock);
327 return;
328 }
329
330 /* we are now committed to table growth */
331 ltdbg_v("BEGIN");
332
333 if (table->next_free_slab == NULL) {
334 /*
335 * before we panic, check one more time to see if any other
336 * threads have free'd from space in the table.
337 */
338 if ((table->nelem - table->used_elem) > 0) {
339 /* there's at least 1 free element: don't panic yet */
340 lck_mtx_unlock(&table->lock);
341 return;
342 }
343 panic("No more room to grow table: %p (nelem: %d, used: %d)",
344 table, table->nelem, table->used_elem);
345 }
346 slot = table->next_free_slab;
347 table->next_free_slab++;
348 if ((uintptr_t)table->next_free_slab >= (uintptr_t)table->table + PAGE_SIZE)
349 table->next_free_slab = NULL;
350
351 assert(*slot == NULL);
352
353 /* allocate another slab */
354 slab = (struct lt_elem *)zalloc(table->slab_zone);
355 if (slab == NULL)
356 panic("Can't allocate a %s table (%p) slab from zone:%p",
357 table->slab_zone->zone_name, table, table->slab_zone);
358
359 memset(slab, 0, table->slab_sz);
360
361 /* put the new elements into a freelist */
362 ltdbg_v(" init %d new links...", table->slab_elem);
363 for (unsigned l = 0; l < table->slab_elem; l++) {
364 uint32_t idx = l + table->nelem;
365 if (idx >= (LT_IDX_MAX - 1))
366 break; /* the last element of the last slab */
367 e = lt_elem_ofst_slab(slab, table->slab_msk, l * table->elem_sz);
368 e->lt_id.idx = idx;
369 e->lt_next_idx = idx + 1;
370 }
371 last_new_elem = e;
372 assert(last_new_elem != NULL);
373
374 first_new_elem = lt_elem_ofst_slab(slab, table->slab_msk, 0);
375
376 /* update table book keeping, and atomically swap the freelist head */
377 *slot = slab;
378 if (table->nelem + table->slab_elem >= LT_IDX_MAX)
379 table->nelem = LT_IDX_MAX - 1;
380 else
381 table->nelem += table->slab_elem;
382
383#if CONFIG_LTABLE_STATS
384 table->nslabs += 1;
385#endif
386
387 /*
388 * The atomic swap of the free list head marks the end of table
389 * growth. Incoming requests may now use the newly allocated slab
390 * of table elements
391 */
392 free_id = table->free_list;
393 /* connect the existing free list to the end of the new free list */
394 last_new_elem->lt_next_idx = free_id.idx;
395 while (OSCompareAndSwap64(free_id.id, first_new_elem->lt_id.id,
396 &table->free_list.id) == FALSE) {
397 OSMemoryBarrier();
398 free_id = table->free_list;
399 last_new_elem->lt_next_idx = free_id.idx;
400 }
401 OSMemoryBarrier();
402
403 lck_mtx_unlock(&table->lock);
404
405 return;
406}
407
408#if DEVELOPMENT || DEBUG
409
410int
411ltable_nelem(struct link_table *table)
412{
413 int nelem = 0;
414
415 lck_mtx_lock(&table->lock);
416
417 nelem = table->used_elem;
418
419 lck_mtx_unlock(&table->lock);
420
421 return nelem;
422}
423#endif
424
425/**
426 * ltable_alloc_elem: allocate one or more elements from a given table
427 *
428 * The returned element(s) will be of type 'type', but will remain invalid.
429 *
430 * If the caller has disabled preemption, then this function may (rarely) spin
431 * waiting either for another thread to either release 'nelem' table elements,
432 * or grow the table.
433 *
434 * If the caller can block, then this function may (rarely) block while
435 * the table grows to meet the demand for 'nelem' element(s).
436 */
437__attribute__((noinline))
438struct lt_elem *ltable_alloc_elem(struct link_table *table, int type,
439 int nelem, int nattempts)
440{
441 int nspins = 0, ntries = 0, nalloc = 0;
442 uint32_t table_size;
443 struct lt_elem *elem = NULL;
444 struct ltable_id free_id, next_id;
445
446 static const int max_retries = 500;
447
448 if (type != LT_ELEM && type != LT_LINK && type != LT_RESERVED)
449 panic("link_table_aloc of invalid elem type:%d from table @%p",
450 type, table);
451
452 assert(nelem > 0);
453
454 /*
455 * If the callers only wants to try a certain number of times, make it
456 * look like we've already made (MAX - nattempts) tries at allocation
457 */
458 if (nattempts > 0 && nattempts <= max_retries) {
459 ntries = max_retries - nattempts;
460 }
461
462try_again:
463 elem = NULL;
464 if (ntries++ > max_retries) {
465 struct lt_elem *tmp;
466 if (nattempts > 0) {
467 /*
468 * The caller specified a particular number of
469 * attempts before failure, so it's expected that
470 * they're prepared to handle a NULL return.
471 */
472 return NULL;
473 }
474
475 if (table->used_elem + nelem >= table_size)
476 panic("No more room to grow table: 0x%p size:%d, used:%d, requested elem:%d",
477 table, table_size, table->used_elem, nelem);
478 if (nelem == 1)
479 panic("Too many alloc retries: %d, table:%p, type:%d, nelem:%d",
480 ntries, table, type, nelem);
481 /* don't panic: try allocating one-at-a-time */
482 while (nelem > 0) {
483 tmp = ltable_alloc_elem(table, type, 1, nattempts);
484 if (elem)
485 lt_elem_list_link(table, tmp, elem);
486 elem = tmp;
487 --nelem;
488 }
489 assert(elem != NULL);
490 return elem;
491 }
492
493 nalloc = 0;
494 table_size = table->nelem;
495
496 if (table->used_elem + nelem >= table_size) {
497 if (get_preemption_level() != 0) {
498#if CONFIG_LTABLE_STATS
499 table->nspins += 1;
500#endif
501 /*
502 * We may have just raced with table growth: check
503 * again to make sure there really isn't any space.
504 */
505 if (++nspins > 4)
506 panic("Can't grow table %p with preemption"
507 " disabled!", table);
508 delay(1);
509 goto try_again;
510 }
511 ltable_grow(table, nelem);
512 goto try_again;
513 }
514
515 /* read this value only once before the CAS */
516 free_id = table->free_list;
517 if (free_id.idx >= table_size)
518 goto try_again;
519
520 /*
521 * Find the item on the free list which will become the new free list
522 * head, but be careful not to modify any memory (read only)! Other
523 * threads can alter table state at any time up until the CAS. We
524 * don't modify any memory until we've successfully swapped out the
525 * free list head with the one we've investigated.
526 */
527 for (struct lt_elem *next_elem = lt_elem_idx(table, free_id.idx);
528 nalloc < nelem;
529 nalloc++) {
530 elem = next_elem;
531 next_id.generation = 0;
532 next_id.idx = next_elem->lt_next_idx;
533 if (next_id.idx < table->nelem) {
534 next_elem = lt_elem_idx(table, next_id.idx);
535 next_id.id = next_elem->lt_id.id;
536 } else {
537 goto try_again;
538 }
539 }
540 /* 'elem' points to the last element being allocated */
541
542 if (OSCompareAndSwap64(free_id.id, next_id.id,
543 &table->free_list.id) == FALSE)
544 goto try_again;
545
546 /* load barrier */
547 OSMemoryBarrier();
548
549 /*
550 * After the CAS, we know that we own free_id, and it points to a
551 * valid table entry (checked above). Grab the table pointer and
552 * reset some values.
553 */
554 OSAddAtomic(nelem, &table->used_elem);
555
556 /* end the list of allocated elements */
557 elem->lt_next_idx = LT_IDX_MAX;
558 /* reset 'elem' to point to the first allocated element */
559 elem = lt_elem_idx(table, free_id.idx);
560
561 /*
562 * Update the generation count, and return the element(s)
563 * with a single reference (and no valid bit). If the
564 * caller immediately calls _put() on any element, then
565 * it will be released back to the free list. If the caller
566 * subsequently marks the element as valid, then the put
567 * will simply drop the reference.
568 */
569 for (struct lt_elem *tmp = elem; ; ) {
570 assert(!lt_bits_valid(tmp->lt_bits) &&
571 (lt_bits_refcnt(tmp->lt_bits) == 0));
572 --nalloc;
573 tmp->lt_id.generation += 1;
574 tmp->lt_bits = 1;
575 lt_elem_set_type(tmp, type);
576 if (tmp->lt_next_idx == LT_IDX_MAX)
577 break;
578 assert(tmp->lt_next_idx != LT_IDX_MAX);
579 tmp = lt_elem_idx(table, tmp->lt_next_idx);
580 }
581 assert(nalloc == 0);
582
583#if CONFIG_LTABLE_STATS
584 uint64_t nreservations;
585 table->nallocs += nelem;
586 if (type == LT_RESERVED)
587 OSIncrementAtomic64(&table->nreservations);
588 nreservations = table->nreservations;
589 if (table->used_elem > table->max_used)
590 table->max_used = table->used_elem;
591 if (nreservations > table->max_reservations)
592 table->max_reservations = nreservations;
593 table->avg_used = (table->avg_used + table->used_elem) / 2;
594 table->avg_reservations = (table->avg_reservations + nreservations) / 2;
595#endif
596
597 return elem;
598}
599
600
601/**
602 * ltable_realloc_elem: convert a reserved element to a particular type
603 *
604 * This funciton is used to convert reserved elements (not yet marked valid)
605 * to the given 'type'. The generation of 'elem' is incremented, the element
606 * is disconnected from any list to which it belongs, and its type is set to
607 * 'type'.
608 */
609void ltable_realloc_elem(struct link_table *table, struct lt_elem *elem, int type)
610{
611 (void)table;
612 assert(lt_elem_in_range(elem, table) &&
613 !lt_bits_valid(elem->lt_bits));
614
615#if CONFIG_LTABLE_STATS
616 table->nreallocs += 1;
617 if (lt_bits_type(elem->lt_bits) == LT_RESERVED && type != LT_RESERVED) {
618 /*
619 * This isn't under any lock, so we'll clamp it.
620 * the stats are meant to be informative, not perfectly
621 * accurate
622 */
623 OSDecrementAtomic64(&table->nreservations);
624 }
625 table->avg_reservations = (table->avg_reservations + table->nreservations) / 2;
626#endif
627
628 /*
629 * Return the same element with a new generation count, and a
630 * (potentially) new type. Don't touch the refcount: the caller
631 * is responsible for getting that (and the valid bit) correct.
632 */
633 elem->lt_id.generation += 1;
634 elem->lt_next_idx = LT_IDX_MAX;
635 lt_elem_set_type(elem, type);
636
637 return;
638}
639
640
641/**
642 * ltable_free_elem: release an element back to a link table
643 *
644 * Do not call this function directly: use ltable_[get|put]_elem!
645 *
646 * Conditions:
647 * 'elem' was originally allocated from 'table'
648 * 'elem' is _not_ marked valid
649 * 'elem' has a reference count of 0
650 */
651static void ltable_free_elem(struct link_table *table, struct lt_elem *elem)
652{
653 struct ltable_id next_id;
654
655 assert(lt_elem_in_range(elem, table) &&
656 !lt_bits_valid(elem->lt_bits) &&
657 (lt_bits_refcnt(elem->lt_bits) == 0));
658
659 OSDecrementAtomic(&table->used_elem);
660
661#if CONFIG_LTABLE_STATS
662 table->avg_used = (table->avg_used + table->used_elem) / 2;
663 if (lt_bits_type(elem->lt_bits) == LT_RESERVED)
664 OSDecrementAtomic64(&table->nreservations);
665 table->avg_reservations = (table->avg_reservations + table->nreservations) / 2;
666#endif
667
668 elem->lt_bits = 0;
669
670 if (table->poison)
671 (table->poison)(table, elem);
672
673again:
674 next_id = table->free_list;
675 if (next_id.idx >= table->nelem)
676 elem->lt_next_idx = LT_IDX_MAX;
677 else
678 elem->lt_next_idx = next_id.idx;
679
680 /* store barrier */
681 OSMemoryBarrier();
682 if (OSCompareAndSwap64(next_id.id, elem->lt_id.id,
683 &table->free_list.id) == FALSE)
684 goto again;
685}
686
687
688/**
689 * ltable_get_elem: get a reference to a table element identified by 'id'
690 *
691 * Returns a reference to the table element associated with the given 'id', or
692 * NULL if the 'id' was invalid or does not exist in 'table'. The caller is
693 * responsible to release the reference using ltable_put_elem().
694 *
695 * NOTE: if the table element pointed to by 'id' is marked as invalid,
696 * this function will return NULL.
697 */
698struct lt_elem *ltable_get_elem(struct link_table *table, uint64_t id)
699{
700 struct lt_elem *elem;
701 uint32_t idx, bits, new_bits;
702
703 /*
704 * Here we have a reference to the table which is guaranteed to remain
705 * valid until we drop the reference
706 */
707
708 idx = ((struct ltable_id *)&id)->idx;
709
710 if (idx >= table->nelem)
711 panic("id:0x%llx : idx:%d > %d", id, idx, table->nelem);
712
713 elem = lt_elem_idx(table, idx);
714
715 /* verify the validity by taking a reference on the table object */
716 bits = elem->lt_bits;
717 if (!lt_bits_valid(bits))
718 return NULL;
719
720 /*
721 * do a pre-verify on the element ID to potentially
722 * avoid 2 compare-and-swaps
723 */
724 if (elem->lt_id.id != id)
725 return NULL;
726
727 new_bits = bits + 1;
728
729 /* check for overflow */
730 assert(lt_bits_refcnt(new_bits) > 0);
731
732 while (OSCompareAndSwap(bits, new_bits, &elem->lt_bits) == FALSE) {
733 /*
734 * either the element became invalid,
735 * or someone else grabbed/removed a reference.
736 */
737 bits = elem->lt_bits;
738 if (!lt_bits_valid(bits)) {
739 /* don't return invalid elements */
740 return NULL;
741 }
742 new_bits = bits + 1;
743 assert(lt_bits_refcnt(new_bits) > 0);
744 }
745
746 /* load barrier */
747 OSMemoryBarrier();
748
749 /* check to see that our reference is to the same generation! */
750 if (elem->lt_id.id != id) {
751 /*
752 ltdbg("ID:0x%llx table generation (%d) != %d",
753 id, elem->lt_id.generation,
754 ((struct ltable_id *)&id)->generation);
755 */
756 ltable_put_elem(table, elem);
757 return NULL;
758 }
759
760 /* We now have a reference on a valid object */
761 return elem;
762}
763
764/**
765 * ltable_put_elem: release a reference to table element
766 *
767 * This function releases a reference taken on a table element via
768 * ltable_get_elem(). This function will release the element back to 'table'
769 * when the reference count goes to 0 AND the element has been marked as
770 * invalid.
771 */
772void ltable_put_elem(struct link_table *table, struct lt_elem *elem)
773{
774 uint32_t bits, new_bits;
775
776 assert(lt_elem_in_range(elem, table));
777
778 bits = elem->lt_bits;
779 new_bits = bits - 1;
780
781 /* check for underflow */
782 assert(lt_bits_refcnt(new_bits) < LT_BITS_REFCNT_MASK);
783
784 while (OSCompareAndSwap(bits, new_bits, &elem->lt_bits) == FALSE) {
785 bits = elem->lt_bits;
786 new_bits = bits - 1;
787 /* catch underflow */
788 assert(lt_bits_refcnt(new_bits) < LT_BITS_REFCNT_MASK);
789 }
790
791 /* load barrier */
792 OSMemoryBarrier();
793
794 /*
795 * if this was the last reference, and it was marked as invalid,
796 * then we can add this link object back to the free list
797 */
798 if (!lt_bits_valid(new_bits) && (lt_bits_refcnt(new_bits) == 0))
799 ltable_free_elem(table, elem);
800
801 return;
802}
803
804
805/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
806 *
807 * API: lt_elem_list_...
808 *
809 * Reuse the free list linkage member, 'lt_next_idx' of a table element
810 * in a slightly more generic singly-linked list. All members of this
811 * list have been allocated from a table, but have not been made valid.
812 *
813 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
814
815/**
816 * lt_elem_list_link: link a child onto a parent
817 *
818 * Note that if 'parent' is the head of a list, this function will follow that
819 * list and attach 'child' to the end of it. In the simplest case, this
820 * results in: parent->child
821 * however this could also result in: parent->...->child
822 */
823int lt_elem_list_link(struct link_table *table, struct lt_elem *parent, struct lt_elem *child)
824{
825 int nelem = 1;
826
827 assert(lt_elem_in_range(parent, table));
828
829 /* find the end of the parent's list */
830 while (parent->lt_next_idx != LT_IDX_MAX) {
831 assert(parent->lt_next_idx < table->nelem);
832 parent = lt_elem_idx(table, parent->lt_next_idx);
833 nelem++;
834 }
835
836 if (child) {
837 assert(lt_elem_in_range(child, table));
838 parent->lt_next_idx = child->lt_id.idx;
839 }
840
841 return nelem;
842}
843
844
845/**
846 * lt_elem_list_first: obtain a pointer to the first element of a list.
847 *
848 * This function converts the head of a singly-linked list, 'id', into a real
849 * lt_elem object and returns a pointer to the object.
850 *
851 * It does _not_ take an extra reference on the object: the list implicitly
852 * holds that reference.
853 */
854struct lt_elem *lt_elem_list_first(struct link_table *table, uint64_t id)
855{
856 uint32_t idx;
857 struct lt_elem *elem = NULL;
858
859 if (id == 0)
860 return NULL;
861
862 idx = ((struct ltable_id *)&id)->idx;
863
864 if (idx > table->nelem)
865 panic("Invalid element for id:0x%llx", id);
866 elem = lt_elem_idx(table, idx);
867
868 /* invalid element: reserved ID was probably already reallocated */
869 if (elem->lt_id.id != id)
870 return NULL;
871
872 /* the returned element should _not_ be marked valid! */
873 if (lt_bits_valid(elem->lt_bits) ||
874 lt_bits_type(elem->lt_bits) != LT_RESERVED ||
875 lt_bits_refcnt(elem->lt_bits) != 1) {
876 panic("Valid/unreserved element %p (0x%x) in reserved list",
877 elem, elem->lt_bits);
878 }
879
880 return elem;
881}
882
883
884/**
885 * lt_elem_list_next: return the item subsequent to 'elem' in a list
886 *
887 * Note that this will return NULL if 'elem' is actually the end of the list.
888 */
889struct lt_elem *lt_elem_list_next(struct link_table *table, struct lt_elem *head)
890{
891 struct lt_elem *elem;
892
893 if (!head)
894 return NULL;
895 if (head->lt_next_idx >= table->nelem)
896 return NULL;
897
898 elem = lt_elem_idx(table, head->lt_next_idx);
899 assert(lt_elem_in_range(elem, table));
900
901 return elem;
902}
903
904
905/**
906 * lt_elem_list_break: break a list in two around 'elem'
907 *
908 * This function will reset the next_idx field of 'elem' (making it the end of
909 * the list), and return the element subsequent to 'elem' in the list
910 * (which could be NULL)
911 */
912struct lt_elem *lt_elem_list_break(struct link_table *table, struct lt_elem *elem)
913{
914 struct lt_elem *next;
915
916 if (!elem)
917 return NULL;
918 next = lt_elem_list_next(table, elem);
919 elem->lt_next_idx = LT_IDX_MAX;
920
921 return next;
922}
923
924
925/**
926 * lt_elem_list_pop: pop an item off the head of a list
927 *
928 * The list head is pointed to by '*id', the element corresponding to '*id' is
929 * returned by this function, and the new list head is returned in the in/out
930 * parameter, '*id'. The caller is responsible for the reference on the
931 * returned object. A realloc is done to reset the type of the object, but it
932 * is still left invalid.
933 */
934struct lt_elem *lt_elem_list_pop(struct link_table *table, uint64_t *id, int type)
935{
936 struct lt_elem *first, *next;
937
938 if (!id || *id == 0)
939 return NULL;
940
941 /* pop an item off the reserved stack */
942
943 first = lt_elem_list_first(table, *id);
944 if (!first) {
945 *id = 0;
946 return NULL;
947 }
948
949 next = lt_elem_list_next(table, first);
950 if (next)
951 *id = next->lt_id.id;
952 else
953 *id = 0;
954
955 ltable_realloc_elem(table, first, type);
956
957 return first;
958}
959
960/**
961 * lt_elem_list_release: free an entire list of reserved elements
962 *
963 * All elements in the list whose first member is 'head' will be released back
964 * to 'table' as free elements. The 'type' parameter is used in development
965 * kernels to assert that all elements on the list are of the given type.
966 */
967int lt_elem_list_release(struct link_table *table, struct lt_elem *head,
968 int __assert_only type)
969{
970 struct lt_elem *elem;
971 struct ltable_id free_id;
972 int nelem = 0;
973
974 if (!head)
975 return 0;
976
977 for (elem = head; ; ) {
978 assert(lt_elem_in_range(elem, table));
979 assert(!lt_bits_valid(elem->lt_bits) && (lt_bits_refcnt(elem->lt_bits) == 1));
980 assert(lt_bits_type(elem->lt_bits) == type);
981
982 nelem++;
983 elem->lt_bits = 0;
984 if (table->poison)
985 (table->poison)(table, elem);
986
987 if (elem->lt_next_idx == LT_IDX_MAX)
988 break;
989 assert(elem->lt_next_idx < table->nelem);
990 elem = lt_elem_idx(table, elem->lt_next_idx);
991 }
992
993 /*
994 * 'elem' now points to the end of our list, and 'head' points to the
995 * beginning. We want to atomically swap the free list pointer with
996 * the 'head' and ensure that 'elem' points to the previous free list
997 * head.
998 */
999
1000again:
1001 free_id = table->free_list;
1002 if (free_id.idx >= table->nelem)
1003 elem->lt_next_idx = LT_IDX_MAX;
1004 else
1005 elem->lt_next_idx = free_id.idx;
1006
1007 /* store barrier */
1008 OSMemoryBarrier();
1009 if (OSCompareAndSwap64(free_id.id, head->lt_id.id,
1010 &table->free_list.id) == FALSE)
1011 goto again;
1012
1013 OSAddAtomic(-nelem, &table->used_elem);
1014 return nelem;
1015}
1016