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 4605 41
4 2410 83
8 1343 99
16 909 131
32 885 195
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.
function old new delta
find_applet_by_name 31 135 +104
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 155261 -605
applet_nameofs 728 28 -700
------------------------------------------------------------------------------
(add/remove: 4/1 grow/shrink: 2/3 up/down: 268/-1349) Total: -1081 bytes
text data bss dec hex filename
823821 4078 9088 836987 cc57b busybox_old
823337 4086 9096 836519 cc3a7 busybox_unstripped
Signed-off-by: Ron Yorston <[email protected]>
---
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..282fe99 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 struct {uint16_t index, offset;} applet_nameofs[]
= {\n");
+ for (i = 1; i < KNOWN_OFFSETS; i++)
+ printf("{ %d, %d },\n", index[i], 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..9bb2784 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].offset) >= 0) {
+ i = applet_nameofs[j].index;
+ p = applet_names + applet_nameofs[j].offset;
+ 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
_______________________________________________
busybox mailing list
[email protected]
http://lists.busybox.net/mailman/listinfo/busybox
