Привет)

Зачада, возможно, чисто алгоритмического плана, но имеет непосредственное отношение к сетям

Я ловлю "не свои" пакеты с помощью pcap - получаю пакеты в сыром виде

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


Соответственно:
Есть ли какая-то стандартная реализация этого алгоритма? (кажется, нет)

Если нет - как мне понять, в какой момент мне пришли ВСЕ части?
Если установлен флаг ip "Не фрагментировать" - вообще можно ничего не проверять
Очевидно, что проверку можно и нужно запускать только тогда, когда пришел пакет ip с установленным флагом "Последний"
Так вот как реализовать проверку? Пробегать по всему массиву я не хочу дико - это медленно.
... а еще нужно помнить, что могут приходить части разного объема (из-за изменения окна), могут приходить одни и те же куски несколько раз, и, в самом неприятном случае - могут приходить части, частично перекрывающие уже пришедшие.
Ну вобщем, если у кого есть мысли, как можно хранить и потом проверять наличие частей - буду очень признателен

(мне на ум приходит только std::map, хранящая структуры {смещение начала, смещение конца})

Это сообщение отредактировал(а) pcapH - 11.2.2012, 16:28

смотри реализацию в линуксовом ядре.

Серьезно? о_О

Чо там реализовывать? Бери большэ -- кидай дальшэ, пока летит -- отдыхай. Ну, ещё ttl у пришэдшых каждую секунду откручивай, чтобы пакеты навечно не застревали.



Очевидно, если у тебя есть пакет с more fragment=0 (т.е. последний пакет), и пакеты с таким жэ IP_SRC:IP_DST:Identification перекрывают весь диапазон до fragment offset этого последнего пакета.



Если не пишэшь роутер -- то не особенно. Сколько там тех фрагментированных пакетов одновременно будет? Но да, можно и BTREE замутить.
И да, разумеется, все части одного пакета надо складывать в одну структуру сразу. Можно с одним заголовком, буфером данных, и битмапом заполнености с гранулированностью 8 байт.



Окна -- это в TCP.



Вообще -- не должны. Только какая разница?

Да, это все так, но задача как раз в том, чтобы понять, что пакеты перекрывают весь диапазон


Пишу :(


Да, признаю, - запутался


Это сообщение отредактировал(а) pcapH - 11.2.2012, 22:26

Битмапом. Что то-вроде char completed[MAX_PACKET_SIZE/8/8+1]; в struct ip_packet_rec.

При приходе ip-пакета received находишь его struct ip_packet (по ip_src:ip_dst:identification), и заполняешь битики completed (если рассматривать его как битовый массив) -- начиная с received.fragment_offset, в количестве received.size/8 (округлится, замечу, в правильную меньшую сторону). Разумеется, если важна скорость -- следует стремиться заполнять не по одному биту, а по байту или дажэ по инту сразу. Ну, то есть нецэлые байты -- уж как есть (хотя тожэ можно таблицу сделать, наверное), а цэлый -- присвоением 0xFF или 0xFFFFFFFF в соответствующие места. А, да, сами данные из received -- разумеется, записываем в буфер. Для простоты -- можно один буфер на ip_packet, сразу чтобы фрагменты собирались.

Далее, если received.more_fragments == 0 -- то мы из суммы received.fragment_offset*8 и received.size можэм записать полный размер нефрагментированного ip_packet.size. Всё, теперь начиная с этого момента -- проверяем (ну, каждый раз по приходе такого жэ пакета) -- весь ли у нас буфер пакета в наличии -- ну т.е. все ли биты от 0 до (ip_packet.size-1)/8 массива ip_packet.completed заполнены. -1 -- потому, что последний хвост из 1-7 байт у нас в любом случае пришли в последнем пакете, но могут быть не отмечены в массиве completed. Внимательно со случаем ip_packet.size == 0 -- его надо отдельно обработать. Проверять, опять жэ, шоткатами где можно. Всё, если заполнено -- пакет собран.

Почему / 8?
В соответствие биту ставим 8 байт?


Ты говоришь о том, как можно вычислить полный размер tcp?
Нужна эта информация, видимо, только для того, чтобы знать, на какой участке битмапа заканчивать проверку?
Почему *8? смещение же в байтах передается?

Потому, что fragment_offset в IP-протоколе у нас считает по 8 байт, если я ничего не путаю.



Какого tcp? Нет у нас никакого tcp, я о нефрагментированном IP-пакете говорю.



Прям щас.

ага. Понял.
Размеры передаем не по 8, а по 4 байта.

"received.size/4"
Почему деление, а не умножение? если пришло 5 - значит же у нас 20 байт?
Это опечатка или хитрый ход?

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



Потому, что size -- размер "data" в байтах, и ни в чём другом быть не можэт по очевидным причинам. Кстати, мне лень лезть в оригинал было, там в оригинале нет size, так что size = "Total length" - IHL*4.

Ну ладно) с размерностями я разберусь)
Идею понял)

Она плоха тем, что все равно придется пробегать по массиву, а если пакет был большой - то сокращение в 8 раз меня все равно сильно не спасет.
Хотя, кажется, других идей пока не звучало)
Спасибо, tzirechnoy, за алгоритм и за знание Сетей

В какие 8 раз? там я вообще-то предлагаю использоватьбитовый массив, т.е. в 64 раза.

PS И незабудьте шоткаты на сравнение/присвоение char и int где можно.