Сегодня мы публикуем перевод первой статьи из серии материалов, посвящённых реализации epoll в ядре Linux 3.16.1*. Автор исходит из предположения о том, что читатели знакомы с API и с использованием epoll. Он уделяет основное внимание реализации подсистемы epoll в ядре Linux, а не особенностям её применения. Если вы не знаете о том, как пользоваться epoll — автор рекомендует сначала почитать документацию. Это значительно облегчит понимание деталей реализации этого механизма.



* — Linux 3.16.1 достаточно старое ядро, но информация работы с epoll актуальна и сегодня (прим. переводчика).

Что такое epoll?

Epoll — это несколько системных вызовов, предоставляемых ядром Linux и предназначенных для эффективной организации мультиплексирования ввода-вывода. Благодаря тому, как спроектирована виртуальная файловая система (VFS, Virtual File System) Linux, с любым «опрашиваемым» файлом, или, точнее, с файлом, реализующим файловую операцию poll(), можно работать, используя epoll. Среди таких файлов можно отметить файлы сокетов, которые в наши дни вызывают наибольший интерес разработчиков.

Старые методы работы

Традиционно программисты использовали для мультиплексирования ввода-вывода select или poll. Но и то и другое было спроектировано уже очень давно, во времена, когда сетевым службам приходилось работать лишь с тысячами одновременных клиентских подключений. Select и poll очень похожи. На самом деле, и тот и другой механизмы реализованы в одном и том же файле в репозитории ядра Linux (fs/select.c). Их, работа, кроме того, организована весьма просто. Приложение генерирует массив файловых дескрипторов (file descriptor, fd), которые его интересуют. Затем приложение выполняет системный вызов, обращаясь к ядру. Ядро копирует массив из пользовательского пространства и обходит дескрипторы, проверяя, с использованием файловой операции poll(), наличие новых событий. После этого select просто генерирует битовый массив и копирует его обратно в пользовательское пространство. А poll напрямую работает со структурой pollfd прямо в пользовательском пространстве, не копируя её.

Проблема

Можно заметить, что реализация select и poll указывает на то, что эти механизмы плохо приспособлены к обработке больших количеств файловых дескрипторов. Временная сложность алгоритмов, лежащих в основе обоих этих механизмов, это O(n). С этим не было никаких проблем до тех пор, пока число тех, кто пользуется интернетом, было сравнительно небольшим. В наши дни вполне обычной является ситуация, когда серверам приходится поддерживать 100000 одновременных подключений. Хотя и можно обрабатывать такие количества подключений, пользуясь select и poll, весьма вероятно то, что ценное процессорное время будет растрачиваться на выполнение опросов огромного количества файловых дескрипторов. Это сильно подействует на масштабируемость и доступность сервера. Данную проблему можно решить с помощью механизма, который способен уведомлять нас о событиях дескрипторов, делая это более интеллектуально. Именно такой вот интеллектуальный механизм уведомлений и реализован в epoll.

Обзор

Прежде чем мы углубимся в исходный код ядра Linux, давайте разберёмся с тем, как, в общих чертах, работает epoll.

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

Экземпляр epoll

Экземпляр epoll — это сердце подсистемы epoll. В Linux экземпляр epoll можно запросить, выполнив команду epoll_create(2) или команду epoll_create1(2). Обе команды возвращают файловый дескриптор. Причина того, что в качестве ссылки на экземпляр epoll используется файловый дескриптор, заключается в том, что это позволяет опрашивать экземпляр epoll. Благодаря такому подходу можно использовать продвинутые схемы работы с epoll, в ходе реализации которых, например, экземпляры epoll можно мониторить с использованием epoll, select или даже poll. Но самая важная часть экземпляра epoll — это внутренняя структура данных struct eventpoll, объявленная в коде ядра, в 180 строке файла fs/eventpoll.c. Эта структура данных отвечает за поддержку всех тех механизмов, которые нужны epoll для правильной работы. Код, который выделяет память под struct eventpoll и возвращает файловый дескриптор, можно найти в файле fs/eventpoll.c, в строке 1767. Вот фрагмент этого файла:

/*
 * Создание внутренней структуры данных ("struct eventpoll").
 */
error = ep_alloc(&ep);

