Перевод Приёмы неблокирующего программирования полные барьеры памяти

В первых двух статьях цикла мы рассмотрели четыре способа упорядочить доступ к памяти: load-acquire и store-release операции впервой части, барьеры чтения и записи в память вовторой. Теперь пришла очередь познакомиться с полными барьерами памяти, их влиянием на производительность, и примерами использования полных барьеров в ядре Linux.

Рассмотренные ранее примитивы ограничивают возможный порядок исполнения операций спамятью четырьмя различными способами:

• Load-acquire операции выполняются перед последующими чтениями и записями.
• Store-release операции выполняются после предыдущих чтений и записей.
• Барьеры чтения разделяют предыдущие и последующие чтения из памяти.
• Барьеры записи разделяют предыдущие и последующие записи в память.

Внимательный читатель заметил, что одна из возможных комбинаций в этом списке отсутствует:

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

Что творится внутри процессоров

В первой статье уже упоминалось, что на самом деле процессоры обмениваются сообщениями через шину вроде QPI или HyperTransport, поддерживая таким образом когерентность кешей. На уровне ассемблера, правда, этого не видно. Там есть только инструкции записи и чтения из памяти. Acquire и release-семантика отдельных операций реализуется уже конвеером исполнения инструкций конкретного процессора, с учём его архитектурных особенностей.

Например, на x86-процессорах любое чтение из памяти это load-acquire операция, а любая запись это store-release, потому что так того требует спецификация архитектуры. Тем не менее, это ещё незначит, что в коде для x86 можно никак не обозначать acquire и release-операции. Барьеры влияют не только на процессор, но и на оптимизации компилятора, которые тоже могут переупорядочивать операции с памятью.

Кроме того, архитектура x86 негарантирует, что все процессоры будут видеть операции с памятью в одинаковом порядке. Рассмотрим следующий пример, где по адресам a и b изначально расположены нули:

    CPU 1                    CPU 2    -------------------      --------------------    store 1 => a             store 1 => b    load  b => x             load  a => y

Как бы вы ни переставляли эти операции между собой, как минимум одна из записей в память будет находиться перед соответствующим чтением. Соответственно, можно было бы ожидать, что либо в x, либо в y, либо в обоих окажется единица. Но даже на x86 может случиться так, что ивx, ивy будут считаны нули.

Почему? Дело в том, у каждого процессора есть так называемый буфер записей (store buffer), находящийся между процессором и его L1-кешем. Запись в память обычно изменяет только часть кеш-линии. Если кеш-линия инвалидирована, то процессору сперва надо достать новые данные из памяти аэто медленно. Поэтому новые данные для записи складываются в буфер, который позволяет процессору продолжить работу не ожидая обновления кеша.

Буфер записей не особо мешает процессорам сохранить глобальный порядок операций с памятью, когда это чтениечтение, чтениезапись, записьзапись:

• Если процессор переупорядочивает инструкции в конвеере для увеличения производительности (out-of-order execution), то механизм спекулятивного исполнения инструкций может сохранять порядок операций относительно чтений из памяти. Процессор начинает отслеживать кеш-линии смомента их чтения и до момента, когда инструкция чтения покидает конвеер. Если на этом промежутке кеш-линия оказывается вытеснена из кеша, то все спекулятивно исполненные и незавершённые операции, зависящие от считанного значения, требуется повторить, считав новое значение из памяти. Если же отслеживаемая кеш-линия остаётся на месте, то все последующие операции спамятью будут завершены после чтения, так как инструкции покидают конвеер и завершают исполение уже впорядке их следования впрограмме.
• Сохранить порядок записей между собой ещё проще: каждому процессору достаточно переносить записи в кеш в порядке их поступления в буфер записей. Дальше протокол когерентности всё сделает сам.

Но вот гарантировать, что только что записанное одним процессором значение будет считано другим процессором это гораздо сложнее. Во-первых, новое значение может застрять на некоторое время в буфере записей одного процессора, и пока оно не попадёт в L1-кеш, другие процессоры его не увидят. Во-вторых, чтобы процессор всегда видел свои же записи, все чтения сперва проходят через буфер записей (механизм store forwarding). То есть, если у CPU1 или CPU2 вих буферах записей окажутся значения для b и a соответственно, то они увидят именно их предыдущие значения (нули), независимо от состояния кешей.

Единственный способ получить ожидаемое поведение это сбросить весь буфер записей вкеш после записи и перед чтением. Несамая дешёвая операция (пара-тройка десятков циклов), но именно это делает полный барьер памяти smp_mb() в Linux. Рассмотрим теперь, как это выглядит наC:

    поток 1                       поток 2    -------------------           --------------------    WRITE_ONCE(a, 1);             WRITE_ONCE(b, 1);    smp_mb();                     smp_mb();    x = READ_ONCE(b);             y = READ_ONCE(a);

