Re: [PATCH] speed up on find_first_bit for i386 (let compiler do the work)

[linux@horizon.com]

> static inline int new_find_first_bit(const unsigned long *b, unsigned size)
> {
> 	int x = 0;
> 	do {
> 		unsigned long v = *b++;
> 		if (v)
> 			return __ffs(v) + x;
> 		if (x >= size)
> 			break;
> 		x += 32;
> 	} while (1);
> 	return x;
> }

Wait a minute... suppose that size == 32 and the bitmap is one word of all
zeros.  Dynamic execution will overflow the buffer:

 	int x = 0;
 		unsigned long v = *b++;	/* Zero */

 		if (v)			/* False, v == 0 */
 		if (x >= size)		/* False, 0 < 32 */
 		x += 32;
 	} while (1);
 		unsigned long v = *b++;	/* Buffer overflow */
 		if (v)			/* Random value, suppose non-zero */
			return __ffs(v) + x;	/* >= 32 */

That should be:
static inline int new_find_first_bit(const unsigned long *b, unsigned size)
	int x = 0;
 	do {
 		unsigned long v = *b++;
 		if (v)
 			return __ffs(v) + x;
	} while ((x += 32) < size);
	return size;
}

Note that we assume that the trailing long is padded with zeros.

In truth, it should probably be either

static inline unsigned new_find_first_bit(u32 const *b, unsigned size)
	int x = 0;
 	do {
 		u32 v = *b++;
 		if (v)
 			return __ffs(v) + x;
	} while ((x += 32) < size);
	return size;
}

or

static inline unsigned
new_find_first_bit(unsigned long const *b, unsigned size)
	unsigned x = 0;
 	do {
 		unsigned long v = *b++;
 		if (v)
 			return __ffs(v) + x;
	} while ((x += CHAR_BIT * sizeof *b) < size);
	return size;
}

Do we actually store bitmaps on 64-bit machines with 32 significant bits
per ulong?
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/