Go under the hood
Go: Under the Hood

9.7 Кооперация и вытеснение

В 9.5 Цикл планирования остался открытый вопрос: если некоторая G выполняется слишком долго, как остальные G всё равно смогут получить время процессора? Ответ неизбежно апеллирует к паре понятий из теории планирования — кооперативному и вытесняющему. Кооперативное планирование опирается на добровольную уступку управления планируемой стороной; вытесняющее — на прерывание планируемой стороны планировщиком извне.

Рантайм Go не располагает возможностью аппаратного прерывания, подобной ядру операционной системы. Планировщик с перехватом работы (9.2) по своей сути является кооперативным планированием в порядке поступления. Вопрос в том, как он всё же способен принудительно прерывать G, отказывающуюся уступать управление, не отступая при этом от данного принципа — именно это и предстоит прояснить в настоящем разделе. Отправной точкой служит теоретический вопрос: почему рантайм не может остановить горутину в произвольной инструкции?

9.7.1 Точки безопасности: почему остановить можно не где угодно

Трудность вытеснения заключается не в самом «прерывании», а в том, чтобы «после него корректно возобновить выполнение и дать сборщику мусора возможность разобраться в стеке этой G». Go использует точную сборку мусора: GC должен знать для каждой остановленной G, содержит ли каждый слот стека и каждый регистр указатель или обычное целое число (13.4). Информация о том, «какие ячейки в данный момент являются указателями», называется картой стека и картой регистров; компилятор генерирует её лишь в определённых местах. Иными словами, программа не несёт полную информацию об указателях при каждой машинной инструкции; позиции, в которых GC может безопасно выполнить сканирование, образуют дискретное множество.

Такая позиция называется точкой безопасности (safe-point): достигнув её, поток предоставляет рантайму возможность полностью идентифицировать все ссылки на объекты. Беспечная остановка G за пределами точки безопасности — например, в середине последовательности барьера записи или между инструкциями, временно разбивающими указатель на целочисленную арифметику, — приведёт к тому, что сканирование пропустит или ошибочно интерпретирует указатель и нарушит корректность GC. Точки безопасности ограничивают «места, пригодные для остановки» дискретным множеством позиций, и это является основой любого механизма вытеснения.

Существуют два подхода к реализации точек безопасности. Первый — опрос (polling): компилятор вставляет небольшой проверочный код в точках безопасности, и G периодически спрашивает себя «хочет ли кто-то, чтобы я остановилась?»; обнаружив такой запрос, она кооперативно останавливается. Этот подход прост и переносим, однако несёт постоянные накладные расходы на выполнение проверочных инструкций и имеет принципиальное слепое пятно: если участок кода долго не проходит ни через одну точку безопасности (например, плотный цикл без вызовов функций), опрос никогда не выполняется и запрос игнорируется. Второй подход — вытесняющий: внешний поток принудительно прерывает цель, а затем каким-либо образом «перемещает» её в точку безопасности; недостатком является неконтролируемый момент прерывания, поэтому при попадании на небезопасную инструкцию необходимо уметь распознать это и отказаться от остановки.

Почему поток, слишком долго добирающийся до точки безопасности, тормозит всю систему? Потому что многие операции рантайма требуют глобальной паузы (stop-the-world, STW), прежде всего некоторые фазы GC. STW не может начаться, пока все G не остановятся в точках безопасности, поэтому суммарная стоимость определяется самым медленным потоком. Для этой величины существует устоявшееся обозначение — time-to-safepoint (TTSP). Поток с неконтролируемым TTSP, например попавший в бесконечный цикл, увеличивает задержку всей STW до неприемлемого уровня. Сокращение хвоста TTSP — это именно та инженерная задача, которую должен решить механизм вытеснения.

9.7.2 Кооперативное вытеснение: использование проверки расширения стека

Первоначальное вытеснение в Go было исключительно кооперативным и повторно использовало уже существующую точку безопасности: проверку расширения стека в прологе функции (14 Управление стеком выполнения). Каждая функция без атрибута nosplit при входе сравнивает указатель стека SP с g.stackguard0; если SP выходит за допустимые пределы, вызывается morestack, который переходит в newstack для расширения стека. Эта проверка является синхронной точкой безопасности: в данный момент стек G полон и пригоден для сканирования.

