Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

panic in virtual document cache #1197

Closed
tsandall opened this issue Feb 4, 2019 · 0 comments · Fixed by #1520
Closed

panic in virtual document cache #1197

tsandall opened this issue Feb 4, 2019 · 0 comments · Fixed by #1520
Assignees
@tsandall
Labels
bug

Comments

@tsandall
Copy link
Member

tsandall commented Feb 4, 2019

Actual Behavior

The virtual document cache is implemented on top of Go maps. If the ref contains an array operand, the insertion panics:

package foo

p[x] = null { x = [1] }

Query:

a = [1]; data.foo.p[a] = b

Panic:

panic: runtime error: hash of unhashable type ast.Array

goroutine 1 [running]:
github.com/open-policy-agent/opa/topdown.(*virtualCache).Put(0xc0002afc60, 0xc0002afda0, 0x4, 0x4, 0xc0002a5760)
	/home/torin/go/src/github.com/open-policy-agent/opa/topdown/cache.go:54 +0x134
github.com/open-policy-agent/opa/topdown.evalVirtualPartial.evalOneRule.func1.1(0xc0002a38c0, 0xc0002b1d00, 0xdad760)
	/home/torin/go/src/github.com/open-policy-agent/opa/topdown/eval.go:1617 +0x1e9
github.com/open-policy-agent/opa/topdown.(*eval).evalExpr(0xc0002a38c0, 0xc0001ce640, 0x1600b80, 0xc0002b1d90)
	/home/torin/go/src/github.com/open-policy-agent/opa/topdown/eval.go:170 +0x1b0
github.com/open-policy-agent/opa/topdown.(*eval).next(0xc0002a38c0, 0xc0001ce640, 0xc0002affc0, 0xfca2feafbf0d220)
	/home/torin/go/src/github.com/open-policy-agent/opa/topdown/eval.go:86 +0x39
github.com/open-policy-agent/opa/topdown.(*eval).evalStep.func1(0xc000263ca8, 0xa6dafe)
	/home/torin/go/src/github.com/open-policy-agent/opa/topdown/eval.go:204 +0x4c

If the ref operand is a set/object, the insertion doesn't panic, but the result will be incorrect.

Additional info

  • It would be acceptable to ignore the virtual cache if the ref operand contains composite values. This is uncommon and not supported in some cases, so it shouldn't impact users today.
@tsandall tsandall added the bug label Feb 4, 2019
@tsandall tsandall self-assigned this Apr 12, 2019
@tsandall tsandall mentioned this issue Jun 24, 2019
Merged
tsandall added a commit to tsandall/opa that referenced this issue Jun 24, 2019
@tsandall
topdown: Fix virtual cache to allow composite key terms
14cfa84 
Previously the virtual cache was implemented using a
map[ast.Value]... which works for scalar key terms but not composites
(because they're not comparable.) This change updates the virtual
cache to use a util.HashMap that supports all term kinds. This
prevents the virtual cache lookup/insert from panicing when a key like
data.x.y[[1]] is received.

In addition to fixing the virtual cache, this change updates the
Term.Equal() function to include an early-exit for types that do not
allocate in their Equal() functions.

The early-exit was added because swapping out the map[ast.Value]...
for util.HashMap introduced allocations into the virtual cache
lookup/insert operations which doubled the benchmark latency. See
below for benchmark results before/after this commit.

```
BEFORE
======
goos: linux
goarch: amd64
pkg: github.com/open-policy-agent/opa/topdown
BenchmarkVirtualCache-8   	 5000000	       284 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	github.com/open-policy-agent/opa/topdown	1.731s
Success: Benchmarks passed.

AFTER
=====
goos: linux
goarch: amd64
pkg: github.com/open-policy-agent/opa/topdown
BenchmarkVirtualCache-8   	 5000000	       322 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	github.com/open-policy-agent/opa/topdown	1.969s
Success: Benchmarks passed.
```

This change will also let us memoize virtual sets using the same cache
(see open-policy-agent#822).

Fixes open-policy-agent#1197

Signed-off-by: Torin Sandall <torinsandall@gmail.com>
patrick-east pushed a commit that referenced this issue Jun 24, 2019
@tsandall @patrick-east
topdown: Fix virtual cache to allow composite key terms
f33a2b2 
Previously the virtual cache was implemented using a
map[ast.Value]... which works for scalar key terms but not composites
(because they're not comparable.) This change updates the virtual
cache to use a util.HashMap that supports all term kinds. This
prevents the virtual cache lookup/insert from panicing when a key like
data.x.y[[1]] is received.

In addition to fixing the virtual cache, this change updates the
Term.Equal() function to include an early-exit for types that do not
allocate in their Equal() functions.

The early-exit was added because swapping out the map[ast.Value]...
for util.HashMap introduced allocations into the virtual cache
lookup/insert operations which doubled the benchmark latency. See
below for benchmark results before/after this commit.

```
BEFORE
======
goos: linux
goarch: amd64
pkg: github.com/open-policy-agent/opa/topdown
BenchmarkVirtualCache-8   	 5000000	       284 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	github.com/open-policy-agent/opa/topdown	1.731s
Success: Benchmarks passed.

AFTER
=====
goos: linux
goarch: amd64
pkg: github.com/open-policy-agent/opa/topdown
BenchmarkVirtualCache-8   	 5000000	       322 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	github.com/open-policy-agent/opa/topdown	1.969s
Success: Benchmarks passed.
```

This change will also let us memoize virtual sets using the same cache
(see #822).

Fixes #1197

Signed-off-by: Torin Sandall <torinsandall@gmail.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@tsandall tsandall

Labels
bug
Projects
Open Policy Agent
Archived in project
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

topdown: Fix virtual cache to allow composite key terms tsandall/opa
1 participant
@tsandall