~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/include/linux/sbitmap.h

Version: ~ [ linux-5.19-rc3 ] ~ [ linux-5.18.5 ] ~ [ linux-5.17.15 ] ~ [ linux-5.16.20 ] ~ [ linux-5.15.48 ] ~ [ linux-5.14.21 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.123 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.199 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.248 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.284 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.319 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.302 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.9 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /*
  2  * Fast and scalable bitmaps.
  3  *
  4  * Copyright (C) 2016 Facebook
  5  * Copyright (C) 2013-2014 Jens Axboe
  6  *
  7  * This program is free software; you can redistribute it and/or
  8  * modify it under the terms of the GNU General Public
  9  * License v2 as published by the Free Software Foundation.
 10  *
 11  * This program is distributed in the hope that it will be useful,
 12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
 13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 14  * General Public License for more details.
 15  *
 16  * You should have received a copy of the GNU General Public License
 17  * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 18  */
 19 
 20 #ifndef __LINUX_SCALE_BITMAP_H
 21 #define __LINUX_SCALE_BITMAP_H
 22 
 23 #include <linux/kernel.h>
 24 #include <linux/slab.h>
 25 
 26 /**
 27  * struct sbitmap_word - Word in a &struct sbitmap.
 28  */
 29 struct sbitmap_word {
 30         /**
 31          * @word: The bitmap word itself.
 32          */
 33         unsigned long word;
 34 
 35         /**
 36          * @depth: Number of bits being used in @word.
 37          */
 38         unsigned long depth;
 39 } ____cacheline_aligned_in_smp;
 40 
 41 /**
 42  * struct sbitmap - Scalable bitmap.
 43  *
 44  * A &struct sbitmap is spread over multiple cachelines to avoid ping-pong. This
 45  * trades off higher memory usage for better scalability.
 46  */
 47 struct sbitmap {
 48         /**
 49          * @depth: Number of bits used in the whole bitmap.
 50          */
 51         unsigned int depth;
 52 
 53         /**
 54          * @shift: log2(number of bits used per word)
 55          */
 56         unsigned int shift;
 57 
 58         /**
 59          * @map_nr: Number of words (cachelines) being used for the bitmap.
 60          */
 61         unsigned int map_nr;
 62 
 63         /**
 64          * @map: Allocated bitmap.
 65          */
 66         struct sbitmap_word *map;
 67 };
 68 
 69 #define SBQ_WAIT_QUEUES 8
 70 #define SBQ_WAKE_BATCH 8
 71 
 72 /**
 73  * struct sbq_wait_state - Wait queue in a &struct sbitmap_queue.
 74  */
 75 struct sbq_wait_state {
 76         /**
 77          * @wait_cnt: Number of frees remaining before we wake up.
 78          */
 79         atomic_t wait_cnt;
 80 
 81         /**
 82          * @wait: Wait queue.
 83          */
 84         wait_queue_head_t wait;
 85 } ____cacheline_aligned_in_smp;
 86 
 87 /**
 88  * struct sbitmap_queue - Scalable bitmap with the added ability to wait on free
 89  * bits.
 90  *
 91  * A &struct sbitmap_queue uses multiple wait queues and rolling wakeups to
 92  * avoid contention on the wait queue spinlock. This ensures that we don't hit a
 93  * scalability wall when we run out of free bits and have to start putting tasks
 94  * to sleep.
 95  */
 96 struct sbitmap_queue {
 97         /**
 98          * @sb: Scalable bitmap.
 99          */
100         struct sbitmap sb;
101 
102         /*
103          * @alloc_hint: Cache of last successfully allocated or freed bit.
104          *
105          * This is per-cpu, which allows multiple users to stick to different
106          * cachelines until the map is exhausted.
107          */
108         unsigned int __percpu *alloc_hint;
109 
110         /**
111          * @wake_batch: Number of bits which must be freed before we wake up any
112          * waiters.
113          */
114         unsigned int wake_batch;
115 
116         /**
117          * @wake_index: Next wait queue in @ws to wake up.
118          */
119         atomic_t wake_index;
120 
121         /**
122          * @ws: Wait queues.
123          */
124         struct sbq_wait_state *ws;
125 
126         /**
127          * @round_robin: Allocate bits in strict round-robin order.
128          */
129         bool round_robin;
130 };
131 
132 /**
133  * sbitmap_init_node() - Initialize a &struct sbitmap on a specific memory node.
134  * @sb: Bitmap to initialize.
135  * @depth: Number of bits to allocate.
136  * @shift: Use 2^@shift bits per word in the bitmap; if a negative number if
137  *         given, a good default is chosen.
138  * @flags: Allocation flags.
139  * @node: Memory node to allocate on.
140  *
141  * Return: Zero on success or negative errno on failure.
142  */
143 int sbitmap_init_node(struct sbitmap *sb, unsigned int depth, int shift,
144                       gfp_t flags, int node);
145 
146 /**
147  * sbitmap_free() - Free memory used by a &struct sbitmap.
148  * @sb: Bitmap to free.
149  */
150 static inline void sbitmap_free(struct sbitmap *sb)
151 {
152         kfree(sb->map);
153         sb->map = NULL;
154 }
155 
156 /**
157  * sbitmap_resize() - Resize a &struct sbitmap.
158  * @sb: Bitmap to resize.
159  * @depth: New number of bits to resize to.
160  *
161  * Doesn't reallocate anything. It's up to the caller to ensure that the new
162  * depth doesn't exceed the depth that the sb was initialized with.
163  */
164 void sbitmap_resize(struct sbitmap *sb, unsigned int depth);
165 
166 /**
167  * sbitmap_get() - Try to allocate a free bit from a &struct sbitmap.
168  * @sb: Bitmap to allocate from.
169  * @alloc_hint: Hint for where to start searching for a free bit.
170  * @round_robin: If true, be stricter about allocation order; always allocate
171  *               starting from the last allocated bit. This is less efficient
172  *               than the default behavior (false).
173  *
174  * Return: Non-negative allocated bit number if successful, -1 otherwise.
175  */
176 int sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint, bool round_robin);
177 
178 /**
179  * sbitmap_get_shallow() - Try to allocate a free bit from a &struct sbitmap,
180  * limiting the depth used from each word.
181  * @sb: Bitmap to allocate from.
182  * @alloc_hint: Hint for where to start searching for a free bit.
183  * @shallow_depth: The maximum number of bits to allocate from a single word.
184  *
185  * This rather specific operation allows for having multiple users with
186  * different allocation limits. E.g., there can be a high-priority class that
187  * uses sbitmap_get() and a low-priority class that uses sbitmap_get_shallow()
188  * with a @shallow_depth of (1 << (@sb->shift - 1)). Then, the low-priority
189  * class can only allocate half of the total bits in the bitmap, preventing it
190  * from starving out the high-priority class.
191  *
192  * Return: Non-negative allocated bit number if successful, -1 otherwise.
193  */
194 int sbitmap_get_shallow(struct sbitmap *sb, unsigned int alloc_hint,
195                         unsigned long shallow_depth);
196 
197 /**
198  * sbitmap_any_bit_set() - Check for a set bit in a &struct sbitmap.
199  * @sb: Bitmap to check.
200  *
201  * Return: true if any bit in the bitmap is set, false otherwise.
202  */
203 bool sbitmap_any_bit_set(const struct sbitmap *sb);
204 
205 /**
206  * sbitmap_any_bit_clear() - Check for an unset bit in a &struct
207  * sbitmap.
208  * @sb: Bitmap to check.
209  *
210  * Return: true if any bit in the bitmap is clear, false otherwise.
211  */
212 bool sbitmap_any_bit_clear(const struct sbitmap *sb);
213 
214 typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *);
215 
216 /**
217  * sbitmap_for_each_set() - Iterate over each set bit in a &struct sbitmap.
218  * @sb: Bitmap to iterate over.
219  * @fn: Callback. Should return true to continue or false to break early.
220  * @data: Pointer to pass to callback.
221  *
222  * This is inline even though it's non-trivial so that the function calls to the
223  * callback will hopefully get optimized away.
224  */
225 static inline void sbitmap_for_each_set(struct sbitmap *sb, sb_for_each_fn fn,
226                                         void *data)
227 {
228         unsigned int i;
229 
230         for (i = 0; i < sb->map_nr; i++) {
231                 struct sbitmap_word *word = &sb->map[i];
232                 unsigned int off, nr;
233 
234                 if (!word->word)
235                         continue;
236 
237                 nr = 0;
238                 off = i << sb->shift;
239                 while (1) {
240                         nr = find_next_bit(&word->word, word->depth, nr);
241                         if (nr >= word->depth)
242                                 break;
243 
244                         if (!fn(sb, off + nr, data))
245                                 return;
246 
247                         nr++;
248                 }
249         }
250 }
251 
252 #define SB_NR_TO_INDEX(sb, bitnr) ((bitnr) >> (sb)->shift)
253 #define SB_NR_TO_BIT(sb, bitnr) ((bitnr) & ((1U << (sb)->shift) - 1U))
254 
255 static inline unsigned long *__sbitmap_word(struct sbitmap *sb,
256                                             unsigned int bitnr)
257 {
258         return &sb->map[SB_NR_TO_INDEX(sb, bitnr)].word;
259 }
260 
261 /* Helpers equivalent to the operations in asm/bitops.h and linux/bitmap.h */
262 
263 static inline void sbitmap_set_bit(struct sbitmap *sb, unsigned int bitnr)
264 {
265         set_bit(SB_NR_TO_BIT(sb, bitnr), __sbitmap_word(sb, bitnr));
266 }
267 
268 static inline void sbitmap_clear_bit(struct sbitmap *sb, unsigned int bitnr)
269 {
270         clear_bit(SB_NR_TO_BIT(sb, bitnr), __sbitmap_word(sb, bitnr));
271 }
272 
273 static inline int sbitmap_test_bit(struct sbitmap *sb, unsigned int bitnr)
274 {
275         return test_bit(SB_NR_TO_BIT(sb, bitnr), __sbitmap_word(sb, bitnr));
276 }
277 
278 unsigned int sbitmap_weight(const struct sbitmap *sb);
279 
280 /**
281  * sbitmap_show() - Dump &struct sbitmap information to a &struct seq_file.
282  * @sb: Bitmap to show.
283  * @m: struct seq_file to write to.
284  *
285  * This is intended for debugging. The format may change at any time.
286  */
287 void sbitmap_show(struct sbitmap *sb, struct seq_file *m);
288 
289 /**
290  * sbitmap_bitmap_show() - Write a hex dump of a &struct sbitmap to a &struct
291  * seq_file.
292  * @sb: Bitmap to show.
293  * @m: struct seq_file to write to.
294  *
295  * This is intended for debugging. The output isn't guaranteed to be internally
296  * consistent.
297  */
298 void sbitmap_bitmap_show(struct sbitmap *sb, struct seq_file *m);
299 
300 /**
301  * sbitmap_queue_init_node() - Initialize a &struct sbitmap_queue on a specific
302  * memory node.
303  * @sbq: Bitmap queue to initialize.
304  * @depth: See sbitmap_init_node().
305  * @shift: See sbitmap_init_node().
306  * @round_robin: See sbitmap_get().
307  * @flags: Allocation flags.
308  * @node: Memory node to allocate on.
309  *
310  * Return: Zero on success or negative errno on failure.
311  */
312 int sbitmap_queue_init_node(struct sbitmap_queue *sbq, unsigned int depth,
313                             int shift, bool round_robin, gfp_t flags, int node);
314 
315 /**
316  * sbitmap_queue_free() - Free memory used by a &struct sbitmap_queue.
317  *
318  * @sbq: Bitmap queue to free.
319  */
320 static inline void sbitmap_queue_free(struct sbitmap_queue *sbq)
321 {
322         kfree(sbq->ws);
323         free_percpu(sbq->alloc_hint);
324         sbitmap_free(&sbq->sb);
325 }
326 
327 /**
328  * sbitmap_queue_resize() - Resize a &struct sbitmap_queue.
329  * @sbq: Bitmap queue to resize.
330  * @depth: New number of bits to resize to.
331  *
332  * Like sbitmap_resize(), this doesn't reallocate anything. It has to do
333  * some extra work on the &struct sbitmap_queue, so it's not safe to just
334  * resize the underlying &struct sbitmap.
335  */
336 void sbitmap_queue_resize(struct sbitmap_queue *sbq, unsigned int depth);
337 
338 /**
339  * __sbitmap_queue_get() - Try to allocate a free bit from a &struct
340  * sbitmap_queue with preemption already disabled.
341  * @sbq: Bitmap queue to allocate from.
342  *
343  * Return: Non-negative allocated bit number if successful, -1 otherwise.
344  */
345 int __sbitmap_queue_get(struct sbitmap_queue *sbq);
346 
347 /**
348  * __sbitmap_queue_get_shallow() - Try to allocate a free bit from a &struct
349  * sbitmap_queue, limiting the depth used from each word, with preemption
350  * already disabled.
351  * @sbq: Bitmap queue to allocate from.
352  * @shallow_depth: The maximum number of bits to allocate from a single word.
353  * See sbitmap_get_shallow().
354  *
355  * Return: Non-negative allocated bit number if successful, -1 otherwise.
356  */
357 int __sbitmap_queue_get_shallow(struct sbitmap_queue *sbq,
358                                 unsigned int shallow_depth);
359 
360 /**
361  * sbitmap_queue_get() - Try to allocate a free bit from a &struct
362  * sbitmap_queue.
363  * @sbq: Bitmap queue to allocate from.
364  * @cpu: Output parameter; will contain the CPU we ran on (e.g., to be passed to
365  *       sbitmap_queue_clear()).
366  *
367  * Return: Non-negative allocated bit number if successful, -1 otherwise.
368  */
369 static inline int sbitmap_queue_get(struct sbitmap_queue *sbq,
370                                     unsigned int *cpu)
371 {
372         int nr;
373 
374         *cpu = get_cpu();
375         nr = __sbitmap_queue_get(sbq);
376         put_cpu();
377         return nr;
378 }
379 
380 /**
381  * sbitmap_queue_get_shallow() - Try to allocate a free bit from a &struct
382  * sbitmap_queue, limiting the depth used from each word.
383  * @sbq: Bitmap queue to allocate from.
384  * @cpu: Output parameter; will contain the CPU we ran on (e.g., to be passed to
385  *       sbitmap_queue_clear()).
386  * @shallow_depth: The maximum number of bits to allocate from a single word.
387  * See sbitmap_get_shallow().
388  *
389  * Return: Non-negative allocated bit number if successful, -1 otherwise.
390  */
391 static inline int sbitmap_queue_get_shallow(struct sbitmap_queue *sbq,
392                                             unsigned int *cpu,
393                                             unsigned int shallow_depth)
394 {
395         int nr;
396 
397         *cpu = get_cpu();
398         nr = __sbitmap_queue_get_shallow(sbq, shallow_depth);
399         put_cpu();
400         return nr;
401 }
402 
403 /**
404  * sbitmap_queue_clear() - Free an allocated bit and wake up waiters on a
405  * &struct sbitmap_queue.
406  * @sbq: Bitmap to free from.
407  * @nr: Bit number to free.
408  * @cpu: CPU the bit was allocated on.
409  */
410 void sbitmap_queue_clear(struct sbitmap_queue *sbq, unsigned int nr,
411                          unsigned int cpu);
412 
413 static inline int sbq_index_inc(int index)
414 {
415         return (index + 1) & (SBQ_WAIT_QUEUES - 1);
416 }
417 
418 static inline void sbq_index_atomic_inc(atomic_t *index)
419 {
420         int old = atomic_read(index);
421         int new = sbq_index_inc(old);
422         atomic_cmpxchg(index, old, new);
423 }
424 
425 /**
426  * sbq_wait_ptr() - Get the next wait queue to use for a &struct
427  * sbitmap_queue.
428  * @sbq: Bitmap queue to wait on.
429  * @wait_index: A counter per "user" of @sbq.
430  */
431 static inline struct sbq_wait_state *sbq_wait_ptr(struct sbitmap_queue *sbq,
432                                                   atomic_t *wait_index)
433 {
434         struct sbq_wait_state *ws;
435 
436         ws = &sbq->ws[atomic_read(wait_index)];
437         sbq_index_atomic_inc(wait_index);
438         return ws;
439 }
440 
441 /**
442  * sbitmap_queue_wake_all() - Wake up everything waiting on a &struct
443  * sbitmap_queue.
444  * @sbq: Bitmap queue to wake up.
445  */
446 void sbitmap_queue_wake_all(struct sbitmap_queue *sbq);
447 
448 /**
449  * sbitmap_queue_show() - Dump &struct sbitmap_queue information to a &struct
450  * seq_file.
451  * @sbq: Bitmap queue to show.
452  * @m: struct seq_file to write to.
453  *
454  * This is intended for debugging. The format may change at any time.
455  */
456 void sbitmap_queue_show(struct sbitmap_queue *sbq, struct seq_file *m);
457 
458 #endif /* __LINUX_SCALE_BITMAP_H */
459 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp