My website 😸

https://hbina.github.io/

applejack's People

Contributors

Stargazers

Watchers

applejack's Issues

Using minivec causes the fuzzer to SEGV.

Checkout branch feat/using-fuzzers-and-minivec.
Perform fuzzing with cargo +nightly fuzz run fuzz_target_1.
See that it SEGV on the simplest input.
Using standard Vec does not cause this problem.
I suspect the implementation of drain is faulty.

   Compiling applejack-fuzz v0.0.0 (/home/hbina/git/applejack/fuzz)
    Finished release [optimized] target(s) in 1.56s
    Finished release [optimized] target(s) in 0.00s
     Running `fuzz/target/x86_64-unknown-linux-gnu/release/fuzz_target_1 -artifact_prefix=/home/hbina/git/applejack/fuzz/artifacts/fuzz_target_1/ /home/hbina/git/applejack/fuzz/corpus/fuzz_target_1`
INFO: Running with entropic power schedule (0xFF, 100).
INFO: Seed: 1066036984
INFO: Loaded 1 modules   (1418 inline 8-bit counters): 1418 [0x55f184dbf712, 0x55f184dbfc9c), 
INFO: Loaded 1 PC tables (1418 PCs): 1418 [0x55f184dbfca0,0x55f184dc5540), 
INFO:     1623 files found in /home/hbina/git/applejack/fuzz/corpus/fuzz_target_1
INFO: -max_len is not provided; libFuzzer will not generate inputs larger than 4096 bytes
INFO: seed corpus: files: 1623 min: 1b max: 4040b total: 471343b rss: 31Mb
AddressSanitizer:DEADLYSIGNAL
=================================================================
==135950==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000000 (pc 0x55f184c0958b bp 0x7ffd424b8570 sp 0x7ffd424b8000 T0)
==135950==The signal is caused by a WRITE memory access.
==135950==Hint: address points to the zero page.
    #0 0x55f184c0958b  (/home/hbina/git/applejack/fuzz/target/x86_64-unknown-linux-gnu/release/fuzz_target_1+0xec58b)
    #1 0x55f184c09981  (/home/hbina/git/applejack/fuzz/target/x86_64-unknown-linux-gnu/release/fuzz_target_1+0xec981)
    #2 0x55f184c0b922  (/home/hbina/git/applejack/fuzz/target/x86_64-unknown-linux-gnu/release/fuzz_target_1+0xee922)
    #3 0x55f184c1e260  (/home/hbina/git/applejack/fuzz/target/x86_64-unknown-linux-gnu/release/fuzz_target_1+0x101260)
    #4 0x55f184c1debf  (/home/hbina/git/applejack/fuzz/target/x86_64-unknown-linux-gnu/release/fuzz_target_1+0x100ebf)
    #5 0x55f184c28a28  (/home/hbina/git/applejack/fuzz/target/x86_64-unknown-linux-gnu/release/fuzz_target_1+0x10ba28)
    #6 0x55f184c2db90  (/home/hbina/git/applejack/fuzz/target/x86_64-unknown-linux-gnu/release/fuzz_target_1+0x110b90)
    #7 0x55f184c30446  (/home/hbina/git/applejack/fuzz/target/x86_64-unknown-linux-gnu/release/fuzz_target_1+0x113446)
    #8 0x55f184c308b7  (/home/hbina/git/applejack/fuzz/target/x86_64-unknown-linux-gnu/release/fuzz_target_1+0x1138b7)
    #9 0x55f184c1a557  (/home/hbina/git/applejack/fuzz/target/x86_64-unknown-linux-gnu/release/fuzz_target_1+0xfd557)
    #10 0x55f184b488d6  (/home/hbina/git/applejack/fuzz/target/x86_64-unknown-linux-gnu/release/fuzz_target_1+0x2b8d6)
    #11 0x7f208e600cb1  (/lib/x86_64-linux-gnu/libc.so.6+0x28cb1)
    #12 0x55f184b48a7d  (/home/hbina/git/applejack/fuzz/target/x86_64-unknown-linux-gnu/release/fuzz_target_1+0x2ba7d)

AddressSanitizer can not provide additional info.
SUMMARY: AddressSanitizer: SEGV (/home/hbina/git/applejack/fuzz/target/x86_64-unknown-linux-gnu/release/fuzz_target_1+0xec58b) 
==135950==ABORTING
MS: 0 ; base unit: 0000000000000000000000000000000000000000
0xe6,0xa4,
\xe6\xa4
artifact_prefix='/home/hbina/git/applejack/fuzz/artifacts/fuzz_target_1/'; Test unit written to /home/hbina/git/applejack/fuzz/artifacts/fuzz_target_1/crash-51943bd7f498abd3bde33971a15101f8445fe8d1
Base64: 5qQ=

────────────────────────────────────────────────────────────────────────────────

Failing input:

	fuzz/artifacts/fuzz_target_1/crash-51943bd7f498abd3bde33971a15101f8445fe8d1

Output of `std::fmt::Debug`:

	[230, 164]

Reproduce with:

	cargo fuzz run fuzz_target_1 fuzz/artifacts/fuzz_target_1/crash-51943bd7f498abd3bde33971a15101f8445fe8d1

Minimize test case with:

	cargo fuzz tmin fuzz_target_1 fuzz/artifacts/fuzz_target_1/crash-51943bd7f498abd3bde33971a15101f8445fe8d1

────────────────────────────────────────────────────────────────────────────────

Error: Fuzz target exited with exit code: 1

Main Features of Redis' Radix Tree

The following is taken directly taken from README of rax. We should try to achieve all this.

Memory conscious:

Packed nodes representation.
Able to avoid storing a NULL pointer inside the node if the key is set to NULL (there is an isnull bit in the node header).
Lack of parent node reference. A stack is used instead when needed.

Fast lookups:

Edges are stored as arrays of bytes directly in the parent node, no need to access non useful children while trying to find a match. This translates into less cache misses compared to other implementations.
Cache line friendly scanning of the correct child by storing edges as two separated arrays: an array of edge chars and one of edge pointers.

Complete implementation:

Deletion with nodes re-compression as needed.
Iterators (including a way to use iterators while the tree is modified).
Random walk iteration.
Ability to report and resist out of memory: if malloc() returns NULL the API can report an out of memory error and always leave the tree in a consistent state.

Readable and fixable implementation:

All complex parts are commented with algorithms details.
Debugging messages can be enabled to understand what the implementation is doing when calling a given function.
Ability to print the radix tree nodes representation as ASCII art.

Portable implemntation:

Never does unaligned accesses to memory.
Written in ANSI C99, no extensions used.
Extensive code and possible states test coverage using fuzz testing.
Testing relies a lot on fuzzing in order to explore non trivial states.
Implementation of the dictionary and iterator compared with behavior-equivalent implementations of simple hash tables and sorted arrays, generating random data and checking if the two implementations results match.
Out of memory condition tests. The implementation is fuzzed with a special allocator returning NULL at random. The resulting radix tree is tested for consistency. Redis, the primary target of this implementation, does not use this feature, but the ability to handle OOM may make this implementation useful where the ability to survive OOMs is needed.