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 | |