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

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

[David Howells]

From: David Howells <dhowells@redhat.com>

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.

Signed-Off-By: David Howells <dhowells@redhat.com>
---

 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(-)

diff --git a/arch/alpha/Kconfig b/arch/alpha/Kconfig
index 7e55ea6..84caf50 100644
--- a/arch/alpha/Kconfig
+++ b/arch/alpha/Kconfig
@@ -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
diff --git a/arch/arm/Kconfig b/arch/arm/Kconfig
index adb05de..0c3dab6 100644
--- a/arch/arm/Kconfig
+++ b/arch/arm/Kconfig
@@ -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
diff --git a/arch/arm26/Kconfig b/arch/arm26/Kconfig
index c14fe91..74eba8b 100644
--- a/arch/arm26/Kconfig
+++ b/arch/arm26/Kconfig
@@ -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
diff --git a/arch/avr32/Kconfig b/arch/avr32/Kconfig
index 5f1694e..bb059a4 100644
--- a/arch/avr32/Kconfig
+++ b/arch/avr32/Kconfig
@@ -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
 
diff --git a/arch/cris/Kconfig b/arch/cris/Kconfig
index 6a1238a..3474309 100644
--- a/arch/cris/Kconfig
+++ b/arch/cris/Kconfig
@@ -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
diff --git a/arch/frv/Kconfig b/arch/frv/Kconfig
index cf1c446..7561d7b 100644
--- a/arch/frv/Kconfig
+++ b/arch/frv/Kconfig
@@ -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"
diff --git a/arch/h8300/Kconfig b/arch/h8300/Kconfig
index cabf0bf..34a84bc 100644
--- a/arch/h8300/Kconfig
+++ b/arch/h8300/Kconfig
@@ -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
diff --git a/arch/i386/Kconfig.cpu b/arch/i386/Kconfig.cpu
index 21c9a4e..99fa842 100644
--- a/arch/i386/Kconfig.cpu
+++ b/arch/i386/Kconfig.cpu
@@ -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
diff --git a/arch/ia64/Kconfig b/arch/ia64/Kconfig
index 70f7eb9..ac23182 100644
--- a/arch/ia64/Kconfig
+++ b/arch/ia64/Kconfig
@@ -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
diff --git a/arch/m32r/Kconfig b/arch/m32r/Kconfig
index 41fd490..f383dab 100644
--- a/arch/m32r/Kconfig
+++ b/arch/m32r/Kconfig
@@ -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
diff --git a/arch/m68k/Kconfig b/arch/m68k/Kconfig
index 805b81f..0953145 100644
--- a/arch/m68k/Kconfig
+++ b/arch/m68k/Kconfig
@@ -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
diff --git a/arch/m68knommu/Kconfig b/arch/m68knommu/Kconfig
index 6d920d4..0e07597 100644
--- a/arch/m68knommu/Kconfig
+++ b/arch/m68knommu/Kconfig
@@ -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
diff --git a/arch/mips/Kconfig b/arch/mips/Kconfig
index 8a49884..8f10fe2 100644
--- a/arch/mips/Kconfig
+++ b/arch/mips/Kconfig
@@ -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
diff --git a/arch/parisc/Kconfig b/arch/parisc/Kconfig
index d210123..0f9ff61 100644
--- a/arch/parisc/Kconfig
+++ b/arch/parisc/Kconfig
@@ -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
diff --git a/arch/powerpc/Kconfig b/arch/powerpc/Kconfig
index 8b69104..1cf67b7 100644
--- a/arch/powerpc/Kconfig
+++ b/arch/powerpc/Kconfig
@@ -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
diff --git a/arch/ppc/Kconfig b/arch/ppc/Kconfig
index 077711e..55abcc9 100644
--- a/arch/ppc/Kconfig
+++ b/arch/ppc/Kconfig
@@ -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
diff --git a/arch/s390/Kconfig b/arch/s390/Kconfig
index 51c2dfe..a3f9550 100644
--- a/arch/s390/Kconfig
+++ b/arch/s390/Kconfig
@@ -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
diff --git a/arch/sh/Kconfig b/arch/sh/Kconfig
index f6a0c44..eaea396 100644
--- a/arch/sh/Kconfig
+++ b/arch/sh/Kconfig
@@ -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"
diff --git a/arch/sh64/Kconfig b/arch/sh64/Kconfig
index 58c678e..03778a1 100644
--- a/arch/sh64/Kconfig
+++ b/arch/sh64/Kconfig
@@ -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
 
