10fc479b1SThomas Gleixner /* SPDX-License-Identifier: GPL-2.0-only */ 288459642SOmar Sandoval /* 388459642SOmar Sandoval * Fast and scalable bitmaps. 488459642SOmar Sandoval * 588459642SOmar Sandoval * Copyright (C) 2016 Facebook 688459642SOmar Sandoval * Copyright (C) 2013-2014 Jens Axboe 788459642SOmar Sandoval */ 888459642SOmar Sandoval 988459642SOmar Sandoval #ifndef __LINUX_SCALE_BITMAP_H 1088459642SOmar Sandoval #define __LINUX_SCALE_BITMAP_H 1188459642SOmar Sandoval 1288459642SOmar Sandoval #include <linux/kernel.h> 1388459642SOmar Sandoval #include <linux/slab.h> 1488459642SOmar Sandoval 1514b470b5SArnd Bergmann struct seq_file; 1614b470b5SArnd Bergmann 1788459642SOmar Sandoval /** 1888459642SOmar Sandoval * struct sbitmap_word - Word in a &struct sbitmap. 1988459642SOmar Sandoval */ 2088459642SOmar Sandoval struct sbitmap_word { 2188459642SOmar Sandoval /** 22ea86ea2cSJens Axboe * @depth: Number of bits being used in @word/@cleared 2388459642SOmar Sandoval */ 2488459642SOmar Sandoval unsigned long depth; 25ea86ea2cSJens Axboe 26ea86ea2cSJens Axboe /** 27ea86ea2cSJens Axboe * @word: word holding free bits 28ea86ea2cSJens Axboe */ 29ea86ea2cSJens Axboe unsigned long word ____cacheline_aligned_in_smp; 30ea86ea2cSJens Axboe 31ea86ea2cSJens Axboe /** 32ea86ea2cSJens Axboe * @cleared: word holding cleared bits 33ea86ea2cSJens Axboe */ 34ea86ea2cSJens Axboe unsigned long cleared ____cacheline_aligned_in_smp; 3588459642SOmar Sandoval } ____cacheline_aligned_in_smp; 3688459642SOmar Sandoval 3788459642SOmar Sandoval /** 3888459642SOmar Sandoval * struct sbitmap - Scalable bitmap. 3988459642SOmar Sandoval * 4088459642SOmar Sandoval * A &struct sbitmap is spread over multiple cachelines to avoid ping-pong. This 4188459642SOmar Sandoval * trades off higher memory usage for better scalability. 4288459642SOmar Sandoval */ 4388459642SOmar Sandoval struct sbitmap { 4488459642SOmar Sandoval /** 4588459642SOmar Sandoval * @depth: Number of bits used in the whole bitmap. 4688459642SOmar Sandoval */ 4788459642SOmar Sandoval unsigned int depth; 4888459642SOmar Sandoval 4988459642SOmar Sandoval /** 5088459642SOmar Sandoval * @shift: log2(number of bits used per word) 5188459642SOmar Sandoval */ 5288459642SOmar Sandoval unsigned int shift; 5388459642SOmar Sandoval 5488459642SOmar Sandoval /** 5588459642SOmar Sandoval * @map_nr: Number of words (cachelines) being used for the bitmap. 5688459642SOmar Sandoval */ 5788459642SOmar Sandoval unsigned int map_nr; 5888459642SOmar Sandoval 5988459642SOmar Sandoval /** 60efe1f3a1SMing Lei * @round_robin: Allocate bits in strict round-robin order. 61efe1f3a1SMing Lei */ 62efe1f3a1SMing Lei bool round_robin; 63efe1f3a1SMing Lei 64efe1f3a1SMing Lei /** 6588459642SOmar Sandoval * @map: Allocated bitmap. 6688459642SOmar Sandoval */ 6788459642SOmar Sandoval struct sbitmap_word *map; 68c548e62bSMing Lei 69c548e62bSMing Lei /* 70c548e62bSMing Lei * @alloc_hint: Cache of last successfully allocated or freed bit. 71c548e62bSMing Lei * 72c548e62bSMing Lei * This is per-cpu, which allows multiple users to stick to different 73c548e62bSMing Lei * cachelines until the map is exhausted. 74c548e62bSMing Lei */ 75c548e62bSMing Lei unsigned int __percpu *alloc_hint; 7688459642SOmar Sandoval }; 7788459642SOmar Sandoval 7888459642SOmar Sandoval #define SBQ_WAIT_QUEUES 8 7988459642SOmar Sandoval #define SBQ_WAKE_BATCH 8 8088459642SOmar Sandoval 8188459642SOmar Sandoval /** 8288459642SOmar Sandoval * struct sbq_wait_state - Wait queue in a &struct sbitmap_queue. 8388459642SOmar Sandoval */ 8488459642SOmar Sandoval struct sbq_wait_state { 8588459642SOmar Sandoval /** 8688459642SOmar Sandoval * @wait_cnt: Number of frees remaining before we wake up. 8788459642SOmar Sandoval */ 8888459642SOmar Sandoval atomic_t wait_cnt; 8988459642SOmar Sandoval 9088459642SOmar Sandoval /** 9188459642SOmar Sandoval * @wait: Wait queue. 9288459642SOmar Sandoval */ 9388459642SOmar Sandoval wait_queue_head_t wait; 9488459642SOmar Sandoval } ____cacheline_aligned_in_smp; 9588459642SOmar Sandoval 9688459642SOmar Sandoval /** 9788459642SOmar Sandoval * struct sbitmap_queue - Scalable bitmap with the added ability to wait on free 9888459642SOmar Sandoval * bits. 9988459642SOmar Sandoval * 10088459642SOmar Sandoval * A &struct sbitmap_queue uses multiple wait queues and rolling wakeups to 10188459642SOmar Sandoval * avoid contention on the wait queue spinlock. This ensures that we don't hit a 10288459642SOmar Sandoval * scalability wall when we run out of free bits and have to start putting tasks 10388459642SOmar Sandoval * to sleep. 10488459642SOmar Sandoval */ 10588459642SOmar Sandoval struct sbitmap_queue { 10688459642SOmar Sandoval /** 10788459642SOmar Sandoval * @sb: Scalable bitmap. 10888459642SOmar Sandoval */ 10988459642SOmar Sandoval struct sbitmap sb; 11088459642SOmar Sandoval 11188459642SOmar Sandoval /** 11288459642SOmar Sandoval * @wake_batch: Number of bits which must be freed before we wake up any 11388459642SOmar Sandoval * waiters. 11488459642SOmar Sandoval */ 11588459642SOmar Sandoval unsigned int wake_batch; 11688459642SOmar Sandoval 11788459642SOmar Sandoval /** 11888459642SOmar Sandoval * @wake_index: Next wait queue in @ws to wake up. 11988459642SOmar Sandoval */ 12088459642SOmar Sandoval atomic_t wake_index; 12188459642SOmar Sandoval 12288459642SOmar Sandoval /** 12388459642SOmar Sandoval * @ws: Wait queues. 12488459642SOmar Sandoval */ 12588459642SOmar Sandoval struct sbq_wait_state *ws; 126f4a644dbSOmar Sandoval 1275d2ee712SJens Axboe /* 1285d2ee712SJens Axboe * @ws_active: count of currently active ws waitqueues 1295d2ee712SJens Axboe */ 1305d2ee712SJens Axboe atomic_t ws_active; 1315d2ee712SJens Axboe 132f4a644dbSOmar Sandoval /** 133a3275539SOmar Sandoval * @min_shallow_depth: The minimum shallow depth which may be passed to 134a3275539SOmar Sandoval * sbitmap_queue_get_shallow() or __sbitmap_queue_get_shallow(). 135a3275539SOmar Sandoval */ 136a3275539SOmar Sandoval unsigned int min_shallow_depth; 13788459642SOmar Sandoval }; 13888459642SOmar Sandoval 13988459642SOmar Sandoval /** 14088459642SOmar Sandoval * sbitmap_init_node() - Initialize a &struct sbitmap on a specific memory node. 14188459642SOmar Sandoval * @sb: Bitmap to initialize. 14288459642SOmar Sandoval * @depth: Number of bits to allocate. 14388459642SOmar Sandoval * @shift: Use 2^@shift bits per word in the bitmap; if a negative number if 14488459642SOmar Sandoval * given, a good default is chosen. 14588459642SOmar Sandoval * @flags: Allocation flags. 14688459642SOmar Sandoval * @node: Memory node to allocate on. 147efe1f3a1SMing Lei * @round_robin: If true, be stricter about allocation order; always allocate 148efe1f3a1SMing Lei * starting from the last allocated bit. This is less efficient 149efe1f3a1SMing Lei * than the default behavior (false). 150c548e62bSMing Lei * @alloc_hint: If true, apply percpu hint for where to start searching for 151c548e62bSMing Lei * a free bit. 15288459642SOmar Sandoval * 15388459642SOmar Sandoval * Return: Zero on success or negative errno on failure. 15488459642SOmar Sandoval */ 15588459642SOmar Sandoval int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift, 156c548e62bSMing Lei gfp_t flags, int node, bool round_robin, bool alloc_hint); 15788459642SOmar Sandoval 15888459642SOmar Sandoval /** 15988459642SOmar Sandoval * sbitmap_free() - Free memory used by a &struct sbitmap. 16088459642SOmar Sandoval * @sb: Bitmap to free. 16188459642SOmar Sandoval */ 16288459642SOmar Sandoval static inline void sbitmap_free(struct sbitmap *sb) 16388459642SOmar Sandoval { 164c548e62bSMing Lei free_percpu(sb->alloc_hint); 16588459642SOmar Sandoval kfree(sb->map); 16688459642SOmar Sandoval sb->map = NULL; 16788459642SOmar Sandoval } 16888459642SOmar Sandoval 16988459642SOmar Sandoval /** 17088459642SOmar Sandoval * sbitmap_resize() - Resize a &struct sbitmap. 17188459642SOmar Sandoval * @sb: Bitmap to resize. 17288459642SOmar Sandoval * @depth: New number of bits to resize to. 17388459642SOmar Sandoval * 17488459642SOmar Sandoval * Doesn't reallocate anything. It's up to the caller to ensure that the new 17588459642SOmar Sandoval * depth doesn't exceed the depth that the sb was initialized with. 17688459642SOmar Sandoval */ 17788459642SOmar Sandoval void sbitmap_resize(struct sbitmap *sb, unsigned int depth); 17888459642SOmar Sandoval 17988459642SOmar Sandoval /** 18088459642SOmar Sandoval * sbitmap_get() - Try to allocate a free bit from a &struct sbitmap. 18188459642SOmar Sandoval * @sb: Bitmap to allocate from. 18288459642SOmar Sandoval * 1834ace53f1SOmar Sandoval * This operation provides acquire barrier semantics if it succeeds. 1844ace53f1SOmar Sandoval * 18588459642SOmar Sandoval * Return: Non-negative allocated bit number if successful, -1 otherwise. 18688459642SOmar Sandoval */ 187c548e62bSMing Lei int sbitmap_get(struct sbitmap *sb); 18888459642SOmar Sandoval 18988459642SOmar Sandoval /** 190c05e6673SOmar Sandoval * sbitmap_get_shallow() - Try to allocate a free bit from a &struct sbitmap, 191c05e6673SOmar Sandoval * limiting the depth used from each word. 192c05e6673SOmar Sandoval * @sb: Bitmap to allocate from. 193c05e6673SOmar Sandoval * @shallow_depth: The maximum number of bits to allocate from a single word. 194c05e6673SOmar Sandoval * 195c05e6673SOmar Sandoval * This rather specific operation allows for having multiple users with 196c05e6673SOmar Sandoval * different allocation limits. E.g., there can be a high-priority class that 197c05e6673SOmar Sandoval * uses sbitmap_get() and a low-priority class that uses sbitmap_get_shallow() 198c05e6673SOmar Sandoval * with a @shallow_depth of (1 << (@sb->shift - 1)). Then, the low-priority 199c05e6673SOmar Sandoval * class can only allocate half of the total bits in the bitmap, preventing it 200c05e6673SOmar Sandoval * from starving out the high-priority class. 201c05e6673SOmar Sandoval * 202c05e6673SOmar Sandoval * Return: Non-negative allocated bit number if successful, -1 otherwise. 203c05e6673SOmar Sandoval */ 204c548e62bSMing Lei int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth); 205c05e6673SOmar Sandoval 206c05e6673SOmar Sandoval /** 20788459642SOmar Sandoval * sbitmap_any_bit_set() - Check for a set bit in a &struct sbitmap. 20888459642SOmar Sandoval * @sb: Bitmap to check. 20988459642SOmar Sandoval * 21088459642SOmar Sandoval * Return: true if any bit in the bitmap is set, false otherwise. 21188459642SOmar Sandoval */ 21288459642SOmar Sandoval bool sbitmap_any_bit_set(const struct sbitmap *sb); 21388459642SOmar Sandoval 2147930d0a0SMing Lei #define SB_NR_TO_INDEX(sb, bitnr) ((bitnr) >> (sb)->shift) 2157930d0a0SMing Lei #define SB_NR_TO_BIT(sb, bitnr) ((bitnr) & ((1U << (sb)->shift) - 1U)) 2167930d0a0SMing Lei 21788459642SOmar Sandoval typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *); 21888459642SOmar Sandoval 21988459642SOmar Sandoval /** 2207930d0a0SMing Lei * __sbitmap_for_each_set() - Iterate over each set bit in a &struct sbitmap. 2217930d0a0SMing Lei * @start: Where to start the iteration. 22288459642SOmar Sandoval * @sb: Bitmap to iterate over. 22388459642SOmar Sandoval * @fn: Callback. Should return true to continue or false to break early. 22488459642SOmar Sandoval * @data: Pointer to pass to callback. 22588459642SOmar Sandoval * 22688459642SOmar Sandoval * This is inline even though it's non-trivial so that the function calls to the 22788459642SOmar Sandoval * callback will hopefully get optimized away. 22888459642SOmar Sandoval */ 2297930d0a0SMing Lei static inline void __sbitmap_for_each_set(struct sbitmap *sb, 2307930d0a0SMing Lei unsigned int start, 2317930d0a0SMing Lei sb_for_each_fn fn, void *data) 23288459642SOmar Sandoval { 2337930d0a0SMing Lei unsigned int index; 2347930d0a0SMing Lei unsigned int nr; 2357930d0a0SMing Lei unsigned int scanned = 0; 23688459642SOmar Sandoval 2377930d0a0SMing Lei if (start >= sb->depth) 2387930d0a0SMing Lei start = 0; 2397930d0a0SMing Lei index = SB_NR_TO_INDEX(sb, start); 2407930d0a0SMing Lei nr = SB_NR_TO_BIT(sb, start); 24188459642SOmar Sandoval 2427930d0a0SMing Lei while (scanned < sb->depth) { 2438c2def89SOmar Sandoval unsigned long word; 2448c2def89SOmar Sandoval unsigned int depth = min_t(unsigned int, 2458c2def89SOmar Sandoval sb->map[index].depth - nr, 2467930d0a0SMing Lei sb->depth - scanned); 2477930d0a0SMing Lei 2487930d0a0SMing Lei scanned += depth; 2498c2def89SOmar Sandoval word = sb->map[index].word & ~sb->map[index].cleared; 2508c2def89SOmar Sandoval if (!word) 2517930d0a0SMing Lei goto next; 25288459642SOmar Sandoval 2537930d0a0SMing Lei /* 2547930d0a0SMing Lei * On the first iteration of the outer loop, we need to add the 2557930d0a0SMing Lei * bit offset back to the size of the word for find_next_bit(). 2567930d0a0SMing Lei * On all other iterations, nr is zero, so this is a noop. 2577930d0a0SMing Lei */ 2587930d0a0SMing Lei depth += nr; 25988459642SOmar Sandoval while (1) { 2608c2def89SOmar Sandoval nr = find_next_bit(&word, depth, nr); 2617930d0a0SMing Lei if (nr >= depth) 26288459642SOmar Sandoval break; 2637930d0a0SMing Lei if (!fn(sb, (index << sb->shift) + nr, data)) 26488459642SOmar Sandoval return; 26588459642SOmar Sandoval 26688459642SOmar Sandoval nr++; 26788459642SOmar Sandoval } 2687930d0a0SMing Lei next: 2697930d0a0SMing Lei nr = 0; 2707930d0a0SMing Lei if (++index >= sb->map_nr) 2717930d0a0SMing Lei index = 0; 27288459642SOmar Sandoval } 27388459642SOmar Sandoval } 27488459642SOmar Sandoval 2757930d0a0SMing Lei /** 2767930d0a0SMing Lei * sbitmap_for_each_set() - Iterate over each set bit in a &struct sbitmap. 2777930d0a0SMing Lei * @sb: Bitmap to iterate over. 2787930d0a0SMing Lei * @fn: Callback. Should return true to continue or false to break early. 2797930d0a0SMing Lei * @data: Pointer to pass to callback. 2807930d0a0SMing Lei */ 2817930d0a0SMing Lei static inline void sbitmap_for_each_set(struct sbitmap *sb, sb_for_each_fn fn, 2827930d0a0SMing Lei void *data) 2837930d0a0SMing Lei { 2847930d0a0SMing Lei __sbitmap_for_each_set(sb, 0, fn, data); 2857930d0a0SMing Lei } 28688459642SOmar Sandoval 28788459642SOmar Sandoval static inline unsigned long *__sbitmap_word(struct sbitmap *sb, 28888459642SOmar Sandoval unsigned int bitnr) 28988459642SOmar Sandoval { 29088459642SOmar Sandoval return &sb->map[SB_NR_TO_INDEX(sb, bitnr)].word; 29188459642SOmar Sandoval } 29288459642SOmar Sandoval 29388459642SOmar Sandoval /* Helpers equivalent to the operations in asm/bitops.h and linux/bitmap.h */ 29488459642SOmar Sandoval 29588459642SOmar Sandoval static inline void sbitmap_set_bit(struct sbitmap *sb, unsigned int bitnr) 29688459642SOmar Sandoval { 29788459642SOmar Sandoval set_bit(SB_NR_TO_BIT(sb, bitnr), __sbitmap_word(sb, bitnr)); 29888459642SOmar Sandoval } 29988459642SOmar Sandoval 30088459642SOmar Sandoval static inline void sbitmap_clear_bit(struct sbitmap *sb, unsigned int bitnr) 30188459642SOmar Sandoval { 30288459642SOmar Sandoval clear_bit(SB_NR_TO_BIT(sb, bitnr), __sbitmap_word(sb, bitnr)); 30388459642SOmar Sandoval } 30488459642SOmar Sandoval 305ea86ea2cSJens Axboe /* 306ea86ea2cSJens Axboe * This one is special, since it doesn't actually clear the bit, rather it 307ea86ea2cSJens Axboe * sets the corresponding bit in the ->cleared mask instead. Paired with 3081e4471e7SShenghui Wang * the caller doing sbitmap_deferred_clear() if a given index is full, which 309ea86ea2cSJens Axboe * will clear the previously freed entries in the corresponding ->word. 310ea86ea2cSJens Axboe */ 311ea86ea2cSJens Axboe static inline void sbitmap_deferred_clear_bit(struct sbitmap *sb, unsigned int bitnr) 312ea86ea2cSJens Axboe { 313ea86ea2cSJens Axboe unsigned long *addr = &sb->map[SB_NR_TO_INDEX(sb, bitnr)].cleared; 314ea86ea2cSJens Axboe 315ea86ea2cSJens Axboe set_bit(SB_NR_TO_BIT(sb, bitnr), addr); 316ea86ea2cSJens Axboe } 317ea86ea2cSJens Axboe 318c548e62bSMing Lei /* 319c548e62bSMing Lei * Pair of sbitmap_get, and this one applies both cleared bit and 320c548e62bSMing Lei * allocation hint. 321c548e62bSMing Lei */ 322c548e62bSMing Lei static inline void sbitmap_put(struct sbitmap *sb, unsigned int bitnr) 323c548e62bSMing Lei { 324c548e62bSMing Lei sbitmap_deferred_clear_bit(sb, bitnr); 325c548e62bSMing Lei 326c548e62bSMing Lei if (likely(sb->alloc_hint && !sb->round_robin && bitnr < sb->depth)) 327035e9f47SBart Van Assche *raw_cpu_ptr(sb->alloc_hint) = bitnr; 328c548e62bSMing Lei } 329c548e62bSMing Lei 33088459642SOmar Sandoval static inline int sbitmap_test_bit(struct sbitmap *sb, unsigned int bitnr) 33188459642SOmar Sandoval { 33288459642SOmar Sandoval return test_bit(SB_NR_TO_BIT(sb, bitnr), __sbitmap_word(sb, bitnr)); 33388459642SOmar Sandoval } 33488459642SOmar Sandoval 3352d13b1eaSMing Lei static inline int sbitmap_calculate_shift(unsigned int depth) 3362d13b1eaSMing Lei { 3372d13b1eaSMing Lei int shift = ilog2(BITS_PER_LONG); 3382d13b1eaSMing Lei 3392d13b1eaSMing Lei /* 3402d13b1eaSMing Lei * If the bitmap is small, shrink the number of bits per word so 3412d13b1eaSMing Lei * we spread over a few cachelines, at least. If less than 4 3422d13b1eaSMing Lei * bits, just forget about it, it's not going to work optimally 3432d13b1eaSMing Lei * anyway. 3442d13b1eaSMing Lei */ 3452d13b1eaSMing Lei if (depth >= 4) { 3462d13b1eaSMing Lei while ((4U << shift) > depth) 3472d13b1eaSMing Lei shift--; 3482d13b1eaSMing Lei } 3492d13b1eaSMing Lei 3502d13b1eaSMing Lei return shift; 3512d13b1eaSMing Lei } 3522d13b1eaSMing Lei 35388459642SOmar Sandoval /** 35424af1ccfSOmar Sandoval * sbitmap_show() - Dump &struct sbitmap information to a &struct seq_file. 35524af1ccfSOmar Sandoval * @sb: Bitmap to show. 35624af1ccfSOmar Sandoval * @m: struct seq_file to write to. 35724af1ccfSOmar Sandoval * 35824af1ccfSOmar Sandoval * This is intended for debugging. The format may change at any time. 35924af1ccfSOmar Sandoval */ 36024af1ccfSOmar Sandoval void sbitmap_show(struct sbitmap *sb, struct seq_file *m); 36124af1ccfSOmar Sandoval 362cbb9950bSMing Lei 363cbb9950bSMing Lei /** 364cbb9950bSMing Lei * sbitmap_weight() - Return how many set and not cleared bits in a &struct 365cbb9950bSMing Lei * sbitmap. 366cbb9950bSMing Lei * @sb: Bitmap to check. 367cbb9950bSMing Lei * 368cbb9950bSMing Lei * Return: How many set and not cleared bits set 369cbb9950bSMing Lei */ 370cbb9950bSMing Lei unsigned int sbitmap_weight(const struct sbitmap *sb); 371cbb9950bSMing Lei 37224af1ccfSOmar Sandoval /** 37324af1ccfSOmar Sandoval * sbitmap_bitmap_show() - Write a hex dump of a &struct sbitmap to a &struct 37424af1ccfSOmar Sandoval * seq_file. 37524af1ccfSOmar Sandoval * @sb: Bitmap to show. 37624af1ccfSOmar Sandoval * @m: struct seq_file to write to. 37724af1ccfSOmar Sandoval * 37824af1ccfSOmar Sandoval * This is intended for debugging. The output isn't guaranteed to be internally 37924af1ccfSOmar Sandoval * consistent. 38024af1ccfSOmar Sandoval */ 38124af1ccfSOmar Sandoval void sbitmap_bitmap_show(struct sbitmap *sb, struct seq_file *m); 38224af1ccfSOmar Sandoval 38324af1ccfSOmar Sandoval /** 38488459642SOmar Sandoval * sbitmap_queue_init_node() - Initialize a &struct sbitmap_queue on a specific 38588459642SOmar Sandoval * memory node. 38688459642SOmar Sandoval * @sbq: Bitmap queue to initialize. 38788459642SOmar Sandoval * @depth: See sbitmap_init_node(). 38888459642SOmar Sandoval * @shift: See sbitmap_init_node(). 389f4a644dbSOmar Sandoval * @round_robin: See sbitmap_get(). 39088459642SOmar Sandoval * @flags: Allocation flags. 39188459642SOmar Sandoval * @node: Memory node to allocate on. 39288459642SOmar Sandoval * 39388459642SOmar Sandoval * Return: Zero on success or negative errno on failure. 39488459642SOmar Sandoval */ 39588459642SOmar Sandoval int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth, 396f4a644dbSOmar Sandoval int shift, bool round_robin, gfp_t flags, int node); 39788459642SOmar Sandoval 39888459642SOmar Sandoval /** 39988459642SOmar Sandoval * sbitmap_queue_free() - Free memory used by a &struct sbitmap_queue. 40088459642SOmar Sandoval * 40188459642SOmar Sandoval * @sbq: Bitmap queue to free. 40288459642SOmar Sandoval */ 40388459642SOmar Sandoval static inline void sbitmap_queue_free(struct sbitmap_queue *sbq) 40488459642SOmar Sandoval { 40588459642SOmar Sandoval kfree(sbq->ws); 40688459642SOmar Sandoval sbitmap_free(&sbq->sb); 40788459642SOmar Sandoval } 40888459642SOmar Sandoval 40988459642SOmar Sandoval /** 41088459642SOmar Sandoval * sbitmap_queue_resize() - Resize a &struct sbitmap_queue. 41188459642SOmar Sandoval * @sbq: Bitmap queue to resize. 41288459642SOmar Sandoval * @depth: New number of bits to resize to. 41388459642SOmar Sandoval * 41488459642SOmar Sandoval * Like sbitmap_resize(), this doesn't reallocate anything. It has to do 41588459642SOmar Sandoval * some extra work on the &struct sbitmap_queue, so it's not safe to just 41688459642SOmar Sandoval * resize the underlying &struct sbitmap. 41788459642SOmar Sandoval */ 41888459642SOmar Sandoval void sbitmap_queue_resize(struct sbitmap_queue *sbq, unsigned int depth); 41988459642SOmar Sandoval 42088459642SOmar Sandoval /** 42140aabb67SOmar Sandoval * __sbitmap_queue_get() - Try to allocate a free bit from a &struct 42240aabb67SOmar Sandoval * sbitmap_queue with preemption already disabled. 42340aabb67SOmar Sandoval * @sbq: Bitmap queue to allocate from. 42440aabb67SOmar Sandoval * 42540aabb67SOmar Sandoval * Return: Non-negative allocated bit number if successful, -1 otherwise. 42640aabb67SOmar Sandoval */ 427f4a644dbSOmar Sandoval int __sbitmap_queue_get(struct sbitmap_queue *sbq); 42840aabb67SOmar Sandoval 42940aabb67SOmar Sandoval /** 4309672b0d4SJens Axboe * __sbitmap_queue_get_batch() - Try to allocate a batch of free bits 4319672b0d4SJens Axboe * @sbq: Bitmap queue to allocate from. 4329672b0d4SJens Axboe * @nr_tags: number of tags requested 4339672b0d4SJens Axboe * @offset: offset to add to returned bits 4349672b0d4SJens Axboe * 4359672b0d4SJens Axboe * Return: Mask of allocated tags, 0 if none are found. Each tag allocated is 4369672b0d4SJens Axboe * a bit in the mask returned, and the caller must add @offset to the value to 4379672b0d4SJens Axboe * get the absolute tag value. 4389672b0d4SJens Axboe */ 4399672b0d4SJens Axboe unsigned long __sbitmap_queue_get_batch(struct sbitmap_queue *sbq, int nr_tags, 4409672b0d4SJens Axboe unsigned int *offset); 4419672b0d4SJens Axboe 4429672b0d4SJens Axboe /** 443c05e6673SOmar Sandoval * __sbitmap_queue_get_shallow() - Try to allocate a free bit from a &struct 444c05e6673SOmar Sandoval * sbitmap_queue, limiting the depth used from each word, with preemption 445c05e6673SOmar Sandoval * already disabled. 446c05e6673SOmar Sandoval * @sbq: Bitmap queue to allocate from. 447c05e6673SOmar Sandoval * @shallow_depth: The maximum number of bits to allocate from a single word. 448c05e6673SOmar Sandoval * See sbitmap_get_shallow(). 449c05e6673SOmar Sandoval * 450a3275539SOmar Sandoval * If you call this, make sure to call sbitmap_queue_min_shallow_depth() after 451a3275539SOmar Sandoval * initializing @sbq. 452a3275539SOmar Sandoval * 453c05e6673SOmar Sandoval * Return: Non-negative allocated bit number if successful, -1 otherwise. 454c05e6673SOmar Sandoval */ 455c05e6673SOmar Sandoval int __sbitmap_queue_get_shallow(struct sbitmap_queue *sbq, 456c05e6673SOmar Sandoval unsigned int shallow_depth); 457c05e6673SOmar Sandoval 458c05e6673SOmar Sandoval /** 45940aabb67SOmar Sandoval * sbitmap_queue_get() - Try to allocate a free bit from a &struct 46040aabb67SOmar Sandoval * sbitmap_queue. 46140aabb67SOmar Sandoval * @sbq: Bitmap queue to allocate from. 46240aabb67SOmar Sandoval * @cpu: Output parameter; will contain the CPU we ran on (e.g., to be passed to 46340aabb67SOmar Sandoval * sbitmap_queue_clear()). 46440aabb67SOmar Sandoval * 46540aabb67SOmar Sandoval * Return: Non-negative allocated bit number if successful, -1 otherwise. 46640aabb67SOmar Sandoval */ 467f4a644dbSOmar Sandoval static inline int sbitmap_queue_get(struct sbitmap_queue *sbq, 46840aabb67SOmar Sandoval unsigned int *cpu) 46940aabb67SOmar Sandoval { 47040aabb67SOmar Sandoval int nr; 47140aabb67SOmar Sandoval 47240aabb67SOmar Sandoval *cpu = get_cpu(); 473f4a644dbSOmar Sandoval nr = __sbitmap_queue_get(sbq); 47440aabb67SOmar Sandoval put_cpu(); 47540aabb67SOmar Sandoval return nr; 47640aabb67SOmar Sandoval } 47740aabb67SOmar Sandoval 47840aabb67SOmar Sandoval /** 479c05e6673SOmar Sandoval * sbitmap_queue_get_shallow() - Try to allocate a free bit from a &struct 480c05e6673SOmar Sandoval * sbitmap_queue, limiting the depth used from each word. 481c05e6673SOmar Sandoval * @sbq: Bitmap queue to allocate from. 482c05e6673SOmar Sandoval * @cpu: Output parameter; will contain the CPU we ran on (e.g., to be passed to 483c05e6673SOmar Sandoval * sbitmap_queue_clear()). 484c05e6673SOmar Sandoval * @shallow_depth: The maximum number of bits to allocate from a single word. 485c05e6673SOmar Sandoval * See sbitmap_get_shallow(). 486c05e6673SOmar Sandoval * 487a3275539SOmar Sandoval * If you call this, make sure to call sbitmap_queue_min_shallow_depth() after 488a3275539SOmar Sandoval * initializing @sbq. 489a3275539SOmar Sandoval * 490c05e6673SOmar Sandoval * Return: Non-negative allocated bit number if successful, -1 otherwise. 491c05e6673SOmar Sandoval */ 492c05e6673SOmar Sandoval static inline int sbitmap_queue_get_shallow(struct sbitmap_queue *sbq, 493c05e6673SOmar Sandoval unsigned int *cpu, 494c05e6673SOmar Sandoval unsigned int shallow_depth) 495c05e6673SOmar Sandoval { 496c05e6673SOmar Sandoval int nr; 497c05e6673SOmar Sandoval 498c05e6673SOmar Sandoval *cpu = get_cpu(); 499c05e6673SOmar Sandoval nr = __sbitmap_queue_get_shallow(sbq, shallow_depth); 500c05e6673SOmar Sandoval put_cpu(); 501c05e6673SOmar Sandoval return nr; 502c05e6673SOmar Sandoval } 503c05e6673SOmar Sandoval 504c05e6673SOmar Sandoval /** 505a3275539SOmar Sandoval * sbitmap_queue_min_shallow_depth() - Inform a &struct sbitmap_queue of the 506a3275539SOmar Sandoval * minimum shallow depth that will be used. 507a3275539SOmar Sandoval * @sbq: Bitmap queue in question. 508a3275539SOmar Sandoval * @min_shallow_depth: The minimum shallow depth that will be passed to 509a3275539SOmar Sandoval * sbitmap_queue_get_shallow() or __sbitmap_queue_get_shallow(). 510a3275539SOmar Sandoval * 511a3275539SOmar Sandoval * sbitmap_queue_clear() batches wakeups as an optimization. The batch size 512a3275539SOmar Sandoval * depends on the depth of the bitmap. Since the shallow allocation functions 513a3275539SOmar Sandoval * effectively operate with a different depth, the shallow depth must be taken 514a3275539SOmar Sandoval * into account when calculating the batch size. This function must be called 515a3275539SOmar Sandoval * with the minimum shallow depth that will be used. Failure to do so can result 516a3275539SOmar Sandoval * in missed wakeups. 517a3275539SOmar Sandoval */ 518a3275539SOmar Sandoval void sbitmap_queue_min_shallow_depth(struct sbitmap_queue *sbq, 519a3275539SOmar Sandoval unsigned int min_shallow_depth); 520a3275539SOmar Sandoval 521a3275539SOmar Sandoval /** 52288459642SOmar Sandoval * sbitmap_queue_clear() - Free an allocated bit and wake up waiters on a 52388459642SOmar Sandoval * &struct sbitmap_queue. 52488459642SOmar Sandoval * @sbq: Bitmap to free from. 52588459642SOmar Sandoval * @nr: Bit number to free. 52640aabb67SOmar Sandoval * @cpu: CPU the bit was allocated on. 52788459642SOmar Sandoval */ 52840aabb67SOmar Sandoval void sbitmap_queue_clear(struct sbitmap_queue *sbq, unsigned int nr, 529f4a644dbSOmar Sandoval unsigned int cpu); 53088459642SOmar Sandoval 531*1aec5e4aSJens Axboe /** 532*1aec5e4aSJens Axboe * sbitmap_queue_clear_batch() - Free a batch of allocated bits 533*1aec5e4aSJens Axboe * &struct sbitmap_queue. 534*1aec5e4aSJens Axboe * @sbq: Bitmap to free from. 535*1aec5e4aSJens Axboe * @offset: offset for each tag in array 536*1aec5e4aSJens Axboe * @tags: array of tags 537*1aec5e4aSJens Axboe * @nr_tags: number of tags in array 538*1aec5e4aSJens Axboe */ 539*1aec5e4aSJens Axboe void sbitmap_queue_clear_batch(struct sbitmap_queue *sbq, int offset, 540*1aec5e4aSJens Axboe int *tags, int nr_tags); 541*1aec5e4aSJens Axboe 54288459642SOmar Sandoval static inline int sbq_index_inc(int index) 54388459642SOmar Sandoval { 54488459642SOmar Sandoval return (index + 1) & (SBQ_WAIT_QUEUES - 1); 54588459642SOmar Sandoval } 54688459642SOmar Sandoval 54788459642SOmar Sandoval static inline void sbq_index_atomic_inc(atomic_t *index) 54888459642SOmar Sandoval { 54988459642SOmar Sandoval int old = atomic_read(index); 55088459642SOmar Sandoval int new = sbq_index_inc(old); 55188459642SOmar Sandoval atomic_cmpxchg(index, old, new); 55288459642SOmar Sandoval } 55388459642SOmar Sandoval 55488459642SOmar Sandoval /** 55588459642SOmar Sandoval * sbq_wait_ptr() - Get the next wait queue to use for a &struct 55688459642SOmar Sandoval * sbitmap_queue. 55788459642SOmar Sandoval * @sbq: Bitmap queue to wait on. 55888459642SOmar Sandoval * @wait_index: A counter per "user" of @sbq. 55988459642SOmar Sandoval */ 56088459642SOmar Sandoval static inline struct sbq_wait_state *sbq_wait_ptr(struct sbitmap_queue *sbq, 56188459642SOmar Sandoval atomic_t *wait_index) 56288459642SOmar Sandoval { 56388459642SOmar Sandoval struct sbq_wait_state *ws; 56488459642SOmar Sandoval 56588459642SOmar Sandoval ws = &sbq->ws[atomic_read(wait_index)]; 56688459642SOmar Sandoval sbq_index_atomic_inc(wait_index); 56788459642SOmar Sandoval return ws; 56888459642SOmar Sandoval } 56988459642SOmar Sandoval 57088459642SOmar Sandoval /** 57188459642SOmar Sandoval * sbitmap_queue_wake_all() - Wake up everything waiting on a &struct 57288459642SOmar Sandoval * sbitmap_queue. 57388459642SOmar Sandoval * @sbq: Bitmap queue to wake up. 57488459642SOmar Sandoval */ 57588459642SOmar Sandoval void sbitmap_queue_wake_all(struct sbitmap_queue *sbq); 57688459642SOmar Sandoval 57724af1ccfSOmar Sandoval /** 578e6fc4649SMing Lei * sbitmap_queue_wake_up() - Wake up some of waiters in one waitqueue 579e6fc4649SMing Lei * on a &struct sbitmap_queue. 580e6fc4649SMing Lei * @sbq: Bitmap queue to wake up. 581e6fc4649SMing Lei */ 582e6fc4649SMing Lei void sbitmap_queue_wake_up(struct sbitmap_queue *sbq); 583e6fc4649SMing Lei 584e6fc4649SMing Lei /** 58524af1ccfSOmar Sandoval * sbitmap_queue_show() - Dump &struct sbitmap_queue information to a &struct 58624af1ccfSOmar Sandoval * seq_file. 58724af1ccfSOmar Sandoval * @sbq: Bitmap queue to show. 58824af1ccfSOmar Sandoval * @m: struct seq_file to write to. 58924af1ccfSOmar Sandoval * 59024af1ccfSOmar Sandoval * This is intended for debugging. The format may change at any time. 59124af1ccfSOmar Sandoval */ 59224af1ccfSOmar Sandoval void sbitmap_queue_show(struct sbitmap_queue *sbq, struct seq_file *m); 59324af1ccfSOmar Sandoval 5945d2ee712SJens Axboe struct sbq_wait { 5959f6b7ef6SJens Axboe struct sbitmap_queue *sbq; /* if set, sbq_wait is accounted */ 5965d2ee712SJens Axboe struct wait_queue_entry wait; 5975d2ee712SJens Axboe }; 5985d2ee712SJens Axboe 5995d2ee712SJens Axboe #define DEFINE_SBQ_WAIT(name) \ 6005d2ee712SJens Axboe struct sbq_wait name = { \ 6019f6b7ef6SJens Axboe .sbq = NULL, \ 6025d2ee712SJens Axboe .wait = { \ 6035d2ee712SJens Axboe .private = current, \ 6045d2ee712SJens Axboe .func = autoremove_wake_function, \ 6055d2ee712SJens Axboe .entry = LIST_HEAD_INIT((name).wait.entry), \ 6065d2ee712SJens Axboe } \ 6075d2ee712SJens Axboe } 6085d2ee712SJens Axboe 6095d2ee712SJens Axboe /* 6105d2ee712SJens Axboe * Wrapper around prepare_to_wait_exclusive(), which maintains some extra 6115d2ee712SJens Axboe * internal state. 6125d2ee712SJens Axboe */ 6135d2ee712SJens Axboe void sbitmap_prepare_to_wait(struct sbitmap_queue *sbq, 6145d2ee712SJens Axboe struct sbq_wait_state *ws, 6155d2ee712SJens Axboe struct sbq_wait *sbq_wait, int state); 6165d2ee712SJens Axboe 6175d2ee712SJens Axboe /* 6185d2ee712SJens Axboe * Must be paired with sbitmap_prepare_to_wait(). 6195d2ee712SJens Axboe */ 6205d2ee712SJens Axboe void sbitmap_finish_wait(struct sbitmap_queue *sbq, struct sbq_wait_state *ws, 6215d2ee712SJens Axboe struct sbq_wait *sbq_wait); 6225d2ee712SJens Axboe 6239f6b7ef6SJens Axboe /* 6249f6b7ef6SJens Axboe * Wrapper around add_wait_queue(), which maintains some extra internal state 6259f6b7ef6SJens Axboe */ 6269f6b7ef6SJens Axboe void sbitmap_add_wait_queue(struct sbitmap_queue *sbq, 6279f6b7ef6SJens Axboe struct sbq_wait_state *ws, 6289f6b7ef6SJens Axboe struct sbq_wait *sbq_wait); 6299f6b7ef6SJens Axboe 6309f6b7ef6SJens Axboe /* 6319f6b7ef6SJens Axboe * Must be paired with sbitmap_add_wait_queue() 6329f6b7ef6SJens Axboe */ 6339f6b7ef6SJens Axboe void sbitmap_del_wait_queue(struct sbq_wait *sbq_wait); 6349f6b7ef6SJens Axboe 63588459642SOmar Sandoval #endif /* __LINUX_SCALE_BITMAP_H */ 636