2075553a1

Denys Vlasenko

2024-05-31

SOURCE BUG Duration: 15s

Subject

libbb: add bit counting function, use where appropriate

SOURCE BUG

This commit was genuinely broken at the time (not related to our build system): libbb.h icinde bb_popcnt_long bildiriminde 'unsigned_long' diye bir tip yazilmisti (dogrusu 'unsigned long') - bu satir sadece 64-bit build'lerde derlendigi icin hata bizim gibi 64-bit ortamlarda cikiyordu (41b47398f ile duzeltildi, ayni gun)

→ Bu hatanin tam hikayesini ve duzeltme diffini gor

Binary

No binary (build failed)

Architecture & Compiler Flags

Architecture: x86_64-linux-gnu Compiler: gcc (Ubuntu 11.4.0-1ubuntu1~22.04.3) 11.4.0

—

Build Log

(log yok)

Commit Diff GitHub →

coreutils/nproc.c +3 -6 include/libbb.h +7 -0 libbb/Kbuild.src +1 -0 libbb/popcnt.c +46 -0 networking/ifupdown.c +1 -7 networking/ipcalc.c +1 -20 networking/libiproute/utils.c +5 -6 networking/udhcp/dhcpc.c +2 -13

coreutils/nproc.c+3 -6

@@ -56,13 +56,10 @@ int nproc_main(int argc UNUSED_PARAM, char **argv UNUSED_PARAM)
	unsigned long *mask = get_malloc_cpu_affinity(0, &sz);
	sz /= sizeof(long);
	for (i = 0; i < sz; i++) {
-	unsigned long m = mask[i];
-	while (m) {
-	if (m & 1)
-	count++;
-	m >>= 1;
-	}
+	if (mask[i] != 0) /* most mask[i] are usually 0 */
+	count += bb_popcnt_long(mask[i]);
	}
+	IF_FEATURE_CLEAN_UP(free(mask);)
	}

	IF_LONG_OPTS(count -= ignore;)

include/libbb.h+7 -0

@@ -397,6 +397,13 @@ extern int *BB_GLOBAL_CONST bb_errno;
	uint64_t bb_bswap_64(uint64_t x) FAST_FUNC;
	#endif

+	unsigned FAST_FUNC bb_popcnt_32(uint32_t m);
+	#if ULONG_MAX > 0xffffffff
+	unsigned FAST_FUNC bb_popcnt_long(unsigned_long m);
+	#else
+	#define bb_popcnt_long(m) bb_popcnt_32(m)
+	#endif
+
	unsigned long FAST_FUNC isqrt(unsigned long long N);

	unsigned long long monotonic_ns(void) FAST_FUNC;

libbb/Kbuild.src+1 -0

@@ -72,6 +72,7 @@ lib-y += perror_nomsg.o
	lib-y += perror_nomsg_and_die.o
	lib-y += pidfile.o
	lib-y += platform.o
+	lib-y += popcnt.o
	lib-y += printable.o
	lib-y += printable_string.o
	lib-y += print_flags.o

libbb/popcnt.c+46 -0

@@ -0,0 +1,46 @@
+	/* vi: set sw=4 ts=4: */
+	/*
+	* Utility routines.
+	*
+	* Copyright (C) 2024 Denys Vlasenko
+	*
+	* Licensed under GPLv2, see file LICENSE in this source tree.
+	*/
+	#include "libbb.h"
+
+	unsigned FAST_FUNC bb_popcnt_32(uint32_t m)
+	{
+	/* replace each 2 bit group with the count of set bits in it */
+	/* 00->00 01->01 10->01 11->10 */
+	m = m - ((m >> 1) & 0x55555555);
+	/* in each 4 bit group, add two 2-bit counts */
+	m = (m & 0x33333333) + ((m >> 2) & 0x33333333);
+	/* in each 8 bit group, add two 4-bit counts (in fact, 3-bit, 0nnn with n=0..4) */
+	m = (m + (m >> 4)) & 0x0f0f0f0f;
+	#if 1 /* assume 3232->32 multiply is fast /
+	m = m * 0x01010101; /* top byte = m + (m<<8) + (m<<16) + (m<<24) */
+	return m >> 24;
+	#else
+	/* 0000aaaa0000bbbb0000cccc0000dddd */
+	/* + 0000aaaa0000bbbb0000cccc */
+	/* = 0000xxxx000_a+b_000xxxxx000_c+d_ (we don't care about x bits) */
+	m += m >> 8; /* in each 16-bit group, lowest 5 bits is the count */
+	/* 0000xxxx000_a+b_000xxxxx000_c+d_ */
+	/* + 0000xxxx000_a+b_ */
+	/* = 0000xxxx000xxxxx00xxxxxx00a+b+cd */
+	m += m >> 16; /* in each 32-bit group, lowest 6 bits is the count */
+	return m & 0x3f; /* clear x bits */
+	#endif
+	}
+
+	#if ULONG_MAX > 0xffffffff
+	unsigned FAST_FUNC bb_popcnt_long(unsigned long m)
+	{
+	BUILD_BUG_ON(sizeof(m) != 8);
+	/* 64-bit version of bb_popcnt_32 exists, but it uses 64-bit constants,
+	* which are awkward to generate on assembly level on most CPUs.
+	* For now, just add two 32-bit counts:
+	*/
+	return bb_popcnt_32((uint32_t)m) + bb_popcnt_32((uint32_t)(m >> 32));
+	}
+	#endif

