- /*
- * First free bit here is our index into the first
- * free bit at the next higher level
- */
- ret = index = (j << UNIT_SHIFT) + ffz(al->map[j]);
- break;
+ /* Shift previously calculated index for next level */
+ index <<= UNIT_SHIFT;
+
+ /*
+ * Start from an index that's at least as large as the
+ * originally passed in bit number.
+ */
+ base_index = bit_nr >> (UNIT_SHIFT * i);
+ if (index < base_index)
+ index = base_index;
+
+ /* Get the offset and bit for this level */
+ offset = index >> UNIT_SHIFT;
+ bit = index & BLOCKS_PER_UNIT_MASK;
+
+ /*
+ * If the previous level had unused bits in its last
+ * word, the offset could be bigger than the map at
+ * this level. That means no free bits exist before the
+ * end of the map, so return -1.
+ */
+ if (offset >= al->map_size)
+ return -1ULL;
+
+ /* Check the first word starting with the specific bit */
+ temp = ~bit_masks[bit] & ~al->map[offset];
+ if (temp)
+ goto found;
+
+ /*
+ * No free bit in the first word, so iterate
+ * looking for a word with one or more free bits.
+ */
+ for (offset++; offset < al->map_size; offset++) {
+ temp = ~al->map[offset];
+ if (temp)
+ goto found;