LinuxLists.cc - [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

[permalink] [raw]

Subject: [PATCH 4/4] LOG2: Provide ilog2() fallbacks for powerpc [try #4]

From: David Howells <[email protected]>

Provide ilog2() fallbacks for powerpc for 32-bit numbers and 64-bit numbers on
ppc64.

Signed-Off-By: David Howells <[email protected]>
---

arch/powerpc/Kconfig | 4 ++--
include/asm-powerpc/bitops.h | 21 ++++++++++++++++++++-
include/asm-powerpc/page_32.h | 10 +---------
3 files changed, 23 insertions(+), 12 deletions(-)

diff --git a/arch/powerpc/Kconfig b/arch/powerpc/Kconfig
index 1cf67b7..9515489 100644
--- a/arch/powerpc/Kconfig
+++ b/arch/powerpc/Kconfig
@@ -43,11 +43,11 @@ config RWSEM_XCHGADD_ALGORITHM

config ARCH_HAS_ILOG2_U32
bool
- default n
+ default y

config ARCH_HAS_ILOG2_U64
bool
- default n
+ default y if 64BIT

config GENERIC_HWEIGHT
bool
diff --git a/include/asm-powerpc/bitops.h b/include/asm-powerpc/bitops.h
index c341063..0288144 100644
--- a/include/asm-powerpc/bitops.h
+++ b/include/asm-powerpc/bitops.h
@@ -190,7 +190,8 @@ #include <asm-generic/bitops/non-atomic.
* Return the zero-based bit position (LE, not IBM bit numbering) of
* the most significant 1-bit in a double word.
*/
-static __inline__ int __ilog2(unsigned long x)
+static __inline__ __attribute__((const))
+int __ilog2(unsigned long x)
{
int lz;

@@ -198,6 +199,24 @@ static __inline__ int __ilog2(unsigned l
return BITS_PER_LONG - 1 - lz;
}

+static inline __attribute__((const))
+int __ilog2_u32(u32 n)
+{
+ int bit;
+ asm ("cntlzw %0,%1" : "=r" (bit) : "r" (n));
+ return 31 - bit;
+}
+
+#ifdef __powerpc64__
+static inline __attribute__((const))
+int __ilog2_u64(u32 n)
+{
+ int bit;
+ asm ("cntlzd %0,%1" : "=r" (bit) : "r" (n));
+ return 63 - bit;
+}
+#endif
+
/*
* Determines the bit position of the least significant 0 bit in the
* specified double word. The returned bit position will be
diff --git a/include/asm-powerpc/page_32.h b/include/asm-powerpc/page_32.h
index 2677bad..07f6d3c 100644
--- a/include/asm-powerpc/page_32.h
+++ b/include/asm-powerpc/page_32.h
@@ -26,15 +26,7 @@ extern void clear_pages(void *page, int
static inline void clear_page(void *page) { clear_pages(page, 0); }
extern void copy_page(void *to, void *from);

-/* Pure 2^n version of get_order */
-extern __inline__ int get_order(unsigned long size)
-{
- int lz;
-
- size = (size-1) >> PAGE_SHIFT;
- asm ("cntlzw %0,%1" : "=r" (lz) : "r" (size));
- return 32 - lz;
-}
+#include <asm-generic/page.h>

#endif /* __ASSEMBLY__ */

2006-10-06 13:34:38

[permalink] [raw]

Subject: [PATCH 3/4] LOG2: Alter get_order() so that it can make use of ilog2() on a constant [try #4]

From: David Howells <[email protected]>

Alter get_order() so that it can make use of ilog2() on a constant to produce a
constant value, retaining the ability for an arch to override it in the
non-const case.

Signed-Off-By: David Howells <[email protected]>
---

include/asm-generic/page.h | 38 ++++++++++++++++++++++++++++++++++----
1 files changed, 34 insertions(+), 4 deletions(-)

diff --git a/include/asm-generic/page.h b/include/asm-generic/page.h
index a96b5d9..b55052c 100644
--- a/include/asm-generic/page.h
+++ b/include/asm-generic/page.h
@@ -4,21 +4,51 @@ #define _ASM_GENERIC_PAGE_H
#ifdef __KERNEL__
#ifndef __ASSEMBLY__

-#include <linux/compiler.h>
+#include <linux/log2.h>

-/* Pure 2^n version of get_order */
-static __inline__ __attribute_const__ int get_order(unsigned long size)
+/*
+ * non-const pure 2^n version of get_order
+ * - the arch may override these in asm/bitops.h if they can be implemented
+ * more efficiently than using the arch log2 routines
+ * - we use the non-const log2() instead if the arch has defined one suitable
+ */
+#ifndef ARCH_HAS_GET_ORDER
+static inline __attribute__((const))
+int __get_order(unsigned long size, int page_shift)
{
+#if BITS_PER_LONG == 32 && defined(ARCH_HAS_ILOG2_U32)
+ int order = __ilog2_u32(size) - page_shift;
+ return order >= 0 ? order : 0;
+#elif BITS_PER_LONG == 64 && defined(ARCH_HAS_ILOG2_U64)
+ int order = __ilog2_u64(size) - page_shift;
+ return order >= 0 ? order : 0;
+#else
int order;

- size = (size - 1) >> (PAGE_SHIFT - 1);
+ size = (size - 1) >> (page_shift - 1);
order = -1;
do {
size >>= 1;
order++;
} while (size);
return order;
+#endif
}
+#endif
+
+/**
+ * get_order - calculate log2(pages) to hold a block of the specified size
+ * @n - size
+ *
+ * calculate allocation order based on the current page size
+ * - this can be used to initialise global variables from constant data
+ */
+#define get_order(n) \
+( \
+ __builtin_constant_p(n) ? \
+ ((n < (1UL << PAGE_SHIFT)) ? 0 : ilog2(n) - PAGE_SHIFT) : \
+ __get_order(n, PAGE_SHIFT) \
+ )

#endif /* __ASSEMBLY__ */
#endif /* __KERNEL__ */

2006-10-06 13:36:58

[permalink] [raw]

Subject: [PATCH 2/4] LOG2: Alter roundup_pow_of_two() so that it can use a ilog2() on a constant [try #4]

From: David Howells <[email protected]>

Alter roundup_pow_of_two() so that it can make use of ilog2() on a constant to
produce a constant value, retaining the ability for an arch to override it in
the non-const case.

This permits the function to be used to initialise variables.

Signed-Off-By: David Howells <[email protected]>
---

include/linux/kernel.h | 6 ------
include/linux/log2.h | 26 ++++++++++++++++++++++++++
2 files changed, 26 insertions(+), 6 deletions(-)

diff --git a/include/linux/kernel.h b/include/linux/kernel.h
index 473101a..67ca3ad 100644
--- a/include/linux/kernel.h
+++ b/include/linux/kernel.h
@@ -156,12 +156,6 @@ #endif

unsigned long int_sqrt(unsigned long);

-static inline unsigned long
-__attribute_const__ roundup_pow_of_two(unsigned long x)
-{
- return 1UL << fls_long(x - 1);
-}
-
extern int printk_ratelimit(void);
extern int __printk_ratelimit(int ratelimit_jiffies, int ratelimit_burst);

diff --git a/include/linux/log2.h b/include/linux/log2.h
index 3979c60..d02e1a5 100644
--- a/include/linux/log2.h
+++ b/include/linux/log2.h
@@ -43,6 +43,15 @@ int __ilog2_u64(u64 n)
}
#endif

+/*
+ * round up to nearest power of two
+ */
+static inline __attribute__((const))
+unsigned long __roundup_pow_of_two(unsigned long n)
+{
+ return 1UL << fls_long(n - 1);
+}
+
/**
* ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value
* @n - parameter
@@ -128,4 +137,21 @@ ( \
__ilog2_u64(n) \
)

+/**
+ * roundup_pow_of_two - round the given value up to nearest power of two
+ * @n - parameter
+ *
+ * round the given balue up to the nearest power of two
+ * - the result is undefined when n == 0
+ * - this can be used to initialise global variables from constant data
+ */
+#define roundup_pow_of_two(n) \
+( \
+ __builtin_constant_p(n) ? ( \
+ (n == 1) ? 0 : \
+ (1UL << (ilog2((n) - 1) + 1)) \
+ ) : \
+ __roundup_pow_of_two(n) \
+ )
+
#endif /* _LINUX_LOG2_H */

2006-10-06 14:17:10

by Matthew Wilcox

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

On Fri, Oct 06, 2006 at 02:34:14PM +0100, David Howells wrote:
> +config ARCH_HAS_ILOG2_U32
> + bool
> + default n

Why not "def_bool n"? Or indeed, since the default is n, why not just
"bool"?

2006-10-06 14:34:11

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

Matthew Wilcox <[email protected]> wrote:

> Why not "def_bool n"?

def_bool? What's that? default + bool? I don't remember seeing any of those
in any of the files I looked in.

> Or indeed, since the default is n, why not just "bool"?

*shrug*

I'd prefer to default all of these in a common place rather than having to
relentlessly duplicate them over all archs. Is that possible?

David

2006-10-06 17:19:59

by Christoph Lameter

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

On Fri, 6 Oct 2006, Matthew Wilcox wrote:

> On Fri, Oct 06, 2006 at 02:34:14PM +0100, David Howells wrote:
> > +config ARCH_HAS_ILOG2_U32
> > + bool
> > + default n
>
> Why not "def_bool n"? Or indeed, since the default is n, why not just
> "bool"?

Why so complicated and why do it at all? We already have fls and ffs
amoung the bit operations and those map to cpu instructions on arches
that support these. fls can be used as a log 2 facilities. If you need
another name and further refine it then just add an inline function.

2006-10-06 20:37:34

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

>+ * the massive ternary operator construction
>+ (sizeof(n) <= 4) ? \
>+ __ilog2_u32(n) : \
>+ __ilog2_u64(n) \

Should not this be: sizeof(n) <= sizeof(u32)

-`J'
--

2006-10-06 20:39:22

by Matthew Wilcox

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

On Fri, Oct 06, 2006 at 10:33:19PM +0200, Jan Engelhardt wrote:
>
> >+ * the massive ternary operator construction
> >+ (sizeof(n) <= 4) ? \
> >+ __ilog2_u32(n) : \
> >+ __ilog2_u64(n) \
>
> Should not this be: sizeof(n) <= sizeof(u32)

Were you planning on porting Linux to a machine with non-8-bit-bytes any
time soon? Because there's a lot more to fix than this.

2006-10-06 20:58:43

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

>> >+ * the massive ternary operator construction
>> >+ (sizeof(n) <= 4) ? \
>> >+ __ilog2_u32(n) : \
>> >+ __ilog2_u64(n) \
>>
>> Should not this be: sizeof(n) <= sizeof(u32)
>
>Were you planning on porting Linux to a machine with non-8-bit-bytes any
>time soon? Because there's a lot more to fix than this.

I am considering the case [assuming 8-bit-byte machines] where
sizeof(u32) is not 4. Though I suppose GCC will probably make a 32-bit
type up if the hardware does not know one.

-`J'
--

2006-10-07 23:55:18

by Roman Zippel

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

Hi,

On Friday 06 October 2006 15:34, David Howells wrote:

> +config ARCH_HAS_ILOG2_U32
> + bool
> + default n

This actually doesn't do much, so you only have to add it, where it's 'y'
and "def_bool y" is shorter there.

bye, Roman

2006-10-09 08:06:35

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

Jan Engelhardt <[email protected]> wrote:

> >Were you planning on porting Linux to a machine with non-8-bit-bytes any
> >time soon? Because there's a lot more to fix than this.
>
> I am considering the case [assuming 8-bit-byte machines] where
> sizeof(u32) is not 4. Though I suppose GCC will probably make a 32-bit
> type up if the hardware does not know one.

If the machine has 8-bit bytes, how can sizeof(u32) be anything other than 4?

David

2006-10-09 08:43:15

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

>> >Were you planning on porting Linux to a machine with non-8-bit-bytes any
>> >time soon? Because there's a lot more to fix than this.
>>
>> I am considering the case [assuming 8-bit-byte machines] where
>> sizeof(u32) is not 4. Though I suppose GCC will probably make a 32-bit
>> type up if the hardware does not know one.
>
>If the machine has 8-bit bytes, how can sizeof(u32) be anything other than 4?

typedef unsigned int u32;

Though this should not be seen in the linux kernel.

-`J'
--

2006-10-09 09:52:13

by Kyle Moffett

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

On Oct 09, 2006, at 04:36:12, Jan Engelhardt wrote:i
>>>> Were you planning on porting Linux to a machine with non-8-bit-
>>>> bytes any
>>>> time soon? Because there's a lot more to fix than this.
>>>
>>> I am considering the case [assuming 8-bit-byte machines] where
>>> sizeof(u32) is not 4. Though I suppose GCC will probably make a
>>> 32-bit
>>> type up if the hardware does not know one.
>>
>> If the machine has 8-bit bytes, how can sizeof(u32) be anything
>> other than 4?
>
> typedef unsigned int u32;
>
> Though this should not be seen in the linux kernel.

Well, uhh, actually...

All presently-supported architectures do exactly that. Well, some do:

typedef unsigned int __u32;
#ifdef __KERNEL__
typedef __u32 u32;
#endif

It might be possible to clean up the types.h files a bit with
something like the following in linux/types.h (nearly identical code
is found in all of the asm-*/types.h files):

typedef unsigned char __u8;
typedef signed char __s8;
typedef unsigned short __u16;
typedef signed short __s16;
typedef unsigned int __u32;
typedef signed int __s32;
#if defined(CONFIG_ARCH_HAS_64BIT_WORD)
typedef unsigned long __u64;
typedef signed long __s64;
#elif defined(__GNUC__)
__extension__ typedef unsigned long long __u64;
__extension__ typedef signed long long __s64;
#endif

#ifdef __KERNEL__
typedef __u8 u8;
typedef __s8 s8;
typedef __u16 u16;
typedef __s16 s16;
typedef __u32 u32;
typedef __s32 s32;
typedef __u64 u64;
typedef __s64 s64;
#endif

With that you could delete ~30 lines from each of the various asm-*/
types.h files in exchange for 3 lines in each of the various arch/*/
Kconfig files.

I'll try to whip up a quick patch later today if I get the time.

Cheers,
Kyle Moffett

2006-10-09 10:11:58

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

Christoph Lameter <[email protected]> wrote:

> Why so complicated and why do it at all? We already have fls and ffs
> amoung the bit operations and those map to cpu instructions on arches
> that support these. fls can be used as a log 2 facilities. If you need
> another name and further refine it then just add an inline function.

There are a number of reasons:

(1) There are a bunch of independent log2 implementations lying around in the
code. It'd be nice to just have one set that anyone can use.

(2) Not everyone realises that fls() can be used to do log2().

(3) ilog2(n) != fls(n)

This means that the asm-optimised version for one might be less optimal
for the other (for example, ilog2() produces an undefined result if n <=
1, fls() must return 0).

(4) There are occasions when you might want to take a log2 of a constant.
With the totally inline asm approach, it would always execute some code,
though it should be unnecessary. What I've done permits you to avoid that
as the answer is always going to be the same.

(5) fls() and fls64() can't be used to initialise a variable at compile time,
ilog2() can.

David

2006-10-09 10:27:07

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

On Monday 09 October 2006 11:51, Kyle Moffett wrote:
> ? ?#if defined(CONFIG_ARCH_HAS_64BIT_WORD)
> ? ?typedef unsigned long ?__u64;
> ? ?typedef ? signed long ?__s64;
> ? ?#elif defined(__GNUC__)
> ? ?__extension__ typedef unsigned long long __u64;
> ? ?__extension__ typedef ? signed long long __s64;
> ? ?#endif
>

Well, some architectures currently expext __u64/__s64 to be
long long even with 64 bits. Changing that will likely cause
a number of new compiler warnings about conversion between
these. Of course it would be nice to clean these up, since
it's already a pain to printk() a variable of type u64.

More importantly, your code has the problem that it relies
on a CONFIG_* symbol, which will break when user space includes
the file, because that does not have config.h.

Arnd <><

2006-10-09 10:32:37

by Stephen Rothwell

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

On Mon, 9 Oct 2006 05:51:14 -0400 Kyle Moffett <[email protected]> wrote:
>
> It might be possible to clean up the types.h files a bit with
> something like the following in linux/types.h (nearly identical code
> is found in all of the asm-*/types.h files):

Even better might be to put this in asm-generic/types.h and include
that from wherever is sensible.

--
Cheers,
Stephen Rothwell [email protected]
http://www.canb.auug.org.au/~sfr/

Attachments:

(No filename) (464.00 B)
(No filename) (189.00 B)
Download all attachments

2006-10-09 11:07:15

by Christoph Lameter

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

On Mon, 9 Oct 2006, David Howells wrote:

> There are a number of reasons:
>
> (1) There are a bunch of independent log2 implementations lying around in the
> code. It'd be nice to just have one set that anyone can use.

True. So wrap around what is there but do not add gazillion of definitions
to all arches.

> (2) Not everyone realises that fls() can be used to do log2().

So this is a case for a wrapper.

> (3) ilog2(n) != fls(n)
>
> This means that the asm-optimised version for one might be less optimal
> for the other (for example, ilog2() produces an undefined result if n <=
> 1, fls() must return 0).

Ok these are boundary checks that are easily coded around. Some
variations on fls even exist that also do various flavors of end case
handling.

> (4) There are occasions when you might want to take a log2 of a constant.
> With the totally inline asm approach, it would always execute some code,
> though it should be unnecessary. What I've done permits you to avoid that
> as the answer is always going to be the same.

Good stuff. I have always wanted that. The wrapper could check for a
constant.

> (5) fls() and fls64() can't be used to initialise a variable at compile time,
> ilog2() can.

Well that is the same issue as (4).

2006-10-09 12:10:01

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

Christoph Lameter <[email protected]> wrote:

> So this is a case for a wrapper.

But it _is_ a wrapper - but the arch gets to decide around what. We fall back
to fls() or fls64() if no other inspiration strikes or is available, but in
some cases we can do better.

> Good stuff. I have always wanted that. The wrapper could check for a
> constant.

That's the main reason I put it in a common file. The const-case wrapper is
large and probably best not repeated.

> > (3) ilog2(n) != fls(n)
> >
> > This means that the asm-optimised version for one might be less
> > optimal for the other (for example, ilog2() produces an undefined
> > result if n <= 1, fls() must return 0).
>
> Ok these are boundary checks that are easily coded around. Some
> variations on fls even exist that also do various flavors of end case
> handling.

On FRV, for example, I don't want to wrap fls() because the code for ilog2()
can be shorter and simpler.

If I did fls() as a wrapper around ilog2() then it would have to involve a
conditional jump because the compiler can't alter the inline asm of ilog2() to
turn the SCAN instruction into CSCAN (which is a conditionally executed
version of SCAN).

So fls() is 5 insns and __ilog2_u32() is 1 because of the requirement that
fls() must return 0 on a zero input value. Similarly fls64() is 14 vs 8 for
__ilog2_u64().

(I have defined ilog2(n) as returning an undefined value if n < 1).

> > (5) fls() and fls64() can't be used to initialise a variable at compile
> > time, ilog2() can.
>
> Well that is the same issue as (4).

Not quite. I think (4) might be sufficiently achievable with an inline
function, but (5) is definitely not.

David

2006-10-09 12:27:57

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

>> > > > Were you planning on porting Linux to a machine with
>> > > > non-8-bit-bytes any
>> > > > time soon? Because there's a lot more to fix than this.
>> > >
>> > > I am considering the case [assuming 8-bit-byte machines] where
>> > > sizeof(u32) is not 4. Though I suppose GCC will probably make a
>> > > 32-bit
>> > > type up if the hardware does not know one.
>> >
>> > If the machine has 8-bit bytes, how can sizeof(u32) be anything other
>> > than 4?
>>
>> typedef unsigned int u32;
>>
>> Though this should not be seen in the linux kernel.
>
> Well, uhh, actually...
>
> All presently-supported architectures do exactly that. Well, some do:
>
> typedef unsigned int __u32;
> #ifdef __KERNEL__
> typedef __u32 u32;
> #endif

Ouch ouch ouch. It should better be

typedef uint32_t __u32;

So that even if there happens to be a compiler that does sizeof(int)=8,
sizeof(u32) will actually be 4. Say, if there happens to be an
architecture that does only know 64-bit integers, the compiler will
have some extra magic to make uint32_t behave like a 32-bit type in C
and transparently use 64-bit assembler. So far the theory.

-`J'
--

2006-10-09 12:54:50

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

Jan Engelhardt <[email protected]> wrote:

> typedef uint32_t __u32;

That only offsets the problem a bit. You still have to derive uint32_t from
somewhere.

David

2006-10-09 13:10:55

by Geert Uytterhoeven

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

On Mon, 9 Oct 2006, Jan Engelhardt wrote:
> >> > > > Were you planning on porting Linux to a machine with
> >> > > > non-8-bit-bytes any
> >> > > > time soon? Because there's a lot more to fix than this.
> >> > >
> >> > > I am considering the case [assuming 8-bit-byte machines] where
> >> > > sizeof(u32) is not 4. Though I suppose GCC will probably make a
> >> > > 32-bit
> >> > > type up if the hardware does not know one.
> >> >
> >> > If the machine has 8-bit bytes, how can sizeof(u32) be anything other
> >> > than 4?
> >>
> >> typedef unsigned int u32;
> >>
> >> Though this should not be seen in the linux kernel.
> >
> > Well, uhh, actually...
> >
> > All presently-supported architectures do exactly that. Well, some do:
> >
> > typedef unsigned int __u32;
> > #ifdef __KERNEL__
> > typedef __u32 u32;
> > #endif
>
> Ouch ouch ouch. It should better be
>
> typedef uint32_t __u32;

You mean

#ifdef __KERNEL__
typedef __u32 u32;
#else
// Assumed we did #include <stdint.h> before
typedef uint32_t __u32;
#endif

?

Gr{oetje,eeting}s,

Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- [email protected]

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
-- Linus Torvalds

2006-10-09 14:52:35

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

On Monday 09 October 2006 15:09, Geert Uytterhoeven wrote:
> On Mon, 9 Oct 2006, Jan Engelhardt wrote:
> >
> > Ouch ouch ouch. It should better be
> >
> > typedef uint32_t __u32;
>
> You mean
>
> #ifdef __KERNEL__
> typedef __u32 u32;
> #else
> // Assumed we did #include <stdint.h> before
> typedef uint32_t __u32;
> #endif

Why should that be a valid assumption? Right now, it works
if you don't include stdint.h in advance.

Arnd <><

2006-10-09 15:06:13

by Geert Uytterhoeven

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

On Mon, 9 Oct 2006, Arnd Bergmann wrote:
> On Monday 09 October 2006 15:09, Geert Uytterhoeven wrote:
> > On Mon, 9 Oct 2006, Jan Engelhardt wrote:
> > >
> > > Ouch ouch ouch. It should better be
> > >
> > > typedef uint32_t __u32;
> >
> > You mean
> >
> > #ifdef __KERNEL__
> > typedef __u32 u32;
> > #else
> > // Assumed we did #include <stdint.h> before
> > typedef uint32_t __u32;
> > #endif
>
> Why should that be a valid assumption? Right now, it works
> if you don't include stdint.h in advance.

According to C99 section 7.18 you need to include <stdint.h> first.

Gr{oetje,eeting}s,

Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- [email protected]

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
-- Linus Torvalds

2006-10-09 15:27:40

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

On Monday 09 October 2006 17:05, Geert Uytterhoeven wrote:
>
> On Mon, 9 Oct 2006, Arnd Bergmann wrote:
> > On Monday 09 October 2006 15:09, Geert Uytterhoeven wrote:
> > > On Mon, 9 Oct 2006, Jan Engelhardt wrote:
> > > >
> > > > Ouch ouch ouch. It should better be
> > > >
> > > > typedef uint32_t __u32;
> > >
> > > You mean
> > >
> > > #ifdef __KERNEL__
> > > typedef __u32 u32;
> > > #else
> > > // Assumed we did #include <stdint.h> before
> > > typedef uint32_t __u32;
> > > #endif
> >
> > Why should that be a valid assumption? Right now, it works
> > if you don't include stdint.h in advance.
>
> According to C99 section 7.18 you need to include <stdint.h> first.

Sorry, I need to rephrase: you can include <linux/types.h> without
including <stdint.h> first, and many people do that.
Relying on uint32_t would mean we break existing source.

Arnd <><

2006-10-09 15:32:10

by Geert Uytterhoeven

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

On Mon, 9 Oct 2006, Arnd Bergmann wrote:
> On Monday 09 October 2006 17:05, Geert Uytterhoeven wrote:
> > On Mon, 9 Oct 2006, Arnd Bergmann wrote:
> > > On Monday 09 October 2006 15:09, Geert Uytterhoeven wrote:
> > > > On Mon, 9 Oct 2006, Jan Engelhardt wrote:
> > > > >
> > > > > Ouch ouch ouch. It should better be
> > > > >
> > > > > typedef uint32_t __u32;
> > > >
> > > > You mean
> > > >
> > > > #ifdef __KERNEL__
> > > > typedef __u32 u32;
> > > > #else
> > > > // Assumed we did #include <stdint.h> before
> > > > typedef uint32_t __u32;
> > > > #endif
> > >
> > > Why should that be a valid assumption? Right now, it works
> > > if you don't include stdint.h in advance.
> >
> > According to C99 section 7.18 you need to include <stdint.h> first.
>
> Sorry, I need to rephrase: you can include <linux/types.h> without
> including <stdint.h> first, and many people do that.
> Relying on uint32_t would mean we break existing source.

IC.

Well, I meant that of course you have to include <stdint.h> at the top of
<linux/types.h>. I just thought inside that particular #ifdef wasn't the right
place.

Problem solved :-)

Gr{oetje,eeting}s,

Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- [email protected]

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
-- Linus Torvalds

2006-10-09 16:47:12

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

On Monday 09 October 2006 17:31, Geert Uytterhoeven wrote:
> Well, I meant that of course you have to include <stdint.h> at the top of
> <linux/types.h>. I just thought inside that particular #ifdef wasn't the right
> place.
>

That has the potential of breaking other source files that don't expect
linux/types.h to bring in the whole stdint.h file.

Also, it may break some other linux header files that include <linux/types.h>
and expect to get stuff like uid_t, which you don't get if a glibc header is
included first, because of __KERNEL_STRICT_NAMES.

Arnd <><

2006-10-09 17:17:34

by Christoph Lameter

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

On Mon, 9 Oct 2006, David Howells wrote:

> On FRV, for example, I don't want to wrap fls() because the code for ilog2()
> can be shorter and simpler.
>
> If I did fls() as a wrapper around ilog2() then it would have to involve a
> conditional jump because the compiler can't alter the inline asm of ilog2() to
> turn the SCAN instruction into CSCAN (which is a conditionally executed
> version of SCAN).

Hmmm.. Why not? If you can define fls on a per arch basis then that should
be possible? You can tell the compiler to produce the correct version of
the scan instructions. We do that frequently on IA64.

> (I have defined ilog2(n) as returning an undefined value if n < 1).

Undefined values are bad. Could you produce a runtime error instead?

> > > (5) fls() and fls64() can't be used to initialise a variable at compile
> > > time, ilog2() can.
> >
> > Well that is the same issue as (4).
>
> Not quite. I think (4) might be sufficiently achievable with an inline
> function, but (5) is definitely not.

With the appropriate per arch modification of fls() this should also be
possible within the existing framework.

2006-10-09 20:08:08

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

>> typedef uint32_t __u32;
>
>That only offsets the problem a bit. You still have to derive uint32_t from
>somewhere.

The compiler could make it available as a 'fundamental type' - i.e.
available without any headers, like 'int' and 'long'.

-`J'
--

2006-10-09 20:37:15

by Andreas Schwab

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

Jan Engelhardt <[email protected]> writes:

>>> typedef uint32_t __u32;
>>
>>That only offsets the problem a bit. You still have to derive uint32_t from
>>somewhere.
>
> The compiler could make it available as a 'fundamental type' - i.e.
> available without any headers, like 'int' and 'long'.

The compiler is not allowed to define uint32_t without including
<stdint.h> first.

Andreas.

--
Andreas Schwab, SuSE Labs, [email protected]
SuSE Linux Products GmbH, Maxfeldstra?e 5, 90409 N?rnberg, Germany
PGP key fingerprint = 58CA 54C7 6D53 942B 1756 01D3 44D5 214B 8276 4ED5
"And now for something completely different."

2006-10-09 21:01:54

by Samuel Tardieu

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

>>>>> "Jan" == Jan Engelhardt <[email protected]> writes:

>> That only offsets the problem a bit. You still have to derive
>> uint32_t from somewhere.

Jan> The compiler could make it available as a 'fundamental type' -
Jan> i.e. available without any headers, like 'int' and 'long'.

The compiler isn't allowed to pollute your namespace with symbols like
that. What if someone defines uint32_t as a function for example in
her code? (yes, this would be sick, but is allowed by default)

Sam
--
Samuel Tardieu -- [email protected] -- http://www.rfc1149.net/

2006-10-10 07:55:49

by David Woodhouse

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

On Mon, 2006-10-09 at 18:47 +0200, Arnd Bergmann wrote:
> That has the potential of breaking other source files that don't expect
> linux/types.h to bring in the whole stdint.h file.

I don't think we need to care about those. Userspace in _general_
shouldn't be including our header files -- this is only for low-level
system stuff, and that can be expected to deal with the fact that we
define and use some standard C types from last century.

> Also, it may break some other linux header files that include <linux/types.h>
> and expect to get stuff like uid_t, which you don't get if a glibc header is
> included first, because of __KERNEL_STRICT_NAMES.

We have that problem already, don't we?

--
dwmw2

2006-10-10 09:52:36

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

>>>> typedef uint32_t __u32;
>>>
>>>That only offsets the problem a bit. You still have to derive uint32_t from
>>>somewhere.
>>
>> The compiler could make it available as a 'fundamental type' - i.e.
>> available without any headers, like 'int' and 'long'.
>
>The compiler is not allowed to define uint32_t without including
><stdint.h> first.

Well no problem, stdint.h may just have

typedef __secret_compiler_provided_uint32_t uint32_t;

-`J'
--

2006-10-10 09:58:48

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

Christoph Lameter <[email protected]> wrote:

> On Mon, 9 Oct 2006, David Howells wrote:
>
> > On FRV, for example, I don't want to wrap fls() because the code for ilog2()
> > can be shorter and simpler.
> >
> > If I did fls() as a wrapper around ilog2() then it would have to involve a
> > conditional jump because the compiler can't alter the inline asm of
> > ilog2() to turn the SCAN instruction into CSCAN (which is a conditionally
> > executed version of SCAN).
>
> Hmmm.. Why not? If you can define fls on a per arch basis then that should
> be possible? You can tell the compiler to produce the correct version of
> the scan instructions. We do that frequently on IA64.

Ummm... How? As far as I know there's no way to do that. Actually, it's
harder than just changing SCAN into CSCAN: you can't tell the compiler about
condition code type parameters to inline asm, so you have to embed all the
conditional bits in the inline asm if you want them, and not if you don't.

> > (I have defined ilog2(n) as returning an undefined value if n < 1).
>
> Undefined values are bad. Could you produce a runtime error instead?

But if I make it clear to the user of ilog(n) that *they* are expected to check
the parameters, then it shouldn't be a problem. Quite often there's no need to
check because n can't be out of range without other things breaking.

Doing enforced runtime error checking slows things down and is frequently
unnecessary. Actually, in a way it's better to let the caller do it as they
know whether it's necessary, and can probably find a better place to do it.

Consider div64(): that might not produce an error if the divisor is 0. And
then there's __ffs() which is explicitly stated as producing an undefined
result if no bits are set in its argument.

> > > > (5) fls() and fls64() can't be used to initialise a variable at compile
> > > > time, ilog2() can.
> > >
> > > Well that is the same issue as (4).
> >
> > Not quite. I think (4) might be sufficiently achievable with an inline
> > function, but (5) is definitely not.
>
> With the appropriate per arch modification of fls() this should also be
> possible within the existing framework.

True, but I suspect that's going to be less required of fls() and co.

David

2006-10-10 11:42:23

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

On Tuesday 10 October 2006 11:41, Jan Engelhardt wrote:
> >The compiler is not allowed to define uint32_t without including
> ><stdint.h> first.
>
> Well no problem, stdint.h may just have
>
> typedef __secret_compiler_provided_uint32_t uint32_t;
>

But it doesn't, and there's nothing the kernel can do about this
for existing gcc versions.

Arnd <><

2006-10-10 12:13:11

[permalink] [raw]

Subject: Re: [PATCH 1/4] LOG2: Implement a general integer log2 facility in the kernel [try #4]

On Tuesday 10 October 2006 09:55, David Woodhouse wrote:
> On Mon, 2006-10-09 at 18:47 +0200, Arnd Bergmann wrote:
> > That has the potential of breaking other source files that don't expect
> > linux/types.h to bring in the whole stdint.h file.
>
> I don't think we need to care about those. Userspace in _general_
> shouldn't be including our header files -- this is only for low-level
> system stuff, and that can be expected to deal with the fact that we
> define and use some standard C types from last century.

Some of our headers are traditionally included by libc headers.
E.g. sys/stat.h might include asm/stat.h, but must not include
stdint.h.

It's somewhat different for file that are completely outside
of the scope of posix, e.g. <mtd/*.h>, that don't give any
guarantees about what they include.

> > Also, it may break some other linux header files that include <linux/types.h>
> > and expect to get stuff like uid_t, which you don't get if a glibc header is
> > included first, because of __KERNEL_STRICT_NAMES.
>
> We have that problem already, don't we?

It would get worse.

An application can now do

#include <linux/types.h>
#include <linux/signal.h>
#include <stdint.h>

but not

#include <stdint.h>
#include <linux/types.h>
#include <linux/signal.h>

If <linux/types.h> includes <stdint.h> itself, the first examples breaks
as well.

I'd prefer to clean up all of our headers so they work with
__KERNEL_STRICT_NAMES and in any order, but that's a lot of work and in
the meantime we should make sure we don't make matters worse.

Arnd <><

2006-10-10 12:24:10