Comments 29
Уже была на Хабре похожая статья пять лет назад. Там тоже есть ссылка на GitHub и вроде даже thread-safety заявлено (не проверял, мельком увидел в статье, пока освещал ее в памяти).
Да, это перевод статьи https://lo.calho.st/posts/black-magic-buffer/, ссылка на которую приведена в тексте.
У нас немного разные сценарии. Тот мужик записывал в буфер сообщения разной длины и хотел избавиться от проверки, не вылезет ли сообщение за границы буфера. У меня сообщения (матрицы) всегда одинаковой длины. Мне нужно экономить место и операции.
Озвученная проблема:
а) нужно иметь писателя и иметь читателя(лей) для потоковых данных, приближенных к realtime
б) нужно максимально быстро переиспользовать уже прочитанную / обработанную память
в) нужно обеспечить непрерывность в памяти нескольких подряд идущих элементов размером в несколько килобайт или мегабайт
Теперь вопрос - а что мешает просто зарезервировать через mmap() (но не выделить) диапазон адресов размером в несколько терабайт (для современных 64-х битных архитектур с 48 реальными адресуемыми битами верхний предел около 128 терабайт, в реальности чуть менее). Физическая память будет выделяться (commit) при записи. Уже обработанную память - просто освобождать через madvise(MADV_DONTNEED). Быстрее в этом мире ничего нет, т.к. malloc()/free()/new/delete это просто обертки над mmap() с его commit on demand
80TB это примерно 80млн чанков размером по 1MB. А при достижении "верхнего предела" можно просто взять паузу и сделать remap() активной часть буфера в начало.
Не просто так конечно - там уже нужно будет две последовательно очень большие области, скажем по 40TB. И если наш читающий хвост переехал из первой области во вторую (т.е. первая стала полностью не нужна), то мы быстро первую отмпаливаем целиком, вторую ставим на место первой через mremap(), и еще раз делаем заново mmap() второй области с MAP_FIXED.
Linux довольно консервативен в части использования диапазонов адресов - все что не первый и не последний терабайт из адресуемых 128TB userspace - это система практически не задействует сама (heap растет снизу вверх, стек и mmap()ы без указания адреса - сверху вниз).
от ASLR сюрпризов не будет?
Насколько я знаю нет, там все достаточно предсказуемо в linux, при уровне 2. Обещают правда совсем полную рандомизацию, но пока это лишь в теории.
Большим сюрпризом там скорее магическое число 89TB, которое есть суть PIE base 0x555555554000, но оно лишь дополняет правило: не первый терабайт и не последний 128й, а да, и 89-й тоже трогать нельзя :)
а что мешает просто зарезервировать через mmap()
Да ничего не мешает. Предложение дельное. Тема для отдельного исследования с выявлением плюсов и минусов такого подхода.
Буду признателен, если поделитесь примером реализации, если имеется.
скажем по 40TB
Это вы хватанули … Буфер же не один в процессе, другим тоже должно хватать. К тому же не забывайте про динамического линковщика, который может прилинковать библиотеку в середину адресного пространства. Терабайта-два должно хватить.
Нюанс с резервированием огромного участка, как мне кажется, нужно всегда учитывать и держать в голове при проектировании и поддержании ПО, так как неизвестно, чем это аукнется в сложных системах.
В любом случае заинтересовали, буду углубляться.
40TB это я рубанул "от души" :) Но скорее с целью показать пределы масштабируемости. Считается же что 64 бит это прям очень много (18.4 экзабайт), а в реальности намного скромнее, 48 бит в общем случае, или 52/56 бит в особо крутых серверных материнках.
Но основная идея да, заключается в том, что с 64 битами адреса и возможностью манипуляций с mmap(MAP_FIXED) многие старые парадигмы управления памятью из 16-, 31-, 32- битных миров из 70-х годов как минимум могут быть пересмотрены. К примеру можно играть в арены (region memory aka memory pools), с заданными циклами жизни, и не заниматься мелкодробным free() / delete - т.е. вместо malloc() / new выделять память, просто последовательно сдвигая HWM в заранее отмпаленном регионе, прям как в Java, и лишь в конце жизненного цикла (внешнего вызова, сессии, процесса) - просто удалять этот регион целиком. Внешние ресурсы (хендлы) - собирать в linked list и удалять вместе с регионом. Про деструкторы и вовсе забыть. Идея кстати не нова, вовсю используется в APR / apache httpd и PostreSQL, образцах long-running стабильности. В виде плюшки заодно и от memory reuse с undefined behavior проблем избавиться.
Реализацией пока не поделюсь, это отдельный исследовательский проект, думаю в следующем году выложить в github/MIT. Правда вопросами кольцевых буферов в аспекте непрерывной группы чанков я не озадачивался, пока не было необходимости. Пока там в части кольцевых буферов пока лишь аналог LMAX Disruptor для сверхскоростной межпроцессной IPC на lockfree алгоритмах. Для меня самого было удивительным, что даже в offset pointer на самом деле уже и не особо надо, если для всех изолированных процессов заранее замапить буфер в строго определенный адрес - так все процессы будут иметь единую сквозную адресацию.
И т.д. :)
В 2026 году, кольцевой буфер все еще не реализован на уровне библиотек, как стандартная функция С++, отлаженная и документированная? Или такая функция отдельно не нужна, и встроена в функции более высокого уровня для работы с данными, в библиотеках для обработки данных?
Не реализован. Вместо него стандарт предписывает использовать std::deque на основе связных списков.
В 2015 было предложение добавить ring adaptor в стандартную библиотеку https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0059r0.pdf. Видимо предложение отклонили, раз адаптор так и не появился.
Или такая функция отдельно не нужна, и встроена в функции более высокого уровня для работы с данными, в библиотеках для обработки данных?
Ближайшая к std реализация — это Boost.Circular Buffer. Других проверенных реализаций я не встречал.
Наверно в стандарты это действительно нельзя включать. Неразрешенной будет ситуация, когда память уже фрагментирована, и нет непрерывного участка нужной длины. Получается что кольцевой буфер идеологически неприемлем для стандарта который ориентирован на многозадачность и динамическое выделение памяти.
Прочитал заголовок и сразу понял, о чем пойдет речь. Сам к такой идее пару лет назад пришел, только потом обнаружил, что так уже делали.
40 лет назад для такого в С++ придумали шаблоны, а затем и STL. Именно чтобы можно было сделать свой контейнер для тензоров в кольцевом буфере, у которого указатель на данные первого индекса будет вычисляться как (head_offset + i) % capacity. И чтобы всё это подставлялось и оптимизировалось во время компиляции, без виртуальных функций и т.д. Потому что кому-то хватит обычного буфера, кому-то кольцевого, а у кого-то разреженные матрицы на основе списка списков. Но увы:)
40 лет назад для такого в С++ придумали шаблоны, а затем и STL
Не улавливаю. Как это связано с темой закольцовки памяти? Если вы говорите про удобный АПИ для доступа к буферу — вопросов нет. Можно разработать свой контейнер для кольцевой структуры данных, а-ля STL. Можно взять готовый std::vector и написать ему свой аллокатор. Главное в том, что у них будет под капотом.
В статье я поднимаю капот и вижу под ним проблему хранения данных непрерывно и упорядоченно, и предлагаю механизм её решения. А какими методами взаимодействовать с данными — это уже на усмотрение каждого.
указатель на данные первого индекса будет вычисляться как (head_offset + i) % capacity
Да, реализация через std::vector со швом. Есть в статье.
без виртуальных функций
Виртуальные функции в тексте нигде не фигурируют.
Речь о том, что это должна поддерживать ваша числодробительная библиотека. Но скорее всего у неё сишный интерфейс (не шаблонный), и никаких контейнеров она не принимает. Поэтому приходится извращаться с виртуальной памятью.
Никакие темплейты вам не обеспечат возврат указателя на массив (автору нужен именно физический массив, а не нечто с operator[]), если вы этот массив не сформируете. Они просто уберут бойлерплейт.
Единственное что – можно за счёт темплейтов сделать платформенно-зависимый кусок маленьким.
Речь о том, что это должна поддерживать ваша числодробительная библиотека
А если не поддерживает? Это зависит от железа, либо проц поддерживает modulo addressing, либо нет. Процы общего назначения не поддерживают. Оптимизации компилятора это вторичное. И уж точно компилятор не будет ничего подставлять на этапе компиляции, если только у него нету оракула, который предсказывает, когда и по какому адресу мне понадобятся данные в рантайме)
Я рассматриваю общий случай, когда библиотекам, обрабатывающим матрицы нужна плоская адресация для цикличных данных.
То есть неудобство с границей плоского буфера вы заменили использованием кучи системных вызовов? И посчитали наносекунды.. а может тогда dma использовать для перемещения 2 блоков в выходной массив?
Каким образом можно это сделать на процессорах общего назначения?
А разве нельзя? Какие то вроде драйверы есть любительские - я давно ничего такого не программировал
А разве нельзя?
Вот я и интересуюсь у вас, как у эксперта) Потому что сам я драйвера не писал и с контроллерами не работал.
а может тогда dma использовать для перемещения 2 блоков в выходной массив?
Можно пример хотя бы? Или схему, как это вообще должно работать?
Я, похоже, сильно ошибся) я использовал режим буферизации в памяти ядра - один канал dma контроллера работал на заполнение элемента циклического буфера, второй - на копирование элемента в user space при операции чтения устройства. Драйвер по прерыванию контроллера апдейтил указатели чтения записи.
А год-два назад проглядел какую то статью здесь про использовпние dma в user space и в памяти осталось, что это уже работает. Но то что работает это доступ к контроллеру из user space, а это не очень перспективно, имхо.
Прошу прощения за ввод в заблуждение)
Несколько вариантов такое сдлать на системах с процессорами общего назначения:
8237. На удивление это самое распространенное решение даже сегодня. Ограничения - работает только в нижних 16 MB адресного пространства (и здесь также попадает регион SMM, который закрывается всякими вариантами TXT и в результате от 16 MB может и совсем мало что остаться; с другой стороны 2 х 8237 дадут максимум 768 KB одновременного пространства для DMA), и латентность вместе с пропускной способностью никуда не годится. Для условного Sound Blaster подергивать DRQ раз в сто микросекунд и получать очередной байт это работает, но для копирования памяти такое на много порядков медленнее даже наивного побайтового скалярного копирования. 2 MB/s память-память теоретический максимум, на практике соседние флоповод и Sound Blaster не дадут достичь того. Это как раз то, что называлось DMA во времена ISA.
Стороннее BM-capable устройство со своей памятью, например, сетевой интерфейс + немного работы руками. Делаем два дескриптора - откуда читать, куда записывать - и пусть копирует туда-сюда. Для блоков меньше чем страница не выгодно - цена подготовки дескрипторов сопоставима с копированием широкими векторами. Оповещение завершения - тоже руками, или поллинг до записи куда-то, или прерывание, или umonitor - если больше делать нечего.
Специализированные ускорители. DSA есть начиная с Sapphire Rapids, и делает свое дело хорошо. Модель похожа на предыдущий вариант, проще тем, что это один дескриптор (и со своей семантикой когерентности) так как DSA умеет memcpy как базовую функцию. Производительность для блоков больше страницы заметно лучше векторного копирования (для блоков меньше - сопоставима с ERMS), плюс это идет через ATS для копирования не в (свою) память.
Все это можно заставить работать. Но для изначальной проблемы решение с отображением физических страницы дважды - это проще и производительнее. Копирование, даже с аппаратным ускорением - это все равно копирование.
Почему же их кучи? Чуть больше 2-х при создании. Граница тоже никуда не делась, все также индекс по модулю сами ограничиваете. Преимущество только в том, что за рабочим буфером у вас его автоматическая тень, в которую у вас вылезает непрерывный массив, с какого бы элемента рабочего буфера вы его не запросили.
Да, ошибался, не дочитал) Всё равно не очень понимаю смысл использования mmap - у вас же всё равно нет сплошной физической памяти, при доступе будет постоянная трансляция страниц. Что мешает просто реализовать самому адресную арифметику по модулю - где надо? Если задача быстро сделать снапшот того, что уже в памяти, то самое эффективное это memcpy, пусть и в 2 этапа - перевычислить адреса это копейки по сравнению с доступом через отображение в память, что ваши тесты и подтверждают. Ну на С это напишите - всё равно же mmap хотите использовать
Я один раз видел, к чему приводят идеи "сделать красиво")) На достаточно дохлой машине надо было считывать файл и блоками передавать его по сети. Формат - заголовок сколько то байт и массив short пара килобайт. Программа на c++ состояла из десятка классов, не помещающихся на пару экранов каждый - сначала открывался и парсился файл, потом создавался объект с объектом заголовком и объектом массивом, потом он сериализовался и побайтно засовывался в сокет. Выглядело это очень академично, но.. ну нельзя же так, если задачей является поток данных порядка 10 МБ сек))
нет сплошной физической памяти, при доступе будет постоянная трансляция страниц.
Ну так ее и так, и так нет. Трансляции есть что при традиционном подходе, что в этом.
Что мешает просто реализовать самому адресную арифметику по модулю - где надо?
Борятся не с арифметикой (она-то как раз никуда не делась), а с созданием копий в памяти. Циклический буфер имеет границу. Если вы хотите извлечь из него один непрерывный кусок байт (в виртуальной адресном пространстве, с которым все и работает), то вам нужно озаботится, чтобы у вас этот непрерывный кусок был. Например, если у вас в буфере его начало на последнем элементе хранилища (т.е. буфер тут же враппится и хвост продолжается в начале), то вам надо:
или скопировать практически весь буфер (кроме первого элемента) в память за концом хранилища (это если там свободно)
или скопировать все хранилище, куда-то в другое место, сделав так, чтобы логически первый элемент был первым и физически
или поддерживать хранилище в двукратном размере, работать в его первой половине, а когда надо отдать непрерывный кусок, то хвост вылезает во вторую половину. Для буфера на
элементов в худшем случае логическое начало на последнем рабочем элементе (индекс 
) и вам нужна копия в хвосте. То есть хранилище должно быть размера 
. В этом хвосте можно или наполнять его по требованию (когда попросят непрерывный кусок памяти из буфера, разумеется, помять можно только одолжить, а не отдать во владение)
или поддерживать в нем копию каждый раз при вставке нового элемента в буфер, чтобы когда непрерывный кусок попросили, он у вас уже был. Полезно, когда просят часто по сравнению со вставками
или сделать так, чтобы ОС это поддерживала автоматически, трансляцией страниц. Полезно, когда и вставляете часто, и непрерывный кусок просят часто. Причем нет каких-то специальных накладных расходов – страницы в любом случае транслируются куда-то в физическую память, только тут эта трансляция еще приносит дополнительную пользу
Эээ... давайте я свои представления про циклический буфер выскажу сначала) Что это и для чего нужно - буферизация данных, когда, допустим, ввод идёт периодичный, а считывание и обработка батчами - то есть обработка может быть быстрой, но периодичность хромает. Простейшый случай - просто двухбуферная схема, когда ввод идёт в одну область памяти, а вторая в это время обрабатывается и потом освобождается. Когда не хватает детерминированности поведения, 2 буфера превращаются в несколько, а если могут возникнуть проблемы с фрагментацией памяти, то это превращается в буфер кратно превышающий фрагмент данных, и поскольку он имеет указатели чтения и записи, то их цикличность это способ имплементации такого буфера в заранее аллоцированой памяти. То, что циклический буфер представляют списком это точно чей то бред)) В здравом уме это точно незачем, имхо.
У вас есть поток данных блоками. То есть кто то пишет в пустой блок, а процесс обработки считывает уже доступные данные из записанного блока. Считал-обработал - освободил. Нужен снапшот - сделал 2 memcpy в другое место либо необработанного содержимого, либо от текущего до записываемого - как надо. И там сам процессор разберётся как ему из одного пространства памяти скопировать в другое - не будет там ещё и ос с mmap памятью болтаться в промежутке.
ЕСли я правильно понимаю вашу задачу, то у вас есть кадры, идущие потоком. Идет обработка кадров, и в какой то момент что то срабатывает, и вам нужно отдельно обработать кадры предыстории и те кадры, которые уже в буфере, но ещё не обработаны. Вы делаете снимок буфера, а поскольку он циклический, то надо в новом буфере обеспечить упорядоченность. Ну так и зачем этот подход с mmap? Правда не понимаю. Все равно всё сводится к тому, насколько поток входных данных затирает старые данные и насколько обработка освобождает буфер. В производительной системе никаких аллокаций памяти вообще не должно происходить - только статика
Чёрная магия C++: Быстрый кольцевой буфер