«Простота — высшая степень утончённости», — Леонардо да Винчи

Оглавление

Глава 1: Разрыв в производительности

Глава 2: Иерархия памяти

Глава 3: Бенчмаркинг и профилирование

Глава 4: Массивы и локальность кэша

Глава 5: Связанные списки — убийцы кэша

Глава 6: Стеки и очереди

Глава 7: Хэш-таблицы и конфликты кэша

Глава 8: Динамические массивы и управление памятью

Глава 9: Двоичные деревья поиска

Глава 10: B-деревья и деревья, эффективно использующие кэш

Глава 11: Префиксные деревья и базисные деревья

Глава 12: Кучи и очереди с приоритетом

Глава 13: Структуры данных без блокировок

Глава 14: Обработка строк и эффективность использования кэша

Глава 15: Графы и их обход с эффективным использованием кэша

Глава 16: Фильтры Блума и вероятностные структуры данных

Глава 17: Структуры данных загрузчиков

Дедлайн в 500 миллисекунд

Наш загрузчик оказался слишком медленным. Требование было чётким: загружаться менее чем за 500 миллисекунд. Показатели оставались не менее чёткими: 720 миллисекунд. Мы отставали от нужного значения на 44%.

Это требование не было «мягким». Загрузчик должен был работать в промышленном контроллере, обязанном реагировать вскоре после включения питания. Каждая секунда времени загрузки — это потерянная продуктивность. В спецификации к изделию был указан максимум в 500 мс. Мы обязаны были их обеспечить.

Задача загрузчика была простой:

1. Инициализировать оборудование (UART, SPI, DDR-контроллер)

2. Загрузить ядро из флэш-памяти

3. Спарсить дерево устройств

4. Перейти ко точке входа ядра

Реализация казалась логичной: стандартные структуры данных из библиотеки C:

// Парсинг дерева устройств при помощи связанных списков, выделенных malloc
typedef struct dt_node {
    char *name;
    struct dt_node *parent;
    struct dt_node *children;  // Связанный список
    struct dt_node *next;
    property_t *properties;    // Связанный список
} dt_node_t;

dt_node_t *parse_device_tree(void *fdt) {
    dt_node_t *root = malloc(sizeof(dt_node_t));
    // Парсинг FDT, распределение узлов при помощи malloc...
}

Показания времени загрузчика:

$ ./bootloader
[0.000] Start
[0.120] Hardware init complete
[0.450] Device tree parsed (2,847 malloc calls)
[0.680] Kernel loaded
[0.720] Jump to kernel

Total boot time: 720 ms

Проблема выявилась при профилировании:

$ perf record -e cycles ./bootloader
$ perf report

  45.2%  malloc/free
  28.3%  Device tree parsing
  15.8%  Flash I/O
  10.7%  Other

45% времени загрузки тратилось на malloc/free! В загрузчике всего с 64 КБ ОЗУ динамическое распределение роняло производительность.

Я переписал загрузчик на основе статических, удобных для кэша структур данных. Результаты:

$ ./bootloader_optimized
[0.000] Start
[0.115] Hardware init complete
[0.210] Device tree parsed (0 malloc calls)
[0.380] Kernel loaded
[0.420] Jump to kernel

Total boot time: 420 ms

420 мс — показатели лучше, чем 500 мс, на 16%!

Среда загрузчика

Загрузчики выполняются в средах с ограничениями:

1. Малый объём памяти

Типичные ограничения:

• SRAM: 64-256 КБ (до инициализации DDR)

• Отсутствие распределителя кучи (или очень простой)

• Стек: 4-16 КБ

Вывод: malloc/free невозможно использовать свободно. Необходимо применить статическое распределение или простой bump allocator.

2. Отсутствие стандартной библиотеки

Чего нет:

• printf (до инициализации UART)

• malloc/free (или они очень простые)

• файлового ввода-вывода

• многопоточности

Вывод: необходимо реализовать их минимальные версии или полностью отказаться от них.

3. Критичность производительности

Почему это важно:

• Время загрузки непосредственно ощущается пользователем

• Чем быстрее загрузка, тем выше удобство для пользователя

• В некоторых системах есть жёсткие ограничения времени загрузки (автомобилестроение, промышленность)

Вывод: важна каждая миллисекунда. Необходимо использовать удобные для кэша структуры данных.

4. Однопоточность

Упрощение:

• Не требуется блокировка

• Отсутствуют состояния гонок

• Более простые структуры данных

---

Что нам рассказывают в учебниках

Загрузчики — это «простые» программы, которые всего лишь:

1. Инициализируют оборудование

2. Загружают ядро

3. Выполняют переход к ядру

Можно использовать в них любые удобные вам структуры данных.

---

Проверка реальностью: почему стандартные решения терпят неудачу

1. malloc/free слишком медленные

В нашем загрузчике malloc/free занимали 45% времени загрузки:

// Распределение каждого узла: ~200 тактов
dt_node_t *node = malloc(sizeof(dt_node_t));  // 200 тактов
node->name = malloc(strlen(name) + 1);        // 200 тактов
node->properties = malloc(sizeof(property_t)); // 200 тактов

Для 2847 распределений: 2847 × 200 = 569400 тактов на одну лишь malloc!

При частоте 1,2 ГГц: 569400 / 1200000 = 0,47 мс потрачено на распределение.

2. Следование по указателям убивает кэш

Обход дерева устройств при помощи связанных списков:

// Посещаем все дочерние узлы
for (dt_node_t *child = node->children; child; child = child->next) {
    process(child);  // Промах кэша для каждого дочернего узла!
}

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

3. Фрагментация в малом объёме памяти

При всего 64 КБ SRAM фрагментация убийственна:

После 1000 распределений/free:
  Общее свободное пространство: 32 КБ
  Наибольший сплошной блок: 4 КБ
  
Невозможно распределить буфер на 8 КБ для загрузки ядра!

---

Решение 1: Bump Allocator

Для загрузчиков достаточно простого bump allocator:

#define HEAP_SIZE (32 * 1024)  // Куча размером 32 КБ

typedef struct {
    uint8_t heap[HEAP_SIZE];
    size_t offset;
} bump_allocator_t;

static bump_allocator_t g_allocator = {0};

void *boot_alloc(size_t size) {
    // Выравнивание по 8 байтам
    size = (size + 7) & ~7;
    
    if (g_allocator.offset + size > HEAP_SIZE) {
        return NULL;  // Закончилась память
    }
    
    void *ptr = &g_allocator.heap[g_allocator.offset];
    g_allocator.offset += size;
    return ptr;
}

void boot_alloc_reset(void) {
    g_allocator.offset = 0;  // Сброс всей кучи
}

Преимущества:

• Скорость: достаточно инкремента смещения (5 тактов против 200 тактов в случае malloc)

• Отсутствие фрагментации: распределения непрерывны

• Простота: 10 строк кода

• Предсказуемость: отсутствие скрытой сложности

Ограничение: невозможность освобождения отдельных распределений (только сброс всей кучи).

Почему это нормально: у загрузчиков есть этапы. После парсинга дерева устройств можно просто выполнить сброс кучи для загрузки ядра.

Бенчмарк

Тест: 2847 распределений (парсинг дерева устройств)

malloc/free:
  Такты: 569400
  Время: 0,47 мс
  Фрагментация: 18 КБ потрачено впустую
  
Bump allocator:
  Такты: 14235 (в 40 раз быстрее!)
  Время: 0,012 мс
  Фрагментация: 0 КБ
  
Ускорение: 40×

---

Решение 2: плоское дерево устройств

Вместо узлов дерева, распределяемых malloc, можно использовать плоский массив:

#define MAX_DT_NODES 512

typedef struct {
    char name[32];
    uint16_t parent_idx;
    uint16_t first_child_idx;
    uint16_t next_sibling_idx;
    uint16_t num_properties;
    property_t properties[8];  // Встроенные, указатель не нужен
} dt_node_flat_t;

typedef struct {
    dt_node_flat_t nodes[MAX_DT_NODES];
    int num_nodes;
} device_tree_t;

static device_tree_t g_dt;  // Статическое распределение, без malloc

