LINUX.ORG.RU

C++ парсинг протоколов. HTTP, например.


0

2

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

Например, в nginx запилена такая FSM (finite state machine), которая жрёт по 1 байту и идёт в длинный switch, где в зависимости от текущего состояния каким-то образом сжирает этот байт.

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

Насколько большой оверхед даёт FSM в виде хождения в таблицу указателей на функции (это то, во что скомпилируется switch) на каждый байт?

Я понимаю, что FSM по-хорошему нужен. Кусок HTTP-запроса может прийти раньше второго куска. Малолетние хакеры могут захотеть посылать HTTP-запросы через nc по одной строчке и это выдержит nginx. Но в реальной жизни целый запрос обычно валится в виде одного пакета.

Для http там switch получится просто огромный...

Малолетние хакеры могут захотеть посылать HTTP-запросы через nc по одной строчке и это выдержит nginx

А ещё малолетние хакеры могут использовать telnet или фиговое соединение, ИМХО, ДКА нужен.

Но в реальной жизни целый запрос обычно валится в виде одного пакета

Определи понятие «реальная жизнь»

Stil ★★★★★ ()

какой идиотизм я только что прочитал

Harald ★★★★★ ()
Ответ на: комментарий от Stil

Для HTTP switch нормальный, если писать не криво. В nginx аффтар напейсал и не умер. Читаемо, никаких фатальных ужоснахов нет.

kiverattes ★☆ ()

даю подсказку - HTTP работает поверх поточно-ориентированных протоколов, например, TCP

Harald ★★★★★ ()

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

Ну тебе же всё равно нужно анализировать каждый байт в буфере, что бы „выцепить из этого буфера разные аспекты парсимого протокола“. Да ещё и делать это будет каждая процедура с начала. Так что упомянутый оверхед может быть как раз отрицательным.

nanoolinux ★★★★ ()

man regexp спасет отца демократии или мать истерии

anonymous ()
Ответ на: комментарий от Harald

Читатели топика массово упоролись, поскольку о своём знакомстве с фактом поточно-ориентированности HTTP я явно упоминул несколько раз в посте. И тут вдруг они внезапно поняли, что надо написать об этом ещё раз.

kiverattes ★☆ ()
Последнее исправление: kiverattes (всего исправлений: 1)

Насколько большой оверхед даёт FSM в виде хождения в таблицу указателей на функции (это то, во что скомпилируется switch) на каждый байт?

Относительно большой. HTTP проектировали чтобы его можно было парсить совсем топорно в заранее накопленном буфере, ~ поиск по \r\n, нулей и т.п. Поиск байта-двух всегда быстрее кормёжки по байтам в FSM.

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

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

mashina ★★★★★ ()
Ответ на: комментарий от kiverattes

Кусок HTTP-запроса может прийти раньше второго куска

наоборот прочитал значит, ок :)

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

Harald ★★★★★ ()
Ответ на: комментарий от Harald

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

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

Просмотр каждого байта функцией strcmp - это быстрее, чем прыгать на каждый байт в switch().

kiverattes ★☆ ()
Ответ на: комментарий от kiverattes

почти всегда запрос целиком есть в первом принятом пакете

Да, точно. Особенно когда в запросе URL c кучей параметров или POST-запрос

Ты хочешь вручную парсить HTTP без построения FSM? Никто же не мешает? Старые протоколы делали типа человеко-читабельными и человеко-писабельными. Можешь читать по «строкам» (\n) и парсить уже отдельную строку (регулярками, хе-хе)

anonymous ()

Кхм... Парсеры бывают разные (тут можно было бы написать целую лекцию). Если известны конкретные требуемые параметры, можно сгенерить парсер чем-то вроде ANTLR (или yacc, lex, flex, bison - вопрос личных предпочтений). Если умеешь работать с генераторами, то это задача лёгкая. Но это вопрос опыта. Иногда проще изучить работу с генераторами парсеров, чем городить какое-то своё чудище. Конечно, всё зависит от задачи. Для одноразовой софтины по выцеплению пары заголовков это слишком мощное решение. А вот для более сложных вещей типа браузеров - вполне себе оправданное.

Iron_Bug ★★★★★ ()

Лучше всего писать код FSM на каком-нибудь DSL, который потом сгенерит тебе оптимизированный код. Например Ragel.

Кроме того, если хочешь парсить HTTP 1.1, то эту FSM даже писать не придётся, можно взять код из Mongrel, см. файлы с расширением rl в https://github.com/evan/mongrel/blob/master/ext/http11/

nozh ()
Последнее исправление: nozh (всего исправлений: 1)

поточно-ориентированности HTTP

в таблицу указателей на функции (это то, во что скомпилируется switch)

на этом пакете запускать всякие функции сравнения строк

запрос целиком есть в первом принятом пакете

вся суть С++ кодеров

rand ()

которые выцепят из этого буфера разные аспекты парсимого протокола

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

Кстати я что то не понимаю о каких огромных switch идет речь? Состояний, да может быть много, но в каждом конкретном состоянии вариантов выбора для http можно по пальцам пересчитать.

Ну и конечно, какой вообще нахрен switch? За switch в крестах нужно расстреливать сразу и без размышлений.

no-such-file ★★★★★ ()
Ответ на: комментарий от no-such-file

Ну и конечно, какой вообще нахрен switch? За switch в крестах нужно расстреливать сразу и без размышлений.

Где ты там кресты увидел?

mashina ★★★★★ ()

Кусок HTTP-запроса может прийти раньше второго куска

- если клиент шлет данные по TCP в правильном порядке, то этого быть не может.

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

  • количество распарсенных байт из предоставленного буфера;
  • признак полностью полученного HTTP-сообщения;
  • признак ошибки парсинга и ее данные;
  • данные распарсенного HTTP-сообщения (method, URI, version, headers, etc.);
  • тело распарсенного HTTP-сообщения.

При этом да, парсер получается stateful, ибо, опять же, можно получить от клиента не весь запрос что повлечет за собой повторное получение данных от клиента и «допарсивание», так что без FSM не обойтись.

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

illy ()
Ответ на: комментарий от kiverattes

вот если бы ты написал «второй кусок позже первого», тогда бы все всё сразу правильно поняли :)

Harald ★★★★★ ()
Ответ на: комментарий от kiverattes

Упс, заработался, прошу прощения. «Второй кусок не может прийти раньше первого» :)

illy ()
Ответ на: комментарий от kiverattes

в интернете.

Ну ты и обалдуй. Кресты были крестами когда интернет ещё пешком под стол ходил.

no-such-file ★★★★★ ()
Ответ на: комментарий от anonymous

весь мир давно за белых людей здесь считают caucasian

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.