Введение
Типичная ситуация:
Одна часть вашего кода аллоцирует структуру (назовём её “struct gpio_config”), заполняет её поля и передаёт указатель другой части кода. Та, в свою очередь, либо сразу обрабатывает полученную информацию, либо откладывает указатель “до лучших времён” и обрабатывает его позже.
Как бы то ни было, в конце концов этот указатель попадает в “free()”, и цикл повторяется:
malloc --> free --> malloc --> free --> ...
(Ну или “new/delete”, если вы пишете на C++.)
А что если нам нужна скорость?
Представим, что у нас сотни структур аллоцируются и освобождаются в секунду. В этом случае “malloc()” начинает давать о себе знать - он не быстрый. Плюс ко всему, при частом “malloc/free” можно упереться в фрагментацию кучи.
Поэтому в быстром или высоконагруженном коде так обычно не пишут.
А как тогда пишут?
Один из популярных подходов - повторное использование памяти.
Идея простая: память выделяют один раз, а вместо освобождения кладут “освобождённый” блок в список свободных. При следующей аллокации сначала смотрят в этот список, и если он не пуст - берут блок оттуда, не вызывая “malloc()”.
Так устроена работа с памятью, например:
- в сетевом стеке FreeBSD (и производных, см. “mbuf”),
- в Linux (см. “sk_buff”),
- и даже lwIP делает что-то похожее (структура “pbuf”, если память не изменяет).
Примерно так это выглядит в псевдокоде:
// Тут мы храним ненужные структуры. Вдруг понадобятся?
static struct gpio_config *unused = NULL;
// Аллокация
//
static struct gpio_config *Get(void) {
// если список пуст - malloc, если нет - берём из списка
if (list_is_empty(unused))
return malloc(...);
else
return list_get_first_element(unused);
}
// Освобождение
//
static void Put(struct gpio_config *gc) {
list_push_item(unused, gc); // кладём в список
}
Функция “Get()” создаёт структуры, функция “Put()” их “уничтожает”. Всё красиво и просто.
Реальность подкрадывается
А теперь внезапно задача усложняется, и у нас появляется:
- несколько потоков (задач / threads);
- несколько ядер.
Возникает логичный вопрос: как синхронизироваться?
Что будет, если две задачи на разных ядрах одновременно вызовут “Put()”?
Тут обычно сразу звучат ответы:
- “Мутекс!”
- “Семафор!”
- или кто-нибудь с форума предложит “просто замаскировать прерывания” - тоже, в общем-то, синхронизация.
И да, в подавляющем большинстве случаев так и делают: вводят объект синхронизации - мутекс, семафор или критическую секцию.
Но есть нюанс
Мутексы и семафоры - не бесплатные:
- они медленные
- они потребляют память
- на FreeRTOS (ESP32) каждый мутекс/семафор - это довольно крупная структура со своей мишурой
- их нельзя захватывать из прерывания
Критическая секция работает быстро и почти не жрёт память, но выключает прерывания, что тоже далеко не всегда допустимо.
В итоге получается парадокс:
пытаясь уйти от медленного “malloc()”, мы упираемся в медленные объекты синхронизации.
А можно без всего этого?
Можно ли обойтись без мутексов и семафоров, при этом сохранив:
- корректную синхронизацию,
- высокую скорость,
- возможность работы из прерываний?
Можно.
Для этого воспользуемся атомарными операциями из стандарта C11
(любителям C++ стоит смотреть в сторону “std::atomic”, по Си++ я живу в 2007 году).
Lock-free список свободных элементов
Наш псевдокод начинает выглядеть так:
// Список неиспользуемых / освобождённых структур (LIFO)
static _Atomic(struct gpio_config *) unused = NULL;
Аллокатор
static struct gpio_config *Get(void) {
struct gpio_config *ret = NULL;
// Пытаемся забрать элемент из списка unused.
// Логика такая:
//
// if (unused != NULL) {
// ret = unused;
// unused = unused->next;
// return ret;
// }
//
do {
if (NULL == (ret = atomic_load_explicit(&unused, memory_order_relaxed)))
break;
} while (!atomic_compare_exchange_weak_explicit(
&unused,
&ret,
ret->next,
memory_order_acquire,
memory_order_relaxed));
// Если список был пуст - аллоцируем новую структуру
if (!ret)
ret = malloc(sizeof(struct gpio_config));
return ret;
}
Деаллокатор
static void Put(struct gpio_config *gc) {
// Кладём освобождаемую структуру в список unused
// Логика вставки в голову списка:
//
// gc->next = unused;
// unused = gc;
//
do {
gc->next = atomic_load_explicit(&unused, memory_order_relaxed);
} while (!atomic_compare_exchange_weak_explicit(
&unused,
&gc->next,
gc,
memory_order_release,
memory_order_relaxed));
}
Что в итоге получилось?
-
Никаких мутексов, семафоров и критических секций
-
Синхронизация достигается за счёт CAS-циклов
-
Код корректно работает:
- в многозадачном приложении\среде,
- на нескольких ядрах,
- и даже в прерывании
На основе этого кода можно написать generic-list, быстрый и без блокировок, работающий и в прерывании и где угодно.
Но это мы сделаем в следующий раз, когда будет время и желание 
Спасибо за внимание, если уж до сюда дочитали. Happy coding!