int dt_add_node(const char *name, int parent_idx) {
    if (g_dt.num_nodes >= MAX_DT_NODES) {
        return -1;  // Слишком много узлов
    }
    
    int idx = g_dt.num_nodes++;
    dt_node_flat_t *node = &g_dt.nodes[idx];
    
    strncpy(node->name, name, sizeof(node->name) - 1);
    node->parent_idx = parent_idx;
    node->first_child_idx = 0xFFFF;  // Дочерние узлы пока отсутствуют
    node->next_sibling_idx = 0xFFFF;
    node->num_properties = 0;
    
    // Ссылка на родителя
    if (parent_idx >= 0) {
        dt_node_flat_t *parent = &g_dt.nodes[parent_idx];
        if (parent->first_child_idx == 0xFFFF) {
            parent->first_child_idx = idx;
        } else {
            // Поиск последнего узла того же уровня
            int sibling_idx = parent->first_child_idx;
            while (g_dt.nodes[sibling_idx].next_sibling_idx != 0xFFFF) {
                sibling_idx = g_dt.nodes[sibling_idx].next_sibling_idx;
            }
            g_dt.nodes[sibling_idx].next_sibling_idx = idx;
        }
    }
    
    return idx;
}

Преимущества:

• Отсутствие malloc: все узлы находятся в одном статическом массиве

• Удобство для кэша: последовательный доступ к узлам

• Предсказуемый объём памяти: во время компиляции можно точно знать используемую память

• Быстрый обход: индексация массива вместо следования по указателям

Бенчмарк

Тест: парсинг дерева устройств (347 узлов, 1245 свойств)

Связанный список, распределённый malloc:
  Такты: 2,8 миллиона
  Промахи кэша: 185 тысяч
  Память: 64 КБ (фрагментированная)
  Время: 2,3 мс

Плоский массив:
  Такты: 0,45 миллиона
  Промахи кэша: 12 тысяч
  Память: 48 КБ (непрерывная)
  Время: 0,38 мс

Ускорение: 6,1×
Снижение количества промахов кэша: 15,4×

---

Решение 3: кольцевой буфер для лога загрузки

Для отладки загрузчикам нужны сообщения логов, но printf невозможно использовать до инициализации UART.

Проблема

Стандартное решение: буферизация сообщений в связанный список, последующий вывод.

typedef struct log_entry {
    char message[128];
    struct log_entry *next;
} log_entry_t;

log_entry_t *log_head = NULL;

void boot_log(const char *msg) {
    log_entry_t *entry = malloc(sizeof(log_entry_t));
    strncpy(entry->message, msg, 127);
    entry->next = log_head;
    log_head = entry;
}

Недостатки:

• malloc для каждого сообщения лога

• Следование по указателям при выводе

• Неограниченное использование памяти

Решение: статический кольцевой буфер

#define LOG_BUFFER_SIZE 4096
#define MAX_LOG_ENTRIES 64

typedef struct {
    char buffer[LOG_BUFFER_SIZE];
    uint16_t offsets[MAX_LOG_ENTRIES];
    int head;
    int tail;
    int count;
} boot_log_t;

static boot_log_t g_log = {0};

void boot_log(const char *msg) {
    int len = strlen(msg);
    if (len >= LOG_BUFFER_SIZE) {
        len = LOG_BUFFER_SIZE - 1;
    }

    // Проверка наличия места в буфере
    int next_tail = (g_log.tail + len + 1) % LOG_BUFFER_SIZE;
    if (next_tail == g_log.head && g_log.count > 0) {
        // Буфер заполнен, стираем самое старое сообщение
        g_log.head = (g_log.head + strlen(&g_log.buffer[g_log.head]) + 1) % LOG_BUFFER_SIZE;
        g_log.count--;
    }

    // Копирование сообщения
    g_log.offsets[g_log.count % MAX_LOG_ENTRIES] = g_log.tail;
    for (int i = 0; i < len; i++) {
        g_log.buffer[g_log.tail] = msg[i];
        g_log.tail = (g_log.tail + 1) % LOG_BUFFER_SIZE;
    }
    g_log.buffer[g_log.tail] = '\0';
    g_log.tail = (g_log.tail + 1) % LOG_BUFFER_SIZE;

    g_log.count++;
    if (g_log.count > MAX_LOG_ENTRIES) {
        g_log.count = MAX_LOG_ENTRIES;
    }
}

void boot_log_print(void) {
    for (int i = 0; i < g_log.count; i++) {
        uart_puts(&g_log.buffer[g_log.offsets[i]]);
    }
}

Преимущества:

• Отсутствие malloc: буфер фиксированного размера

• Границы использования памяти: 4 КБ + 128 байт

• Скорость: отсутствие оверхеда на распределение

• Автоматическая обработка переполнения: удаление самых старых сообщений

---

Решение 4: таблица конфигурации, создаваемая на этапе компиляции

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

Проблема

Парсинг в среде исполнения:

