company_banner

Реализация epoll, часть 1

Автор оригинала: Datong Sun
  • Перевод
Сегодня мы публикуем перевод первой статьи из серии материалов, посвящённых реализации 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() читайте в следующей статье.



Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

Подскажите, стоит ли переводить продолжение этого цикла статей о epoll?

  • 93,1%Да67
  • 6,9%Нет5
RUVDS.com
VDS/VPS-хостинг. Скидка 10% по коду HABR

Комментарии 15

    +3

    Интересна реализация epoll в многопотоке. Что происходит, когда работа с добавлением-удалением дескрипторов происходит одновременно из нескольких потоков? Что происходит при одновременном ожидании событий?

      0
      Как я понял после прочтения man7.org/linux/man-pages/man7/epoll.7.html,

      если все потоки работают с одним epoll fd, то

      1.1 добавлять можно, но при добавлении уже существующего fd получишь EEXIST; можно копировать fd, например через dup(), и тогда добавлять от каждого потока по своему (интересно, правда, где такое можно применить);
      1.2 с удалением, думаю, такя же история как и с добавлением;
      2) при одновременном ожидании события, получит событие только один поток (процесс, если унаследовал epoll fd, например при форке).
        0

        Не-не, эту логику работы я знаю. Но речь идёт о деталях реализации epoll. Вот мне и интересны эти детали.


        Например, имеет ли смысл балансировать нагрузку, работая с механизмом epoll из нескольких потоков? Или в ядре всё обложено мьютексами, и никакого преимущества по сравнению с работой из одного потока это не даст.

          0
          детали не подскажу, а в качестве примера, тот же nginx использует такую схему для балансировки нагрузки по процессам, при этом можно добиться равномерного распределения загрузки, избежав ситуации, когда 2 процесса обрабатывают большую часть, а другие простаивают
            0

            Не уверен, что nginx работает именно так. Насколько я понял, в каждом потоке — свой epoll, который не пересекается по дескрипторам с другими. А балансировка осуществляется на уровне accept и reuse_addr, т.е. просто создаётся несколько сокетов для прослушивания одного и того же порта.

              0
              да, вы правы. не правильно понял ваш вопрос.
              преимущество должно быть, два лучше, чем один :)
              хотя за деталями и сам сюда пришел. но пока не могу представить, в чем была бы затычка против «своего epoll», кроме того, что «первые» потоки будут работать чаще, пока евенты влезают в запрошенный объем, как следствие и делают «свой epoll».
        0

        Скорее всего, 1) Эффекты одновременных epoll_ctl могут применяться в любом порядке, тут никакой синхронизации, но воздействие на каждый дескриптор атомарно. 2) При готовности по epoll_wait будут разбужены все нити, которые успеют ухватить хотя бы по одному событию, но порядок формирования выходных списков не гарантирован, и может получиться какой угодно интерливинг.
        В документации я что-то подобное читал, но так как тестировать такие вещи сложно, то шансы на баг ненулевые.


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

        +1

        Интересная вещь, что все вещи в линуксе стараются (пере)делать на файловые дескрипторы. Кроме epoll'а, о чём речь в этой статье, туда же перемещаются например таймеры (timerfd), семафоры (eventfd), сигналы (signalfd).

          +2

          И это очень удобно. Вот в Windows есть IOCP, но таймеры и ивенты она не поддерживает, только сокеты и файлы, причём для сокетов и файлов используются разные вызовы.

            +1

            Таймеры и события — это объекты ожидания, они не производят операции ввода‐вывода, им IOCP ни к чему.


            Насколько знаю, порт завершения ввода‐вывода одинаково инициализируется для файлов и сокетов; на сокетах и файлах асинхронные операции запускаются одной и той же функцией ReadFile.

              0

              Верно. Но для ConnectEx и AcceptEx это решение не универсально.

            0

            Ну это удобно просто для учёта и лимитирования, если сравнивать, например, с BSD kqueue. Там есть аналогичные возможности, но они сидят внутри реализации и ограничения на них значительно глобальнее и топорнее.

            +3

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


            пользуясь случаем, правильно ли понимаю, что нет способа самому пробудить сокет с конкретным типом евента? (некий "fire_event(ep, fd, EPOLLIN)" речь про пробуждение из собственного кода, а не когда удалённая сторона действительно пишет данные, или отключается)
            пробовал по всякому, если писать в socket_fd(write/send), epollin не срабатывает.
            хотя shutdown на сокете все же пробуждает его как epollrdhup.(мог ошибиться, словом, как евент закрытия сокета)

              0
              пользуясь случаем, правильно ли понимаю, что нет способа самому пробудить сокет с конкретным типом евента?

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


              Если же надо пробудить весь комплект epoll в целом, то обычно используют сигнальный пайп, или, по-современному, eventfd.

                0
                Может быть epoll_ctl() с EPOLL_CTL_MOD сработает?
                Например, в качестве ивента можно передать EPOLLIN, что значит — файловый дескриптор готов к чтению.

                #include <sys/epoll.h>
                int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);


                man7.org/linux/man-pages/man2/epoll_ctl.2.html

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое