Messages in this thread Patch in this message | | | Date | Mon, 8 Apr 2013 14:30:37 -0700 | From | Andrew Morton <> | Subject | Re: [PATCH] bitmap: speedup in bitmap_find_free_region when order is 0 |
| |
On Mon, 8 Apr 2013 11:23:48 +0900 Chanho Min <chanho.min@lge.com> wrote:
> If bitmap_find_free_region() is called with order=0, We can reduce > for-loops to find 1 free bit. First, It scans bitmap array by the > increment of long type, then find 1 free bit within 1 long type value.
That seems sensible. I assume-without-checking that single-bit is a common case?
> In 32 bits system and 1024 bits size, in the worst case, We need 1024 > for-loops to find 1 free bit. But, If This is applied, it takes > 64 for-loops. Instead, if free bit is in the first index of the bitmaps, > It will be needed additional 1 for-loop. But from second index, It > will be speed up significantly. > > --- a/lib/bitmap.c > +++ b/lib/bitmap.c > @@ -1099,6 +1099,37 @@ done: > } > > /** > + * bitmap_find_free_one - find a mem region > + * @bitmap: array of unsigned longs corresponding to the bitmap > + * @bits: number of bits in the bitmap > + * > + * Find one of free (zero) bits in a @bitmap of @bits bits and > + * allocate them (set them to one). > + * > + * Return the bit offset in bitmap of the allocated region, > + * or -errno on failure. > + */ > +static int __bitmap_find_free_one(unsigned long *bitmap, int bits) > +{ > + int pos, i; > + unsigned long mask = (unsigned long)(~((unsigned long) 0));
That seems unnecessarily complicated. "unsigned long mask = -1;" works :)
> + int nlongs_reg = BITS_TO_LONGS(bits); > + > + for (i = 0 ; i < nlongs_reg ; i++) { > + if ((bitmap[i] & mask) != mask) {
But here we could just do "if (bitmap[i] != -1)". Or ~0UL.
> + for (pos = 0 ; pos < BITS_PER_LONG ; pos++) { > + if (!__reg_op(&bitmap[i], pos, 0, > + REG_OP_ISFREE)) > + continue; > + __reg_op(&bitmap[i], pos, 0, REG_OP_ALLOC); > + return pos; > + } > + } > + } > + return -ENOMEM; > +}
afacit the code is buggy - if `bits' is not an exact multiple of BITS_PER_LONG, this search will wander off the end of the specified region?
> +/** > * bitmap_find_free_region - find a contiguous aligned mem region > * @bitmap: array of unsigned longs corresponding to the bitmap > * @bits: number of bits in the bitmap > @@ -1116,6 +1147,9 @@ int bitmap_find_free_region(unsigned long *bitmap, int bits, int order) > { > int pos, end; /* scans bitmap by regions of size order */ > > + if (order == 0) > + return __bitmap_find_free_one(bitmap, bits); > + > for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) { > if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) > continue;
| |