Garbage-collected Object-Pool Forests as in [JUNG13]. More...

Classes
union	gc_pointer_raw
	A portable and logical pointer with mark-for-death, ABA counter, and generation/segement bits. More...

struct	GcSegment< T >
	A segment in each generation. More...

struct	GcGeneration< T >
	A generation of objects. More...

struct	GcPoolEntry

struct	GcWakeupFunctor

struct	GcPoolForest< T >
	Garbage-collected Pool Forest. More...

Typedefs
typedef int32_t	gc_status
	Status bits in gc_pointer. More...

typedef uint32_t	gc_aba

typedef uint8_t	gc_generation

typedef uint8_t	gc_segment

typedef uint16_t	gc_offset

typedef uint64_t	gc_thread_id

Detailed Description

Garbage-collected Object-Pool Forests as in [JUNG13].

Overview

We maintain a forest of object pools with garbage-collector for each type of object. Such an object pool is quite effective to address the following issues in lock-free algorithms:

Garbage collection and Safe Memory Reclamation (SMR)
ABA Problem
Portability (c.f. "bit-stealing" pointer packing techniques, and double-word CAS algo)
Object allocation/deallocation costs

The usual drawback of this approach is that there are few one-size-fits-all GC design, so it has either unwanted overheads or some restrictions on users. However, this is our Roll-Your-Own Garbage Collector implementation optimized for long-running services with small number of object types, such as filesystems and databases.

Rather than general and more advanced techniques such as Hazard Pointers, this is much more simple, robust, efficient, and satisfactory for our usecase.

Hierarchy

The GC Forest consists of the following three levels.

Generation, which groups objects in similar age and is retired together.
Segement, which is the unit of bulk allocation/deallocation.
Object, which is the pooled object.

References

[JUNG13] "A scalable lock manager for multicores" Hyungsoo Jung, Hyuck Han, Alan D. Fekete, Gernot Heiser, Heon Y. Yeom. SIGMOD'13.

Dependency

All the classes are header-only template classes. Just include w_gc_pool_forest.h to use.

Typedef Documentation

§ gc_aba

typedef uint32_t gc_aba

ABA counter bits in gc_pointer.

§ gc_generation

typedef uint8_t gc_generation

Generation bits in gc_pointer (0 means an invalid generation = NULL).

§ gc_offset

typedef uint16_t gc_offset

Offset bits in gc_pointer (not in bytes but in objects).

§ gc_segment

typedef uint8_t gc_segment

Segment bits in gc_pointer.

§ gc_status

typedef int32_t gc_status

Status bits in gc_pointer.

This is logically not part of the pointer, but additional bits for lock-free algorithms.

The higest bit (sign bit) is mark-for-death. TRUE means the object is logically deactivated in lock-free data structures.
The remaining 31 bits are ABA-counter. Used to prevent ABA issues in lock-free data structures. 31 bits should be fairly safe.

§ gc_thread_id

typedef uint64_t gc_thread_id

Identifier of threads (which might be pthread_self() or something else).

Classes

Typedefs