LINUX.ORG.RU

crc32 calculation

 , , ,


0

3

Нашёл вот тут реализацию crc32 для little-endian. Конкретно я думаю выбрать crc32cx.

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

★★★★★

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

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

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

О, интересно, спасибо. Я смотрю везде используется этот полином 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

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

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

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

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

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

Ну я так понял, на 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;
UVV ★★★★★ ()

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

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

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

UVV ★★★★★ ()

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

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

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

invy ★★★★★ ()

- У 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 или чего подревней...

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

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

Dennis7 ()
Последнее исправление: Dennis7 (всего исправлений: 1)
Ответ на: комментарий от vromanov

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

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

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

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

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

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

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

Dennis7 ()
Ответ на: комментарий от Iron_Bug

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Iron_Bug ★★★★★ ()
Последнее исправление: Iron_Bug (всего исправлений: 1)
Ответ на: комментарий от Iron_Bug

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

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

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

Iron_Bug ★★★★★ ()
Последнее исправление: Iron_Bug (всего исправлений: 2)
Ответ на: комментарий от Iron_Bug

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

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

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

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

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

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

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

Dennis7 ()
Ответ на: комментарий от Iron_Bug

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

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

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

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