void init_uart(void) {
    // Парсинг дерева устройств для нахождения конфигурации UART
    dt_node_t *uart = dt_find_node("/soc/uart@10000000");
    uint32_t base = dt_get_property_u32(uart, "reg");
    uint32_t baud = dt_get_property_u32(uart, "baud-rate");

    // Инициализация UART
    uart_init(base, baud);
}

Недостатки:

• Парсинг дерева устройств во время загрузки

• Сравнение строк для поиска узлов

• Множественные операции доступа к памяти

Решение: таблица этапа компиляции

// Генерируется из дерева устройств на этапе компиляции
typedef struct {
    uint32_t base;
    uint32_t baud;
    uint32_t irq;
} uart_config_t;

static const uart_config_t g_uart_config = {
    .base = 0x10000000,
    .baud = 115200,
    .irq = 10,
};

void init_uart(void) {
    // Непосредственный доступ, парсинг не требуется
    uart_init(g_uart_config.base, g_uart_config.baud);
}

Преимущества:

• Нулевой оверхед в среде исполнения: парсинг отсутствует

• Типобезопасность: типы проверяет компилятор

• Удобство для кэша: вся конфигурация в одной структуре

• Скорость: прямой доступ к памяти

Бенчмарк

Тест: инициализация 8 периферийных устройств (UART, SPI, I2C, GPIO и так далее)

Парсинг дерева устройств в среде исполнения:
  Такты: 1,2 миллиона
  Промахи кэша: 85 тысяч
  Время: 1,0 мс

Таблица конфигурации, генерируемая на этапе компиляции:
  Такты: 45 тысяч
  Промахи кэша: 2 тысячи
  Время: 0,038 мс

Ускорение: 26,7×

---

Пример из реального мира: FDT (Flattened Device Tree) загрузчика U-Boot

В U-Boot (Universal Bootloader) для деревьев устройств используется хитрое представление.

Формат FDT

FDT — это плоский двоичный блоб, а не дерево распределённых malloc узлов:

FDT Header (40 bytes):
  magic: 0xd00dfeed
  totalsize: size of entire blob
  off_dt_struct: offset to structure block
  off_dt_strings: offset to strings block

Structure Block:
  FDT_BEGIN_NODE "/"
    FDT_PROP "compatible" → offset to "vendor,board"
    FDT_BEGIN_NODE "cpus"
      FDT_BEGIN_NODE "cpu@0"
        FDT_PROP "device_type" → offset to "cpu"
        FDT_PROP "reg" → 0x00000000
      FDT_END_NODE
    FDT_END_NODE
  FDT_END_NODE

Strings Block:
  "vendor,board\0"
  "cpu\0"
  ...

Преимущества:

• Единственное распределение: всё дерево находится в одном блобе

• Последовательный доступ: парсинг выполняется в процессе движения вперёд

• Компактность: устранены дубликаты строк

• Скорость: нет следования по указателям

Парсинг FDT

int fdt_next_node(const void *fdt, int offset, int *depth) {
    uint32_t tag;

    do {
        offset = fdt_next_tag(fdt, offset, &tag);

        switch (tag) {
        case FDT_BEGIN_NODE:
            (*depth)++;
            break;
        case FDT_END_NODE:
            (*depth)--;
            break;
        case FDT_PROP:
            // Пропуск свойства
            break;
        }
    } while (tag != FDT_BEGIN_NODE && tag != FDT_END);

    return offset;
}

Производительность:

Парсинг дерева устройств из 500 узлов:

Дерево malloc:
  Время: 3,5 мс
  Память: 128 КБ
  Промахи кэша: 250 тысяч

FDT (плоское):
  Время: 0,6 мс
  Память: 24 КБ
  Промахи кэша: 18 тысяч

Ускорение: 5,8×

---

Соединяем всё вместе: оптимизированный загрузчик

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

// 1. Bump allocator для временных распределений
static bump_allocator_t g_allocator;

// 2. Flat device tree
static device_tree_t g_dt;

// 3. Кольцевой буфер для лога загрузки
static boot_log_t g_log;

// 4. Конфигурация, генерируемая на этапе компиляции
static const hw_config_t g_hw_config = {
    .uart = { .base = 0x10000000, .baud = 115200 },
    .spi = { .base = 0x10001000, .freq = 50000000 },
    // ...
};

