Онлайн-соответствие запросов приложений с ответами в Linux Kernel

Question

Использование крючков Netfilter Я реализовал модуль ядра Linux, который проверяет все входящие и исходящие пакеты хоста. Используя этот модуль, я могу контролировать потоки данного приложения, работающего на этом хосте, то есть, зная порты/IP-адреса src/dst, я могу отфильтровывать (классифицировать) соответствующие пакеты при их получении/отправке.

Что я хочу сделать дальше, это совпадение во время выполнения, запросы входящих приложений с соответствующими исходящими ответами. Каждый запрос/ответ идентифицируется с помощью src/dst IP и уникального идентификатора.

Наивный реализация является текучий:

• магазин каждый входящий запрос в списке (массив/связанный список и т.д.)
• Для каждого исходящего ответа:
  • Поиск через чтобы найти соответствующий запрос. Если запрос найден, удалите его из списка.
• Периодически сокращать список запросов на удаление запросов старше X секунд.

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

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

Спасибо!

Answer 1

Вы можете использовать хеш-таблицы для уменьшения операций поиска, в ядре linux 3.7+ есть общая хеш-таблица implementation, которую вы можете использовать в своем модуле ядра. Он имеет очень простые в использовании функции.

Необходимо создать ключ с вашими требованиями, скажем src/dest ip & порт + запрос уникального идентификатора и использование его в хеш-таблице, хэш-таблица хранит значение для каждого ключа, значение может быть указателем на реальный запросить полезную нагрузку. основанный на его реализации, он мог бы иметь наихудший случай O (n), но хеш-таблицы с хорошим коэффициентом заполнения могли бы легко достичь O (1) или O (logN).

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