# 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:

```C++
#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.

```C++
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:

```C++
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:

```C++
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:

```C++
// 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.