From 5e182235cb7e7b601c5e010c298bf17415113ce0 Mon Sep 17 00:00:00 2001 From: eldritch horrors Date: Mon, 4 Mar 2024 05:51:23 +0100 Subject: Merge pull request #7348 from thufschmitt/dont-use-vlas Remove the usage of VLAs in the code (cherry picked from commit ac4431e9d016e62fb5dc9ae36833bd0c6cdadeec) Change-Id: Ifbf5fbfc2e27122362a2aaea4b62c7cf3ca46b1a --- src/libexpr/eval.cc | 35 ++++++++++++++++++++++++++++++----- src/libexpr/eval.hh | 12 ++++++++++++ src/libexpr/primops.cc | 19 +++++++++++-------- src/libexpr/primops.hh | 16 ++++++++++++++++ src/libexpr/value.hh | 8 +------- 5 files changed, 70 insertions(+), 20 deletions(-) (limited to 'src/libexpr') diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc index b1268bb12..e98280f33 100644 --- a/src/libexpr/eval.cc +++ b/src/libexpr/eval.cc @@ -1,6 +1,7 @@ #include "eval.hh" #include "eval-settings.hh" #include "hash.hh" +#include "primops.hh" #include "types.hh" #include "util.hh" #include "store-api.hh" @@ -38,6 +39,7 @@ #include #include #include +#include #endif @@ -703,6 +705,23 @@ void EvalState::addConstant(const std::string & name, Value * v, Constant info) } +void PrimOp::check() +{ + if (arity > maxPrimOpArity) { + throw Error("primop arity must not exceed %1%", maxPrimOpArity); + } +} + + +void Value::mkPrimOp(PrimOp * p) +{ + p->check(); + clearValue(); + internalType = tPrimOp; + primOp = p; +} + + Value * EvalState::addPrimOp(PrimOp && primOp) { /* Hack to make constants lazy: turn them into a application of @@ -1683,7 +1702,7 @@ void EvalState::callFunction(Value & fun, size_t nrArgs, Value * * args, Value & /* We have all the arguments, so call the primop with the previous and new arguments. */ - Value * vArgs[arity]; + Value * vArgs[maxPrimOpArity]; auto n = argsDone; for (Value * arg = &vCur; arg->isPrimOpApp(); arg = arg->primOpApp.left) vArgs[--n] = arg->primOpApp.right; @@ -1740,11 +1759,17 @@ void ExprCall::eval(EvalState & state, Env & env, Value & v) Value vFun; fun->eval(state, env, vFun); - Value * vArgs[args.size()]; + // Empirical arity of Nixpkgs lambdas by regex e.g. ([a-zA-Z]+:(\s|(/\*.*\/)|(#.*\n))*){5} + // 2: over 4000 + // 3: about 300 + // 4: about 60 + // 5: under 10 + // This excluded attrset lambdas (`{...}:`). Contributions of mixed lambdas appears insignificant at ~150 total. + boost::container::small_vector vArgs(args.size()); for (size_t i = 0; i < args.size(); ++i) vArgs[i] = args[i]->maybeThunk(state, env); - state.callFunction(vFun, args.size(), vArgs, v, pos); + state.callFunction(vFun, args.size(), vArgs.data(), v, pos); } @@ -1983,8 +2008,8 @@ void ExprConcatStrings::eval(EvalState & state, Env & env, Value & v) return result; }; - Value values[es->size()]; - Value * vTmpP = values; + boost::container::small_vector values(es->size()); + Value * vTmpP = values.data(); for (auto & [i_pos, i] : *es) { Value & vTmp = *vTmpP++; diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh index 42dd73d11..4425efbca 100644 --- a/src/libexpr/eval.hh +++ b/src/libexpr/eval.hh @@ -18,6 +18,12 @@ namespace nix { +/** + * We put a limit on primop arity because it lets us use a fixed size array on + * the stack. 8 is already an impractical number of arguments. Use an attrset + * argument for such overly complicated functions. + */ +constexpr size_t maxPrimOpArity = 8; class Store; class EvalState; @@ -69,6 +75,12 @@ struct PrimOp * Optional experimental for this to be gated on. */ std::optional experimentalFeature; + + /** + * Validity check to be performed by functions that introduce primops, + * such as RegisterPrimOp() and Value::mkPrimOp(). + */ + void check(); }; /** diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc index fca20358a..44a97461a 100644 --- a/src/libexpr/primops.cc +++ b/src/libexpr/primops.cc @@ -28,7 +28,6 @@ #include - namespace nix { @@ -2547,6 +2546,7 @@ static void prim_removeAttrs(EvalState & state, const PosIdx pos, Value * * args /* Get the attribute names to be removed. We keep them as Attrs instead of Symbols so std::set_difference can be used to remove them from attrs[0]. */ + // 64: large enough to fit the attributes of a derivation boost::container::small_vector names; names.reserve(args[1]->listSize()); for (auto elem : args[1]->listItems()) { @@ -2726,8 +2726,8 @@ static void prim_catAttrs(EvalState & state, const PosIdx pos, Value * * args, V auto attrName = state.symbols.create(state.forceStringNoCtx(*args[0], pos, "while evaluating the first argument passed to builtins.catAttrs")); state.forceList(*args[1], pos, "while evaluating the second argument passed to builtins.catAttrs"); - Value * res[args[1]->listSize()]; - unsigned int found = 0; + boost::container::small_vector res(args[1]->listSize()); + size_t found = 0; for (auto v2 : args[1]->listItems()) { state.forceAttrs(*v2, pos, "while evaluating an element in the list passed as second argument to builtins.catAttrs"); @@ -3061,9 +3061,8 @@ static void prim_filter(EvalState & state, const PosIdx pos, Value * * args, Val state.forceFunction(*args[0], pos, "while evaluating the first argument passed to builtins.filter"); - // FIXME: putting this on the stack is risky. - Value * vs[args[1]->listSize()]; - unsigned int k = 0; + boost::container::small_vector vs(args[1]->listSize()); + size_t k = 0; bool same = true; for (unsigned int n = 0; n < args[1]->listSize(); ++n) { @@ -3188,10 +3187,14 @@ static void anyOrAll(bool any, EvalState & state, const PosIdx pos, Value * * ar state.forceFunction(*args[0], pos, std::string("while evaluating the first argument passed to builtins.") + (any ? "any" : "all")); state.forceList(*args[1], pos, std::string("while evaluating the second argument passed to builtins.") + (any ? "any" : "all")); + std::string_view errorCtx = any + ? "while evaluating the return value of the function passed to builtins.any" + : "while evaluating the return value of the function passed to builtins.all"; + Value vTmp; for (auto elem : args[1]->listItems()) { state.callFunction(*args[0], *elem, vTmp, pos); - bool res = state.forceBool(vTmp, pos, std::string("while evaluating the return value of the function passed to builtins.") + (any ? "any" : "all")); + bool res = state.forceBool(vTmp, pos, errorCtx); if (res == any) { v.mkBool(any); return; @@ -3447,7 +3450,7 @@ static void prim_concatMap(EvalState & state, const PosIdx pos, Value * * args, state.forceList(*args[1], pos, "while evaluating the second argument passed to builtins.concatMap"); auto nrLists = args[1]->listSize(); - Value lists[nrLists]; + boost::container::small_vector lists(nrLists); size_t len = 0; for (unsigned int n = 0; n < nrLists; ++n) { diff --git a/src/libexpr/primops.hh b/src/libexpr/primops.hh index 930e7f32a..45486608f 100644 --- a/src/libexpr/primops.hh +++ b/src/libexpr/primops.hh @@ -8,6 +8,22 @@ namespace nix { +/** + * For functions where we do not expect deep recursion, we can use a sizable + * part of the stack a free allocation space. + * + * Note: this is expected to be multiplied by sizeof(Value), or about 24 bytes. + */ +constexpr size_t nonRecursiveStackReservation = 128; + +/** + * Functions that maybe applied to self-similar inputs, such as concatMap on a + * tree, should reserve a smaller part of the stack for allocation. + * + * Note: this is expected to be multiplied by sizeof(Value), or about 24 bytes. + */ +constexpr size_t conservativeStackReservation = 16; + struct RegisterPrimOp { typedef std::vector PrimOps; diff --git a/src/libexpr/value.hh b/src/libexpr/value.hh index c44683e50..ec7d82a64 100644 --- a/src/libexpr/value.hh +++ b/src/libexpr/value.hh @@ -349,13 +349,7 @@ public: // Value will be overridden anyways } - inline void mkPrimOp(PrimOp * p) - { - clearValue(); - internalType = tPrimOp; - primOp = p; - } - + void mkPrimOp(PrimOp * p); inline void mkPrimOpApp(Value * l, Value * r) { -- cgit v1.2.3