Possible bug in `ck_rhs_t` on OOM.

[michael-grunder]

I encountered what might be an edge case in ck_rhs_t causing inconsistency in the map.

The issue has nothing to do with concurrency so if I'm doing something obviously wrong it should be easy to see.

What I'm doing is creating a CK_RHS_MODE_OBJECT map with a capacity of 8 (which appears to be what ck_rhs_t actually picks). I allow the allocation of the initial map to succeed, but then fail every additional call to our allocator, when ck_rhs_t attempts to grow.

ck_rhs_t stores 8 elements, failing when we try to store the ninth. I then iterate over the elements in the map deleting them. This appears to lead ck_rhs_t to an inconsistent state, where it fails to find the final element.

I've created a repo that demonstrates the behavior

fail_to_allocate: yes, read_mostly: no, reverse: no
--- Adding 9 elements ---
[0] Attmpting to add '0'@0x557b44c2c010
[1] Attmpting to add '1'@0x557b44c2c012
[2] Attmpting to add '2'@0x557b44c2c014
[3] Attmpting to add '3'@0x557b44c2c016
[4] Attmpting to add '4'@0x557b44c2c018
    Failing to allocate 4519 bytes
[5] Attmpting to add '5'@0x557b44c2c01a
    Failing to allocate 4519 bytes
[6] Attmpting to add '6'@0x557b44c2c01c
    Failing to allocate 4519 bytes
[7] Attmpting to add '7'@0x557b44c2c01e
    Failing to allocate 4519 bytes
[8] Attmpting to add '8'@0x557b44c2c020
    Failing to allocate 4519 bytes
    Failed to insert: '8'@0x557b44c2c020
--- Iterating over ck_rhs_t with 8 elements ---
[0] '0'@0x557b44c2c010
[1] '1'@0x557b44c2c012
[2] '2'@0x557b44c2c014
[3] '3'@0x557b44c2c016
[4] '4'@0x557b44c2c018
[5] '5'@0x557b44c2c01a
[6] '6'@0x557b44c2c01c
[7] '7'@0x557b44c2c01e
--- Removing 8 elements ---
[0] Attempting to remove '0'@0x557b44c2c010
    OK '0'@0x557b44c2c010 == '0'@0x557b44c2c010
[1] Attempting to remove '1'@0x557b44c2c012
    OK '1'@0x557b44c2c012 == '1'@0x557b44c2c012
[2] Attempting to remove '2'@0x557b44c2c014
    OK '2'@0x557b44c2c014 == '2'@0x557b44c2c014
[3] Attempting to remove '3'@0x557b44c2c016
    OK '3'@0x557b44c2c016 == '3'@0x557b44c2c016
[4] Attempting to remove '4'@0x557b44c2c018
    OK '4'@0x557b44c2c018 == '4'@0x557b44c2c018
[5] Attempting to remove '5'@0x557b44c2c01a
    OK '5'@0x557b44c2c01a == '5'@0x557b44c2c01a
[6] Attempting to remove '6'@0x557b44c2c01c
    OK '6'@0x557b44c2c01c == '6'@0x557b44c2c01c
[7] Attempting to remove '7'@0x557b44c2c01e
    ERR Failed to remove '7'@0x557b44c2c01e (not found)

The repo also includes a GDB pretty printer to dump the internal state of the ck_rhs_t.

(gdb) source rhs-state-printer.py
(gdb) print_rhs_t hs

One thing that did catch my eye is that on the failed ck_rhs_set the internal state gets modified where every in_rh -> true becomes in_rh -> false https://github.com/concurrencykit/ck/blob/471558111ff7c376450724945665cbf5033534a5/src/ck_rhs.c#L939-L944

Before:

[0] probes: 2, wanted: 0, probe_bound: 5 '\005', in_rh: true, entry: 0
[1] probes: 1, wanted: 0, probe_bound: 2 '\002', in_rh: true, entry: 1
[2] probes: 2, wanted: 0, probe_bound: 2 '\002', in_rh: true, entry: 2
[3] probes: 2, wanted: 0, probe_bound: 2 '\002', in_rh: true, entry: 3
[4] probes: 2, wanted: 0, probe_bound: 2 '\002', in_rh: true, entry: 4
[5] probes: 2, wanted: 0, probe_bound: 2 '\002', in_rh: true, entry: 5
[6] probes: 2, wanted: 0, probe_bound: 1 '\001', in_rh: true, entry: 6
[7] probes: 5, wanted: 0, probe_bound: 2 '\002', in_rh: true, entry: 7

And after:

[0] probes: 2, wanted: 0, probe_bound: 5 '\005', in_rh: false, entry: 0
[1] probes: 1, wanted: 0, probe_bound: 2 '\002', in_rh: false, entry: 1
[2] probes: 2, wanted: 0, probe_bound: 2 '\002', in_rh: false, entry: 2
[3] probes: 2, wanted: 0, probe_bound: 2 '\002', in_rh: false, entry: 3
[4] probes: 2, wanted: 0, probe_bound: 2 '\002', in_rh: false, entry: 4
[5] probes: 2, wanted: 0, probe_bound: 2 '\002', in_rh: false, entry: 5
[6] probes: 2, wanted: 0, probe_bound: 1 '\001', in_rh: false, entry: 6
[7] probes: 5, wanted: 0, probe_bound: 2 '\002', in_rh: false, entry: 7

I didn't see anything in the documentation about a failure in ck_rhs_set meaning the map can't be further used but perhaps I missed it. Also, using CK_RHS_MODE_READ_MOSTLY fixes the problem as it probes more deeply.

You can run the demo program with different options to demonstrate slightly different behavior.

USAGE:
    ./debug-dynamic [FLAGS]

