26.03.2021 00:26
ilammy 4 3200 Источник

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


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


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

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

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



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


В первой статье уже упоминалось, что на самом деле процессоры обмениваются сообщениями через шину вроде 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). То есть, если у CPU 1 или CPU 2 в их буферах записей окажутся значения для 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, их применение для оптимизации блокировок и важную роль в реализации неблокирующих связных списков.