[C][C++] libfabric

Libfabric Programmer's Guide - Introduction

libfabric

[C++] hash library

martinus/robin-hood-hashing

[C++] pointer-compression; from v8 oilpan-library point of view.

Reference:

• https://v8.dev/blog/oilpan-pointer-compression
• https://v8.dev/blog/oilpan-library
• oilpan code [google git]
• https://en.wikipedia.org/wiki/64-bit_computing#Limits_of_processors
• https://vsdmars.blogspot.com/2020/07/virtual-memory-refresh.html
• Pointer Compression in Oilpan design doc
• https://v8.dev/blog/pointer-compression

Pointer compression has been used in many opensource projects (e.g. cachelib, chrome);

the idea is to use less bits in 64-bit arch (usually 1 word/8 bytes for pointer, 2-words for pointer to member function) to present virtual memory address.

Thus the pointer size compression implementation design can be done as follows:

1. cage' (or slab) a range of heap memory block
2. The size of a heap cage is limited by the available bits for the offset. e.g., a 4GB heap cage requires 32-bit offsets.
   The compressed pointer contains only the offset index from the base address of the 'cage' heap virtual memory.
3. the 'cage' continuously heap virtual memory base address is per thread, thus, thread_local base pointer can be used here. However, thread local storage (TLS) is slow; thus Oilpan uses single caged heap memory per process.

Oilpan design requirements:

'Member' type instance(i.e. ref counted smart pointer) can take:

1. A valid heap pointer to an object;
2. The C++ nullptr (or similar);
3. A sentinel value which must be known at compile time. The sentinel value can e.g. be used to signal deleted values in hash tables that also support nullptr as entries.

nullptr has its own type domain; what 's value of compress(nullptr) ?

Is it nullptr means deleted object or just pointing to null?

Extra requirements:

1. Compress/decompress should be inlined at call site. (i.e. __attribute__((always_inline)) )
2. Fast and compact instruction sequence to minimize i-cache misses.
3. Branchless instruction sequence to avoid using up branch predictors.
4. Consider read/write separately. Read > Write counts; thus:
   Fast decompression is preferred.

Design idea:

The main idea for the scheme that is implemented as of today is to separate regular heap pointers from nullptr and sentinel by relying on alignment of the heap cage.

Thus, for cage heap memory, allocated it with alignment such that the least significant bit

of the upper half-word is always set.

cage heap memory allocated with alignment as base address:

0x00 00 00 01  |  00 00 00 00

nullptr:

0x00 00 00 00  |  00 00 00 00

sentinel:

0x00 00 00 00  |  00 00 00 02

Compression generates a compressed value by merely right-shifting by one and truncating away the upper half of the value. In this way, the alignment bit (which now becomes the most significant bit of the compressed value) signals a valid heap pointer.

e.g.

original heap memory:

00000000 00000000 00000000 00000001 00000000 11111111 00000000 00000000

compressed:

00000000 00000000 00000000 00000000 10000000 01111111 10000000 00000000

and truncating away the upper half:

10000000 01111111 10000000 00000000 (half word, the msb 1 indicates a valid heap memory address)

With this implementation, compressed nullptr become:

00000000 00000000 00000000 00000000

With this implementation, compressed sentinel become:

00000000 00000000 00000000 00000001

Note that this allows for figuring out whether a compressed value represents a heap pointer, nullptr, or the sentinel value, which is important to avoid useless decompressions in user code.

Decompression relies on a specifically crafted base pointer, in which the least significant 32 bits are set to 1.

Base:

0x00 00 00 01  |  FF FF FF FF

The decompression operation first sign extends the compressed value and then left-shifts to undo the compression operation for the sign bit.

And  the decompressed pointer is just the result of a bitwise and between this intermediate value and the base pointer. 

Heap pointer:

10000000 01111111 10000000 00000000 to

00000000 00000000 00000000 00000000 10000000 01111111 10000000 00000000 to

