BufferPool

This crate provides a Write trait used to replace std::io::Write in a non_std environment a Buffer trait and two implementations of Buffer: BufferFromSystemMemory and BufferPool.

Intro

BufferPool is useful whenever we need to work with buffers sequentially (fill a buffer, get the filled buffer, fill a new buffer, get the filled buffer, and so on).

To fill a buffer BufferPool returns an &mut [u8] with the requested len (the filling part). When the buffer is filled and the owner needs to be changed, BufferPool returns a Slice that implements Send and AsMut<u8> (the get part).

BufferPool pre-allocates a user-defined capacity in the heap and use it to allocate the buffers, when a Slice is dropped BufferPool acknowledge it and reuse the freed space in the pre-allocated memory.

Implementation

The crate is [no_std] and lock-free, so, to synchronize the state of the pre-allocated memory (taken or free) between different contexts an AtomicU8 is used. Each bit of the u8 represent a memory slot, if the bit is 0 the memory slot is free if is 1 is taken. Whenever BufferPool creates a Slice a bit is set to 1 and whenever a Slice is dropped a bit is set to 0.

Use case

BufferPool has been developed to be used in proxies with thousand of connection, each connection must parse a particular data format via a Decoder each decoder use 1 or 2 Buffer for each received message. With BufferPool each connection can be instantiated with its own BufferPool and reuse the space freed by old messages for new ones.

Unsafe

There are 5 unsafes: buffer_pool/mod.rs 550 slice.rs 8 slice.rs 27

Write

Waiting for Write in core a compatible trait is used so that it can be replaced.

Buffer

The Buffer trait has been written to work with codec_sv2::Decoder.

codec_sv2::Decoder works by:

1. fill a buffer of the size of the header of the protocol that is decoding
2. parse the filled bytes and compute the message length
3. fill a buffer of the size of the message
4. use the header and the message to construct a frame_sv2::Frame

To fill the buffer Decoder must pass a reference of the buffer to a filler. In order to construct a Frame the Decoder must pass the ownership of the buffer to Frame.

get_writable(&mut self, len: usize) -> &mut [u8]

Return a mutable reference to the buffer, starting at buffer length and ending at buffer length + len. and set buffer len at previous len + len.

