1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright (C) 2022 Intel Corporation. 3 * All rights reserved. 4 */ 5 6 #include "spdk/log.h" 7 #include "spdk/util.h" 8 9 #include "ftl_bitmap.h" 10 #include "ftl_internal.h" 11 12 typedef unsigned long bitmap_word; 13 14 const size_t ftl_bitmap_buffer_alignment = sizeof(bitmap_word); 15 16 #define FTL_BITMAP_WORD_SHIFT spdk_u32log2(sizeof(bitmap_word) * 8) 17 #define FTL_BITMAP_WORD_MASK (~(~0UL << FTL_BITMAP_WORD_SHIFT)) 18 19 uint64_t 20 ftl_bitmap_bits_to_size(uint64_t bits) 21 { 22 uint64_t size; 23 24 if (bits < ftl_bitmap_buffer_alignment) { 25 bits = ftl_bitmap_buffer_alignment; 26 } 27 28 size = spdk_divide_round_up(bits, 8); 29 size = spdk_divide_round_up(size, ftl_bitmap_buffer_alignment) * ftl_bitmap_buffer_alignment; 30 31 return size; 32 } 33 34 uint64_t 35 ftl_bitmap_bits_to_blocks(uint64_t bits) 36 { 37 uint64_t size = ftl_bitmap_bits_to_size(bits); 38 39 return spdk_divide_round_up(size, FTL_BLOCK_SIZE); 40 } 41 42 struct ftl_bitmap { 43 bitmap_word *buf; 44 size_t size; 45 }; 46 47 struct ftl_bitmap *ftl_bitmap_create(void *buf, size_t size) 48 { 49 struct ftl_bitmap *bitmap; 50 51 if ((uintptr_t)buf % ftl_bitmap_buffer_alignment) { 52 SPDK_ERRLOG("Buffer for bitmap must be aligned to %lu bytes\n", 53 ftl_bitmap_buffer_alignment); 54 return NULL; 55 } 56 57 if (size % ftl_bitmap_buffer_alignment) { 58 SPDK_ERRLOG("Size of buffer for bitmap must be divisible by %lu bytes\n", 59 ftl_bitmap_buffer_alignment); 60 return NULL; 61 } 62 63 bitmap = calloc(1, sizeof(*bitmap)); 64 if (!bitmap) { 65 return NULL; 66 } 67 68 bitmap->buf = buf; 69 bitmap->size = size / sizeof(bitmap_word); 70 71 return bitmap; 72 } 73 74 void 75 ftl_bitmap_destroy(struct ftl_bitmap *bitmap) 76 { 77 free(bitmap); 78 } 79 80 static inline void 81 locate_bit(const struct ftl_bitmap *bitmap, uint64_t bit, 82 bitmap_word **word_out, uint8_t *word_bit_idx_out) 83 { 84 size_t word_idx = bit >> FTL_BITMAP_WORD_SHIFT; 85 86 assert(word_idx < bitmap->size); 87 88 *word_bit_idx_out = bit & FTL_BITMAP_WORD_MASK; 89 *word_out = &bitmap->buf[word_idx]; 90 } 91 92 bool 93 ftl_bitmap_get(const struct ftl_bitmap *bitmap, uint64_t bit) 94 { 95 bitmap_word *word; 96 uint8_t word_bit_idx; 97 98 locate_bit(bitmap, bit, &word, &word_bit_idx); 99 100 return *word & (1UL << word_bit_idx); 101 } 102 103 void 104 ftl_bitmap_set(struct ftl_bitmap *bitmap, uint64_t bit) 105 { 106 bitmap_word *word; 107 uint8_t word_bit_idx; 108 109 locate_bit(bitmap, bit, &word, &word_bit_idx); 110 111 *word |= (1UL << word_bit_idx); 112 } 113 114 void 115 ftl_bitmap_clear(struct ftl_bitmap *bitmap, uint64_t bit) 116 { 117 bitmap_word *word; 118 uint8_t word_bit_idx; 119 120 locate_bit(bitmap, bit, &word, &word_bit_idx); 121 122 *word &= ~(1UL << word_bit_idx); 123 } 124 125 static uint64_t 126 ftl_bitmap_find_first(struct ftl_bitmap *bitmap, uint64_t start_bit, 127 uint64_t end_bit, bool value) 128 { 129 bitmap_word skip = (value ? 0 : ~0UL); 130 bitmap_word word; 131 size_t i, end; 132 uint64_t ret; 133 134 assert(start_bit <= end_bit); 135 136 i = start_bit >> FTL_BITMAP_WORD_SHIFT; 137 assert(i < bitmap->size); 138 139 word = (bitmap->buf[i] ^ skip) & (~0UL << (start_bit & FTL_BITMAP_WORD_MASK)); 140 if (word != 0) { 141 goto found; 142 } 143 144 end = spdk_min((end_bit >> FTL_BITMAP_WORD_SHIFT) + 1, bitmap->size); 145 for (i = i + 1; i < end; i++) { 146 word = bitmap->buf[i] ^ skip; 147 if (word != 0) { 148 goto found; 149 } 150 } 151 152 return UINT64_MAX; 153 found: 154 ret = (i << FTL_BITMAP_WORD_SHIFT) + __builtin_ctzl(word); 155 if (ret > end_bit) { 156 return UINT64_MAX; 157 } 158 return ret; 159 } 160 161 uint64_t 162 ftl_bitmap_find_first_set(struct ftl_bitmap *bitmap, uint64_t start_bit, uint64_t end_bit) 163 { 164 return ftl_bitmap_find_first(bitmap, start_bit, end_bit, true); 165 } 166 167 uint64_t 168 ftl_bitmap_find_first_clear(struct ftl_bitmap *bitmap, uint64_t start_bit, 169 uint64_t end_bit) 170 { 171 return ftl_bitmap_find_first(bitmap, start_bit, end_bit, false); 172 } 173 174 uint64_t 175 ftl_bitmap_count_set(struct ftl_bitmap *bitmap) 176 { 177 size_t i; 178 bitmap_word *word = bitmap->buf; 179 uint64_t count = 0; 180 181 for (i = 0; i < bitmap->size; i++, word++) { 182 count += __builtin_popcountl(*word); 183 } 184 185 return count; 186 } 187