summaryrefslogtreecommitdiffstats
path: root/src/opt.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/opt.c')
-rw-r--r--src/opt.c179
1 files changed, 87 insertions, 92 deletions
diff --git a/src/opt.c b/src/opt.c
index ffc795b..9b091bd 100644
--- a/src/opt.c
+++ b/src/opt.c
@@ -102,39 +102,20 @@ enum pred_type {
PRED_TYPES,
};
-/** Get the name of a predicate type. */
-static const char *pred_type_name(enum pred_type type) {
- switch (type) {
- case READABLE_PRED:
- return "-readable";
- case WRITABLE_PRED:
- return "-writable";
- case EXECUTABLE_PRED:
- return "-executable";
- case ACL_PRED:
- return "-acl";
- case CAPABLE_PRED:
- return "-capable";
- case EMPTY_PRED:
- return "-empty";
- case HIDDEN_PRED:
- return "-hidden";
- case NOGROUP_PRED:
- return "-nogroup";
- case NOUSER_PRED:
- return "-nouser";
- case SPARSE_PRED:
- return "-sparse";
- case XATTR_PRED:
- return "-xattr";
-
- case PRED_TYPES:
- break;
- }
-
- bfs_bug("Unknown predicate %d", (int)type);
- return "???";
-}
+/** Predicate type names. */
+static const char *const pred_names[] = {
+ [READABLE_PRED] = "-readable",
+ [WRITABLE_PRED] = "-writable",
+ [EXECUTABLE_PRED] = "-executable",
+ [ACL_PRED] = "-acl",
+ [CAPABLE_PRED] = "-capable",
+ [EMPTY_PRED] = "-empty",
+ [HIDDEN_PRED] = "-hidden",
+ [NOGROUP_PRED] = "-nogroup",
+ [NOUSER_PRED] = "-nouser",
+ [SPARSE_PRED] = "-sparse",
+ [XATTR_PRED] = "-xattr",
+};
/**
* A contrained integer range.
@@ -242,29 +223,15 @@ enum range_type {
RANGE_TYPES,
};
-/** Get the name of a range type. */
-static const char *range_type_name(enum range_type type) {
- switch (type) {
- case DEPTH_RANGE:
- return "-depth";
- case GID_RANGE:
- return "-gid";
- case INUM_RANGE:
- return "-inum";
- case LINKS_RANGE:
- return "-links";
- case SIZE_RANGE:
- return "-size";
- case UID_RANGE:
- return "-uid";
-
- case RANGE_TYPES:
- break;
- }
-
- bfs_bug("Unknown range %d", (int)type);
- return "???";
-}
+/** Range type names. */
+static const char *const range_names[] = {
+ [DEPTH_RANGE] = "-depth",
+ [GID_RANGE] = "-gid",
+ [INUM_RANGE] = "-inum",
+ [LINKS_RANGE] = "-links",
+ [SIZE_RANGE] = "-size",
+ [UID_RANGE] = "-uid",
+};
/**
* The data flow analysis domain.
@@ -333,27 +300,27 @@ static void df_init_top(struct df_domain *value) {
/** Check for the top element. */
static bool df_is_top(const struct df_domain *value) {
- for (int i = 0; i < PRED_TYPES; ++i) {
- if (value->preds[i] != PRED_TOP) {
- return false;
- }
- }
+ for (int i = 0; i < PRED_TYPES; ++i) {
+ if (value->preds[i] != PRED_TOP) {
+ return false;
+ }
+ }
- for (int i = 0; i < RANGE_TYPES; ++i) {
- if (!range_is_top(&value->ranges[i])) {
- return false;
- }
- }
+ for (int i = 0; i < RANGE_TYPES; ++i) {
+ if (!range_is_top(&value->ranges[i])) {
+ return false;
+ }
+ }
- if (value->types != ~0U) {
- return false;
- }
+ if (value->types != ~0U) {
+ return false;
+ }
- if (value->xtypes != ~0U) {
- return false;
- }
+ if (value->xtypes != ~0U) {
+ return false;
+ }
- return true;
+ return true;
}
/** Compute the union of two fact sets. */
@@ -503,7 +470,7 @@ typedef bool dump_fn(struct bfs_opt *opt, const char *format, ...);
/** Print a df_pred. */
static void pred_dump(dump_fn *dump, struct bfs_opt *opt, const struct df_domain *value, enum pred_type type) {
- dump(opt, "${blu}%s${rs}: ", pred_type_name(type));
+ dump(opt, "${blu}%s${rs}: ", pred_names[type]);
FILE *file = opt->ctx->cerr->file;
switch (value->preds[type]) {
@@ -524,7 +491,7 @@ static void pred_dump(dump_fn *dump, struct bfs_opt *opt, const struct df_domain
/** Print a df_range. */
static void range_dump(dump_fn *dump, struct bfs_opt *opt, const struct df_domain *value, enum range_type type) {
- dump(opt, "${blu}%s${rs}: ", range_type_name(type));
+ dump(opt, "${blu}%s${rs}: ", range_names[type]);
FILE *file = opt->ctx->cerr->file;
const struct df_range *range = &value->ranges[type];
@@ -947,8 +914,12 @@ static struct bfs_expr *visit_shallow(struct bfs_opt *opt, struct bfs_expr *expr
expr = general(opt, expr, visitor);
}
+ if (!expr) {
+ return NULL;
+ }
+
visit_fn *specific = look_up_visitor(expr, visitor->table);
- if (expr && specific) {
+ if (specific) {
expr = specific(opt, expr, visitor);
}
@@ -1084,7 +1055,7 @@ static struct bfs_expr *annotate_and(struct bfs_opt *opt, struct bfs_expr *expr,
expr->cost = 0.0;
expr->probability = 1.0;
- for (struct bfs_expr *child = bfs_expr_children(expr); child; child = child->next) {
+ for_expr (child, expr) {
expr->pure &= child->pure;
expr->always_true &= child->always_true;
expr->always_false |= child->always_false;
@@ -1103,7 +1074,7 @@ static struct bfs_expr *annotate_or(struct bfs_opt *opt, struct bfs_expr *expr,
expr->cost = 0.0;
float false_prob = 1.0;
- for (struct bfs_expr *child = bfs_expr_children(expr); child; child = child->next) {
+ for_expr (child, expr) {
expr->pure &= child->pure;
expr->always_true |= child->always_true;
expr->always_false &= child->always_false;
@@ -1120,7 +1091,7 @@ static struct bfs_expr *annotate_comma(struct bfs_opt *opt, struct bfs_expr *exp
expr->pure = true;
expr->cost = 0.0;
- for (struct bfs_expr *child = bfs_expr_children(expr); child; child = child->next) {
+ for_expr (child, expr) {
expr->pure &= child->pure;
expr->always_true = child->always_true;
expr->always_false = child->always_false;
@@ -1786,7 +1757,7 @@ static struct bfs_expr *data_flow_leave(struct bfs_opt *opt, struct bfs_expr *ex
if (df_is_bottom(&opt->after_false)) {
if (!expr->pure) {
expr->always_true = true;
- expr->probability = 0.0;
+ expr->probability = 1.0;
} else if (expr->eval_fn != eval_true) {
opt_warning(opt, expr, "This expression is always true.\n\n");
opt_debug(opt, "pure, always true\n");
@@ -1915,7 +1886,7 @@ static struct bfs_expr *simplify_not(struct bfs_opt *opt, struct bfs_expr *expr,
static struct bfs_expr *lift_andor_not(struct bfs_opt *opt, struct bfs_expr *expr) {
// Only lift negations if it would reduce the number of (-not) expressions
size_t added = 0, removed = 0;
- for (struct bfs_expr *child = bfs_expr_children(expr); child; child = child->next) {
+ for_expr (child, expr) {
if (child->eval_fn == eval_not) {
++removed;
} else {
@@ -1964,7 +1935,7 @@ static struct bfs_expr *first_ignorable(struct bfs_opt *opt, struct bfs_expr *ex
}
struct bfs_expr *ret = NULL;
- for (struct bfs_expr *child = bfs_expr_children(expr); child; child = child->next) {
+ for_expr (child, expr) {
if (!child->pure) {
ret = NULL;
} else if (!ret) {
@@ -2172,17 +2143,20 @@ static struct bfs_expr *optimize(struct bfs_opt *opt, struct bfs_expr *expr) {
return expr;
}
-/** Estimate the odds of an expression calling stat(). */
-static float expr_stat_odds(struct bfs_expr *expr) {
- if (expr->calls_stat) {
+/** An expression predicate. */
+typedef bool expr_pred(const struct bfs_expr *expr);
+
+/** Estimate the odds that a matching expression will be evaluated. */
+static float estimate_odds(const struct bfs_expr *expr, expr_pred *pred) {
+ if (pred(expr)) {
return 1.0;
}
- float nostat_odds = 1.0;
+ float nonmatch_odds = 1.0;
float reached_odds = 1.0;
- for (struct bfs_expr *child = bfs_expr_children(expr); child; child = child->next) {
- float child_odds = expr_stat_odds(child);
- nostat_odds *= 1.0 - reached_odds * child_odds;
+ for_expr (child, expr) {
+ float child_odds = estimate_odds(child, pred);
+ nonmatch_odds *= 1.0 - reached_odds * child_odds;
if (expr->eval_fn == eval_and) {
reached_odds *= child->probability;
@@ -2191,7 +2165,12 @@ static float expr_stat_odds(struct bfs_expr *expr) {
}
}
- return 1.0 - nostat_odds;
+ return 1.0 - nonmatch_odds;
+}
+
+/** Whether an expression calls stat(). */
+static bool calls_stat(const struct bfs_expr *expr) {
+ return expr->calls_stat;
}
/** Estimate the odds of calling stat(). */
@@ -2200,15 +2179,20 @@ static float estimate_stat_odds(struct bfs_ctx *ctx) {
return 1.0;
}
- float nostat_odds = 1.0 - expr_stat_odds(ctx->exclude);
+ float nostat_odds = 1.0 - estimate_odds(ctx->exclude, calls_stat);
float reached_odds = 1.0 - ctx->exclude->probability;
- float expr_odds = expr_stat_odds(ctx->expr);
+ float expr_odds = estimate_odds(ctx->expr, calls_stat);
nostat_odds *= 1.0 - reached_odds * expr_odds;
return 1.0 - nostat_odds;
}
+/** Matches -(exec|ok) ... \; */
+static bool single_exec(const struct bfs_expr *expr) {
+ return expr->eval_fn == eval_exec && !(expr->exec->flags & BFS_EXEC_MULTI);
+}
+
int bfs_optimize(struct bfs_ctx *ctx) {
bfs_ctx_dump(ctx, DEBUG_OPT);
@@ -2287,6 +2271,17 @@ int bfs_optimize(struct bfs_ctx *ctx) {
opt_leave(&opt, "eager stat cost: ${ylw}%g${rs}\n", eager_cost);
}
+#ifndef POSIX_SPAWN_SETRLIMIT
+ // If bfs_spawn_setrlimit() would force us to use fork() over
+ // posix_spawn(), the extra cost may outweigh the benefit of a
+ // higher RLIMIT_NOFILE
+ float single_exec_odds = estimate_odds(ctx->expr, single_exec);
+ if (single_exec_odds >= 0.5) {
+ opt_enter(&opt, "single ${blu}-exec${rs} odds: ${ylw}%g${rs}\n", single_exec_odds);
+ ctx->raise_nofile = false;
+ opt_leave(&opt, "not raising RLIMIT_NOFILE\n");
+ }
+#endif
}
opt_leave(&opt, NULL);
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-27 07:34:09 +0000