Вытеснение воспользовалось этим механизмом. Установив stackguard0 в сигнальное значение stackPreempt, превышающее любой реальный SP, следующая проверка стека при вызове функции гарантированно «провалится» и передаст управление в newstack, который отличает это от настоящего запроса на расширение стека:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// Сигнальное значение вытеснения: помещается в g.stackguard0 и гарантирует,
// что следующая проверка стека завершится неудачей и перейдёт в newstack.
// Превышает любой реальный SP (0xfffffade).
const stackPreempt = (1<<(8*goarch.PtrSize) - 1) & -1314

func newstack() {
    gp := getg().m.curg
    // Это запрос на вытеснение, а не настоящий запрос на расширение стека.
    preempt := gp.stackguard0 == stackPreempt
    if preempt {
        if !canPreemptM(gp.m) {
            // Рантайм находится в невытесняемом состоянии: отменить запрос, продолжить выполнение.
            gp.stackguard0 = gp.stack.lo + stackGuard
            gogo(&gp.sched)
        }
        if gp.preemptStop {
            preemptPark(gp) // Переход в парковку GC, не возвращается.
        }
        gopreempt_m(gp) // Аналогично добровольному вызову Gosched, уступает P.
    }
    // ... иначе это настоящее расширение стека.
}

canPreemptM ограничивает вытеснение безопасными состояниями рантайма. Функция требует, чтобы M не удерживала блокировок, не выполняла аллокацию памяти, не отключала вытеснение, а её P находилась в состоянии выполнения:

1
2
3
4
5
6

//go:nosplit
func canPreemptM(mp *m) bool {
    return mp.locks == 0 && mp.mallocing == 0 && mp.preemptoff == "" &&
        mp.p.ptr().status == _Prunning && mp.curg != nil &&
        readgstatus(mp.curg)&^_Gscan != _Gsyscall
}

Элегантность данного решения состоит в его нулевых дополнительных накладных расходах: никакой новой инструкции не добавляется — проверка вытеснения является той же самой проверкой переполнения стека, и рантайм получает точку останова бесплатно. gopreempt_m в конечном счёте проходит через тот же goschedImpl, что и runtime.Gosched (добровольная уступка пользователем), помещая G обратно в глобальную очередь и возвращаясь в цикл планирования. С точки зрения «записи живого состояния» это кооперативное вытеснение, происходящее в прологе функции, также наименее обременительно: здесь стековый фрейм аккуратен и информация об указателях полна, поэтому для чистого выхода достаточно сохранить PC и SP.

Платой за это является наследование принципиального слепого пятна опроса. Рассмотрим классическую программу:

1
2
3
4
5
6
7
8
9

func main() {
    runtime.GOMAXPROCS(1)
    go func() {
        for {
        } // Не содержит вызова функции, никогда не проходит через проверку стека.
    }()
    time.Sleep(time.Millisecond)
    println("OK") // До Go 1.14 никогда не выводилось.
}

Единственный P занят этим пустым циклом, тело которого не содержит вызовов функций; точка безопасности проверки стека никогда не выполняется, и установка stackPreempt лишена смысла. Главная горутина не может вернуть P, и программа зависает. Это в точности то слепое пятно опроса, о котором шла речь в 9.7.1, проявившееся в Go.

9.7.3 Асинхронное вытеснение: сигналы, инжекция и консервативное сканирование