Допустим, в x получается ноль. Что должно для этого произойти? Волнистой линией обозначим ситуацию, когда WRITE_ONCE(b,1) не успевает перезаписать значение, считываемое другим потоком. (Вмодели памяти ядра такое отношение называется from-reads.) Поведение потоков можно описать так:

    WRITE_ONCE(a, 1);           |      -----+----- smp_mb();           |           v    x = READ_ONCE(b);   >  WRITE_ONCE(b, 1);                                         |                                    -----+----- smp_mb();                                         |                                         v                                  y = READ_ONCE(a);

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

Полный барьер в потоке2 гарантирует, что к моменту выполнения READ_ONCE(a) буфер записей будет сброшен в кеш. Если это произойдёт перед READ_ONCE(b), то она уже увидит запись WRITE_ONCE(b,1) и в x должна будет оказаться единица. Соответственно, если там оказался ноль, порядок выполнения должен быть другим READ_ONCE(b) должна выполниться первой:

    WRITE_ONCE(a, 1);              WRITE_ONCE(b, 1);           |                              |           |                         -----+----- smp_mb();           |                              |           v                              v    x = READ_ONCE(b); -----------> y = READ_ONCE(a);                      (если x = 0)

Благодаря транзитивности, READ_ONCE(a) втаком случае увидит эффект WRITE_ONCE(a,1) и, соответственно, y=1 когда x=0. Аналогично, если второй поток всё ещё видит ноль вa, то полный барьер в первом потоке гарантирует, что READ_ONCE(a) выполнится перед READ_ONCE(b):

    WRITE_ONCE(a, 1);              WRITE_ONCE(b, 1);           |                              |      -----+----- smp_mb();               |           |                              |           v                              v    x = READ_ONCE(b); <----------- y = READ_ONCE(a);                      (если y = 0)

То есть, если y=0, то обязательно x=1. Порядок выполнения операций негарантируется, но каким бы он ни оказался, x и y теперь немогут одновременно содержать нули. Иначе READ_ONCE(a) должна была бы выполниться перед READ_ONCE(b), а READ_ONCE(b) перед READ_ONCE(a), что невозможно.

Модель памяти Linux не считает такие ситуации отношением happens-before между потоками, ведь ни одна из операций не имеет acquire или release-семантики и порядок между ними, строго говоря, не определён. Но тем не менее, барьеры памяти всё же способны влиять на поведение потоков, что позволяет писать высокоуровневые примитивы синхронизации, пользователи которых могут рассчитывать на вполне определённое неопределённое поведение. Рассмотрим теперь, как барьеры применяются на практике.

Синхронизация сна и пробуждения

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

Рассмотрим типичный пример. Пусть один поток хочет попросить другой что-то сделать. Адругой поток часто бывает занят, либо вообще устаёт работать и хочет поспать самоудаляется из планировщика потоков и отправляется на неопределённое время всон. Первому потоку надо растормошить второй. Вкоде это выглядит как-то так:

    поток 1                               поток 2    -------------------                   --------------------------    WRITE_ONCE(dont_sleep, 1);            WRITE_ONCE(wake_me, 1);    smp_mb();                             smp_mb();    if (READ_ONCE(wake_me))               if (!READ_ONCE(dont_sleep))      wake(thread2);                        sleep();

Если второй поток видит в dont_sleep ноль, то первый поток увидит в wake_me единицу иразбудит второй поток. Выглядит, как будто у первого потока release-семантика (представьте, что wake() это как mutex_unlock()). Если же первый поток увидит в wake_me ноль, то второй поток обязательно увидит единицу в dont_sleep и просто непойдёт спать. Второй поток это как бы acquire-половинка операции.

Всё это держится на предположении, что команды первого потока нетеряются. Если, например, wake() вызывается после READ_ONCE() во втором потоке, но до sleep(), то второй поток недолжен витоге заснуть. Как вариант, эти операции могут блокироваться на общем мьютексе. Вот вам ещё один пример того, как неблокирующие приёмы программирования применяются вместе с традиционной синхронизацией. Вданном случае это неявляется проблемой, так как блокировки будут очень редкими.

Приём действительно работает и применяется, например, в интерфейсах prepare_to_wait() и wake_up_process(). Они были добавлены в ядро ещё в ветке 2.5.x, что в своё время подробно разбиралось наLWN. Если раскрыть вызовы функций, то можно увидеть знакомые строки:

    поток 1                                       поток 2    -------------------                           --------------------------    WRITE_ONCE(condition, 1);                     prepare_to_wait(..., TASK_INTERRUPTIBLE) {    wake_up_process(p) {                            set_current_state(TASK_INTERRUPTIBLE) {      try_to_wake_up(p, TASK_NORMAL, 0) {             WRITE_ONCE(current->state, TASK_INTERRUPTIBLE);        smp_mb();                                     smp_mb();        if (READ_ONCE(p->state) & TASK_NORMAL)      }          ttwu_queue(p);                          }      }                                           if (!READ_ONCE(condition))    }                                               schedule();

