cb - GitLite

KO | EN

gitlite — search

#python #java #python3 #arduino #golang #machine-learning #rust #html #flask #javascript #seismology #nodejs

cb

★ 17 Open GitHub ↗

Continuous Buffer

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

## What is CB?

CB is an experiment toward a language runtime which targets at least the 
following features:
* Wait-free Garbage Collection (GC)
* M:N threading
* Value-based semantics
* Persistent data structures

It is hoped that this runtime will ultimately:
* Be an extremely performant M:N runtime for future language syntax(es)
* Allow use of Garbage Collection even in low-latency applications
* Offer a simple and elegant conceptual framework of implementation
* Eliminate distinctions between stack vs. dynamic (heap) allocation

## Background

* Minimally, a Garbage Collector reclaims no-longer-used areas of memory
  for use by future allocations.  Simply reclaiming these areas of memory where 
they exist permits increasing fragmentation over time.  Fragmentation is 
essentially small areas of available memory interspersed between allocated 
areas such that the total quantity of available memory exceeds a requested 
allocation, but there doesn't exist a contiguous amount of available memory 
sufficient to fulfill the requested allocation.  To avoid such undesirable 
fragmentation, a Garbage Collector may also perform consolidation of the 
no-longer-used memory in a phase known as "compaction".
* Compaction must make the no-longer-used areas of memory contiguous with one 
  another.  This implies that the still-in-use areas of memory will also become 
contiguous with one another.  This implies that some still-in-use areas of 
memory must be relocated from where they have existed in memory to some new 
location.
* Relocation of in-use areas of memory is problematic for program state 
  directly holding addresses of old locations (e.g. Java references and C/C++ 
pointers).  Typically as part of the garbage collection all such references 
need to be rewritten to point to the new consolidated locations.  While these 
references are being rewritten to point to their new locations the Mutator 
thread(s) must pause, which is what causes garbage collection pauses.
* RAM is essentially an `address -> value` O(1) mapping.  In the model of 
  C/C++, every byte of RAM is directly referencable/addressable via a `char*`, 
but this is not necessary for a programming language.  The very successful Java 
language (among others) has shown it is sufficient to have references which can 
only refer to class instances, without providing pointers that can refer to any 
byte.
*  Under the covers, Java references are implemented as containing an address 
   whose valid values are a much sparser set than C/C++ (not being allowed to 
point to just any byte, but rather just to the start byte of instances). The
address is an implementation detail and is not exposed to the programmer.  An 
alternate implementation of references could instead hold a non-address
"handle" as long as there were a way for the VM to ultimately translate this 
handle into the needed address of the referred-to structure.  This requires a 
lookup by the VM of `handle -> address` whenever a reference would be be 
dereferenced.  Having this layer of abstraction would allow the Compaction 
phase to rewrite only this lookup table instead of every reference's contained 
address throughout all of the program state.

## Sketch of Wait-free GC Mechanism

* The program thread (a.k.a. "Mutator") to hold 3 maps of `handle -> address`: 
  A, B, C.
* Mutator only ever modifies C.
* These maps have a precedence: entries in C supersede entries in B which 
  supersede entries in A.  (It can be said that C "overlays" B "overlays" A.)
* When Mutator needs to lookup an address for a given handle it checks C then B 
  then A, stopping when it finds the entry.
* Deletions of an entry for handle `h` must be performed by storing a mapping 
  `h -> TOMBSTONE` in C, because a simple deletion of `h` in C would otherwise 
allow an entry for `h` to "peek through" from B or A.
* Asynchronously to the Mutator, the GC thread can consolidate and merge maps A 
  and B into a merged map M.  (M gets then union of A's and B's keys minus B's 
keys whose value was TOMBSTONE, then all data at the addresses get relocated 
and the addresses updated.)
* Once the GC has completed its consolidation, it can inform the Mutator of M, 
  which can then atomically do:  A=M, B=C, C=(empty) (these should be seen as 
cheap pointer-like assignments, not recursive actions).
* This cycle repeats over time, such that the C map migrates to B, which will 
  eventually get merged by the GC with A, allowing the Mutator to never have to 
stop for GC consolidations.

