summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--src/opt.c54
-rw-r--r--src/parse.c54
2 files changed, 57 insertions, 51 deletions
diff --git a/src/opt.c b/src/opt.c
index c80d584..1daf390 100644
--- a/src/opt.c
+++ b/src/opt.c
@@ -804,6 +804,8 @@ static struct bfs_expr *optimize_empty(struct opt_state *state, struct bfs_expr
static struct bfs_expr *optimize_exec(struct opt_state *state, struct bfs_expr *expr) {
if (expr->exec->flags & BFS_EXEC_MULTI) {
expr->always_true = true;
+ } else {
+ expr->cost = 1000000.0;
}
return expr;
@@ -929,6 +931,50 @@ static bfs_eval_fn *const opt_always_false[] = {
eval_quit,
};
+#define FAST_COST 40.0
+#define FNMATCH_COST 400.0
+#define STAT_COST 1000.0
+#define PRINT_COST 20000.0
+
+/**
+ * Table of expression costs.
+ */
+static const struct {
+ /** The evaluation function with this cost. */
+ bfs_eval_fn *eval_fn;
+ /** The matching cost. */
+ float cost;
+} opt_costs[] = {
+ {eval_access, STAT_COST},
+ {eval_acl, STAT_COST},
+ {eval_capable, STAT_COST},
+ {eval_empty, 2 * STAT_COST}, // readdir() is worse than stat()
+ {eval_fls, PRINT_COST},
+ {eval_fprint, PRINT_COST},
+ {eval_fprint0, PRINT_COST},
+ {eval_fprintf, PRINT_COST},
+ {eval_fprintx, PRINT_COST},
+ {eval_fstype, STAT_COST},
+ {eval_gid, STAT_COST},
+ {eval_inum, STAT_COST},
+ {eval_links, STAT_COST},
+ {eval_lname, FNMATCH_COST},
+ {eval_name, FNMATCH_COST},
+ {eval_newer, STAT_COST},
+ {eval_nogroup, STAT_COST},
+ {eval_nouser, STAT_COST},
+ {eval_path, FNMATCH_COST},
+ {eval_perm, STAT_COST},
+ {eval_samefile, STAT_COST},
+ {eval_size, STAT_COST},
+ {eval_sparse, STAT_COST},
+ {eval_time, STAT_COST},
+ {eval_uid, STAT_COST},
+ {eval_used, STAT_COST},
+ {eval_xattr, STAT_COST},
+ {eval_xattrname, STAT_COST},
+};
+
/**
* Table of simple predicates.
*/
@@ -1017,6 +1063,14 @@ static struct bfs_expr *optimize_expr_lookup(struct opt_state *state, struct bfs
}
}
+ expr->cost = FAST_COST;
+ for (size_t i = 0; i < BFS_COUNTOF(opt_costs); ++i) {
+ if (opt_costs[i].eval_fn == expr->eval_fn) {
+ expr->cost = opt_costs[i].cost;
+ 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 5766237..eee185b 100644
--- a/src/parse.c
+++ b/src/parse.c
@@ -68,11 +68,6 @@ static char *fake_or_arg = "-o";
static char *fake_print_arg = "-print";
static char *fake_true_arg = "-true";
-// Cost estimation constants
-#define FAST_COST 40.0
-#define STAT_COST 1000.0
-#define PRINT_COST 20000.0
-
struct bfs_expr *bfs_expr_new(bfs_eval_fn *eval_fn, size_t argc, char **argv) {
struct bfs_expr *expr = malloc(sizeof(*expr));
if (!expr) {
@@ -88,7 +83,7 @@ struct bfs_expr *bfs_expr_new(bfs_eval_fn *eval_fn, size_t argc, char **argv) {
expr->pure = false;
expr->always_true = false;
expr->always_false = false;
- expr->cost = FAST_COST;
+ expr->cost = 0.0;
expr->probability = 0.5;
expr->evaluations = 0;
expr->successes = 0;
@@ -436,7 +431,6 @@ static bool parse_expr_warning(const struct parser_state *state, const struct bf
* Fill in a "-print"-type expression.
*/
static void init_print_expr(struct parser_state *state, struct bfs_expr *expr) {
- expr->cost = PRINT_COST;
expr->cfile = state->ctx->cout;
expr->path = NULL;
}
@@ -1021,7 +1015,6 @@ static struct bfs_expr *parse_access(struct parser_state *state, int flag, int a
}
expr->num = flag;
- expr->cost = STAT_COST;
switch (flag) {
case R_OK:
@@ -1045,7 +1038,6 @@ 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->cost = STAT_COST;
expr->probability = 0.00002;
}
return expr;
@@ -1069,7 +1061,6 @@ static struct bfs_expr *parse_newer(struct parser_state *state, int field, int a
goto fail;
}
- expr->cost = STAT_COST;
expr->reftime = sb.mtime;
expr->stat_field = field;
return expr;
@@ -1088,7 +1079,6 @@ static struct bfs_expr *parse_min(struct parser_state *state, int field, int arg
return NULL;
}
- expr->cost = STAT_COST;
expr->reftime = state->now;
expr->stat_field = field;
expr->time_unit = BFS_MINUTES;
@@ -1104,7 +1094,6 @@ static struct bfs_expr *parse_time(struct parser_state *state, int field, int ar
return NULL;
}
- expr->cost = STAT_COST;
expr->reftime = state->now;
expr->stat_field = field;
@@ -1173,7 +1162,6 @@ static struct bfs_expr *parse_capable(struct parser_state *state, int flag, int
#if BFS_CAN_CHECK_CAPABILITIES
struct bfs_expr *expr = parse_nullary_test(state, eval_capable);
if (expr) {
- expr->cost = STAT_COST;
expr->probability = 0.000002;
}
return expr;
@@ -1309,7 +1297,6 @@ static struct bfs_expr *parse_empty(struct parser_state *state, int arg1, int ar
return NULL;
}
- expr->cost = 2000.0;
expr->probability = 0.01;
expr->ephemeral_fds = 1;
return expr;
@@ -1332,10 +1319,6 @@ static struct bfs_expr *parse_exec(struct parser_state *state, int flags, int ar
expr->exec = execbuf;
- if (!(execbuf->flags & BFS_EXEC_MULTI)) {
- expr->cost = 1000000.0;
- }
-
expr->ephemeral_fds = 2;
if (execbuf->flags & BFS_EXEC_CHDIR) {
if (execbuf->flags & BFS_EXEC_MULTI) {
@@ -1495,7 +1478,6 @@ static struct bfs_expr *parse_fls(struct parser_state *state, int arg1, int arg2
goto fail;
}
- expr->cost = PRINT_COST;
return expr;
fail:
@@ -1509,7 +1491,6 @@ fail:
static struct bfs_expr *parse_fprint(struct parser_state *state, int arg1, int arg2) {
struct bfs_expr *expr = parse_unary_action(state, eval_fprint);
if (expr) {
- expr->cost = PRINT_COST;
if (expr_open(state, expr, expr->argv[1]) != 0) {
goto fail;
}
@@ -1527,7 +1508,6 @@ fail:
static struct bfs_expr *parse_fprint0(struct parser_state *state, int arg1, int arg2) {
struct bfs_expr *expr = parse_unary_action(state, eval_fprint0);
if (expr) {
- expr->cost = PRINT_COST;
if (expr_open(state, expr, expr->argv[1]) != 0) {
goto fail;
}
@@ -1562,8 +1542,6 @@ static struct bfs_expr *parse_fprintf(struct parser_state *state, int arg1, int
return NULL;
}
- expr->cost = PRINT_COST;
-
if (expr_open(state, expr, file) != 0) {
goto fail;
}
@@ -1594,7 +1572,6 @@ static struct bfs_expr *parse_fstype(struct parser_state *state, int arg1, int a
return NULL;
}
- expr->cost = STAT_COST;
return expr;
}
@@ -1623,7 +1600,6 @@ static struct bfs_expr *parse_group(struct parser_state *state, int arg1, int ar
goto fail;
}
- expr->cost = STAT_COST;
return expr;
fail:
@@ -1643,11 +1619,7 @@ static struct bfs_expr *parse_unique(struct parser_state *state, int arg1, int a
* Parse -used N.
*/
static struct bfs_expr *parse_used(struct parser_state *state, int arg1, int arg2) {
- struct bfs_expr *expr = parse_test_icmp(state, eval_used);
- if (expr) {
- expr->cost = STAT_COST;
- }
- return expr;
+ return parse_test_icmp(state, eval_used);
}
/**
@@ -1675,7 +1647,6 @@ static struct bfs_expr *parse_user(struct parser_state *state, int arg1, int arg
goto fail;
}
- expr->cost = STAT_COST;
return expr;
fail:
@@ -1708,7 +1679,6 @@ static struct bfs_expr *parse_ignore_races(struct parser_state *state, int ignor
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->cost = STAT_COST;
expr->probability = expr->int_cmp == BFS_INT_EQUAL ? 0.01 : 0.50;
}
return expr;
@@ -1720,7 +1690,6 @@ static struct bfs_expr *parse_inum(struct parser_state *state, int arg1, int arg
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->cost = STAT_COST;
expr->probability = bfs_expr_cmp(expr, 1) ? 0.99 : 0.01;
}
return expr;
@@ -1795,8 +1764,6 @@ static struct bfs_expr *parse_fnmatch(const struct parser_state *state, struct b
return expr;
}
- expr->cost = 400.0;
-
if (strchr(pattern, '*')) {
expr->probability = 0.5;
} else {
@@ -1942,8 +1909,6 @@ static struct bfs_expr *parse_newerxy(struct parser_state *state, int arg1, int
expr->reftime = *reftime;
}
- expr->cost = STAT_COST;
-
return expr;
fail:
@@ -1960,7 +1925,6 @@ static struct bfs_expr *parse_nogroup(struct parser_state *state, int arg1, int
return NULL;
}
- expr->cost = STAT_COST;
expr->probability = 0.01;
// Who knows how many FDs getgrgid_r() needs? Probably at least one for
@@ -2006,7 +1970,6 @@ static struct bfs_expr *parse_nouser(struct parser_state *state, int arg1, int a
return NULL;
}
- expr->cost = STAT_COST;
expr->probability = 0.01;
// Who knows how many FDs getpwuid_r() needs? Probably at least one for
@@ -2272,8 +2235,6 @@ static struct bfs_expr *parse_perm(struct parser_state *state, int field, int ar
goto fail;
}
- expr->cost = STAT_COST;
-
return expr;
fail:
@@ -2468,7 +2429,6 @@ static struct bfs_expr *parse_samefile(struct parser_state *state, int arg1, int
expr->dev = sb.dev;
expr->ino = sb.ino;
- expr->cost = STAT_COST;
expr->probability = 0.01;
return expr;
@@ -2531,7 +2491,6 @@ static struct bfs_expr *parse_since(struct parser_state *state, int field, int a
goto fail;
}
- expr->cost = STAT_COST;
expr->stat_field = field;
return expr;
@@ -2589,7 +2548,6 @@ static struct bfs_expr *parse_size(struct parser_state *state, int arg1, int arg
goto bad_unit;
}
- expr->cost = STAT_COST;
expr->probability = expr->int_cmp == BFS_INT_EQUAL ? 0.01 : 0.50;
return expr;
@@ -2605,11 +2563,7 @@ fail:
* Parse -sparse.
*/
static struct bfs_expr *parse_sparse(struct parser_state *state, int arg1, int arg2) {
- struct bfs_expr *expr = parse_nullary_test(state, eval_sparse);
- if (expr) {
- expr->cost = STAT_COST;
- }
- return expr;
+ return parse_nullary_test(state, eval_sparse);
}
/**
@@ -2728,7 +2682,6 @@ static struct bfs_expr *parse_xattr(struct parser_state *state, int arg1, int ar
#if BFS_CAN_CHECK_XATTRS
struct bfs_expr *expr = parse_nullary_test(state, eval_xattr);
if (expr) {
- expr->cost = STAT_COST;
expr->probability = 0.01;
}
return expr;
@@ -2745,7 +2698,6 @@ static struct bfs_expr *parse_xattrname(struct parser_state *state, int arg1, in
#if BFS_CAN_CHECK_XATTRS
struct bfs_expr *expr = parse_unary_test(state, eval_xattrname);
if (expr) {
- expr->cost = STAT_COST;
expr->probability = 0.01;
}
return expr;