Что такое refcounter и зачем он нужен
Когда программа работает с объектами динамически (через “malloc”, “new”, всякие фабрики и т.п.), рано
или поздно возникает вопрос:
А когда, собственно, объект можно безопасно удалить?
В однозадачном коде ответ простой: удаляем там, где он больше не нужен и для решения этой задачи
часто применяют refcounter (reference counter).
Refcounter - это счётчик, связанный с объектом/структурой (обычно это член структуры (Си) или класса (Си++)) и показывающий,
сколько “пользователей” сейчас используют этот объект.
На refcounters реализованы “shared_ptr” в Си++, например, поэтому, если вы пишете на Си++, то используйте “shared_ptr”. Читать дальше можно или из академического интереса или в попытке сделать чуть быстрее, чем уже сделано 
Идея очень простая:
- объект создаётся с “ref = 1”
- каждый новый пользователь объекта делает “ref++”
- когда пользователь закончил работу - делает “ref–”
- когда “ref” становится равным 0, объект удаляется
Объект будет жить, пока он кому-то нужен
Примерчик (одна задача, одно ядро). Примерчик на Си, хотя на Си++ все это было бы компактнее и проще.
struct Object {
int ref;
int data;
};
void addref(struct Object *o) {
o->ref++;
}
void unref(struct Object *o) {
o->ref--;
if (o->ref == 0)
free(o);
}
Это простой, базовый код, который можно усложнить, добавив, например, выбор деструктора для удаления вместо стандартного free()
Пока “ref > 0” - объект существует, а вот когда последний пользователь вызывает
“unref()” - память освобождается. И в одной задаче все прекрасно работает.
В многозадачном коде всё чуть усложняется из-за того, что объект может использоваться несколькими
задачами одновременно. Что произойдет, если одна задача вызовет ref++ тогда как вторая задача вызовет ref–?
Что, если ref-- выполнится раньше и вызовет удаление объекта, а другая задача будет делать obj->ref++ не подозревая,
что указатель на объект уже мертвенький?
Обычно тут говорят: “давайте сделаем mutex или semaphore, который и будет нас защищать”. И так и делают, и работает:
struct Object {
int ref;
int data;
mutex_t mux;
};
void addref(struct Object *o) {
mutex_acquire(o->mux);
o->ref++;
mutex_release(o->mux);
}
void unref(struct Object *o) {
mutex_acquire(o->mux);
o->ref--;
if (o->ref == 0)
free(o);
mutex_release(o->mux);
}
Мутекс тут не только защищает переменную →ref, но и выполняет важную функцию - дожидается отложенных записей в память сделаных разными ядрами. Но все это скрыто от глаз программиста. Что произойдет теперь, если две задачи попытаются одновременно сделать ref– и ref++? Одна из задач успеет захватить мутекс а вторая - повиснет на этом мутексе. Шедулер операционки (FreeRTOS) поместит задачу повисшую на мутексе в список приостановленных задач и переключится на следующую. Задач будет заблокирована минимум на несколько тиков операционной системы (1 тик = 1 миллисекунда).
А можно без мутексов? Без блокировок задач, без всего вот этого?
Можно. Все с теми же нашими любимыми атомиками
Если несколько задач на нескольких ядрах одновременно увеличивают и уменьшают счётчик, операции типа “++” и “–”
становятся неоднозначными. Поэтому сам счетчик сделаем атомарным:
#include <stdatomic.h>
typedef _Atomic(unsigned int) refc_t; // в Си++ см. std::atomic и всякие atomic<unsigned int>
// Какой-то объект со счетчиком ссылок и мембером data
struct Object {
refc_t ref;
int data;
};
Теперь исправим addref() и unref() так, чтобы доступ к ->ref был атомарным:
// Увеличить счетчик ссылок r на 1.
// Возвращает true = можно работать с объектом
// Возвращает false = объект уже умер, пока вы делали addref(), объектом пользоваться нельзя
//
bool addref(refc_t *r) {
// Загружаем текущее значение счетчика ссылок в ref
unsigned int ref = atomic_load_explicit(r, memory_order_relaxed);
// Проверяем, что (ref + count) <= 2^32
if (ref == (unsigned int )(-1))
abort();
// Пытаемся увеличить r на единичку, достаточно упорно.
do {
// Если ref в какой-то момент упадет до нуля, значет объект
// умер, пока мы пытались прибавить единичку.
if (ref < 1)
return false;
} while (!atomic_compare_exchange_weak_explicit(
r, // куда писать
&ref, // ..только если значение не поменялось
ref + 1, // что писать
memory_order_acquire,
memory_order_relaxed));
// Ура. Счетчик увеличен, объектом можно пользоваться
return true;
}
// Уменьшение счетчика ссылок на единичку
// и удаление объекта, если счетчик равен нулю. Можно добавить еще один аргумент - деструктор.
// Ну или переписать на Си++
//
void unref(refc_t *r, void *object) {
// Уменьшаем счетчик на 1. Если он и был 1 до этого, то
if (atomic_fetch_sub_explicit(r, 1, memory_order_release) == 1) {
// дожидаемся всех отложенных записей в object
atomic_thread_fence(memory_order_acquire);
// теперь удаляем
free(object);
}
}
Типичный шаблон использования выглядит так:
if (addref(&obj->ref)) {
// безопасно работаем с объектом
...
unref(&obj->ref, obj);
}
или
// посылаем объект куда-то. получатель удалит объект вызовом unref()
if (addref(&obj->ref)) {
send_object_to_task1(obj);
}
Тадам. Получилось отложенное удаление без блокировок :). Простенькое, но кому надо - тот сам добавит фичи по вкусу.
Не уверен, что кому-то пригодится, но кто его знает. Если будете писать сетевые драйвера или ковырять tcp/ip стек - пригодится.
Там все пакеты данных со счетчиками