Skip to content
This repository has been archived by the owner on May 25, 2023. It is now read-only.

IPSet.Ranges sometimes generates invalid IPRanges #125

Closed
danderson opened this issue Jan 27, 2021 · 3 comments
Closed

IPSet.Ranges sometimes generates invalid IPRanges #125

danderson opened this issue Jan 27, 2021 · 3 comments

Comments

@danderson
Copy link
Member

Found while implementing other functionality and writing tests. PR at #124 adds an assert that trips on the existing single_ips test.

--- FAIL: TestIPSet (0.00s)
    --- FAIL: TestIPSet/single_ips (0.00s)
        ipset.go:162: post-sort:
        ipset.go:142:  {  10.0.0.0        ✅
        ipset.go:144:   } 10.0.0.0        ✅
        ipset.go:142:  {  10.0.0.1        ✅
        ipset.go:144:   } 10.0.0.1        ✅
        ipset.go:142:  {  10.0.0.2        ✅
        ipset.go:144:   } 10.0.0.2        ✅
        ipset.go:142:  {  10.0.0.3        ✅
        ipset.go:144:   } 10.0.0.3        ✅
        ipset.go:142:  {  10.0.0.4        ❌
        ipset.go:142:  {  10.0.0.4        ✅
        ipset.go:144:   } 10.0.0.4        ❌
        ipset.go:144:   } 10.0.0.4        ✅
        ipset.go:164: merging...
        ipset.go:183: at[0] ({ip:{addr:{hi:0 lo:281470849515520} z:0xc000128060} want:true start:true}), add=1, remove=0
        ipset.go:183: at[1] ({ip:{addr:{hi:0 lo:281470849515520} z:0xc000128060} want:true start:false}), add=0, remove=0
        ipset.go:183: at[2] ({ip:{addr:{hi:0 lo:281470849515521} z:0xc000128060} want:true start:true}), add=1, remove=0
        ipset.go:183: at[3] ({ip:{addr:{hi:0 lo:281470849515521} z:0xc000128060} want:true start:false}), add=0, remove=0
        ipset.go:183: at[4] ({ip:{addr:{hi:0 lo:281470849515522} z:0xc000128060} want:true start:true}), add=1, remove=0
        ipset.go:183: at[5] ({ip:{addr:{hi:0 lo:281470849515522} z:0xc000128060} want:true start:false}), add=0, remove=0
        ipset.go:183: at[6] ({ip:{addr:{hi:0 lo:281470849515523} z:0xc000128060} want:true start:true}), add=1, remove=0
        ipset.go:183: at[7] ({ip:{addr:{hi:0 lo:281470849515523} z:0xc000128060} want:true start:false}), add=0, remove=0
        ipset.go:183: at[8] ({ip:{addr:{hi:0 lo:281470849515524} z:0xc000128060} want:false start:true}), add=0, remove=1
        ipset.go:183: at[9] ({ip:{addr:{hi:0 lo:281470849515524} z:0xc000128060} want:true start:true}), add=1, remove=1
        ipset.go:183: at[10] ({ip:{addr:{hi:0 lo:281470849515524} z:0xc000128060} want:false start:false}), add=1, remove=0
        ipset.go:183: at[11] ({ip:{addr:{hi:0 lo:281470849515524} z:0xc000128060} want:true start:false}), add=0, remove=0
        ipset.go:225: post-merge:
        ipset.go:142:  {  10.0.0.0        ✅
        ipset.go:144:   } 10.0.0.3        ✅
        ipset.go:142:  {  10.0.0.5        ✅
        ipset.go:144:   } 10.0.0.4        ✅
panic: internal error; end before start [recovered]
	panic: internal error; end before start

The sort looks reasonable, but post-merge we end up with the invalid range 10.0.0.5-10.0.0.4.

cc @bradfitz
@danderson
Copy link
Member Author

With more debugspam:

