Merge pull request #21531 from keszybz/log2-tables

Optimize log2 tables

11 files changed, 188 insertions, 115 deletions

diff --git a/src/basic/capability-util.c b/src/basic/capability-util.c
index b31a9cb211..fa74b5b9c6 100644
--- a/src/basic/capability-util.c
+++ b/src/basic/capability-util.c
@@ -336,7 +336,7 @@ int drop_privileges(uid_t uid, gid_t gid, uint64_t keep_capabilities) {
 
         /* Now upgrade the permitted caps we still kept to effective caps */
         if (keep_capabilities != 0) {
-                cap_value_t bits[u64log2(keep_capabilities) + 1];
+                cap_value_t bits[log2u64(keep_capabilities) + 1];
                 _cleanup_cap_free_ cap_t d = NULL;
                 unsigned i, j = 0;
 
diff --git a/src/basic/util.h b/src/basic/util.h
index b6c51c036e..f5434c9641 100644
--- a/src/basic/util.h
+++ b/src/basic/util.h
@@ -22,11 +22,20 @@ void in_initrd_force(bool value);
 
 int on_ac_power(void);
 
-static inline unsigned u64log2(uint64_t n) {
+/* Note: log2(0) == log2(1) == 0 here and below. */
+
+#define CONST_LOG2ULL(x) ((x) > 1 ? (unsigned) __builtin_clzll(x) ^ 63U : 0)
+#define NONCONST_LOG2ULL(x) ({                                     \
+                unsigned long long _x = (x);                       \
+                _x > 1 ? (unsigned) __builtin_clzll(_x) ^ 63U : 0; \
+        })
+#define LOG2ULL(x) __builtin_choose_expr(__builtin_constant_p(x), CONST_LOG2ULL(x), NONCONST_LOG2ULL(x))
+
+static inline unsigned log2u64(uint64_t x) {
 #if __SIZEOF_LONG_LONG__ == 8
-        return (n > 1) ? (unsigned) __builtin_clzll(n) ^ 63U : 0;
+        return LOG2ULL(x);
 #else
-#error "Wut?"
+#  error "Wut?"
 #endif
 }
 
@@ -34,26 +43,27 @@ static inline unsigned u32ctz(uint32_t n) {
 #if __SIZEOF_INT__ == 4
         return n != 0 ? __builtin_ctz(n) : 32;
 #else
-#error "Wut?"
+#  error "Wut?"
 #endif
 }
 
-static inline unsigned log2i(int x) {
-        assert(x > 0);
+#define CONST_LOG2U(x) ((x) > 1 ? __SIZEOF_INT__ * 8 - __builtin_clz(x) - 1 : 0)
+#define NONCONST_LOG2U(x) ({                                             \
+                unsigned _x = (x);                                       \
+                _x > 1 ? __SIZEOF_INT__ * 8 - __builtin_clz(_x) - 1 : 0; \
+        })
+#define LOG2U(x) __builtin_choose_expr(__builtin_constant_p(x), CONST_LOG2U(x), NONCONST_LOG2U(x))
 
