SIGSERV at cuckoo_filter_lookup

[peko]

I experimented a bit with your implementation of the filter, and faced with the following error. Program received signal SIGSEGV, Segmentation fault. 0x0000000000401075 in cuckoo_filter_lookup (filter=0x6039e0, result=0x7fffffffe990, key=0x603010, key_length_in_bytes=22) at cuckoo_filter.c: 217

Pull request with test

Conditions

I create about 1000 small filters to store 100-500 values in each (values 22 bytes long). When I try to call cuckoo_filter_add or cuckoo_filter_check, I'm occasionally get an SIGSERV. The error does not appear immediately, but for some filters. When I test with shorter values - error appears less frequently.

Compilation trivial gcc -O0 -g3 -Wall ...

Tested with clang version 3.7.1 (tags/RELEASE_371/final) and gcc (GCC) 5.3.0

Code

214│   for (size_t ii = 0; ii < filter->nests_per_bucket; ++ii) {
215│     cuckoo_nest_t *n1 =
216│       &filter->bucket[((h1 - 1) * filter->nests_per_bucket) + ii];
217├>    if (fingerprint == n1->fingerprint) {
218│       result->was_found = true;
219│       break;
220│     }

Backtrace

#0  0x0000000000401075 in cuckoo_filter_lookup (
filter=0x6039e0, 
result=0x7fffffffe990, 
key=0x603010, 
key_length_in_bytes=22) 
at ./cuckoo/libcuckoofilter/src/cuckoo_filter.c:217

#1  0x000000000040124f in cuckoo_filter_contains (
filter=0x6039e0, 
key=0x603010, 
key_length_in_bytes=22) 
at ./cuckoo/libcuckoofilter/src/cuckoo_filter.c:305
...

Stack

(gdb) p *result
$2 = {was_found = false, item = {fingerprint = 0, h1 = 0, h2 = 0, padding = 1660944384}}

(gdb) p *filter
$3 = {bucket_count = 16, nests_per_bucket = 4, mask = 65535, max_kick_attempts = 100, seed = 1456275313, padding = 0, victim = {fingerprint = 0, h1 = 0, h2 = 0, padding = 0}, last_victim = 0x0, bucket = {{fingerprint = 0}}}

(gdb) info locals
n1 = 0x200603a08
n2 = 0x0
ii = 0
fingerprint = 0
h1 = 0
h2 = 9

[jonahharris]

While I couldn't re-create the issue, I do think there may have been an off-by-one there causing wraparound of the unsigned int. Can you pull master and retest?

[peko]

Retested issue on two different hardwares / distros:

• Linux version 4.4.1-2-ARCH (gcc version 5.3.0 (GCC) )
• Linux version 2.6.32-042stab106.4 (gcc version 4.4.6 20120305 (Red Hat 4.4.6-4) )

cuckootest2.c still occasionally falls on both platforms, but subjectively less often.

This time seg fault at add_fingerpirnt_to_bucket

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400767 in add_fingerprint_to_bucket (filter=0x602010, fp=24, h=0) at src/cuckoo_filter.c:68
(gdb) info locals
nest = 0x200602038
ii = 0
(gdb) bt
#0  0x0000000000400767 in add_fingerprint_to_bucket (filter=0x602010, fp=24, h=0) at src/cuckoo_filter.c:68
#1  0x0000000000400887 in cuckoo_filter_move (filter=0x602010, fingerprint=24, h1=0, depth=0) at src/cuckoo_filter.c:112
#2  0x0000000000400d4c in cuckoo_filter_add (filter=0x602010, key=0x401314, key_length_in_bytes=20) at src/cuckoo_filter.c:260
#3  0x0000000000401199 in main (argc=1, argv=0x7fffffffe598) at tests/cuckootest2.c:29

[solardiz]

I think this can be closed now that #3 is merged, as it included testing of the finally corrected code with ASan.