--- FAIL: TestIPSet (0.00s)
    --- FAIL: TestIPSet/single_ips (0.00s)
        ipset.go:169: post-sort:
        ipset.go:149:  {  10.0.0.0        ✅
        ipset.go:151:   } 10.0.0.0        ✅
        ipset.go:149:  {  10.0.0.1        ✅
        ipset.go:151:   } 10.0.0.1        ✅
        ipset.go:149:  {  10.0.0.2        ✅
        ipset.go:151:   } 10.0.0.2        ✅
        ipset.go:149:  {  10.0.0.3        ✅
        ipset.go:151:   } 10.0.0.3        ✅
        ipset.go:149:  {  10.0.0.4        ❌
        ipset.go:149:  {  10.0.0.4        ✅
        ipset.go:151:   } 10.0.0.4        ❌
        ipset.go:151:   } 10.0.0.4        ✅
        ipset.go:171: merging...
        ipset.go:190: at[0] ({ip:10.0.0.0 want:true start:true}), addDepth=1, rmDepth=0
        ipset.go:250: at[0] ({ip:10.0.0.0 want:true start:true}), keep want, out={ip:10.0.0.0 want:true start:true}
        ipset.go:190: at[1] ({ip:10.0.0.0 want:true start:false}), addDepth=0, rmDepth=0
        ipset.go:250: at[1] ({ip:10.0.0.0 want:true start:false}), keep want, out={ip:10.0.0.0 want:true start:false}
        ipset.go:190: at[2] ({ip:10.0.0.1 want:true start:true}), addDepth=1, rmDepth=0
        ipset.go:243: at[2] ({ip:10.0.0.1 want:true start:true}), merge prior, out={ip:10.0.0.0 want:true start:true}
        ipset.go:190: at[3] ({ip:10.0.0.1 want:true start:false}), addDepth=0, rmDepth=0
        ipset.go:250: at[3] ({ip:10.0.0.1 want:true start:false}), keep want, out={ip:10.0.0.1 want:true start:false}
        ipset.go:190: at[4] ({ip:10.0.0.2 want:true start:true}), addDepth=1, rmDepth=0
        ipset.go:243: at[4] ({ip:10.0.0.2 want:true start:true}), merge prior, out={ip:10.0.0.0 want:true start:true}
        ipset.go:190: at[5] ({ip:10.0.0.2 want:true start:false}), addDepth=0, rmDepth=0
        ipset.go:250: at[5] ({ip:10.0.0.2 want:true start:false}), keep want, out={ip:10.0.0.2 want:true start:false}
        ipset.go:190: at[6] ({ip:10.0.0.3 want:true start:true}), addDepth=1, rmDepth=0
        ipset.go:243: at[6] ({ip:10.0.0.3 want:true start:true}), merge prior, out={ip:10.0.0.0 want:true start:true}
        ipset.go:190: at[7] ({ip:10.0.0.3 want:true start:false}), addDepth=0, rmDepth=0
        ipset.go:250: at[7] ({ip:10.0.0.3 want:true start:false}), keep want, out={ip:10.0.0.3 want:true start:false}
        ipset.go:190: at[8] ({ip:10.0.0.4 want:false start:true}), addDepth=0, rmDepth=1
        ipset.go:190: at[9] ({ip:10.0.0.4 want:true start:true}), addDepth=1, rmDepth=1
        ipset.go:190: at[10] ({ip:10.0.0.4 want:false start:false}), addDepth=1, rmDepth=0
        ipset.go:229: at[10] ({ip:10.0.0.4 want:false start:false}), drop>want out={ip:10.0.0.5 want:true start:true}
        ipset.go:190: at[11] ({ip:10.0.0.4 want:true start:false}), addDepth=0, rmDepth=0
        ipset.go:250: at[11] ({ip:10.0.0.4 want:true start:false}), keep want, out={ip:10.0.0.4 want:true start:false}
        ipset.go:254: post-merge:
        ipset.go:149:  {  10.0.0.0        ✅
        ipset.go:151:   } 10.0.0.3        ✅
        ipset.go:149:  {  10.0.0.5        ✅
        ipset.go:151:   } 10.0.0.4        ✅

