[PATCH v5] applet_tables: save space by removing applet name offsets

Ron Yorston rmy at pobox.com
Tue Mar 29 15:31:44 UTC 2016


The array applet_nameofs consumes two bytes per applet.  It encodes

   nofork/noexec flags
   suid flags
   the offset of the applet name in the applet_name string

Change the applet_table build tool to store the flags in two separate
arrays (applet_flags and applet_suid).  Replace applet_nameofs with a
smaller version that only stores a limited number of offsets.

This requires changes to the macros APPLET_IS_NOFORK, APPLET_IS_NOEXEC
and APPLET_SUID.  The APPLET_NAME macro is replaced by a function,
get_applet_name, which uses a linear search though the applet_name
string to find the applet name given its number.  As an optimisation
get_applet_name stores the last applet number/name looked up.

There are three cases where get_applet_name is used:

1) In install_links applets are processed in numerical order.  Every
   time get_applet_name is called it is to search for the applet
   number following the last stored value.

2) In find_applet_by_name get_applet_name is called in the comparison
   function of a binary search.  Replace this with a linear search which
   uses the known offsets to provide an improved starting value.

   According to Valgrind the original find_applet_by_name required
   353 cycles per call, averaged over all names.  Adjusting the number
   of known offsets allows space to be traded off against execution time:

      KNOWN_OFFSETS     cycles     bytes (wrt KNOWN_OFFSETS = 0)

           0             9057        -
           2             4604       32
           4             2407       75
           8             1342       98
          16              908      130
          32              884      194

   This patch uses KNOWN_OFFSETS = 8.

3) In run_applet_no_and_exit and run_nofork_applet the applet number
   passed to get_applet_name was obtained by an earlier call to
   find_applet_by_name.  The stored value is often exactly the one
   required so no linear search is needed.

v2:
   Remove some dead code from the applet_table tool;
   Treat the applet in the middle of the table as a special case.

v3:
   Use the middle applet to adjust the start of the linear search as
   well as the last applet found.

v4:
   Use an augmented linear search in find_applet_by_name.
   Drop the special treatment of the middle name from get_applet_name:
   most of the advantage now derives from the last stored value.

v5:
   Don't store index in applet_nameofs, it can be calculated.

function                                             old     new   delta
find_applet_by_name                                   31     132    +101
applet_suid                                            -      91     +91
get_applet_name                                        -      60     +60
static.last_applet_name                                -       8      +8
static.last_applet_no                                  -       4      +4
run_applet_no_and_exit                               480     481      +1
run_applet_and_exit                                  755     742     -13
applet_name_compare                                   31       -     -31
.rodata                                           155866  155243    -623
applet_nameofs                                       728      14    -714
------------------------------------------------------------------------------
(add/remove: 4/1 grow/shrink: 2/3 up/down: 265/-1381)       Total: -1116 bytes
   text	   data	    bss	    dec	    hex	filename
 823821	   4078	   9088	 836987	  cc57b	busybox_old
 823316	   4086	   9096	 836498	  cc392	busybox_unstripped

Signed-off-by: Ron Yorston <rmy at pobox.com>
---
 applets/applet_tables.c    | 69 ++++++++++++++++++++++++++++++++++------------
 include/busybox.h          | 15 ++++------
 include/libbb.h            |  1 +
 libbb/appletlib.c          | 55 ++++++++++++++++++++++--------------
 libbb/vfork_daemon_rexec.c |  2 +-
 5 files changed, 93 insertions(+), 49 deletions(-)