get_data_owned(&mut self) -> Slice {

It returns Slice: something that implements AsMut[u8] and Send, and sets the buffer len to 0.

BufferFromSystemMemory

Is the simplest implementation of a Buffer: each time that a new buffer is needed it create a new Vec<u8>.

get_writable(..) returns mutable references to the inner vector.

get_data_owned(..) returns the inner vector.

BufferPool

Usually BufferFromSystemMemory should be enough, but sometimes it is better to use something faster.

For each Sv2 connection, there is a Decoder and for each decoder, there are 1 or 2 buffers.

Proxies and pools with thousands of connections should use Decoder<BufferPool> rather than Decoder<BufferFromSystemMemory>

BufferPool when created preallocate a user-defined capacity of bytes in the heap using a Vec<u8>, then when get_data_owned(..) is called it create a Slice that contains a view into the preallocated memory. BufferPool guarantees that slices never overlap and the uniqueness of the Slice ownership.

Slice implements Drop so that the view into the preallocated memory can be reused.

Fragmentation overflow and optimization

BufferPool can allocate a maximum of 8 Slices (cause it uses an AtomicU8 to keep track of the used and freed slots) and at maximum capacity bytes. Whenever all the 8 slots are tacked or there is no more space on the preallocated memory BufferPool failover to a BufferFromSystemMemory.

Usually, a message is decoded then a response is sent then a new message is decoded, etc. So BufferPool is optimized for use all the slots then check if the first slot has been dropped If so use it, then check if the second slot has been dropped, and so on. BufferPool is also optimized to drop all the slices. BufferPool is also optimized to drop the last slice.

Below a graphical representation of the most optimized cases:

A number [0f] means that the slot is taken, the minus symbol (-) means the slot is free
There are 8 slot

CASE 1
--------  BACK MODE
1-------  BACK MODE
12------  BACK MODE
123-----  BACK MODE
1234----  BACK MODE
12345---  BACK MODE
123456--  BACK MODE
1234567-  BACK MODE
12345678  BACK MODE
12345698  BACK MODE
1234569a  BACK MODE
123456ba  BACK MODE
123456ca  BACK MODE
..... and so on

CASE 2
--------  BACK MODE
1-------  BACK MODE
12------  BACK MODE
123-----  BACK MODE
1234----  BACK MODE
12345---  BACK MODE
123456--  BACK MODE
1234567-  BACK MODE
12345678  BACK MODE
--------  RESET
9a------  BACK MODE
9ab-----  BACK MODE

CASE 3
-------- BACK MODE
1------- BACK MODE
12------ BACK MODE
123----- BACK MODE
1234---- BACK MODE
12345--- BACK MODE
123456-- BACK MODE
1234567- BACK MODE
12345678 BACK MODE
12345678 BACK MODE
--345678 SWITCH TO FRONT MODE
92345678 FRONT MODE
9a345678 FRONT MODE
9a3456-- SWITCH TO BACK MODE
9a3456b- BACK MODE
9a3456bc BACK MODE

BufferPool can operate in three modalities:

1. Back: it allocates in the back of the inner vector
2. Front: it allocates in the front of the inner vector
3. Alloc: failover to BufferFromSystemMemory

BufferPool can be fragmented only between front and back and between back and end.

Performance

To run the benchmarks cargo bench --features criterion.

To have an idea of the performance gains, BufferPool is benchmarked against BufferFromSystemMemory and two control structures PPool and MaxEfficeincy.

PPool is a buffer pool implemented with a hashmap and MaxEfficeincy is a Buffer implemented in the fastest possible way so that the benches do not panic and the compiler does not complain. Btw they are both completely broken, useful only as references for the benchmarks.

The benchmarks are:

Single thread

for 0..1000:
  add random bytes to the buffer
  get the buffer
  add random bytes to the buffer
  get the buffer
  drop the 2 buffer

Multi threads (this is the most similar to the actual use case IMHO)

for 0..1000:
  add random bytes to the buffer
  get the buffer
  send the buffer to another thread   -> wait 1 ms and then drop it
  add random bytes to the buffer
  get the buffer
  send the buffer to another thread   -> wait 1 ms and then drop it

Multi threads 2

for 0..1000:
  add random bytes to the buffer
  get the buffer
  send the buffer to another thread   -> wait 1 ms and then drop it
  add random bytes to the buffer
  get the buffer
  send the buffer to another thread   -> wait 1 ms and then drop it
  wait for the 2 buffer to be dropped

Test

Some failing cases from fuzz.

From the benchmark in BENCHES.md executed for 2000 samples:

* single thread with  `BufferPool`: ---------------------------------- 7.5006 ms
* single thread with  `BufferFromSystemMemory`: ---------------------- 10.274 ms
* single thread with  `PPoll`: --------------------------------------- 32.593 ms
* single thread with  `MaxEfficeincy`: ------------------------------- 1.2618 ms
* multi-thread with   `BufferPool`: ---------------------------------- 34.660 ms
* multi-thread with   `BufferFromSystemMemory`: ---------------------- 142.23 ms
* multi-thread with   `PPoll`: --------------------------------------- 49.790 ms
* multi-thread with   `MaxEfficeincy`: ------------------------------- 18.201 ms
* multi-thread 2 with `BufferPool`: ---------------------------------- 80.869 ms
* multi-thread 2 with `BufferFromSystemMemory`: ---------------------- 192.24 ms
* multi-thread 2 with `PPoll`: --------------------------------------- 101.75 ms
* multi-thread 2 with `MaxEfficeincy`: ------------------------------- 66.972 ms

From the above numbers, it results that BufferPool always outperform the hashmap buffer pool and the solution without a pool:

Single thread

If the buffer is not sent to another context BufferPool is 1.4 times faster than no pool and 4.3 time faster than the hashmap pool and 5.7 times slower than max efficiency.

Multi threads

If the buffer is sent to other contexts BufferPool is 4 times faster than no pool, 0.6 times faster than the hashmap pool and 1.8 times slower than max efficiency.

Fuzzy tests

Install cargo fuzz with cargo install cargo-fuzz

Then do cd ./fuzz

Run them with cargo fuzz run slower -- -rss_limit_mb=5000000000 and cargo fuzz run faster -- -rss_limit_mb=5000000000

BufferPool is fuzzy tested with cargo fuzzy. The test checks if slices created by BufferPool still contain the same bytes contained at creation time after a random amount of time and after been sent to other threads. There are 2 fuzzy test, the first (faster) it map a smaller input space to test the most likely inputs, the second (slower) it have a bigger input space to pick "all" the corner case. The slower also forces the buffer to be sent to different cores. I run both for several hours without crashes.

The test must be run with -rss_limit_mb=5000000000 cause they check BufferPool with capacities from 0 to 2^32.

(1) TODO check if is always true