summaryrefslogtreecommitdiffstats
path: root/src/opt.c
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2023-01-24 17:23:18 -0500
committerTavian Barnes <tavianator@tavianator.com>2023-01-24 17:37:33 -0500
commit220fb782da63fd648dedb02a7c43c837792b3d4a (patch)
tree7c4b1658cd894aaf65812127b472f554b04f042e /src/opt.c
parentcb3805257092cea2fa6d1fce8d2f99f6b01f44ed (diff)
downloadbfs-220fb782da63fd648dedb02a7c43c837792b3d4a.tar.xz
opt: Move probabilities out of the parser
Diffstat (limited to 'src/opt.c')
-rw-r--r--src/opt.c132
1 files changed, 132 insertions, 0 deletions
diff --git a/src/opt.c b/src/opt.c
index 1daf390..e76e216 100644
--- a/src/opt.c
+++ b/src/opt.c
@@ -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);