Garbage Collection

2026-11-18 · garbage collection

notes / DOCS

RAII: Resource Aquisition is Initilisation

during allocation define lifetime

relies heavily on scope

std::unique_ptr<>();
std::shared_ptr<>();
std::mutex m;

void bad() 
{
  m.lock();             // acquire the mutex
  f();                  // if f() throws an exception, the mutex is never released
  if (!everything_ok())
      return;           // early return, the mutex is never released
  m.unlock();           // if bad() reaches this statement, the mutex is released
}

void good()
{
  std::lock_guard<std::mutex> lk(m); // RAII class: mutex acquisition is initialization
  f();                               // if f() throws an exception, the mutex is released
  if (!everything_ok())
      return;                        // early return, the mutex is released
}                                    // if good() returns normally, the mutex is released
class ScopedFlag {
  bool& flag;
public:
  ScopedFlag(bool& f) : flag(f) { flag = true; }
  ~ScopedFlag() { flag = false; }
};
#include <chrono>
#include <iostream>
#include <string>

class ScopedTimer {
  std::string name;
  std::chrono::steady_clock::time_point start;
public:
  explicit ScopedTimer(std::string n)
      : name(std::move(n)), start(std::chrono::steady_clock::now()) {
      std::cout << name << " started.\n";
  }
  
  ~ScopedTimer() {
      auto end = std::chrono::steady_clock::now();
      auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
      std::cout << name << " finished in " << ms << " ms.\n";
  }
};

Garbage Collection Techniques

Ideally: The perfect garbage collector

  1. No visible impact on program execution: parallel
  2. Works with any program/data structure/access pattern: cyclic data structures?
  3. Collects garbage immediately: incremental
  4. Spatial locality of reference: no excessive paging/cache effects
  5. Efficient heap management: minimise fragmentation etc

Reference Counting

Costs:

Benefits:

eg. std::shared_ptr

perhaps related

krefs

Kernel developers get to use kernel references for their data structures to manage lifetimes. A kref is just an atomic reference counter provided in the core-api of the linux kernel.

struct my_kernel_ds {
  /* ... */
  struct kref kref;
};

void data_release(struct kref *ref) {
  // this is dircetly from the docs
  struct my_kernel_ds *data = container_of(ref, struct my_kernel_ds, refcount);
  kfree(data);
}

void data_handling(void* cb_ds) {
  struct my_kernel_ds my_ds = cb_ds;
  /* ... */
  kref_put(&my_ds->kref, data_release); // PUT when done with the reference
}

int main() {
  struct my_ds *data;
  data = kmalloc(sizeof(*data), GFP_KERNEL);
  kref_init(&data->kref);

  /* ... whatever multithreaded stuff ... */
  kref_get(&data->kref); // GET before creating a reference
  task = kthread_run(data_handling, data, "meh");
}

kref src code (very short). Notice the mutex/lock versions of kref_put():

/**
 * kref_put_lock - Decrement refcount for object
 * @kref: Object
 * @release: Pointer to the function that will clean up the object when the
 *       last reference to the object is released.
 * @lock: Spinlock which protects the release function.
 *
 * This variant of kref_lock() calls the @release function with the @lock
 * held.  The @release function will release the lock.
 */
static inline int kref_put_lock(struct kref *kref,
                void (*release)(struct kref *kref),
                spinlock_t *lock)
    __cond_acquires(true, lock)
{
    if (refcount_dec_and_lock(&kref->refcount, lock)) {
        release(kref);
        return 1;
    }
    return 0;
}

those are to ensure the atomicity of the release function if that is something that is desired. kref_put_lock() acquires the lock, and the release function is the one that releases the lock

Something like

static DEFINE_MUTEX(mutex);
static LIST_HEAD(q);

struct my_data {
  struct kref      refcount;
  struct list_head link;
};

static struct my_data *get_entry() {
  struct my_data *entry = NULL;
  mutex_lock(&mutex);
  if (!list_empty(&q)) {
          entry = container_of(q.next, struct my_data, link);
          kref_get(&entry->refcount);
  }
  mutex_unlock(&mutex);
  return entry;
}

static void release_entry(struct kref *ref) {
  struct my_data *entry = container_of(ref, struct my_data, refcount);

  list_del(&entry->link);
  kfree(entry);

  mutex_unlock(&mutex);
}

static void put_entry(struct my_data *entry) {
  kref_put_mutex(&entry->refcount, release_entry, &mutex);
}

Cyclic data structures

Reference counting only accounts for existing references, not whether the cell is reachable

for example

something -> A ------+
             ^       |
             |       v
             +------ B <- something

both A and B have 2 references each

now both the somethings die and A and B are no longer reachable, yet their references are not 0 and they can not be deleted :(

-X->  A ------+
      ^       |
      |       v
      +------ B 

Tracing

tracks reachability which is more reliable than references

Costs:

Pros:

Generational Tracing

optimisation over direct tracing GC

Most objects die young

Costs:

Pros:

Drawbacks of Automatic GC


  1. discord switched to rust because of this↩︎