LOG2: Implement a general integer log2 facility in the kernel [try #4]
Subsystems (16)
PATCH 1/4 LOG2: Implement a general integer log2 facility in the kernel [try #4]
From: David Howells <[email protected]>
This facility provides three entry points:
ilog2() Log base 2 of unsigned long ilog2_u32() Log base 2 of u32 ilog2_u64() Log base 2 of u64
These facilities can either be used inside functions on dynamic data:
int do_something(long q)
{
...;
y = ilog2(x)
...;
}Or can be used to statically initialise global variables with constant values:
unsigned n = ilog2(27);
When performing static initialisation, the compiler will report "error:
initializer element is not constant" if asked to take a log of zero or of something not reducible to a constant. They treat negative numbers as unsigned.
When not dealing with a constant, they fall back to using fls() which permits them to use arch-specific log calculation instructions - such as BSR on x86/x86_64 or SCAN on FRV - if available.
---
arch/alpha/Kconfig | 8 ++ arch/arm/Kconfig | 8 ++ arch/arm26/Kconfig | 8 ++ arch/avr32/Kconfig | 8 ++ arch/cris/Kconfig | 8 ++ arch/frv/Kconfig | 8 ++ arch/h8300/Kconfig | 8 ++ arch/i386/Kconfig.cpu | 8 ++ arch/ia64/Kconfig | 8 ++ arch/m32r/Kconfig | 8 ++ arch/m68k/Kconfig | 8 ++ arch/m68knommu/Kconfig | 8 ++ arch/mips/Kconfig | 8 ++ arch/parisc/Kconfig | 8 ++ arch/powerpc/Kconfig | 8 ++ arch/ppc/Kconfig | 8 ++ arch/s390/Kconfig | 8 ++ arch/sh/Kconfig | 8 ++ arch/sh64/Kconfig | 8 ++ arch/sparc/Kconfig | 8 ++ arch/sparc64/Kconfig | 8 ++ arch/v850/Kconfig | 8 ++ arch/x86_64/Kconfig | 8 ++ arch/xtensa/Kconfig | 8 ++ drivers/infiniband/hw/mthca/mthca_provider.c | 4 - drivers/infiniband/hw/mthca/mthca_qp.c | 4 - drivers/infiniband/hw/mthca/mthca_srq.c | 4 - drivers/infiniband/ulp/iser/iser_memory.c | 4 - fs/ext2/super.c | 6 - fs/ext3/super.c | 6 - include/asm-frv/bitops.h | 44 +++++++++ include/linux/kernel.h | 9 -- include/linux/log2.h | 131 ++++++++++++++++++++++++++ mm/page_alloc.c | 4 - 34 files changed, 382 insertions(+), 26 deletions(-)
arch/alpha/Kconfig +8 -0
@@ -25,6 +25,14 @@ config RWSEM_XCHGADD_ALGORITHM bool default y +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + config GENERIC_FIND_NEXT_BIT bool default y
arch/arm/Kconfig +8 -0
@@ -74,6 +74,14 @@ config RWSEM_GENERIC_SPINLOCK config RWSEM_XCHGADD_ALGORITHM bool +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + config GENERIC_HWEIGHT bool default y
arch/arm26/Kconfig +8 -0
@@ -41,6 +41,14 @@ config RWSEM_GENERIC_SPINLOCK config RWSEM_XCHGADD_ALGORITHM bool +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + config GENERIC_HWEIGHT bool default y
arch/avr32/Kconfig +8 -0
@@ -45,6 +45,14 @@ config GENERIC_TIME config RWSEM_XCHGADD_ALGORITHM bool +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + config GENERIC_BUST_SPINLOCK bool
arch/cris/Kconfig +8 -0
@@ -16,6 +16,14 @@ config RWSEM_GENERIC_SPINLOCK config RWSEM_XCHGADD_ALGORITHM bool +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + config GENERIC_FIND_NEXT_BIT bool default y
arch/frv/Kconfig +8 -0
@@ -41,6 +41,14 @@ config TIME_LOW_RES bool default y +config ARCH_HAS_ILOG2_U32 + bool + default y + +config ARCH_HAS_ILOG2_U64 + bool + default y + mainmenu "Fujitsu FR-V Kernel Configuration" source "init/Kconfig"
arch/h8300/Kconfig +8 -0
@@ -29,6 +29,14 @@ config RWSEM_XCHGADD_ALGORITHM bool default n +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + config GENERIC_FIND_NEXT_BIT bool default y
arch/i386/Kconfig.cpu +8 -0
@@ -240,6 +240,14 @@ config RWSEM_XCHGADD_ALGORITHM depends on !M386 default y +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + config GENERIC_CALIBRATE_DELAY bool default y
arch/ia64/Kconfig +8 -0
@@ -34,6 +34,14 @@ config RWSEM_XCHGADD_ALGORITHM bool default y +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + config GENERIC_FIND_NEXT_BIT bool default y
arch/m32r/Kconfig +8 -0
@@ -214,6 +214,14 @@ config RWSEM_XCHGADD_ALGORITHM bool default n +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + config GENERIC_FIND_NEXT_BIT bool default y
arch/m68k/Kconfig +8 -0
@@ -17,6 +17,14 @@ config RWSEM_GENERIC_SPINLOCK config RWSEM_XCHGADD_ALGORITHM bool +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + config GENERIC_HWEIGHT bool default y
arch/m68knommu/Kconfig +8 -0
@@ -25,6 +25,14 @@ config RWSEM_XCHGADD_ALGORITHM bool default n +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + config GENERIC_FIND_NEXT_BIT bool default y
arch/mips/Kconfig +8 -0
@@ -789,6 +789,14 @@ config RWSEM_GENERIC_SPINLOCK config RWSEM_XCHGADD_ALGORITHM bool +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + config GENERIC_FIND_NEXT_BIT bool default y
arch/parisc/Kconfig +8 -0
@@ -25,6 +25,14 @@ config RWSEM_GENERIC_SPINLOCK config RWSEM_XCHGADD_ALGORITHM bool +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + config GENERIC_FIND_NEXT_BIT bool default y
arch/powerpc/Kconfig +8 -0
@@ -41,6 +41,14 @@ config RWSEM_XCHGADD_ALGORITHM bool default y +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + config GENERIC_HWEIGHT bool default y
arch/ppc/Kconfig +8 -0
@@ -19,6 +19,14 @@ config RWSEM_XCHGADD_ALGORITHM bool default y +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + config GENERIC_HWEIGHT bool default y
arch/s390/Kconfig +8 -0
@@ -22,6 +22,14 @@ config RWSEM_XCHGADD_ALGORITHM bool default y +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + config GENERIC_HWEIGHT bool default y
arch/sh/Kconfig +8 -0
@@ -48,6 +48,14 @@ config GENERIC_IOMAP config ARCH_MAY_HAVE_PC_FDC bool +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + source "init/Kconfig" menu "System type"
arch/sh64/Kconfig +8 -0
@@ -36,6 +36,14 @@ config GENERIC_CALIBRATE_DELAY config RWSEM_XCHGADD_ALGORITHM bool +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + config GENERIC_ISA_DMA bool
arch/sparc/Kconfig +8 -0
@@ -166,6 +166,14 @@ config ARCH_MAY_HAVE_PC_FDC bool default y +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + config SUN_PM bool default y
arch/sparc64/Kconfig +8 -0
@@ -34,6 +34,14 @@ config ARCH_MAY_HAVE_PC_FDC bool default y +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + config AUDIT_ARCH bool default y
arch/v850/Kconfig +8 -0
@@ -38,6 +38,14 @@ config TIME_LOW_RES bool default y +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + # Turn off some random 386 crap that can affect device config config ISA bool
arch/x86_64/Kconfig +8 -0
@@ -96,6 +96,14 @@ config AUDIT_ARCH bool default y +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + source "init/Kconfig"
arch/xtensa/Kconfig +8 -0
@@ -34,6 +34,14 @@ config GENERIC_HARDIRQS bool default y +config ARCH_HAS_ILOG2_U32 + bool + default n + +config ARCH_HAS_ILOG2_U64 + bool + default n + source "init/Kconfig" menu "Processor type and features"
drivers/infiniband/hw/mthca/mthca_provider.c +2 -2
@@ -124,7 +124,7 @@ static int mthca_query_device(struct ib_ props->max_map_per_fmr =255 ; else props->max_map_per_fmr = - (1 << (32 -long_log2 (mdev->limits.num_mpts))) -1 ; + (1 << (32 -ilog2 (mdev->limits.num_mpts))) -1 ; err =0 ; out:
@@ -814,7 +814,7 @@ static int mthca_resize_cq(struct ib_cq lkey = ucmd.lkey; } - ret =mthca_RESIZE_CQ (dev, cq->cqn, lkey,long_log2 (entries), &status); + ret =mthca_RESIZE_CQ (dev, cq->cqn, lkey,ilog2 (entries), &status);if (status) ret = -EINVAL ;
drivers/infiniband/hw/mthca/mthca_qp.c +2 -2
@@ -635,11 +635,11 @@ int mthca_modify_qp(struct ib_qp *ibqp,if (mthca_is_memfree (dev)) {if (qp->rq.max) - qp_context->rq_size_stride =long_log2 (qp->rq.max) <<3 ; + qp_context->rq_size_stride =ilog2 (qp->rq.max) <<3 ; qp_context->rq_size_stride |= qp->rq.wqe_shift -4 ;if (qp->sq.max) - qp_context->sq_size_stride =long_log2 (qp->sq.max) <<3 ; + qp_context->sq_size_stride =ilog2 (qp->sq.max) <<3 ; qp_context->sq_size_stride |= qp->sq.wqe_shift -4 ; }
drivers/infiniband/hw/mthca/mthca_srq.c +2 -2
@@ -118,7 +118,7 @@ static void mthca_arbel_init_srq_contextmemset (context,0 ,sizeof *context); - logsize =long_log2 (srq->max) + srq->wqe_shift; + logsize =ilog2 (srq->max) + srq->wqe_shift; context->state_logsize_srqn =cpu_to_be32 (logsize <<24 | srq->srqn); context->lkey =cpu_to_be32 (srq->mr.ibmr.lkey); context->db_index =cpu_to_be32 (srq->db_index);
@@ -209,7 +209,7 @@ int mthca_alloc_srq(struct mthca_dev *deif (!mthca_is_memfree (dev) && (ds > dev->limits.max_desc_sz))return -EINVAL ; - srq->wqe_shift =long_log2 (ds); + srq->wqe_shift =ilog2 (ds); srq->srqn =mthca_alloc (&dev->srq_table.alloc);if (srq->srqn ==-1 )
drivers/infiniband/ulp/iser/iser_memory.c +2 -2
@@ -113,7 +113,7 @@ int iser_start_rdma_unaligned_sg(structif (cmd_data_len >ISER_KMALLOC_THRESHOLD ) mem = (void *)__get_free_pages (GFP_NOIO , -long_log2 (roundup_pow_of_two (cmd_data_len)) -PAGE_SHIFT ); +ilog2 (roundup_pow_of_two (cmd_data_len)) -PAGE_SHIFT );else mem =kmalloc (cmd_data_len,GFP_NOIO );
@@ -210,7 +210,7 @@ void iser_finalize_rdma_unaligned_sg(strif (cmd_data_len >ISER_KMALLOC_THRESHOLD )free_pages ((unsigned long )mem_copy->copy_buf, -long_log2 (roundup_pow_of_two (cmd_data_len)) -PAGE_SHIFT ); +ilog2 (roundup_pow_of_two (cmd_data_len)) -PAGE_SHIFT );else kfree (mem_copy->copy_buf);
fs/ext2/super.c +2 -4
@@ -593,8 +593,6 @@ static int ext2_check_descriptors (strucreturn 1 ; } -#define log2 (n) ffz(~(n)) -/* * Maximal file size. There is a direct, and {,double-,triple-}indirect * block limit, and also a limit of (2^32 - 1) 512-byte sectors in i_blocks.
@@ -828,9 +826,9 @@ static int ext2_fill_super(struct super_ sbi->s_sbh = bh; sbi->s_mount_state =le16_to_cpu (es->s_state); sbi->s_addr_per_block_bits = -log2 (EXT2_ADDR_PER_BLOCK (sb)); +ilog2 (EXT2_ADDR_PER_BLOCK (sb)); sbi->s_desc_per_block_bits = -log2 (EXT2_DESC_PER_BLOCK (sb)); +ilog2 (EXT2_DESC_PER_BLOCK (sb));if (sb->s_magic !=EXT2_SUPER_MAGIC ) goto cantfind_ext2;
fs/ext3/super.c +2 -4
@@ -1341,8 +1341,6 @@ #endif sb->s_flags = s_flags;/* Restore MS_RDONLY status */ } -#define log2 (n) ffz(~(n)) -/* * Maximal file size. There is a direct, and {,double-,triple-}indirect * block limit, and also a limit of (2^32 - 1) 512-byte sectors in i_blocks.
@@ -1589,8 +1587,8 @@ static int ext3_fill_super (struct super sbi->s_desc_per_block = blocksize /sizeof (struct ext3_group_desc ); sbi->s_sbh = bh; sbi->s_mount_state =le16_to_cpu (es->s_state); - sbi->s_addr_per_block_bits =log2 (EXT3_ADDR_PER_BLOCK (sb)); - sbi->s_desc_per_block_bits =log2 (EXT3_DESC_PER_BLOCK (sb)); + sbi->s_addr_per_block_bits =ilog2 (EXT3_ADDR_PER_BLOCK (sb)); + sbi->s_desc_per_block_bits =ilog2 (EXT3_DESC_PER_BLOCK (sb));for (i=0 ; i <4 ; i++) sbi->s_hash_seed[i] =le32_to_cpu (es->s_hash_seed[i]); sbi->s_def_hash_version = es->s_def_hash_version;
include/asm-frv/bitops.h +44 -0
50 lines not on this page · raw message
include/linux/kernel.h +1 -8
@@ -13,6 +13,7 @@ #include <linux/stddef.h>#include <linux/types.h> #include <linux/compiler.h> #include <linux/bitops.h> +#include <linux/log2.h> #include <asm/byteorder.h> #include <asm/bug.h>
@@ -155,14 +156,6 @@ #endifunsigned long int_sqrt (unsigned long ); -static inline int __attribute_pure__ long_log2(unsigned long x) -{ -int r =0 ; -for (x >>=1 ; x >0 ; x >>=1 ) - r++; -return r; -} -static inline unsigned long __attribute_const__ roundup_pow_of_two (unsigned long x) {
include/linux/log2.h new file +131 -0
131 lines not on this page · raw message
mm/page_alloc.c +2 -2
@@ -3091,7 +3091,7 @@ void *__init alloc_large_system_hash(conif (numentries > max) numentries = max; - log2qty =long_log2 (numentries); + log2qty =ilog2 (numentries); do { size = bucketsize << log2qty;
@@ -3113,7 +3113,7 @@ void *__init alloc_large_system_hash(conprintk ("%s hash table entries: %d (order: %d, %lu bytes)\n" , tablename, (1U << log2qty), -long_log2 (size) -PAGE_SHIFT , +ilog2 (size) -PAGE_SHIFT , size);if (_hash_shift)
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.
---
include/linux/kernel.h | 6 ------ include/linux/log2.h | 26 ++++++++++++++++++++++++++ 2 files changed, 26 insertions(+), 6 deletions(-)
include/linux/kernel.h +0 -6
@@ -156,12 +156,6 @@ #endifunsigned 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);
include/linux/log2.h +26 -0
@@ -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 */
PATCH 3/4 LOG2: Alter get_order() so that it can make use of ilog2() on a constant [try #4]
In reply to David HowellsFrom: 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.
---
include/asm-generic/page.h | 38 ++++++++++++++++++++++++++++++++++---- 1 files changed, 34 insertions(+), 4 deletions(-)
include/asm-generic/page.h +34 -4
@@ -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__ */
PATCH 4/4 LOG2: Provide ilog2() fallbacks for powerpc [try #4]
In reply to David HowellsFrom: David Howells <[email protected]>
Provide ilog2() fallbacks for powerpc for 32-bit numbers and 64-bit numbers on ppc64.
---
arch/powerpc/Kconfig | 4 ++-- include/asm-powerpc/bitops.h | 21 ++++++++++++++++++++- include/asm-powerpc/page_32.h | 10 +--------- 3 files changed, 23 insertions(+), 12 deletions(-)
arch/powerpc/Kconfig +2 -2
@@ -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
include/asm-powerpc/bitops.h +20 -1
@@ -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 lreturn 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
include/asm-powerpc/page_32.h +1 -9
@@ -26,15 +26,7 @@ extern void clear_pages(void *page, intstatic 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__ */
arch/alpha/Kconfig config RWSEM_XCHGADD_ALGORITHM · line 30
Quoted 3 lines · David Howells
arch/alpha/Kconfig +3
-0+config ARCH_HAS_ILOG2_U32 + bool + default n
Why not "def_bool n"? Or indeed, since the default is n, why not just "bool"?
Quoted 1 line · Matthew Wilcox
Why not "
def_booln"?
def_bool? What's that? default + bool? I don't remember seeing any of those in any of the files I looked in.
Quoted 1 line
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
Quoted 7 lines · Matthew Wilcox
arch/alpha/Kconfig config RWSEM_XCHGADD_ALGORITHM · line 30
Quoted 3 lines · David Howells
arch/alpha/Kconfig +3
-0+config ARCH_HAS_ILOG2_U32 + bool + default nWhy not "
def_booln"? 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.
Quoted 4 lines · Christoph Lameter
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
Quoted 4 lines · David Howells
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.
Quoted 1 line
(2) Not everyone realises that
fls()can be used to dolog2().
So this is a case for a wrapper.
Quoted 5 lines
(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.
Quoted 4 lines
(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.
Quoted 2 lines
(5)
fls()andfls64()can't be used to initialise a variable at compile time,ilog2() can.
Well that is the same issue as (4).
Quoted 1 line · Christoph Lameter
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.
Quoted 2 lines
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.
Quoted 9 lines
Quoted 5 lines
(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).
Quoted 4 lines
Quoted 2 lines
(5)
fls()andfls64()can't be used to initialise a variable at compiletime, 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
Quoted 7 lines · David Howells
On FRV, for example, I don't want to wrap
fls()because the code forilog2()can be shorter and simpler.If I did
fls()as a wrapper aroundilog2()then it would have to involve a conditional jump because the compiler can't alter the inline asm ofilog2()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.
Quoted 1 line
(I have defined ilog2(n) as returning an undefined value if n < 1).
Undefined values are bad. Could you produce a runtime error instead?
Quoted 7 lines
Quoted 4 lines
Quoted 2 lines
(5)
fls()andfls64()can't be used to initialise a variable at compiletime, 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.
Quoted 5 lines · Christoph Lameter
Quoted 3 lines · David Howells
On FRV, for example, I don't want to wrap
fls()because the code forilog2()can be shorter and simpler.
Quoted 8 lines
Quoted 4 lines
If I did
fls()as a wrapper aroundilog2()then it would have to involve a conditional jump because the compiler can't alter the inline asm ofilog2()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.
Quoted 3 lines
Quoted 1 line
(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.
Quoted 10 lines
Quoted 7 lines
Quoted 4 lines
Quoted 2 lines
(5)
fls()andfls64()can't be used to initialise a variable at compiletime, 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
include/linux/log2.h line 128
Quoted 5 lines
+ * the massive ternary operator construction
include/linux/log2.h new file +3
-0+ (sizeof (n) <=4 ) ? \ +__ilog2_u32 (n) : \ +__ilog2_u64 (n) \
Should not this be: sizeof(n) <= sizeof(u32)
-`J'
Quoted 7 lines · Jan Engelhardt
include/linux/log2.h line 128
Quoted 5 lines
+ * the massive ternary operator construction
include/linux/log2.h new file +3
-0+ (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.
Quoted 10 lines
Quoted 7 lines
include/linux/log2.h line 128
Quoted 5 lines
+ * the massive ternary operator construction
include/linux/log2.h new file +3
-0+ (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'
Quoted 6 lines · Jan Engelhardt
Quoted 2 lines
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
Quoted 9 lines
Quoted 7 lines
Quoted 3 lines
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'
On Oct 09, 2006, at 04:36:12, Jan Engelhardt wrote:i
Quoted 7 lines
Quoted 7 lines
Quoted 6 lines
Quoted 2 lines
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.
Quoted 5 lines
Quoted 1 line
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
Quoted 8 lines · Kyle Moffett
#if
defined(CONFIG_ARCH_HAS_64BIT_WORD)typedef unsigned long __u64;
typedef signed long __s64;
#elifdefined(__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 <><
Quoted 4 lines · On Mon, 9 Oct 2006 05:51:14 -0400 Kyle Moffett <[email protected]> wrote:
It might be possible to clean up the
types.hfiles a bit with something like the following inlinux/types.h(nearly identical code is found in all of theasm-*/types.hfiles):
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/
Quoted 16 lines
Quoted 9 lines
Quoted 9 lines
Quoted 8 lines
Quoted 3 lines
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.Quoted 6 lines
Quoted 2 lines
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.
Quoted 8 lines
Well, uhh, actually...
All presently-supported architectures do exactly that. Well, some do:
typedef unsigned int
__u32;
#ifdef__KERNEL__
typedef__u32u32;
#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'
Quoted 1 line · Jan Engelhardt
typedef
uint32_t__u32;
That only offsets the problem a bit. You still have to derive uint32_t from somewhere.
David
Quoted 5 lines
Quoted 2 lines
typedef
uint32_t__u32;That only offsets the problem a bit. You still have to derive
uint32_tfrom somewhere.
The compiler could make it available as a 'fundamental type' - i.e. available without any headers, like 'int' and 'long'.
-`J'
Quoted 7 lines · Jan Engelhardt
Quoted 4 lines
Quoted 1 line
typedef
uint32_t__u32;That only offsets the problem a bit. You still have to derive
uint32_tfrom 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.
Signature · 4 lines
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."
Quoted 11 lines
Quoted 8 lines
Quoted 5 lines
Quoted 2 lines
typedef
uint32_t__u32;That only offsets the problem a bit. You still have to derive
uint32_tfrom 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_twithout including <stdint.h> first.
Well no problem, stdint.h may just have
typedef __secret_compiler_provided_uint32_t uint32_t;
-`J'
Quoted 7 lines · Jan Engelhardt
Quoted 2 lines
The compiler is not allowed to define
uint32_twithout including <stdint.h> first.Well no problem,
stdint.hmay just havetypedef
__secret_compiler_provided_uint32_tuint32_t;
But it doesn't, and there's nothing the kernel can do about this for existing gcc versions.
Arnd <><
Quoted 4 lines
Quoted 4 lines
Quoted 1 line
Quoted 1 line
Quoted 1 line
"Jan" == Jan Engelhardt <[email protected]> writes:
That only offsets the problem a bit. You still have to derive
uint32_tfrom 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
Signature · 1 line
Samuel Tardieu -- [email protected] -- http://www.rfc1149.net/
Geert Uytterhoeven
maintainerQuoted 20 lines · Jan Engelhardt
Quoted 20 lines
Quoted 9 lines
Quoted 9 lines
Quoted 8 lines
Quoted 3 lines
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.Quoted 6 lines
Quoted 2 lines
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:
Quoted 8 lines
Quoted 4 lines
typedef unsigned int
__u32;
#ifdef__KERNEL__
typedef__u32u32;
#endifOuch 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
Quoted 6 lines · Geert Uytterhoeven
Quoted 4 lines · Jan Engelhardt
Ouch ouch ouch. It should better be
typedef
uint32_t__u32;
Quoted 8 lines
You mean
#ifdef
__KERNEL__
typedef__u32u32;
#else
// Assumed we did #include <stdint.h> before
typedefuint32_t__u32;
#endif
Why should that be a valid assumption? Right now, it works if you don't include stdint.h in advance.
Arnd <><
Geert Uytterhoeven
maintainerQuoted 16 lines · Arnd Bergmann
Quoted 6 lines · Geert Uytterhoeven
Quoted 4 lines · Jan Engelhardt
Ouch ouch ouch. It should better be
typedef
uint32_t__u32;Quoted 8 lines
You mean
#ifdef
__KERNEL__
typedef__u32u32;
#else
// Assumed we did #include <stdint.h> before
typedefuint32_t__u32;
#endif
Quoted 2 lines
Why should that be a valid assumption? Right now, it works if you don't include
stdint.hin 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
Quoted 18 lines · Geert Uytterhoeven
Quoted 16 lines · Arnd Bergmann
Quoted 14 lines · Geert Uytterhoeven
Quoted 4 lines · Jan Engelhardt
Ouch ouch ouch. It should better be
typedef
uint32_t__u32;You mean
#ifdef
__KERNEL__
typedef__u32u32;
#else
// Assumed we did #include <stdint.h> before
typedefuint32_t__u32;
#endif
Quoted 4 lines
Quoted 2 lines
Why should that be a valid assumption? Right now, it works if you don't include
stdint.hin 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 <><
Geert Uytterhoeven
maintainerQuoted 18 lines · Arnd Bergmann
Quoted 17 lines · Geert Uytterhoeven
Quoted 16 lines · Arnd Bergmann
Quoted 14 lines · Geert Uytterhoeven
Quoted 4 lines · Jan Engelhardt
Ouch ouch ouch. It should better be
typedef
uint32_t__u32;You mean
#ifdef
__KERNEL__
typedef__u32u32;
#else
// Assumed we did #include <stdint.h> before
typedefuint32_t__u32;
#endif
Quoted 8 lines
Quoted 4 lines
Quoted 2 lines
Why should that be a valid assumption? Right now, it works if you don't include
stdint.hin 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 onuint32_twould 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
Quoted 4 lines · Geert Uytterhoeven
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 <><
Quoted 2 lines · Arnd Bergmann
That has the potential of breaking other source files that don't expect
linux/types.hto bring in the wholestdint.hfile.
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.
Quoted 3 lines
Also, it may break some other linux header files that include <
linux/types.h> and expect to get stuff likeuid_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?
Signature · 1 line
dwmw2
Quoted 8 lines · David Woodhouse
Quoted 2 lines · Arnd Bergmann
That has the potential of breaking other source files that don't expect
linux/types.hto bring in the wholestdint.hfile.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.
Quoted 5 lines
Quoted 3 lines
Also, it may break some other linux header files that include <
linux/types.h> and expect to get stuff likeuid_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 <><
Quoted 3 lines · Jan Engelhardt
Ouch ouch ouch. It should better be
typedef
uint32_t__u32;
Actually, if you want to guarantee the size of an integer variable with gcc, you can do, for example, this:
typedef int __attribute__((mode(SI))) siint;
which creates a 32-bit signed integer type called "siint".
The "mode" attribute is parameterised with one of the following values to indicate the specific size of integer required:
QI 8-bit HI 16-bit SI 32-bit DI 64-bit TI 128-bit
David
Hi,
arch/alpha/Kconfig config RWSEM_XCHGADD_ALGORITHM · line 30
Quoted 3 lines · David Howells
arch/alpha/Kconfig +3
-0+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