1 /* 2 * Copyright (c) 2022 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 29 #ifndef _KERN_COMPACT_ID_H_ 30 #define _KERN_COMPACT_ID_H_ 31 32 #include <stdbool.h> 33 #include <stdint.h> 34 #include <kern/bits.h> 35 #include <kern/startup.h> 36 #include <kern/locks.h> 37 38 __BEGIN_DECLS 39 #pragma GCC visibility push(hidden) 40 41 #define COMPACT_ID_SHIFT_BASE (10) 42 #define COMPACT_ID_COUNT_BASE (1u << COMPACT_ID_SHIFT_BASE) 43 #define COMPACT_ID_SLAB_COUNT (12) 44 #define COMPACT_ID_MAX ((COMPACT_ID_COUNT_BASE << (COMPACT_ID_SLAB_COUNT - 1)) - 1u) 45 46 typedef uint32_t compact_id_t; 47 typedef struct compact_id_table *compact_id_table_t; 48 49 /* 50 * @struct compact_id_table 51 * 52 * @discussion 53 * A compact ID table contains an array of COMPACT_ID_SLAB_COUNT 54 * compact_id_slab slabs. 55 * 56 * Each slab contains a different number of values, depending on its position 57 * within the cidt_slabs. 58 * 59 * The entries in the table are never deallocated once created, 60 * which allows to access the table without holding a lock. 61 * 62 * Slots within each slab can be re-used once an association 63 * with a prior value has been released. 64 * 65 * The first 2 entries will have COMPACT_ID_COUNT_BASE entries, 66 * all others will have size COMPACT_ID_COUNT_BASE * 2^(index - 1). 67 * 68 * |BASE|BASE|2BASE|4BASE|...|2^(MAX-2)BASE| 69 * 0 1 2 3 MAX-1 70 * 71 * This can allow a maximum capacity of BASE(2^(MAX-1)) values 72 * 73 * Because COMPACT_ID_COUNT_BASE is a power of 2, it lets us 74 * lookup into the tables very efficiently: each table slab 75 * contains all the compact IDs between subsequent power of 2 76 * of COMPACT_ID_COUNT_BASE. 77 * 78 * |0 -> (B-1)|B -> (2B-1)|2B -> (4B-1)|...|2^(MAX-2)B -> ((2^(MAX-1)B)-1)| 79 * 0 1 2 MAX-1 80 * 81 * By observing the most significant bit of a given compact ID, 82 * we can compute its slab index very efficiently: 83 * 84 * slab_index = clz(COMPACT_ID_COUNT_BASE) - clz(ctid | (COMPACT_ID_COUNT_BASE - 1)) + 1 85 * 86 * Note: because we expect lookups to be common, 87 * cidt_array isn't the real array but shifted 88 * so that dereferencing it with the compact ID 89 * works for any slab. 90 */ 91 struct compact_id_table { 92 /* 93 * slabs first saves one instruction per compact_id_resolve() 94 */ 95 void **cidt_array[COMPACT_ID_SLAB_COUNT]; 96 bitmap_t *cidt_bitmap[COMPACT_ID_SLAB_COUNT]; 97 lck_mtx_t cidt_lock; 98 struct thread *cidt_allocator; 99 bool cidt_waiters; 100 uint32_t cidt_count; 101 compact_id_t cidt_first_free; 102 }; 103 104 extern void compact_id_table_init( 105 compact_id_table_t table); 106 107 extern void **compact_id_resolve( 108 compact_id_table_t table, 109 compact_id_t compact_id) __pure2; 110 111 extern compact_id_t compact_id_get_locked( 112 compact_id_table_t table, 113 compact_id_t limit, 114 void *value); 115 116 extern compact_id_t compact_id_get( 117 compact_id_table_t table, 118 compact_id_t limit, 119 void *value); 120 121 extern void *compact_id_put( 122 compact_id_table_t table, 123 compact_id_t compact_id); 124 125 extern void compact_id_for_each( 126 compact_id_table_t table, 127 uint32_t stride, 128 bool (^cb)(void *v)); 129 130 extern void compact_id_table_lock( 131 compact_id_table_t table); 132 133 extern void compact_id_table_unlock( 134 compact_id_table_t table); 135 136 #define COMPACT_ID_TABLE_DEFINE(class, var) \ 137 static void *var##_array0[COMPACT_ID_COUNT_BASE]; \ 138 static bitmap_t var##_bits0[BITMAP_LEN(COMPACT_ID_COUNT_BASE)] = { \ 139 [0 ... BITMAP_LEN(COMPACT_ID_COUNT_BASE) - 1] = ~0ull, \ 140 }; \ 141 class struct compact_id_table var = { \ 142 .cidt_bitmap[0] = var##_bits0, \ 143 .cidt_array[0] = var##_array0, \ 144 }; \ 145 STARTUP_ARG(LOCKS, STARTUP_RANK_THIRD, compact_id_table_init, &var) 146 147 #pragma GCC visibility pop 148 __END_DECLS 149 150 #endif /* _KERN_COMPACT_ID_H_ */ 151