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 | #include <kern/compact_id.h> |
30 | #include <kern/locks.h> |
31 | #include <kern/thread.h> |
32 | |
33 | static LCK_GRP_DECLARE(compact_id_lck_grp, "compact_id" ); |
34 | |
35 | #define compact_id_table_sleep(table) \ |
36 | lck_mtx_sleep_with_inheritor(&(table)->cidt_lock, \ |
37 | LCK_SLEEP_DEFAULT, (event_t)(table), (table)->cidt_allocator, \ |
38 | THREAD_UNINT, TIMEOUT_WAIT_FOREVER) |
39 | #define compact_id_table_wake(table) \ |
40 | wakeup_all_with_inheritor((event_t)(table), THREAD_AWAKENED) |
41 | |
42 | static inline uint32_t |
43 | compact_id_prev_max(uint32_t idx) |
44 | { |
45 | /* |
46 | * |BASE|BASE|2BASE|4BASE|...|2^(index-2)BASE|2^(index-1)BASE| |
47 | * 0 1 2 3 index - 1 index |
48 | * |
49 | * the maximum number of values that can be stored on all |
50 | * entries previous to table_index is: |
51 | * CTID_BASE_TABLE * 2^(table_index - 1) |
52 | * for table_index greater then 0. |
53 | */ |
54 | return idx ? COMPACT_ID_COUNT_BASE << (idx - 1) : 0; |
55 | } |
56 | |
57 | static uint32_t |
58 | compact_id_slab_size(uint32_t table_index) |
59 | { |
60 | if (table_index == 0) { |
61 | return COMPACT_ID_COUNT_BASE; |
62 | } |
63 | return COMPACT_ID_COUNT_BASE << (table_index - 1); |
64 | } |
65 | |
66 | static uint32_t |
67 | compact_id_slab_index(compact_id_t cid) |
68 | { |
69 | /* |
70 | * The first 2 entries have size COMPACT_ID_COUNT_BASE, |
71 | * all others have size COMPACT_ID_COUNT_BASE * 2^(i - 1). |
72 | * |
73 | * If you get the the number of the most significant 0s |
74 | * on COMPACT_ID_COUNT_BASE and you subtract how many there |
75 | * are in cidt, you get the index in the table. |
76 | */ |
77 | cid |= COMPACT_ID_COUNT_BASE - 1; |
78 | return __builtin_clz(COMPACT_ID_COUNT_BASE) - __builtin_clz(cid) + 1; |
79 | } |
80 | |
81 | void |
82 | compact_id_table_init(compact_id_table_t table) |
83 | { |
84 | /* lck_group_init knows about what this function does */ |
85 | lck_mtx_init(lck: &table->cidt_lock, grp: &compact_id_lck_grp, LCK_ATTR_NULL); |
86 | } |
87 | |
88 | void ** |
89 | compact_id_resolve(compact_id_table_t table, compact_id_t cid) |
90 | { |
91 | return table->cidt_array[compact_id_slab_index(cid)] + cid; |
92 | } |
93 | |
94 | __attribute__((noinline)) |
95 | static void |
96 | compact_id_table_grow(compact_id_table_t table, uint32_t idx) |
97 | { |
98 | uint32_t size; |
99 | |
100 | /* |
101 | * Let's check if is someone is already |
102 | * allocating memory. |
103 | */ |
104 | if (table->cidt_allocator != NULL) { |
105 | table->cidt_waiters = true; |
106 | compact_id_table_sleep(table); |
107 | return; |
108 | } |
109 | |
110 | /* |
111 | * We need to allocate more memory. |
112 | * Let's unlock and notify |
113 | * other thread who is allocating. |
114 | */ |
115 | table->cidt_allocator = current_thread(); |
116 | compact_id_table_unlock(table); |
117 | |
118 | size = compact_id_slab_size(table_index: idx); |
119 | table->cidt_bitmap[idx] = zalloc_permanent(BITMAP_SIZE(size), ZALIGN(bitmap_t)); |
120 | table->cidt_array[idx] = zalloc_permanent(size * sizeof(thread_t), ZALIGN_PTR); |
121 | /* |
122 | * Note: because we expect lookups to be common, |
123 | * cidt_array isn't the real array but shifted |
124 | * so that dereferencing it with the compact ID |
125 | * works for any slab. |
126 | */ |
127 | table->cidt_array[idx] -= compact_id_prev_max(idx); |
128 | bitmap_full(map: table->cidt_bitmap[idx], nbits: size); |
129 | |
130 | compact_id_table_lock(table); |
131 | assert(table->cidt_allocator == current_thread()); |
132 | table->cidt_allocator = NULL; |
133 | if (table->cidt_waiters) { |
134 | table->cidt_waiters = false; |
135 | compact_id_table_wake(table); |
136 | } |
137 | } |
138 | |
139 | compact_id_t |
140 | compact_id_get_locked( |
141 | compact_id_table_t table, |
142 | compact_id_t limit, |
143 | void *value) |
144 | { |
145 | compact_id_t cid; |
146 | uint32_t slab_size; |
147 | uint32_t idx = 0; |
148 | int bit_index; |
149 | |
150 | again: |
151 | idx = compact_id_slab_index(cid: table->cidt_first_free); |
152 | for (; idx < COMPACT_ID_SLAB_COUNT; idx++) { |
153 | bitmap_t *map = table->cidt_bitmap[idx]; |
154 | void **arr = table->cidt_array[idx]; |
155 | |
156 | if (arr == NULL) { |
157 | compact_id_table_grow(table, idx); |
158 | goto again; |
159 | } |
160 | |
161 | slab_size = compact_id_slab_size(table_index: idx); |
162 | bit_index = bitmap_lsb_first(map, nbits: slab_size); |
163 | if (bit_index >= 0) { |
164 | cid = compact_id_prev_max(idx) + bit_index; |
165 | if (cid > limit) { |
166 | break; |
167 | } |
168 | |
169 | table->cidt_count++; |
170 | table->cidt_first_free = cid + 1; |
171 | bitmap_clear(map, n: bit_index); |
172 | assert(arr[cid] == NULL); |
173 | arr[cid] = value; |
174 | return cid; |
175 | } |
176 | } |
177 | |
178 | panic("table %p ran out of compact IDs" , table); |
179 | } |
180 | |
181 | compact_id_t |
182 | compact_id_get( |
183 | compact_id_table_t table, |
184 | compact_id_t limit, |
185 | void *value) |
186 | { |
187 | compact_id_t cid; |
188 | |
189 | compact_id_table_lock(table); |
190 | cid = compact_id_get_locked(table, limit, value); |
191 | compact_id_table_unlock(table); |
192 | return cid; |
193 | } |
194 | |
195 | void * |
196 | compact_id_put(compact_id_table_t table, compact_id_t cid) |
197 | { |
198 | uint32_t idx = compact_id_slab_index(cid); |
199 | bitmap_t *map = table->cidt_bitmap[idx]; |
200 | void **arr = table->cidt_array[idx]; |
201 | void *value; |
202 | |
203 | compact_id_table_lock(table); |
204 | value = arr[cid]; |
205 | arr[cid] = NULL; |
206 | bitmap_set(map, n: cid - compact_id_prev_max(idx)); |
207 | if (cid < table->cidt_first_free) { |
208 | table->cidt_first_free = cid; |
209 | } |
210 | table->cidt_count--; |
211 | compact_id_table_unlock(table); |
212 | |
213 | return value; |
214 | } |
215 | |
216 | void |
217 | compact_id_for_each( |
218 | compact_id_table_t table, |
219 | uint32_t stride, |
220 | bool (^cb)(void *v)) |
221 | { |
222 | const uint64_t pause_init = stride; |
223 | uint64_t pause = pause_init; |
224 | |
225 | compact_id_table_lock(table); |
226 | for (uint32_t sidx = 0; sidx < COMPACT_ID_SLAB_COUNT; sidx++) { |
227 | void **arr = table->cidt_array[sidx]; |
228 | uint32_t size = compact_id_slab_size(table_index: sidx); |
229 | uint32_t prev = compact_id_prev_max(idx: sidx); |
230 | |
231 | if (arr == NULL) { |
232 | break; |
233 | } |
234 | for (compact_id_t cid = prev; cid < prev + size; cid++) { |
235 | if (arr[cid] == NULL) { |
236 | continue; |
237 | } |
238 | if (!cb(arr[cid])) { |
239 | break; |
240 | } |
241 | if (pause-- == 0) { |
242 | compact_id_table_unlock(table); |
243 | pause = pause_init; |
244 | compact_id_table_lock(table); |
245 | } |
246 | } |
247 | } |
248 | compact_id_table_unlock(table); |
249 | } |
250 | |
251 | void |
252 | compact_id_table_lock(compact_id_table_t table) |
253 | { |
254 | lck_mtx_lock(lck: &table->cidt_lock); |
255 | } |
256 | |
257 | void |
258 | compact_id_table_unlock(compact_id_table_t table) |
259 | { |
260 | lck_mtx_unlock(lck: &table->cidt_lock); |
261 | } |
262 | |