It's mostly useless, but aren't we all.
Also added benchmarks to make sure I didn't mess anything up. And one or
two tiny but unrelated fixes.
---------
Signed-off-by: Anders Eknert <anders.eknert@apple.com>
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
Co-authored-by: Stephan Renatus <stephan.renatus@gmail.com>
* wasm: update wabt and binaryen in builder image
* wasm: bump ubuntu and llvm
* wasm: bump LLVM 13 -> 21, adjust headers
* wasm: make docker optional
We depend on it in our builds, but if you happen to bring
clang (LLVM 21)
clang++ (LLVM 21)
wasm-ld (LLVM 21)
wasm2wat (wabt)
wasm-opt (binaryen)
node
you should be able to build the opa.wasm blob without the docker image.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
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
In the Wasm modules built with OPA, arithmetic comparison for very large numbers
could be wrong, caused by an integer overflow.
Fixes#6991.
Signed-off-by: Pierre Troger <pierre@narval.xyz>
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>
When feeding a `char *` into `re->Match()`, it was converted to a StringPiece,
taking its size as `strlen()`. For our (long) input, that wasn't resulting in
the correct size, and did then freak out the re2 match input validation if the
regular expression has an end anchor, but the endpos wasn't the same as its
length. Since the endpos was taken from `s->len`, and the "length" taken via
the mentioned StringPiece's strlen() call, they did indeed not match.
Worked around by feeding it a properly-constructed std::string instead. I'm a
C++ novice at best, but it does the trick, and I'm reasonable certain it's less
wrong than before.
Fixes#6376.
Signed-off-by: Stephan Renatus <stephan@styra.com>
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 change allows rules to have string prefixes in their heads -- we've
come to call them "ref heads".
String prefixes means that where before, you had
package a.b.c
allow = true
you can now have
package a
b.c.allow = true
This allows for more concise policies, and different ways to structure
larger rule corpuses.
Backwards-compatibility:
- There are code paths that accept ast.Module structs that don't necessarily
come from the parser -- so we're backfilling the rule's Head.Reference
field from the Name when it's not present.
This is exposed through (Head).Ref() which always returns a Ref.
This also affects the `opa parse` "pretty" output:
With x.rego as
package x
import future.keywords
a.b.c.d if true
e[x] if true
we get
$ opa parse x rego
module
package
ref
data
"x"
import
ref
future
"keywords"
rule
head
ref
a
"b"
"c"
"d"
true
body
expr index=0
true
rule
head
ref
e
x
true
body
expr index=0
true
Note that
Name: e
Key: x
becomes
Reference: e[x]
in the output above (since that's how we're parsing it, back-compat edge cases aside)
- One special case for backcompat is `p[x] { ... }`:
rule | ref | key | value | name
------------------------+-------+-----+-------+-----
p[x] { ... } | p | x | nil | "p"
p contains x if { ... } | p | x | nil | "p"
p[x] if { ... } | p[x] | nil | true | ""
For interpreting a rule, we now have the following procedure:
1. if it has a Key, it's a multi-value rule; and its Ref defines the set:
Head{Key: x, Ref: p} ~> p is a set
^-- we'd get this from `p contains x if true`
or `p[x] { true }` (back compat)
2. if it has a Value, it's a single-value rule; its Ref may contain vars:
Head{Ref: p.q.r[s], Value: 12} ~> body determines s, `p.q.r.[s]` is 12
^-- we'd get this from `p.q.r[s] = 12 { s := "whatever" }`
Head{Key: x, Ref: p[x], Value: 3} ~> `p[x]` has value 3, `x` is determined
by the rule body
^-- we'd get this from `p[x] = 3 if x := 2`
or `p[x] = 3 { x := 2 }` (back compat)
Here, the Key isn't used, it's present for backwards compatibility: for ref-
less rule heads, `p[x] = 3` used to be a partial object: key x, value 3,
name "p"
- The destinction between complete rules and partial object rules disappears.
They're both single-value rules now.
- We're now outputting the refs of the rules completely in error messages, as
it's hard to make sense of "rule r" when there's rule r in package a.b.c and
rule b.c.r in package a.
Restrictions/next steps:
- Support for ref head rules in the REPL is pretty poor so far. Anything that
works does so rather accidentally. You should be able to work with policies
that contain ref heads, but you cannot interactively define them.
This is because before, we'd looked at REPL input like
p.foo.bar = true
and noticed that it cannot be a rule, so it's got to be a query. This is no
longer the case with ref heads.
- Currently vars in Refs are only allowed in the last position. This is expected
to change in the future.
- Also, for multi-value rules, we can not have a var at all -- so the following
isn't supported yet:
p.q.r[s] contains t if { ... }
-----
Most of the work happens when the RuleTree is derived from the ModuleTree -- in
the RuleTree, it doesn't matter if a rule was `p` in `package a.b.c` or `b.c.p`
in `package a`.
As such, the planner and wasm compiler hasn't seen that many adaptations:
- We're putting rules into the ruletree _including_ the var parts, so
p.q.a = 1
p.q.[x] = 2 { x := "b" }
end up in two different leaves:
p
`-> q
`-> a = 1
`-> [x] = 2`
- When planing a ref, we're checking if a rule tree node's children have
var keys, and plan "one level higher" accordingly:
Both sets of rules, p.q.a and p.q[x] will be planned into one function
(same as before); and accordingly return an object {"a": 1, "b": 2}
- When we don't have vars in the last ref part, we'll end up planning
the rules separately. This will have an effect on the IR.
p.q = 1
p.r = 2
Before, these would have been one function; now, it's two. As a result,
in Wasm, some "object insertion" conflicts can become "var assignment
conflicts", but that's in line with the now-new view of "multi-value"
and "single-value" rules, not partial {set/obj} vs complete.
* planner: only check ref.GroundPrefix() for optimizations
In a previous commit, we've only mapped
p.q.r[7]
as p.q.r; and as such, also need to lookup the ref
p.q.r[__local0__]
via p.q.r
(I think. Full disclosure: there might be edge cases here that are unaccounted
for, but right now, I'm aiming for making the existing tests green...)
New compiler stage:
In the compiler, we're having a new early rewriting step to ensure that the
RuleTree's keys are comparible. They're ast.Value, but some of them cause us
grief:
- ast.Object cannot be compared structurally; so
_, ok := map[ast.Value]bool{ast.NewObject([2]*ast.Term{ast.StringTerm("foo"), ast.StringTerm("bar")}): true}[ast.NewObject([2]*ast.Term{ast.StringTerm("foo"), ast.StringTerm("bar")})]
`ok` will never be true here.
- ast.Ref is a slice type, not hashable, so adding that to the RuleTree would
cause a runtime panic:
p[y.z] { y := input }
is now rewritten to
p[__local0__] { y := input; __local0__ := y.z }
This required moving the InitLocalVarGen stage up the chain, but as it's still
below ResolveRefs, we should be OK.
As a consequence, we've had to adapt `oracle` to cope with that rewriting:
1. The compiler rewrites rule head refs early because the rule tree expects
only simple vars, no refs, in rule head refs. So `p[x.y]` becomes
`p[local] { local = x.y }`
2. The oracle circles in on the node it's finding the definition for based
on source location, and the logic for doing that depends on unaltered
modules.
So here, (2.) is relaxed: the logic for building the lookup node stack can
now cope with generated statements that have been appended to the rule bodies.
There is a peculiarity about ref rules and extents:
See the added tests: having a ref rule implies that we get an empty object
in the full extent:
package p
foo.bar if false
makes the extent of data.p: {"foo": {}}
This is somewhat odd, but also follows from the behaviour we have right now
with empty modules:
package p.foo
bar if false
this also gives data.p the extent {"foo": {}}.
This could be worked around by recording, in the rule tree, when a node was
added because it's an intermediary with no values, but only children.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
It had slipped my mind that those need docker, too. Previously, I've disabled
docker for those tests to avoid having them rebuild their wasm artifacts.
The wasm/Makefile change is superficial, and just meant to ensure we run this
test while the PR is WIP. Changes to .github/workflow/* alone won't trigger the
wasm tests.
Signed-off-by: Stephan Renatus <stephan.renatus@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>
This commit updates the `*.is_valid` functions to no longer produce
errors when providing wrong-typed arguments. Instead, they will now
return true/false for all inputs. Tests and WASM versions of these
builtins have been updated to match the new behavior.
Fixes#4760.
Signed-off-by: Philip Conrad <philipaconrad@gmail.com>
This commit extends the go and wasm implementations of object.get to
allow a key to also be an array.
When passed an array, each element in the array will be used as a key in
turn. This allows values at deeply nested paths to be extracted from
objects.
It also supports getting indexes of nested arrays.
The functionality was originally inspired by Ruby's Hash.dig function:
https://ruby-doc.org/core-2.3.0_preview1/Hash.html#method-i-dig however
we opted to include the behavior in object.get instead after being
uncertain 'dig' was a commonly understood name.
Signed-off-by: Charlie Egan <charlieegan3@users.noreply.github.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>
Before, we'd either trap with out-of-bounds memory access, or other weird
behaviour.
Included some code cosmetics in pool.go, replacing `for` loop with a `copy`.
Added tests to opa_test.go.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
This sets the stage for eventually allowing OPA wasm modules that do NOT
import memory.
With this change, we add the necessary segments to the wasm module that
declare that memory is to be imported, in the wasm compiler. As far as
LLVM and our C base is concerned, the memory is NOT imported.
The test runners have been adapted, `make wasm-lib-test` works without
having imported memory now. `make wasm-rego-test` can deal with both: it
will provide memory in its `imports` for instantiation, but if the wasm
module happens to not want that import, it'll be ignored. The memory used
in the other host methods is the exported one. (Whether that is exported
or re-exported imported doesn't make a difference.)
Some first steps have been included to make OPA's Wasm SDK work without
imported memory. There are a few loose ends around enforcing memory
limits, to be taken care of later.
----
This also addresses a problem we've seen in the wild before: when our
additions to the wasm modules' data segments exceed the number of pages
needed for the memory import, a "data segment overflowing memory" issue
could have happened. That was because the minimal memory size for the
imported memory was determined by LLVM, and we'd just squeeze our added
data segments in, without adjusting that limit.
Now, the limit will be set properly; and if a too small memory was
provided, a more descriptive failure will happen at instantiation time.
Wasmtime, for example, raises
incompatible import type for `env::memory`
Caused by:
memory types incompatible
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
The builtin rules are what causes `make` to attempt to build `src/libc++/mutex`
from `src/libc++/mutex.cc`. The build call will fail like this,
clang++-12 -std=c++17 -MD -MP -nodefaultlibs --target=wasm32-unknown-unknown-wasm -fno-exceptions -fno-rtti -I src/lib -I src/libc++ -I /usr/lib/llvm-12/include/c++/v1 -I /usr/lib/llvm-12/lib/clang/12.0.0/include -I src/re2 -D_LIBCPP_HAS_NO_THREADS -D_LIBCPP_HAS_NO_LIBRARY_ALIGNED_ALLOCATION -O3 src/libc++/mutex.cc -o src/libc++/mutex
clang: error: unable to execute command: Executable "wasm-ld" doesn't exist!
clang: error: linker command failed with exit code 1 (use -v to see invocation)
and leave the working tree in a state where `src/libc++/mutex` is deleted,
since it was truncated by the `-o` argument to the cpp compiler, and an
untracked `src/libc++/mutex.d` dependency file was created, also by that
call (and its -MD -MP args).
With this change, these implicit rules are turned off: we don't want any
rules we haven't built ourselves here. `src/libc++/mutex` is a stub header
file, and has no ending.
We're also adding an extra rule to remove the pitfall for anyone calling
`make` themselves, outside of our build make targets.
Signed-off-by: Stephan Renatus <stephan.renatus@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>
* wasm/sdk: check version, call old eval path for ABI 1.1
Fixes#3146.
* docs/wasm: document addition as ABI 1.2
* wasm-sdk: overwrite previous inputs, don't accumulate them
There is a little room for optimization here, should the input
ever grow so large that it eats up too much precious heap space,
we could look into changing this so that the memory used for it
can be reclaimed.
* internal/compiler/wasm: commit generated wasm
I've noticed that since the CI build running on macos-latest doesn't
have docker installed, it cannot update these files itself at build
time. We thus end up with macos binaries that have the wasm binary
data from the main branch, not the PR.
This can be observed from the test failure:
Run make ci-binary-smoke-test-wasm BINARY=opa_darwin_amd64
chmod +x "_release/0.31.0-dev/opa_darwin_amd64"
"_release/0.31.0-dev/opa_darwin_amd64" eval -t "wasm" 'time.now_ns()'
make: *** [ci-binary-smoke-test-wasm] Error 2
{
"errors": [
{
"message": "caller not found: opa_eval (opa_eval)"
}
]
}
Error: Process completed with exit code 2.
Since I had previously commit the CSV data that drives the dead
code elimination process, that optimization had failed to find a
function it expected to have.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
* wasm: count() invalid utf-8 runes, don't abort
Previously, we'd bail out when the string count() is given contained
anything that isn't a valid utf-8 rune. Now, we'll have it count the
invalid chars -- they're replaced by chartorune() in the same manner
as happens when passing casting the string to []rune in golang:
package main
import (
"encoding/base64"
"fmt"
)
func main() {
sample, _ := base64.StdEncoding.DecodeString("2E84ZuPUd7zfvCZSNEchVpDEIj6PL7JfLpIqyxVG16k=")
fmt.Printf("% x\n%x\n%d, %d\n", sample, []rune(string(sample)), len(sample), len([]rune(string(sample))))
}
This yields:
d8 4f 38 66 e3 d4 77 bc df bc 26 52 34 47 21 56 90 c4 22 3e 8f 2f b2 5f 2e 92 2a cb 15 46 d7 a9
[fffd 4f 38 66 fffd fffd 77 fffd 7fc 26 52 34 47 21 56 fffd fffd 22 3e fffd 2f fffd 5f 2e fffd 2a fffd 15 46 5e9]
32, 30
Where fffd is the replacement char whenever something isn't a proper rune.
* topdown/builtins: fix indexof() result when using unicode
Previously, indexof() would count unicode characters as strings, so
indexof("μx", "x")
would return 2 insteads of 1.
Now, we're converting to rune and compare explicitly, returnig the
proper result.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
It's become apparent that a call to opa_abort in opa_agg_count did NOT
stop execution. Failures in bad input there haven't been thoroughly tested.
Comparing to the calls to opa_abort that happen in compiler-emitted code
(as opposed to calls in the C portion of our wasm code base), we find that
they are always emitting `unreachable` after the call to opa_abort.
As it turns out, doing the same thing in the C parts fixes the problem.
It thus seems like this is somehow related to changes in wasmtime's
cranelift (or its backend). It's never wrong to give the compiler some
more information that we can readily share, so let's put some `unreachable`
into the their proper places.
To avoid touching the entire code base of the C parts, we're defining a
function called `opa_abort(msg)` that'll call `opa_abort_(msg)` followed
by `__builtin_unreachable()`, which gives us that instruction. `opa_abort_`
in turn is imported as `opa_abort`, to keep compatibility with any SDKs
out there.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
Without the added _LIBCPP_HAS_NO_LIBRARY_ALIGNED_ALLOCATION, the
build would fail looking for posix_memalign. Having added that,
the build failed because it's missing the symbol std::align_val_t.
It looks like everything is fine without those methods, so they
have been removed.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
* wasm-e2e: fix test runner, adapt and include jsonpatch tests
The `sort_bindings` key now is interpreted a little differently now: it's
no longer sorting and comparing, but building two sets and compares them.
From the test author's perspective, nothing has changed, except that it
now actually compares them.
Fixes#2949.
* exported tests: don't sort test expectations
This leads to very weird situations, and seems to only be a convenience
for the test authors. So, instead, we'll have the test authors pin down
whatever the sorted bindings are, and assert that the sorted bindings of
the returned result set match.
* wasm: fix regex.find_all_string_submatch_n with n != -1
Fixes#3352.
* wasm: unify objects that contain vars
Unification only happens by the reused existing code path, but we still
have to assert equality of the rest.
Fixes#3351.
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>
We're in this situation: performing dead code analysis on wasm isn't too
hard, but it requires a representation of all wasm instructions: we'd need
to be able to parse the "runtime" wasm bits, i.e., what's built using llvm
from C code. When building upon that wasm module, we process the function
bodies uninterpreted -- they are all just `[]byte` to us.
This restriction lets us get by without implementing all the wasm
instructions -- we only write what we use, and read a bare minimum to work
as outlined above.
To still be able to remove dead code, this change employs a trick: at build
time, when the aforementioned runtime wasm module is compiled, we're calling
wasm-opt on it to extract its call graph. We'll use that, together with the
functions actually planned in our wasm compiler (using the subset of
instructions that we understand), to remove all unused functions from the
name section, and replace their function bodies with `unreachable`.
We cannot really remove them, since that would require reindexing all
functions; and we cannot do that without replacing the function indices at
their call sites in the "runtime" wasm module.
Another restriction to the impact of this approach is call_indirect: We
need to keep every function that's referenced in the table -- we don't know
which function might be calling them indirectly. In a follow-up, we could
record that information and use it to further reduce the code size: we know
that if none of the regex-related builtins are used, we could also stub out
the re2-related functions.
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>
Some smaller changes to the wasm-builder docker image:
- wabt: bump to latest release
- binaryen: add
Uses update-alternatives to select LLVM 11: Set up like this, we can
build binaryen without the trouble I had run into otherwise.
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>
Anders Eknert