188459642SOmar Sandoval /* 288459642SOmar Sandoval * Fast and scalable bitmaps. 388459642SOmar Sandoval * 488459642SOmar Sandoval * Copyright (C) 2016 Facebook 588459642SOmar Sandoval * Copyright (C) 2013-2014 Jens Axboe 688459642SOmar Sandoval * 788459642SOmar Sandoval * This program is free software; you can redistribute it and/or 888459642SOmar Sandoval * modify it under the terms of the GNU General Public 988459642SOmar Sandoval * License v2 as published by the Free Software Foundation. 1088459642SOmar Sandoval * 1188459642SOmar Sandoval * This program is distributed in the hope that it will be useful, 1288459642SOmar Sandoval * but WITHOUT ANY WARRANTY; without even the implied warranty of 1388459642SOmar Sandoval * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1488459642SOmar Sandoval * General Public License for more details. 1588459642SOmar Sandoval * 1688459642SOmar Sandoval * You should have received a copy of the GNU General Public License 1788459642SOmar Sandoval * along with this program. If not, see <https://www.gnu.org/licenses/>. 1888459642SOmar Sandoval */ 1988459642SOmar Sandoval 2088459642SOmar Sandoval #ifndef __LINUX_SCALE_BITMAP_H 2188459642SOmar Sandoval #define __LINUX_SCALE_BITMAP_H 2288459642SOmar Sandoval 2388459642SOmar Sandoval #include <linux/kernel.h> 2488459642SOmar Sandoval #include <linux/slab.h> 2588459642SOmar Sandoval 2688459642SOmar Sandoval /** 2788459642SOmar Sandoval * struct sbitmap_word - Word in a &struct sbitmap. 2888459642SOmar Sandoval */ 2988459642SOmar Sandoval struct sbitmap_word { 3088459642SOmar Sandoval /** 3188459642SOmar Sandoval * @word: The bitmap word itself. 3288459642SOmar Sandoval */ 3388459642SOmar Sandoval unsigned long word; 3488459642SOmar Sandoval 3588459642SOmar Sandoval /** 3688459642SOmar Sandoval * @depth: Number of bits being used in @word. 3788459642SOmar Sandoval */ 3888459642SOmar Sandoval unsigned long depth; 3988459642SOmar Sandoval } ____cacheline_aligned_in_smp; 4088459642SOmar Sandoval 4188459642SOmar Sandoval /** 4288459642SOmar Sandoval * struct sbitmap - Scalable bitmap. 4388459642SOmar Sandoval * 4488459642SOmar Sandoval * A &struct sbitmap is spread over multiple cachelines to avoid ping-pong. This 4588459642SOmar Sandoval * trades off higher memory usage for better scalability. 4688459642SOmar Sandoval */ 4788459642SOmar Sandoval struct sbitmap { 4888459642SOmar Sandoval /** 4988459642SOmar Sandoval * @depth: Number of bits used in the whole bitmap. 5088459642SOmar Sandoval */ 5188459642SOmar Sandoval unsigned int depth; 5288459642SOmar Sandoval 5388459642SOmar Sandoval /** 5488459642SOmar Sandoval * @shift: log2(number of bits used per word) 5588459642SOmar Sandoval */ 5688459642SOmar Sandoval unsigned int shift; 5788459642SOmar Sandoval 5888459642SOmar Sandoval /** 5988459642SOmar Sandoval * @map_nr: Number of words (cachelines) being used for the bitmap. 6088459642SOmar Sandoval */ 6188459642SOmar Sandoval unsigned int map_nr; 6288459642SOmar Sandoval 6388459642SOmar Sandoval /** 6488459642SOmar Sandoval * @map: Allocated bitmap. 6588459642SOmar Sandoval */ 6688459642SOmar Sandoval struct sbitmap_word *map; 6788459642SOmar Sandoval }; 6888459642SOmar Sandoval 6988459642SOmar Sandoval #define SBQ_WAIT_QUEUES 8 7088459642SOmar Sandoval #define SBQ_WAKE_BATCH 8 7188459642SOmar Sandoval 7288459642SOmar Sandoval /** 7388459642SOmar Sandoval * struct sbq_wait_state - Wait queue in a &struct sbitmap_queue. 7488459642SOmar Sandoval */ 7588459642SOmar Sandoval struct sbq_wait_state { 7688459642SOmar Sandoval /** 7788459642SOmar Sandoval * @wait_cnt: Number of frees remaining before we wake up. 7888459642SOmar Sandoval */ 7988459642SOmar Sandoval atomic_t wait_cnt; 8088459642SOmar Sandoval 8188459642SOmar Sandoval /** 8288459642SOmar Sandoval * @wait: Wait queue. 8388459642SOmar Sandoval */ 8488459642SOmar Sandoval wait_queue_head_t wait; 8588459642SOmar Sandoval } ____cacheline_aligned_in_smp; 8688459642SOmar Sandoval 8788459642SOmar Sandoval /** 8888459642SOmar Sandoval * struct sbitmap_queue - Scalable bitmap with the added ability to wait on free 8988459642SOmar Sandoval * bits. 9088459642SOmar Sandoval * 9188459642SOmar Sandoval * A &struct sbitmap_queue uses multiple wait queues and rolling wakeups to 9288459642SOmar Sandoval * avoid contention on the wait queue spinlock. This ensures that we don't hit a 9388459642SOmar Sandoval * scalability wall when we run out of free bits and have to start putting tasks 9488459642SOmar Sandoval * to sleep. 9588459642SOmar Sandoval */ 9688459642SOmar Sandoval struct sbitmap_queue { 9788459642SOmar Sandoval /** 9888459642SOmar Sandoval * @sb: Scalable bitmap. 9988459642SOmar Sandoval */ 10088459642SOmar Sandoval struct sbitmap sb; 10188459642SOmar Sandoval 10240aabb67SOmar Sandoval /* 10340aabb67SOmar Sandoval * @alloc_hint: Cache of last successfully allocated or freed bit. 10440aabb67SOmar Sandoval * 10540aabb67SOmar Sandoval * This is per-cpu, which allows multiple users to stick to different 10640aabb67SOmar Sandoval * cachelines until the map is exhausted. 10740aabb67SOmar Sandoval */ 10840aabb67SOmar Sandoval unsigned int __percpu *alloc_hint; 10940aabb67SOmar Sandoval 11088459642SOmar Sandoval /** 11188459642SOmar Sandoval * @wake_batch: Number of bits which must be freed before we wake up any 11288459642SOmar Sandoval * waiters. 11388459642SOmar Sandoval */ 11488459642SOmar Sandoval unsigned int wake_batch; 11588459642SOmar Sandoval 11688459642SOmar Sandoval /** 11788459642SOmar Sandoval * @wake_index: Next wait queue in @ws to wake up. 11888459642SOmar Sandoval */ 11988459642SOmar Sandoval atomic_t wake_index; 12088459642SOmar Sandoval 12188459642SOmar Sandoval /** 12288459642SOmar Sandoval * @ws: Wait queues. 12388459642SOmar Sandoval */ 12488459642SOmar Sandoval struct sbq_wait_state *ws; 12588459642SOmar Sandoval }; 12688459642SOmar Sandoval 12788459642SOmar Sandoval /** 12888459642SOmar Sandoval * sbitmap_init_node() - Initialize a &struct sbitmap on a specific memory node. 12988459642SOmar Sandoval * @sb: Bitmap to initialize. 13088459642SOmar Sandoval * @depth: Number of bits to allocate. 13188459642SOmar Sandoval * @shift: Use 2^@shift bits per word in the bitmap; if a negative number if 13288459642SOmar Sandoval * given, a good default is chosen. 13388459642SOmar Sandoval * @flags: Allocation flags. 13488459642SOmar Sandoval * @node: Memory node to allocate on. 13588459642SOmar Sandoval * 13688459642SOmar Sandoval * Return: Zero on success or negative errno on failure. 13788459642SOmar Sandoval */ 13888459642SOmar Sandoval int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift, 13988459642SOmar Sandoval gfp_t flags, int node); 14088459642SOmar Sandoval 14188459642SOmar Sandoval /** 14288459642SOmar Sandoval * sbitmap_free() - Free memory used by a &struct sbitmap. 14388459642SOmar Sandoval * @sb: Bitmap to free. 14488459642SOmar Sandoval */ 14588459642SOmar Sandoval static inline void sbitmap_free(struct sbitmap *sb) 14688459642SOmar Sandoval { 14788459642SOmar Sandoval kfree(sb->map); 14888459642SOmar Sandoval sb->map = NULL; 14988459642SOmar Sandoval } 15088459642SOmar Sandoval 15188459642SOmar Sandoval /** 15288459642SOmar Sandoval * sbitmap_resize() - Resize a &struct sbitmap. 15388459642SOmar Sandoval * @sb: Bitmap to resize. 15488459642SOmar Sandoval * @depth: New number of bits to resize to. 15588459642SOmar Sandoval * 15688459642SOmar Sandoval * Doesn't reallocate anything. It's up to the caller to ensure that the new 15788459642SOmar Sandoval * depth doesn't exceed the depth that the sb was initialized with. 15888459642SOmar Sandoval */ 15988459642SOmar Sandoval void sbitmap_resize(struct sbitmap *sb, unsigned int depth); 16088459642SOmar Sandoval 16188459642SOmar Sandoval /** 16288459642SOmar Sandoval * sbitmap_get() - Try to allocate a free bit from a &struct sbitmap. 16388459642SOmar Sandoval * @sb: Bitmap to allocate from. 16488459642SOmar Sandoval * @alloc_hint: Hint for where to start searching for a free bit. 16588459642SOmar Sandoval * @round_robin: If true, be stricter about allocation order; always allocate 16688459642SOmar Sandoval * starting from the last allocated bit. This is less efficient 16788459642SOmar Sandoval * than the default behavior (false). 16888459642SOmar Sandoval * 16988459642SOmar Sandoval * Return: Non-negative allocated bit number if successful, -1 otherwise. 17088459642SOmar Sandoval */ 17188459642SOmar Sandoval int sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint, bool round_robin); 17288459642SOmar Sandoval 17388459642SOmar Sandoval /** 17488459642SOmar Sandoval * sbitmap_any_bit_set() - Check for a set bit in a &struct sbitmap. 17588459642SOmar Sandoval * @sb: Bitmap to check. 17688459642SOmar Sandoval * 17788459642SOmar Sandoval * Return: true if any bit in the bitmap is set, false otherwise. 17888459642SOmar Sandoval */ 17988459642SOmar Sandoval bool sbitmap_any_bit_set(const struct sbitmap *sb); 18088459642SOmar Sandoval 18188459642SOmar Sandoval /** 18288459642SOmar Sandoval * sbitmap_any_bit_clear() - Check for an unset bit in a &struct 18388459642SOmar Sandoval * sbitmap. 18488459642SOmar Sandoval * @sb: Bitmap to check. 18588459642SOmar Sandoval * 18688459642SOmar Sandoval * Return: true if any bit in the bitmap is clear, false otherwise. 18788459642SOmar Sandoval */ 18888459642SOmar Sandoval bool sbitmap_any_bit_clear(const struct sbitmap *sb); 18988459642SOmar Sandoval 19088459642SOmar Sandoval typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *); 19188459642SOmar Sandoval 19288459642SOmar Sandoval /** 19388459642SOmar Sandoval * sbitmap_for_each_set() - Iterate over each set bit in a &struct sbitmap. 19488459642SOmar Sandoval * @sb: Bitmap to iterate over. 19588459642SOmar Sandoval * @fn: Callback. Should return true to continue or false to break early. 19688459642SOmar Sandoval * @data: Pointer to pass to callback. 19788459642SOmar Sandoval * 19888459642SOmar Sandoval * This is inline even though it's non-trivial so that the function calls to the 19988459642SOmar Sandoval * callback will hopefully get optimized away. 20088459642SOmar Sandoval */ 20188459642SOmar Sandoval static inline void sbitmap_for_each_set(struct sbitmap *sb, sb_for_each_fn fn, 20288459642SOmar Sandoval void *data) 20388459642SOmar Sandoval { 20488459642SOmar Sandoval unsigned int i; 20588459642SOmar Sandoval 20688459642SOmar Sandoval for (i = 0; i < sb->map_nr; i++) { 20788459642SOmar Sandoval struct sbitmap_word *word = &sb->map[i]; 20888459642SOmar Sandoval unsigned int off, nr; 20988459642SOmar Sandoval 21088459642SOmar Sandoval if (!word->word) 21188459642SOmar Sandoval continue; 21288459642SOmar Sandoval 21388459642SOmar Sandoval nr = 0; 21488459642SOmar Sandoval off = i << sb->shift; 21588459642SOmar Sandoval while (1) { 21688459642SOmar Sandoval nr = find_next_bit(&word->word, word->depth, nr); 21788459642SOmar Sandoval if (nr >= word->depth) 21888459642SOmar Sandoval break; 21988459642SOmar Sandoval 22088459642SOmar Sandoval if (!fn(sb, off + nr, data)) 22188459642SOmar Sandoval return; 22288459642SOmar Sandoval 22388459642SOmar Sandoval nr++; 22488459642SOmar Sandoval } 22588459642SOmar Sandoval } 22688459642SOmar Sandoval } 22788459642SOmar Sandoval 22888459642SOmar Sandoval #define SB_NR_TO_INDEX(sb, bitnr) ((bitnr) >> (sb)->shift) 22988459642SOmar Sandoval #define SB_NR_TO_BIT(sb, bitnr) ((bitnr) & ((1U << (sb)->shift) - 1U)) 23088459642SOmar Sandoval 23188459642SOmar Sandoval static inline unsigned long *__sbitmap_word(struct sbitmap *sb, 23288459642SOmar Sandoval unsigned int bitnr) 23388459642SOmar Sandoval { 23488459642SOmar Sandoval return &sb->map[SB_NR_TO_INDEX(sb, bitnr)].word; 23588459642SOmar Sandoval } 23688459642SOmar Sandoval 23788459642SOmar Sandoval /* Helpers equivalent to the operations in asm/bitops.h and linux/bitmap.h */ 23888459642SOmar Sandoval 23988459642SOmar Sandoval static inline void sbitmap_set_bit(struct sbitmap *sb, unsigned int bitnr) 24088459642SOmar Sandoval { 24188459642SOmar Sandoval set_bit(SB_NR_TO_BIT(sb, bitnr), __sbitmap_word(sb, bitnr)); 24288459642SOmar Sandoval } 24388459642SOmar Sandoval 24488459642SOmar Sandoval static inline void sbitmap_clear_bit(struct sbitmap *sb, unsigned int bitnr) 24588459642SOmar Sandoval { 24688459642SOmar Sandoval clear_bit(SB_NR_TO_BIT(sb, bitnr), __sbitmap_word(sb, bitnr)); 24788459642SOmar Sandoval } 24888459642SOmar Sandoval 24988459642SOmar Sandoval static inline int sbitmap_test_bit(struct sbitmap *sb, unsigned int bitnr) 25088459642SOmar Sandoval { 25188459642SOmar Sandoval return test_bit(SB_NR_TO_BIT(sb, bitnr), __sbitmap_word(sb, bitnr)); 25288459642SOmar Sandoval } 25388459642SOmar Sandoval 25488459642SOmar Sandoval unsigned int sbitmap_weight(const struct sbitmap *sb); 25588459642SOmar Sandoval 25688459642SOmar Sandoval /** 25788459642SOmar Sandoval * sbitmap_queue_init_node() - Initialize a &struct sbitmap_queue on a specific 25888459642SOmar Sandoval * memory node. 25988459642SOmar Sandoval * @sbq: Bitmap queue to initialize. 26088459642SOmar Sandoval * @depth: See sbitmap_init_node(). 26188459642SOmar Sandoval * @shift: See sbitmap_init_node(). 26288459642SOmar Sandoval * @flags: Allocation flags. 26388459642SOmar Sandoval * @node: Memory node to allocate on. 26488459642SOmar Sandoval * 26588459642SOmar Sandoval * Return: Zero on success or negative errno on failure. 26688459642SOmar Sandoval */ 26788459642SOmar Sandoval int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth, 26888459642SOmar Sandoval int shift, gfp_t flags, int node); 26988459642SOmar Sandoval 27088459642SOmar Sandoval /** 27188459642SOmar Sandoval * sbitmap_queue_free() - Free memory used by a &struct sbitmap_queue. 27288459642SOmar Sandoval * 27388459642SOmar Sandoval * @sbq: Bitmap queue to free. 27488459642SOmar Sandoval */ 27588459642SOmar Sandoval static inline void sbitmap_queue_free(struct sbitmap_queue *sbq) 27688459642SOmar Sandoval { 27788459642SOmar Sandoval kfree(sbq->ws); 27840aabb67SOmar Sandoval free_percpu(sbq->alloc_hint); 27988459642SOmar Sandoval sbitmap_free(&sbq->sb); 28088459642SOmar Sandoval } 28188459642SOmar Sandoval 28288459642SOmar Sandoval /** 28388459642SOmar Sandoval * sbitmap_queue_resize() - Resize a &struct sbitmap_queue. 28488459642SOmar Sandoval * @sbq: Bitmap queue to resize. 28588459642SOmar Sandoval * @depth: New number of bits to resize to. 28688459642SOmar Sandoval * 28788459642SOmar Sandoval * Like sbitmap_resize(), this doesn't reallocate anything. It has to do 28888459642SOmar Sandoval * some extra work on the &struct sbitmap_queue, so it's not safe to just 28988459642SOmar Sandoval * resize the underlying &struct sbitmap. 29088459642SOmar Sandoval */ 29188459642SOmar Sandoval void sbitmap_queue_resize(struct sbitmap_queue *sbq, unsigned int depth); 29288459642SOmar Sandoval 29388459642SOmar Sandoval /** 29440aabb67SOmar Sandoval * __sbitmap_queue_get() - Try to allocate a free bit from a &struct 29540aabb67SOmar Sandoval * sbitmap_queue with preemption already disabled. 29640aabb67SOmar Sandoval * @sbq: Bitmap queue to allocate from. 29740aabb67SOmar Sandoval * @round_robin: See sbitmap_get(). 29840aabb67SOmar Sandoval * 29940aabb67SOmar Sandoval * Return: Non-negative allocated bit number if successful, -1 otherwise. 30040aabb67SOmar Sandoval */ 30140aabb67SOmar Sandoval int __sbitmap_queue_get(struct sbitmap_queue *sbq, bool round_robin); 30240aabb67SOmar Sandoval 30340aabb67SOmar Sandoval /** 30440aabb67SOmar Sandoval * sbitmap_queue_get() - Try to allocate a free bit from a &struct 30540aabb67SOmar Sandoval * sbitmap_queue. 30640aabb67SOmar Sandoval * @sbq: Bitmap queue to allocate from. 30740aabb67SOmar Sandoval * @round_robin: See sbitmap_get(). 30840aabb67SOmar Sandoval * @cpu: Output parameter; will contain the CPU we ran on (e.g., to be passed to 30940aabb67SOmar Sandoval * sbitmap_queue_clear()). 31040aabb67SOmar Sandoval * 31140aabb67SOmar Sandoval * Return: Non-negative allocated bit number if successful, -1 otherwise. 31240aabb67SOmar Sandoval */ 31340aabb67SOmar Sandoval static inline int sbitmap_queue_get(struct sbitmap_queue *sbq, bool round_robin, 31440aabb67SOmar Sandoval unsigned int *cpu) 31540aabb67SOmar Sandoval { 31640aabb67SOmar Sandoval int nr; 31740aabb67SOmar Sandoval 31840aabb67SOmar Sandoval *cpu = get_cpu(); 31940aabb67SOmar Sandoval nr = __sbitmap_queue_get(sbq, round_robin); 32040aabb67SOmar Sandoval put_cpu(); 32140aabb67SOmar Sandoval return nr; 32240aabb67SOmar Sandoval } 32340aabb67SOmar Sandoval 32440aabb67SOmar Sandoval /** 32588459642SOmar Sandoval * sbitmap_queue_clear() - Free an allocated bit and wake up waiters on a 32688459642SOmar Sandoval * &struct sbitmap_queue. 32788459642SOmar Sandoval * @sbq: Bitmap to free from. 32888459642SOmar Sandoval * @nr: Bit number to free. 32940aabb67SOmar Sandoval * @round_robin: See sbitmap_get(). 33040aabb67SOmar Sandoval * @cpu: CPU the bit was allocated on. 33188459642SOmar Sandoval */ 33240aabb67SOmar Sandoval void sbitmap_queue_clear(struct sbitmap_queue *sbq, unsigned int nr, 33340aabb67SOmar Sandoval bool round_robin, unsigned int cpu); 33488459642SOmar Sandoval 33588459642SOmar Sandoval static inline int sbq_index_inc(int index) 33688459642SOmar Sandoval { 33788459642SOmar Sandoval return (index + 1) & (SBQ_WAIT_QUEUES - 1); 33888459642SOmar Sandoval } 33988459642SOmar Sandoval 34088459642SOmar Sandoval static inline void sbq_index_atomic_inc(atomic_t *index) 34188459642SOmar Sandoval { 34288459642SOmar Sandoval int old = atomic_read(index); 34388459642SOmar Sandoval int new = sbq_index_inc(old); 34488459642SOmar Sandoval atomic_cmpxchg(index, old, new); 34588459642SOmar Sandoval } 34688459642SOmar Sandoval 34788459642SOmar Sandoval /** 34888459642SOmar Sandoval * sbq_wait_ptr() - Get the next wait queue to use for a &struct 34988459642SOmar Sandoval * sbitmap_queue. 35088459642SOmar Sandoval * @sbq: Bitmap queue to wait on. 35188459642SOmar Sandoval * @wait_index: A counter per "user" of @sbq. 35288459642SOmar Sandoval */ 35388459642SOmar Sandoval static inline struct sbq_wait_state *sbq_wait_ptr(struct sbitmap_queue *sbq, 35488459642SOmar Sandoval atomic_t *wait_index) 35588459642SOmar Sandoval { 35688459642SOmar Sandoval struct sbq_wait_state *ws; 35788459642SOmar Sandoval 35888459642SOmar Sandoval ws = &sbq->ws[atomic_read(wait_index)]; 35988459642SOmar Sandoval sbq_index_atomic_inc(wait_index); 36088459642SOmar Sandoval return ws; 36188459642SOmar Sandoval } 36288459642SOmar Sandoval 36388459642SOmar Sandoval /** 36488459642SOmar Sandoval * sbitmap_queue_wake_all() - Wake up everything waiting on a &struct 36588459642SOmar Sandoval * sbitmap_queue. 36688459642SOmar Sandoval * @sbq: Bitmap queue to wake up. 36788459642SOmar Sandoval */ 36888459642SOmar Sandoval void sbitmap_queue_wake_all(struct sbitmap_queue *sbq); 36988459642SOmar Sandoval 37088459642SOmar Sandoval #endif /* __LINUX_SCALE_BITMAP_H */ 371