diff --git a/arch/sparc/Kconfig b/arch/sparc/Kconfig
index 9431e96..44b79c2 100644
--- a/arch/sparc/Kconfig
+++ b/arch/sparc/Kconfig
@@ -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
diff --git a/arch/sparc64/Kconfig b/arch/sparc64/Kconfig
index b627f8d..d391d11 100644
--- a/arch/sparc64/Kconfig
+++ b/arch/sparc64/Kconfig
@@ -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
diff --git a/arch/v850/Kconfig b/arch/v850/Kconfig
index 37ec644..bcf8258 100644
--- a/arch/v850/Kconfig
+++ b/arch/v850/Kconfig
@@ -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
diff --git a/arch/x86_64/Kconfig b/arch/x86_64/Kconfig
index 010d226..c007ab2 100644
--- a/arch/x86_64/Kconfig
+++ b/arch/x86_64/Kconfig
@@ -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"
 
 
diff --git a/arch/xtensa/Kconfig b/arch/xtensa/Kconfig
index c1e69a1..9eccfbd 100644
--- a/arch/xtensa/Kconfig
+++ b/arch/xtensa/Kconfig
@@ -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"
diff --git a/drivers/infiniband/hw/mthca/mthca_provider.c b/drivers/infiniband/hw/mthca/mthca_provider.c
index 981fe2e..20c0fc1 100644
--- a/drivers/infiniband/hw/mthca/mthca_provider.c
+++ b/drivers/infiniband/hw/mthca/mthca_provider.c
@@ -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;
 
diff --git a/drivers/infiniband/hw/mthca/mthca_qp.c b/drivers/infiniband/hw/mthca/mthca_qp.c
index 5e5c58b..1bf0856 100644
--- a/drivers/infiniband/hw/mthca/mthca_qp.c
+++ b/drivers/infiniband/hw/mthca/mthca_qp.c
@@ -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;
 	}
 
