Парсинг потока на пакеты сообщений - минимизировать копирование

Кормим парсер побайтово, как это делают все нормальные люди.

Если протокол поддерживает разбиение на сообщения без разбора явно или не явно, то перед парсером можно поставить сплиттер.

Т.е. интерфейс будет выглядеть примерно так:

struct Parser {
  list<message> feed(vector<char> received);
}

Это DOM-like вариант, для случаев когда сообщения нужны целиком.

SAX-like вариант, он же потоковый может выглядеть примерно так:

struct Handler {
   void on_message(MessageHeader*);
   void on_field(Field*);
   // e.t.c
   void on_message_end(MessageFooter*);
}

struct Parser {
    void feed(vector<char> data, Handler& handler);
}

Фишка в том, что sax вариант в нормальном парсере у тебя одна фигня будет в реализации так или иначе, вопрос только какие требования к интерфейсу.

Используй первый метод, mmap’ни свой буфер 2 раза рядом друг с другом, и ты получишь бесплатный «wraparound», никаких memmove.

https://en.wikipedia.org/w/index.php?title=Circular_buffer&oldid=588930355#Optimization

https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buffer/

Подправь код под memfd_create или что у тебя там.

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

В первом варианте - проще писать итоговую бизнес логику, но сложнее оптимизировать работу с памятью, т.к. придётся обрабатывать аллокации. Во втором варианте сложнее писать логику, но аллокаций можно избежать вовсе, или сильно снизить их количество (зависит от протокола).

У меня контроллер и виртуальной памяти там нет :)

У меня контроллер и виртуальной памяти там нет :)

Ладно, я пытался. 🤠–/

но идея конечно интересная

Не сразу понял суть проблемы, по факту ты спрашиваешь, делать ли тебе сплиттер и если и делать, то как, либо кормить поток парсеру и копировать данные в контекст, а ты хотел бы обойтись вообще без копий.

Т.е. я по факту предложил третий вариант.

это называется стриминговый протокол, у всех есть в начале размер пейлоада который идет дальше[br]

да

Что подразумевается под сплиттером?

То что предлагает пончик, это слишком сложно.

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

Нет, есть случаи, когда не обязательно хранить контекст состояния разбора. ИМХО, то что описывает ТС как раз тот случай.

Я предложу свой вариант. У него есть свои плюсы, и свои минусы. Но с точки зрения простоты и удобства ИМХО, самый лучший. Правда нужно иметь реализацию некоторой структуры данных - кольцевого буфера. Уверен ТС сам сможет осилить написание реализации.

У нас есть кольцевой буфер фиксированного размера, такого, чтобы в него гарантировано влезло хотя бы одно сообщение максимального размера.

По мере прихода данных по сети мы записываем байты в этот кольцевой буфер «в хвост». Потом пытаемся достать полное сообщение из «из головы» буфера. Т.е. сначала проверяем, что байт в буфере набралось на заголовок. Если набралось, то достаем заголовок без извлечения (т.е. операция Peek, а не Pop) и смотрим на поле размера. По полю размера определяем полный размер сообщения. Теперь смотрим, есть ли в кольцевом буфере все сообщение целиком. Если есть, то достаем и обрабатываем. Если не получилось достать полное сообщение в этот раз, то когда придут новые данные, попытаемся достать полное сообщение снова.

Теперь смотрим, есть ли в кольцевом буфере все сообщение целиком. Если есть, то достаем и обрабатываем.

Оно может быть целиком, но сдвинуто от начала буфера, т.е сначала хвост сообщения, потом начало сообщения

То, как хранятся данные в кольцевом буфере, пускай интересно только реализации этого самого буфера. У тебя есть функции Pop(), Peek(),Push(),GetSize(). Больше ничего интересовать не должно.

У нас есть кольцевой буфер фиксированного размера, такого, чтобы в него гарантировано влезло хотя бы одно сообщение максимального размера.

У меня в TODO тоже есть подобная проблема с uIP. Памяти в обрез, счёт на байты. Но DMA контроллер на DSP ничего не знает про кольцевой буфер.

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

Pop()

Т.е. нужен ещё один целый буфер с копированием?

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

Я не понимаю, вам с этим данными ещё работать надо, т.е. приводить к удобному виду, что само собой подразумевает копирование.

Я не понимаю, вам с этим данными ещё работать надо, т.е. приводить к удобному виду, что само собой подразумевает копирование.

ну в первых двух вариантах можно передавать указатели на содержимое внутри буфера, во время выполнения функции-обработчика они будут валидными

А тут не будут?

а тут содержимое сообщения разорванным может оказаться :)

Я так понимаю, тебя не пугает перспектива обращаться по указателю на не выровненные данные, а экономия копирования стоит на первом месте. Тогда делай по второму варианту.

2 вариант кажется мне наиболее простым

В случае большого потока сообщений его видимо можно и заоптимизировать выделив буфер размером x*N и читать из сокета не больше (x-1)*N байт за раз

