1 | /* |
2 | * Copyright (c) 2015-2016 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 | * Bit manipulation functions |
29 | */ |
30 | |
31 | #ifndef __BITS_H__ |
32 | #define __BITS_H__ |
33 | |
34 | #include <kern/kalloc.h> |
35 | #include <stdbool.h> |
36 | #include <stdint.h> |
37 | |
38 | typedef unsigned int uint; |
39 | |
40 | #define BIT(b) (1ULL << (b)) |
41 | |
42 | #define mask(width) (width >= 64 ? -1 : (BIT(width) - 1)) |
43 | #define (x, shift, width) ((((uint64_t)(x)) >> (shift)) & mask(width)) |
44 | #define bits(x, hi, lo) extract((x), (lo), (hi) - (lo) + 1) |
45 | |
46 | #define bit_set(x, b) ((x) |= BIT(b)) |
47 | #define bit_clear(x, b) ((x) &= ~BIT(b)) |
48 | #define bit_test(x, b) ((bool)((x) & BIT(b))) |
49 | |
50 | inline static uint64_t |
51 | bit_ror64(uint64_t bitmap, uint n) |
52 | { |
53 | #if defined(__arm64__) |
54 | uint64_t result; |
55 | uint64_t _n = (uint64_t)n; |
56 | asm volatile("ror %0, %1, %2" : "=r" (result) : "r" (bitmap), "r" (_n)); |
57 | return result; |
58 | #else |
59 | n = n & 63; |
60 | return ((bitmap >> n) | (bitmap << (64 - n))); |
61 | #endif |
62 | } |
63 | |
64 | inline static uint64_t |
65 | bit_rol64(uint64_t bitmap, uint n) |
66 | { |
67 | #if defined(__arm64__) |
68 | return bit_ror64(bitmap, 64U - n); |
69 | #else |
70 | n = n & 63; |
71 | return ((bitmap << n) | (bitmap >> (64 - n))); |
72 | #endif |
73 | } |
74 | |
75 | /* Non-atomically clear the bit and returns whether the bit value was changed */ |
76 | inline static bool |
77 | bit_clear_if_set(uint64_t bitmap, int bit) |
78 | { |
79 | bool bit_is_set = bit_test(bitmap, bit); |
80 | bit_clear(bitmap, bit); |
81 | return bit_is_set; |
82 | } |
83 | |
84 | /* Non-atomically set the bit and returns whether the bit value was changed */ |
85 | inline static bool |
86 | bit_set_if_clear(uint64_t bitmap, int bit) |
87 | { |
88 | bool bit_is_set = bit_test(bitmap, bit); |
89 | bit_set(bitmap, bit); |
90 | return !bit_is_set; |
91 | } |
92 | |
93 | /* Returns the most significant '1' bit, or -1 if all zeros */ |
94 | inline static int |
95 | bit_first(uint64_t bitmap) |
96 | { |
97 | #if defined(__arm64__) |
98 | int64_t result; |
99 | asm volatile("clz %0, %1" : "=r" (result) : "r" (bitmap)); |
100 | return 63 - (int)result; |
101 | #else |
102 | return (bitmap == 0) ? -1 : 63 - __builtin_clzll(bitmap); |
103 | #endif |
104 | } |
105 | |
106 | |
107 | inline static int |
108 | __bit_next(uint64_t bitmap, int previous_bit) |
109 | { |
110 | uint64_t mask = previous_bit ? mask(previous_bit) : ~0ULL; |
111 | |
112 | return bit_first(bitmap & mask); |
113 | } |
114 | |
115 | /* Returns the most significant '1' bit that is less significant than previous_bit, |
116 | * or -1 if no such bit exists. |
117 | */ |
118 | inline static int |
119 | bit_next(uint64_t bitmap, int previous_bit) |
120 | { |
121 | if (previous_bit == 0) { |
122 | return -1; |
123 | } else { |
124 | return __bit_next(bitmap, previous_bit); |
125 | } |
126 | } |
127 | |
128 | /* Returns the least significant '1' bit, or -1 if all zeros */ |
129 | inline static int |
130 | lsb_first(uint64_t bitmap) |
131 | { |
132 | return __builtin_ffsll(bitmap) - 1; |
133 | } |
134 | |
135 | /* Returns the least significant '1' bit that is more significant than previous_bit, |
136 | * or -1 if no such bit exists. |
137 | * previous_bit may be -1, in which case this is equivalent to lsb_first() |
138 | */ |
139 | inline static int |
140 | lsb_next(uint64_t bitmap, int previous_bit) |
141 | { |
142 | uint64_t mask = mask(previous_bit + 1); |
143 | |
144 | return lsb_first(bitmap & ~mask); |
145 | } |
146 | |
147 | inline static int |
148 | bit_count(uint64_t x) |
149 | { |
150 | return __builtin_popcountll(x); |
151 | } |
152 | |
153 | /* Return the highest power of 2 that is <= n, or -1 if n == 0 */ |
154 | inline static int |
155 | bit_floor(uint64_t n) |
156 | { |
157 | return bit_first(n); |
158 | } |
159 | |
160 | /* Return the lowest power of 2 that is >= n, or -1 if n == 0 */ |
161 | inline static int |
162 | bit_ceiling(uint64_t n) |
163 | { |
164 | if (n == 0) { |
165 | return -1; |
166 | } |
167 | return bit_first(n - 1) + 1; |
168 | } |
169 | |
170 | /* If n is a power of 2, bit_log2(n) == bit_floor(n) == bit_ceiling(n) */ |
171 | #define bit_log2(n) bit_floor((uint64_t)(n)) |
172 | |
173 | typedef _Atomic uint64_t bitmap_t; |
174 | |
175 | |
176 | inline static bool |
177 | atomic_bit_set(bitmap_t *map, int n, int mem_order) |
178 | { |
179 | bitmap_t prev; |
180 | prev = __c11_atomic_fetch_or(map, BIT(n), mem_order); |
181 | return bit_test(prev, n); |
182 | } |
183 | |
184 | inline static bool |
185 | atomic_bit_clear(bitmap_t *map, int n, int mem_order) |
186 | { |
187 | bitmap_t prev; |
188 | prev = __c11_atomic_fetch_and(map, ~BIT(n), mem_order); |
189 | return bit_test(prev, n); |
190 | } |
191 | |
192 | |
193 | #define BITMAP_LEN(n) (((uint)(n) + 63) >> 6) /* Round to 64bit bitmap_t */ |
194 | #define BITMAP_SIZE(n) (size_t)(BITMAP_LEN(n) << 3) /* Round to 64bit bitmap_t, then convert to bytes */ |
195 | #define bitmap_bit(n) bits(n, 5, 0) |
196 | #define bitmap_index(n) bits(n, 63, 6) |
197 | |
198 | inline static bitmap_t * |
199 | bitmap_zero(bitmap_t *map, uint nbits) |
200 | { |
201 | return (bitmap_t *)memset((void *)map, 0, BITMAP_SIZE(nbits)); |
202 | } |
203 | |
204 | inline static bitmap_t * |
205 | bitmap_full(bitmap_t *map, uint nbits) |
206 | { |
207 | return (bitmap_t *)memset((void *)map, ~0, BITMAP_SIZE(nbits)); |
208 | } |
209 | |
210 | inline static bitmap_t * |
211 | bitmap_alloc(uint nbits) |
212 | { |
213 | assert(nbits > 0); |
214 | bitmap_t *map = (bitmap_t *)kalloc(BITMAP_SIZE(nbits)); |
215 | if (map) { |
216 | bitmap_zero(map, nbits); |
217 | } |
218 | return map; |
219 | } |
220 | |
221 | inline static void |
222 | bitmap_free(bitmap_t *map, uint nbits) |
223 | { |
224 | assert(nbits > 0); |
225 | kfree(map, BITMAP_SIZE(nbits)); |
226 | } |
227 | |
228 | inline static void |
229 | bitmap_set(bitmap_t *map, uint n) |
230 | { |
231 | bit_set(map[bitmap_index(n)], bitmap_bit(n)); |
232 | } |
233 | |
234 | inline static void |
235 | bitmap_clear(bitmap_t *map, uint n) |
236 | { |
237 | bit_clear(map[bitmap_index(n)], bitmap_bit(n)); |
238 | } |
239 | |
240 | inline static bool |
241 | atomic_bitmap_set(bitmap_t *map, uint n, int mem_order) |
242 | { |
243 | return atomic_bit_set(&map[bitmap_index(n)], bitmap_bit(n), mem_order); |
244 | } |
245 | |
246 | inline static bool |
247 | atomic_bitmap_clear(bitmap_t *map, uint n, int mem_order) |
248 | { |
249 | return atomic_bit_clear(&map[bitmap_index(n)], bitmap_bit(n), mem_order); |
250 | } |
251 | |
252 | inline static bool |
253 | bitmap_test(bitmap_t *map, uint n) |
254 | { |
255 | return bit_test(map[bitmap_index(n)], bitmap_bit(n)); |
256 | } |
257 | |
258 | inline static int |
259 | bitmap_first(bitmap_t *map, uint nbits) |
260 | { |
261 | for (int i = (int)bitmap_index(nbits - 1); i >= 0; i--) { |
262 | if (map[i] == 0) { |
263 | continue; |
264 | } |
265 | return (i << 6) + bit_first(map[i]); |
266 | } |
267 | |
268 | return -1; |
269 | } |
270 | |
271 | inline static int |
272 | bitmap_and_not_mask_first(bitmap_t *map, bitmap_t *mask, uint nbits) |
273 | { |
274 | for (int i = (int)bitmap_index(nbits - 1); i >= 0; i--) { |
275 | if ((map[i] & ~mask[i]) == 0) { |
276 | continue; |
277 | } |
278 | return (i << 6) + bit_first(map[i] & ~mask[i]); |
279 | } |
280 | |
281 | return -1; |
282 | } |
283 | |
284 | inline static int |
285 | bitmap_lsb_first(bitmap_t *map, uint nbits) |
286 | { |
287 | for (uint i = 0; i <= bitmap_index(nbits - 1); i++) { |
288 | if (map[i] == 0) { |
289 | continue; |
290 | } |
291 | return (int)((i << 6) + (uint32_t)lsb_first(map[i])); |
292 | } |
293 | |
294 | return -1; |
295 | } |
296 | |
297 | inline static int |
298 | bitmap_next(bitmap_t *map, uint prev) |
299 | { |
300 | if (prev == 0) { |
301 | return -1; |
302 | } |
303 | |
304 | int64_t i = bitmap_index(prev - 1); |
305 | int res = __bit_next(map[i], bits(prev, 5, 0)); |
306 | if (res >= 0) { |
307 | return (int)(res + (i << 6)); |
308 | } |
309 | |
310 | for (i = i - 1; i >= 0; i--) { |
311 | if (map[i] == 0) { |
312 | continue; |
313 | } |
314 | return (int)((i << 6) + bit_first(map[i])); |
315 | } |
316 | |
317 | return -1; |
318 | } |
319 | |
320 | inline static int |
321 | bitmap_lsb_next(bitmap_t *map, uint nbits, uint prev) |
322 | { |
323 | if ((prev + 1) >= nbits) { |
324 | return -1; |
325 | } |
326 | |
327 | uint64_t i = bitmap_index(prev + 1); |
328 | uint b = bits((prev + 1), 5, 0) - 1; |
329 | int32_t res = lsb_next((uint64_t)map[i], (int)b); |
330 | if (res >= 0) { |
331 | return (int)((uint64_t)res + (i << 6)); |
332 | } |
333 | |
334 | for (i = i + 1; i <= bitmap_index(nbits - 1); i++) { |
335 | if (map[i] == 0) { |
336 | continue; |
337 | } |
338 | return (int)((i << 6) + (uint64_t)lsb_first(map[i])); |
339 | } |
340 | |
341 | return -1; |
342 | } |
343 | |
344 | #endif |
345 | |