#### Q: "Won't the deallocation of the old A and B maps cause work for the Mutator?"
A: No, we can deallocate A and B en-masse based on how allocations will only 
have increasing offsets and how we calculate our used-data-range of the 
ring-buffer.  The used-data-range of the ring-buffer goes from `LOW = 
min(lowest_offset(A), lowest_offset(B), lowest_offset(C))` to `HIGH = cursor` 
(the ring-buffer's next-allocation cursor).  As each A map was formerly a B 
map, and each B map was formerly a C map, note that the following is true for a 
given set of maps: `lowest_offset(A) < lowest_offset(B) < lowest_offset(C)`.  
Also, as the maps get reassigned by Mutator upon notifcation of GC 
consolidation, note that the following will be true: `lowest_offset(old_A) < 
lowest_offset(M) AND lowest_offset(old_B) < lowest_offset(M)`.  This is because 
M must necessarily have been constructed *after* A and B, so it will have a 
higher `lowest_offset` than both of them.  As such, upon the reassignment of 
the maps and recalculation of `LOW`, the old_A and old_B maps will exist below 
`LOW` (`LOW` having been essentially recalculated as `LOW = 
min(lowest_offset(M), lowest_offset(old_C), lowest_offset(new_C))`.  This means 
old_A and old_B now exist outside the used data range (LOW..HIGH) of the 
ring-buffer, which means those locations are considered deallocated and free 
for reuse with no further action.

#### Q: "Will the Mutator and GC need to contend through atomic operations on the ring-buffer's cursor?"
A: No, Mutator can initiate the GC collection by preallocating a region in the 
ring-buffer which is `size(A) + size(B)` and then passing that region to GC to 
be filled in with M.  Note that this doesn't affect M's relative placement to A 
and B:  M will still exist after A and B.

#### Q: "What happens when the offset reaches the end of the ring-buffer and as such gets modulo'd down to a lower value?  Then the above comparisons won't work, right?"
A: We keep the offsets in a pre-modulo'd state (actually, "pre-masked" as we 
use power-of-2 ring-buffer sizes), modulo'ing into the ring-buffer's memory 
only as necessary.  This allows the above comparisons to stay valid.

#### Q: "OK, but what happens when your offset's datatype overflows and wraps around, then the comparisons must fail, right?"
A: The above comparison operator is a simplification.  In actuality, we'll be 
using Serial Number Arithmetic (see below) which will prevent problems with 
wrap-around comparisons.

#### Q: "You've been shifting between addresses and offsets in your descriptions, could you clarify?"
A: Yes, sorry, I am trying to ease concept introduction.  An allocations within 
the ring-buffer will return an offset, not an address.  However, this offset is 
efficiently resolvable into an address: `ADDRESS = (offset & 
(ringbuffer.power_of_2_size - 1))`.  The purpose of using offsets instead of 
addresses is to abstract over ring-buffer resizes (the offsets will still apply 
to the larger ring-buffer, but resolve to a new actual address).  Above, where 
we create A, B, and C maps of `handle -> address` it is actually more correct 
to say they are `handle -> offset` maps.

#### Q: "It seems you'd want to use O(1) hashtables for the map implementation.  Wouldn't there be issues with choosing the right size, or or otherwise wouldn't the C map need an occasional large pause for a resize?"
A: Yes, it is true that an O(1) hashtable has these undesirable properties.  We 
will use for the map implementation a structure called the Array-Mapped Trie by 
Phil Bagwell that can give us "effective O(1)" complexity (in reality O(log32 
n)).  It is essentially a very shallow tree with a large (32-way) branching 
factor.  It has useful properties of not needing resizes and of easily being 
made persistent.

#### Q: "I see how the 3 map implementation suffices for dereferencing of handles given allocations and deallocations, but programs will also want to *modify* structures via their handles.  Wouldn't it cause problems if the Mutator would be modifying structures while the GC is observing them for its consolidation?"
A: Yes, this is another several points I glossed over.  The runtime will 
provide persistent data types such as an O(log n) RB-tree, an O(log32 n) 
hashmap, etc.  A mutation to a persistent data type instance is done via 
path-copying and produces a new instance version as represented by an offset to 
the root of the newly written path (with nodes along this path pointing to 
subsections of the older instances for data-sharing).  Because of this, the 
state of older instance versions will remain in place and still under GC 
observations even as new instance versions are derived from them.  (The 
alternative "fat-pointer" method of constructing persistent data structures 
would require undesirable mutations and so is avoided.)  So modifications to 
the persistent data types will be fine.
It is anticipated that the 3-map mechanism will only be used for containing 
entries to tuples which will be used to compose fields of primitive data types 
and persistent data types.  These tuples can be seen as analogous to structs in 
the C language.  One of these primitive data types would be "handle" which can 
be dereferenced through the 3-map set.  Read-only dereferences of handles would 
work fine.  Dereferences for mutation would be more involved: To modify a field 
of the tuple at handle `h`, it would be required to first copy the tuple 
forward with the modified field to new offset `o` and then place a new entry `h 
-> o` into map C.  Having a maximum arity for tuples (say of 256) would bound 
the work of this copy forward.

#### Q: "That sounds like a lot of tuple copying!"
A: Yeah, actually we won't actually copy the tuple for each field modification, 
we will use something I've termed the `cutoff_offset` to minimize the need for 
copying.  The `cutoff_offset` is an offset within the ring-buffer which 
represents the following property:  offsets lower than the `cutoff_offset` must 
remain immutable, offsets higher than the `cutoff_offset` can be mutated in 
place.  The `cutoff_offset` is maintained by the Mutator as needed, so as to 
lock down previous writes.

A simple example of a use case for `cutoff_offset` could be the following: data 
at offsets less than `cutoff_offset` have been exposed to the GC thread via a 
collection request, data at offsets greater than the `cutoff_offset` are 
exclusive to the Mutator, and when the Mutator transmits to the GC thread it 
updates `cutoff_offset` to point to the ring-buffer's cursor (exposing all 
previously-written data and forcing tuples to be copied-forward for updates).