diff --git a/applets/applet_tables.c b/applets/applet_tables.c
index 92bf1e4..6053942 100644
--- a/applets/applet_tables.c
+++ b/applets/applet_tables.c
@@ -41,8 +41,6 @@ struct bb_applet {
 
 enum { NUM_APPLETS = ARRAY_SIZE(applets) };
 
-static int offset[NUM_APPLETS];
-
 static int cmp_name(const void *a, const void *b)
 {
 	const struct bb_applet *aa = a;
@@ -60,22 +58,28 @@ static int str_isalnum_(const char *s)
 	return 1;
 }
 
+#define KNOWN_OFFSETS 8
+
 int main(int argc, char **argv)
 {
-	int i;
-	int ofs;
+	int i, j;
+	int ofs, offset[KNOWN_OFFSETS], index[KNOWN_OFFSETS];
 //	unsigned MAX_APPLET_NAME_LEN = 1;
 
 	qsort(applets, NUM_APPLETS, sizeof(applets[0]), cmp_name);
 
+	for (i=0; i<KNOWN_OFFSETS; i++)
+		index[i] = i*NUM_APPLETS/KNOWN_OFFSETS;
+
 	ofs = 0;
 	for (i = 0; i < NUM_APPLETS; i++) {
-		offset[i] = ofs;
+		for (j = 0; j < KNOWN_OFFSETS; j++)
+			if (i == index[j])
+				offset[j] = ofs;
 		ofs += strlen(applets[i].name) + 1;
 	}
-	/* We reuse 4 high-order bits of offset array for other purposes,
-	 * so if they are indeed needed, refuse to proceed */
-	if (ofs > 0xfff)
+	/* If the list of names is too long refuse to proceed */
+	if (ofs > 0xffff)
 		return 1;
 	if (!argv[1])
 		return 1;
@@ -94,7 +98,17 @@ int main(int argc, char **argv)
 		printf("#define SINGLE_APPLET_STR \"%s\"\n", applets[0].name);
 		printf("#define SINGLE_APPLET_MAIN %s_main\n", applets[0].main);
 	}
-	printf("\n");
+
+	if (KNOWN_OFFSETS > 0 && NUM_APPLETS > 2*KNOWN_OFFSETS) {
+		printf("#define KNOWN_OFFSETS %u\n\n", KNOWN_OFFSETS);
+		printf("const uint16_t applet_nameofs[] ALIGN2 = {\n");
+		for (i = 1; i < KNOWN_OFFSETS; i++)
+			printf("%d,\n", offset[i]);
+		printf("};\n\n");
+	}
+	else {
+		printf("#define KNOWN_OFFSETS 0\n\n");
+	}
 
 	//printf("#ifndef SKIP_definitions\n");
 	printf("const char applet_names[] ALIGN1 = \"\"\n");
@@ -119,20 +133,39 @@ int main(int argc, char **argv)
 	printf("};\n");
 	printf("#endif\n\n");
 
-	printf("const uint16_t applet_nameofs[] ALIGN2 = {\n");
-	for (i = 0; i < NUM_APPLETS; i++) {
-		printf("0x%04x,\n",
-			offset[i]
 #if ENABLE_FEATURE_PREFER_APPLETS
-			+ (applets[i].nofork << 12)
-			+ (applets[i].noexec << 13)
+	printf("const uint8_t applet_flags[] ALIGN1 = {\n");
+	i = 0;
+	while (i < NUM_APPLETS) {
+		int v = applets[i].nofork + (applets[i].noexec << 1);
+		if (++i < NUM_APPLETS)
+			v |= (applets[i].nofork + (applets[i].noexec << 1)) << 2;
+		if (++i < NUM_APPLETS)
+			v |= (applets[i].nofork + (applets[i].noexec << 1)) << 4;
+		if (++i < NUM_APPLETS)
+			v |= (applets[i].nofork + (applets[i].noexec << 1)) << 6;
+		printf("0x%02x,\n", v);
+		i++;
+	}
+	printf("};\n\n");
 #endif
+
 #if ENABLE_FEATURE_SUID
-			+ (applets[i].need_suid << 14) /* 2 bits */
-#endif
-		);
+	printf("const uint8_t applet_suid[] ALIGN1 = {\n");
+	i = 0;
+	while (i < NUM_APPLETS) {
+		int v = applets[i].need_suid; /* 2 bits */
+		if (++i < NUM_APPLETS)
+			v |= applets[i].need_suid << 2;
+		if (++i < NUM_APPLETS)
+			v |= applets[i].need_suid << 4;
+		if (++i < NUM_APPLETS)
+			v |= applets[i].need_suid << 6;
+		printf("0x%02x,\n", v);
+		i++;
 	}
 	printf("};\n\n");
+#endif
 
 #if ENABLE_FEATURE_INSTALLER
 	printf("const uint8_t applet_install_loc[] ALIGN1 = {\n");
diff --git a/include/busybox.h b/include/busybox.h
index b1e31e5..737627b 100644
--- a/include/busybox.h
+++ b/include/busybox.h
@@ -15,25 +15,20 @@ PUSH_AND_SET_FUNCTION_VISIBILITY_TO_HIDDEN
 /* Keep in sync with applets/applet_tables.c! */
 extern const char applet_names[] ALIGN1;
 extern int (*const applet_main[])(int argc, char **argv);
-extern const uint16_t applet_nameofs[];
+extern const uint8_t applet_flags[] ALIGN1;
+extern const uint8_t applet_suid[] ALIGN1;
 extern const uint8_t applet_install_loc[] ALIGN1;
 
-#if ENABLE_FEATURE_SUID || ENABLE_FEATURE_PREFER_APPLETS
-# define APPLET_NAME(i) (applet_names + (applet_nameofs[i] & 0x0fff))
-#else
-# define APPLET_NAME(i) (applet_names + applet_nameofs[i])
-#endif
-
 #if ENABLE_FEATURE_PREFER_APPLETS
-# define APPLET_IS_NOFORK(i) (applet_nameofs[i] & (1 << 12))
-# define APPLET_IS_NOEXEC(i) (applet_nameofs[i] & (1 << 13))
+# define APPLET_IS_NOFORK(i) (applet_flags[(i)/4] & (1 << (2 * ((i)%4))))
+# define APPLET_IS_NOEXEC(i) (applet_flags[(i)/4] & (1 << ((2 * ((i)%4))+1)))
 #else
 # define APPLET_IS_NOFORK(i) 0
 # define APPLET_IS_NOEXEC(i) 0
 #endif
 
 #if ENABLE_FEATURE_SUID
-# define APPLET_SUID(i) ((applet_nameofs[i] >> 14) & 0x3)
+# define APPLET_SUID(i) ((applet_suid[(i)/4] >> (2 * ((i)%4)) & 3))
 #endif
 
 #if ENABLE_FEATURE_INSTALLER
diff --git a/include/libbb.h b/include/libbb.h
index 8b226c0..692b9f3 100644
--- a/include/libbb.h
+++ b/include/libbb.h
@@ -1226,6 +1226,7 @@ const struct hwtype *get_hwntype(int type) FAST_FUNC;
 
 #ifndef BUILD_INDIVIDUAL
 extern int find_applet_by_name(const char *name) FAST_FUNC;
+extern const char *get_applet_name(int applet_no) FAST_FUNC;
 /* Returns only if applet is not found. */
 extern void run_applet_and_exit(const char *name, char **argv) FAST_FUNC;
 extern void run_applet_no_and_exit(int a, char **argv) NORETURN FAST_FUNC;
diff --git a/libbb/appletlib.c b/libbb/appletlib.c
index 95e589e..9a08056 100644
--- a/libbb/appletlib.c
+++ b/libbb/appletlib.c
@@ -139,28 +139,44 @@ void FAST_FUNC bb_show_usage(void)
 	xfunc_die();
 }
 
-#if NUM_APPLETS > 8
-static int applet_name_compare(const void *name, const void *idx)
+const char * FAST_FUNC get_applet_name(int applet_no)
 {
-	int i = (int)(ptrdiff_t)idx - 1;
-	return strcmp(name, APPLET_NAME(i));
+	int count = applet_no;
+	const char *p = applet_names;
+	static int last_applet_no = 0;
+	static const char *last_applet_name = applet_names;
+
+	if (applet_no >= last_applet_no) {
+		count = applet_no - last_applet_no;
+		p = last_applet_name;
+	}
+
+	while (count--) {
+		while (*p++)
+			;
+	}
+
+	last_applet_no = applet_no;
+	last_applet_name = p;
+
+	return p;
 }
-#endif
+
 int FAST_FUNC find_applet_by_name(const char *name)
 {
-#if NUM_APPLETS > 8
-	/* Do a binary search to find the applet entry given the name. */
-	const char *p;
-	p = bsearch(name, (void*)(ptrdiff_t)1, ARRAY_SIZE(applet_main), 1, applet_name_compare);
-	/*
-	 * if (!p) return -1;
-	 * ^^^^^^^^^^^^^^^^^^ the code below will do this if p == NULL :)
-	 */
-	return (int)(ptrdiff_t)p - 1;
-#else
-	/* A version which does not pull in bsearch */
-	int i = 0;
+	int i = 0, j;
 	const char *p = applet_names;
+
+#if KNOWN_OFFSETS
+	for (j=ARRAY_SIZE(applet_nameofs)-1; j>=0; j--) {
+		if (strcmp(name, applet_names+applet_nameofs[j]) >= 0) {
+			i = (j+1)*NUM_APPLETS/KNOWN_OFFSETS;
+			p = applet_names + applet_nameofs[j];
+			break;
+		}
+	}
+#endif
+
 	while (i < NUM_APPLETS) {
 		if (strcmp(name, p) == 0)
 			return i;
@@ -168,7 +184,6 @@ int FAST_FUNC find_applet_by_name(const char *name)
 		i++;
 	}
 	return -1;
-#endif
 }
 
 
@@ -593,7 +608,7 @@ static void install_links(const char *busybox, int use_symbolic_links,
 	for (i = 0; i < ARRAY_SIZE(applet_main); i++) {
 		fpc = concat_path_file(
 				custom_install_dir ? custom_install_dir : install_dir[APPLET_INSTALL_LOC(i)],
-				APPLET_NAME(i));
+				get_applet_name(i));
 		// debug: bb_error_msg("%slinking %s to busybox",
 		//		use_symbolic_links ? "sym" : "", fpc);
 		rc = lf(busybox, fpc);
@@ -754,7 +769,7 @@ void FAST_FUNC run_applet_no_and_exit(int applet_no, char **argv)
 
 	/* Reinit some shared global data */
 	xfunc_error_retval = EXIT_FAILURE;
-	applet_name = APPLET_NAME(applet_no);
+	applet_name = get_applet_name(applet_no);
 
 	/* Special case. POSIX says "test --help"
 	 * should be no different from e.g. "test --foo".
diff --git a/libbb/vfork_daemon_rexec.c b/libbb/vfork_daemon_rexec.c
index d6ca7b2..640d216 100644
--- a/libbb/vfork_daemon_rexec.c
+++ b/libbb/vfork_daemon_rexec.c
@@ -116,7 +116,7 @@ int FAST_FUNC run_nofork_applet(int applet_no, char **argv)
 
 	save_nofork_data(&old);
 
-	applet_name = APPLET_NAME(applet_no);
+	applet_name = get_applet_name(applet_no);
 
 	xfunc_error_retval = EXIT_FAILURE;
 
-- 
2.5.5



More information about the busybox mailing list