Как и с seqcount, все барьеры спрятаны за удобным высокоуровневым API. Собственно, как раз использование барьеров или load-acquire/store-release операций и придаёт acquire- или release-семантику всему интерфейсу. Вданном случае wake_up_process() обладает release-семантикой, аset_current_state() распространяет свою acquire-семантику на вызов prepare_to_wait().

Ещё часто бывает, что флажок проверяют дважды, дабы по возможности избежать лишних вызовов wake():

    поток 1                               поток 2    -------------------                   --------------------------    WRITE_ONCE(dont_sleep, 1);            if (!READ_ONCE(dont_sleep)) {    smp_mb();                               WRITE_ONCE(wake_me, 1);    if (READ_ONCE(wake_me))                 smp_mb();      wake(thread2);                        if (!READ_ONCE(dont_sleep))                                              sleep();                                          }

В ядре подобные проверки можно найти в tcp_data_snd_check(), вызываемой из tcp_check_space() одним потоком и tcp_poll() в другом потоке. Код здесь довольно низкоуровневый, так что разберём его подробнее. Если в буфере сокета закончилось место, то надо подождать, пока оно освободится. tcp_poll() в одном потоке устанавливает флаг SOCK_NOSPACE раз места нет, то надо спать перед проверкой __sk_stream_is_writeable(), вот здесь:

    set_bit(SOCK_NOSPACE, &sk->sk_socket->flags);    smp_mb__after_atomic();    if (__sk_stream_is_writeable(sk, 1))      mask |= EPOLLOUT | EPOLLWRNORM;

Если возвращаемая маска будет пустой, то для вызывающего кода это означает, что сокет не готов (и надо ждать, пока будет готов). smp_mb__after_atomic() это специализированная версия smp_mb() с аналогичной семантикой. Коптимизациям барьеров мы ещё вернёмся, но позже.

Другой поток, занятый отправкой данных из сокета, должен впоследствии разбудить первый поток. tcp_data_snd_check() сперва отправляет TCP-пакеты, освобождая место в буфере можно неспать, место появилось затем проверяет флажок SOCK_NOSPACE, и наконец (через указатель нафункцию sk->sk_write_space()) попадает в sk_stream_write_space(), где флажок сбрасывается и если там кто-то спит, то его будят. Вызовов функций тут немного, так что я думаю, вы сами легко разберётесь. Также обратите внимание на комментарий в tcp_check_space():

    /* pairs with tcp_poll() */    smp_mb();    if (test_bit(SOCK_NOSPACE, &sk->sk_socket->flags))      tcp_new_space(sk);

Парное использование барьеров означает, что функции составляют взаимосвязанную пару операций с acquire и release-семантикой. По барьерам чтения или записи в память легко понять, какая у чего семантика: acquire для чтения, release для записи. Сполными барьерами же для понимания семантики следует читать код вокруг них и думать. Внашем случае мы знаем, что функция, инициирующая пробуждение tcp_check_space() обладает release-семантикой. Соответственно, у tcp_poll() acquire-семантика.

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

• Workqueues таким образом решают, может ли рабочий поток отправиться поспать, если ему больше нечего делать. Будильником здесь выступает insert_work(), тогда как wq_worker_sleeping(), очевидно, хочет спать.
• Системный вызов futex() с одной стороны имеет пользовательский поток, записывающий новое значение в память, а барьеры являются частью futex(FUTEX_WAKE). Сдругой стороны находится поток, выполняющий futex(FUTEX_WAIT) и все операции с флажком wake_me внутри ядра. futex(FUTEX_WAIT) получает через аргумент ожидаемое значение в памяти, и потом решает, надо ли спать или уже нет. См.длинный комментарий в начале kernel/futex.c, где подробно рассматривается этот механизм.
• В контексте KVM роль сна играет переход процессора в гостевой режим, когда он отдаётся враспоряжение виртуальной машины. Для того, чтобы выбить процессор из рук гостевой ОС ивернуть его себе обратно, kvm_vcpu_kick() отправляет межпроцессорное прерывание. Вглубине стека вызовов можно найти kvm_vcpu_exiting_guest_mode(), где видно знакомые нам комментарии о парных барьерах вокруг флажка vcpu->mode.
• В драйверах virtio можно найти два места, где smp_mb() используется похожим образом. Содной стороны находится драйвер, который иногда хочет прервать операцию и пинает занятое устройство прерыванием. Сдругой стороны есть устройство, которому иногда надо отсигналить ожидающему драйверу о завершении операции.

На этом знакомство с барьерами памяти оглашается оконченным. Вследующей части мы примемся за операции compare-and-swap, их применение для оптимизации блокировок и важную роль вреализации неблокирующих связных списков.