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
ftl_bitmap_bits_to_size(uint64_t bits)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
ftl_bitmap_bits_to_blocks(uint64_t bits)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
ftl_bitmap_create(void * buf,size_t size)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
ftl_bitmap_destroy(struct ftl_bitmap * bitmap)75 ftl_bitmap_destroy(struct ftl_bitmap *bitmap)
76 {
77 free(bitmap);
78 }
79
80 static inline void
locate_bit(const struct ftl_bitmap * bitmap,uint64_t bit,bitmap_word ** word_out,uint8_t * word_bit_idx_out)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
ftl_bitmap_get(const struct ftl_bitmap * bitmap,uint64_t bit)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
ftl_bitmap_set(struct ftl_bitmap * bitmap,uint64_t bit)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
ftl_bitmap_clear(struct ftl_bitmap * bitmap,uint64_t bit)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
ftl_bitmap_find_first(struct ftl_bitmap * bitmap,uint64_t start_bit,uint64_t end_bit,bool value)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
ftl_bitmap_find_first_set(struct ftl_bitmap * bitmap,uint64_t start_bit,uint64_t end_bit)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
ftl_bitmap_find_first_clear(struct ftl_bitmap * bitmap,uint64_t start_bit,uint64_t end_bit)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
ftl_bitmap_count_set(struct ftl_bitmap * bitmap)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