crc32 calculation

Таблицу захардкодить, вручную раскручивать циклы особо нет нужды. Короче, всё уже придумано.

mix_mix дела говорит.

или у тебя срс32 там критическая хрень, которая считается 1000000 раз в секунду?

О, интересно, спасибо. Я смотрю везде используется этот полином 0xEDB88320. А в ядре предпочли другой..

/*
* This is the CRC32c polynomial, as outlined by Castagnoli.
* x^32+x^28+x^27+x^26+x^25+x^23+x^22+x^20+x^19+x^18+x^14+x^13+x^11+x^10+x^9+
* x^8+x^6+x^0
*/
#define CRC32C_POLY_LE 0x82F63B78

Просто нашёл, как через сокеты можно ядерную версию дёрнуть.

или у тебя срс32 там критическая хрень, которая считается 1000000 раз в секунду?

Нет, большого траффика не ожидается.

Ну я так понял, на LE цикл всё равно другой будет, так?

   crc = 0xFFFFFFFF;
   while (((word = *(unsigned int *)message) & 0xFF) != 0) {
      crc = crc ^ word;
      crc = (crc >> 8) ^ table[crc & 0xFF];
      crc = (crc >> 8) ^ table[crc & 0xFF];
      crc = (crc >> 8) ^ table[crc & 0xFF];
      crc = (crc >> 8) ^ table[crc & 0xFF];
      message = message + 4;
   }
   return ~crc;

А зачем тогда оптимизёвываешь? :)

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

Не, ну можно конечно запустить цикл самому и проверить сгенерированную таблицу. Но надо ли? По-моему, ты параноишь там, где не надо =)

В ядре есть вычисление crc32.

Я выше написал, что видел. Это код для userspace. Имхо, этому место там.

Тогда в чем вопрос - брать ли странную «оптимизированную» версию для вычислений ня небольшом потоке данных? Нет, конечно.

Если бы там были тесты с code coverage, то не параноил бы :)

- У arm, пункт 9.7 есть intrinsics. Какую часть алгоритма подсчёта crc они выполняют? (Ну что б предоставить оптимизированную под arm версию)

в гугле забанили?

Operation
CRC32 checksum performs a cyclic redundancy check (CRC) calculation on a value held in a general-purpose register. It takes an input CRC value in the first source operand, performs a CRC on the input value in the second source operand, and returns the output CRC value. The second source operand can be 8, 16, 32, or 64 bits. To align with common usage, the bit order of the values is reversed as part of the operation, and the polynomial 0x04C11DB7 is used for the CRC calculation.
In ARMv8-A, this is an OPTIONAL instruction.

Но ты учти

9.7 CRC32 intrinsics
CRC32 intrinsics provide direct access to CRC32 instructions CRC32{C}{B, H, W, X} in both ARMv8 AArch32 and AArch64 execution states. These intrinsics are available when __ARM_FEATURE_CRC32 is defined

у тебя ж поди ARMv7 или чего подревней...

это CRC-32-IEEE 802.3

+1

Сейчас процы это умеют.

На многих армах есть реализация CRC в железе. Например, на STM32F4 и TMS570. Она сильно быстрее!

gcc по какому ключу компиляции умеет такой код генерить? И есть ли поддержка от libc и с какой версии? Или писать на асме (не то чтобы надоело, но хочется изкаробки)?

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

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

через сокеты к железу лезть жопа изрядная. само таскание данных из юзерспейса в кернел и обратно отожрёт немало времени из-за синхронизаций и переключения контекста. проц не будет нагружен, но работать может не так уж быстро.
кстати, один чувак провёл тесты на разных реализациях crc32. может, пригодится: https://blog.fastmail.com/2015/12/03/the-search-for-a-faster-crc32/

А вот вопрос, каждый ip пакет содержит поле crc, т.е. для достоверности данных, и надо, по идее пройти по всем данным в пакете данной длины, и затем сравнить со значением, что в этом поле? И, если они не равны - изначит пакет «битый» (ну не знаю, нейтрино там левое пролетело...) и его надо отбрасывать? Тогда кто(что) производит этот подсчет crc? Корректный ли мой вопрос или я уже напился «в хлам» и мне пора нафиг смотреть как Реал играет с МанСи?

Еще вопрос: что «отжирает» больше времени, переключение контекста между юзер спейсом и ядром или между юзер спейсом и юзер спейсом? Ведь вдруг, шедулер решил передать квант времени от ssh демона mysql'y?

да знаю я это всё. в кернеле tcp/ip ковыряю не один год. но внутри кернела это быстро работает. а вот из юзерспейса будет всяко медленней. однако, кернел сам битые пакеты отбрасывает, чаще всего. так что до юзерспейса доходят уже «хорошие» данные и в большинстве случаев юзер не парится с проверками crc пакетов. разве что там ещё юзерский какой-то crc навешан сверху, тогда уже придётся его вручную считать самому.

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

Все классно! Но вот, Netfiler придумало какую-то не очень удобную систему фильтрацию трафика... Может быть это и есть хорошее решение на данный момент... Но держать в памяти ядра каждый connection track, это как-то жирно.

Но ведь есть решения, которые перенесли tcp/ip из кернела в юзерспейс

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

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

что некоторые процы умеют считать его искаропки, а это однозначно шустрее в тыщи раз.

На x86, ЕМНИП, когда только появился, было всего в 4-5 раз быстрей.

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

если ты к ней подкатываешь то ты уже вхлам... иначе бухай дальше, лол

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

Ага, умеет. При портмаппинге, когда записываешь запрещающие правила в iptables, то трафик при соеденившейся сессии все равно идет,потомучто TCP Established, и у коннекшн трафик нет ни единого резона эту сессию обрывать, а мне надо.

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

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

Ну так AES с CRC32 сравнивать не надо, второе - это, фактически, индикатор того, на сколько эффективна подсистема работы с памятью в железке сделана, ибо и табличка в кэш влезает, и микроопсы закэшированы и переиспользуются.

Не, ну на совсем стрёмных процах, застрявших в начале 90-х, может быть плохо, да.

А нафига сдался именно этот устаревший crc32? Почему бы не взять хеш функции, которые пилят другие разработчики, к примеру, вот эту (fnv): https://github.com/maciejczyzewski/retter/tree/master/algorithms/FNV

вообще-то, правила iptables обычно настраиваются при старте системы, ну или до старта TCP сессии

Мне нужно динамически. Клиенту из внешней сети нужен внутренний ресурс, скажем ftp. Делается классический портмаппинг на роутере, клиент скачивает и постит все, что ему нужно, но вдруг пришел злой админ и потер правила в iptables, а трафик все равно идет некоторое время, т.к. tcp сессия помечена как established.

Поигрался с таймаутами, нужного результата не дало. Решил посылать в порт FIN вместо RST, хотя RST наверно лучше.

tcpkill хорошая штука, но надо ее тащить на роутер, включать в прошивку, нужна поддержка от ядра (которое у нас на некоторых девайсах старее, чем испражнения мамонта).

Навскидку решил так, сделал файл в /proc, пишу туда что-то типа «X.X.X.X -> Y.Y.Y.Y», а кернел потом ищет соответствие по айпишникам и удаляет соответствующие им conntsction tracks, и все вопрос решен (конечно с синхронизацией, а то мало ли кто чего начнет писать в список соединений).

Может быть это не самое лучшее решение и сделано через одно место, на котором мы все сидим, но проблема решена.