Команда ep_alloc() просто выделяет из кучи ядра память, объём которой достаточен для хранения struct eventpoll, и инициализирует эту память.

После этого epoll_create() пытается получить у процесса неиспользуемый файловый дескриптор:

/*
* Создание всего что нужно для настройки файла eventpoll. То есть -
* файловой структуры и свободного файлового дескриптора.
*/
fd = get_unused_fd_flags(O_RDWR | (flags & O_CLOEXEC));

Если epoll_create() удалось получить файловый дескриптор, то будет сделана попытка получить у системы анонимный inode. Обратите внимание на то, что epoll_create() сохраняет указатель на ранее выделенную память под struct eventpoll в поле файла private_data. Так как любые системные вызовы, работающие с экземпляром epoll, обращаются к нему с использованием номера файлового дескриптора экземпляра, это крайне упрощает и делает весьма эффективным повторное получение struct eventpoll, выполняемое позже:

file = anon_inode_getfile("[eventpoll]", &eventpoll_fops, ep,
                          O_RDWR | (flags & O_CLOEXEC));

После этого epoll_create связывает анонимный inode с файловым дескриптором и возвращает файловый дескриптор вызывающему процессу:

fd_install(fd, file);
return fd;

Как экземпляр epoll «запоминает» файловые дескрипторы?

Экземпляр epoll, по очевидным причинам, должен как-то «запоминать» файловые дескрипторы, наблюдение за которыми ему поручили. Для этого применяется структура данных, которая часто используется в ядре Linux. Это — красно-чёрное дерево (КЧ-дерево, Red-black tree, RB-Tree), в котором хранятся файловые дескрипторы, за которыми наблюдает конкретный экземпляр epoll. Корень дерева представлен членом rbr структуры eventpoll, он инициализируется в функции ep_alloc().

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

Когда для добавления файлового дескриптора в экземпляр epoll используется команда epoll_ctl(2), ядро сначала использует ep_find() в попытке найти структуру epitem, соответствующую этому файлу (строка 973 файла fs/eventpoll.c).

Так как красно-чёрное дерево — это двоичное дерево поиска, то оказывается, что, прежде чем сохранять в нём элементы epitem, им нужно назначать ключи, содержащие данные, которые можно использовать в операциях сравнения. В случае с epoll ключи элементов, хранящихся в КЧ-дереве, представлены структурами epoll_filefd, хранящимися в epitem. Структуры epoll_filefd устроены очень просто, код их объявления можно найти в файле fs/eventpoll.c, в строке 106. Вот этот код с моими комментариями:

struct epoll_filefd {
  struct file *file; // указатель на структуру целевого файла, соответствующий fd
  int fd; // номер дескриптора целевого файла
} __packed;

Функция, которая выполняет сравнение значений, носит имя ep_cmp_ffd() (файл fs/eventpoll.c, строка 326):

/* Сравнение ключей красно-чёрного дерева */
static inline int ep_cmp_ffd(struct epoll_filefd *p1,
                            struct epoll_filefd *p2)
{
  return (p1->file > p2->file ? +1:
     (p1->file < p2->file ? -1 : p1->fd - p2->fd));
}

Сначала функция ep_cmp_ffd() сравнивает с имеющимися данными адрес памяти из struct file. «Большей» считается структура с большим адресом.

Если адреса памяти совпадают (что возможно, так как несколько файловых дескрипторов могут ссылаться на один и тот же элемент struct file, например, благодаря dup()), то ep_cmp_ffd() просто сочтёт, что файл с большим файловым дескриптором «больше». Такой подход гарантирует то, что функция ep_cmp_ffd() способна сравнить любые два файловых дескриптора, которые не эквивалентны друг другу. Кроме того, если два файловых дескриптора идентичны, ep_cmp_ffd() вернёт 0.

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

Предположим, мы пытаемся добавить в экземпляр epoll файловый дескриптор. После того, как успешно отработает функция ep_find(), epoll_ctl() узнает о том, что ep_find() ничего не нашла. В противном случае работа ep_find() будет завершена с errno, установленным в EEXIST.

После этого epoll_ctl() вызовет ep_insert() для добавления в КЧ-дерево нового файлового дескриптора, а так же — для настройки некоторых структур данных и коллбэков, необходимых для получения уведомлений о событиях. Подробности о ep_insert() читайте в следующей статье.