git: b0056b31e900 - main - libkern: add ilog2 macro
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Mon, 03 Jun 2024 16:54:51 UTC
The branch main has been updated by dougm:
URL: https://cgit.FreeBSD.org/src/commit/?id=b0056b31e90029553894d17c441cbb2c06d31412
commit b0056b31e90029553894d17c441cbb2c06d31412
Author: Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2024-06-03 16:37:55 +0000
Commit: Doug Moore <dougm@FreeBSD.org>
CommitDate: 2024-06-03 16:37:55 +0000
libkern: add ilog2 macro
The kernel source contains several definitions of an ilog2 function;
some are slower than necessary, and one of them is incorrect.
Elimininate them all and define an ilog2 macro in libkern to replace
them, in a way that is fast, correct for all argument types, and, in a
GENERIC kernel, includes a check for an invalid zero parameter.
Folks at Microsoft have verified that having a correct ilog2
definition for their MANA driver doesn't break it.
Reviewed by: alc, markj, mhorne (older version), jhibbits (older version)
Differential Revision: https://reviews.freebsd.org/D45170
Differential Revision: https://reviews.freebsd.org/D45235
---
sys/amd64/include/cpufunc.h | 4 -
sys/arm64/iommu/smmu.c | 9 --
sys/compat/linuxkpi/common/include/linux/log2.h | 73 ----------------
sys/dev/bxe/bxe.h | 10 ---
sys/dev/bxe/ecore_sp.h | 2 +-
sys/dev/cxgbe/osdep.h | 8 --
sys/dev/enetc/enetc_hw.h | 1 -
sys/dev/mana/gdma_util.h | 9 --
sys/dev/qat/qat/qat_ocf.c | 2 +-
sys/i386/include/cpufunc.h | 9 --
sys/powerpc/booke/pmap.c | 1 -
sys/powerpc/booke/pmap_32.c | 13 ---
sys/powerpc/booke/pmap_64.c | 13 ---
sys/sys/libkern.h | 106 ++++++++++++++++++++++++
14 files changed, 108 insertions(+), 152 deletions(-)
diff --git a/sys/amd64/include/cpufunc.h b/sys/amd64/include/cpufunc.h
index 44d93494d830..62e782304fca 100644
--- a/sys/amd64/include/cpufunc.h
+++ b/sys/amd64/include/cpufunc.h
@@ -65,10 +65,6 @@ breakpoint(void)
#define bsfq(mask) __builtin_ctzl(mask)
-#define bsrl(mask) (__builtin_clz(mask) ^ 0x1f)
-
-#define bsrq(mask) (__builtin_clzl(mask) ^ 0x3f)
-
static __inline void
clflush(u_long addr)
{
diff --git a/sys/arm64/iommu/smmu.c b/sys/arm64/iommu/smmu.c
index 1d1996a69027..76a7d29dc2db 100644
--- a/sys/arm64/iommu/smmu.c
+++ b/sys/arm64/iommu/smmu.c
@@ -309,15 +309,6 @@ smmu_write_ack(struct smmu_softc *sc, uint32_t reg,
return (0);
}
-static inline int
-ilog2(long x)
-{
-
- KASSERT(x > 0 && powerof2(x), ("%s: invalid arg %ld", __func__, x));
-
- return (flsl(x) - 1);
-}
-
static int
smmu_init_queue(struct smmu_softc *sc, struct smmu_queue *q,
uint32_t prod_off, uint32_t cons_off, uint32_t dwords)
diff --git a/sys/compat/linuxkpi/common/include/linux/log2.h b/sys/compat/linuxkpi/common/include/linux/log2.h
index 27e91a8bdbe0..2d54c75c7c23 100644
--- a/sys/compat/linuxkpi/common/include/linux/log2.h
+++ b/sys/compat/linuxkpi/common/include/linux/log2.h
@@ -51,79 +51,6 @@ rounddown_pow_of_two(unsigned long x)
return (1UL << (flsl(x) - 1));
}
-#define ilog2(n) \
-( \
- __builtin_constant_p(n) ? ( \
- (n) < 1 ? -1 : \
- (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 : \
- -1) : \
- (sizeof(n) <= 4) ? \
- fls((u32)(n)) - 1 : flsll((u64)(n)) - 1 \
-)
-
#define order_base_2(x) ilog2(roundup_pow_of_two(x))
#endif /* _LINUXKPI_LINUX_LOG2_H_ */
diff --git a/sys/dev/bxe/bxe.h b/sys/dev/bxe/bxe.h
index 0c7e6232dbdb..79d2792f7d6f 100644
--- a/sys/dev/bxe/bxe.h
+++ b/sys/dev/bxe/bxe.h
@@ -126,16 +126,6 @@
#ifndef roundup
#define roundup(x, y) ((((x) + ((y) - 1)) / (y)) * (y))
#endif
-#ifndef ilog2
-static inline
-int bxe_ilog2(int x)
-{
- int log = 0;
- while (x >>= 1) log++;
- return (log);
-}
-#define ilog2(x) bxe_ilog2(x)
-#endif
#include "ecore_sp.h"
diff --git a/sys/dev/bxe/ecore_sp.h b/sys/dev/bxe/ecore_sp.h
index f39c908f7530..917f27549c1b 100644
--- a/sys/dev/bxe/ecore_sp.h
+++ b/sys/dev/bxe/ecore_sp.h
@@ -159,7 +159,7 @@ typedef struct mtx ECORE_MUTEX_SPIN;
#define ECORE_FREE(_s, _buf, _size) free(_buf, M_TEMP)
#define SC_ILT(sc) ((sc)->ilt)
-#define ILOG2(x) bxe_ilog2(x)
+#define ILOG2(x) ilog2(x)
#define ECORE_ILT_ZALLOC(x, y, size) \
do { \
diff --git a/sys/dev/cxgbe/osdep.h b/sys/dev/cxgbe/osdep.h
index 39675339dd2c..b8692692fd43 100644
--- a/sys/dev/cxgbe/osdep.h
+++ b/sys/dev/cxgbe/osdep.h
@@ -130,14 +130,6 @@ typedef boolean_t bool;
#define PCI_EXP_LNKSTA_NLW PCIEM_LINK_STA_WIDTH
#define PCI_EXP_DEVCTL2 PCIER_DEVICE_CTL2
-static inline int
-ilog2(long x)
-{
- KASSERT(x > 0 && powerof2(x), ("%s: invalid arg %ld", __func__, x));
-
- return (flsl(x) - 1);
-}
-
static inline char *
strstrip(char *s)
{
diff --git a/sys/dev/enetc/enetc_hw.h b/sys/dev/enetc/enetc_hw.h
index 507c4657453d..323d5529f50a 100644
--- a/sys/dev/enetc/enetc_hw.h
+++ b/sys/dev/enetc/enetc_hw.h
@@ -9,7 +9,6 @@
#define BIT(x) (1UL << (x))
#define GENMASK(h, l) (((~0U) - (1U << (l)) + 1) & (~0U >> (32 - 1 - (h))))
-#define ilog2(x) (flsl(x) - 1)
#define PCI_VENDOR_FREESCALE 0x1957
diff --git a/sys/dev/mana/gdma_util.h b/sys/dev/mana/gdma_util.h
index 822c831b9d70..37c2653d5ec9 100644
--- a/sys/dev/mana/gdma_util.h
+++ b/sys/dev/mana/gdma_util.h
@@ -170,15 +170,6 @@ find_first_zero_bit(const unsigned long *p, unsigned long max)
return (max);
}
-static inline unsigned long
-ilog2(unsigned long x)
-{
- unsigned long log = x;
- while (x >>= 1)
- log++;
- return (log);
-}
-
static inline unsigned long
roundup_pow_of_two(unsigned long x)
{
diff --git a/sys/dev/qat/qat/qat_ocf.c b/sys/dev/qat/qat/qat_ocf.c
index 8958c7b82e49..b25135b6a678 100644
--- a/sys/dev/qat/qat/qat_ocf.c
+++ b/sys/dev/qat/qat/qat_ocf.c
@@ -517,7 +517,7 @@ qat_ocf_session_init(device_t dev,
M_NOWAIT,
0,
~1UL,
- 1 << (bsrl(sessionCtxSize - 1) + 1),
+ 1 << (ilog2(sessionCtxSize - 1) + 1),
0);
if (NULL == sessionCtx) {
device_printf(dev, "unable to allocate memory for session\n");
diff --git a/sys/i386/include/cpufunc.h b/sys/i386/include/cpufunc.h
index bf643e6da21f..4bed57b5afbf 100644
--- a/sys/i386/include/cpufunc.h
+++ b/sys/i386/include/cpufunc.h
@@ -63,15 +63,6 @@ bsfl(u_int mask)
return (result);
}
-static __inline __pure2 u_int
-bsrl(u_int mask)
-{
- u_int result;
-
- __asm("bsrl %1,%0" : "=r" (result) : "rm" (mask) : "cc");
- return (result);
-}
-
static __inline void
clflush(u_long addr)
{
diff --git a/sys/powerpc/booke/pmap.c b/sys/powerpc/booke/pmap.c
index fe84a2a3c213..9f96255ea00e 100644
--- a/sys/powerpc/booke/pmap.c
+++ b/sys/powerpc/booke/pmap.c
@@ -239,7 +239,6 @@ static __inline uint32_t tlb_calc_wimg(vm_paddr_t pa, vm_memattr_t ma);
static vm_size_t tsize2size(unsigned int);
static unsigned int size2tsize(vm_size_t);
-static unsigned long ilog2(unsigned long);
static void set_mas4_defaults(void);
diff --git a/sys/powerpc/booke/pmap_32.c b/sys/powerpc/booke/pmap_32.c
index 580c54c3642f..efeefb6a91c5 100644
--- a/sys/powerpc/booke/pmap_32.c
+++ b/sys/powerpc/booke/pmap_32.c
@@ -116,7 +116,6 @@ static unsigned int kernel_ptbls; /* Number of KVA ptbls. */
#define VM_MAPDEV_BASE ((vm_offset_t)VM_MAXUSER_ADDRESS + PAGE_SIZE)
static void tid_flush(tlbtid_t tid);
-static unsigned long ilog2(unsigned long);
/**************************************************************************/
/* Page table management */
@@ -931,18 +930,6 @@ mmu_booke_quick_remove_page(vm_offset_t addr)
/* TID handling */
/**************************************************************************/
-/*
- * Return the largest uint value log such that 2^log <= num.
- */
-static unsigned long
-ilog2(unsigned long num)
-{
- long lz;
-
- __asm ("cntlzw %0, %1" : "=r" (lz) : "r" (num));
- return (31 - lz);
-}
-
/*
* Invalidate all TLB0 entries which match the given TID. Note this is
* dedicated for cases when invalidations should NOT be propagated to other
diff --git a/sys/powerpc/booke/pmap_64.c b/sys/powerpc/booke/pmap_64.c
index 802f37e921a4..affa08ebee3f 100644
--- a/sys/powerpc/booke/pmap_64.c
+++ b/sys/powerpc/booke/pmap_64.c
@@ -125,7 +125,6 @@ static pte_t ****kernel_ptbl_root;
#define VM_MAPDEV_PA_MAX 0x4000000000000000 /* Don't encroach on DMAP */
static void tid_flush(tlbtid_t tid);
-static unsigned long ilog2(unsigned long);
/**************************************************************************/
/* Page table management */
@@ -746,18 +745,6 @@ mmu_booke_quick_remove_page(vm_offset_t addr)
/* TID handling */
/**************************************************************************/
-/*
- * Return the largest uint value log such that 2^log <= num.
- */
-static unsigned long
-ilog2(unsigned long num)
-{
- long lz;
-
- __asm ("cntlzd %0, %1" : "=r" (lz) : "r" (num));
- return (63 - lz);
-}
-
/*
* Invalidate all TLB0 entries which match the given TID. Note this is
* dedicated for cases when invalidations should NOT be propagated to other
diff --git a/sys/sys/libkern.h b/sys/sys/libkern.h
index 6fbb97e48dac..84d982c43a76 100644
--- a/sys/sys/libkern.h
+++ b/sys/sys/libkern.h
@@ -186,6 +186,112 @@ flsll(long long mask)
8 * sizeof(mask) - __builtin_clzll((unsigned long long)mask));
}
+static __inline __pure2 int
+ilog2_int(int n)
+{
+
+ MPASS(n != 0);
+ return (8 * sizeof(n) - 1 - __builtin_clz((u_int)n));
+}
+
+static __inline __pure2 int
+ilog2_long(long n)
+{
+
+ MPASS(n != 0);
+ return (8 * sizeof(n) - 1 - __builtin_clzl((u_long)n));
+}
+
+static __inline __pure2 int
+ilog2_long_long(long long n)
+{
+
+ MPASS(n != 0);
+ return (8 * sizeof(n) - 1 -
+ __builtin_clzll((unsigned long long)n));
+}
+
+#define ilog2_var(n) \
+ _Generic((n), \
+ default: ilog2_int, \
+ long: ilog2_long, \
+ unsigned long: ilog2_long, \
+ long long: ilog2_long_long, \
+ unsigned long long: ilog2_long_long \
+ )(n)
+
+#define ilog2(n) \
+( \
+ __builtin_constant_p(n) ? ( \
+ (n) < 1 ? -1 : \
+ (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 : \
+ -1) : \
+ ilog2_var(n) \
+)
+
#define bitcount64(x) __bitcount64((uint64_t)(x))
#define bitcount32(x) __bitcount32((uint32_t)(x))
#define bitcount16(x) __bitcount16((uint16_t)(x))