Данные буферизации для разделенных блоками разделителей

Question

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

Давайте предположим, что у меня есть входной поток (например, файл / сокет / канал) и я хочу проанализировать входящие данные. Давайте предположим, что каждый блок входящих данных разделен новой строкой, как большинство распространенных интернет-протоколов. Это приложение также может выполнять синтаксический анализ html, xml или любой другой интеллектуальной структуры данных. Дело в том, что данные делятся на логические блоки с помощью разделителя, а не фиксированной длины. Как я могу буферизовать данные для ожидания появления разделителя?

Ответ кажется достаточно простым: достаточно большого массива байтов / символов, чтобы вместить все это.

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

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

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

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

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

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

Есть мысли на эту тему? Очевидно, что должен быть способ, так как языки более высокого уровня предлагают какие-то механизмы буферизации с их readLine() потоковыми методами.

Есть ли "лучший способ" решить это или всегда есть компромисс? Я действительно ценю все мысли и идеи по этой теме, так как этот вопрос преследует меня каждый раз, когда мне нужно написать какой-то парсер.

Answer 1

Обычно есть два метода для этого

1) Что, я думаю, использует readline - если заполнение буфера возвращает данные без разделителя в конце

2) Когда буфер заполнится, запомните, что он заполнен, продолжайте чтение, пока не получите разделитель и не сообщите об ошибке (или не обрежете запись до размера буфера)

Answer 2

1. Если протокол или вы не определяете верхнюю границу для длины каждого блока, тогда я не вижу, как вы можете предотвратить случаи с исчерпанием памяти.

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

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

Answer 3

Почему вы должны ждать, чтобы начать обработку?

Обычно альтернативой 4 является звук. Однако это не требует «предположения», а скорее определения. Вы просто объявляете, что блоки меньше 8 КБ, и с этим покончено. Это не сложно сделать.

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

HTML, XML, JSON / YAML и т. Д. Могут анализироваться постепенно. Вам не нужно требовать разделителя для выполнения полезной обработки.

Answer 4

Опции (2) и (3) отсутствуют, поскольку вы теряете данные в обоих случаях. Вариант (4) большого буфера фиксированного размера не решит проблему, поскольку просто невозможно узнать, какой размер достаточно велик? Это вся физическая память + пространство подкачки + свободное место, доступное на всех дисках в любой известной вселенной?

Изменение размера буфера выглядит как лучшее решение. Скажите realloc, чтобы удвоить размер и продолжить запись. Всегда есть шанс специально сконструированного потока, такого как DoS, который пытается отключить систему. Моей первой мыслью было установить произвольно большой размер как max_size для буфера. Однако, если бы мы могли это сделать, мы могли бы просто установить это как размер большого буфера. Таким образом, изменение размера буфера выглядит для меня лучшим вариантом.