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
46typedef uint32_t compact_id_t;
47typedef 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 */
91struct 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
104extern void compact_id_table_init(
105 compact_id_table_t table);
106
107extern void **compact_id_resolve(
108 compact_id_table_t table,
109 compact_id_t compact_id) __pure2;
110
111extern compact_id_t compact_id_get_locked(
112 compact_id_table_t table,
113 compact_id_t limit,
114 void *value);
115
116extern compact_id_t compact_id_get(
117 compact_id_table_t table,
118 compact_id_t limit,
119 void *value);
120
121extern void *compact_id_put(
122 compact_id_table_t table,
123 compact_id_t compact_id);
124
125extern void compact_id_for_each(
126 compact_id_table_t table,
127 uint32_t stride,
128 bool (^cb)(void *v));
129
130extern void compact_id_table_lock(
131 compact_id_table_t table);
132
133extern 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