osfmk/kern/bits.h

   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)                     (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
  50 /* Returns the most significant '1' bit, or -1 if all zeros */
  51 inline static int
  52 bit_first(uint64_t bitmap)
  53 {
  54         return (bitmap == 0) ? -1 : 63 - __builtin_clzll(bitmap);
  55 }
  56
  57
  58 inline static int
  59 __bit_next(uint64_t bitmap, int previous_bit)
  60 {
  61         uint64_t mask = previous_bit ? mask(previous_bit) : ~0ULL;
  62
  63         return bit_first(bitmap & mask);
  64 }
  65
  66 /* Returns the most significant '1' bit that is less significant than previous_bit,
  67  * or -1 if no such bit exists.
  68  */
  69 inline static int
  70 bit_next(uint64_t bitmap, int previous_bit)
  71 {
  72         if (previous_bit == 0) {
  73                 return -1;
  74         } else {
  75                 return __bit_next(bitmap, previous_bit);
  76         }
  77 }
  78
  79 /* Returns the least significant '1' bit, or -1 if all zeros */
  80 inline static int
  81 lsb_first(uint64_t bitmap)
  82 {
  83         return __builtin_ffsll(bitmap) - 1;
  84 }
  85
  86 /* Returns the least significant '1' bit that is more significant than previous_bit,
  87  * or -1 if no such bit exists.
  88  * previous_bit may be -1, in which case this is equivalent to lsb_first()
  89  */
  90 inline static int
  91 lsb_next(uint64_t bitmap, int previous_bit)
  92 {
  93         uint64_t mask = mask(previous_bit + 1);
  94
  95         return lsb_first(bitmap & ~mask);
  96 }
  97
  98 inline static int
  99 bit_count(uint64_t x)
 100 {
 101         return __builtin_popcountll(x);
 102 }
 103
 104 /* Return the highest power of 2 that is <= n, or -1 if n == 0 */
 105 inline static int
 106 bit_floor(uint64_t n)
 107 {
 108         return bit_first(n);
 109 }
 110
 111 /* Return the lowest power of 2 that is >= n, or -1 if n == 0 */
 112 inline static int
 113 bit_ceiling(uint64_t n)
 114 {
 115         if (n == 0) {
 116                 return -1;
 117         }
 118         return bit_first(n - 1) + 1;
 119 }
 120
 121 /* If n is a power of 2, bit_log2(n) == bit_floor(n) == bit_ceiling(n) */
 122 #define bit_log2(n)             bit_floor((uint64_t)(n))
 123
 124 typedef _Atomic uint64_t                bitmap_t;
 125
 126
 127 inline static bool
 128 atomic_bit_set(bitmap_t *map, int n, int mem_order)
 129 {
 130         bitmap_t prev;
 131         prev = __c11_atomic_fetch_or(map, BIT(n), mem_order);
 132         return bit_test(prev, n);
 133 }
 134
 135 inline static bool
 136 atomic_bit_clear(bitmap_t *map, int n, int mem_order)
 137 {
 138         bitmap_t prev;
 139         prev = __c11_atomic_fetch_and(map, ~BIT(n), mem_order);
 140         return bit_test(prev, n);
 141 }
 142
 143
 144 #define BITMAP_LEN(n)   (((uint)(n) + 63) >> 6)         /* Round to 64bit bitmap_t */
 145 #define BITMAP_SIZE(n)  (size_t)(BITMAP_LEN(n) << 3)            /* Round to 64bit bitmap_t, then convert to bytes */
 146 #define bitmap_bit(n)   bits(n, 5, 0)
 147 #define bitmap_index(n) bits(n, 63, 6)
 148
 149 inline static bitmap_t *
 150 bitmap_zero(bitmap_t *map, uint nbits)
 151 {
 152         return (bitmap_t *)memset((void *)map, 0, BITMAP_SIZE(nbits));
 153 }
 154
 155 inline static bitmap_t *
 156 bitmap_full(bitmap_t *map, uint nbits)
 157 {
 158         return (bitmap_t *)memset((void *)map, ~0, BITMAP_SIZE(nbits));
 159 }
 160
 161 inline static bitmap_t *
 162 bitmap_alloc(uint nbits)
 163 {
 164         assert(nbits > 0);
 165         bitmap_t *map = (bitmap_t *)kalloc(BITMAP_SIZE(nbits));
 166         if (map) {
 167                 bitmap_zero(map, nbits);
 168         }
 169         return map;
 170 }
 171
 172 inline static void
 173 bitmap_free(bitmap_t *map, uint nbits)
 174 {
 175         assert(nbits > 0);
 176         kfree(map, BITMAP_SIZE(nbits));
 177 }
 178
 179 inline static void
 180 bitmap_set(bitmap_t *map, uint n)
 181 {
 182         bit_set(map[bitmap_index(n)], bitmap_bit(n));
 183 }
 184
 185 inline static void
 186 bitmap_clear(bitmap_t *map, uint n)
 187 {
 188         bit_clear(map[bitmap_index(n)], bitmap_bit(n));
 189 }
 190
 191 inline static bool
 192 atomic_bitmap_set(bitmap_t *map, uint n, int mem_order)
 193 {
 194         return atomic_bit_set(&map[bitmap_index(n)], bitmap_bit(n), mem_order);
 195 }
 196
 197 inline static bool
 198 atomic_bitmap_clear(bitmap_t *map, uint n, int mem_order)
 199 {
 200         return atomic_bit_clear(&map[bitmap_index(n)], bitmap_bit(n), mem_order);
 201 }
 202
 203 inline static bool
 204 bitmap_test(bitmap_t *map, uint n)
 205 {
 206         return bit_test(map[bitmap_index(n)], bitmap_bit(n));
 207 }
 208
 209 inline static int
 210 bitmap_first(bitmap_t *map, uint nbits)
 211 {
 212         for (int i = (int)bitmap_index(nbits - 1); i >= 0; i--) {
 213                 if (map[i] == 0) {
 214                         continue;
 215                 }
 216                 return (i << 6) + bit_first(map[i]);
 217         }
 218
 219         return -1;
 220 }
 221
 222 inline static int
 223 bitmap_and_not_mask_first(bitmap_t *map, bitmap_t *mask, uint nbits)
 224 {
 225         for (int i = (int)bitmap_index(nbits - 1); i >= 0; i--) {
 226                 if ((map[i] & ~mask[i]) == 0) {
 227                         continue;
 228                 }
 229                 return (i << 6) + bit_first(map[i] & ~mask[i]);
 230         }
 231
 232         return -1;
 233 }
 234
 235 inline static int
 236 bitmap_lsb_first(bitmap_t *map, uint nbits)
 237 {
 238         for (uint i = 0; i <= bitmap_index(nbits - 1); i++) {
 239                 if (map[i] == 0) {
 240                         continue;
 241                 }
 242                 return (int)((i << 6) + (uint32_t)lsb_first(map[i]));
 243         }
 244
 245         return -1;
 246 }
 247
 248 inline static int
 249 bitmap_next(bitmap_t *map, uint prev)
 250 {
 251         if (prev == 0) {
 252                 return -1;
 253         }
 254
 255         int64_t i = bitmap_index(prev - 1);
 256         int res = __bit_next(map[i], bits(prev, 5, 0));
 257         if (res >= 0) {
 258                 return (int)(res + (i << 6));
 259         }
 260
 261         for (i = i - 1; i >= 0; i--) {
 262                 if (map[i] == 0) {
 263                         continue;
 264                 }
 265                 return (int)((i << 6) + bit_first(map[i]));
 266         }
 267
 268         return -1;
 269 }
 270
 271 inline static int
 272 bitmap_lsb_next(bitmap_t *map, uint nbits, uint prev)
 273 {
 274         if ((prev + 1) >= nbits) {
 275                 return -1;
 276         }
 277
 278         uint64_t i = bitmap_index(prev + 1);
 279         uint b = bits((prev + 1), 5, 0) - 1;
 280         int32_t res = lsb_next((uint64_t)map[i], (int)b);
 281         if (res >= 0) {
 282                 return (int)((uint64_t)res + (i << 6));
 283         }
 284
 285         for (i = i + 1; i <= bitmap_index(nbits - 1); i++) {
 286                 if (map[i] == 0) {
 287                         continue;
 288                 }
 289                 return (int)((i << 6) + (uint64_t)lsb_first(map[i]));
 290         }
 291
 292         return -1;
 293 }
 294
 295 #endif