--- /dev/null
+/*
+ * Copyright (c) 2015-2016 Apple Inc. All rights reserved.
+ *
+ * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
+ *
+ * This file contains Original Code and/or Modifications of Original Code
+ * as defined in and that are subject to the Apple Public Source License
+ * Version 2.0 (the 'License'). You may not use this file except in
+ * compliance with the License. The rights granted to you under the License
+ * may not be used to create, or enable the creation or redistribution of,
+ * unlawful or unlicensed copies of an Apple operating system, or to
+ * circumvent, violate, or enable the circumvention or violation of, any
+ * terms of an Apple operating system software license agreement.
+ *
+ * Please obtain a copy of the License at
+ * http://www.opensource.apple.com/apsl/ and read it before using this file.
+ *
+ * The Original Code and all software distributed under the License are
+ * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
+ * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
+ * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
+ * Please see the License for the specific language governing rights and
+ * limitations under the License.
+ *
+ * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
+ *
+ * Bit manipulation functions
+ */
+
+#ifndef __BITS_H__
+#define __BITS_H__
+
+#include <kern/kalloc.h>
+#include <stdbool.h>
+#include <stdint.h>
+
+typedef unsigned int uint;
+
+#define BIT(b) (1ULL << (b))
+
+#define mask(width) (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)))
+
+/* Returns the most significant '1' bit, or -1 if all zeros */
+inline static int
+bit_first(uint64_t bitmap)
+{
+ return (bitmap == 0) ? -1 : 63 - __builtin_clzll(bitmap);
+}
+
+
+inline static int
+__bit_next(uint64_t bitmap, int previous_bit)
+{
+ uint64_t mask = previous_bit ? mask(previous_bit) : ~0ULL;
+
+ return bit_first(bitmap & mask);
+}
+
+/* Returns the most significant '1' bit that is less significant than previous_bit,
+ * or -1 if no such bit exists.
+ */
+inline static int
+bit_next(uint64_t bitmap, int previous_bit)
+{
+ if (previous_bit == 0) {
+ return -1;
+ } else {
+ return __bit_next(bitmap, previous_bit);
+ }
+}
+
+/* Returns the least significant '1' bit, or -1 if all zeros */
+inline static int
+lsb_first(uint64_t bitmap)
+{
+ return __builtin_ffsll(bitmap) - 1;
+}
+
+/* Returns the least significant '1' bit that is more significant than previous_bit,
+ * or -1 if no such bit exists.
+ * previous_bit may be -1, in which case this is equivalent to lsb_first()
+ */
+inline static int
+lsb_next(uint64_t bitmap, int previous_bit)
+{
+ uint64_t mask = mask(previous_bit + 1);
+
+ return lsb_first(bitmap & ~mask);
+}
+
+inline static int
+bit_count(uint64_t x)
+{
+ return __builtin_popcountll(x);
+}
+
+/* Return the highest power of 2 that is <= n, or -1 if n == 0 */
+inline static int
+bit_floor(uint64_t n)
+{
+ return bit_first(n);
+}
+
+/* Return the lowest power of 2 that is >= n, or -1 if n == 0 */
+inline static int
+bit_ceiling(uint64_t n)
+{
+ if (n == 0) {
+ return -1;
+ }
+ return bit_first(n - 1) + 1;
+}
+
+/* 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))
+
+typedef _Atomic uint64_t bitmap_t;
+
+
+inline static bool
+atomic_bit_set(bitmap_t *map, int n, int mem_order)
+{
+ bitmap_t prev;
+ prev = __c11_atomic_fetch_or(map, BIT(n), mem_order);
+ return bit_test(prev, n);
+}
+
+inline static bool
+atomic_bit_clear(bitmap_t *map, int n, int mem_order)
+{
+ bitmap_t prev;
+ prev = __c11_atomic_fetch_and(map, ~BIT(n), mem_order);
+ return bit_test(prev, n);
+}
+
+
+#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)
+{
+ return (bitmap_t *)memset((void *)map, 0, BITMAP_SIZE(nbits));
+}
+
+inline static bitmap_t *
+bitmap_full(bitmap_t *map, uint nbits)
+{
+ return (bitmap_t *)memset((void *)map, ~0, BITMAP_SIZE(nbits));
+}
+
+inline static bitmap_t *
+bitmap_alloc(uint nbits)
+{
+ assert(nbits > 0);
+ bitmap_t *map = (bitmap_t *)kalloc(BITMAP_SIZE(nbits));
+ if (map) {
+ bitmap_zero(map, nbits);
+ }
+ return map;
+}
+
+inline static void
+bitmap_free(bitmap_t *map, uint nbits)
+{
+ assert(nbits > 0);
+ kfree(map, BITMAP_SIZE(nbits));
+}
+
+inline static void
+bitmap_set(bitmap_t *map, uint n)
+{
+ bit_set(map[bitmap_index(n)], bitmap_bit(n));
+}
+
+inline static void
+bitmap_clear(bitmap_t *map, uint n)
+{
+ bit_clear(map[bitmap_index(n)], bitmap_bit(n));
+}
+
+inline static bool
+atomic_bitmap_set(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)
+{
+ return atomic_bit_clear(&map[bitmap_index(n)], bitmap_bit(n), mem_order);
+}
+
+inline static bool
+bitmap_test(bitmap_t *map, uint n)
+{
+ return bit_test(map[bitmap_index(n)], bitmap_bit(n));
+}
+
+inline static int
+bitmap_first(bitmap_t *map, uint nbits)
+{
+ for (int i = (int)bitmap_index(nbits - 1); i >= 0; i--) {
+ if (map[i] == 0) {
+ continue;
+ }
+ return (i << 6) + bit_first(map[i]);
+ }
+
+ return -1;
+}
+
+inline static int
+bitmap_and_not_mask_first(bitmap_t *map, bitmap_t *mask, uint nbits)
+{
+ for (int i = (int)bitmap_index(nbits - 1); i >= 0; i--) {
+ if ((map[i] & ~mask[i]) == 0) {
+ continue;
+ }
+ return (i << 6) + bit_first(map[i] & ~mask[i]);
+ }
+
+ return -1;
+}
+
+inline static int
+bitmap_lsb_first(bitmap_t *map, uint nbits)
+{
+ for (uint i = 0; i <= bitmap_index(nbits - 1); i++) {
+ if (map[i] == 0) {
+ continue;
+ }
+ return (int)((i << 6) + (uint32_t)lsb_first(map[i]));
+ }
+
+ return -1;
+}
+
+inline static int
+bitmap_next(bitmap_t *map, uint prev)
+{
+ if (prev == 0) {
+ return -1;
+ }
+
+ int64_t i = bitmap_index(prev - 1);
+ int res = __bit_next(map[i], bits(prev, 5, 0));
+ if (res >= 0) {
+ return (int)(res + (i << 6));
+ }
+
+ for (i = i - 1; i >= 0; i--) {
+ if (map[i] == 0) {
+ continue;
+ }
+ return (int)((i << 6) + bit_first(map[i]));
+ }
+
+ return -1;
+}
+
+inline static int
+bitmap_lsb_next(bitmap_t *map, uint nbits, uint prev)
+{
+ if ((prev + 1) >= nbits) {
+ return -1;
+ }
+
+ uint64_t i = bitmap_index(prev + 1);
+ uint b = bits((prev + 1), 5, 0) - 1;
+ int32_t res = lsb_next((uint64_t)map[i], (int)b);
+ if (res >= 0) {
+ return (int)((uint64_t)res + (i << 6));
+ }
+
+ for (i = i + 1; i <= bitmap_index(nbits - 1); i++) {
+ if (map[i] == 0) {
+ continue;
+ }
+ return (int)((i << 6) + (uint64_t)lsb_first(map[i]));
+ }
+
+ return -1;
+}
+
+#endif
projects / apple / xnu.git / blobdiff