Команда Go знала об этом слепом пятне с самого начала. После того как в Go 1.2 была добавлена маркировка вытеснения в прологе, проблема была отложена до накопления достаточного числа пользовательских сообщений (#10958). Примерно в версии 1.5 Остин Клементс предпринял попытку заставить компилятор вставлять проверки вытеснения на обратных переходах цикла (loop back-edges), а Дэвид Чейс оптимизировал это до единственной инструкции TESTB без ветвления и давления на регистры. Тем не менее на плотных циклах по-прежнему наблюдалось среднегеометрическое замедление около 7,8%. Нести постоянную инструкцию в горячем цикле ради события, которое почти никогда не происходит, в конечном счёте нецелесообразно.

Переломным моментом стало асинхронное вытеснение, появившееся в версии 1.14 (предложение #24543). Идея в точности совпадает с подходом операционной системы: внешний поток отправляет сигнал, принудительно прерывая целевой M, а в обработчике сигнала «перемещает» его в точку безопасности. Трудность именно та, что была предсказана в 9.7.1: сигнал может прийти на любую инструкцию, не обязательно являющуюся точкой безопасности.

Здесь есть деталь, о которой нередко сообщают неточно и которую стоит прояснить. Хотя #24543 озаглавлен «некооперативное вытеснение», принятая схема не генерирует точную карту регистров при каждой инструкции — подобные метаданные раздулись бы до неприемлемого размера. Реально принятым решением стал компромисс: сигнал инжектирует вызов asyncPreempt, и когда сканирование стека GC встречает стековый фрейм asyncPreempt, оно применяет консервативное сканирование к этому фрейму и его родительскому фрейму: каждое слово внутри фрейма, похожее на указатель кучи, считается живым указателем — предпочтительнее лишний раз удержать объект, чем пропустить метку. Ценой является небольшое количество плавающего мусора в точке прерывания; взамен отпадает необходимость подготавливать точную карту для каждой инструкции. Понимание этого «консервативного внутреннего фрейма» является ключом к пониманию асинхронного вытеснения в Go.

Поскольку требуется консервативное сканирование, точка остановки не может быть произвольной инструкцией. isAsyncSafePoint служит привратником: при поступлении сигнала она определяет, является ли текущий PC безопасным, и отвергает любую позицию, при которой консервативное сканирование даст некорректный результат:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// Определяет, может ли gp, остановленная на pc, быть асинхронно вытеснена
// (набросок: сохранена логика принятия решения, угловые случаи опущены).
func isAsyncSafePoint(gp *g, pc, sp, lr uintptr) (bool, uintptr) {
    mp := gp.m
    if mp.curg != gp { return false, 0 }       // Вытеснять только пользовательскую G.
    if mp.p == 0 || !canPreemptM(mp) { return false, 0 } // Те же условия безопасности, что и для кооперативного пути.
    if sp-gp.stack.lo < asyncPreemptStack { return false, 0 } // Стек должен быть достаточно велик для инжекции.

    f := findfunc(pc)
    if !f.valid() { return false, 0 }          // Не Go-код.
    up, _ := pcdatavalue2(f, abi.PCDATA_UnsafePoint, pc)
    if up == abi.UnsafePointUnsafe {
        return false, 0  // Точка, помеченная компилятором как небезопасная: барьер записи, атомарная последовательность, nosplit.
    }
    // Если имя самой внутренней (включая встроенные) функции принадлежит самому рантайму — никогда не вытеснять.
    name := /* имя innermost srcFunc */ ""
    if hasPrefix(name, "runtime.") || hasPrefix(name, "internal/runtime/") ||
        hasPrefix(name, "reflect.") {
        return false, 0
    }
    return true, pc
}

Отвергаемые случаи охватывают каждое место, где «остановка была бы ошибочной»: середину барьера записи или атомарной последовательности, внутренность функции nosplit, код на ассемблере и собственный код рантайма (планировщик, defer, внутренние атомарные операции и т. д., чьи стеки нередко содержат нетипизированные данные). Иными словами, асинхронное вытеснение воздействует только на аккуратную часть пользовательского кода.

В качестве сигнала для отправки выбран SIGURG. Этот выбор не случаен: в обычных условиях он используется только отладчиком для передачи сигналов, допускает «ложные» срабатывания без вреда (в отличие от SIGALRM, который необходимо обрабатывать при каждом получении), не конфликтует с SIGUSR1/2, широко используемыми в пользовательском коде, и совместим с платформами без сигналов реального времени (например, macOS). Вся цепочка инжекции устроена следующим образом; ключевой момент состоит в том, что обработчик сигнала может перезаписать контекст выполнения прерванного потока:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

const sigPreempt = _SIGURG

// Пришёл сигнал: если G хочет быть вытесненной и текущая точка является безопасной,
// перезаписать адрес возврата, инжектировав один вызов asyncPreempt.
func doSigPreempt(gp *g, ctxt *sigctxt) {
    if wantAsyncPreempt(gp) {
        if ok, newpc := isAsyncSafePoint(gp, ctxt.sigpc(), ctxt.sigsp(), ctxt.siglr()); ok {
            ctxt.pushCall(abi.FuncPCABI0(asyncPreempt), newpc) // Установить адрес возобновления на asyncPreempt.
        }
    }
    gp.m.preemptGen.Add(1) // Подтвердить, что данное вытеснение было обработано.
}

pushCall помещает исходный PC в стек, затем направляет адрес возобновления на asyncPreempt; поэтому, когда обработчик сигнала вернётся, прерванная G не возобновится с исходного места, а «из ниоткуда» исполнит вызов asyncPreempt. asyncPreempt написан на ассемблере; его задача — выгрузить все пользовательские регистры в стек и сохранить их (это также является причиной консервативного сканирования родительского фрейма), вызвать asyncPreempt2, а при возврате восстановить всё в исходное состояние — вытесненная G ничего не заметит:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

//go:nosplit
//go:nowritebarrierrec
func asyncPreempt2() {
    mcall(func(gp *g) {
        gp.asyncSafePoint = true
        if gp.preemptStop {
            preemptPark(gp)  // Парковка для GC.
        } else {
            gopreempt_m(gp)  // Уступить управление, вернуться в цикл планирования.
        }
    })
    getg().asyncSafePoint = false
}

Конечная точка совпадает с кооперативным путём: либо gopreempt_m уступает P, либо preemptPark выполняет парковку для GC.

9.7.4 Активация обоих путей одновременно: preemptone и sysmon

Кооперативный и асинхронный подходы не являются взаимоисключающими; единственный запрос на вытеснение активирует оба пути одновременно. preemptone — единая точка входа для запроса вытеснения G на некотором P; она устанавливает кооперативное сигнальное значение и отправляет асинхронный сигнал, срабатывая по тому пути, которого G достигнет первой:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func preemptone(pp *p) bool {
    mp := pp.m.ptr()
    gp := mp.curg
    // ... проверить, что mp, gp корректны и не находятся в системном вызове.
    gp.preempt = true
    gp.stackguard0 = stackPreempt // Кооперативно: следующая проверка стека сработает.
    if preemptMSupported && debug.asyncpreemptoff == 0 {
        pp.preempt = true
        preemptM(mp)              // Асинхронно: отправить SIGURG.
    }
    return true
}

Кто вызывает preemptone? Главным образом retake внутри системного монитора sysmon (9.6). Он периодически обходит все P и выполняет два различных вида «вытеснения»:

  • Изъятие P: когда G заблокирована в системном вызове, P отвязывается от M (handoffp) и передаётся другому M для выполнения других G. Прерывать при этом никого не нужно — G уже остановлена, и при возобновлении она самостоятельно найдёт P для привязки. Критерий — системный вызов превысил примерно один тик sysmon (20 мкс).
  • Прерывание M: когда G слишком долго выполняется в пользовательском коде (превышая временной квант forcePreemptNS, равный 10 мс), вызывается preemptone для её прерывания. Именно здесь вступают в игру описанные выше два пути.

Этот квант в 10 мс вместе с порогом системного вызова в 20 мкс задаёт верхнюю границу TTSP в Go: как бы упорно ни выполнялся цикл, не позднее чем через один квант он будет прерван по SIGURG. Сборщик мусора, когда ему необходимо перейти в режим STW, также проходит через тот же preemptone, однако устанавливает gp.preemptStop, направляя точку приземления на preemptPark, а не на уступку управления.

Объединение двух путей на одной диаграмме наглядно показывает структуру «один запрос, две растяжки»:

flowchart TD
    REQ["preemptone(P): таймаут sysmon / GC переходит в STW"]
    REQ --> COOP["Кооперативно: stackguard0 = stackPreempt"]
    REQ --> ASYNC["Асинхронно: preemptM отправляет SIGURG"]

    COOP -->|проверка стека при следующем вызове функции G| MORE["morestack -> newstack"]
    MORE -->|canPreemptM пройдена| YIELD

    ASYNC -->|ОС прерывает M, входит в sighandler| DSP["doSigPreempt"]
    DSP -->|isAsyncSafePoint пройдена| INJ["pushCall инжектирует asyncPreempt"]
    DSP -->|не в точке безопасности| DROP["Пропустить на этот раз, повторить позже"]
    INJ --> AP2["asyncPreempt2"]
    AP2 --> YIELD

    YIELD{"preemptStop?"}
    YIELD -->|нет| GP["gopreempt_m: уступить P, вернуться в цикл планирования"]
    YIELD -->|да| PP["preemptPark: парковка для GC"]

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

9.7.5 Сравнительный анализ: ось проектирования «опрос против асинхронности»

Рассмотрение Go в контексте эволюции языков показывает, что столкнувшееся слепое пятно характерно для данного класса языков. HotSpot JVM давно использует polling safe-points: поток опрашивает сторожевую страницу при возврате из методов, на обратных переходах цикла и т. д.; когда необходима пауза, страница делается нечитаемой, вызывая ловушку для сбора всех потоков. Это то же слепое пятно, что и в Go, но проявляется оно на счётных циклах: JIT для оптимизации удаляет опрос точки безопасности внутри цикла, и длинный счётный цикл может привести к неконтролируемому росту TTSP. Путь исправления в JVM отличается от подхода Go, но имеет общий корень: в JDK 10 введено loop strip mining — разбиение большого цикла на два уровня: внешний с опросом и внутренний без него, что сохраняет оптимизацию, одновременно ограничивая TTSP; JEP 312 пошёл дальше с thread-local handshakes — механизмом, позволяющим VM инициировать обратный вызов для отдельного потока без глобальной STW.

.NET выбирает другой путь — перехват (hijacking): рантайм приостанавливает целевой поток и временно перезаписывает его адрес возврата на заглушку рантайма, так что при первом же возврате поток попадает в руки рантайма. Это работает на том же принципе, что и использование сигнала в Go для перезаписи адреса возобновления и инжекции asyncPreempt — оба подхода представляют собой «вмешательство в поток управления с целью направить поток к точке безопасности».

Систематизация этих схем даёт чёткую ось проектирования: опрос против асинхронности. Опрос (ранние пролог-проверки Go, safe-points JVM) прост в реализации и переносим, но ограничен слепым пятном «точка опроса должна быть исполнена»; асинхронный подход (сигналы Go 1.14, перехват .NET, handshakes JEP 312) способен прервать в любой точке ценой строгой фильтрации момента остановки и обработки сложности консервативного сканирования или сохранения контекста. Решение Go 1.14 — использовать оба подхода: кооперативный как дешёвый штатный путь и асинхронный для устранения слепого пятна. Механизм активаций планировщика, представляющий собой «кооперативное уведомление ядра и пространства пользователя о блокировке», является ортогональным данной оси; он решает проблему параллелизма при блокировке M, а не TTSP отдельной G.

9.7.6 Эволюция и перспективы: дальнейшее сокращение STW

Ретроспективно: от полного отсутствия вытеснения до Go 1.0, к маркировке в прологе в версии 1.2 (слепое пятно которой вскрыл #10958), к эксперименту с вытеснением на обратных переходах цикла в версии 1.5 (не принятому повсеместно из-за потерь производительности), и наконец — к закрытию этого вопроса в версии 1.14 посредством предложения #24543 с применением сигналов и консервативного сканирования внутреннего фрейма. Движущей силой никогда не была «справедливость планирования» как таковая, а жёсткая потребность механизмов рантайма (особенно GC) в управляемом TTSP. Вытеснение существует для того, чтобы GC мог своевременно остановить каждую G.

Исследовательский фронт продолжает движение в том же направлении: ещё большее сокращение STW вплоть до его полного устранения. ZGC в HotSpot (JEP 376) реализовал конкурентную обработку стеков: стеки потоков сканируются и корректируются в конкурентной фазе GC, а не в STW, что снижает паузу до субмиллисекундных значений и делает её практически независимой от размера кучи. Это совпадает с целью постоянных усилий Go по сокращению STW (13 Сборка мусора): точки безопасности и вытеснение — это механизм ответа на вопрос «когда можно остановиться», а исследовательский фронт ищет ответ на вопрос «можно ли вообще не останавливаться».

При отладке, если требуется исключить влияние асинхронного вытеснения (например, небольшое количество плавающего мусора, которое оно порождает, или для исследования проблем, связанных с сигналами), можно воспользоваться GODEBUG=asyncpreemptoff=1 для его отключения и возврата к исключительно кооперативному поведению. Классическая программа с бесконечным циклом в этом случае снова зависнет, что может служить проверкой работоспособности механизма.

Дополнительные материалы

  1. Austin Clements. Proposal: Non-cooperative goroutine preemption. Go issue #24543, 2018. https://github.com/golang/go/issues/24543 (общий дизайн асинхронного вытеснения; включает ключевой компромисс «консервативного сканирования фрейма asyncPreempt и его родительского фрейма» вместо точной карты на протяжении всего кода)
  2. The Go Authors. runtime: tight loops should be preemptible. Go issue #10958, 2015. https://github.com/golang/go/issues/10958 (первоначальное сообщение о слепом пятне кооперативного вытеснения в прологе)
  3. Austin Clements, David Chase. Non-cooperative goroutine preemption (design doc). 2019. https://github.com/golang/proposal/blob/master/design/24543-non-cooperative-preemption (вытеснение на обратных переходах цикла, оптимизация TESTB и история потерь производительности в 7,8%)
  4. The Go Authors. Go 1.14 Release Notes: Goroutine preemption. 2020. https://go.dev/doc/go1.14#runtime (асинхронное вытеснение стало официально доступно; asyncpreemptoff)
  5. Nitsan Wakart. Safepoints: Meaning, Side Effects and Overheads. 2015. https://psy-lob-saw.blogspot.com/2015/12/safepoints.html (систематическое рассмотрение точек безопасности и TTSP)
  6. Aleksey Shipilëv. JVM Anatomy Quark #22: Safepoint Polls. 2019. https://shipilev.net/jvm/anatomy-quarks/22-safepoint-polls/ (анализ стоимости polling safe-points)
  7. JEP 312: Thread-Local Handshakes. OpenJDK, 2018. https://openjdk.org/jeps/312 (от глобальной STW к per-thread handshakes)
  8. JEP 376: ZGC Concurrent Thread-Stack Processing. OpenJDK, 2020. https://openjdk.org/jeps/376 (конкурентная обработка стеков, приближение к режиму без STW)
  9. Dmitry Vyukov. Go Preemptive Scheduler Design Doc. 2013. https://docs.google.com/document/d/1ETuA2IOmnaQ4j81AtTGT40Y4_Jr6_IDASEKg0t0dBR8/edit (самый ранний проект дизайна вытесняющего планировщика, предшествующий кооперативной схеме, появившейся до асинхронного вытеснения)
  10. David Chase. cmd/compile: loop preemption with fault branch on amd64. CL 43050, 2019. https://golang.org/cl/43050 (реализация вытеснения на обратном переходе через fault-branch, не принятая повсеместно из-за потерь производительности)
  11. The Go Authors. runtime/preempt.go, signal_unix.go, proc.go (retake/preemptone). https://github.com/golang/go/tree/master/src/runtime
  12. Эта книга: 9.5 Цикл планирования, 9.6 Системный мониторинг, 14 Управление стеком выполнения, 13.4 Сканирование и маркировка с помощью ассистента.