Page MenuHomeFreeBSD
Files F159127608

D11819.id31589.diff
No OneTemporary
Actions

D11819.id31589.diff
View Options

Index: sys/kern/subr_blist.c
===================================================================
--- sys/kern/subr_blist.c
+++ sys/kern/subr_blist.c
@@ -170,6 +170,28 @@
}
/*
+ * Use a de Bruijn sequence to find the 1 bit in a daddr_t.
+ * Assumes that the argument has only one bit set. ffs(x)
+ * could be implemented as return (x==0? 0: 1+bitpos(x&-x)).
+ */
+static inline int
+bitpos(daddr_t mask)
+{
+ const u_daddr_t magic = 0x025f9a9c5643dba3;
+ const unsigned char magictable[64] = {
+ 0, 1, 2, 42, 3, 30, 59, 43,
+ 39, 4, 31, 7, 60, 17, 25, 44,
+ 40, 57, 5, 23, 21, 32, 34, 8,
+ 61, 36, 18, 50, 26, 53, 45, 10,
+ 63, 41, 29, 58, 38, 6, 16, 24,
+ 56, 22, 20, 33, 35, 49, 52, 9,
+ 62, 28, 37, 15, 55, 19, 48, 51,
+ 27, 14, 54, 47, 13, 46, 12, 11,
+ };
+ return (magictable[(mask * magic) >> 58]);
+}
+
+/*
* blist_create() - create a blist capable of handling up to the specified
* number of blocks
*
@@ -353,13 +375,13 @@
*
* This is the core of the allocator and is optimized for the
* BLIST_BMAP_RADIX block allocation case. Otherwise, execution
- * time is proportional to log2(count) + log2(BLIST_BMAP_RADIX).
+ * time is proportional to log2(count).
*/
static daddr_t
blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count, daddr_t cursor)
{
u_daddr_t mask;
- int count1, hi, lo, mid, num_shifts, range1, range_ext;
+ int count1, lo, num_shifts, range1, range_ext;
if (count == BLIST_BMAP_RADIX) {
/*
@@ -417,17 +439,10 @@
/*
* The least significant set bit in mask marks the start of the first
* available range of sufficient size. Clear all the bits but that one,
- * and then perform a binary search to find its position.
+ * and find its position.
*/
mask &= -mask;
- hi = BLIST_BMAP_RADIX - count1;
- while (lo + 1 < hi) {
- mid = (lo + hi) >> 1;
- if ((mask >> mid) != 0)
- lo = mid;
- else
- hi = mid;
- }
+ lo = bitpos(mask);
/*
* Set in mask exactly the bits being allocated, and clear them from

File Metadata

Mime Type
text/plain
Expires
Thu, Jun 11, 10:20 AM (21 h, 40 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
33868643
Default Alt Text
D11819.id31589.diff (1 KB)

Event Timeline