void bootloader_main(void) {
    uint64_t start = read_cycle_counter();

    // Этап 1: инициализация оборудования (используется конфигурация, сгенерированная на этапе компиляции)
    boot_log("Initializing hardware...");
    init_uart(&g_hw_config.uart);
    init_spi(&g_hw_config.spi);
    // ... другие периферийные устройства

    uint64_t hw_init_done = read_cycle_counter();

    // Этап 2: парсинг дерева устройств (в плоском виде)
    boot_log("Parsing device tree...");
    parse_fdt(&g_dt, (void *)FDT_BASE_ADDR);

    uint64_t dt_done = read_cycle_counter();

    // Этап 3: загрузка ядра (для буферов используется bump allocator)
    boot_log("Loading kernel...");
    void *kernel_buf = boot_alloc(KERNEL_SIZE);
    load_kernel_from_flash(kernel_buf, KERNEL_SIZE);

    uint64_t kernel_loaded = read_cycle_counter();

    // Вывод лога загрузки
    boot_log_print();

    // Вывод таймингов
    uart_printf("Hardware init: %llu cycles\n", hw_init_done - start);
    uart_printf("Device tree:   %llu cycles\n", dt_done - hw_init_done);
    uart_printf("Kernel load:   %llu cycles\n", kernel_loaded - dt_done);
    uart_printf("Total:         %llu cycles\n", kernel_loaded - start);

    // Переход к ядру
    jump_to_kernel(kernel_buf);
}

Окончательный бенчмарк

Тест: загрузка системы на RISC-V (1,2 ГГц)

Изначальная (malloc, связанные списки, парсинг во время исполнения):
  Инициализация оборудования: 144 миллиона тактов (120 мс)
  Дерево устройств:           396 миллионов тактов (330 мс)
  Загрузка ядра:              216 миллионов тактов (180 мс)
  Прочее:                     108 миллионов тактов (90 мс)
  Итого:                      864 миллионов тактов (720 мс)

Оптимизированная (bump allocator, плоские массивы, конфигурация на этапе компиляции):
  Инициализация оборудования: 138 миллионов тактов (115 мс)
  Дерево устройств:           114 миллионов тактов (95 мс)
  Загрузка ядра:              204 миллиона тактов (170 мс)
  Прочее:                      48 миллионов тактов (40 мс)
  Итого:                      504 миллиона тактов (420 мс)

Ускорение: 1,71× (720 мс → 420 мс)
Снижение времени загрузки: на 300 мс (41,7%)

---

Подведём итог

Мы уместились в 500 миллисекунд. Время загрузки упало с 720 мс до 420 мс — улучшение на 41,7% с запасом в 80 мс от требуемого. Теперь промышленный контроллер мог быстро реагировать после включения питания, соответствуя параметрам спецификации.

Основные выводы:

1. Bump allocator идеальны для загрузчиков. Они в 40 раз быстрее malloc, обеспечивают нулевую фрагментацию и состоят всего из десяти строк кода. Между этапами выполняется сброс.

2. Плоские массивы лучше связанных структур. При использовании плоского массива парсинг дерева устройств стал в 6,1 быстрее, чем при распределяемых malloc-узлах. Промахов кэша стало в 15,4 меньше.

3. Создание конфигурации на этапе компиляции избавляет от необходимости парсинга во время исполнения. Инициализация оборудования стала в 26,7 раза быстрее, чем при парсинге дерева устройств при загрузке.

4. Кольцевые буферы при логгинге просты и предсказуемы по памяти. Буфер размером 4 КБ справляется со всеми сообщениями загрузки с автоматической обработкой переполнения. При этом не требуется malloc.

5. Формат FDT великолепен. Единый блоб, последовательный доступ, отсутствие повторов строк. Он в 5,8 раза быстрее, чем дерево указателей.

Характеристики загрузчика:

• Bump allocator: в 40 раз быстрее, чем malloc

• Плоское дерево устройств: в 6,1 раза быстрее, в 15,4 раза меньше промахов кэша

• Конфигурация, генерируемая на этапе компиляции: в 26,7 раза быстрее, чем парсинг в среде исполнения

• Итого: скорость загрузки увеличилась в 1,71 раза (720 мс → 420 мс)

Загрузчикам нужны простые, предсказуемые удобные для кэша структуры данных. Избегайте malloc, избегайте указателей, используйте статическое распределение.

В следующей главе: очереди драйверов устройств — как эффективно копировать данные между оборудованием и ПО.