00000000 00000000 00000000 00000001 00000000 11111111 00000000 00000000 (first stage decompressed)

00000000 00000000 00000000 00000001 11111111 11111111 11111111 11111111 &

----------------------------------------------------------------------------------------------------------------

00000000 00000000 00000000 00000001 00000000 11111111 00000000 00000000 (decompressed)

nullptr:

00000000 00000000 00000000 00000000 000000000 00000000 00000000 00000000

00000000 00000000 00000000 00000001 111111111 11111111 11111111 11111111 &

----------------------------------------------------------------------------------------------------------------

00000000 00000000 00000000 00000000 000000000 00000000 00000000 00000000 (decompressed)

sentinel:

00000000 00000000 00000000 00000000 000000000 00000000 00000000 00000010

00000000 00000000 00000000 00000001 111111111 11111111 11111111 11111111 &

----------------------------------------------------------------------------------------------------------------

00000000 00000000 00000000 00000000 000000000 00000000 00000000 00000010 (decompressed)

Several gotcha in the article mentioned worth noted here:

1. Optimizing cage base load, the cage base pointer an't constexpr at runtime thus impedes compilter to reason for generating faster code. The Oilpan team tackle this with clang's attributes; i.e. using 
   __attribute__((require_constant_initialization));
   (https://chromium-review.googlesource.com/c/v8/v8/+/2739979/17/include/cppgc/member.h#38
   https://chromium.googlesource.com/chromium/src/+/f47da96363899cbe1b3b851119bb3409eac253e1/base/allocator/partition_allocator/pcscan.h#17
   https://clang.llvm.org/docs/AttributeReference.html#require-constant-initialization-constinit-c-20)
2. Avoiding decompression at all;
1. decompress nullptr to check if it's null
2. constructing or assigning a Member from another Member needs no decompression/compression
3. Comparison of pointers is preserved by compression, so we can avoid transformations for them as well.
4. Hashing can be sped up with compressed pointers. Decompression for hash calculation is redundant, because the fixed base does not increase the hash entropy. Instead, a simpler hashing function for 32-bit integers can be used.
   Blink has many hash tables that use Member as a key; the 32-bit hashing resulted in faster collections!
3. Helping clang where it fails to optimize; remove unnecessary decompression in memory barriar blocks.
4. While now the pointer has been compressed, be ware of padding since pointer is now size of int_32; using compressed pointer inside the structure should be padding considered.

TBD:

oilpan-library code dig. 

https://chromium.googlesource.com/v8/v8.git/+/HEAD/include/cppgc/

https://chromium.googlesource.com/v8/v8/+/main/samples/cppgc/hello-world.cc

[library] libsodium - a modern, easy-to-use software library for encryption, decryption, signatures, password hashing and more.

Reference:

https://libsodium.gitbook.io/doc/

[linux][namespace] unfork

Reference:

https://github.com/vsdmars/unfork

userfaultfd: https://www.man7.org/linux/man-pages/man2/userfaultfd.2.html

process_vm_readv: https://man7.org/linux/man-pages/man2/process_vm_readv.2.html

[C++] Opaque Typedef library

video:
https://www.youtube.com/watch?v=jLdSjh8oqmE

library:
https://sourceforge.net/p/opaque-typedef/wiki/Home/#opaque-typedef-library

Reference:
Toward Opaque Typedefs for C++1Y, v2 (PDF)
[C++][NOTE][ORIGINAL] Strong typedef

Microprocessors have kinds of addresses:

• Virtual address
• Linear address
• Guest physical address
• Host physical address
• DDR address

What kind of address am I talking about?

Opaque typedef

Idea:

• Wrap a variable of some type in a new type
• Mimic the interface of the original type, but using the new type

code:

struct linaddr : numeric_typedef<uint64_t, linaddr>
{
 using base = numeric_typedef<uint64_t, linaddr>;
 using base::base;
}

Merit:

• Safer interfaces by removing implicit convertibility
• Makes overloading on the new type possible
• Turn semantic bugs into compile time errors

[C++11][note] C++11 Library Design

Excerpt from Aerix Consulting

Study notes:

1. Function Interface Design

Is my function? :

• easy to call correctly?
• hard to call incorrectly?
• efficient to call?
• with minimal copying?
• with minimal aliasing?
• without unnecessary resource allocation?
• easily composable with other functions?
• usable in higher-order constructs?

What’s the best way of getting data into and out of a function?

• Input Argument Categories
• Read-only: value is only ever read from, never modified or stored
• const l-ref (except small ones)
• Sink: value is consumed, stored, or mutated locally
• Goal: Avoid unnecessary copies, allow temporaries to be moved in.
• const l-ref and copy it into local variable
• r-ref. Take the r-value into function.
• What if the function takes more than 1 sink argument?
• Take sink arguments by value.
  Since if passing in r-value, the r-value will be created as the l-value argument.
  No extra copy constructor call needed. (extra reference: WANT SPEED? DON’T (ALWAYS) PASS BY VALUE.)
• Eric Niebler : Out Parameters, Move Semantics, and Stateful Algorithms
• Encapsulate an algorithm’s state in an object that implements the algorithm.
  

2. Class Design
Can my type be…?:

• …copied and assigned?
• …efficiently passed and returned?
• …efficiently inserted into a vector?
• …sorted?
• …used in a map? An unordered_map?
• …iterated over (if it’s a collection)?
• …streamed?
• …used to declare global constants?

• Regular Types
• Reference:
• rules of three:
• http://stackoverflow.com/a/4172724
• Basically, int-like types.
• Copyable, default constructable, assignable, equality-comparable, swappable, order-able
• They let us reason mathematically
• The STL containers and algorithms assume regularity in many places
• 
• Make your types regular (if possible)
• **Make your types’ move operations noexcept (if possible)
• Q: Is my type Regular?
  A: Check it at compile time!

template<typename T>
struct is_regular
: std::integral_constant< bool,
std::is_default_constructible<T>::value &&
std::is_copy_constructible<T>::value &&
std::is_move_constructible<T>::value &&
std::is_copy_assignable<T>::value &&
std::is_move_assignable<T>::value >
{};
struct T {};
static_assert(is_regular<T>::value, "huh?");

Movable Types:

• The moved-from state must be part of a class’s invariant.
• If above doesn’t make sense, the type isn’t movable.
• Every movable type must have a cheap(er)-to-construct, valid default state.

3. Module

Think:

• In C++11, what support is there for…
• … enforcing acyclic, hierarchical physical component dependencies? 
• … decomposing large components into smaller ones? 
• … achieving extensibility of components? 
• … versioning (source & binary) components?

New library version with interface-breaking changes:

• Put all interface elements in a versioning namespace from day one
• Make the current version namespace inline

Name Hijacking: Unintentional ADL finds the wrong overload:

• template arguments are participating ADL.

ADL:
If the class is a class template instantiation, then the types of the template type arguments and the classes and namespaces in which the template template arguments are declared are also included.

Solution:

1. Use a non-inline ADL-blocking namespace

2. Use global function objects instead of free functions(i.e: Global function object, aka. functor)

C++14 Variable Templates:
cpp14_variable_templates

template<typename T> struct lexical_cast_fn 
{ 
template<typename U> T operator()(U const &u) const 
{ //... } 
};

template<typename T> constexpr lexical_cast_fn<T> lexical_cast{};

int main()
{ 
lexical_cast<int>("42");
}

Ode To Function Objects:

• They are never found by ADL!
• If phase 1 lookup finds an object instead of a function, ADL is disabled!
• They are first class objects
• Easy to bind
• Easy to pass to higher-order functions like std::accumulate

Guideline:

• Put type definitions in an ADL-blocking (non-inline!)
  namespaces and export then with a using declaration, or…
• Prefer global constexpr function objects over named free functions (except for documented customization points)