-        return __SIZEOF_INT__ * 8 - __builtin_clz(x) - 1;
+static inline unsigned log2i(int x) {
+        return LOG2U(x);
 }
 
 static inline unsigned log2u(unsigned x) {
-        assert(x > 0);
-
-        return sizeof(unsigned) * 8 - __builtin_clz(x) - 1;
+        return LOG2U(x);
 }
 
 static inline unsigned log2u_round_up(unsigned x) {
-        assert(x > 0);
-
-        if (x == 1)
+        if (x <= 1)
                 return 0;
 
         return log2u(x - 1) + 1;
diff --git a/src/journal/journald-rate-limit.c b/src/journal/journald-rate-limit.c
index f464b6e0d8..8accd7c7f5 100644
--- a/src/journal/journald-rate-limit.c
+++ b/src/journal/journald-rate-limit.c
@@ -162,7 +162,7 @@ static unsigned burst_modulate(unsigned burst, uint64_t available) {
         /* Modulates the burst rate a bit with the amount of available
          * disk space */
 
-        k = u64log2(available);
+        k = log2u64(available);
 
         /* 1MB */
         if (k <= 20)
diff --git a/src/libsystemd/sd-event/sd-event.c b/src/libsystemd/sd-event/sd-event.c
index 8d21627b3f..3c916f2466 100644
--- a/src/libsystemd/sd-event/sd-event.c
+++ b/src/libsystemd/sd-event/sd-event.c
@@ -4218,7 +4218,7 @@ _public_ int sd_event_run(sd_event *e, uint64_t timeout) {
 
                 this_run = now(CLOCK_MONOTONIC);
 
-                l = u64log2(this_run - e->last_run_usec);
+                l = log2u64(this_run - e->last_run_usec);
                 assert(l < ELEMENTSOF(e->delays));
                 e->delays[l]++;
 
diff --git a/src/network/meson.build b/src/network/meson.build
index 9247734c75..cfa16a8ecf 100644
--- a/src/network/meson.build
+++ b/src/network/meson.build
@@ -284,6 +284,12 @@ tests += [
          [],
          network_includes],
 
+        [['src/network/test-networkd-util.c'],
+         [libnetworkd_core,
+          libsystemd_network],
+         [],
+         network_includes],
+
         [['src/network/test-network.c'],
          [libnetworkd_core,
           libsystemd_network],
diff --git a/src/network/networkd-address.c b/src/network/networkd-address.c
index 701bffe5ee..826b061f24 100644
--- a/src/network/networkd-address.c
+++ b/src/network/networkd-address.c
@@ -26,33 +26,30 @@
 
 int address_flags_to_string_alloc(uint32_t flags, int family, char **ret) {
         _cleanup_free_ char *str = NULL;
-        static const struct {
-                uint32_t flag;
-                const char *name;
-        } map[] = {
-                { IFA_F_SECONDARY,      "secondary"                }, /* This is also called "temporary" for ipv6. */
-                { IFA_F_NODAD,          "nodad"                    },
-                { IFA_F_OPTIMISTIC,     "optimistic"               },
-                { IFA_F_DADFAILED,      "dadfailed"                },
-                { IFA_F_HOMEADDRESS,    "home-address"             },
-                { IFA_F_DEPRECATED,     "deprecated"               },
-                { IFA_F_TENTATIVE,      "tentative"                },
-                { IFA_F_PERMANENT,      "permanent"                },
-                { IFA_F_MANAGETEMPADDR, "manage-temporary-address" },
-                { IFA_F_NOPREFIXROUTE,  "no-prefixroute"           },
-                { IFA_F_MCAUTOJOIN,     "auto-join"                },
-                { IFA_F_STABLE_PRIVACY, "stable-privacy"           },
+        static const char* map[] = {
+                [LOG2U(IFA_F_SECONDARY)]      = "secondary", /* This is also called "temporary" for ipv6. */
+                [LOG2U(IFA_F_NODAD)]          = "nodad",
+                [LOG2U(IFA_F_OPTIMISTIC)]     = "optimistic",
+                [LOG2U(IFA_F_DADFAILED)]      = "dadfailed",
+                [LOG2U(IFA_F_HOMEADDRESS)]    = "home-address",
+                [LOG2U(IFA_F_DEPRECATED)]     = "deprecated",
+                [LOG2U(IFA_F_TENTATIVE)]      = "tentative",
+                [LOG2U(IFA_F_PERMANENT)]      = "permanent",
+                [LOG2U(IFA_F_MANAGETEMPADDR)] = "manage-temporary-address",
+                [LOG2U(IFA_F_NOPREFIXROUTE)]  = "no-prefixroute",
+                [LOG2U(IFA_F_MCAUTOJOIN)]     = "auto-join",
+                [LOG2U(IFA_F_STABLE_PRIVACY)] = "stable-privacy",
         };
 
         assert(IN_SET(family, AF_INET, AF_INET6));
         assert(ret);
 
         for (size_t i = 0; i < ELEMENTSOF(map); i++)
-                if (flags & map[i].flag &&
-                    !strextend_with_separator(
-                                &str, ",",
-                                map[i].flag == IFA_F_SECONDARY && family == AF_INET6 ? "temporary" : map[i].name))
-                        return -ENOMEM;
+                if (FLAGS_SET(flags, 1 << i) && map[i])
+                        if (!strextend_with_separator(
+                                            &str, ",",
+                                            family == AF_INET6 && (1 << i) == IFA_F_SECONDARY ? "temporary" : map[i]))
+                                return -ENOMEM;
 
         *ret = TAKE_PTR(str);
         return 0;
diff --git a/src/network/networkd-link.c b/src/network/networkd-link.c
index 3489dfa0d2..4df3e19220 100644
--- a/src/network/networkd-link.c
+++ b/src/network/networkd-link.c
@@ -2660,50 +2660,47 @@ int link_call_getlink(Link *link, link_netlink_message_handler_t callback) {
 }
 
 static const char* const link_state_table[_LINK_STATE_MAX] = {
-        [LINK_STATE_PENDING] = "pending",
+        [LINK_STATE_PENDING]     = "pending",
         [LINK_STATE_INITIALIZED] = "initialized",
         [LINK_STATE_CONFIGURING] = "configuring",
-        [LINK_STATE_CONFIGURED] = "configured",
-        [LINK_STATE_UNMANAGED] = "unmanaged",
-        [LINK_STATE_FAILED] = "failed",
-        [LINK_STATE_LINGER] = "linger",
+        [LINK_STATE_CONFIGURED]  = "configured",
+        [LINK_STATE_UNMANAGED]   = "unmanaged",
+        [LINK_STATE_FAILED]      = "failed",
+        [LINK_STATE_LINGER]      = "linger",
 };
 
 DEFINE_STRING_TABLE_LOOKUP(link_state, LinkState);
 
 int link_flags_to_string_alloc(uint32_t flags, char **ret) {
         _cleanup_free_ char *str = NULL;
-        static const struct {
-                uint32_t flag;
-                const char *name;
-        } map[] = {
-                { IFF_UP,          "up"             }, /* interface is up. */
-                { IFF_BROADCAST,   "broadcast"      }, /* broadcast address valid.*/
-                { IFF_DEBUG,       "debug"          }, /* turn on debugging. */
-                { IFF_LOOPBACK,    "loopback"       }, /* interface is a loopback net. */
-                { IFF_POINTOPOINT, "point-to-point" }, /* interface has p-p link. */
-                { IFF_NOTRAILERS,  "no-trailers"    }, /* avoid use of trailers. */
-                { IFF_RUNNING,     "running"        }, /* interface RFC2863 OPER_UP. */
-                { IFF_NOARP,       "no-arp"         }, /* no ARP protocol. */
-                { IFF_PROMISC,     "promiscuous"    }, /* receive all packets. */
-                { IFF_ALLMULTI,    "all-multicast"  }, /* receive all multicast packets. */
-                { IFF_MASTER,      "master"         }, /* master of a load balancer. */
-                { IFF_SLAVE,       "slave"          }, /* slave of a load balancer. */
-                { IFF_MULTICAST,   "multicast"      }, /* supports multicast.*/
-                { IFF_PORTSEL,     "portsel"        }, /* can set media type. */
-                { IFF_AUTOMEDIA,   "auto-media"     }, /* auto media select active. */
-                { IFF_DYNAMIC,     "dynamic"        }, /* dialup device with changing addresses. */
-                { IFF_LOWER_UP,    "lower-up"       }, /* driver signals L1 up. */
-                { IFF_DORMANT,     "dormant"        }, /* driver signals dormant. */
-                { IFF_ECHO,        "echo"           }, /* echo sent packets. */
+        static const char* map[] = {
+                [LOG2U(IFF_UP)]          = "up",             /* interface is up. */
+                [LOG2U(IFF_BROADCAST)]   = "broadcast",      /* broadcast address valid.*/
+                [LOG2U(IFF_DEBUG)]       = "debug",          /* turn on debugging. */
+                [LOG2U(IFF_LOOPBACK)]    = "loopback",       /* interface is a loopback net. */
+                [LOG2U(IFF_POINTOPOINT)] = "point-to-point", /* interface has p-p link. */
+                [LOG2U(IFF_NOTRAILERS)]  = "no-trailers",    /* avoid use of trailers. */
+                [LOG2U(IFF_RUNNING)]     = "running",        /* interface RFC2863 OPER_UP. */
+                [LOG2U(IFF_NOARP)]       = "no-arp",         /* no ARP protocol. */
+                [LOG2U(IFF_PROMISC)]     = "promiscuous",    /* receive all packets. */
+                [LOG2U(IFF_ALLMULTI)]    = "all-multicast",  /* receive all multicast packets. */
+                [LOG2U(IFF_MASTER)]      = "master",         /* master of a load balancer. */
+                [LOG2U(IFF_SLAVE)]       = "slave",          /* slave of a load balancer. */
+                [LOG2U(IFF_MULTICAST)]   = "multicast",      /* supports multicast.*/
+                [LOG2U(IFF_PORTSEL)]     = "portsel",        /* can set media type. */
+                [LOG2U(IFF_AUTOMEDIA)]   = "auto-media",     /* auto media select active. */
+                [LOG2U(IFF_DYNAMIC)]     = "dynamic",        /* dialup device with changing addresses. */
+                [LOG2U(IFF_LOWER_UP)]    = "lower-up",       /* driver signals L1 up. */
+                [LOG2U(IFF_DORMANT)]     = "dormant",        /* driver signals dormant. */
+                [LOG2U(IFF_ECHO)]        = "echo",           /* echo sent packets. */
         };
 
         assert(ret);
 
         for (size_t i = 0; i < ELEMENTSOF(map); i++)
-                if (flags & map[i].flag &&
-                    !strextend_with_separator(&str, ",", map[i].name))
-                        return -ENOMEM;
+                if (FLAGS_SET(flags, 1 << i) && map[i])
+                        if (!strextend_with_separator(&str, ",", map[i]))
+                                return -ENOMEM;
 
         *ret = TAKE_PTR(str);
         return 0;
diff --git a/src/network/networkd-route-util.c b/src/network/networkd-route-util.c
index c1ab437fac..c57adbe0ab 100644
--- a/src/network/networkd-route-util.c
+++ b/src/network/networkd-route-util.c
@@ -221,25 +221,22 @@ DEFINE_STRING_TABLE_LOOKUP_WITH_FALLBACK(route_protocol_full, int, UINT8_MAX);
 
 int route_flags_to_string_alloc(uint32_t flags, char **ret) {
         _cleanup_free_ char *str = NULL;
-        static const struct {
-                uint32_t flag;
-                const char *name;
-        } map[] = {
-                { RTNH_F_DEAD,       "dead"       }, /* Nexthop is dead (used by multipath) */
-                { RTNH_F_PERVASIVE,  "pervasive"  }, /* Do recursive gateway lookup */
-                { RTNH_F_ONLINK,     "onlink"     }, /* Gateway is forced on link */
-                { RTNH_F_OFFLOAD,    "offload"    }, /* Nexthop is offloaded */
-                { RTNH_F_LINKDOWN,   "linkdown"   }, /* carrier-down on nexthop */
-                { RTNH_F_UNRESOLVED, "unresolved" }, /* The entry is unresolved (ipmr) */
-                { RTNH_F_TRAP,       "trap"       }, /* Nexthop is trapping packets */
+        static const char* map[] = {
+                [LOG2U(RTNH_F_DEAD)]       = "dead",       /* Nexthop is dead (used by multipath) */
+                [LOG2U(RTNH_F_PERVASIVE)]  = "pervasive",  /* Do recursive gateway lookup */
+                [LOG2U(RTNH_F_ONLINK)]     = "onlink" ,    /* Gateway is forced on link */
+                [LOG2U(RTNH_F_OFFLOAD)]    = "offload",    /* Nexthop is offloaded */
+                [LOG2U(RTNH_F_LINKDOWN)]   = "linkdown",   /* carrier-down on nexthop */
+                [LOG2U(RTNH_F_UNRESOLVED)] = "unresolved", /* The entry is unresolved (ipmr) */
+                [LOG2U(RTNH_F_TRAP)]       = "trap",       /* Nexthop is trapping packets */
         };
 
         assert(ret);
 
         for (size_t i = 0; i < ELEMENTSOF(map); i++)
-                if (flags & map[i].flag &&
-                    !strextend_with_separator(&str, ",", map[i].name))
-                        return -ENOMEM;
+                if (FLAGS_SET(flags, 1 << i) && map[i])
+                        if (!strextend_with_separator(&str, ",", map[i]))
+                                return -ENOMEM;
 
         *ret = TAKE_PTR(str);
         return 0;
diff --git a/src/network/networkd-util.c b/src/network/networkd-util.c
index b0020efe89..6011e9b998 100644
--- a/src/network/networkd-util.c
+++ b/src/network/networkd-util.c
@@ -24,25 +24,25 @@ static const char * const network_config_source_table[_NETWORK_CONFIG_SOURCE_MAX
 DEFINE_STRING_TABLE_LOOKUP_TO_STRING(network_config_source, NetworkConfigSource);
 
 int network_config_state_to_string_alloc(NetworkConfigState s, char **ret) {
-        static const struct {
-                NetworkConfigState state;
-                const char *str;
-        } map[] = {
-                { .state = NETWORK_CONFIG_STATE_PROBING,     .str = "probing",     },
-                { .state = NETWORK_CONFIG_STATE_REQUESTING,  .str = "requesting",  },
-                { .state = NETWORK_CONFIG_STATE_CONFIGURING, .str = "configuring", },
-                { .state = NETWORK_CONFIG_STATE_CONFIGURED,  .str = "configured",  },
-                { .state = NETWORK_CONFIG_STATE_MARKED,      .str = "marked",      },
-                { .state = NETWORK_CONFIG_STATE_REMOVING,    .str = "removing",    },
+        static const char* states[] = {
+                [LOG2U(NETWORK_CONFIG_STATE_PROBING)]     = "probing",
+                [LOG2U(NETWORK_CONFIG_STATE_REQUESTING)]  = "requesting",
+                [LOG2U(NETWORK_CONFIG_STATE_CONFIGURING)] = "configuring",
+                [LOG2U(NETWORK_CONFIG_STATE_CONFIGURED)]  = "configured",
+                [LOG2U(NETWORK_CONFIG_STATE_MARKED)]      = "marked",
+                [LOG2U(NETWORK_CONFIG_STATE_REMOVING)]    = "removing",
         };
         _cleanup_free_ char *buf = NULL;
 
         assert(ret);
 
-        for (size_t i = 0; i < ELEMENTSOF(map); i++)
-                if (FLAGS_SET(s, map[i].state) &&
-                    !strextend_with_separator(&buf, ",", map[i].str))
-                        return -ENOMEM;
+        for (size_t i = 0; i < ELEMENTSOF(states); i++)
+                if (FLAGS_SET(s, 1 << i)) {
+                        assert(states[i]);
+
+                        if (!strextend_with_separator(&buf, ",", states[i]))
+                                return -ENOMEM;
+                }
 
         *ret = TAKE_PTR(buf);
         return 0;
diff --git a/src/network/test-networkd-util.c b/src/network/test-networkd-util.c
new file mode 100644
index 0000000000..f29ca2cc72
--- /dev/null
+++ b/src/network/test-networkd-util.c
@@ -0,0 +1,19 @@
+/* SPDX-License-Identifier: LGPL-2.1-or-later */
+
+#include "networkd-util.h"
+#include "tests.h"
+
+TEST(network_config_state_to_string_alloc) {
+        for (unsigned i = 1; i <= NETWORK_CONFIG_STATE_REMOVING; i <<= 1) {
+                _cleanup_free_ char *x;
+
+                assert_se(network_config_state_to_string_alloc(i, &x) == 0);
+                log_debug("%u → %s", i, x);
+        }
+
+        _cleanup_free_ char *x;
+        assert_se(network_config_state_to_string_alloc(~0u, &x) == 0);
+        log_debug("%u → %s", ~0u, x);
+};
+
+DEFINE_TEST_MAIN(LOG_DEBUG);
diff --git a/src/test/test-util.c b/src/test/test-util.c
index 413469a26f..21ab016c22 100644
--- a/src/test/test-util.c
+++ b/src/test/test-util.c
@@ -17,14 +17,72 @@
 #include "tests.h"
 #include "util.h"
 
-TEST(u64log2) {
-        assert_se(u64log2(0) == 0);
-        assert_se(u64log2(8) == 3);
-        assert_se(u64log2(9) == 3);
-        assert_se(u64log2(15) == 3);
-        assert_se(u64log2(16) == 4);
-        assert_se(u64log2(1024*1024) == 20);
-        assert_se(u64log2(1024*1024+5) == 20);
+TEST(LOG2ULL) {
+        assert_se(LOG2ULL(0) == 0);
+        assert_se(LOG2ULL(1) == 0);
+        assert_se(LOG2ULL(8) == 3);
+        assert_se(LOG2ULL(9) == 3);
+        assert_se(LOG2ULL(15) == 3);
+        assert_se(LOG2ULL(16) == 4);
+        assert_se(LOG2ULL(1024*1024) == 20);
+        assert_se(LOG2ULL(1024*1024+5) == 20);
+}
+
+TEST(CONST_LOG2ULL) {
+        assert_se(CONST_LOG2ULL(0) == 0);
+        assert_se(CONST_LOG2ULL(1) == 0);
+        assert_se(CONST_LOG2ULL(8) == 3);
+        assert_se(CONST_LOG2ULL(9) == 3);
+        assert_se(CONST_LOG2ULL(15) == 3);
+        assert_se(CONST_LOG2ULL(16) == 4);
+        assert_se(CONST_LOG2ULL(1024*1024) == 20);
+        assert_se(CONST_LOG2ULL(1024*1024+5) == 20);
+}
+
+TEST(NONCONST_LOG2ULL) {
+        assert_se(NONCONST_LOG2ULL(0) == 0);
+        assert_se(NONCONST_LOG2ULL(1) == 0);
+        assert_se(NONCONST_LOG2ULL(8) == 3);
+        assert_se(NONCONST_LOG2ULL(9) == 3);
+        assert_se(NONCONST_LOG2ULL(15) == 3);
+        assert_se(NONCONST_LOG2ULL(16) == 4);
+        assert_se(NONCONST_LOG2ULL(1024*1024) == 20);
+        assert_se(NONCONST_LOG2ULL(1024*1024+5) == 20);
+}
+
+TEST(log2u64) {
+        assert_se(log2u64(0) == 0);
+        assert_se(log2u64(1) == 0);
+        assert_se(log2u64(8) == 3);
+        assert_se(log2u64(9) == 3);
+        assert_se(log2u64(15) == 3);
+        assert_se(log2u64(16) == 4);
+        assert_se(log2u64(1024*1024) == 20);
+        assert_se(log2u64(1024*1024+5) == 20);
+}
+
+TEST(log2u) {
+        assert_se(log2u(0) == 0);
+        assert_se(log2u(1) == 0);
+        assert_se(log2u(2) == 1);
+        assert_se(log2u(3) == 1);
+        assert_se(log2u(4) == 2);
+        assert_se(log2u(32) == 5);
+        assert_se(log2u(33) == 5);
+        assert_se(log2u(63) == 5);
+        assert_se(log2u(INT_MAX) == sizeof(int)*8-2);
+}
+
+TEST(log2i) {
+        assert_se(log2i(0) == 0);
+        assert_se(log2i(1) == 0);
+        assert_se(log2i(2) == 1);
+        assert_se(log2i(3) == 1);
+        assert_se(log2i(4) == 2);
+        assert_se(log2i(32) == 5);
+        assert_se(log2i(33) == 5);
+        assert_se(log2i(63) == 5);
+        assert_se(log2i(INT_MAX) == sizeof(int)*8-2);
 }
 
 TEST(protect_errno) {
@@ -58,17 +116,6 @@ TEST(unprotect_errno) {
         assert_se(errno == 4711);
 }
 
-TEST(log2i) {
-        assert_se(log2i(1) == 0);
-        assert_se(log2i(2) == 1);
-        assert_se(log2i(3) == 1);
-        assert_se(log2i(4) == 2);
-        assert_se(log2i(32) == 5);
-        assert_se(log2i(33) == 5);
-        assert_se(log2i(63) == 5);
-        assert_se(log2i(INT_MAX) == sizeof(int)*8-2);
-}
-
 TEST(eqzero) {
         const uint32_t zeros[] = {0, 0, 0};
         const uint32_t ones[] = {1, 1};