diff options
| -rw-r--r-- | src/opt.c | 132 | ||||
| -rw-r--r-- | src/parse.c | 149 |
2 files changed, 161 insertions, 120 deletions
@@ -54,6 +54,7 @@ #include <stdarg.h> #include <stdbool.h> #include <stdio.h> +#include <string.h> #include <unistd.h> static char *fake_and_arg = "-a"; @@ -776,15 +777,23 @@ static void infer_icmp_facts(struct opt_state *state, const struct bfs_expr *exp /** Optimize -{execut,read,writ}able. */ static struct bfs_expr *optimize_access(struct opt_state *state, struct bfs_expr *expr) { + expr->probability = 1.0; + if (expr->num & R_OK) { infer_pred_facts(state, READABLE_PRED); + expr->probability *= 0.99; } + if (expr->num & W_OK) { infer_pred_facts(state, WRITABLE_PRED); + expr->probability *= 0.8; } + if (expr->num & X_OK) { infer_pred_facts(state, EXECUTABLE_PRED); + expr->probability *= 0.2; } + return expr; } @@ -811,6 +820,17 @@ static struct bfs_expr *optimize_exec(struct opt_state *state, struct bfs_expr * return expr; } +/** Optimize -name/-lname/-path. */ +static struct bfs_expr *optimize_fnmatch(struct opt_state *state, struct bfs_expr *expr) { + if (strchr(expr->argv[1], '*')) { + expr->probability = 0.5; + } else { + expr->probability = 0.1; + } + + return expr; +} + /** Optimize -gid. */ static struct bfs_expr *optimize_gid(struct opt_state *state, struct bfs_expr *expr) { struct range *range = &state->facts_when_true.ranges[GID_RANGE]; @@ -825,6 +845,30 @@ static struct bfs_expr *optimize_gid(struct opt_state *state, struct bfs_expr *e return expr; } +/** Optimize -inum. */ +static struct bfs_expr *optimize_inum(struct opt_state *state, struct bfs_expr *expr) { + struct range *range = &state->facts_when_true.ranges[INUM_RANGE]; + if (range->min == range->max) { + expr->probability = 0.01; + } else { + expr->probability = 0.5; + } + + return expr; +} + +/** Optimize -links. */ +static struct bfs_expr *optimize_links(struct opt_state *state, struct bfs_expr *expr) { + struct range *range = &state->facts_when_true.ranges[LINKS_RANGE]; + if (1 >= range->min && 1 <= range->max) { + expr->probability = 0.99; + } else { + expr->probability = 0.5; + } + + return expr; +} + /** Optimize -uid. */ static struct bfs_expr *optimize_uid(struct opt_state *state, struct bfs_expr *expr) { struct range *range = &state->facts_when_true.ranges[UID_RANGE]; @@ -847,10 +891,59 @@ static struct bfs_expr *optimize_samefile(struct opt_state *state, struct bfs_ex return expr; } +/** Optimize -size. */ +static struct bfs_expr *optimize_size(struct opt_state *state, struct bfs_expr *expr) { + struct range *range = &state->facts_when_true.ranges[SIZE_RANGE]; + if (range->min == range->max) { + expr->probability = 0.01; + } else { + expr->probability = 0.5; + } + + return expr; +} + +/** Estimate probability for -x?type. */ +static void estimate_type_probability(struct bfs_expr *expr) { + unsigned int types = expr->num; + + expr->probability = 0.0; + if (types & (1 << BFS_BLK)) { + expr->probability += 0.00000721183; + } + if (types & (1 << BFS_CHR)) { + expr->probability += 0.0000499855; + } + if (types & (1 << BFS_DIR)) { + expr->probability += 0.114475; + } + if (types & (1 << BFS_DOOR)) { + expr->probability += 0.000001; + } + if (types & (1 << BFS_FIFO)) { + expr->probability += 0.00000248684; + } + if (types & (1 << BFS_REG)) { + expr->probability += 0.859772; + } + if (types & (1 << BFS_LNK)) { + expr->probability += 0.0256816; + } + if (types & (1 << BFS_SOCK)) { + expr->probability += 0.0000116881; + } + if (types & (1 << BFS_WHT)) { + expr->probability += 0.000001; + } +} + /** Optimize -type. */ static struct bfs_expr *optimize_type(struct opt_state *state, struct bfs_expr *expr) { state->facts_when_true.types &= expr->num; state->facts_when_false.types &= ~expr->num; + + estimate_type_probability(expr); + return expr; } @@ -865,6 +958,9 @@ static struct bfs_expr *optimize_xtype(struct opt_state *state, struct bfs_expr state->facts_when_true.xtypes &= expr->num; state->facts_when_false.xtypes &= ~expr->num; + + estimate_type_probability(expr); + return expr; } @@ -976,6 +1072,29 @@ static const struct { }; /** + * Table of expression probabilities. + */ +static const struct { + /** The evaluation function with this cost. */ + bfs_eval_fn *eval_fn; + /** The matching probability. */ + float probability; +} opt_probs[] = { + {eval_acl, 0.00002}, + {eval_capable, 0.000002}, + {eval_empty, 0.01}, + {eval_false, 0.0}, + {eval_hidden, 0.01}, + {eval_nogroup, 0.01}, + {eval_nouser, 0.01}, + {eval_samefile, 0.01}, + {eval_true, 1.0}, + {eval_xattr, 0.01}, + {eval_xattrname, 0.01}, +}; + + +/** * Table of simple predicates. */ static const struct { @@ -1026,7 +1145,13 @@ static const struct { {eval_empty, optimize_empty}, {eval_exec, optimize_exec}, {eval_gid, optimize_gid}, + {eval_inum, optimize_inum}, + {eval_links, optimize_links}, + {eval_lname, optimize_fnmatch}, + {eval_name, optimize_fnmatch}, + {eval_path, optimize_fnmatch}, {eval_samefile, optimize_samefile}, + {eval_size, optimize_size}, {eval_type, optimize_type}, {eval_uid, optimize_uid}, {eval_xtype, optimize_xtype}, @@ -1071,6 +1196,13 @@ static struct bfs_expr *optimize_expr_lookup(struct opt_state *state, struct bfs } } + for (size_t i = 0; i < BFS_COUNTOF(opt_probs); ++i) { + if (opt_probs[i].eval_fn == expr->eval_fn) { + expr->probability = opt_probs[i].probability; + break; + } + } + for (size_t i = 0; i < BFS_COUNTOF(opt_preds); ++i) { if (opt_preds[i].eval_fn == expr->eval_fn) { infer_pred_facts(state, opt_preds[i].pred); diff --git a/src/parse.c b/src/parse.c index eee185b..f2582e0 100644 --- a/src/parse.c +++ b/src/parse.c @@ -1010,24 +1010,9 @@ static struct bfs_expr *parse_xargs_safe(struct parser_state *state, int arg1, i */ static struct bfs_expr *parse_access(struct parser_state *state, int flag, int arg2) { struct bfs_expr *expr = parse_nullary_test(state, eval_access); - if (!expr) { - return NULL; - } - - expr->num = flag; - - switch (flag) { - case R_OK: - expr->probability = 0.99; - break; - case W_OK: - expr->probability = 0.8; - break; - case X_OK: - expr->probability = 0.2; - break; + if (expr) { + expr->num = flag; } - return expr; } @@ -1036,11 +1021,7 @@ static struct bfs_expr *parse_access(struct parser_state *state, int flag, int a */ static struct bfs_expr *parse_acl(struct parser_state *state, int flag, int arg2) { #if BFS_CAN_CHECK_ACL - struct bfs_expr *expr = parse_nullary_test(state, eval_acl); - if (expr) { - expr->probability = 0.00002; - } - return expr; + return parse_nullary_test(state, eval_acl); #else parse_error(state, "Missing platform support.\n"); return NULL; @@ -1160,11 +1141,7 @@ fail: */ static struct bfs_expr *parse_capable(struct parser_state *state, int flag, int arg2) { #if BFS_CAN_CHECK_CAPABILITIES - struct bfs_expr *expr = parse_nullary_test(state, eval_capable); - if (expr) { - expr->probability = 0.000002; - } - return expr; + return parse_nullary_test(state, eval_capable); #else parse_error(state, "Missing platform support.\n"); return NULL; @@ -1293,12 +1270,9 @@ static struct bfs_expr *parse_depth_limit(struct parser_state *state, int is_min */ static struct bfs_expr *parse_empty(struct parser_state *state, int arg1, int arg2) { struct bfs_expr *expr = parse_nullary_test(state, eval_empty); - if (!expr) { - return NULL; + if (expr) { + expr->ephemeral_fds = 1; } - - expr->probability = 0.01; - expr->ephemeral_fds = 1; return expr; } @@ -1658,11 +1632,7 @@ fail: * Parse -hidden. */ static struct bfs_expr *parse_hidden(struct parser_state *state, int arg1, int arg2) { - struct bfs_expr *expr = parse_nullary_test(state, eval_hidden); - if (expr) { - expr->probability = 0.01; - } - return expr; + return parse_nullary_test(state, eval_hidden); } /** @@ -1677,22 +1647,14 @@ static struct bfs_expr *parse_ignore_races(struct parser_state *state, int ignor * Parse -inum N. */ static struct bfs_expr *parse_inum(struct parser_state *state, int arg1, int arg2) { - struct bfs_expr *expr = parse_test_icmp(state, eval_inum); - if (expr) { - expr->probability = expr->int_cmp == BFS_INT_EQUAL ? 0.01 : 0.50; - } - return expr; + return parse_test_icmp(state, eval_inum); } /** * Parse -links N. */ static struct bfs_expr *parse_links(struct parser_state *state, int arg1, int arg2) { - struct bfs_expr *expr = parse_test_icmp(state, eval_links); - if (expr) { - expr->probability = bfs_expr_cmp(expr, 1) ? 0.99 : 0.01; - } - return expr; + return parse_test_icmp(state, eval_links); } /** @@ -1764,12 +1726,6 @@ static struct bfs_expr *parse_fnmatch(const struct parser_state *state, struct b return expr; } - if (strchr(pattern, '*')) { - expr->probability = 0.5; - } else { - expr->probability = 0.1; - } - return expr; } @@ -1921,16 +1877,11 @@ fail: */ static struct bfs_expr *parse_nogroup(struct parser_state *state, int arg1, int arg2) { struct bfs_expr *expr = parse_nullary_test(state, eval_nogroup); - if (!expr) { - return NULL; + if (expr) { + // Who knows how many FDs getgrgid_r() needs? Probably at least + // one for /etc/group + expr->ephemeral_fds = 1; } - - expr->probability = 0.01; - - // Who knows how many FDs getgrgid_r() needs? Probably at least one for - // /etc/group - expr->ephemeral_fds = 1; - return expr; } @@ -1943,8 +1894,6 @@ static struct bfs_expr *parse_nohidden(struct parser_state *state, int arg1, int return NULL; } - hidden->probability = 0.01; - if (parse_exclude(state, hidden) != 0) { return NULL; } @@ -1966,16 +1915,11 @@ static struct bfs_expr *parse_noleaf(struct parser_state *state, int arg1, int a */ static struct bfs_expr *parse_nouser(struct parser_state *state, int arg1, int arg2) { struct bfs_expr *expr = parse_nullary_test(state, eval_nouser); - if (!expr) { - return NULL; + if (expr) { + // Who knows how many FDs getpwuid_r() needs? Probably at least + // one for /etc/passwd + expr->ephemeral_fds = 1; } - - expr->probability = 0.01; - - // Who knows how many FDs getpwuid_r() needs? Probably at least one for - // /etc/passwd - expr->ephemeral_fds = 1; - return expr; } @@ -2428,9 +2372,6 @@ static struct bfs_expr *parse_samefile(struct parser_state *state, int arg1, int expr->dev = sb.dev; expr->ino = sb.ino; - - expr->probability = 0.01; - return expr; } @@ -2548,8 +2489,6 @@ static struct bfs_expr *parse_size(struct parser_state *state, int arg1, int arg goto bad_unit; } - expr->probability = expr->int_cmp == BFS_INT_EQUAL ? 0.01 : 0.50; - return expr; bad_unit: @@ -2584,50 +2523,37 @@ static struct bfs_expr *parse_type(struct parser_state *state, int x, int arg2) return NULL; } - unsigned int types = 0; - float probability = 0.0; + expr->num = 0; const char *c = expr->argv[1]; while (true) { - enum bfs_type type; - float type_prob; - switch (*c) { case 'b': - type = BFS_BLK; - type_prob = 0.00000721183; + expr->num |= 1 << BFS_BLK; break; case 'c': - type = BFS_CHR; - type_prob = 0.0000499855; + expr->num |= 1 << BFS_CHR; break; case 'd': - type = BFS_DIR; - type_prob = 0.114475; + expr->num |= 1 << BFS_DIR; break; case 'D': - type = BFS_DOOR; - type_prob = 0.000001; + expr->num |= 1 << BFS_DOOR; break; case 'p': - type = BFS_FIFO; - type_prob = 0.00000248684; + expr->num |= 1 << BFS_FIFO; break; case 'f': - type = BFS_REG; - type_prob = 0.859772; + expr->num |= 1 << BFS_REG; break; case 'l': - type = BFS_LNK; - type_prob = 0.0256816; + expr->num |= 1 << BFS_LNK; break; case 's': - type = BFS_SOCK; - type_prob = 0.0000116881; + expr->num |= 1 << BFS_SOCK; break; case 'w': - type = BFS_WHT; - type_prob = 0.000001; + expr->num |= 1 << BFS_WHT; break; case '\0': @@ -2639,12 +2565,6 @@ static struct bfs_expr *parse_type(struct parser_state *state, int x, int arg2) goto fail; } - unsigned int flag = 1 << type; - if (!(types & flag)) { - types |= flag; - probability += type_prob; - } - ++c; if (*c == '\0') { break; @@ -2657,9 +2577,6 @@ static struct bfs_expr *parse_type(struct parser_state *state, int x, int arg2) } } - expr->num = types; - expr->probability = probability; - return expr; fail: @@ -2680,11 +2597,7 @@ static struct bfs_expr *parse_warn(struct parser_state *state, int warn, int arg */ static struct bfs_expr *parse_xattr(struct parser_state *state, int arg1, int arg2) { #if BFS_CAN_CHECK_XATTRS - struct bfs_expr *expr = parse_nullary_test(state, eval_xattr); - if (expr) { - expr->probability = 0.01; - } - return expr; + return parse_nullary_test(state, eval_xattr); #else parse_error(state, "Missing platform support.\n"); return NULL; @@ -2696,11 +2609,7 @@ static struct bfs_expr *parse_xattr(struct parser_state *state, int arg1, int ar */ static struct bfs_expr *parse_xattrname(struct parser_state *state, int arg1, int arg2) { #if BFS_CAN_CHECK_XATTRS - struct bfs_expr *expr = parse_unary_test(state, eval_xattrname); - if (expr) { - expr->probability = 0.01; - } - return expr; + return parse_unary_test(state, eval_xattrname); #else parse_error(state, "Missing platform support.\n"); return NULL; |