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
33static 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
42static inline uint32_t
43compact_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
57static uint32_t
58compact_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
66static uint32_t
67compact_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
81void
82compact_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
88void **
89compact_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))
95static void
96compact_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
139compact_id_t
140compact_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
150again:
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
181compact_id_t
182compact_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
195void *
196compact_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
216void
217compact_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
251void
252compact_id_table_lock(compact_id_table_t table)
253{
254 lck_mtx_lock(lck: &table->cidt_lock);
255}
256
257void
258compact_id_table_unlock(compact_id_table_t table)
259{
260 lck_mtx_unlock(lck: &table->cidt_lock);
261}
262