Re: "[PATCH] idr.c: extra features enhancements" breaks some archs

Re: "[PATCH] idr.c: extra features enhancements" breaks some archs

[Andrew Morton]

Bartlomiej Zolnierkiewicz <B.Zolnierkiewicz@elka.pw.edu.pl> wrote:
>
> 
> http://linus.bkbits.net:8080/linux-2.5/cset@408422f91NJQZKJweeY7yvmNfDTRmg?nav=index.html|ChangeSet@-2d
> 
> > [PATCH] idr.c: extra features enhancements
> 
> This patch adds find_next_bit() call to lib/idr.c but find_next_bit()
> is not implemented on arm, arm26, cris, h8300, m68k, m68knommu, um and v850.
> 
> Please fix it...
> 

eww, how irritating.

find_next_bit() is used in:

- the cpumask code

- Andi's NUMA code

- drivers/atm/lanai.c

- the sched-domains patches in -mm

- and, now, lib/idr.c


the above architectures simply hadn't stumbled across it, but now they
have.

There are fairly generic-looking implementations of find_next_bit() in
alpha, parisc, others.

Could I please ask the relevant arch maintainers to prepare an implementation?

Thanks.

Re: "[PATCH] idr.c: extra features enhancements" breaks some archs

[Russell King]

On Tue, Apr 20, 2004 at 02:29:47PM -0700, Andrew Morton wrote:
> Could I please ask the relevant arch maintainers to prepare an implementation?

Its in the usual place.

-- 
Russell King
 Linux kernel    2.6 ARM Linux   - http://www.arm.linux.org.uk/
 maintainer of:  2.6 PCMCIA      - http://pcmcia.arm.linux.org.uk/
                 2.6 Serial core

Re: "[PATCH] idr.c: extra features enhancements" breaks some archs

[Bartlomiej Zolnierkiewicz]

On Wednesday 21 of April 2004 00:42, Russell King wrote:
> On Tue, Apr 20, 2004 at 02:29:47PM -0700, Andrew Morton wrote:
> > Could I please ask the relevant arch maintainers to prepare an
> > implementation?
>
> Its in the usual place.

I'm talking about find_next_bit() not find_next_zero_bit().

Re: "[PATCH] idr.c: extra features enhancements" breaks some archs

[Andrew Morton]

Bartlomiej Zolnierkiewicz <B.Zolnierkiewicz@elka.pw.edu.pl> wrote:
>
> On Wednesday 21 of April 2004 00:42, Russell King wrote:
> > On Tue, Apr 20, 2004 at 02:29:47PM -0700, Andrew Morton wrote:
> > > Could I please ask the relevant arch maintainers to prepare an
> > > implementation?
> >
> > Its in the usual place.
> 
> I'm talking about find_next_bit() not find_next_zero_bit().

Russell's bk tree now contains an impementation of find_next_bit().


diff -Nru a/arch/arm/lib/findbit.S b/arch/arm/lib/findbit.S
--- a/arch/arm/lib/findbit.S	Tue Apr 20 12:58:39 2004
+++ b/arch/arm/lib/findbit.S	Tue Apr 20 12:58:39 2004
@@ -51,6 +51,39 @@
 		add	r2, r2, #1		@ align bit pointer
 		b	2b			@ loop for next bit
 
