Reference Counting

Stuttgart Media University

1 Ownership Problem

void* create() {
  return new char[128];
}

void release(void* &p) {
  delete[] p;
  p = nullptr;
}

void use(void* p) {
  cout << p << endl;
}

void* g_p = nullptr;
void useAndRemember(void* p) {
  g_p = p;
  cout << g_p << endl;
}

void useRemembered() {
  cout << g_p << endl;
}

void* p = create();
use(p);
useAndRemember(p);
useRemembered();
release(p);
use(p);
useRemembered();

Output:

0000000000209B70
0000000000209B70
0000000000209B70
0000000000000000
0000000000209B70

Who owns p?
Who is responsible for the deletion of p?
How do we know when the data is no longer needed?

2 Smart Pointers

A smart pointer is a C++ class that mimics a regular pointer in syntax and some semantics, but it does more.

template <class T>
class SmartPtr
{
public:
  explicit SmartPtr(T* pointee) : m_pPointee(pointee) { }
  ~SmartPtr() { delete m_pPointee; }
  T& operator* () const { return *m_pPointee; }
  T* operator->() const { return m_pPointee; }
private:
  T* m_pPointee;
};

{
  SmartPtr<Enemy> spEnemy(new Enemy());
  spEnemy->attack();
  (*spEnemy).flee();
} // destructor is called -> enemy is deleted

2.1 Smart Pointer Value Semantics

An object with value semantics is an object that you can copy and assign to.
- Thus, things like a reference count can be updated inside the respective functions.

=> Smart Pointers are most commonly used for ownership management and reference counting!

template <class T>
class SmarterPtr
{
public:
  // constructors
  SmarterPtr();
  SmarterPtr(T* p);
  SmarterPtr(const SmarterPtr& other);
  SmarterPtr(SmarterPtr&& other);
  // destructor
  ~SmarterPtr();
  // assignment operators
  SmarterPtr<T>& operator=(T* p);
  SmarterPtr<T>& operator=(const SmarterPtr& rh);
  SmarterPtr<T>& operator=(SmarterPtr&& rh);
  // pointer semantics
  T& operator* () const;
  T* operator->() const;
};

3 Intrusive vs. Non-intrusive Reference Counting

Non-intrusive Reference Counting can cause a significant overhead
- Multiple referenced need to be maintained and managed
- Large jumps in memory are often required (low cache efficiency)
- Threading and concurrency are more difficult to realize properly

50%

Intrusive Reference Counting: The reference count is an "intruder" in the pointee - it semantically belongs to the smart pointer.
- The implementation and performance overheads are much lower
- Multiple inheritance makes the implementation rather trivial
  - All objects in need of reference counting simply inherit from a type that supports counting
- Smart pointers wrap around these objects and change their reference counts accordingly
- This is the preferred method, especially in game engines

50%

=> A generic smart pointer should use intrusive reference counting where available and implement a non-intrusive reference counting scheme as an acceptable alternative.

4 C++ Standard Smart Pointers

4.1 Usage Example

struct Named
{
  char m_pName[4];
  Named(const char* name) { memcpy(m_pName, name, 3); m_pName[3]=0; }
  ~Named() { printf("deleting '%s'\n", m_pName); }
};

#include <memory>

#define BEGIN { printf("{\n");
#define END } printf("}\n");

weak_ptr <Named> wp1;
BEGIN 
  unique_ptr<Named> up1(new Named("uni"));
  shared_ptr<Named> sp1(new Named("shr"));
  BEGIN
    unique_ptr<Named> up2 = std::move(up1);

  END // object 'uni' is destroyed

  wp1 = sp1; // assign weak pointer
  BEGIN 
    shared_ptr<Named> sp2 = sp1;
  END // reference count is decremnted
  cout << wp1.lock() << endl;

END // object 'shr' is destroyed
cout << wp1.lock() << endl; // weak pointer is expired

Output:
(line breaks and line indents were modified for better readability)




{


  {

    deleting 'uni'
  }


  {

  }
  00000000003DFAF0
  deleting 'shr'
}
0000000000000000

5 Smart Pointers: Implementation Considerations

