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
38typedef unsigned int uint;
39
40#define BIT(b) (1ULL << (b))
41
42#define mask(width) (width >= 64 ? -1 : (BIT(width) - 1))
43#define extract(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
50inline static uint64_t
51bit_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
64inline static uint64_t
65bit_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 */
76inline static bool
77bit_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 */
85inline static bool
86bit_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 */
94inline static int
95bit_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
107inline 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 */
118inline static int
119bit_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 */
129inline static int
130lsb_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 */
139inline static int
140lsb_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
147inline static int
148bit_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 */
154inline static int
155bit_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 */
161inline static int
162bit_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
173typedef _Atomic uint64_t bitmap_t;
174
175
176inline static bool
177atomic_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
184inline static bool
185atomic_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
198inline static bitmap_t *
199bitmap_zero(bitmap_t *map, uint nbits)
200{
201 return (bitmap_t *)memset((void *)map, 0, BITMAP_SIZE(nbits));
202}
203
204inline static bitmap_t *
205bitmap_full(bitmap_t *map, uint nbits)
206{
207 return (bitmap_t *)memset((void *)map, ~0, BITMAP_SIZE(nbits));
208}
209
210inline static bitmap_t *
211bitmap_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
221inline static void
222bitmap_free(bitmap_t *map, uint nbits)
223{
224 assert(nbits > 0);
225 kfree(map, BITMAP_SIZE(nbits));
226}
227
228inline static void
229bitmap_set(bitmap_t *map, uint n)
230{
231 bit_set(map[bitmap_index(n)], bitmap_bit(n));
232}
233
234inline static void
235bitmap_clear(bitmap_t *map, uint n)
236{
237 bit_clear(map[bitmap_index(n)], bitmap_bit(n));
238}
239
240inline static bool
241atomic_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
246inline static bool
247atomic_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
252inline static bool
253bitmap_test(bitmap_t *map, uint n)
254{
255 return bit_test(map[bitmap_index(n)], bitmap_bit(n));
256}
257
258inline static int
259bitmap_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
271inline static int
272bitmap_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
284inline static int
285bitmap_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
297inline static int
298bitmap_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
320inline static int
321bitmap_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