FLAGS:
    --nofail         don't fail to allocate
    --read-mostly    set read mostly mode
    --silent         don't print status messages
    --reverse        Delete from back to front
    --djb3           Use djb3 instead of the silly one

The default "hash" function effectively hashes the keys to themselves as an integer just to make it easier to map them back and forth. You can pass --djb3 to use a real hash function.

I don't think I'm missing anything obvious, but it's certainly possible :smile:

Thanks!

[cognet]

Hi @michael-grunder,

Thanks for the detailed issue, and the reproducer! I believe I understand what was going on, for each entry that was modified, the function would change the probes number, but failed to restore it if we failed to allocate memory. It should be fixed with 872522abff84afceb5af3835bd8c3875de690674 Can you confirm it is fixed for you ?

Thanks!

[michael-grunder]

Will do when I'm back at my desk. Thanks for such a quick reply!

[michael-grunder]

https://github.com/concurrencykit/ck/commit/872522abff84afceb5af3835bd8c3875de690674 fixes the issue for me locally. Thank you so much!

[michael-grunder]

Hi everyone :wave:,

I think I found another OOM edge case.

Reproducer here.

fail_to_allocate: yes, read_mostly: no, limit: 0
--- Adding 9 elements ---
[0] Attmpting to add 0x1
[1] Attmpting to add 0x2
[2] Attmpting to add 0x3
[3] Attmpting to add 0x4
[4] Attmpting to add 0x5
    Failing to allocate 4519 bytes
[5] Attmpting to add 0x6
    Failing to allocate 4519 bytes
[6] Attmpting to add 0x9
    Failing to allocate 4519 bytes
[7] Attmpting to add 0xa
    Failing to allocate 4519 bytes
[8] Attmpting to add 0xb
    Failing to allocate 4519 bytes
    Failed to insert: 0xb
--- Removing 8 elements ---
[0] Attempting to remove 0xa
    OK 0xa == 0xa
[1] Attempting to remove 0x3
    ERR Failed to remove 0x3 (not found)

This time I'm using CK_RHS_MODE_DIRECT just to make sure the issue didn't have to do with the map using the high bits for optimizations.

One interesting thing is that the ck_rhs_set operation (that fails because there are no more free buckets), increases a bucket's probes to 15 which seems wrong, although I only partially understand the probing logic.

Before the final ck_rhs_set that fails:

map buckets:
  0) probes: 3, wanted: 2, probe_bound: 0, in_rh: T, entry: 0xa
  1) probes: 3, wanted: 3, probe_bound: 3, in_rh: F, entry: 0x3
  2) probes: 2, wanted: 3, probe_bound: 5, in_rh: T, entry: 0x9
  3) probes: 3, wanted: 3, probe_bound: 3, in_rh: F, entry: 0x1
  4) probes: 1, wanted: 0, probe_bound: 1, in_rh: F, entry: 0x4
  5) probes: 5, wanted: 1, probe_bound: 2, in_rh: F, entry: 0x2
  6) probes: 2, wanted: 1, probe_bound: 2, in_rh: F, entry: 0x5
  7) probes: 2, wanted: 0, probe_bound: 0, in_rh: F, entry: 0x6

After the failed insertion:

map buckets:
  0) probes: 3, wanted: 2, probe_bound: 0, in_rh: T, entry: 0xa
  1) probes: 15, wanted: 3, probe_bound: 6, in_rh: F, entry: 0x3
  2) probes: 2, wanted: 3, probe_bound: 15, in_rh: T, entry: 0x9
  3) probes: 5, wanted: 3, probe_bound: 5, in_rh: F, entry: 0x1
  4) probes: 3, wanted: 0, probe_bound: 5, in_rh: F, entry: 0x4
  5) probes: 3, wanted: 1, probe_bound: 3, in_rh: F, entry: 0x2
  6) probes: 2, wanted: 1, probe_bound: 3, in_rh: F, entry: 0x5
  7) probes: 1, wanted: 0, probe_bound: 0, in_rh: F, entry: 0x6

After the first ck_rhs_remove and its backward shift delete, we end up with this:

  0) probes: 0, wanted: 0, probe_bound: 0, in_rh: T, entry: NULL
  1) probes: 1, wanted: 2, probe_bound: 6, in_rh: F, entry: 0x9
  2) probes: 1, wanted: 1, probe_bound: 2, in_rh: T, entry: 0x3
  3) probes: 5, wanted: 1, probe_bound: 5, in_rh: F, entry: 0x1
  4) probes: 3, wanted: 0, probe_bound: 5, in_rh: F, entry: 0x4
  5) probes: 3, wanted: 1, probe_bound: 3, in_rh: F, entry: 0x2
  6) probes: 2, wanted: 1, probe_bound: 3, in_rh: F, entry: 0x5
  7) probes: 1, wanted: 0, probe_bound: 0, in_rh: F, entry: 0x6

The second deletion 0x3 maps to bucket 3:

  3) probes: 5, wanted: 1, probe_bound: 5, in_rh: F, entry: 0x1

The probe depth is too low and it is not found.

If in gdb I manually reset the probes, wanted, and probe_bound to the values before the failed ninth insertion, the program completes without issues and everything is found.

Let me know if you have any questions or if I am confused about something.

Cheers

[cognet]

Hey @michael-grunder !

Thanks for reporting this one too! And hopefully there won't be much more to come. I believe I understood what was happening, and fixed it with commit 53d8e34bbb9a0c569ce7daa091d89e729864eb9e, but honestly this is code I wrote quite a long time ago, and getting the logic is hard for me too, so please let me know if it gets you more trouble.

[michael-grunder]

I can confirm that 53d8e34 fixes the second edge case for me.

Thanks again for taking a look so quickly!