Everything works fine until we hit 10.0.0.4. The two starts are ignored (first because it's a remove, second because it's within a remove). Then the first end is treated as a transition from drop->want, which adds a point for 10.0.0.5, and finally the last point adds a range end for 10.0.0.4.

One way to fix it would be to have the sorting reverse ordering when want=false, start=false, so that in this test case, the nesting would go:

  • want=false start=true
  • want=true start=true
  • want=true start=false
  • want=false start=true

I think this only matters in cases where an add range and a remove overlap exactly.

@danderson
Copy link
Member Author

Fixed one set of issues with the change I suggested above, but now hitting other edge conditions I'm still working on.

danderson added a commit that referenced this issue Jan 27, 2021
@danderson
ipset: order range ends the opposite of range starts.
8350763 
The effect is to correctly nest start(want=false),start(want=true),
end(want=true),end(want=false) rather than alternating want={true,false}.

Corrects part of #125.

Signed-off-by: David Anderson <[email protected]>
danderson added a commit that referenced this issue Jan 27, 2021
@danderson
ipset: reimplement with a (somewhat) easier to follow algorithm.
0afcbbc 
The main goal was to fix #125 by providing a less tricky implementation
of Ranges as a comparison baseline... But this implementation turns out
to also be a bit faster and memory efficient.

Fixes #125.

name         old time/op    new time/op    delta
IPSetFuzz-8    16.3µs ± 3%    14.1µs ± 1%  -12.99%  (p=0.008 n=5+5)

name         old alloc/op   new alloc/op   delta
IPSetFuzz-8    2.60kB ± 0%    1.95kB ± 0%  -25.24%  (p=0.008 n=5+5)

name         old allocs/op  new allocs/op  delta
IPSetFuzz-8      33.0 ± 0%      30.0 ± 0%   -9.09%  (p=0.008 n=5+5)

Signed-off-by: David Anderson <[email protected]>
@danderson
Copy link
Member Author

Ended up reimplementing IPSet.Ranges with an algorithm that (I think) is easier to follow, fixes this bug, and also happens to be a little bit faster. Cleaning up PR for review now.

danderson added a commit that referenced this issue Jan 27, 2021
@danderson
ipset: reimplement with a (somewhat) easier to follow algorithm.
56caec2 
The main goal was to fix #125 by providing a less tricky implementation
of Ranges as a comparison baseline... But this implementation turns out
to also be a bit faster and memory efficient.

Fixes #125.

name         old time/op    new time/op    delta
IPSetFuzz-8    16.3µs ± 3%    14.1µs ± 1%  -12.99%  (p=0.008 n=5+5)

name         old alloc/op   new alloc/op   delta
IPSetFuzz-8    2.60kB ± 0%    1.95kB ± 0%  -25.24%  (p=0.008 n=5+5)

name         old allocs/op  new allocs/op  delta
IPSetFuzz-8      33.0 ± 0%      30.0 ± 0%   -9.09%  (p=0.008 n=5+5)

Signed-off-by: David Anderson <[email protected]>
danderson added a commit that referenced this issue Jan 27, 2021
@danderson
ipset: reimplement with a (somewhat) easier to follow algorithm.
eac2f63 
The main goal was to fix #125 by providing a less tricky implementation
of Ranges as a comparison baseline... But this implementation turns out
to also be a bit faster and memory efficient.

Fixes #125.

name         old time/op    new time/op    delta
IPSetFuzz-8    16.3µs ± 3%    14.1µs ± 1%  -12.99%  (p=0.008 n=5+5)

name         old alloc/op   new alloc/op   delta
IPSetFuzz-8    2.60kB ± 0%    1.95kB ± 0%  -25.24%  (p=0.008 n=5+5)

name         old allocs/op  new allocs/op  delta
IPSetFuzz-8      33.0 ± 0%      30.0 ± 0%   -9.09%  (p=0.008 n=5+5)

Signed-off-by: David Anderson <[email protected]>
danderson added a commit that referenced this issue Jan 27, 2021
@danderson
ipset: reimplement with a (somewhat) easier to follow algorithm.
117f074 
The main goal was to fix #125 by providing a less tricky implementation
of Ranges as a comparison baseline... But this implementation turns out
to also be a bit faster and memory efficient.