Как раз сущность которая разбивает поток на сообщения и кормит буфером в котором ровно одно сообщение парсер. Его не всегда возможно реализовать, но практически всегда. Вот реализовать его эффективно, без реалоков или избыточных обращений к i/o - сложно.

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

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

или по кусочкам копировать в отдельные буфера.

Есть место для нескольких? Тогда фантазии

Сделать N буферов . Например 4

• Сообщение A пришло полностью в 1N -> отдаём обработчику -> очищаем буфер получаем следующее сообщение
• Сообщение B пришло частично в 1N -> ну пришло и пришло в обработчик передавать пока нечего, устанавливаем в качестве текущего буфер 2N
• Сообщение C пришло тоже частично в уже 2N ну опять мимо устанавливаем в качестве текущего буфер 3N
• Сообщение B пришло теперь оно готово передаём обработчику типа 1N=240 3N=240 где 240 размеры, a 1N 2N последовательность откуда читать очищяем буферы
• Сообщение D пришло полностью текущий N3 уже пустой - отдаём - очищаем
• Сообщение X пришло в 3N частично переключаем на 2N
• Сообщение Y пришло частично - да что же такое то! переключаем на 4N
• Сообщение Z пришло опять частично … timestep D > X || Y || Z Сорян D но ты в пролёте стираем его и Текущий снова N3

Тоесть если идут ошмётки сообщения то мы их всё же храним в некотором колличестве, но если остатки куда то алё, а буферы для кусков кончились шлём нахрен самый старый.

P.S С этими xN ABCDXYZ я сам запустался, но смысл понятен наверное. Копировать ничего не надо но в обработчик надо отдавать список последовательности буферов с размерами что бы он их читал и получал по итогу целое сообщение всегда. Количество буферов подобрать как компромисс того сколько есть памяти и насколько часто приходят вместо целых сообщений ошмётки которые надо собирать

Я хз как это реализовывать, но мне прикольно показалось :D

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

сообщения идут последовательно, пока одно не придёт целиком, слеующее не может появиться. Ну или другая сторона шлёт неправильные сообщения и мы дропаем соединение

Ааа, эмм. Ок. Тогда второй вариант =)

Возможно, вы идёте немного не с той стороны и/или смотрите на процесс не с той высоты.

Просто избавление от копирования в каком-то конкретном месте может породить существенные накладные расходы в другом. Один из антипаттернов - кормить парсер отдельными байтами, а не использовать SIMD (примеры №1, №2).

Однократное копирование может быть очень оправдано, особенно для сбора сообщений («выпрямления» данных), для простой и эффективной их последующей обработки.

В сценариях без user-mode TCP-стека (когда данные копируются из ядра), достаточно неплохо работает вариант кольцевого буфера:

• Данные принимаются непосредственно в голову буфера, т.е. каждый read() их просто дописывает.
• Перевод указателя записи из конца буфера в начало происходит на границе сообщения, когда до конца буфера остается места меньше максимального размера сообщения. Таким образом, все сообщения всегда лежат в памяти линейными кусками.
• Данные передаются на обработку целым куском с хвоста буфера, без копирования. Хвост сдвигается после завершения обработки.
• Если обработка асинхронная, то для каждого обрабатывающего треда (или отправленного на обработку сообщения), отслеживается свое значение «хвоста», а свободное место в буфере отслеживается по минимальному значению из всех «хвостов» находящихся в обработке. При необходимости можно организовать цепочку кольцевых буферов.

Эта схема даёт 0 лишних копирований, при условии что данные всё равно приходиться вычитывать/копировать из ядра.

Если хочется еще быстрее, то см Seastar.

читать и обрабатывать блоками размером до MTU. Вместо массива байт будет массив(или список, от реализации) частично заполненных блоков. Операции копирования резко сокращаются, почти исчезают, но появляются трабл что важный кусок может быть «разрезан» между двумя блоками. Чтобы такого избегать неплохо знать протокол.

Посмотри как кернигановский streams сделан в плане работы с памятью. Может где-то в архивах ещё остались оргинальные публикации.

Каждое сообщение имеет либо фиксированный заранее известный размер,

Тогда проблемы же нет. Просто размер буфера должен быть кратен размеру сообщения.

либо в заголовке содержит длину.

Можно сначала читать заголовок, смотреть есть ли место и действовать по обстоятельствам (если нет, то запомнить заголовок на будущее).

Чувствую себя капитаном, но, вроде, это не озвучили, либо все поняли почему это не подходит.

Кольцевой буфер?

В сценариях без user-mode TCP-стека (когда данные копируются из ядра), достаточно неплохо работает вариант кольцевого буфера:

Данные принимаются непосредственно в голову буфера, т.е. каждый read() их просто дописывает. […]

Эта схема даёт 0 лишних копирований, при условии что данные всё равно приходиться вычитывать/копировать из ядра.

Внезапно наткнулся на (возможно первое) публичное описание обозначенного подхода, с примерами для recv(): https://web.archive.org/web/20121006080117/http://www.codeproject.com/Articles/3479/The-Bip-Buffer-The-Circular-Buffer-with-a-Twist