[PATCH 1/7] FRV: Fix fls() to handle bit 31 being set correctly [try #3]

[PATCH 1/7] FRV: Fix fls() to handle bit 31 being set correctly [try #3]

[David Howells]

From: David Howells <dhowells@redhat.com>

Fix FRV fls() to handle bit 31 being set correctly (it should return 32 not 0).

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

 include/asm-frv/bitops.h |   21 +++++++++++++++++----
 1 files changed, 17 insertions(+), 4 deletions(-)

diff --git a/include/asm-frv/bitops.h b/include/asm-frv/bitops.h
index 980ae1b..97fb746 100644
--- a/include/asm-frv/bitops.h
+++ b/include/asm-frv/bitops.h
@@ -161,16 +161,29 @@ #include <asm-generic/bitops/ffs.h>
 #include <asm-generic/bitops/__ffs.h>
 #include <asm-generic/bitops/find.h>
 
-/*
- * fls: find last bit set.
+/**
+ * fls - find last bit set
+ * @x: the word to search
+ *
+ * This is defined the same way as ffs:
+ * - return 32..1 to indicate bit 31..0 most significant bit set
+ * - return 0 to indicate no bits set
  */
 #define fls(x)						\
 ({							\
 	int bit;					\
 							\
-	asm("scan %1,gr0,%0" : "=r"(bit) : "r"(x));	\
+	asm("	subcc	%1,gr0,gr0,icc0		\n"	\
+	    "	ckne	icc0,cc4		\n"	\
+	    "	cscan.p	%1,gr0,%0	,cc4,#1	\n"	\
+	    "	csub	%0,%0,%0	,cc4,#0	\n"	\
+	    "   csub    %2,%0,%0	,cc4,#1	\n"	\
+	    : "=&r"(bit)				\
+	    : "r"(x), "r"(32)				\
+	    : "icc0", "cc4"				\
+	    );						\
 							\
-	bit ? 33 - bit : bit;				\
+	bit;						\
 })
 
 #include <asm-generic/bitops/fls64.h>

[PATCH 2/7] FRV: Implement fls64() [try #3]

[David Howells]

From: David Howells <dhowells@redhat.com>

Implement fls64() for FRV without recource to conditional jumps.

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

 include/asm-frv/bitops.h |   42 +++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 41 insertions(+), 1 deletions(-)

diff --git a/include/asm-frv/bitops.h b/include/asm-frv/bitops.h
index 97fb746..591eecc 100644
--- a/include/asm-frv/bitops.h
+++ b/include/asm-frv/bitops.h
@@ -186,7 +186,47 @@ ({							\
 	bit;						\
 })
 
-#include <asm-generic/bitops/fls64.h>
+/**
+ * fls64 - find last bit set in a 64-bit value
+ * @n: the value to search
+ *
+ * This is defined the same way as ffs:
+ * - return 64..1 to indicate bit 63..0 most significant bit set
+ * - return 0 to indicate no bits set
+ */
+static inline __attribute__((const))
+int fls64(u64 n)
+{
+	union {
+		u64 ll;
+		struct { u32 h, l; };
+	} _;
+	int bit, x, y;
+
+	_.ll = n;
+
+	asm("	subcc.p		%3,gr0,gr0,icc0		\n"
+	    "	subcc		%4,gr0,gr0,icc1		\n"
+	    "	ckne		icc0,cc4		\n"
+	    "	ckne		icc1,cc5		\n"
+	    "	norcr		cc4,cc5,cc6		\n"
+	    "	csub.p		%0,%0,%0	,cc6,1	\n"
+	    "	orcr		cc5,cc4,cc4		\n"
+	    "	andcr		cc4,cc5,cc4		\n"
+	    "	cscan.p		%3,gr0,%0	,cc4,0	\n"
+	    "   setlos		#64,%1			\n"
+	    "	cscan.p		%4,gr0,%0	,cc4,1	\n"
+	    "   setlos		#32,%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", "icc1", "cc4", "cc5", "cc6"
+	    );
+	return bit;
+
+}
+
 #include <asm-generic/bitops/sched.h>
 #include <asm-generic/bitops/hweight.h>
 

[PATCH 3/7] FRV: Optimise ffs() [try #3]

[David Howells]

From: David Howells <dhowells@redhat.com>

Optimise ffs(x) by using fls(x & x - 1) which we optimise to use the SCAN
instruction.

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

 include/asm-frv/bitops.h |   33 +++++++++++++++++++++++++++++++--
 1 files changed, 31 insertions(+), 2 deletions(-)

diff --git a/include/asm-frv/bitops.h b/include/asm-frv/bitops.h
index 591eecc..1f70d47 100644
--- a/include/asm-frv/bitops.h
+++ b/include/asm-frv/bitops.h
@@ -157,8 +157,6 @@ (__builtin_constant_p(nr) ? \
  __constant_test_bit((nr),(addr)) : \
  __test_bit((nr),(addr)))
 
-#include <asm-generic/bitops/ffs.h>
-#include <asm-generic/bitops/__ffs.h>
 #include <asm-generic/bitops/find.h>
 
 /**
@@ -227,6 +225,37 @@ int fls64(u64 n)
 
 }
 
+/**
+ * ffs - find first bit set
+ * @x: the word to search
+ *
+ * - return 32..1 to indicate bit 31..0 most least significant bit set
+ * - return 0 to indicate no bits set
+ */
+static inline __attribute__((const))
+int ffs(int x)
+{
+	/* Note: (x & -x) gives us a mask that is the least significant
+	 * (rightmost) 1-bit of the value in x.
+	 */
+	return fls(x & -x);
+}
+
+/**
+ * __ffs - find first bit set
+ * @x: the word to search
+ *
+ * - return 31..0 to indicate bit 31..0 most least significant bit set
+ * - if no bits are set in x, the result is undefined
+ */
+static inline __attribute__((const))
+int __ffs(unsigned long x)
+{
+	int bit;
+	asm("scan %1,gr0,%0" : "=r"(bit) : "r"(x & -x));
+	return 31 - bit;
+}
+
 #include <asm-generic/bitops/sched.h>
 #include <asm-generic/bitops/hweight.h>
 

[PATCH 4/7] Implement a general integer log2 facility in the kernel [try #3]

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

 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                         |  188 ++++++++++++++++++++++++++
 mm/page_alloc.c                              |    4 -
 10 files changed, 247 insertions(+), 26 deletions(-)

diff --git a/drivers/infiniband/hw/mthca/mthca_provider.c b/drivers/infiniband/hw/mthca/mthca_provider.c
index 265b1d1..413dd6d 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 2e8f6f3..bace21e 100644
--- a/drivers/infiniband/hw/mthca/mthca_qp.c
+++ b/drivers/infiniband/hw/mthca/mthca_qp.c
@@ -632,11 +632,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 b60a9d7..69d842b 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 31950a5..13aeeba 100644
--- a/drivers/infiniband/ulp/iser/iser_memory.c
+++ b/drivers/infiniband/ulp/iser/iser_memory.c
@@ -112,7 +112,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);
 
@@ -209,7 +209,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 681dea8..b4b4eae 100644
--- a/fs/ext2/super.c
+++ b/fs/ext2/super.c
@@ -548,8 +548,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.
@@ -784,9 +782,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 813d589..b088686 100644
--- a/fs/ext3/super.c
+++ b/fs/ext3/super.c
@@ -1294,8 +1294,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.
@@ -1543,8 +1541,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 851aa1b..e8c6c66 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>
 
@@ -154,14 +155,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..6ce81b7
--- /dev/null
+++ b/include/linux/log2.h
@@ -0,0 +1,188 @@
+/* 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()
+ */
+#ifndef ARCH_HAS_ILOG2_U32
+static inline __attribute__((const))
+int __ilog2_u32(u32 n)
+{
+	return fls(n) - 1;
+}
+#endif
+
+#ifndef ARCH_HAS_ILOG2_U64
+static inline __attribute__((const))
+int __ilog2_u64(u64 n)
+{
+	return fls64(n) - 1;
+}
+#endif
+
+/**
+ * ilog2_u32 - log of base 2 of 32-bit unsigned value
+ * @n - parameter
+ *
+ * constant-capable 32-bit log of base 2 calculation
+ * - this can be used to initialise global variables from constant data, hence
+ *   the massive ternary operator construction
+ */
+#define ilog2_u32(n)					\
+(						\
+	__builtin_constant_p(n) ? (		\
+		n < 1 ? ____ilog2_NaN() :	\
+		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()			\
+				   ) :		\
+	__ilog2_u32(n)				\
+ )
+
+/**
+ * ilog2_u64 - log of base 2 of 64-bit unsigned value
+ * @n - parameter
+ *
+ * constant-capable 64-bit log of base 2 calculation
+ * - this can be used to initialise global variables from constant data, hence
+ *   the massive ternary operator construction
+ */
+#define ilog2_u64(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()			\
+				   ) :		\
+	__ilog2_u64(n)				\
+ )
+
+/**
+ * ilog2 - log of base 2 of unsigned long value
+ * @n - parameter
+ *
+ * constant-capable unsigned long log of base 2 calculation
+ * - this can be used to initialise global variables from constant data
+ */
+#if BITS_PER_LONG == 32
+#define ilog2(n) ilog2_u32(n)
+#else
+#define ilog2(n) ilog2_u64(n)
+#endif
+
+#endif /* _LINUX_LOG2_H */
diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index 54a4f53..2ccb960 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -2420,7 +2420,7 @@ void *__init alloc_large_system_hash(con
 	if (numentries > max)
 		numentries = max;
 
-	log2qty = long_log2(numentries);
+	log2qty = ilog2(numentries);
 
 	do {
 		size = bucketsize << log2qty;
@@ -2442,7 +2442,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)

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

[Stephen Rothwell]

Hi David,

Just a small nit ...

On Wed, 13 Sep 2006 19:35:29 +0100 David Howells <dhowells@redhat.com> wrote:
>
> diff --git a/fs/ext2/super.c b/fs/ext2/super.c
> index 681dea8..b4b4eae 100644
> --- a/fs/ext2/super.c
> +++ b/fs/ext2/super.c
> @@ -784,9 +782,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));

While you are here, could you get rid of the spaces before the parentheses?

-- 
Cheers,
Stephen Rothwell                    sfr@canb.auug.org.au
http://www.canb.auug.org.au/~sfr/

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

[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 |   14 --------------
 include/linux/log2.h       |   45 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 45 insertions(+), 14 deletions(-)

diff --git a/include/asm-generic/page.h b/include/asm-generic/page.h
index a96b5d9..a7e374e 100644
--- a/include/asm-generic/page.h
+++ b/include/asm-generic/page.h
@@ -6,20 +6,6 @@ #ifndef __ASSEMBLY__
 
 #include <linux/compiler.h>
 
-/* Pure 2^n version of get_order */
-static __inline__ __attribute_const__ int get_order(unsigned long size)
-{
-	int order;
-
-	size = (size - 1) >> (PAGE_SHIFT - 1);
-	order = -1;
-	do {
-		size >>= 1;
-		order++;
-	} while (size);
-	return order;
-}
-
 #endif	/* __ASSEMBLY__ */
 #endif	/* __KERNEL__ */
 
diff --git a/include/linux/log2.h b/include/linux/log2.h
index 6ce81b7..88b7b0e 100644
--- a/include/linux/log2.h
+++ b/include/linux/log2.h
@@ -25,6 +25,7 @@ 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 ARCH_HAS_ILOG2_U32
 static inline __attribute__((const))
@@ -42,6 +43,36 @@ int __ilog2_u64(u64 n)
 }
 #endif
 
+/*
+ * 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);
+	order = -1;
+	do {
+		size >>= 1;
+		order++;
+	} while (size);
+	return order;
+#endif
+}
+#endif
+
 /**
  * ilog2_u32 - log of base 2 of 32-bit unsigned value
  * @n - parameter
@@ -185,4 +216,18 @@ #else
 #define ilog2(n) ilog2_u64(n)
 #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 /* _LINUX_LOG2_H */

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

[Stephen Rothwell]

Hi David,

On Wed, 13 Sep 2006 19:35:31 +0100 David Howells <dhowells@redhat.com> wrote:
>
> diff --git a/include/asm-generic/page.h b/include/asm-generic/page.h
> index a96b5d9..a7e374e 100644
> --- a/include/asm-generic/page.h
> +++ b/include/asm-generic/page.h
> @@ -6,20 +6,6 @@ #ifndef __ASSEMBLY__
>  
>  #include <linux/compiler.h>
>  
> -/* Pure 2^n version of get_order */
> -static __inline__ __attribute_const__ int get_order(unsigned long size)
> -{
> -	int order;
> -
> -	size = (size - 1) >> (PAGE_SHIFT - 1);
> -	order = -1;
> -	do {
> -		size >>= 1;
> -		order++;
> -	} while (size);
> -	return order;
> -}
> -
>  #endif	/* __ASSEMBLY__ */
>  #endif	/* __KERNEL__ */

After this patch, you don't need to include <linux/compiler.h> any more
(and, in fact, the file ends up essentially empty).  Is there a good
reason to move this function out of asm-generic/page.h?

-- 
Cheers,
Stephen Rothwell                    sfr@canb.auug.org.au
http://www.canb.auug.org.au/~sfr/

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

[David Howells]

Stephen Rothwell <sfr@canb.auug.org.au> wrote:

> After this patch, you don't need to include <linux/compiler.h> any more
> (and, in fact, the file ends up essentially empty).

True.  I could possibly delete the whole file, depending on who else has
designs on it.

> Is there a good reason to move this function out of asm-generic/page.h?

So that all the general log2-based functions are grouped together was what I
was thinking (at least their primary interfaces).

David

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

[Stephen Rothwell]

Hi David,

On Thu, 14 Sep 2006 12:52:04 +0100 David Howells <dhowells@redhat.com> wrote:
>
> Stephen Rothwell <sfr@canb.auug.org.au> wrote:
> 
> > After this patch, you don't need to include <linux/compiler.h> any more
> > (and, in fact, the file ends up essentially empty).
> 
> True.  I could possibly delete the whole file, depending on who else has
> designs on it.

I think the patch consolidating PAGE_SIZE may want it.

> > Is there a good reason to move this function out of asm-generic/page.h?
> 
> So that all the general log2-based functions are grouped together was what I
> was thinking (at least their primary interfaces).

Except the get_order() interface is purely related to pages (the fact
that you have reimplemented it using the log2-based functions is just an
implementation detail.

-- 
Cheers,
Stephen Rothwell                    sfr@canb.auug.org.au
http://www.canb.auug.org.au/~sfr/

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

[David Howells]

Stephen Rothwell <sfr@canb.auug.org.au> wrote:

> Except the get_order() interface is purely related to pages (the fact
> that you have reimplemented it using the log2-based functions is just an
> implementation detail.

Do you have a major objection to it moving to linux/log2.h (do you count the
one you've just raised as "major")?

I'd rather avoid including linux/log2.h or linux/kernel.h in asm/page.h, plus
asm-generic/page.h isn't used by all archs (though that's a minor point).

David

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

[Stephen Rothwell]

On Fri, 15 Sep 2006 15:42:42 +0100 David Howells <dhowells@redhat.com> wrote:
>
> Stephen Rothwell <sfr@canb.auug.org.au> wrote:
> 
> > Except the get_order() interface is purely related to pages (the fact
> > that you have reimplemented it using the log2-based functions is just an
> > implementation detail.
> 
> Do you have a major objection to it moving to linux/log2.h (do you count the
> one you've just raised as "major")?

I just think that things should be grouped according to the function they
provide (and not their implemetation) and get_order is part of the paging
API.

> I'd rather avoid including linux/log2.h or linux/kernel.h in asm/page.h, plus
> asm-generic/page.h isn't used by all archs (though that's a minor point).

You only have to include linux/log2.h in asm-generic/page.h.  Presumably
the architectures that don't use asm-generic/page.h won't want the new
implementation of get_order() either (I didn't keep the original patch).

Won't you need to include linux/log2.h in some places to get get_order(),
now?  And if I was needing the paging API, I am much more likely to look
for it in {linux,asm}/page.h than in linux/log2.h.

-- 
Cheers,
Stephen Rothwell                    sfr@canb.auug.org.au
http://www.canb.auug.org.au/~sfr/

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

[Andrew Morton]

On Wed, 13 Sep 2006 19:35:31 +0100
David Howells <dhowells@redhat.com> wrote:

> 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 |   14 --------------
>  include/linux/log2.h       |   45 ++++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 45 insertions(+), 14 deletions(-)
> 
> diff --git a/include/asm-generic/page.h b/include/asm-generic/page.h
> index a96b5d9..a7e374e 100644
> --- a/include/asm-generic/page.h
> +++ b/include/asm-generic/page.h
> @@ -6,20 +6,6 @@ #ifndef __ASSEMBLY__
>  
>  #include <linux/compiler.h>
>  
> -/* Pure 2^n version of get_order */
> -static __inline__ __attribute_const__ int get_order(unsigned long size)
> -{
> -	int order;
> -
> -	size = (size - 1) >> (PAGE_SHIFT - 1);
> -	order = -1;
> -	do {
> -		size >>= 1;
> -		order++;
> -	} while (size);
> -	return order;
> -}
> -
>  #endif	/* __ASSEMBLY__ */
>  #endif	/* __KERNEL__ */
>  
> diff --git a/include/linux/log2.h b/include/linux/log2.h
> index 6ce81b7..88b7b0e 100644
> --- a/include/linux/log2.h
> +++ b/include/linux/log2.h
> @@ -25,6 +25,7 @@ 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 ARCH_HAS_ILOG2_U32
>  static inline __attribute__((const))
> @@ -42,6 +43,36 @@ int __ilog2_u64(u64 n)
>  }
>  #endif
>  
> +/*
> + * 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

This breaks ia64:

In file included from include/asm/ptrace.h:234,
                 from include/asm/processor.h:19,
                 from include/linux/prefetch.h:14,
                 from include/linux/list.h:8,
                 from include/linux/wait.h:22,
                 from include/linux/fs.h:266,
                 from init/do_mounts_initrd.c:3:
include/asm/page.h:165: error: syntax error before '?' token
include/asm/page.h:170: warning: type defaults to `int' in declaration of `order'
include/asm/page.h:170: error: conflicting types for 'order'
include/asm/page.h:168: error: previous declaration of 'order' was here
include/asm/page.h:170: error: braced-group within expression allowed only inside a function
include/asm/page.h:170: warning: type defaults to `int' in declaration of `ia64_intri_res'

But for some reason putting ARCH_HAS_GET_ORDER into
include/asm-ia64/bitops.h and including linux/log2.h in
include/asm-ia64/page.h doesn't fix it.

I didn't pursue it further, because sprinkling ARCH_HAS_FOO things into
bitops.h(!) is all rather hacky.  Better to use CONFIG_* so they're always
visible and one knows where to go to find things.

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

[David Howells]

Andrew Morton <akpm@osdl.org> wrote:

> This breaks ia64:

Okay, drop it for now.

> But for some reason putting ARCH_HAS_GET_ORDER into
> include/asm-ia64/bitops.h and including linux/log2.h in
> include/asm-ia64/page.h doesn't fix it.

Seems I need to get an IA64 cross-compiler.

> I didn't pursue it further, because sprinkling ARCH_HAS_FOO things into
> bitops.h(!) is all rather hacky.  Better to use CONFIG_* so they're always
> visible and one knows where to go to find things.

But (1) they're not config options, and (2) there's plenty of precedent for
this sort of thing (ARCH_HAS_PREFETCH for example).

David

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

[Andrew Morton]

On Tue, 19 Sep 2006 10:08:17 +0100
David Howells <dhowells@redhat.com> wrote:

> > I didn't pursue it further, because sprinkling ARCH_HAS_FOO things into
> > bitops.h(!) is all rather hacky.  Better to use CONFIG_* so they're always
> > visible and one knows where to go to find things.
> 
> But (1) they're not config options,

Well they are, really.  "This architecture has its own get_order()".  It's
not *user* configurable, but neither is, say CONFIG_GENERIC_HARDIRQS.

The problem we have with the ARCH_HAS_FOO things is that there's never been
an include/asm/arch_has_foo.h in which to define them, so stuff gets
sprinkled all over the place.

> and (2) there's plenty of precedent for
> this sort of thing (ARCH_HAS_PREFETCH for example).

There's precedent both ways.  The advantages of doing it in config are

a) You know where to go to find it: arch/foo/Kconfig

b) It's always available, due to forced inclusion of config.h.

(I think I actually would prefer include/asm/arch_has_foo.h if we had it,
because it's lighter-weight.  But we don't)

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

[Christoph Hellwig]

On Tue, Sep 19, 2006 at 08:03:24AM -0700, Andrew Morton wrote:
> On Tue, 19 Sep 2006 10:08:17 +0100
> David Howells <dhowells@redhat.com> wrote:
> 
> > > I didn't pursue it further, because sprinkling ARCH_HAS_FOO things into
> > > bitops.h(!) is all rather hacky.  Better to use CONFIG_* so they're always
> > > visible and one knows where to go to find things.
> > 
> > But (1) they're not config options,
> 
> Well they are, really.  "This architecture has its own get_order()".  It's
> not *user* configurable, but neither is, say CONFIG_GENERIC_HARDIRQS.
> 
> The problem we have with the ARCH_HAS_FOO things is that there's never been
> an include/asm/arch_has_foo.h in which to define them, so stuff gets
> sprinkled all over the place.
> 
> > and (2) there's plenty of precedent for
> > this sort of thing (ARCH_HAS_PREFETCH for example).
> 
> There's precedent both ways.  The advantages of doing it in config are
> 
> a) You know where to go to find it: arch/foo/Kconfig
> 
> b) It's always available, due to forced inclusion of config.h.
> 
> (I think I actually would prefer include/asm/arch_has_foo.h if we had it,
> because it's lighter-weight.  But we don't)

That approach has the problem of not beeing available in the Kconfig
language and thus the Makefiles, so we can't compile files conditionally
on it.   Otherwise I'd say just add asm/config.h, include it automatically
and go ahead.

[PATCH 6/7] Alter roundup_pow_of_two() so that it can make use of ilog2() on a constant [try #3]

[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 e8c6c66..e5947fb 100644
--- a/include/linux/kernel.h
+++ b/include/linux/kernel.h
@@ -155,12 +155,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 88b7b0e..c7574a6 100644
--- a/include/linux/log2.h
+++ b/include/linux/log2.h
@@ -73,6 +73,15 @@ #endif
 }
 #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_u32 - log of base 2 of 32-bit unsigned value
  * @n - parameter
@@ -230,4 +239,21 @@ (									\
 	__get_order(n, PAGE_SHIFT)					\
  )
 
+/**
+ * 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 7/7] Provide ilog2() fallbacks for powerpc [try #3]

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

 include/asm-powerpc/bitops.h |   23 ++++++++++++++++++++++-
 1 files changed, 22 insertions(+), 1 deletions(-)

diff --git a/include/asm-powerpc/bitops.h b/include/asm-powerpc/bitops.h
index c341063..b6b1169 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,26 @@ static __inline__ int __ilog2(unsigned l
 	return BITS_PER_LONG - 1 - lz;
 }
 
+#define ARCH_HAS_ILOG2_U32
+static inline __attribute__((const))
+int __ilog2_u32(u32 n)
+{
+	int bit;
+	asm ("cntlzw %0,%1" : "=r" (bit) : "r" (n));
+	return 31 - bit;
+}
+
+#ifdef __powerpc64__
+#define ARCH_HAS_ILOG2_U64
+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