+/*
+ * Purpose  : Find a 'one' bit
+ * Prototype: int find_first_bit(const unsigned long *addr, unsigned int maxbit);
+ */
+ENTRY(_find_first_bit_le)
+		teq	r1, #0	
+		beq	3f
+		mov	r2, #0
+1:		ldrb	r3, [r0, r2, lsr #3]
+		movs	r3, r3
+		bne	.found			@ any now set - found zero bit
+		add	r2, r2, #8		@ next bit pointer
+2:		cmp	r2, r1			@ any more?
+		blo	1b
+3:		mov	r0, r1			@ no free bits
+		RETINSTR(mov,pc,lr)
+
+/*
+ * Purpose  : Find next 'one' bit
+ * Prototype: int find_next_zero_bit(void *addr, unsigned int maxbit, int offset)
+ */
+ENTRY(_find_next_bit_le)
+		teq	r1, #0
+		beq	2b
+		ands	ip, r2, #7
+		beq	1b			@ If new byte, goto old routine
+		ldrb	r3, [r0, r2, lsr #3]
+		movs	r3, r3, lsr ip		@ shift off unused bits
+		bne	.found
+		orr	r2, r2, #7		@ if zero, then no bits here
+		add	r2, r2, #1		@ align bit pointer
+		b	2b			@ loop for next bit
+
 #ifdef __ARMEB__
 
 ENTRY(_find_first_zero_bit_be)
@@ -73,6 +106,30 @@
 		eor	r3, r2, #0x18		@ big endian byte ordering
 		ldrb	r3, [r0, r3, lsr #3]
 		eor	r3, r3, #0xff		@ now looking for a 1 bit
+		movs	r3, r3, lsr ip		@ shift off unused bits
+		orreq	r2, r2, #7		@ if zero, then no bits here
+		addeq	r2, r2, #1		@ align bit pointer
+		beq	2b			@ loop for next bit
+
+ENTRY(_find_first_bit_be)
+		teq	r1, #0
+		beq	3f
+		mov	r2, #0
+1:		eor	r3, r2, #0x18		@ big endian byte ordering
+		ldrb	r3, [r0, r3, lsr #3]
+		movs	r3, r3
+		bne	.found			@ any now set - found zero bit
+		add	r2, r2, #8		@ next bit pointer
+2:		cmp	r2, r1			@ any more?
+		blo	1b
+3:		mov	r0, r1			@ no free bits
+		RETINSTR(mov,pc,lr)
+
+ENTRY(_find_next_bit_be)
+		ands	ip, r2, #7
+		beq	1b			@ If new byte, goto old routine
+		eor	r3, r2, #0x18		@ big endian byte ordering
+		ldrb	r3, [r0, r3, lsr #3]
 		movs	r3, r3, lsr ip		@ shift off unused bits
 		orreq	r2, r2, #7		@ if zero, then no bits here
 		addeq	r2, r2, #1		@ align bit pointer
diff -Nru a/include/asm-arm/bitops.h b/include/asm-arm/bitops.h
--- a/include/asm-arm/bitops.h	Tue Apr 20 12:58:39 2004
+++ b/include/asm-arm/bitops.h	Tue Apr 20 12:58:39 2004
@@ -212,6 +212,8 @@
 extern int _test_and_change_bit_le(int nr, volatile unsigned long * p);
 extern int _find_first_zero_bit_le(void * p, unsigned size);
 extern int _find_next_zero_bit_le(void * p, int size, int offset);
+extern int _find_first_bit_le(const unsigned long *p, unsigned size);
+extern int _find_next_bit_le(const unsigned long *p, int size, int offset);
 
 /*
  * Big endian assembly bitops.  nr = 0 -> byte 3 bit 0.
@@ -224,7 +226,8 @@
 extern int _test_and_change_bit_be(int nr, volatile unsigned long * p);
 extern int _find_first_zero_bit_be(void * p, unsigned size);
 extern int _find_next_zero_bit_be(void * p, int size, int offset);
-
+extern int _find_first_bit_be(const unsigned long *p, unsigned size);
+extern int _find_next_bit_be(unsigned long *p, int size, int offset);
 
 /*
  * The __* form of bitops are non-atomic and may be reordered.
@@ -255,6 +258,8 @@
 #define test_bit(nr,p)			__test_bit(nr,p)
 #define find_first_zero_bit(p,sz)	_find_first_zero_bit_le(p,sz)
 #define find_next_zero_bit(p,sz,off)	_find_next_zero_bit_le(p,sz,off)
+#define find_first_bit(p,sz)		_find_first_bit_le(p,sz)
+#define find_next_bit(p,sz,off)		_find_next_bit_le(p,sz,off)
 
 #define WORD_BITOFF_TO_LE(x)		((x))
 
@@ -272,6 +277,8 @@
 #define test_bit(nr,p)			__test_bit(nr,p)
 #define find_first_zero_bit(p,sz)	_find_first_zero_bit_be(p,sz)
 #define find_next_zero_bit(p,sz,off)	_find_next_zero_bit_be(p,sz,off)
+#define find_first_bit(p,sz)		_find_first_bit_be(p,sz)
+#define find_next_bit(p,sz,off)		_find_next_bit_be(p,sz,off)
 
 #define WORD_BITOFF_TO_LE(x)		((x) ^ 0x18)