compile_time_object_collections.md

Compile-Time Object Collections Discussion

This document covers active discussion about building compile-time collections of objects in C++. The following use cases are examples of where compile-time collections are useful:

• StringRef - A type that supports building a compile-time collection of string labels with associated unique numeric ids for tracing purposes.
• LockClass - A type that supports building a compile-time collection of state objects for runtime lock validation purposes.

The following sections discuss common and unique requirements of each use case, the current challenges with the implementations, and proposed solutions.

StringRef

StringRef is a type that implements the concept of string references. A string reference is a mapping from a numeric id to a character string. Using the mapping makes more economical use of the trace buffer: an (id, string) pair is emitted once in a tracing session and then subsequent events may refer to the string by id instead of including the full character sequence inline.

The following is a simple example of StringRef in action:

#include <lib/ktrace.h>

template <typename Op, typename... Args>
inline DoSomething(Op&& op, Args&&... args) {
    ktrace_probe(TraceAlways, TraceContext::Thread, "DoSomething"_stringref);
    // ...
}

Here the string literal operator _stringref returns an instance of StringRef that provides the facility to map the string "DoSomething" to a numeric id used by the tracing function.

Requirements

• Emit each (id, string) mapping at most once per tracing session, prior to any trace event that references the id. Ideally the full set of mappings is emitted at once at the start of a tracing session to avoid the overhead of emitting mappings in the middle of timing sensitive code however, this is not a hard requirement.
• A dense id space is desirable so that down stream processing code can use a linear pre-allocated array or vector to implement the id-to-string lookup, however this is not a hard requirement.
• Some method to unique duplicate string references, since trace calls must be supported in template and inline functions and methods.

Current Implementation

The following is an outline of the current StringRef implementation.

struct StringRef {
    static constexpr int kInvalidId = -1;

    const char* string{nullptr};
    ktl::atomic<int> id{kInvalidId};
    StringRef* next{nullptr};

    int GetId() {
        const int ref_id = id.load(ktl::memory_order_relaxed);
        return ref_id == kInvalidId ? Register(this) : ref_id;
    }

    // Returns the head of the global string ref linked list.
    static StringRef* head() { return head_.load(ktl::memory_order_acquire); }

private:
    // Registers a string ref in the global linked list.
    static int Register(StringRef* string_ref);

    static ktl::atomic<int> id_counter_;
    static ktl::atomic<StringRef*> head_;
};

// Returns an instance of StringRef that corresponds to the given string
// literal.
template <typename T, T... chars>
inline StringRef* operator""_stringref() {
    static const char storage[] = {chars..., '\0'};
    static StringRef string_ref{storage};
    return &string_ref;
}

LockClass

LockClass is a type that captures information about a lock that is common to all instances of the lock (e.g. its containing type if it is a struct/class member, the type of the underlying lock primitive, flags describing its behavior). The LockClass type is used by the runtime lock validator to determine which ordering rules apply to each lock and to locate the per-lock-class tracking structure used to record ordering observations.

The following is a simplified example of LockClass in action:

struct Foo {
    LockClass<Foo, fbl::Mutex> lock;
    // ...
};

struct Bar {
    LockClass<Bar, fbl::Mutex> lock;
};

Requirements

• Ability to iterate the tracking state for all instantiations of LockClass, for cycle detection and error reporting purposes.
• Some method to unique duplicate tracking state, since instantiations of LockClass may be visible from multiple compilation units, depending on how the containing types (e.g. Foo and Bar) are used.
• A dense id space is desirable so that down stream processing code can simplify id storage however, this is not a hard requirement.

Current Implementation

The following is a simplified implementation of LockClass:

template <typename ContainingType, typename LockType>
class LockClass {
    // ...
private:
    static LockClassState lock_class_state_;
};

Each instantiation of LockClass creates a unique instance of LockClassState to track the online lock order observations related to locks of class (ContainingType, LockType). The current implementation of LockClassState constructs a linked list of all instances in a global ctor to support the iteration requirement.

Compile-Time Array Solution

One way to address the requirements of both types is to build a compile-time array of de-duplicated static instances, using COMDAT sections and groups. This completely removes the need to build linked lists of objects at init time or runtime and supports all of the requirements for each type.

For example:

// Defined in the linker script mark the beginning and end of the section:
// .data.lock_class_state_table.
extern "C" LockClassState __start_lock_class_state_table[];
extern "C" LockClassState __end_lock_class_state_table[];

template <typename ContainingType, typename LockClass>
class LockClass {
    // ...
private:
    static LockClassState lock_class_state_ __SECTION(".data.lock_class_state_table");
};

// Defined in the linker script to make the beginning and end of the section:
// .rodata.string_ref_table.
extern "C" StringRef __start_string_ref_table[];
extern "C" StringRef __end_string_ref_table[];

struct StringRef {
    const char* const string;
    size_t GetId() const {
        return static_cast<size_t>(this - __start_string_ref_table);
    }
};

template <typename T, T... chars>
inline StringRef* operator""_stringref() {
    static const char storage[] = {chars..., '\0'};
    static StringRef string_ref __SECTION(".rodata.string_ref_table") {storage};
    return &string_ref;
}

The challenge with this approach is that GCC does not properly handle the section attribute on static members of template types or functions. However, Clang does handle the section attribute correctly for these types.