google / google/gopacket

reassembly pages allocation/shrinking inefficient memory usage

Open
#732 3 comments 0 reactions 0 assignees View on GitHub
Dominant language
Go
Stars
6.8k
Forks
1.2k
PR merge metrics
No merged PRs in 30d

Description

Hello,
This issue is a continuation of PR #665 .
I will first describe the issue and a demonstration test, then list some possible solutions and benchmarks.

### Problem description and demo
To remind, reassembly package has a flaw in pages allocation/shrinking logic.
In particular, it doesn't take into account that when allocating a slice of pages they get allocated in a single memory block and in order to let GC free this memory, one has to clear all pointers(pages) related to that memory block.

While `tryShrink` function attempts to clear excessive page pointers from the `free` list, there is no guarantee that **all** pages of **same** memory block will be cleared at any time. At some point, `free` list can consist of pages which are all from different memory blocks, and thus resulting in inefficient memory usage. And while the size of a page is around `2k` bytes, each page will actually be responsible for `2k*c.pcSize` bytes. Where `c.pcSize` is initially set to 1024.

I have come up with a [test](https://github.com/jandos/gopacket/blob/b143162b7a602682bfff604a67d0d5630a9b521b/reassembly/tcpassembly_test.go#L1710) to demonstrate this issue. Here I mix up the free list with pages from different memory blocks (what happens in real traffic) and then call `tryShrink`. This function will shrink `free` list by about a half, therefore, after running GC, live/total allocated memory ratio should be around 50%.
Current `master` branch will show results of around 98%. `jandos/fix-reassm-pages-v1` branch shows results of around 50%, as expected.
I haven't added this test to fixed branches, because it is meant for demonstration only and it doesn't apply for versions 2 and 3 fix branches, because they don't have shrinking functionality.

`go test ./reassembly -run ^TestMemoryShrinkDemo$ -v`
gopacket master:
```
=== RUN TestMemoryShrinkDemo
2019/11/19 10:15:47 Live/total ratio: 98.82644%
```
version 1 fix:
```
=== RUN TestMemoryShrinkDemo
2019/11/19 10:14:11 Live/total ratio: 51.32094%
```

### Possible solutions
Now, to possible solutions that I have come up with.
First, we need to understand that, initial purpose of `pageCache` was to avoid memory allocations.
As I understand, this was done for performance reasons, because allocating a page each time when it is needed would be expensive. However, by keeping a list of pointers(`free` pages) we increase the load on GC marking phase. GC will have to scan all those pages every time.

Taking into account this knowledge, I have come up with 3 possible solutions:

- [Version 1](https://github.com/jandos/gopacket/tree/fix-reassm-pages-v1): Have a `free` list, but allocate pages one by one (separate memory blocks). Shrinking now will actually let GC collect unused pages. Problem with long GC marking phase still exists here.
- [Version 2](https://github.com/jandos/gopacket/tree/fix-reassm-pages-v2): Use `sync.Pool` instead of the `free` list. Since Go 1.13, large `sync.Pool` [doesn't increase stop-the-world times](https://golang.org/doc/go1.13#sync).
Actually, sync.Pool has exactly the same goal, as what we want to achieve with pageCache. However, as [documentation](https://golang.org/pkg/sync/#Pool) for sync.Pool states, it is not well suited for short-lived objects, which is what we have.
- [Version 3](https://github.com/jandos/gopacket/tree/fix-reassm-pages-v3): Have a fixed size `free` list, which gets reloaded when it runs out of pages.
Allocate pages in bulks, to gain some performance.
Do not put used pages back to the `free` list, to let GC collect corresponding memory blocks. Such memory blocks will stay live, at worst until we call one of the `Flush*` functions.
This solution helps us reduce the load on GC, because the `free` list will not grow, and we fix the initial problem of inefficient memory usage.

If any of the solutions look good, I can create another PR. If not, we should discuss on how to solve this issue, because otherwise gopacket/reassembly is not usable for long running applications with fluctuating traffic rate.

### Benchmarks
My setup:
Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz
go version go1.13.3 linux/amd64

Benchmarks show that **version 3 fix performs best**.

Compare gopacket master with **version 1** fix:
```
benchstat google.master.bench v1.bench
name old time/op new time/op delta
SingleStreamNo-8 506ns ± 0% 504ns ± 0% ~ (p=0.056 n=5+5)
SingleStreamSkips-8 1.29µs ±12% 1.88µs ±12% +46.12% (p=0.008 n=5+5)
SingleStreamLoss-8 1.29µs ±11% 1.73µs ± 4% +33.84% (p=0.008 n=5+5)
MultiStreamGrow-8 1.28µs ±12% 1.76µs ± 6% +36.84% (p=0.008 n=5+5)
MultiStreamConn-8 444ns ± 0% 440ns ± 0% -0.96% (p=0.029 n=4+4)

name old alloc/op new alloc/op delta
SingleStreamNo-8 81.0B ± 0% 81.0B ± 0% ~ (all equal)
SingleStreamSkips-8 2.69kB ±16% 3.56kB ± 2% +32.12% (p=0.016 n=5+4)
SingleStreamLoss-8 2.66kB ±12% 3.55kB ± 4% +33.54% (p=0.008 n=5+5)
MultiStreamGrow-8 2.69kB ±11% 3.55kB ± 6% +32.06% (p=0.008 n=5+5)
MultiStreamConn-8 81.0B ± 0% 81.0B ± 0% ~ (all equal)

name old allocs/op new allocs/op delta
SingleStreamNo-8 1.00 ± 0% 1.00 ± 0% ~ (all equal)
SingleStreamSkips-8 1.00 ± 0% 2.00 ± 0% +100.00% (p=0.008 n=5+5)
SingleStreamLoss-8 1.00 ± 0% 2.00 ± 0% +100.00% (p=0.008 n=5+5)
MultiStreamGrow-8 1.00 ± 0% 2.00 ± 0% +100.00% (p=0.008 n=5+5)
MultiStreamConn-8 1.00 ± 0% 1.00 ± 0% ~ (all equal)
```

Compare gopacket master with **version 2** fix:
```
benchstat google.master.bench v2.bench
name old time/op new time/op delta
SingleStreamNo-8 506ns ± 0% 503ns ± 1% -0.67% (p=0.016 n=5+5)
SingleStreamSkips-8 1.29µs ±12% 1.65µs ±34% +28.40% (p=0.016 n=5+5)
SingleStreamLoss-8 1.29µs ±11% 1.41µs ± 5% ~ (p=0.056 n=5+5)
MultiStreamGrow-8 1.28µs ±12% 1.45µs ± 2% +13.21% (p=0.016 n=5+5)
MultiStreamConn-8 444ns ± 0% 439ns ± 2% ~ (p=0.127 n=4+5)

name old alloc/op new alloc/op delta
SingleStreamNo-8 81.0B ± 0% 80.0B ± 0% -1.23% (p=0.008 n=5+5)
SingleStreamSkips-8 2.69kB ±16% 2.13kB ± 0% -20.96% (p=0.008 n=5+5)
SingleStreamLoss-8 2.66kB ±12% 2.13kB ± 0% -19.99% (p=0.008 n=5+5)
MultiStreamGrow-8 2.69kB ±11% 2.13kB ± 0% -20.80% (p=0.008 n=5+5)
MultiStreamConn-8 81.0B ± 0% 80.0B ± 0% -1.23% (p=0.008 n=5+5)

name old allocs/op new allocs/op delta
SingleStreamNo-8 1.00 ± 0% 1.00 ± 0% ~ (all equal)
SingleStreamSkips-8 1.00 ± 0% 2.00 ± 0% +100.00% (p=0.008 n=5+5)
SingleStreamLoss-8 1.00 ± 0% 2.00 ± 0% +100.00% (p=0.008 n=5+5)
MultiStreamGrow-8 1.00 ± 0% 2.00 ± 0% +100.00% (p=0.008 n=5+5)
MultiStreamConn-8 1.00 ± 0% 1.00 ± 0% ~ (all equal)
```

Compare gopacket master with **version 3** fix:
```
benchstat google.master.bench v3.bench
name old time/op new time/op delta
SingleStreamNo-8 506ns ± 0% 503ns ± 0% -0.63% (p=0.016 n=5+5)
SingleStreamSkips-8 1.29µs ±12% 1.22µs ±36% ~ (p=0.310 n=5+5)
SingleStreamLoss-8 1.29µs ±11% 1.04µs ± 1% -19.43% (p=0.008 n=5+5)
MultiStreamGrow-8 1.28µs ±12% 1.04µs ± 2% -19.05% (p=0.008 n=5+5)
MultiStreamConn-8 444ns ± 0% 441ns ± 2% ~ (p=0.127 n=4+5)

name old alloc/op new alloc/op delta
SingleStreamNo-8 81.0B ± 0% 81.0B ± 0% ~ (all equal)
SingleStreamSkips-8 2.69kB ±16% 2.08kB ± 0% -22.73% (p=0.008 n=5+5)
SingleStreamLoss-8 2.66kB ±12% 2.08kB ± 0% -21.78% (p=0.008 n=5+5)
MultiStreamGrow-8 2.69kB ±11% 2.08kB ± 0% -22.57% (p=0.008 n=5+5)
MultiStreamConn-8 81.0B ± 0% 81.0B ± 0% ~ (all equal)

name old allocs/op new allocs/op delta
SingleStreamNo-8 1.00 ± 0% 1.00 ± 0% ~ (all equal)
SingleStreamSkips-8 1.00 ± 0% 1.00 ± 0% ~ (all equal)
SingleStreamLoss-8 1.00 ± 0% 1.00 ± 0% ~ (all equal)
MultiStreamGrow-8 1.00 ± 0% 1.00 ± 0% ~ (all equal)
MultiStreamConn-8 1.00 ± 0% 1.00 ± 0% ~ (all equal)
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.