This PR introduces an initial version of an epoch garbage collector [1], which is a corner stone for the new iteration of the internal KeyValue database.

The epoch garbage collector works on a very simple principle:

data can be staged for deletion by any thread
any thread wanting to use the garbage collector has to register
when a pointer is staged is associated with an object type and with the epoch of the staging
for each object type a destructor is registered
threads have to advance their own epoch (and will use a queue of operations to track the operations, will be introduced in a future PR)
threads can stage pointers only in their own queue
an ad-hoc thread for the gc is required, when the collection runs the lowest epoch is selected among the threads and all the staged pointers that have an older epoch are batched together and submitted for collection.

There are currently 4 different object types but this might change down the line.

The epoch gc uses a double linked list for the threads, that requires a spinlock when is used, and uses a double linked list of ring bounded spsc to stage the pointers to clean up, the list is expanded only when the current ring is full of staged pointers that can't be deleted.

Pointers are traced only when they are submitted for deletion, not before, to avoid overloading the system for no reason.

[1] https://en.wikipedia.org/wiki/Garbage_collection_(computer_science)

Codecov Report

Base: 81.89% // Head: 82.20% // Increases project coverage by +0.31% :tada:

Coverage data is based on head (9768af6) compared to base (5f38ef2). Patch coverage: 96.06% of modified lines in pull request are covered.

Additional details and impacted files

```diff @@ Coverage Diff @@ ## main #255 +/- ## ========================================== + Coverage 81.89% 82.20% +0.31% ========================================== Files 153 155 +2 Lines 9421 9624 +203 ========================================== + Hits 7715 7911 +196 - Misses 1706 1713 +7 ``` | Flag | Coverage Δ | | |---|---|---| | unittests | `82.20% <96.06%> (+0.31%)` | :arrow_up: | Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Daniele+Salvatore+Albano#carryforward-flags-in-the-pull-request-comment) to find out more. | [Impacted Files](https://codecov.io/gh/danielealbano/cachegrand/pull/255?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Daniele+Salvatore+Albano) | Coverage Δ | | |---|---|---| | [src/epoch\_gc.c](https://codecov.io/gh/danielealbano/cachegrand/pull/255/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Daniele+Salvatore+Albano#diff-c3JjL2Vwb2NoX2djLmM=) | `96.00% <96.00%> (ø)` | | | [src/intrinsics.h](https://codecov.io/gh/danielealbano/cachegrand/pull/255/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Daniele+Salvatore+Albano#diff-c3JjL2ludHJpbnNpY3MuaA==) | `100.00% <100.00%> (ø)` | | | [...a\_structures/ring\_bounded\_spsc/ring\_bounded\_spsc.c](https://codecov.io/gh/danielealbano/cachegrand/pull/255/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Daniele+Salvatore+Albano#diff-c3JjL2RhdGFfc3RydWN0dXJlcy9yaW5nX2JvdW5kZWRfc3BzYy9yaW5nX2JvdW5kZWRfc3BzYy5j) | `93.75% <0.00%> (+2.08%)` | :arrow_up: | Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Daniele+Salvatore+Albano). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Daniele+Salvatore+Albano)

:umbrella: View full report at Codecov.
:loudspeaker: Do you have feedback about the report comment? Let us know in this issue.

danielealbano / cachegrand

Implement epoch gc #255

Codecov Report