5.1 Godot Smart Pointers

Object
- Base class for most Godot classes
RefCounted
- Base class for reference counted objects
- Intruder that holds the reference count and does the actual counting
Ref
- Smart Pointer implementation that associates instances of RefCounted
- Overloads operators needed to mimic pointer syntax and semantics
WeakRef
- Can hold a RefCounted without contributing to the reference counter

5.2 Thread Safety

Important: Even a simple increment operation, e.g. i++, is subject to data races! Internally, the CPU does three steps: load, increment, and store.

Atomic types are free from data races
Allow lockless concurrent programming
If one thread writes to an atomic while another thread reads from it, the behavior is well-defined.

75%

#include <atomic>

struct AtomicCounter
{ 
  atomic_uint value;
  
  void increment() { ++value; }
  void decrement() { --value; }

  unsigned int get() const { return value.load(); }
};

// thread safe
AtomicCounter ac = { 0 };
ac.increment(); PRINT(ac.get());
ac.decrement(); PRINT(ac.get());

Godot's `SafeRefCount`

// core/object/ref_counted.h

class SafeRefCount {
  SafeNumeric<uint32_t> count;
// ...
}

template <class T>
class SafeNumeric {
  std::atomic<T> value;

// ...
public:
  // ...
  T increment() {
    return value.fetch_add(1, std::memory_order_acq_rel) + 1;
  }

  // Returns the original value instead of the new one
  T postincrement() {
    return value.fetch_add(1, std::memory_order_acq_rel);
  }

  T decrement() {
    return value.fetch_sub(1, std::memory_order_acq_rel) - 1;
  }
// ...
}

5.3 Mutable Members

mutable members: can be changed inside const member functions
- This can be useful for counting the number of accesses or allowing reference counting, for example

// example taken from http://msdn.microsoft.com/en-us/library/4h2h0ktk.aspx
class X
{
public:
  bool GetFlag() const
  {
    m_accessCount++;
    return m_flag;
  }
//private:
  bool m_flag;
  mutable int m_accessCount;
};

int _tmain(int argc, _TCHAR* argv[])
{
  const X x;
  x.GetFlag();
  x.GetFlag();
  x.GetFlag();
  printf("%i\n", x.m_accessCount); // output: 3
  return 0;
}

Use of Mutable Members in Godot

Godot uses mutable, for example, in its Variant containers Array and Dictionary in order to...
- make reference counting possible, even in const member functions
- optionally have read-only variations of the containers

// core/variant/array.h

class Array {
  mutable ArrayPrivate *_p;
  void _unref() const;

public:
  void _ref(const Array &p_from) const;

  Variant &operator[](int p_idx);
  const Variant &operator[](int p_idx) const;

  // ...
  void make_read_only();
  bool is_read_only() const;

  // ...
  Array();
  ~Array();
};

// core/variant/array.cpp

class ArrayPrivate {
public:
  SafeRefCount refcount;
  Vector<Variant> array;
  Variant *read_only = nullptr;
  ContainerTypeValidate typed;
};

void Array::_ref(const Array &p_from) const {
  ArrayPrivate *_fp = p_from._p;
  // ...
  bool success = _fp->refcount.ref();  // Radicke: ref() is not const
  // ...
  _unref();
  _p = _fp;
}

void Array::_unref() const {
  //...
  if (_p->refcount.unref()) {  // Radicke: unref() is not const
    // ...
  }
  _p = nullptr;
}

// ...
Array::Array() {
  _p = memnew(ArrayPrivate);
  _p->refcount.init();
}

Array::~Array() {
  _unref();
}

5.4 Using Pre-Allocated Memory

Placement new: constructs an object on a pre-allocated buffer
- This is required because reference counted objects typically overload the operators new and delete

class A
{
public:
  A() { printf("constructed\n"); }
  ~A() { printf("destructed\n"); }
  void* operator new(size_t size) // regular new
  { 
    printf("regular new\n");
    return ::new char[sizeof(A)];
  }
  void* operator new(size_t size, void* pWhere) // placement new
  { 
    printf("placement new\n");
    return pWhere;
  }
};