networking/ifupdown.c+1 -7

@@ -306,7 +306,6 @@ static int count_netmask_bits(const char *dotted_quad)
	// d = ~d; /* 11110000 -> 00001111 */

	/* Shorter version */
-	int result;
	struct in_addr ip;
	unsigned d;

@@ -316,12 +315,7 @@ static int count_netmask_bits(const char *dotted_quad)
	d = ~d; /* 11110000 -> 00001111 */
	if (d & (d+1)) /* check that it is in 00001111 form */
	return -1; /* no it is not */
-	result = 32;
-	while (d) {
-	d >>= 1;
-	result--;
-	}
-	return result;
+	return bb_popcnt_32(~d);
	}
	# endif

networking/ipcalc.c+1 -20

@@ -71,25 +71,6 @@ static unsigned long get_netmask(unsigned long ipaddr)
	return 0;
	}

-	#if ENABLE_FEATURE_IPCALC_FANCY
-	static int get_prefix(unsigned long netmask)
-	{
-	unsigned long msk = 0x80000000;
-	int ret = 0;
-
-	netmask = htonl(netmask);
-	while (msk) {
-	if (netmask & msk)
-	ret++;
-	msk >>= 1;
-	}
-	return ret;
-	}
-	#else
-	int get_prefix(unsigned long netmask);
-	#endif
-
-
	#define NETMASK 0x01
	#define BROADCAST 0x02
	#define NETWORK 0x04
@@ -210,7 +191,7 @@ int ipcalc_main(int argc UNUSED_PARAM, char **argv)

	if (ENABLE_FEATURE_IPCALC_FANCY) {
	if (opt & NETPREFIX) {
-	printf("PREFIX=%i\n", get_prefix(netmask));
+	printf("PREFIX=%i\n", bb_popcnt_32(netmask));
	}

	if (opt & HOSTNAME) {

networking/libiproute/utils.c+5 -6

@@ -175,14 +175,13 @@ static void get_prefix_1(inet_prefix dst, char arg, int family)
	if (netmask_pfx.family == AF_INET) {
	/* fill in prefix length of dotted quad */
	uint32_t mask = ntohl(netmask_pfx.data[0]);
-	uint32_t host = ~mask;
+	uint32_t inv = ~mask;

-	/* a valid netmask must be 2^n - 1 */
-	if (host & (host + 1))
-	goto bad;
+	/* a valid netmask must be 11..10..00 */
+	if (inv & (inv + 1))
+	goto bad; /* inv is not 00..01..11 */

-	for (plen = 0; mask; mask <<= 1)
-	++plen;
+	plen = bb_popcnt_32(mask);
	if (plen > dst->bitlen)
	goto bad;
	/* dst->flags \|= PREFIXLEN_SPECIFIED; */

networking/udhcp/dhcpc.c+2 -13

@@ -150,18 +150,6 @@ static int sprint_nip(char dest, const char pre, const uint8_t *ip)
	return sprintf(dest, "%s%u.%u.%u.%u", pre, ip[0], ip[1], ip[2], ip[3]);
	}

-	/* really simple implementation, just count the bits */
-	static int mton(uint32_t mask)
-	{
-	int i = 0;
-	mask = ntohl(mask); /* 111110000-like bit pattern */
-	while (mask) {
-	i++;
-	mask <<= 1;
-	}
-	return i;
-	}
-
	#if ENABLE_FEATURE_UDHCPC_SANITIZEOPT
	/* Check if a given name represents a valid DNS name */
	/* See RFC1035, 2.3.1 */
@@ -508,7 +496,8 @@ static void fill_envp(struct dhcp_packet *packet)
	/* Generate extra envvar for DHCP_SUBNET, $mask */
	uint32_t subnet;
	move_from_unaligned32(subnet, opt_item->data);
-	putenvp(xasprintf("mask=%u", mton(subnet)));
+	//FIXME: we do not check that subnet has bit pattern 11..10..0
+	putenvp(xasprintf("mask=%u", bb_popcnt_32(subnet)));
	}
	} else {
	unsigned ofs;