Implement get_count_order in lttng utils

Imported from Userspace RCU rculfhash.c.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

diff --git a/src/bin/lttng/utils.c b/src/bin/lttng/utils.c
index b7f5170aad76bf66518e2f8aefb54b622e31441a..94c4527d97ff293029f99dbdca79e3cbf6956caa 100644 (file)
--- a/src/bin/lttng/utils.c
+++ b/src/bin/lttng/utils.c
@@ -77,3 +77,155 @@ void list_cmd_options(FILE *ofp, struct poptOption *options)
                }
        }
 }
+
+/*
+ * fls: returns the position of the most significant bit.
+ * Returns 0 if no bit is set, else returns the position of the most
+ * significant bit (from 1 to 32 on 32-bit, from 1 to 64 on 64-bit).
+ */
+#if defined(__i386) || defined(__x86_64)
+static inline
+unsigned int fls_u32(uint32_t x)
+{
+       int r;
+
+       asm("bsrl %1,%0\n\t"
+           "jnz 1f\n\t"
+           "movl $-1,%0\n\t"
+           "1:\n\t"
+           : "=r" (r) : "rm" (x));
+       return r + 1;
+}
+#define HAS_FLS_U32
+#endif
+
+#if defined(__x86_64)
+static inline
+unsigned int fls_u64(uint64_t x)
+{
+       long r;
+
+       asm("bsrq %1,%0\n\t"
+           "jnz 1f\n\t"
+           "movq $-1,%0\n\t"
+           "1:\n\t"
+           : "=r" (r) : "rm" (x));
+       return r + 1;
+}
+#define HAS_FLS_U64
+#endif
+
+#ifndef HAS_FLS_U64
+static __attribute__((unused))
+unsigned int fls_u64(uint64_t x)
+{
+       unsigned int r = 64;
+
+       if (!x)
+               return 0;
+
+       if (!(x & 0xFFFFFFFF00000000ULL)) {
+               x <<= 32;
+               r -= 32;
+       }
+       if (!(x & 0xFFFF000000000000ULL)) {
+               x <<= 16;
+               r -= 16;
+       }
+       if (!(x & 0xFF00000000000000ULL)) {
+               x <<= 8;
+               r -= 8;
+       }
+       if (!(x & 0xF000000000000000ULL)) {
+               x <<= 4;
+               r -= 4;
+       }
+       if (!(x & 0xC000000000000000ULL)) {
+               x <<= 2;
+               r -= 2;
+       }
+       if (!(x & 0x8000000000000000ULL)) {
+               x <<= 1;
+               r -= 1;
+       }
+       return r;
+}
+#endif
+
+#ifndef HAS_FLS_U32
+static __attribute__((unused))
+unsigned int fls_u32(uint32_t x)
+{
+       unsigned int r = 32;
+
+       if (!x)
+               return 0;
+       if (!(x & 0xFFFF0000U)) {
+               x <<= 16;
+               r -= 16;
+       }
+       if (!(x & 0xFF000000U)) {
+               x <<= 8;
+               r -= 8;
+       }
+       if (!(x & 0xF0000000U)) {
+               x <<= 4;
+               r -= 4;
+       }
+       if (!(x & 0xC0000000U)) {
+               x <<= 2;
+               r -= 2;
+       }
+       if (!(x & 0x80000000U)) {
+               x <<= 1;
+               r -= 1;
+       }
+       return r;
+}
+#endif
+
+static
+unsigned int fls_ulong(unsigned long x)
+{
+#if (CAA_BITS_PER_LONG == 32)
+       return fls_u32(x);
+#else
+       return fls_u64(x);
+#endif
+}
+
+/*
+ * Return the minimum order for which x <= (1UL << order).
+ * Return -1 if x is 0.
+ */
+int get_count_order_u32(uint32_t x)
+{
+       if (!x)
+               return -1;
+
+       return fls_u32(x - 1);
+}
+
+/*
+ * Return the minimum order for which x <= (1UL << order).
+ * Return -1 if x is 0.
+ */
+int get_count_order_u64(uint64_t x)
+{
+       if (!x)
+               return -1;
+
+       return fls_u64(x - 1);
+}
+
+/*
+ * Return the minimum order for which x <= (1UL << order).
+ * Return -1 if x is 0.
+ */
+int get_count_order_ulong(unsigned long x)
+{
+       if (!x)
+               return -1;
+
+       return fls_ulong(x - 1);
+}

diff --git a/src/bin/lttng/utils.h b/src/bin/lttng/utils.h
index 9f7bfcca1053544e5ebad5d0b52b36f3943ff97a..57bec1250fe1ea237b0e6913b0160bd83b3c646c 100644 (file)
--- a/src/bin/lttng/utils.h
+++ b/src/bin/lttng/utils.h
@@ -23,4 +23,22 @@
 char *get_session_name(void);
 void list_cmd_options(FILE *ofp, struct poptOption *options);
 
+/*
+ * Return the minimum order for which x <= (1UL << order).
+ * Return -1 if x is 0.
+ */
+int get_count_order_u32(uint32_t x);
+
+/*
+ * Return the minimum order for which x <= (1UL << order).
+ * Return -1 if x is 0.
+ */
+int get_count_order_u64(uint64_t x);
+
+/*
+ * Return the minimum order for which x <= (1UL << order).
+ * Return -1 if x is 0.
+ */
+int get_count_order_ulong(unsigned long x);
+
 #endif /* _LTTNG_UTILS_H */