1 /* 2 * Copyright (C) 2016 Facebook 3 * Copyright (C) 2013-2014 Jens Axboe 4 * 5 * This program is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU General Public 7 * License v2 as published by the Free Software Foundation. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 * General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program. If not, see <https://www.gnu.org/licenses/>. 16 */ 17 18 #include <linux/random.h> 19 #include <linux/sbitmap.h> 20 21 int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift, 22 gfp_t flags, int node) 23 { 24 unsigned int bits_per_word; 25 unsigned int i; 26 27 if (shift < 0) { 28 shift = ilog2(BITS_PER_LONG); 29 /* 30 * If the bitmap is small, shrink the number of bits per word so 31 * we spread over a few cachelines, at least. If less than 4 32 * bits, just forget about it, it's not going to work optimally 33 * anyway. 34 */ 35 if (depth >= 4) { 36 while ((4U << shift) > depth) 37 shift--; 38 } 39 } 40 bits_per_word = 1U << shift; 41 if (bits_per_word > BITS_PER_LONG) 42 return -EINVAL; 43 44 sb->shift = shift; 45 sb->depth = depth; 46 sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word); 47 48 if (depth == 0) { 49 sb->map = NULL; 50 return 0; 51 } 52 53 sb->map = kzalloc_node(sb->map_nr * sizeof(*sb->map), flags, node); 54 if (!sb->map) 55 return -ENOMEM; 56 57 for (i = 0; i < sb->map_nr; i++) { 58 sb->map[i].depth = min(depth, bits_per_word); 59 depth -= sb->map[i].depth; 60 } 61 return 0; 62 } 63 EXPORT_SYMBOL_GPL(sbitmap_init_node); 64 65 void sbitmap_resize(struct sbitmap *sb, unsigned int depth) 66 { 67 unsigned int bits_per_word = 1U << sb->shift; 68 unsigned int i; 69 70 sb->depth = depth; 71 sb->map_nr = DIV_ROUND_UP(sb->depth, bits_per_word); 72 73 for (i = 0; i < sb->map_nr; i++) { 74 sb->map[i].depth = min(depth, bits_per_word); 75 depth -= sb->map[i].depth; 76 } 77 } 78 EXPORT_SYMBOL_GPL(sbitmap_resize); 79 80 static int __sbitmap_get_word(struct sbitmap_word *word, unsigned int hint, 81 bool wrap) 82 { 83 unsigned int orig_hint = hint; 84 int nr; 85 86 while (1) { 87 nr = find_next_zero_bit(&word->word, word->depth, hint); 88 if (unlikely(nr >= word->depth)) { 89 /* 90 * We started with an offset, and we didn't reset the 91 * offset to 0 in a failure case, so start from 0 to 92 * exhaust the map. 93 */ 94 if (orig_hint && hint && wrap) { 95 hint = orig_hint = 0; 96 continue; 97 } 98 return -1; 99 } 100 101 if (!test_and_set_bit(nr, &word->word)) 102 break; 103 104 hint = nr + 1; 105 if (hint >= word->depth - 1) 106 hint = 0; 107 } 108 109 return nr; 110 } 111 112 int sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint, bool round_robin) 113 { 114 unsigned int i, index; 115 int nr = -1; 116 117 index = SB_NR_TO_INDEX(sb, alloc_hint); 118 119 for (i = 0; i < sb->map_nr; i++) { 120 nr = __sbitmap_get_word(&sb->map[index], 121 SB_NR_TO_BIT(sb, alloc_hint), 122 !round_robin); 123 if (nr != -1) { 124 nr += index << sb->shift; 125 break; 126 } 127 128 /* Jump to next index. */ 129 index++; 130 alloc_hint = index << sb->shift; 131 132 if (index >= sb->map_nr) { 133 index = 0; 134 alloc_hint = 0; 135 } 136 } 137 138 return nr; 139 } 140 EXPORT_SYMBOL_GPL(sbitmap_get); 141 142 bool sbitmap_any_bit_set(const struct sbitmap *sb) 143 { 144 unsigned int i; 145 146 for (i = 0; i < sb->map_nr; i++) { 147 if (sb->map[i].word) 148 return true; 149 } 150 return false; 151 } 152 EXPORT_SYMBOL_GPL(sbitmap_any_bit_set); 153 154 bool sbitmap_any_bit_clear(const struct sbitmap *sb) 155 { 156 unsigned int i; 157 158 for (i = 0; i < sb->map_nr; i++) { 159 const struct sbitmap_word *word = &sb->map[i]; 160 unsigned long ret; 161 162 ret = find_first_zero_bit(&word->word, word->depth); 163 if (ret < word->depth) 164 return true; 165 } 166 return false; 167 } 168 EXPORT_SYMBOL_GPL(sbitmap_any_bit_clear); 169 170 unsigned int sbitmap_weight(const struct sbitmap *sb) 171 { 172 unsigned int i, weight; 173 174 for (i = 0; i < sb->map_nr; i++) { 175 const struct sbitmap_word *word = &sb->map[i]; 176 177 weight += bitmap_weight(&word->word, word->depth); 178 } 179 return weight; 180 } 181 EXPORT_SYMBOL_GPL(sbitmap_weight); 182 183 static unsigned int sbq_calc_wake_batch(unsigned int depth) 184 { 185 unsigned int wake_batch; 186 187 /* 188 * For each batch, we wake up one queue. We need to make sure that our 189 * batch size is small enough that the full depth of the bitmap is 190 * enough to wake up all of the queues. 191 */ 192 wake_batch = SBQ_WAKE_BATCH; 193 if (wake_batch > depth / SBQ_WAIT_QUEUES) 194 wake_batch = max(1U, depth / SBQ_WAIT_QUEUES); 195 196 return wake_batch; 197 } 198 199 int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth, 200 int shift, bool round_robin, gfp_t flags, int node) 201 { 202 int ret; 203 int i; 204 205 ret = sbitmap_init_node(&sbq->sb, depth, shift, flags, node); 206 if (ret) 207 return ret; 208 209 sbq->alloc_hint = alloc_percpu_gfp(unsigned int, flags); 210 if (!sbq->alloc_hint) { 211 sbitmap_free(&sbq->sb); 212 return -ENOMEM; 213 } 214 215 if (depth && !round_robin) { 216 for_each_possible_cpu(i) 217 *per_cpu_ptr(sbq->alloc_hint, i) = prandom_u32() % depth; 218 } 219 220 sbq->wake_batch = sbq_calc_wake_batch(depth); 221 atomic_set(&sbq->wake_index, 0); 222 223 sbq->ws = kzalloc_node(SBQ_WAIT_QUEUES * sizeof(*sbq->ws), flags, node); 224 if (!sbq->ws) { 225 free_percpu(sbq->alloc_hint); 226 sbitmap_free(&sbq->sb); 227 return -ENOMEM; 228 } 229 230 for (i = 0; i < SBQ_WAIT_QUEUES; i++) { 231 init_waitqueue_head(&sbq->ws[i].wait); 232 atomic_set(&sbq->ws[i].wait_cnt, sbq->wake_batch); 233 } 234 235 sbq->round_robin = round_robin; 236 return 0; 237 } 238 EXPORT_SYMBOL_GPL(sbitmap_queue_init_node); 239 240 void sbitmap_queue_resize(struct sbitmap_queue *sbq, unsigned int depth) 241 { 242 sbq->wake_batch = sbq_calc_wake_batch(depth); 243 sbitmap_resize(&sbq->sb, depth); 244 } 245 EXPORT_SYMBOL_GPL(sbitmap_queue_resize); 246 247 int __sbitmap_queue_get(struct sbitmap_queue *sbq) 248 { 249 unsigned int hint; 250 int nr; 251 252 hint = this_cpu_read(*sbq->alloc_hint); 253 nr = sbitmap_get(&sbq->sb, hint, sbq->round_robin); 254 255 if (nr == -1) { 256 /* If the map is full, a hint won't do us much good. */ 257 this_cpu_write(*sbq->alloc_hint, 0); 258 } else if (nr == hint || unlikely(sbq->round_robin)) { 259 /* Only update the hint if we used it. */ 260 hint = nr + 1; 261 if (hint >= sbq->sb.depth - 1) 262 hint = 0; 263 this_cpu_write(*sbq->alloc_hint, hint); 264 } 265 266 return nr; 267 } 268 EXPORT_SYMBOL_GPL(__sbitmap_queue_get); 269 270 static struct sbq_wait_state *sbq_wake_ptr(struct sbitmap_queue *sbq) 271 { 272 int i, wake_index; 273 274 wake_index = atomic_read(&sbq->wake_index); 275 for (i = 0; i < SBQ_WAIT_QUEUES; i++) { 276 struct sbq_wait_state *ws = &sbq->ws[wake_index]; 277 278 if (waitqueue_active(&ws->wait)) { 279 int o = atomic_read(&sbq->wake_index); 280 281 if (wake_index != o) 282 atomic_cmpxchg(&sbq->wake_index, o, wake_index); 283 return ws; 284 } 285 286 wake_index = sbq_index_inc(wake_index); 287 } 288 289 return NULL; 290 } 291 292 static void sbq_wake_up(struct sbitmap_queue *sbq) 293 { 294 struct sbq_wait_state *ws; 295 int wait_cnt; 296 297 /* Ensure that the wait list checks occur after clear_bit(). */ 298 smp_mb(); 299 300 ws = sbq_wake_ptr(sbq); 301 if (!ws) 302 return; 303 304 wait_cnt = atomic_dec_return(&ws->wait_cnt); 305 if (unlikely(wait_cnt < 0)) 306 wait_cnt = atomic_inc_return(&ws->wait_cnt); 307 if (wait_cnt == 0) { 308 atomic_add(sbq->wake_batch, &ws->wait_cnt); 309 sbq_index_atomic_inc(&sbq->wake_index); 310 wake_up(&ws->wait); 311 } 312 } 313 314 void sbitmap_queue_clear(struct sbitmap_queue *sbq, unsigned int nr, 315 unsigned int cpu) 316 { 317 sbitmap_clear_bit(&sbq->sb, nr); 318 sbq_wake_up(sbq); 319 if (likely(!sbq->round_robin)) 320 *per_cpu_ptr(sbq->alloc_hint, cpu) = nr; 321 } 322 EXPORT_SYMBOL_GPL(sbitmap_queue_clear); 323 324 void sbitmap_queue_wake_all(struct sbitmap_queue *sbq) 325 { 326 int i, wake_index; 327 328 /* 329 * Make sure all changes prior to this are visible from other CPUs. 330 */ 331 smp_mb(); 332 wake_index = atomic_read(&sbq->wake_index); 333 for (i = 0; i < SBQ_WAIT_QUEUES; i++) { 334 struct sbq_wait_state *ws = &sbq->ws[wake_index]; 335 336 if (waitqueue_active(&ws->wait)) 337 wake_up(&ws->wait); 338 339 wake_index = sbq_index_inc(wake_index); 340 } 341 } 342 EXPORT_SYMBOL_GPL(sbitmap_queue_wake_all); 343