A* pA1 = new A();
delete pA1;

void* pBuffer = malloc(sizeof(A));
A* pA2 = new (pBuffer) A();
pA2->~A();
free(pBuffer);

Output:
regular new
constructed
destructed
placement new
constructed
destructed

Godot's memnew is used to hook into its custom memory management system
- There, the allocation and the call of placement new are done separately

// core/object/ref_counted.h

template <class T>
class Ref {
// ...
  void instantiate() {
    ref(memnew(T));
  }
// ...
};

6 Handles (aka Weak Pointers)

A handle is basically an integer index into a global handle table.
- The handle table, contains pointers to the referred objects
- The pointers can be updated without affecting the handles
- Handles can be invalidated when the respective pointer is deleted
- Handles support relocation of pointers or memory blocks

6.1 Handle Indices and Validation

Problem: Old invalid handles can index to newly occupied entries in the pointer table

80%

Solution: Unique Ids for the handles (hash value or counter)

80%

6.2 Handle Indices: bit-fields

It can be beneficial, to combine the handle index and the hash into a single number using bit-fields.

union HandleIdx
{ 
  struct
  {
    unsigned int index : 24; // bit field: 24 bits are used
    unsigned int hash  : 8;  // bit field: 8 bits are used
  };
  unsigned int both;         // 24 + 8 = 32 bits in total
};

// compile-time assertion checking
static_assert(sizeof(HandleIdx) == 4, "HandleIdx should be 4 bytes in size");

HandleIdx h1 = { 0, 128 };
HandleIdx h2 = { 1, 129 };
HandleIdx h3 = { 1, 130 };

cout << (h1.index == h2.index) << endl; // false
cout << (h1.both == h2.both )  << endl; // false

cout << (h1.index == h3.index) << endl; // false
cout << (h1.both == h3.both )  << endl; // false

cout << (h2.index == h3.index) << endl; // true
cout << (h2.both == h3.both )  << endl; // false

6.3 Godot Handles

// core/object/ref_counted.h

class WeakRef : public RefCounted {
// ...
  ObjectID ref;

// ...
public:
  Variant get_ref() const;
  void set_obj(Object *p_object);
  void set_ref(const Ref<RefCounted> &p_ref);

  WeakRef() {}
};

// core/object/ref_counted.cpp

Variant WeakRef::get_ref() const {
  // ...
  Object *obj = ObjectDB::get_instance(ref);
  if (!obj) { return Variant(); }
  // ...
  return obj;
}

void WeakRef::set_obj(Object *p_object) {
  ref = p_object ? p_object->get_instance_id() : ObjectID();
}
void WeakRef::set_ref(const Ref<RefCounted> &p_ref) {
  ref = p_ref.is_valid() ? p_ref->get_instance_id() : ObjectID();
}

// core/object/object_id.h

class ObjectID {
  uint64_t id = 0;

public:
  bool is_ref_counted() const {
    return (id & (uint64_t(1) << 63)) != 0;
  }
  bool is_valid() const { return id != 0; }
  bool is_null() const { return id == 0; }
  
  // ...
  ObjectID() {}
  explicit ObjectID(const uint64_t p_id) { id = p_id; }
  explicit ObjectID(const int64_t p_id) { id = p_id; }
};

// core/object/object.h

class Object {
// ...
  ObjectID _instance_id;
// ...
};

class ObjectDB {
// ...
  struct ObjectSlot { // 128 bits per slot.
    uint64_t validator : OBJECTDB_VALIDATOR_BITS;       // Radicke: 39
    uint64_t next_free : OBJECTDB_SLOT_MAX_COUNT_BITS;  // Radicke: 24
    uint64_t is_ref_counted : 1;
    Object *object = nullptr;
  };

  // ...
  static ObjectSlot *object_slots;  // Radicke: handle index table
  // ...
  friend class Object;
  // ...
  // Radicke: finds a slot, makes an entry and creates an ObjectID
  static ObjectID add_instance(Object *p_object);
  // Radicke: removes the object from its slot
  static void remove_instance(Object *p_object);
  //...
}