git: kernel - Initial commit for Existential structural tracking

[Michael Neumann]

On Tue, Oct 13, 2020 at 09:54:21AM -0900, Matthew Dillon wrote:
> Interesting paper but kinda all over the place.   He mentions cache-line
> bouncing as an issue but the paper is from 2004... so kudos for recognizing

Cache-line bouncing: Academia was playing with SMP long before mere mortal
could buy these machines :). I can't remeber it being a topic in system
architecture lessions in 2003, but definitively in 2009.

> that it was an issue way back then!  However, in 2004 it was a relatively
> minor issue and so in the paper the author still relies heavily on
> compare-and-swap style atomic ops.  These can be used in lockless
> implementations but they still cause massive cache-line bouncing
> between cpu cores.

How can you avoid compare-and-swap for the data structure itself?

> In 2020, lock contention has been largely dealt with and cache line
> bouncing is the single biggest problem we face.
> 
> I read the section on epoch-based reclamation more carefully, and it is a
> similar idea to the Existential type-safe mechanism.  He describes it in
> the context of garbage collection while in modern terms we would describe
> it in terms of type-safeness and object repurposing/reuse.  That is,
> type-safe access to a data structure that might be undergoing destruction
> or repurposing.   The core idea is the same though... all cpu cores agree
> on a deterministic time stamp (not really a 'time' stamp but more an
> incrementing counter).  This agreement allows certain assumptions to be
> made with regards to accessing the related structures safely.

FYI, I came epoch-based reclamation via this [1] blog post, which mentioned
that paper. It is also used in Rust's crossbeam [2] library, that contains
tools for concurrent programming.

> A more important way to think about this is not just for garbage
> collection, but also when this mechanism is integrated into a lockless
> cache mechanism such as a hash table.  The combination can result in a data
> structure containing objects which can be reliably accessed with ZERO locks
> and (almost) ZERO cache line bounces.

The blog post mentioned above describes the problem pretty well in terms of a
lockless stack implemented using a single-linked list. My understaning is that
it would be similar for a hash table: Every bucket is the head of a
single-linked list. Insertion is simple by using a compare-and-swap on the head
element. Deletion of an entry is more complex though, probably simplest is by
using COW for the chain. Or do you simply use linear probing?

That Existential structural tracking method, is that your own invention or
terminology? I can't find any papers about this topic :)

Regards,

  Michael

[1]: https://aturon.github.io/blog/2015/08/27/epoch/
[2]: https://github.com/crossbeam-rs/crossbeam