diff --git a/drivers/infiniband/hw/mthca/mthca_srq.c b/drivers/infiniband/hw/mthca/mthca_srq.c
index 0f316c8..2af1b8e 100644
--- a/drivers/infiniband/hw/mthca/mthca_srq.c
+++ b/drivers/infiniband/hw/mthca/mthca_srq.c
@@ -118,7 +118,7 @@ static void mthca_arbel_init_srq_context
 
 	memset(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 *de
 	if (!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)
diff --git a/drivers/infiniband/ulp/iser/iser_memory.c b/drivers/infiniband/ulp/iser/iser_memory.c
index 0606744..15de90e 100644
--- a/drivers/infiniband/ulp/iser/iser_memory.c
+++ b/drivers/infiniband/ulp/iser/iser_memory.c
@@ -113,7 +113,7 @@ int iser_start_rdma_unaligned_sg(struct 
 
 	if (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(str
 
 	if (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);
 
diff --git a/fs/ext2/super.c b/fs/ext2/super.c
index 513cd42..4f0bd87 100644
--- a/fs/ext2/super.c
+++ b/fs/ext2/super.c
@@ -593,8 +593,6 @@ static int ext2_check_descriptors (struc
 	return 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;
diff --git a/fs/ext3/super.c b/fs/ext3/super.c
index 8bfd56e..b97119c 100644
--- a/fs/ext3/super.c
+++ b/fs/ext3/super.c
@@ -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;
diff --git a/include/asm-frv/bitops.h b/include/asm-frv/bitops.h
index 1f70d47..f8560ed 100644
--- a/include/asm-frv/bitops.h
+++ b/include/asm-frv/bitops.h
@@ -256,6 +256,50 @@ int __ffs(unsigned long x)
 	return 31 - bit;
 }
 
+/*
+ * special slimline version of fls() for calculating ilog2_u32()
+ * - note: no protection against n == 0
+ */
+#define ARCH_HAS_ILOG2_U32
+static inline __attribute__((const))
+int __ilog2_u32(u32 n)
+{
+	int bit;
+	asm("scan %1,gr0,%0" : "=r"(bit) : "r"(n));
+	return 31 - bit;
+}
+
+/*
+ * special slimline version of fls64() for calculating ilog2_u64()
+ * - note: no protection against n == 0
+ */
+#define ARCH_HAS_ILOG2_U64
+static inline __attribute__((const))
+int __ilog2_u64(u64 n)
+{
+	union {
+		u64 ll;
+		struct { u32 h, l; };
+	} _;
+	int bit, x, y;
+
+	_.ll = n;
+
+	asm("	subcc		%3,gr0,gr0,icc0		\n"
+	    "	ckeq		icc0,cc4		\n"
+	    "	cscan.p		%3,gr0,%0	,cc4,0	\n"
+	    "   setlos		#63,%1			\n"
+	    "	cscan.p		%4,gr0,%0	,cc4,1	\n"
+	    "   setlos		#31,%2			\n"
+	    "	csub.p		%1,%0,%0	,cc4,0	\n"
+	    "	csub		%2,%0,%0	,cc4,1	\n"
+	    : "=&r"(bit), "=r"(x), "=r"(y)
+	    : "0r"(_.h), "r"(_.l)
+	    : "icc0", "cc4"
+	    );
+	return bit;
+}
+
 #include <asm-generic/bitops/sched.h>
 #include <asm-generic/bitops/hweight.h>
 
diff --git a/include/linux/kernel.h b/include/linux/kernel.h
index 80f39ca..473101a 100644
--- a/include/linux/kernel.h
+++ b/include/linux/kernel.h
@@ -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 @@ #endif
 
 unsigned 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)
 {
diff --git a/include/linux/log2.h b/include/linux/log2.h
new file mode 100644
index 0000000..3979c60
--- /dev/null
+++ b/include/linux/log2.h
@@ -0,0 +1,131 @@
+/* Integer base 2 logarithm calculation
+ *
+ * Copyright (C) 2006 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version
+ * 2 of the License, or (at your option) any later version.
+ */
+
+#ifndef _LINUX_LOG2_H
+#define _LINUX_LOG2_H
+
+#include <linux/types.h>
+#include <linux/bitops.h>
+
+/*
+ * deal with unrepresentable constant logarithms
+ */
+extern __attribute__((const, noreturn))
+int ____ilog2_NaN(void);
+
+/*
+ * non-constant log of base 2 calculators
+ * - the arch may override these in asm/bitops.h if they can be implemented
+ *   more efficiently than using fls() and fls64()
+ * - the arch is not required to handle n==0 if implementing the fallback
+ */
+#ifndef CONFIG_ARCH_HAS_ILOG2_U32
+static inline __attribute__((const))
+int __ilog2_u32(u32 n)
+{
+	return fls(n) - 1;
+}
+#endif
+
+#ifndef CONFIG_ARCH_HAS_ILOG2_U64
+static inline __attribute__((const))
+int __ilog2_u64(u64 n)
+{
+	return fls64(n) - 1;
+}
+#endif
+
+/**
+ * ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value
+ * @n - parameter
+ *
+ * constant-capable log of base 2 calculation
+ * - this can be used to initialise global variables from constant data, hence
+ *   the massive ternary operator construction
+ *
+ * selects the appropriately-sized optimised version depending on sizeof(n)
+ */
+#define ilog2(n)				\
+(						\
+	__builtin_constant_p(n) ? (		\
+		(n) < 1 ? ____ilog2_NaN() :	\
+		(n) & (1ULL << 63) ? 63 :	\
+		(n) & (1ULL << 62) ? 62 :	\
+		(n) & (1ULL << 61) ? 61 :	\
+		(n) & (1ULL << 60) ? 60 :	\
+		(n) & (1ULL << 59) ? 59 :	\
+		(n) & (1ULL << 58) ? 58 :	\
+		(n) & (1ULL << 57) ? 57 :	\
+		(n) & (1ULL << 56) ? 56 :	\
+		(n) & (1ULL << 55) ? 55 :	\
+		(n) & (1ULL << 54) ? 54 :	\
+		(n) & (1ULL << 53) ? 53 :	\
+		(n) & (1ULL << 52) ? 52 :	\
+		(n) & (1ULL << 51) ? 51 :	\
+		(n) & (1ULL << 50) ? 50 :	\
+		(n) & (1ULL << 49) ? 49 :	\
+		(n) & (1ULL << 48) ? 48 :	\
+		(n) & (1ULL << 47) ? 47 :	\
+		(n) & (1ULL << 46) ? 46 :	\
+		(n) & (1ULL << 45) ? 45 :	\
+		(n) & (1ULL << 44) ? 44 :	\
+		(n) & (1ULL << 43) ? 43 :	\
+		(n) & (1ULL << 42) ? 42 :	\
+		(n) & (1ULL << 41) ? 41 :	\
+		(n) & (1ULL << 40) ? 40 :	\
+		(n) & (1ULL << 39) ? 39 :	\
+		(n) & (1ULL << 38) ? 38 :	\
+		(n) & (1ULL << 37) ? 37 :	\
+		(n) & (1ULL << 36) ? 36 :	\
+		(n) & (1ULL << 35) ? 35 :	\
+		(n) & (1ULL << 34) ? 34 :	\
+		(n) & (1ULL << 33) ? 33 :	\
+		(n) & (1ULL << 32) ? 32 :	\
+		(n) & (1ULL << 31) ? 31 :	\
+		(n) & (1ULL << 30) ? 30 :	\
+		(n) & (1ULL << 29) ? 29 :	\
+		(n) & (1ULL << 28) ? 28 :	\
+		(n) & (1ULL << 27) ? 27 :	\
+		(n) & (1ULL << 26) ? 26 :	\
+		(n) & (1ULL << 25) ? 25 :	\
+		(n) & (1ULL << 24) ? 24 :	\
+		(n) & (1ULL << 23) ? 23 :	\
+		(n) & (1ULL << 22) ? 22 :	\
+		(n) & (1ULL << 21) ? 21 :	\
+		(n) & (1ULL << 20) ? 20 :	\
+		(n) & (1ULL << 19) ? 19 :	\
+		(n) & (1ULL << 18) ? 18 :	\
+		(n) & (1ULL << 17) ? 17 :	\
+		(n) & (1ULL << 16) ? 16 :	\
+		(n) & (1ULL << 15) ? 15 :	\
+		(n) & (1ULL << 14) ? 14 :	\
+		(n) & (1ULL << 13) ? 13 :	\
+		(n) & (1ULL << 12) ? 12 :	\
+		(n) & (1ULL << 11) ? 11 :	\
+		(n) & (1ULL << 10) ? 10 :	\
+		(n) & (1ULL <<  9) ?  9 :	\
+		(n) & (1ULL <<  8) ?  8 :	\
+		(n) & (1ULL <<  7) ?  7 :	\
+		(n) & (1ULL <<  6) ?  6 :	\
+		(n) & (1ULL <<  5) ?  5 :	\
+		(n) & (1ULL <<  4) ?  4 :	\
+		(n) & (1ULL <<  3) ?  3 :	\
+		(n) & (1ULL <<  2) ?  2 :	\
+		(n) & (1ULL <<  1) ?  1 :	\
+		(n) & (1ULL <<  0) ?  0 :	\
+		____ilog2_NaN()			\
+				   ) :		\
+	(sizeof(n) <= 4) ?			\
+	__ilog2_u32(n) :			\
+	__ilog2_u64(n)				\
+ )
+
+#endif /* _LINUX_LOG2_H */
diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index a8c003e..bd30dff 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -3091,7 +3091,7 @@ void *__init alloc_large_system_hash(con
 	if (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(con
 	printk("%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]

[David Howells]

From: David Howells <dhowells@redhat.com>

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 <dhowells@redhat.com>
---

 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 */

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

[David Howells]

From: David Howells <dhowells@redhat.com>

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 <dhowells@redhat.com>
---

 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__ */

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

[David Howells]

From: David Howells <dhowells@redhat.com>

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

Signed-Off-By: David Howells <dhowells@redhat.com>
---

 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__ */
 

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

[Matthew Wilcox]

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"?

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

[David Howells]

Matthew Wilcox <matthew@wil.cx> 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

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

[Christoph Lameter]

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.

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

[Jan Engelhardt]

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

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


	-`J'
-- 

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

[Matthew Wilcox]

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.

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

[Jan Engelhardt]

>> >+ *   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'
-- 

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

[Roman Zippel]

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

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

[David Howells]

Jan Engelhardt <jengelh@linux01.gwdg.de> 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

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

[Jan Engelhardt]

>> >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'
-- 

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

[Kyle Moffett]

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

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

[David Howells]

Christoph Lameter <clameter@sgi.com> 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

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

[Arnd Bergmann]

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 <><

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

[Stephen Rothwell]

[-- Attachment #1: Type: text/plain, Size: 464 bytes --]

On Mon, 9 Oct 2006 05:51:14 -0400 Kyle Moffett <mrmacman_g4@mac.com> 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                    sfr@canb.auug.org.au
http://www.canb.auug.org.au/~sfr/

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

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

[Christoph Lameter]

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).

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

[David Howells]

Christoph Lameter <clameter@sgi.com> 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

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

[Jan Engelhardt]

>> > > > 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'
-- 

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

[David Howells]

Jan Engelhardt <jengelh@linux01.gwdg.de> wrote:

> typedef uint32_t __u32;

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

David

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

[Geert Uytterhoeven]

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 -- geert@linux-m68k.org

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

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

[Arnd Bergmann]

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 <><

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

[Geert Uytterhoeven]

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 -- geert@linux-m68k.org

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

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

[Arnd Bergmann]

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 <><

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

[Geert Uytterhoeven]

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 -- geert@linux-m68k.org

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

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

[Arnd Bergmann]

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 <><

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

[Christoph Lameter]

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.

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

[Jan Engelhardt]

>> 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'
-- 

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

[Andreas Schwab]

Jan Engelhardt <jengelh@linux01.gwdg.de> 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, schwab@suse.de
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."

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

[David Woodhouse]

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

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

[Jan Engelhardt]

>>>> 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'
-- 

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

[David Howells]

Christoph Lameter <clameter@sgi.com> 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

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

[Arnd Bergmann]

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 <><

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

[Arnd Bergmann]

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 <><

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

[David Howells]

Jan Engelhardt <jengelh@linux01.gwdg.de> wrote:

> 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