Once an area of data has been locked down via the `cutoff_offset` it can no 
longer be modified, though the data will eventually be deallocated once 
observers of it can no longer exist.  As a tuple is copied forward its new copy 
must necessarily exist at an offset greater than the `cutoff_offset`.  The 
tuple's offset being greater than the `cutoff_offset` implies that there can be 
no other observers of this tuple and so it is safe to modify it in place with 
no further need to copy forward nor add/update an entry in map C.  So 
copy-forwards of tuples are only needed and performed for tuples whose offset 
is less than `cutoff_offset`.  If the Mutator does something to increase the 
`cutoff_offset` such that it now encompasses the tuple as "locked down" then 
the target tuple must be copied forward beyond the `cutoff_offset` before its 
copy can then be modified.

#### Q: "You mentioned resizing of the ring-buffer... Wouldn't this cause pauses?"
A: Yes, CB eliminates pauses due to GC consolidation/defragmentation but it 
does not eliminate pauses due to enlarging the amount of working memory.  These 
enlargements are performed by resizing the ring-buffer larger and will need to 
cause a pause.  It is expected that an appropriate ring-buffer size can be 
reliably estimated/overestimated to be used for the initial size at VM startup
Remember that with power-of-2 ring-sizing we are talking about an estimate of 
the order of magnitude!  Also, a ring-buffer resize pause is only as long as it 
takes for several mmap()s and a memcpy() of the smaller ring-buffer's contents 
into the larger one, so it should be relatively quick.

#### Q: "Wouldn't you have to check ring-buffer wrap-around of every read and write?"
A: Not with a "magic ring buffer"!  Please see a description below.  Basically, 
there will be a guarantee that reads/writes from/to the ring-buffer below the 
loop size will be contiguously visible in virtual memory due to the loop 
remapping the first N pages of the ring-buffer.  So long as our data structures 
are composed of substructures which remain smaller than this guarantee, we will 
never have to check for wrap-around (i.e. discontiguous reads/writes).  This 
does, however, mean, that thinks like arrays and hashmaps MUST be either 
unusually short or composed of shallow tree persistent data structures (which 
seem at best to achieve O(log32 N) complexity).

#### Q: "What is the complexity of this 3-map mechanism?"
A: The complexity of the 3 map lookup is the same as the complexity of the 
chosen map implementation itself because there is a constant factor of 3 
layers.  So, in our case, O(log32 n).  This doesn't mean that such constant
factors won't become limiting factors, unfortunately, and this is part of the 
experiment.

## Illustration of Mechanism

The algorithm requires 3 key-value maps: A, B, C.  In the initial state, these 
each begin empty:

