diff options
Diffstat (limited to 'src/opt.c')
-rw-r--r-- | src/opt.c | 179 |
1 files changed, 87 insertions, 92 deletions
@@ -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); |