X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/d9a64523371fa019c4575bb400cbbc3a50ac9903..c3c9b80d004dbbfdf763edeb97968c6997e3b45b:/osfmk/kern/bits.h diff --git a/osfmk/kern/bits.h b/osfmk/kern/bits.h index 13ce948d2..045ed9621 100644 --- a/osfmk/kern/bits.h +++ b/osfmk/kern/bits.h @@ -31,21 +31,30 @@ #ifndef __BITS_H__ #define __BITS_H__ +#ifdef KERNEL +#include #include +#else +#include +#include +#define kalloc(x) malloc(x) +#define kfree(x, y) free(x) +#endif #include #include +#include -typedef unsigned int uint; +typedef unsigned int uint; -#define BIT(b) (1ULL << (b)) +#define BIT(b) (1ULL << (b)) -#define mask(width) (width >= 64 ? -1 : (BIT(width) - 1)) -#define extract(x, shift, width) ((((uint64_t)(x)) >> (shift)) & mask(width)) -#define bits(x, hi, lo) extract((x), (lo), (hi) - (lo) + 1) +#define mask(width) (width >= 64 ? -1ULL : (BIT(width) - 1)) +#define extract(x, shift, width) ((((uint64_t)(x)) >> (shift)) & mask(width)) +#define bits(x, hi, lo) extract((x), (lo), (hi) - (lo) + 1) -#define bit_set(x, b) ((x) |= BIT(b)) -#define bit_clear(x, b) ((x) &= ~BIT(b)) -#define bit_test(x, b) ((bool)((x) & BIT(b))) +#define bit_set(x, b) ((x) |= BIT(b)) +#define bit_clear(x, b) ((x) &= ~BIT(b)) +#define bit_test(x, b) ((bool)((x) & BIT(b))) inline static uint64_t bit_ror64(uint64_t bitmap, uint n) @@ -53,11 +62,11 @@ bit_ror64(uint64_t bitmap, uint n) #if defined(__arm64__) uint64_t result; uint64_t _n = (uint64_t)n; - asm volatile("ror %0, %1, %2" : "=r" (result) : "r" (bitmap), "r" (_n)); + asm volatile ("ror %0, %1, %2" : "=r" (result) : "r" (bitmap), "r" (_n)); return result; #else n = n & 63; - return ((bitmap >> n) | (bitmap << (64 - n))); + return (bitmap >> n) | (bitmap << (64 - n)); #endif } @@ -68,7 +77,7 @@ bit_rol64(uint64_t bitmap, uint n) return bit_ror64(bitmap, 64U - n); #else n = n & 63; - return ((bitmap << n) | (bitmap >> (64 - n))); + return (bitmap << n) | (bitmap >> (64 - n)); #endif } @@ -76,18 +85,18 @@ bit_rol64(uint64_t bitmap, uint n) inline static bool bit_clear_if_set(uint64_t bitmap, int bit) { - bool bit_is_set = bit_test(bitmap, bit); - bit_clear(bitmap, bit); - return bit_is_set; + bool bit_is_set = bit_test(bitmap, bit); + bit_clear(bitmap, bit); + return bit_is_set; } /* Non-atomically set the bit and returns whether the bit value was changed */ inline static bool bit_set_if_clear(uint64_t bitmap, int bit) { - bool bit_is_set = bit_test(bitmap, bit); - bit_set(bitmap, bit); - return !bit_is_set; + bool bit_is_set = bit_test(bitmap, bit); + bit_set(bitmap, bit); + return !bit_is_set; } /* Returns the most significant '1' bit, or -1 if all zeros */ @@ -96,7 +105,7 @@ bit_first(uint64_t bitmap) { #if defined(__arm64__) int64_t result; - asm volatile("clz %0, %1" : "=r" (result) : "r" (bitmap)); + asm volatile ("clz %0, %1" : "=r" (result) : "r" (bitmap)); return 63 - (int)result; #else return (bitmap == 0) ? -1 : 63 - __builtin_clzll(bitmap); @@ -129,7 +138,7 @@ bit_next(uint64_t bitmap, int previous_bit) inline static int lsb_first(uint64_t bitmap) { - return __builtin_ffsll(bitmap) - 1; + return __builtin_ffsll((long long)bitmap) - 1; } /* Returns the least significant '1' bit that is more significant than previous_bit, @@ -168,13 +177,13 @@ bit_ceiling(uint64_t n) } /* If n is a power of 2, bit_log2(n) == bit_floor(n) == bit_ceiling(n) */ -#define bit_log2(n) bit_floor((uint64_t)(n)) +#define bit_log2(n) bit_floor((uint64_t)(n)) -typedef _Atomic uint64_t bitmap_t; +typedef uint64_t bitmap_t; inline static bool -atomic_bit_set(bitmap_t *map, int n, int mem_order) +atomic_bit_set(_Atomic bitmap_t *map, int n, int mem_order) { bitmap_t prev; prev = __c11_atomic_fetch_or(map, BIT(n), mem_order); @@ -182,7 +191,7 @@ atomic_bit_set(bitmap_t *map, int n, int mem_order) } inline static bool -atomic_bit_clear(bitmap_t *map, int n, int mem_order) +atomic_bit_clear(_Atomic bitmap_t *map, int n, int mem_order) { bitmap_t prev; prev = __c11_atomic_fetch_and(map, ~BIT(n), mem_order); @@ -190,10 +199,10 @@ atomic_bit_clear(bitmap_t *map, int n, int mem_order) } -#define BITMAP_LEN(n) (((uint)(n) + 63) >> 6) /* Round to 64bit bitmap_t */ -#define BITMAP_SIZE(n) (size_t)(BITMAP_LEN(n) << 3) /* Round to 64bit bitmap_t, then convert to bytes */ -#define bitmap_bit(n) bits(n, 5, 0) -#define bitmap_index(n) bits(n, 63, 6) +#define BITMAP_LEN(n) (((uint)(n) + 63) >> 6) /* Round to 64bit bitmap_t */ +#define BITMAP_SIZE(n) (size_t)(BITMAP_LEN(n) << 3) /* Round to 64bit bitmap_t, then convert to bytes */ +#define bitmap_bit(n) bits(n, 5, 0) +#define bitmap_index(n) bits(n, 63, 6) inline static bitmap_t * bitmap_zero(bitmap_t *map, uint nbits) @@ -204,7 +213,39 @@ bitmap_zero(bitmap_t *map, uint nbits) inline static bitmap_t * bitmap_full(bitmap_t *map, uint nbits) { - return (bitmap_t *)memset((void *)map, ~0, BITMAP_SIZE(nbits)); + uint i; + + for (i = 0; i < bitmap_index(nbits - 1); i++) { + map[i] = ~((uint64_t)0); + } + + uint nbits_filled = i * 64; + + if (nbits > nbits_filled) { + map[i] = mask(nbits - nbits_filled); + } + + return map; +} + +inline static bool +bitmap_is_full(bitmap_t *map, uint nbits) +{ + uint i; + + for (i = 0; i < bitmap_index(nbits - 1); i++) { + if (map[i] != ~((uint64_t)0)) { + return false; + } + } + + uint nbits_filled = i * 64; + + if (nbits > nbits_filled) { + return map[i] == mask(nbits - nbits_filled); + } + + return true; } inline static bitmap_t * @@ -238,19 +279,19 @@ bitmap_clear(bitmap_t *map, uint n) } inline static bool -atomic_bitmap_set(bitmap_t *map, uint n, int mem_order) +atomic_bitmap_set(_Atomic bitmap_t *map, uint n, int mem_order) { return atomic_bit_set(&map[bitmap_index(n)], bitmap_bit(n), mem_order); } inline static bool -atomic_bitmap_clear(bitmap_t *map, uint n, int mem_order) +atomic_bitmap_clear(_Atomic bitmap_t *map, uint n, int mem_order) { return atomic_bit_clear(&map[bitmap_index(n)], bitmap_bit(n), mem_order); } inline static bool -bitmap_test(bitmap_t *map, uint n) +bitmap_test(const bitmap_t *map, uint n) { return bit_test(map[bitmap_index(n)], bitmap_bit(n)); } @@ -268,6 +309,58 @@ bitmap_first(bitmap_t *map, uint nbits) return -1; } +inline static void +bitmap_not(bitmap_t *out, const bitmap_t *in, uint nbits) +{ + uint i; + + for (i = 0; i < bitmap_index(nbits - 1); i++) { + out[i] = ~in[i]; + } + + uint nbits_complete = i * 64; + + if (nbits > nbits_complete) { + out[i] = ~in[i] & mask(nbits - nbits_complete); + } +} + +inline static void +bitmap_and(bitmap_t *out, const bitmap_t *in1, const bitmap_t *in2, uint nbits) +{ + for (uint i = 0; i <= bitmap_index(nbits - 1); i++) { + out[i] = in1[i] & in2[i]; + } +} + +inline static void +bitmap_and_not(bitmap_t *out, const bitmap_t *in1, const bitmap_t *in2, uint nbits) +{ + uint i; + + for (i = 0; i < bitmap_index(nbits - 1); i++) { + out[i] = in1[i] & ~in2[i]; + } + + uint nbits_complete = i * 64; + + if (nbits > nbits_complete) { + out[i] = (in1[i] & ~in2[i]) & mask(nbits - nbits_complete); + } +} + +inline static bool +bitmap_equal(const bitmap_t *in1, const bitmap_t *in2, uint nbits) +{ + for (uint i = 0; i <= bitmap_index(nbits - 1); i++) { + if (in1[i] != in2[i]) { + return false; + } + } + + return true; +} + inline static int bitmap_and_not_mask_first(bitmap_t *map, bitmap_t *mask, uint nbits) { @@ -282,7 +375,7 @@ bitmap_and_not_mask_first(bitmap_t *map, bitmap_t *mask, uint nbits) } inline static int -bitmap_lsb_first(bitmap_t *map, uint nbits) +bitmap_lsb_first(const bitmap_t *map, uint nbits) { for (uint i = 0; i <= bitmap_index(nbits - 1); i++) { if (map[i] == 0) { @@ -295,7 +388,7 @@ bitmap_lsb_first(bitmap_t *map, uint nbits) } inline static int -bitmap_next(bitmap_t *map, uint prev) +bitmap_next(const bitmap_t *map, uint prev) { if (prev == 0) { return -1; @@ -318,7 +411,7 @@ bitmap_next(bitmap_t *map, uint prev) } inline static int -bitmap_lsb_next(bitmap_t *map, uint nbits, uint prev) +bitmap_lsb_next(const bitmap_t *map, uint nbits, uint prev) { if ((prev + 1) >= nbits) { return -1;