ugidctl – linux uid/gid control, часть 3

Пора придумать как хранить списки uid’ов и gid’ов в ядре. Из основных особенностей этих списков должны быть следующие:

  1. Списки могут быть большими, например 1 млн. записей.
  2. Списки будут содержать только уникальные значения.
  3. По спискам нужно эффективно искать элементы.
  4. На входе списки могут содержать дублирующиеся элементы, могут быть не отсортированными. Другими словами сортировка и исключение дубликатов должны быть на стадии сохранения.

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

Тем временем для хранения узлов деревьев нужно будет динамически выделять и освобождать небольше куски памяти ядра. Они у меня все будут одинакового размера.

Для этого отлично подходит kmem_cache. Он позволяет заранее сообщить ядру размер кусков памяти, которые я буду выделять и освобождать. Фактическое выделение и освобождение будет уже делаться функциями, которым нужно будет сообщить не размер выделяемого участка памяти, а адрес пула, из которого они будут выделяться. Это позволяет сильно сократить накладные расходы памяти, связанные с её выделением, и держать выделенные куски памяти ближе друг от друга.

Делается это как-то так:

Результат:

Теперь возьму почти оригинальную реализацию красно-черных деревьев из документации к ядру и опишу несколько функций для управления списком uid’ов. Напишу их в отдельном файле — ugidctl-cache.c. Основной файл переименую в ugidctl-dev.c. Makefile, соответственно, тоже придется поменять:

Структуры ugidctl_uid_node и ugidctl_gid_node стоит вынести в ugidctl.h:

А вот, собственно, и ugidctl-cache.c, всё прямо как тут. Для краткости оставлю пока только функции управления списком uid’ов — для gid’ов они аналогичны:

В ugidctl-dev.c проверю, всё ли корректно работает:

Результат:

Кажется почти все. Пора начинать все части совмещать воедино. В следующем посте заставлю это работать.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *