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  #ifdef KERNEL
 35  #include <kern/assert.h>
 36  #include <kern/kalloc.h>
 37  #else
 38  #include <assert.h>
 39  #include <stdlib.h>
 40  #define kalloc(x) malloc(x)
 41  #define kfree(x, y) free(x)
 42  #endif
 43  #include <stdbool.h>
 44  #include <stdint.h>
 45  #include <stdatomic.h>
 46  
 47  typedef unsigned int                    uint;
 48  
 49  #define BIT(b)                          (1ULL << (b))
 50  
 51  #define mask(width)                     (width >= 64 ? -1ULL : (BIT(width) - 1))
 52  #define extract(x, shift, width)        ((((uint64_t)(x)) >> (shift)) & mask(width))
 53  #define bits(x, hi, lo)                 extract((x), (lo), (hi) - (lo) + 1)
 54  
 55  #define bit_set(x, b)                   ((x) |= BIT(b))
 56  #define bit_clear(x, b)                 ((x) &= ~BIT(b))
 57  #define bit_test(x, b)                  ((bool)((x) & BIT(b)))
 58  
 59  inline static uint64_t
 60  bit_ror64(uint64_t bitmap, uint n)
 61  {
 62  #if defined(__arm64__)
 63  	uint64_t result;
 64  	uint64_t _n = (uint64_t)n;
 65  	asm volatile ("ror %0, %1, %2" : "=r" (result) : "r" (bitmap), "r" (_n));
 66  	return result;
 67  #else
 68  	n = n & 63;
 69  	return (bitmap >> n) | (bitmap << (64 - n));
 70  #endif
 71  }
 72  
 73  inline static uint64_t
 74  bit_rol64(uint64_t bitmap, uint n)
 75  {
 76  #if defined(__arm64__)
 77  	return bit_ror64(bitmap, 64U - n);
 78  #else
 79  	n = n & 63;
 80  	return (bitmap << n) | (bitmap >> (64 - n));
 81  #endif
 82  }
 83  
 84  /* Non-atomically clear the bit and returns whether the bit value was changed */
 85  inline static bool
 86  bit_clear_if_set(uint64_t *bitmap, int bit)
 87  {
 88  	bool bit_is_set = bit_test(*bitmap, bit);
 89  	bit_clear(*bitmap, bit);
 90  	return bit_is_set;
 91  }
 92  
 93  /* Non-atomically set the bit and returns whether the bit value was changed */
 94  inline static bool
 95  bit_set_if_clear(uint64_t *bitmap, int bit)
 96  {
 97  	bool bit_is_set = bit_test(*bitmap, bit);
 98  	bit_set(*bitmap, bit);
 99  	return !bit_is_set;
100  }
101  
102  /* Returns the most significant '1' bit, or -1 if all zeros */
103  inline static int
104  bit_first(uint64_t bitmap)
105  {
106  #if defined(__arm64__)
107  	int64_t result;
108  	asm volatile ("clz %0, %1" : "=r" (result) : "r" (bitmap));
109  	return 63 - (int)result;
110  #else
111  	return (bitmap == 0) ? -1 : 63 - __builtin_clzll(bitmap);
112  #endif
113  }
114  
115  
116  inline static int
117  __bit_next(uint64_t bitmap, int previous_bit)
118  {
119  	uint64_t mask = previous_bit ? mask(previous_bit) : ~0ULL;
120  
121  	return bit_first(bitmap & mask);
122  }
123  
124  /* Returns the most significant '1' bit that is less significant than previous_bit,
125   * or -1 if no such bit exists.
126   */
127  inline static int
128  bit_next(uint64_t bitmap, int previous_bit)
129  {
130  	if (previous_bit == 0) {
131  		return -1;
132  	} else {
133  		return __bit_next(bitmap, previous_bit);
134  	}
135  }
136  
137  /* Returns the least significant '1' bit, or -1 if all zeros */
138  inline static int
139  lsb_first(uint64_t bitmap)
140  {
141  	return __builtin_ffsll((long long)bitmap) - 1;
142  }
143  
144  /* Returns the least significant '1' bit that is more significant than previous_bit,
145   * or -1 if no such bit exists.
146   * previous_bit may be -1, in which case this is equivalent to lsb_first()
147   */
148  inline static int
149  lsb_next(uint64_t bitmap, int previous_bit)
150  {
151  	uint64_t mask = mask(previous_bit + 1);
152  
153  	return lsb_first(bitmap & ~mask);
154  }
155  
156  inline static int
157  bit_count(uint64_t x)
158  {
159  	return __builtin_popcountll(x);
160  }
161  
162  /* Return the highest power of 2 that is <= n, or -1 if n == 0 */
163  inline static int
164  bit_floor(uint64_t n)
165  {
166  	return bit_first(n);
167  }
168  
169  /* Return the lowest power of 2 that is >= n, or -1 if n == 0 */
170  inline static int
171  bit_ceiling(uint64_t n)
172  {
173  	if (n == 0) {
174  		return -1;
175  	}
176  	return bit_first(n - 1) + 1;
177  }
178  
179  /* If n is a power of 2, bit_log2(n) == bit_floor(n) == bit_ceiling(n) */
180  #define bit_log2(n)             bit_floor((uint64_t)(n))
181  
182  typedef uint64_t                bitmap_t;
183  
184  
185  inline static bool
186  atomic_bit_set(_Atomic bitmap_t *map, int n, int mem_order)
187  {
188  	bitmap_t prev;
189  	prev = __c11_atomic_fetch_or(map, BIT(n), mem_order);
190  	return bit_test(prev, n);
191  }
192  
193  inline static bool
194  atomic_bit_clear(_Atomic bitmap_t *map, int n, int mem_order)
195  {
196  	bitmap_t prev;
197  	prev = __c11_atomic_fetch_and(map, ~BIT(n), mem_order);
198  	return bit_test(prev, n);
199  }
200  
201  
202  #define BITMAP_LEN(n)   (((uint)(n) + 63) >> 6)         /* Round to 64bit bitmap_t */
203  #define BITMAP_SIZE(n)  (size_t)(BITMAP_LEN(n) << 3)            /* Round to 64bit bitmap_t, then convert to bytes */
204  #define bitmap_bit(n)   bits(n, 5, 0)
205  #define bitmap_index(n) bits(n, 63, 6)
206  
207  inline static bitmap_t *
208  bitmap_zero(bitmap_t *map, uint nbits)
209  {
210  	return (bitmap_t *)memset((void *)map, 0, BITMAP_SIZE(nbits));
211  }
212  
213  inline static bitmap_t *
214  bitmap_full(bitmap_t *map, uint nbits)
215  {
216  	uint i;
217  
218  	for (i = 0; i < bitmap_index(nbits - 1); i++) {
219  		map[i] = ~((uint64_t)0);
220  	}
221  
222  	uint nbits_filled = i * 64;
223  
224  	if (nbits > nbits_filled) {
225  		map[i] = mask(nbits - nbits_filled);
226  	}
227  
228  	return map;
229  }
230  
231  inline static bool
232  bitmap_is_full(bitmap_t *map, uint nbits)
233  {
234  	uint i;
235  
236  	for (i = 0; i < bitmap_index(nbits - 1); i++) {
237  		if (map[i] != ~((uint64_t)0)) {
238  			return false;
239  		}
240  	}
241  
242  	uint nbits_filled = i * 64;
243  
244  	if (nbits > nbits_filled) {
245  		return map[i] == mask(nbits - nbits_filled);
246  	}
247  
248  	return true;
249  }
250  
251  inline static bitmap_t *
252  bitmap_alloc(uint nbits)
253  {
254  	assert(nbits > 0);
255  	bitmap_t *map = (bitmap_t *)kalloc(BITMAP_SIZE(nbits));
256  	if (map) {
257  		bitmap_zero(map, nbits);
258  	}
259  	return map;
260  }
261  
262  inline static void
263  bitmap_free(bitmap_t *map, uint nbits)
264  {
265  	assert(nbits > 0);
266  	kfree(map, BITMAP_SIZE(nbits));
267  }
268  
269  inline static void
270  bitmap_set(bitmap_t *map, uint n)
271  {
272  	bit_set(map[bitmap_index(n)], bitmap_bit(n));
273  }
274  
275  inline static void
276  bitmap_clear(bitmap_t *map, uint n)
277  {
278  	bit_clear(map[bitmap_index(n)], bitmap_bit(n));
279  }
280  
281  inline static bool
282  atomic_bitmap_set(_Atomic bitmap_t *map, uint n, int mem_order)
283  {
284  	return atomic_bit_set(&map[bitmap_index(n)], bitmap_bit(n), mem_order);
285  }
286  
287  inline static bool
288  atomic_bitmap_clear(_Atomic bitmap_t *map, uint n, int mem_order)
289  {
290  	return atomic_bit_clear(&map[bitmap_index(n)], bitmap_bit(n), mem_order);
291  }
292  
293  inline static bool
294  bitmap_test(const bitmap_t *map, uint n)
295  {
296  	return bit_test(map[bitmap_index(n)], bitmap_bit(n));
297  }
298  
299  inline static int
300  bitmap_first(bitmap_t *map, uint nbits)
301  {
302  	for (int i = (int)bitmap_index(nbits - 1); i >= 0; i--) {
303  		if (map[i] == 0) {
304  			continue;
305  		}
306  		return (i << 6) + bit_first(map[i]);
307  	}
308  
309  	return -1;
310  }
311  
312  inline static void
313  bitmap_not(bitmap_t *out, const bitmap_t *in, uint nbits)
314  {
315  	uint i;
316  
317  	for (i = 0; i < bitmap_index(nbits - 1); i++) {
318  		out[i] = ~in[i];
319  	}
320  
321  	uint nbits_complete = i * 64;
322  
323  	if (nbits > nbits_complete) {
324  		out[i] = ~in[i] & mask(nbits - nbits_complete);
325  	}
326  }
327  
328  inline static void
329  bitmap_and(bitmap_t *out, const bitmap_t *in1, const bitmap_t *in2, uint nbits)
330  {
331  	for (uint i = 0; i <= bitmap_index(nbits - 1); i++) {
332  		out[i] = in1[i] & in2[i];
333  	}
334  }
335  
336  inline static void
337  bitmap_and_not(bitmap_t *out, const bitmap_t *in1, const bitmap_t *in2, uint nbits)
338  {
339  	uint i;
340  
341  	for (i = 0; i < bitmap_index(nbits - 1); i++) {
342  		out[i] = in1[i] & ~in2[i];
343  	}
344  
345  	uint nbits_complete = i * 64;
346  
347  	if (nbits > nbits_complete) {
348  		out[i] = (in1[i] & ~in2[i]) & mask(nbits - nbits_complete);
349  	}
350  }
351  
352  inline static bool
353  bitmap_equal(const bitmap_t *in1, const bitmap_t *in2, uint nbits)
354  {
355  	for (uint i = 0; i <= bitmap_index(nbits - 1); i++) {
356  		if (in1[i] != in2[i]) {
357  			return false;
358  		}
359  	}
360  
361  	return true;
362  }
363  
364  inline static int
365  bitmap_and_not_mask_first(bitmap_t *map, bitmap_t *mask, uint nbits)
366  {
367  	for (int i = (int)bitmap_index(nbits - 1); i >= 0; i--) {
368  		if ((map[i] & ~mask[i]) == 0) {
369  			continue;
370  		}
371  		return (i << 6) + bit_first(map[i] & ~mask[i]);
372  	}
373  
374  	return -1;
375  }
376  
377  inline static int
378  bitmap_lsb_first(const bitmap_t *map, uint nbits)
379  {
380  	for (uint i = 0; i <= bitmap_index(nbits - 1); i++) {
381  		if (map[i] == 0) {
382  			continue;
383  		}
384  		return (int)((i << 6) + (uint32_t)lsb_first(map[i]));
385  	}
386  
387  	return -1;
388  }
389  
390  inline static int
391  bitmap_next(const bitmap_t *map, uint prev)
392  {
393  	if (prev == 0) {
394  		return -1;
395  	}
396  
397  	int64_t i = bitmap_index(prev - 1);
398  	int res = __bit_next(map[i], bits(prev, 5, 0));
399  	if (res >= 0) {
400  		return (int)(res + (i << 6));
401  	}
402  
403  	for (i = i - 1; i >= 0; i--) {
404  		if (map[i] == 0) {
405  			continue;
406  		}
407  		return (int)((i << 6) + bit_first(map[i]));
408  	}
409  
410  	return -1;
411  }
412  
413  inline static int
414  bitmap_lsb_next(const bitmap_t *map, uint nbits, uint prev)
415  {
416  	if ((prev + 1) >= nbits) {
417  		return -1;
418  	}
419  
420  	uint64_t i = bitmap_index(prev + 1);
421  	uint b = bits((prev + 1), 5, 0) - 1;
422  	int32_t res = lsb_next((uint64_t)map[i], (int)b);
423  	if (res >= 0) {
424  		return (int)((uint64_t)res + (i << 6));
425  	}
426  
427  	for (i = i + 1; i <= bitmap_index(nbits - 1); i++) {
428  		if (map[i] == 0) {
429  			continue;
430  		}
431  		return (int)((i << 6) + (uint64_t)lsb_first(map[i]));
432  	}
433  
434  	return -1;
435  }
436  
437  #endif