aboutsummaryrefslogtreecommitdiff
path: root/applets
diff options
context:
space:
mode:
authorGravatar Ron Yorston <rmy@pobox.com>2016-03-30 00:42:05 +0200
committerGravatar Denys Vlasenko <vda.linux@googlemail.com>2016-03-30 00:44:11 +0200
commit610c4c385b38280c7bde7a48d95ec019cbfe1ab4 (patch)
tree82ad4366ce9e927f64efa89d178c4dd2bfea1435 /applets
parent9844d7e830a2c55421e27e8828d2067c50f57c23 (diff)
downloadbusybox-610c4c385b38280c7bde7a48d95ec019cbfe1ab4.tar.gz
busybox-610c4c385b38280c7bde7a48d95ec019cbfe1ab4.tar.bz2
applet_tables: save space by removing applet name offsets
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. 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. 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. v6: Tweaks by Denys function old new delta find_applet_by_name 25 125 +100 applet_suid - 92 +92 run_applet_no_and_exit 452 460 +8 run_applet_and_exit 695 697 +2 applet_name_compare 31 - -31 applet_nameofs 734 14 -720 ------------------------------------------------------------------------------ (add/remove: 1/1 grow/shrink: 3/1 up/down: 202/-751) Total: -549 bytes text data bss dec hex filename 925464 906 17160 943530 e65aa busybox_old 924915 906 17160 942981 e6385 busybox_unstripped Signed-off-by: Ron Yorston <rmy@pobox.com> Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>
Diffstat (limited to 'applets')
-rw-r--r--applets/applet_tables.c78
1 files changed, 60 insertions, 18 deletions
diff --git a/applets/applet_tables.c b/applets/applet_tables.c
index 92bf1e447..48544f08d 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,37 @@ static int str_isalnum_(const char *s)
return 1;
}
+// Before linear search, narrow it down by looking at N "equidistant" names:
+// KNOWN_APPNAME_OFFSETS cycles code_size
+// 0 9057
+// 2 4604 +32
+// 4 2407 +75
+// 8 1342 +98
+// 16 908 +130
+// 32 884 +194
+// With 8, applet_nameofs[] table has 7 elements.
+#define KNOWN_APPNAME_OFFSETS 8
+
int main(int argc, char **argv)
{
- int i;
- int ofs;
+ int i, j;
+ int ofs, offset[KNOWN_APPNAME_OFFSETS], index[KNOWN_APPNAME_OFFSETS];
// unsigned MAX_APPLET_NAME_LEN = 1;
qsort(applets, NUM_APPLETS, sizeof(applets[0]), cmp_name);
+ for (i = 0; i < KNOWN_APPNAME_OFFSETS; i++)
+ index[i] = i * NUM_APPLETS / KNOWN_APPNAME_OFFSETS;
+
ofs = 0;
for (i = 0; i < NUM_APPLETS; i++) {
- offset[i] = ofs;
+ for (j = 0; j < KNOWN_APPNAME_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 +107,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_APPNAME_OFFSETS > 0 && NUM_APPLETS > 2*KNOWN_APPNAME_OFFSETS) {
+ printf("#define KNOWN_APPNAME_OFFSETS %u\n\n", KNOWN_APPNAME_OFFSETS);
+ printf("const uint16_t applet_nameofs[] ALIGN2 = {\n");
+ for (i = 1; i < KNOWN_APPNAME_OFFSETS; i++)
+ printf("%d,\n", offset[i]);
+ printf("};\n\n");
+ }
+ else {
+ printf("#define KNOWN_APPNAME_OFFSETS 0\n\n");
+ }
//printf("#ifndef SKIP_definitions\n");
printf("const char applet_names[] ALIGN1 = \"\"\n");
@@ -119,20 +142,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");