```
    A            B            C
   ---          ---          ---
   (empty)      (empty)      (empty)
```

New allocations of class instances are assigned in C.  Here the program has 
allocated three new instances:

```
    A            B            C
   ---          ---          ---
   (empty)      (empty)      0 -> 0x10
                             1 -> 0x20
                             2 -> 0x30
```

Deallocations of instances are not removed from C, instead a tombstone value 
indicating non-presence is stored.  Here the program has deallocated instance 
1:

```
    A            B            C
   ---          ---          ---
   (empty)      (empty)      0 -> 0x10
                             1 -> TOMBSTONE
                             2 -> 0x30
```

At this point, the main program thread (a.k.a. the Mutator) intitates a garbage 
collection (e.g.  due to a timer, or a number of function calls, or some other
reason).  This will allow the separate garbage collector thread to begin the 
work of compacting the full set of items still in existence in A and B.

Message from Mutator To GC:  `{ do_collection, A, B }`

The main program thread (a.k.a. the Mutator) continues to run and modify C:

```
    A            B            C
   ---          ---          ---
   (empty)      (empty)      0 -> 0x10
                             1 -> TOMBSTONE
                             2 -> 0x30
                             3 -> TOMBSTONE
                             4 -> 0x50
```

The Garbage Collector thread replies to the Mutator thread with its resultant 
consolidation.  This is represented by a new map called M which contains the 
union of all entries in A or B, minus any keys which had a TOMBSTONE in B.  (B 
acts as an overlay of A).  Also, the address value for each remaining key has 
has been rewritten to point to a new, relocated address.

```
    M
   ---
   (empty)
```

Message from GC to Mutator:  `{ collection_done, M }`

At this point, the Mutator incorporates the GC-consolidated memory into its 
worldview.  These assignments happen atomically as far as main program 
execution is concerned:

```
A = M
B = C
C = (empty)

A            B                  C
   ---          ---                ---
   (empty)      0 -> 0x10          (empty)
                1 -> TOMBSTONE
                2 -> 0x30
                3 -> TOMBSTONE
                4 -> 0x50
```

Let's do a few more allocations:

```
    A            B                  C
   ---          ---                ---
   (empty)      0 -> 0x10          5 -> 0x60
                1 -> TOMBSTONE     6 -> 0x70
                2 -> 0x30
                3 -> TOMBSTONE
                4 -> 0x50
```
                
Now another merge...

```
    M
   ---
   0 -> 0x80
   2 -> 0x90
   4 -> 0xA0
```

... while C continues to be modified...

```
    A            B                  C
   ---          ---                ---
   (empty)      0 -> 0x10          2 -> TOMBSTONE
                1 -> TOMBSTONE     6 -> 0x70
                2 -> 0x30          7 -> 0xB0
                3 -> TOMBSTONE
                4 -> 0x50
```
                
... another map reassignment...

```
    A            B                  C
   ---          ---                ---
   0 -> 0x80    2 -> TOMBSTONE    (empty)
   2 -> 0x90    6 -> 0x70
   4 -> 0xA0    7 -> 0xB0
```

... another merge...

```
    M
   ---
   0 -> 0xC0
   4 -> 0xD0
   6 -> 0xE0
   7 -> 0xF0
```

... while C continues to be modified...

```
    A            B                  C
   ---          ---                ---
   0 -> 0x80    2 -> TOMBSTONE     8 -> 0x100
   2 -> 0x90    6 -> 0x70          9 -> 0x110
   4 -> 0xA0    7 -> 0xB0
```

... and finally, another map reassignment.

```
    A            B                  C
   ---          ---                ---
   0 -> 0xC0    8 -> 0x100         (empty)
   4 -> 0xD0    9 -> 0x110
   6 -> 0xE0
   7 -> 0xF0
```

