Статическое выделение памяти

В обсуждении проблем безопасности памяти возникла интересная тема: объектные пулы чем-то напоминают помеченные объединения (tagged unions), где метка — это информация о том, какой объект в данный момент занимает конкретную ячейку памяти. Тип системы никак не отслеживает эту метаинформацию. Это проблема, которая на первый взгляд похожа на ошибку use-after-free: заказ был освобождён и возвращён в пул, но оставался связанным в ценовом уровне, так что следующее выделение памяти отдало эту область другому заказу, и старая ссылка продолжала указывать на уже переназначенную память.

Однако здесь стоит различать логическую ошибку и её физический эффект. Если не использовать пул объектов, а просто выделять и освобождать память через malloc и free, логическая ошибка use-after-free превращается в путаницу типов: два объекта разных типов могут занимать одну и ту же область памяти. Это легко может привести к уязвимости — например, управляемое пользователем целое число в одном объекте может оказаться указателем функции в другом.

При использовании объектного пула, хранящего список "мёртвых" объектов одного типа T, логическая ошибка всё ещё возможна, но физический эффект совсем другой. Память по-прежнему становится разделяемой, но путаницы типов нет. Невозможно просто изменить целое число и повлиять на указатель функции (если, конечно, объект не содержит встроенное перечисление). Результат будет вполне определённым и детерминированным, даже если это не совсем то, что хотелось.

Отсюда вытекает интересный подход к упрочнению кода, который подсказал проект Fil. Если функция выделения памяти типизирована (принимает параметр типа T или свидетельство типа, а не просто размер и выравнивание), можно написать распределитель, использующий внутренне пулы, разделённые по типам. Это будет несколько менее эффективно по памяти — распределитель не сможет переиспользовать освобождённую память объекта типа U для объекта типа T, но накладные расходы памяти будут незначительны, а улучшение локальности памяти может оказать положительный эффект. Встроенные перечисления остаются проблемой, но если их всегда выделять в heap, это решается. C не позволяет это сделать из-за нетипизированного интерфейса выделителя памяти, но другие языки могут.

Но это скорее теория. Как же на практике избежать таких багов? Обобщающие индексы (generational indices) — популярный способ, но есть и другие подходы. Вот два приёма из TigerStyle, которые могут помочь в разработке надёжного кода, подобного системе сопоставления заказов.

Первый принцип — это:

Никакого динамического выделения памяти после инициализации

Это идея пула объектов, доведённая до логического завершения. Максимальное количество заказов, с которыми система готова работать, задаётся при запуске, и этот лимит никогда не превышается. Программа может быть запущена так:

$ order-engine --orders-max=1_000_000

А в функции main одна из первых строк будет:

const orders: []Order = try gpa.alloc(Order, cli_args.orders_max);

Если во время работы поступит больше orders_max запросов, лишние будут отклонены. Кто-то может возразить: "Но что если у меня есть свободная память для ещё одного заказа? Не стоит ли попробовать его обработать?"

Ответ прост: "А что если нет?" Системы, работающие на пределе возможностей без чётких лимитов, выходят из строя катастрофически. Попытка выделить память для одного дополнительного заказа может вызвать OOM killer на уровне ядра, который убьёт весь механизм сопоставления заказов и потеряет все остальные миллионы заказов. Или того хуже — убьёт процесс надзора, так что систему даже невозможно будет перезагрузить.

Статическое выделение памяти даёт душевное спокойствие. Система может не запуститься, если памяти недостаточно, но если она всё же запустилась, можно быть уверенным, что она справится с перегрузкой элегантно, продолжая обслуживать запросы, пока идёт проверка возможности масштабирования на более мощную машину.

Константная работа

Что делать с массивом заказов? Один из подходов — инициализировать пул объектов с помощью битовых масок:

const OrderPool = struct {
    orders: []Order,
    free: DynamicBitSet,

    fn acquire(pool: *OrderPool) ?*Order { ... }
    fn release(pool: *OrderPool, order: *Order) { ... }
};

Или с использованием свободного списка:

const OrderPool = struct {
    orders: []union {
        order: Order,
        next_free: ?u32,
    },
    first_free: ?u32,
};

Но есть альтернативный подход. Вместо лимита на количество заказов можно спроектировать систему так, чтобы всегда было ровно фиксированное количество заказов, введя нейтральный, пустой заказ:

const Order = {
    id: u128,
    price: u32,
    count: u32,

    tag: enum { bid, ask, reserved },

    pub const reserved: Order = .{
        .id = 0,
        .price = 0,
        .count = 0,
        .tag = .reserved,
    };
};

Инициализация тогда становится просто @memset(orders, .reserved).

Этот подход даёт несколько преимуществ. Прежде всего, это когнитивное преимущество. Перестаёшь думать в терминах создания и уничтожения заказов. Заказы просто циркулируют в системе в соответствии с законом сохранения количества заказов. Гораздо сложнее потерять заказ, если постоянно обращать внимание не только на то, куда он идёт, но и откуда он пришёл. Функции переходов между состояниями пишутся для каждой пары состояний, что облегчает исчерпывающее перечисление всех случаев. И можно на каждом этапе проверять утверждения о том, что состояние именно такое, как ожидается (а затем убирать эти проверки через мёртвый код).

Второе преимущество — упрощение кода и предсказуемость. Больше не нужно отслеживать отдельную коллекцию "живых" заказов. Просто всегда итерируешь полный набор, пропуская зарезервированные. Это кажется неэффективным: разве не стоит оптимизировать код на случай, когда активных заказов мало? Но вспомни: задав лимит заказов заранее, ты обязуешься быть способным обслуживать это количество. Если максимальное количество заказов активно, может ли система иметь приемлемую производительность? Если нет — это баг! Серая деградация (система становится непригодной для использования) — это другой способ отказа при достижении лимита.

Избегание индексов улучшает производительность при максимальной нагрузке. Такой код:

for (orders) |order| {
    process(order)
}

гораздо легче компилятору векторизовать и процессору предварительно загружать в cache, чем этот:

for (orders_active) |order_index| {
    const order = orders[order_index];
    process(order);
}

Подобно статическому выделению памяти, принцип Константной работы даёт уверенность в производительности. Latency P100 остаётся плоским независимо от нагрузки. Недостаточная производительность обнаруживается при развёртывании системы, а не в пятницу перед Чёрной пятницей.

В TigerBeetle этот паттерн применяется и в малом масштабе. Вместо поиска с ранним выходом:

const item = for (items) |item| {
    if (predicate(item)) break item;
} else null;

иногда разрешают цикл полностью пройти сквозь все элементы, дополнительно утверждая, что найдется ровно один подходящий элемент:

https://github.com/tigerbeetle/tigerbeetle/blob/0.17.9/src/vsr/grid.zig#L715-L725

Как обычно, это один из приёмов, полезный в арсенале разработчика, но не универсальное решение для всех проблем программирования.