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