Fixes #125.

name         old time/op    new time/op    delta
IPSetFuzz-8    16.3µs ± 3%    14.1µs ± 1%  -12.99%  (p=0.008 n=5+5)

name         old alloc/op   new alloc/op   delta
IPSetFuzz-8    2.60kB ± 0%    1.95kB ± 0%  -25.24%  (p=0.008 n=5+5)

name         old allocs/op  new allocs/op  delta
IPSetFuzz-8      33.0 ± 0%      30.0 ± 0%   -9.09%  (p=0.008 n=5+5)

Signed-off-by: David Anderson <[email protected]>
danderson added a commit that referenced this issue Jan 27, 2021
@danderson
ipset: reimplement with a (somewhat) easier to follow algorithm.
d6a364c 
The main goal was to fix #125 by providing a less tricky implementation
of Ranges as a comparison baseline... But this implementation turns out
to also be a bit faster and memory efficient.

Fixes #125.

name         old time/op    new time/op    delta
IPSetFuzz-8    16.3µs ± 3%    14.1µs ± 1%  -12.99%  (p=0.008 n=5+5)

name         old alloc/op   new alloc/op   delta
IPSetFuzz-8    2.60kB ± 0%    1.95kB ± 0%  -25.24%  (p=0.008 n=5+5)

name         old allocs/op  new allocs/op  delta
IPSetFuzz-8      33.0 ± 0%      30.0 ± 0%   -9.09%  (p=0.008 n=5+5)

Signed-off-by: David Anderson <[email protected]>
danderson added a commit that referenced this issue Jan 27, 2021
@danderson
Reimplement IPSet.Ranges with a (somewhat) easier to follow algorithm.
8e07aed 
The main goal was to fix #125 by providing a less tricky implementation
of Ranges as a comparison baseline... But this implementation turns out
to also be a bit faster and more memory efficient.

Fixes #125.

name         old time/op    new time/op    delta
IPSetFuzz-8    16.3µs ± 3%    14.1µs ± 1%  -12.99%  (p=0.008 n=5+5)

name         old alloc/op   new alloc/op   delta
IPSetFuzz-8    2.60kB ± 0%    1.95kB ± 0%  -25.24%  (p=0.008 n=5+5)

name         old allocs/op  new allocs/op  delta
IPSetFuzz-8      33.0 ± 0%      30.0 ± 0%   -9.09%  (p=0.008 n=5+5)

Signed-off-by: David Anderson <[email protected]>
danderson added a commit that referenced this issue Jan 27, 2021
@danderson
Add regression test for #125.
4bcf3b6 
Signed-off-by: David Anderson <[email protected]>
danderson added a commit that referenced this issue Jan 29, 2021
@danderson
Reimplement IPSet.Ranges with a (somewhat) easier to follow algorithm.
1b83c2c 
The main goal was to fix #125 by providing a less tricky implementation
of Ranges as a comparison baseline... But this implementation turns out
to also be a bit faster and more memory efficient.

Fixes #125.

name         old time/op    new time/op    delta
IPSetFuzz-8    16.3µs ± 3%    14.1µs ± 1%  -12.99%  (p=0.008 n=5+5)

name         old alloc/op   new alloc/op   delta
IPSetFuzz-8    2.60kB ± 0%    1.95kB ± 0%  -25.24%  (p=0.008 n=5+5)

name         old allocs/op  new allocs/op  delta
IPSetFuzz-8      33.0 ± 0%      30.0 ± 0%   -9.09%  (p=0.008 n=5+5)

Signed-off-by: David Anderson <[email protected]>
danderson added a commit that referenced this issue Jan 29, 2021
@danderson
Add regression test for #125.
b265e07 
Signed-off-by: David Anderson <[email protected]>
danderson added a commit that referenced this issue Jan 29, 2021
@danderson
Add regression test for #125.
8429105 
Signed-off-by: David Anderson <[email protected]>
@danderson danderson mentioned this issue Jan 29, 2021
Merged
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@danderson