Originally meant to be `array.concat_n`, but this name is better
as the behavior of this function differs from `array.concat` —
namely that `array.flatten` accepts any type of valued in the
input array. Only arrays are however flattened, and the rest
are appended directly to the flattened output.
Note that this function only flattens at the topmost level of
the input array — not recursively! A cursory look
at a few other languages suggest a single level is the common case.
But if others feel we should flstten more, I'm happy to make an update.
The C code for a Wasm implementstion here is cowboy coded, and
I did not manage to run the tests on my machine due to some
`docker` <-> `container` differences. I mostly just imitated
the existing code in the array category. I doubt it'll work
on the first try, but only CI can judge me.
Also:
- Remove `opa fmt` step from the Rego CI step, as this is done by
Regal anyway a little later in the list of tasks.
- Replace some hard-coded `docker` names in the `Makefile` with `$(DOCKER)`
- Added name of built-in function missing to the unsupportedBuiltinErr
error, as it has happened a few times now that I've used `:=` in a
query, and had no clue what built-in it referred to.
Fixes#8226
Signed-off-by: Anders Eknert <anders.eknert@apple.com>
Adding string interpolation support to the Rego language.
An interpolated string is composed of a template-string that can contain zero or more template-expressions that interpolates values into the string generated at eval-time.
Requires the `template_strings` capability feature and `internal.template_string` built-in function.
Implements: #4733
Fixing possible memory leak where caches grow uncontrollably when large amounts of regexes or globs are generated or originate from the input document.
Fixes: #6828
Signed-off-by: Johan Fylling <johan.dev@fylling.se>
This patch removes ordered block storage in fixed-sized block freelists
in the OPA WASM memory allocator. Variable-sized block allocation still
orders blocks so that free() can coalesce them back into larger sized
blocks. This greatly reduces the runtime of opa_free() for fixed-size
blocks as it turns it from an O(N) operation to an O(1) operation.
This comes at the cost that reducing the heap_ptr implicitly on
opa_free() becomes impractical since reduction will stop at the first
fixed-sied block regardless of whether it is allocated or not. In
practice, what this means is that the allocator can never combine
fixed-size and variable-sized blocks. However, it was rarely able to do
so previously: only when the two blocks happened to be free at the same
time and line up with the heap_ptr.
This patch also adds support for a new function called opa_free_bulk() that
enables releasing memory objects always in O(1) time per object and
O(N log N) worst case for releasing N objects. The patch works by
freeing variable-sized objects (which would normally take O(N) time per
free) to a temporary holding list and setting a flag indicating that the
next variable-sized allocation needs to merge said holding list.
When releasing the holding list, the memory allocator first merge-sorts
in address-order the released blocks and then merges and coalesces them
into the variable-sized block list in address order. This takes at most
O(max(M+N, N log N)) time where M is the number of blocks on the
variable freelist and N is the number of blocks bulk freed.
The patch also updates the __opa_value_free() function to take a new
parameter named 'bulk' which directs the function passes to its various
type-specific subroutines. Every time one of the type-sepcific
subroutines goes to free an object it invokes either opa_free() or
opa_free_bulk() depending upon the 'bulk' parameter. (This is
abstracted by a function __opa_free_maybe_bulk() in value.c)
Calls to opa_value_free() or opa_value_free_shallow(), will set the
the 'bulk' parameter to false preserving the existing behavior.
However, the opa_value_add_path() and opa_value_remove_path()
functions will invoke the function with 'bulk' set to true to ensure
that the cascaded free operations on objects each take only O(1) time.
Finally, the patch re-enables the RESTAuthzAllow100Paths benchmark.
Fixes: #5901
Signed-off-by: Chris Telfer <chris.telfer@sophos.com>
This commit fixes several memory leaks in the WASM engine that occur
when a caller mixes incremental calls to opa_value_path_add() /
opa_value_path_remove() with actual policy evaluations. The issue
occurs due to a combination of lack of deep free of internal data
structures and the fact that eval() and opa_eval() calls reset the heap
to free temporary memory that they previous allocated.
More details about the issues and their fix are described in detail at
https://github.com/open-policy-agent/opa/issues/5785.
The changes in this patch fall into 5 categories:
1. Adding support for both internal WASM functions and external WASM
callers to perform a "deep" free of OPA values by freeing not only
the immediate object memory but all the opa values it refers to.
The opa_value_free() function now does this by default and is
also an exported function. The opa_value_free_shallow() is added
for the few cases where shallow frees are required, primarily in
eval()-invoked functions.
2. Enable stashing of free blocks prior to eval() and opa_eval() calls.
Eval calls will always leak free blocks due to the way that
opa_heap_ptr_get() works. This patch adds three new exports allowing
the user to save this memory from leaking.
* opa_heap_blocks_stash() -- saves free heap blocks to shadow
freelists.
* opa_heap_blocks_restore() -- restores the allocated heap blocks from
shadow freelists.
* opa_heap_stash_clear() -- discard any saved heap blocks on the shadow
freelists. (this is used for resetting VM heap to an initial state)
3. Update the WASM calling conventions in the SDK. This includes using
the new APIs to avoid leaking memory when adding or removing data
from the data doc. It requires bumping the WASM ABI to 1.3
4. Adding unit tests for the WASM ABI 1.3 functions.
5. Adding documenttion for the WASM ABI 1.3 functions.
Fixes: #5785
Signed-off-by: Chris Telfer <chris.telfer@sophos.com>
The `object.keys` function will return a set of all top-level keys on
a given object. Since object keys in Rego don't have the same
restrictions as names in JSON name-value pairs, we also ensure
support for non-string key types.
Fixes#5363.
Signed-off-by: Kevin Swiber <kswiber@gmail.com>
This commit fixes an issue around the WASM C tests breaking due to not
getting updated during recent changes to the is_type builtin functions.
Signed-off-by: Philip Conrad <philipaconrad@gmail.com>
This commit ensures that the `graph.reachable` and `graph.reachable_paths` builtins check the types of both of their operands, and return type errors instead of default values if a wrong type is provided.
Fixes#4951
Using null for delimiters disables delimiters in glob matching. Preferable over regex on some cases for performance reasons.
Fixes#4923.
Signed-off-by: vinhph0906 <vinhph0906@gmail.com>
Co-authored-by: Stephan Renatus <stephan.renatus@gmail.com>
wasm: Add support for WASM and simple tests.
internal: Add opa_json_is_valid to map of wasm built-ins.
docs: Indicate that WASM support is now available for json.is_valid.
Fixes#4140
Signed-off-by: Kristian Svalland <kristian.svalland@gmail.com>
The function `array.reverse` takes an array as an argument, and returns an array with a reversed order of elements.
The function `strings.reverse` takes a string as an argument, and returns a string with a reversed order of unicode code points.
WASM support is included for both built-ins.
Fixes#3736
Signed-off-by: Kristian Svalland <kristian.svalland@gmail.com>
Putting the stack first is preferrable for how C/C++'s stack is mapped
in to Wasm: it's assigned a memory pointer, and grows up. Without
putting the stack first, it can grow into the data section and over-
write globals, leading to situations best described as weird.
Putting it first means that if the evaluation runs out of stack space,
a memory-out-of-bounds trap will occur: it'll try to access a negative
memory location.
In internal/compiler/wasm, we append segments to the data section.
Since our memory layout is
| <-- stack | -- data (llvm, opa) -- | heap --> |
we need to adjust the border between data and heap, i.e., where the heap
starts. When initializing a module, the Start function emitted by the
compiler will call the opa_malloc_init function with the new heap base.
Also:
* run-wasm-rego-tests.sh: bump node image version
* wasm/graph.unreachable: fix "memory access out of bounds" issue
We've never seen this bug in the wild before, but due to the memory layout
change, the second branch -- casting to an array, accessing its fields --
would now attempt to read something well beyond the end of memory, and trap.
* rego/testdata: remove Makefile and input rego policy
This test bundle is simple enough to recreate if need be.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
Also
- use opa_value_iter in opa_glob_match
- add test cases to `wasm-rego-test`
- adapt existing test cases in `wasm-lib-test`
Fixes#3294.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
* wasm: introduce OPA_STRING_INTERNED for interned strings
opa_value_type will report these as OPA_STRING, so special behaviour
should use node->type to discern OPA_STRING/OPA_STRING_INTERNED:
- shallow copies don't need to copy interned strings
- interned strings aren't free()'ed
* wasm: pass constants along, compile them accordingly
* wasm/src: switch to stdbool.h's bool
I'm not aware of any strong reason not to, it seems to be what's commonly
advised, and the memory use of this type is smaller.
* wasm: intern opa_boolean
The heap allocs for these probably don't amount to much, but interning
them allows for shovelling them through the IR as constants. This lets
us shortcut the evaluation of (n)eq when both operands would be known
at compile-time (not likely). However, it also lets us safe a few more
locals, namely all the ones for MakeBooleanStmt.
* wasm: replace `opa_boolean()` by func returning interned bools
The new function will end up having this body:
00b742 func[188] <opa_boolean>:
00b743: 41 8a d0 03 | i32.const 59402
00b747: 41 8c d0 03 | i32.const 59404
00b74b: 20 00 | local.get 0
00b74d: 1b | select
00b74e: 0b | end
Where the addresses correspond to our interned boolean `opa_value *`.
The previous implementation, should anyone need it, is still available
as `opa_boolean_allocated`. It's used in tests, too, where we do not
have the `opa_boolean()` emitted by our Wasm compiler.
* wasm: br_if/br optimizations for constants
* wasm: remove AssignBooleanStmt and opa_value_boolean_set
This could be trouble for our interned opa_boolean_t's, but it's not used.
So, let's just get rid of it.
* wasm: avoid some blocks where possible
Due to how the planner plans functions, any partial rule defining a
set or an object would have a block like this:
block
call 208 <opa_object>
local.set 2
end
With this change, those will no longer be wrapped.
It's not a big deal, neither in what it gets us, nor in what it takes
to apply the optimization.
* wasm: add one-branched if, use in memoization
* wasm: de-block internal calls
I've been comparing our instructions to what wasm-opt does to them, and
this seems like a reasonable change.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
Before, the added/altered test cases would have failed: it came down to the
(undefined) data being a==NULL in opa_value_merge.
Fixes#3130.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
* wasm: fix caching of mpd values over multiple runs
The minimal test case included would fail because on the second run,
the global `initialized`, used in `mpd.c` to record that `mpd_one` had
been prepared, was true; whereas the value that `mpd_one` pointed to
no longer was a valid mpd_t struct. The addition happening in the loop
of the `numbers.range` implementation would thus fail to add NaN to 1,
and everything goes downhill from there.
To remedy this, we expose the init function as `opa_mpd_init`, and
call it from the module's `Start` function (`_initialize`). As a side
effect, tests in test.c (`make wasm-lib-tests`) that use mpd need to
have opa_mpd_init run, too. Those tests are not randomized, so seems
we're OK with having that executed by the added tests, fairly early on
in test.c
Fixes#3110.
Also: wasm/tests/test.c: add `void`s
A consistency thing. I had removed them earlier, but I've come to
understand it's better with than without.
(https://stackoverflow.com/questions/41803937/func-vs-funcvoid-in-c99)
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
* wasm: optimize package access with non-ground refs using call_indrect
We now
1. write an object corresponding to data paths into the module data
2. initialize an opa_object_t from that using `_initialize`, called
as the module's Start function
3. write out CallDynamicStmts in IR when the ref is not all ground,
but its vars have been seen
4. compile those CallDynamicStmts to call_indirect invocations in
WASM, preceded by a lookup using the path in the object prepared
in (2.)
5. if the lookup fails to come up with a result, the eval goes
undefined
What it looks like:
With t.rego as
package t
p {
data.foo[input.x].bar.p
}
and foo.rego as
package foo.a.bar
p = true
when building policy.wasm using `opa build -t wasm -e t/p t.rego foo.rego`,
the body of function `g0.data.t.p` will contain
i32.const 5
call $opa_array_with_cap
local.set $11
local.get $11
local.get $7
call $opa_array_append
local.get $11
local.get $8
call $opa_array_append
local.get $11
local.get $6
call $opa_array_append
local.get $11
local.get $9
call $opa_array_append
local.get $11
local.get $10
call $opa_array_append
local.get $0
local.get $1
local.get $11
call $opa_mapping_lookup
local.tee $12
i32.eqz
br_if $block
local.get $12
call_indirect $29 (type $1)
local.tee $13
i32.eqz
br_if $block
Where the array-related functions build an array of
["g0", "foo", input.x, "bar", "p"]
and pass that to `opa_mapping_lookup` to determine the element index to
pass to `call_indirect`. The lookup function returns 74 from the JSON
blob put into the data section,
(data $38 (i32.const 56485)
"{\"g0\": {\"foo\": {\"a\": {\"bar\": {\"p\": 74}}}, \"t\": {\"p\": 75}}}")
iff input.x happens to be "a". Otherwise, it'll return 0, and the result
will end up being undefined.
Element 74 of the modules func table is, of course, $g0.data.foo.a.bar.p:
(elem $33 (i32.const 74)
$g0.data.foo.a.bar.p $g0.data.t.p)
($33 is some id of that piece of function table, an artifact of the
`wavm disassemble` output.)
* compiler/wasm: add memoization to call_indirect logic
- adds a data segment for mapping element indices (used with call_indirect)
to function indices (as used with opa_memoize_{get,insert})
- emits mapping function elem -> func idx that uses that data segment
- wires up memoization lookup and insert in call_indirect code path
The added test case would cause `make wasm-rego-test` to fail like this
if memoization wasn't happening:
ERROR 019_call_indirect_optimization.json: memoization: should have been memoized
* planner: add debug messages, carry them over into the compiler
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
When we've removed the --export-all from the build of opa-test.wasm in
https://github.com/open-policy-agent/opa/pull/3061, we've robbed
wasm/test.js of the ability to see and run them.
Now, the existing tests have been explicitly exported, and the test
runner was adapted to fail if nothing was run at all.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
In topdown, we have two different error modes: strict/non-strict.
In WASM, everything is meant to be non-strict. Thus errors that
only appear in topdown with strict mode are annotated as such,
and checked for an empty result-set in the WASM test runner.
Several WASM builtins that have returned an error where they should
return NULL have been adjusted.
This allows us to fix most of the exceptions brought up in #2954.
Notable pieces:
* wasm sdk: ignore builtin errors
This should be in line with the non-strict builtin error semantics used
in WASM.
Before, when the WASM SDK had called out top a topdown-defined builtin,
and that builtin had returned an error, the WASM caller returned that
error. It's been at odds with how topdown evaluated builtin errors when
run without strict builtin errors.
Now, the errors are properly ignored, except for topdown.Halt. That one
doesn't seem like it's used at the moment, at least from this code base.
* cases: add want_result where non-strict eval yields something
This happens to work for both topdown and wasm:
- in topdown, the test runner checks for expected errors first, and
ignores the wanted result;
- in wasm, we check for a desired result first, checking the error
if no result was defined.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
Fixes#2926.
This is in line with what topdown does.
Changed opa_value_merge instead of introducing another function since
its seemed to be limited to this one case.
Also removed all object merge conflict test cases, since that wasm runtime error can't happen anymore now.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
Co-authored-by: Torin Sandall <torinsandall@gmail.com>
I'm not exactly sure why we had been rounding here before. Topdown truncates
when formatting a decimal number as int:
format_int(15.9, 16) == "f"
format_int(-15.9, 16) == "-f"
Fixes#2923.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
Previously we returned undefined rather than false, this changes the
c implementation to match the golang one and return false if the
parameter was the wrong type.
Fixes: #2925
Signed-off-by: Patrick East <east.patrick@gmail.com>
This commit updates the C library to expose a global key-value mapping
that can be initialized and supports push/pop operations for
shadowing. The key-value mapping is implemented using opa_object_t to
keep things simple. In the future, this could be replaced with
something more efficient.
The wasm compiler uses the key-value mapping to memoize calls to
planned functions that only depend on input and data. The compiler
uses the function index as the key and the function return value as
the value. The choice to memoize at the call-site as opposed to inside
planned functions was arbitrary.
Signed-off-by: Torin Sandall <torinsandall@gmail.com>
Previously the C library was not escaping non-string object
before serializing them--this would break callers that expect
valid JSON output from opa_json_dump. With this change,
opa_json_dump will serialize/escape non-string object
keys. opa_value_dump retains the old behaviour.
Signed-off-by: Torin Sandall <torinsandall@gmail.com>
split("", <delim>) should return [""]. The implementation was not
handling the empty string case or more generally where the string is
shorter than the delimiter.
Signed-off-by: Torin Sandall <torinsandall@gmail.com>
Unlike the golang builtin, this does not support caching of compiled
patterns across evaluations.
The glob builtin builds on regex builtins, compiling the glob to regex
and then using regex builtins to execute the actual matching.
Signed-off-by: Teemu Koponen <koponen@styra.com>
This commit adds support into the C library for parsing and dumping
set literals without representing them as arrays (we use the Rego
convention of curly-braces and set() for emptiness.) The parsing and
dumping that supports set literals is exposed via new opa_value_parse
and opa_value_dump functions (respectively).
Fixes#2773
Signed-off-by: Torin Sandall <torinsandall@gmail.com>
There are three new API's implemented and exposed from the C code:
```
opa_value_add_path
opa_value_remove_path
```
and a new helper:
```
opa_object_remove
```
The first two provide similar functionality as the OPA stores "add"
and "remove" op (same style of path). The main difference for the add
is that it will create intermediate objects as required, we do not
have a separate `mkdir` operation like the store does.
Signed-off-by: Patrick East <east.patrick@gmail.com>
These builtins should operate on codepoints, not on characters. This
also improves the string conversion from a memory byte array holding
UTF-8 string to a valid JavaScript string which is UTF-16.
The improved unicode tests were provided by Anders Eknert
<anders.eknert@bisnode.com>.
Signed-off-by: Teemu Koponen <koponen@styra.com>
Split the single free list to many: each list holds chunks of specific
size, and therefore, while searching for a free block, identifying the
right list is cheap. To reduce fragmentation all but the list with
largest chunks holds fixed size blocks.
The number of free lists and chunk sizes (currently 4, 8, 16, 64, and
128+ bytes) warrant proper tuning.
Signed-off-by: Teemu Koponen <koponen@styra.com>
Previously the parser was constructing strings and numbers with
references to the input buffer memory. If that memory was freed after
the opa_json_parse() call, it would corrupt the strings and numbers
returned by the parse.
This commit just updates the parser to create a copy of the
string/number values. If this becomes a performance issue in the
future, we can introduce an optional API for callers that promise NOT
to free the input buffer.
Signed-off-by: Torin Sandall <torinsandall@gmail.com>
A lot of the tests assume knowledge about the state of the free block
list and usage of the heap. This gets thrown off when >1 test is
messing around with the heap, and the ordering of tests isn't
guaranteed.
This changes to do a hacky reset to reset the heap to a starting
position at the current heap top. This simulates a "fresh" vm with
no pre-allocated memory but leaks anything up until then.
Signed-off-by: Patrick East <east.patrick@gmail.com>
To help reduce fragmentation we will now have a minimum of 16 byte
sized allocation block. In testing with JSON parsed objects we
generate a significant amount of 12 and 16 byte allocations for the
container structs for opa values, the size chosen should fit the
majority of them. In addition we will not split free blocks unless
the remainder is big enough to make additional allocations.
Testing with a relatively large (6MB) nested JSON object being parsed
this cuts the length of our free block list from a few thousand down
to zero. The time it takes to parse it (on my machine) goes from about
30 seconds to a few hundred milliseconds.
Signed-off-by: Patrick East <east.patrick@gmail.com>
Anders Eknert