forked from ~ljy/RK356X_SDK_RELEASE
blame | history | patch | commit | commitdiff
hc
2024-05-10 093a6c67005148ae32a5c9e4553491b9f5c2457b 
 kernel/include/linux/sbitmap.h
....@@ -1,20 +1,9 @@
1
+/* SPDX-License-Identifier: GPL-2.0-only */
12 /*
23  * Fast and scalable bitmaps.
34  *
45  * Copyright (C) 2016 Facebook
56  * 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/>.
187  */
198 
209 #ifndef __LINUX_SCALE_BITMAP_H
....@@ -30,14 +19,24 @@
3019  */
3120 struct sbitmap_word {
3221 	/**
33
-	 * @word: The bitmap word itself.
34
-	 */
35
-	unsigned long word;
36
-
37
-	/**
38
-	 * @depth: Number of bits being used in @word.
22
+	 * @depth: Number of bits being used in @word/@cleared
3923 	 */
4024 	unsigned long depth;
25
+
26
+	/**
27
+	 * @word: word holding free bits
28
+	 */
29
+	unsigned long word ____cacheline_aligned_in_smp;
30
+
31
+	/**
32
+	 * @cleared: word holding cleared bits
33
+	 */
34
+	unsigned long cleared ____cacheline_aligned_in_smp;
35
+
36
+	/**
37
+	 * @swap_lock: Held while swapping word <-> cleared
38
+	 */
39
+	spinlock_t swap_lock;
4140 } ____cacheline_aligned_in_smp;
4241 
4342 /**
....@@ -124,6 +123,11 @@
124123 	 * @ws: Wait queues.
125124 	 */
126125 	struct sbq_wait_state *ws;
126
+
127
+	/*
128
+	 * @ws_active: count of currently active ws waitqueues
129
+	 */
130
+	atomic_t ws_active;
127131 
128132 	/**
129133 	 * @round_robin: Allocate bits in strict round-robin order.
....@@ -212,15 +216,6 @@
212216  */
213217 bool sbitmap_any_bit_set(const struct sbitmap *sb);
214218 
215
-/**
216
- * sbitmap_any_bit_clear() - Check for an unset bit in a &struct
217
- * sbitmap.
218
- * @sb: Bitmap to check.
219
- *
220
- * Return: true if any bit in the bitmap is clear, false otherwise.
221
- */
222
-bool sbitmap_any_bit_clear(const struct sbitmap *sb);
223
-
224219 #define SB_NR_TO_INDEX(sb, bitnr) ((bitnr) >> (sb)->shift)
225220 #define SB_NR_TO_BIT(sb, bitnr) ((bitnr) & ((1U << (sb)->shift) - 1U))
226221 
....@@ -250,12 +245,14 @@
250245 	nr = SB_NR_TO_BIT(sb, start);
251246 
252247 	while (scanned < sb->depth) {
253
-		struct sbitmap_word *word = &sb->map[index];
254
-		unsigned int depth = min_t(unsigned int, word->depth - nr,
248
+		unsigned long word;
249
+		unsigned int depth = min_t(unsigned int,
250
+					   sb->map[index].depth - nr,
255251 					   sb->depth - scanned);
256252 
257253 		scanned += depth;
258
-		if (!word->word)
254
+		word = sb->map[index].word & ~sb->map[index].cleared;
255
+		if (!word)
259256 			goto next;
260257 
261258 		/*
....@@ -265,7 +262,7 @@
265262 		 */
266263 		depth += nr;
267264 		while (1) {
268
-			nr = find_next_bit(&word->word, depth, nr);
265
+			nr = find_next_bit(&word, depth, nr);
269266 			if (nr >= depth)
270267 				break;
271268 			if (!fn(sb, (index << sb->shift) + nr, data))
....@@ -310,6 +307,19 @@
310307 	clear_bit(SB_NR_TO_BIT(sb, bitnr), __sbitmap_word(sb, bitnr));
311308 }
312309 
310
+/*
311
+ * This one is special, since it doesn't actually clear the bit, rather it
312
+ * sets the corresponding bit in the ->cleared mask instead. Paired with
313
+ * the caller doing sbitmap_deferred_clear() if a given index is full, which
314
+ * will clear the previously freed entries in the corresponding ->word.
315
+ */
316
+static inline void sbitmap_deferred_clear_bit(struct sbitmap *sb, unsigned int bitnr)
317
+{
318
+	unsigned long *addr = &sb->map[SB_NR_TO_INDEX(sb, bitnr)].cleared;
319
+
320
+	set_bit(SB_NR_TO_BIT(sb, bitnr), addr);
321
+}
322
+
313323 static inline void sbitmap_clear_bit_unlock(struct sbitmap *sb,
314324 					    unsigned int bitnr)
315325 {
....@@ -320,8 +330,6 @@
320330 {
321331 	return test_bit(SB_NR_TO_BIT(sb, bitnr), __sbitmap_word(sb, bitnr));
322332 }
323
-
324
-unsigned int sbitmap_weight(const struct sbitmap *sb);
325333 
326334 /**
327335  * sbitmap_show() - Dump &struct sbitmap information to a &struct seq_file.
....@@ -531,4 +539,45 @@
531539  */
532540 void sbitmap_queue_show(struct sbitmap_queue *sbq, struct seq_file *m);
533541 
542
+struct sbq_wait {
543
+	struct sbitmap_queue *sbq;	/* if set, sbq_wait is accounted */
544
+	struct wait_queue_entry wait;
545
+};
546
+
547
+#define DEFINE_SBQ_WAIT(name)							\
548
+	struct sbq_wait name = {						\
549
+		.sbq = NULL,							\
550
+		.wait = {							\
551
+			.private	= current,				\
552
+			.func		= autoremove_wake_function,		\
553
+			.entry		= LIST_HEAD_INIT((name).wait.entry),	\
554
+		}								\
555
+	}
556
+
557
+/*
558
+ * Wrapper around prepare_to_wait_exclusive(), which maintains some extra
559
+ * internal state.
560
+ */
561
+void sbitmap_prepare_to_wait(struct sbitmap_queue *sbq,
562
+				struct sbq_wait_state *ws,
563
+				struct sbq_wait *sbq_wait, int state);
564
+
565
+/*
566
+ * Must be paired with sbitmap_prepare_to_wait().
567
+ */
568
+void sbitmap_finish_wait(struct sbitmap_queue *sbq, struct sbq_wait_state *ws,
569
+				struct sbq_wait *sbq_wait);
570
+
571
+/*
572
+ * Wrapper around add_wait_queue(), which maintains some extra internal state
573
+ */
574
+void sbitmap_add_wait_queue(struct sbitmap_queue *sbq,
575
+			    struct sbq_wait_state *ws,
576
+			    struct sbq_wait *sbq_wait);
577
+
578
+/*
579
+ * Must be paired with sbitmap_add_wait_queue()
580
+ */
581
+void sbitmap_del_wait_queue(struct sbq_wait *sbq_wait);
582
+
534583 #endif /* __LINUX_SCALE_BITMAP_H */