Note here several things:
1) TOMBSTONEs get removed from A and B as they get merged to M, as M will no 
longer need to overlay any other map with its deletions once M is installed as 
the new A.
2) The C map proceeded with modifications as M was being built.
3) During the first collection iteration, the instance 2 has been deleted in 
the C map, even as M is also concerned with instance 2 for the collection.  The 
overlay semantics guarantees that this will not be a problem.
4) During the first allocation The C map allocations continued at 0xB0, while M 
used 0x80, 0x90, and 0xA0.  This is because the initiation of the GC was able 
to allocate an appropriately sized region for M to allocate within and bump the 
cursor ahead by this amount.  The M map allocates from within this region 
arranged for it, and the C map allocates beyond it.
5) Omitted in this illustration:  the map implementation will have its own 
internal nodes, so addresses would not appear so regularly-spaced; TOMBSTONEs 
take up space as they require aforementioned internal nodes; the sizing of M 
may be a maximal size and not as accurate as portrayed here; allocations within 
M's region would be most efficient when moving the cursor in reverse, as this 
would allow maximizing M's lowest_bound (further packing the ring-buffer's 
still-in-use data towards upper offsets and thereby maximizing the available 
data range).

## Dereferencing Pseudocode

```
void* offset_to_address(offset)
{
    return ring.baseptr + (offset & (ring.power_of_2_size - 1));
}

offset dereference_handle_for_read(handle)
{
    if (C[handle] exists) {
        if (C[handle] == TOMBSTONE)
            return NULLOFFSET;

return C[handle];
    }

if (B[handle] exists) {
        if (B[handle] == TOMBSTONE)
            return NULLOFFSET;

return B[handle];
    }

if (A[handle] exists) {
        /* Cannot be TOMBSTONE, as these will be cleared by consolidation */
        return A[handle];
    }

return NULLOFFSET;
}

offset dereference_handle_for_write(handle)
{
    if (C[handle] exists) {
        if (C[handle] == TOMBSTONE)
            return NULLOFFSET;

return C[handle];
    }

if (B[handle] exists) {
        if (B[handle] == TOMBSTONE)
            return NULLOFFSET;

new_offset = copy_instance_at(B[handle]);
        C[handle] = new_offset;
        return new_offset;
    }

if (A[handle] exists) {
        /* Cannot be TOMBSTONE, as these will be cleared by consolidation */
        new_offset = copy_instance_at(A[handle]);
        C[handle] = new_offset;
        return new_offset;
    }

return NULLOFFSET;
}
```

## Concepts / Glossary

### Dynamic Memory Allocation
Programs need to use memory to perform their duties.  Apportioning memory for 
use by a program is called memory allocation.  Some needed allocations can be 
known in advance at time of programming, but for many (and perhaps most) 
programs the needed allocations can only be determined during runtime.  The 
former set is considered "static memory allocation" and the latter set is 
called "dynamic memory allocation".

In unmanaged and non-garbage-collected languages like C and C++, any dynamic 
allocation of memory is the programmer's responsibility to free.  e.g.  in C:
```
   void *p = malloc(5);  //Allocate 5 bytes, returning a pointer to them.
   //...some work...
   free(p);   //Deallocate the allocated bytes.
```
Note that both `malloc()` and `free()` may perform some not-insubstantial 
amount of work during their invocations.  There are many opportunities for 
programmer error in the pairing of allocations and deallcations, especially as 
these two halves become further apart in code and/or time.

Benefit of Dynamic Memory Allocation:
* Dynamic Memory Allocation is the only solution for problems whose allocations 
  can only be known at runtime.

Drawback of Dynamic Memory Allocation:
* Can add a significant fast-path cost for both the `malloc()` and `free()` 
  routines.
* Can cause memory fragmentation. This is where available memory exceeds a 
  requested allocation size, but this available memory is not contiguous so 
cannot be used to fulfill the allocation request.

