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

Question

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

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

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

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

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

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

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

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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

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

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

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