### Garbage Collection
Garbage-collection is a technology which allows automatic reclamation of 
dynamically allocated memory which has become no longer in use.  In 
garbage-collected languages, the programmer still specifies dynamic allocations 
(via something analoguous to `malloc()`, though a given language's syntax may 
not make such allocations obvious), but the programmer does not specify an 
equivalent of `free()`.  Instead, the language runtime performs 
garbage-collection of dynamically allocated memory which can be detected to be 
no-longer used.  This detection is often done via a reachability analysis of 
the memory structures of the program.  As in, there is a section of code of the 
language runtime called "the garbage collector" which will start from a root 
set of "definitely reachable" structures (e.g. static variables, and all of the 
stack-allocated references of all threads' stack frames) and then recursively 
introspect structures and chase pointers until it has fully exhausted the set 
of all reachable memory which it then considers "still-in-use".  At this point, 
the garbage collector can consider all unreachable memory addresses as now 
available for re-use by future allocations.  To reduce fragmentation of 
available memory, there will often also be a "compaction" of the "still-in-use" 
memory.  This will consolidate the still-in-use structures into a more 
condensed arrangement with the corresponding intent that the free areas become 
contiguous and can therefore be used to fulfill larger future allocations than 
if they had remained small and discontiguous.

Benefits of Garbage Collection:
* Reduces concerns needing to be managed by the programmer, leading to faster 
  coding cycles.
* Reduces chances of error by programmer (i.e. lack of `free()` causing memory 
  leak, double-`free()` causing memory corruption).
* The `free()` can happen asynchronously to the main body of code, potentially 
  taking its work off of the fast path and reducing latency
* Memory consolidating garbage collectors allow for lower fragmentation of 
  available process memory, increasing efficiency (smaller memory footprint in 
terms of VM pages, fewer trips to OS to ask for more memory).

Drawbacks of Garbage Collection:
* The work of collecting garbage historically must cause pauses in the work of 
  the application.  These pauses can be minimized (as with advanced techniques 
such as Erlang's runtime, which can use ultra-small GC cycles limited to the 
memory of a single green-thread) but they still exist and cause latency jitter 
in the execution of applications.

References:
_The Garbage Collection Handbook: The Art of Automatic Memory Management_ by 
Richard Jones, Antony Hosking, Eliot Moss

### Arena-Based Allocation
(a.k.a. "Bump-pointer Allocation", "Sequential Allocation", "Region-Based 
Allocation")

As mentioned above, both `malloc()` and `free()` routines have a potentially 
significant cost.  This is especially true if they are done multiple times or 
if they are done on the fast-path (a latency-sensitive portion of an 
application's code).  Arena-based allocation is an alternative approach for 
dynamic memory allocation which is sometimes used.

```
//Allocate a 10MB arena.
char *arena = malloc(10 * 1024 * 1024);
char *arena_cursor = arena;

// Later... Perform cheap dynamic allocation(s).
item *item = arena_cursor;
arena_cursor += sizeof(item);
other_item *other_item = arena_cursor;
arena_cursor += sizeof(other_item);

//Possibly reset the arena to reuse its space.
arena_cursor = arena;

//Later... Deallocate the entire arena and any contained items at once.
free(arena);
```

Advantages of Arena-Based Allocation:
* Aside from the initial `malloc()`, the cost of any dynamic allocation has 
  been reduced from the cost of a `malloc()` call to the cost of adding a value 
to a pointer.  The cost of adding a value to a pointer is so cheap as to be 
effectively free.
* Multiple dynamic allocations have paid only a single cost of `malloc()`.
* Multiple dynamic deallocations have paid only a single cost of `free()`.
* Arena-allocated items do not need to be of equal size.

Disadvantages of Arena-Based Allocation:
* Must consider appropriate initial size of arena.
* Must consider dynamic allocations exhausting the size of the arena.
* Individual deallocations of items is unsupported.  (It can be supported but 
  complexifies and slows allocations, and would generally only be appropriate 
for arenas which allocate items of a single size.)

Reference: [Wikipedia: Region-Based Memory Management] (https://en.wikipedia.org/wiki/Region-based_memory_management)

### Ring Buffers
A ring buffer is a data structure implemented as a contiguous array of 
elements.  The elements of this array are accessed using cursors that will be 
mapped to the array index range `[0, count)` via modulo arithmetic.  This 
allows the cursors to perpetually advance while being used to refer to array 
elements within the valid range.  If the underlying array has a number
of elements which is a power of two, instead of the (relatively expensive) 
modulo operation a (relatively cheap) bitmask AND operation may be used as it 
will be numerically equivalent.

Ring buffers are often used with two cursors as a FIFO channel between a 
producer and a consumer.  The producer is responsible for one cursor's 
advancement, and the consumer for the other cursor's advancement.  The 
relationship `consumer_cursor <= producer_cursor` is maintained, and the range 
`[consumer_cursor, producer_cursor)` will contain produced-but-not-yet-consumed 
data.

Reference: [Wikipedia: Circular Buffer](https://en.wikipedia.org/wiki/Circular_buffer)

### Magic Ringbuffers
(a.k.a. Virtual Ring Buffers)

Ring buffers may be used to contain slotted elements of data (e.g.  slots of 
pointers), or could alternatively be used as a character array stream.  For the 
character array stream case, writing a logically contiguous region of memory 
into the ring buffer may necessitate a two part write if the placement of
to-be-written-region were to surpass the last index within the ringbuffer and 
as such need to wrap-around to earlier indices.  In addition to the two part 
write, bounds checking operations need to take place during every read and 
write, to ensure that this "wrapping around" will take place when appropriate.

Philip Howard seems to be (according to my Google searches) the inventor of the 
following optimization:  Memory management APIs (e.g.  `mmap()` on Linux), can 
be used to cause the same physical page of memory (i.e. hardware memory pages) 
to be made available through multiple virtual memory addresses (i.e. the 
addresses which are used within a C program's memory address space).  As such, 
the entire ringbuffer pages could be `mmap()`'d again immediately subsequent to 
their original location.  E.g.:

```
Simple Ring Buffer
    [ A | B | C | D ]

Magic Ring Buffer
    [ A | B | C | D | A' | B' | C' | D' ]

\-------remap-------/

The A'...D' pages are the exact same physical pages as A...D, just available 
also under other virtual addresses.  A write in B' will show up in B and vice 
versa.

```

With this layout, no two-part writes nor bounds checking need to take place 
during reads or writes.  Any write or read less than the length of the 
ring-buffer must begin within A...D (due to the ring buffer's modulo operation) 
and end within A'...D'.  Due to the second mapping of these pages, the 
wraparound reads/writes will be automatic and no bounds checks will be 
necessary.

Reference: [Virtual Ring Buffers by Philip Howard] (http://vrb.sourceforge.net/)

### Serial Number Arithmetic
It is often useful to compare two sequence numbers to determine which is 
greater than another.  In infinite or very large sequences with sequence 
numbers represented by values of finite size (e.g. hardware 32-bit integer 
registers), eventually deriving the next sequence number will "wrap-around" 
such that direct comparison between sequence numbers is inadequate to represent 
their ordering.

The solution to this problem is called "Serial Number Arithmetic".  Basically, 
value1 is greater than value2 if value1 exists in the half of the total range 
of values (i.e. 2^31) subsequent to value2, even if this half-the-total-range 
wraps around to lower values.  Likewise, but in the lower-half, for value1 
being less-than value2.  This forms somewhat of a finite "sliding window" for 
working with sequences larger than that window.

Reference: [Serial Number Arithmetic] (https://en.wikipedia.org/wiki/Serial_number_arithmetic)
Reference: [RFC 1982] (https://tools.ietf.org/html/rfc1982)

### Persistent Data Structures
TODO

### Persistent Red-black Tree
TODO

### Persistent HAMT
TODO

### The Cutoff Offset
TODO

### Green-Threads
TODO

### Alternative to Address-based Pointers
Conceptually, a pointer in C is a unique handle through which you can access 
your data via "dereferencing" it.  Mostly, C language implementations leverage 
the fact that your data will exist somewhere in memory and that the address of 
your data's location will already be a suitably unique value, so the address is 
what gets used as a handle.  Hardware instructions will ultimately require an 
address, so using the address as a handle dovetails with hardware details and 
allows avoidance of a separate lookup of `handle -> address`.

However, using addresses is not required for pointers.  Instead, an 
implementation could choose to use some other form of identifier (say sequence 
numbers), so long as dereferencing actions then included such a `handle -> 
address` lookup.

Reference: [What exactly is a C pointer if not a memory address?]( http://stackoverflow.com/questions/15151377/what-exactly-is-a-c-pointer-if-not-a-memory-address/15151542#15151542 )

### cb_offset_t
TODO

### The Structmap
The structmap is an implementation of the "Alternative to Address-based 
Pointers", as described above.  Instead of "pointers represented by addresses" 
there will be "references represented by integer struct_ids". The idea is that
dynamic allocations will be assigned unique sequential integer identifiers 
derived from a monotonically increasing `next_struct_id`.  These allocations 
will also place a new entry in the structmap, which will be used for later 
`struct_id -> cb_offset_t` "dereferences".

## Roadmap
TODO

vim: fo=cqtaw2l

cb

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README