Для начала “терминология”:
Stop The World (STW) — это пауза в выполнении программы в Golang, необходимая для корректной работы сборщика мусора.
STW может негативно влиять на производительность приложений. Для уменьшения его влияния в языке используется алгоритм трёхцветной маркировки, который окрашивает объекты в чёрный, серый или белый цвет в стадии разметки.
1 | SA: |
Что нужно изучить
Proposal: Non-cooperative goroutine preemption(Некооперативное вытеснение для goroutine)
- Статья обсуждает проблемы с небезопасными точками в Go и предлагает альтернативы для их решения.
- Небезопасные точки могут вызывать проблемы с выживаемостью, перемещением стека и сложными альтернативами.
- Предлагается отказаться от небезопасных точек и повторить попытку позже, когда программа будет готова.
- Обсуждаются общие последствия использования сигналов для вытеснения запущенной программы.
- Предлагаются альтернативы для сигнализируемого вытеснения, включая нацеливание на определенные потоки и возобновление выполнения.
- Обсуждаются проблемы, связанные с одноступенчатыми переходами и переписыванием кода для перехода в безопасную точку.
- Предлагаются альтернативные подходы, такие как использование аппаратной одноступенчатой поддержки и переписывание следующей инструкции по прыжку в безопасную точку.
Устранение недостатков асинхронного вытеснения
В Go 1.14 введено асинхронное вытеснение, чтобы можно было вытеснять узкие циклы (# 10958). Однако все еще есть несколько незаконченных концов, которые нужно связать. Это общая ошибка для отслеживания оставшейся работы:
Аннотация (Abstract)
В настоящее время Go использует вставленные компилятором точки вытеснения сотрудничества в прологах функций. В большинстве случаев этого достаточно, чтобы позволить разработчикам Go игнорировать preemption и сосредоточиться на написании четкого параллельного кода, но у него есть острые углы, которые, как мы видели, снова и снова ухудшают опыт разработчиков. Когда что-то идет не так, все идет совершенно неправильно, что приводит к загадочным проблемам с задержкой в системе, а иногда и к полному зависанию. И поскольку это проблема языковой реализации, которая существует вне языковой семантики Go, эти сбои неожиданны и их очень трудно отладить.
@dr2chase приложил значительные усилия для создания прототипов точек вытеснения кооперативов в циклах, что является одним из способов решения этой проблемы. Однако даже сложные подходы к этому приводили к неприемлемым замедлениям в узких циклах (где замедления, как правило, наименее приемлемы).
Я предлагаю, чтобы реализация Go переключилась на вытеснение без сотрудничества, что позволило бы вытеснять программы практически в любой момент без необходимости явных проверок вытеснения. Такой подход решит проблему отложенного вытеснения и сделает это с нулевыми затратами времени выполнения.
Некооперативное упреждение - это общая концепция с целым классом методов реализации. В этом документе описывается и мотивируется переход на некооперативное преимущественное использование и обсуждаются общие проблемы любого некооперативного подхода к преимущественному использованию в Go. Конкретные подходы к реализации подробно описаны во вложенных предложениях, связанных с этим документом.
Справочная информация (Background)
До Go 1.10 включительно Go использовала совместное вытеснение с безопасными точками только при вызовах функций (и даже тогда, если функция маленькая или встроена). Это означает, что Go может переключаться между программами, выполняющимися одновременно, только в определенных точках. Основное преимущество этого заключается в том, что компилятор может гарантировать полезные инварианты в этих безопасных точках. В частности, компилятор гарантирует, что все локальные корни сборки мусора известны во всех безопасных точках, что критически важно для точной сборки мусора. Он также может гарантировать, что никакие регистры не будут активированы в безопасных точках, что означает, что среда выполнения Go может переключать подпрограммы без необходимости сохранять и восстанавливать большой набор регистров.
Однако это может привести к нечастым безопасным точкам, что приводит ко многим проблемам:
Наиболее распространенным в производственном коде является то, что это может задерживать операции STW, такие как запуск и завершение цикла GC. Это увеличивает задержку STW и при большом количестве ядер может существенно повлиять на пропускную способность (если, например, большинство потоков остановлено, пока среда выполнения ожидает отставшего в течение длительного времени). (#17831, #19241)
Это может задержать планирование, не позволяя конкурирующим программам выполняться своевременно.
Это может задержать сканирование стека, которое потребляет центральный процессор, пока среда выполнения ожидает точки вытеснения, и в конечном итоге может задержать завершение GC, что приводит к эффективному STW, когда в системе заканчивается куча и никакие программы не могут ее выделить.
В действительно экстремальных случаях это может привести к остановке программы, например, когда подпрограмма, работающая на атомной нагрузке, истощает подпрограмму, ответственную за настройку этой атомной нагрузки. Это часто указывает на плохой или глючный код, но, тем не менее, удивительно и явно отняло у разработчика много времени на отладку. (#543, #12553, #13546, #14561, #15442, #17174, #20793, #21053)
Эти проблемы снижают производительность разработчиков и эффективность производства и знакомят пользователей Go с деталями реализации, о которых им не следует беспокоиться.
Преимущественное использование кооперативного цикла (Cooperative loop preemption)
@dr2chase приложил значительные усилия, пытаясь решить эти проблемы с помощью кооперативного вытеснения цикла (# 10958). Это стандартный подход для сред выполнения, использующих совместное вытеснение, при котором компилятор вставляет проверки вытеснения и безопасные точки на задних ребрах графа потока. Это значительно улучшает качество вытеснения, поскольку код почти никогда не выполняется без поддержки в течение какого-либо нетривиального периода времени.
Наш самый последний подход к вытеснению циклов, который мы называем вытеснение на основе сбоев, добавляет единую инструкцию, без ветвей и давления регистра на циклы на платформах x86 и UNIX (CL 43050). Несмотря на это, геометрическое замедление по большому набору тестов составляет 7,8%, с несколькими значительно худшими выбросами. Даже по сравнению с Go 1.9, где замедление составляет всего 1% благодаря другим улучшениям, в большинстве тестов наблюдается некоторое замедление, и все еще наблюдаются значительные отклонения.
Вытеснение на основе ошибок также имеет несколько недостатков реализации. Оно не может быть нацелено на определенные потоки или подпрограммы, поэтому плохо подходит для сканирования стека, неровных барьеров или вытеснения обычного планировщика. Это также “залипание” в том смысле, что мы не можем возобновить какие-либо циклы, пока не возобновим все циклы, поэтому безопасная точка не может просто возобновиться, если это происходит в небезопасном состоянии (например, когда удерживаются блокировки во время выполнения). Требуется больше инструкций (и больше накладных расходов) на платформах, отличных от x86 и UNIX. Наконец, это мешает работе отладчиков, которые предполагают, что плохие ссылки на память являются веской причиной для остановки программы. Неясно, может ли оно вообще работать во многих отладчиках OS X из-за ошибки ядра.
Некооперативное вытеснение (Non-cooperative preemption)
Некооперативное вытеснение переключается между контекстами параллельного выполнения без явных проверок вытеснения или помощи со стороны этих контекстов. Это используется всеми современными настольными и серверными операционными системами для переключения между потоками. Без этого одно приложение с плохим поведением может заклинить всю систему, подобно тому, как одна программа с плохим поведением в настоящее время может заклинить приложение Go. Это также удобная абстракция: она позволяет нам программировать так, как будто доступно бесконечное количество процессоров, скрывая тот факт, что ОС выполняет временное мультиплексирование конечного числа процессоров.
Планировщики операционной системы используют поддержку аппаратных прерываний для переключения запущенного потока в планировщик ОС, который может сохранять состояние этого потока, например, его регистры процессора, чтобы его можно было возобновить позже. В Go мы бы использовали поддержку операционной системы, чтобы сделать то же самое. В UNIX-подобных операционных системах это можно сделать с помощью сигналов.
Однако из-за сборщика мусора у Go есть требования, которых нет у операционной системы: Go должен иметь возможность находить текущие указатели в стеке goroutine, где бы он ее ни останавливал. Большая часть сложности отказа от сотрудничества в Go проистекает из этого требования.
Предложение
В статье предлагается в Go реализовать вытеснение некооперативной подпрограммы, отправив сигнал POSIX (или используя эквивалентный механизм операционной системы), чтобы остановить запущенную программу goroutine и зафиксировать состояние ее процессора. Если подпрограмма прерывается в точке, которая должна быть GC atomic, как подробно описано в разделе “Обработка небезопасных точек”, среда выполнения может просто возобновить работу подпрограммы и повторить попытку позже.
Основная сложность реализации вытеснения без сотрудничества для Go заключается в поиске активных указателей в стеке вытесняемой подпрограммы. Существует множество возможных способов сделать это, которые подробно описаны в этих подпредложениях:
В предложении с безопасными точками везде описывается реализация, в которой компилятор записывает карты стека и регистра практически для каждой инструкции. Это позволяет среде выполнения останавливать goroutine в любом месте и находить ее корни GC.
В предложении по консервативному сканированию внутреннего фрейма описывается реализация, которая использует консервативные методы GC для поиска указателей в самом внутреннем фрейме стека вытесняемой подпрограммы goroutine. Это можно сделать без каких-либо дополнительных метаданных безопасной точки.
Обработка небезопасных точек (Handling unsafe-points)
Любой некооперативный подход вытеснения в Go должен иметь дело с кодовыми последовательностями, которые должны быть атомарными по отношению к сборщику мусора. Мы называем их “небезопасными точками”, в отличие от безопасных точек GC. Несколько известных ситуаций:
Выражения, включающие unsafe.Pointer, могут временно представлять единственный указатель на объект как uintptr. Следовательно, не должно быть безопасных точек, пока a uintptr производный от an unsafe.Pointer активен. Аналогично, мы должны распознавать преобразования reflect.Value.Pointer, reflect.Value.UnsafeAddr и reflect.Value.InterfaceData как unsafe.Pointerвuintptr. В качестве альтернативы, если компилятор может надежно обнаружить такие uintptrы, он может пометить их как указатели, но есть опасность, что промежуточное значение может не представлять допустимое значение указателя.
В барьере записи(write barrier) не должно быть безопасной точки между проверкой с включенным барьером записи и прямой записью. Например, предположим, что goroutine записывает указатель на B в объект A. Если проверка произойдет, то GC запустится и просканирует A, затем goroutine запишет B в A и удалит все ссылки на B из своего стека, сборщик мусора может не отметить B.
Есть места, где компилятор генерирует временные указатели, которые могут находиться за пределами конца выделения, например, в циклах диапазона над фрагментами и массивами. Этих действий следует либо избегать, либо запретить использование безопасных точек, пока они действуют.
Во всех этих случаях уже должно быть исключено существенное изменение порядка, чтобы избежать разделения по вызову. Внутренне это достигается с помощью псевдозначения “mem”, которое должно последовательно передаваться через все значения SSA, которые манипулируют памятью. Mem также передается через значения, которые нельзя изменять, даже если они не затрагивают память. Например, преобразование между unsafe.Pointer и uintptr выполняется с помощью специальной операции “Преобразовать”, которая использует mem исключительно для ограничения изменения порядка.
Существует несколько возможных решений этой проблемы, некоторые из которых можно комбинировать:
Мы могли бы отметить базовые блоки, которые не должны содержать точек вытеснения. Для unsafe.Pointer преобразований мы бы отказались от базового блока, содержащего преобразование. Для кода, соответствующего unsafe.Pointer правилам, этого должно быть достаточно, но это может привести к поломке кода, который является некорректным, но, как оказалось, работает сегодня способами, которые очень трудно отлаживать. Для барьеров записи этого также достаточно. Для циклов это слишком широко и потребует разделения некоторых базовых блоков.
Для unsafe.Pointer преобразований мы могли бы просто отказаться от целых функций, которые преобразуют из unsafe.Pointer в uintptr. Это было бы легко реализовать, и даже неисправный небезопасный код продолжал бы работать так же хорошо, как сегодня, но может иметь широкое влияние, особенно при наличии встраивания.
Простой комбинацией 1 и 2 было бы отказаться от любого базового блока, который достижим от преобразования unsafe.Pointer в uintptr, вплоть до вызова функции (что сегодня является безопасной точкой).
Для циклов диапазона компилятор мог бы скомпилировать их по-другому, чтобы он никогда не создавал указатель, выходящий за пределы (см. Ниже).
Гораздо более точным и общим подходом (благодаря @cherrymui) было бы создание новых операций SSA, которые “загрязняют” и “не загрязняют” память. Операция заражения возьмет mem и вернет новый поврежденный mem. Это заражение будет распространяться на любые значения, которые сами принимают поврежденное значение. Незапятнанная операция примет значение и mem и вернет незапятнанное значение и незапятнанный mem. Во время анализа жизнеспособности безопасные точки будут запрещены везде, где действовало испорченное значение. Это, вероятно, наиболее точное решение, которое, вероятно, сохранит даже неправильное использование unsafe working, но требует сложной реализации.
В более широком смысле, стоит подумать о том, чтобы заставить компилятор проверять код, использующий unsafe.Pointer, и активно отклонять код, который не соответствует разрешенным шаблонам. Это можно было бы реализовать как простую систему типов, которая отличает указатель uintptr от числового uintptr. Но это выходит за рамки данного предложения.
Циклы диапазона (Range loops)
Начиная с версии 1.10, циклы диапазона составляются примерно так:
1 | for i, x := range s { b } |
Проблема с этим понижением заключается в том, что _p может временно превышать конец распределения за момент до завершения цикла. В настоящее время это безопасно, потому что никогда не существует безопасной точки, пока это значение _p действует.
Это уменьшение требует, чтобы компилятор пометил блоки increment и condition как небезопасные точки. Однако, если тело короткое, это может привести к нечастым безопасным точкам. Это также требует создания отдельного блока для приращения, который в настоящее время обычно добавляется в конец основного текста. Разделение этих блоков ограничило бы возможности изменения порядка.
При подготовке к вытеснению без сотрудничества в Go 1.11 была начата компиляция циклов диапазона следующим образом, чтобы избежать создания указателя, переходящего в конец:
1 | i, _n, _p := 0, len(s), &s[0] |
Это позволяет использовать безопасные точки повсюду в цикле. По сравнению с исходной компиляцией цикла, он генерирует немного больше кода, но выполняет то же количество инструкций условного перехода (n + 1) и приводит к тому же количеству базовых блоков SSA (3).
Это снижение усложняет устранение проверки границ. В Go 1.10 устранение проверки границ знало об этом i < _n в теле, потому что в блоке body доминирует блок cond. Однако в новом понижении для получения этого факта потребовалось определить, что i < _n на обоих путях в тело и, следовательно, верно в теле.
Безопасные точки выполнения (Runtime safe-points)
Помимо сгенерированного кода, среда выполнения в целом не предназначена для произвольного вытеснения, и есть много мест, которые не должны вытесняться. Следовательно, мы, вероятно, отключили бы безопасные точки по умолчанию во время выполнения, за исключением вызовов (где они происходят сейчас).
Хотя это имело бы небольшие недостатки для большей части среды выполнения, есть некоторые части среды выполнения, которые могли бы существенно выиграть от вытеснения без сотрудничества, например, функции памяти, такие как memmove. Вытеснение без сотрудничества - отличный способ сделать их вытесняемыми без замедления общего случая, поскольку нам нужно было бы только пометить их карты регистров (которые часто были бы пустыми для функций типа memmove, поскольку все указатели уже были бы защищены аргументами).
Со временем мы можем использовать больше времени выполнения.
Небезопасный код стандартной библиотеки (Unsafe standard library code)
Пакет системного вызова Windows содержит множество unsafe.Pointer преобразований, которые не соответствуют unsafe.Pointer правилам. В целом он делает шаткие предположения о поведении безопасной точки, жизнеспособности и о том, когда может произойти перемещение стека. Вероятно, потребуется тщательный аудит или от него придется отказаться, как от среды выполнения.
Возможно, более тревожным является то, что некоторые типы пакетов системного вызова Windows имеют поля uintptr, которые на самом деле являются указателями, следовательно, вынуждая вызывающих выполнять небезопасные преобразования указателей. Например, смотрите Выпуск #21376 .
Обеспечение прогресса с небезопасными точками (Ensuring progress with unsafe-points)
Мы предлагаем просто сдаться и повторить попытку позже, когда подпрограмма прерывается в небезопасной точке. Одна из опасностей этого заключается в том, что безопасные точки могут быть редкими в узких циклах. Однако во многих случаях существуют более сложные альтернативы этому подходу.
При прерываниях во время выполнения или в функциях без каких-либо безопасных точек (таких как сборка) обработчик сигналов может размотать стек и вставить возвратный трамплин при следующем возврате к функции с метаданными безопасных точек. В этом случае среда выполнения могла бы позволить goroutine продолжить работу, и trampoline приостановил бы ее как можно скорее.
Для барьеров записи и unsafe.Pointer последовательностей компилятор мог бы вставить дешевую, явную проверку вытеснения в конце последовательности. Например, среда выполнения может изменить некоторый регистр, который будет проверяться в конце последовательности, и позволить потоку продолжить выполнение. В последовательности с барьером записи это может быть даже регистр, в который был загружен флаг с барьером записи, и компилятор может вставить простой тестовый регистр и условную ветвь в конце последовательности. Чтобы еще больше сократить последовательность, среда выполнения могла бы поместить адрес функции stop в этот регистр, чтобы последовательность stop была просто вызовом регистра и переходом.
Альтернативы этой проверке включают прямое и обратное моделирование. Прямое моделирование сложно, потому что компилятор должен быть осторожен, чтобы генерировать только операции, которые среда выполнения знает, как имитировать. Обратное моделирование легко, если компилятор всегда может сгенерировать перезапускаемую последовательность (просто верните компьютер к проверке флага ограничения записи), но быстро усложняется, если в последовательности выполняется несколько операций записи или более сложные операции записи, такие как DUFFCOPY.
Другие соображения (Other considerations)
Все предлагаемые подходы к вытеснению без сотрудничества включают остановку запущенной подпрограммы путем отправки ее потоку сигнала операционной системы. В этом разделе обсуждаются общие последствия этого.
Поддержка Windows. В отличие от вытеснения цикла на основе сбоя, сигнальное вытеснение довольно легко поддерживать в Windows, потому что оно предоставляет SuspendThread и GetThreadContext, которые упрощают получение набора регистров потока.
Выбор сигнала. Мы должны выбрать сигнал, который вряд ли будет мешать существующему использованию сигналов или отладчикам. Идеального выбора не существует, но есть некоторые эвристические приемы.
- Это должен быть сигнал, который по умолчанию передается отладчиками. В Linux это SIGALRM, SIGURG, SIGCHLD, SIGIO, SIGVTALRM, SIGPROF и SIGWINCH, плюс некоторые сигналы glibc-internal.
- Он не должен использоваться libc внутри в смешанных двоичных файлах Go / C, потому что libc может предположить, что это единственное, что может обрабатывать эти сигналы. Например, SIGCANCEL или SIGSETXID .
- Это должен быть сигнал, который может произойти непреднамеренно без последствий. Например, SIGALRM - плохой выбор, потому что обработчик сигнала не может определить, было ли это вызвано реальным сигналом тревоги процесса или нет (возможно, это означает, что сигнал нарушен, но я отвлекся). SIGUSR1 и SIGUSR2 также плохи, потому что они часто используются приложениями значимыми способами.
- Нам нужно иметь дело с платформами без сигналов реального времени (например, macOS), поэтому они исключены.
Мы используем SIGURG, потому что он соответствует всем этим критериям, крайне маловероятно, что он будет использоваться приложением в его “реальном” значении (как потому, что внеполосные данные в основном не используются, так и потому, что SIGURG не сообщает, у какого сокета есть условие, что делает его довольно бесполезным), и даже если это так, приложение должно быть готово к ложному SIGURG. SIGIO тоже был бы неплохим выбором, но, скорее всего, его будут использовать по-настоящему.
Преимущественное использование планировщика. Этот механизм хорошо подходит для временных вытеснений, когда одна и та же подпрограмма возобновляется после вытеснения, потому что нам не нужно сохранять полное состояние регистра и мы можем полагаться на существующий путь возврата сигнала для восстановления полного состояния регистра. Это применимо ко всем вытеснениям, связанным с GC, но не так хорошо подходит для постоянного вытеснения, выполняемого планировщиком. Тем не менее, мы все равно могли бы использовать этот механизм. Например, поскольку большую часть времени goroutines самостоятельно вытесняют сигнал, нам нужно сохранить полное состояние сигнала только в необычном случае, поэтому g может содержать указатель на его полное сохраненное состояние, которое используется только после принудительного вытеснения. Восстановление полного состояния сигнала может быть выполнено либо путем написания зависящего от архитектуры кода для восстановления полного набора регистров (усиленного runtime.gogo), либо путем самосигнализации, замены в желаемом контексте и предоставления ОС возможности восстановить полный набор регистров.
Нацеливание и возобновление. В отличие от прерывания цикла на основе сбоя, сигнальное прерывание может быть нацелено на определенный поток и может немедленно возобновиться. Нацеливание на потоки немного отличается от совместного вытеснения, которое ориентировано на горутины. Однако во многих случаях это на самом деле лучше, поскольку нацеливание программ на вытеснение является пикантным и, следовательно, требует циклов повторных попыток, которые могут значительно увеличить время STW. Использование этого для сканирования стека потребует некоторой реструктуризации того, как мы отслеживаем корни GC, но результат должен устранить блокирующий цикл повторных попыток, который мы используем в настоящее время.
Указатели без указателей. Это может привести к некорректному использованию unsafe.Pointer для временного хранения указателей без указателей. Такое использование является явным нарушением unsafe.Pointer правил, но оно может иметь место (особенно, например, в коде, использующем cgo).
Альтернативы (Alternatives)
Одноступенчатый (Single-stepping)
Вместо того, чтобы прилагать усилия для остановки на любой инструкции, компилятор мог бы выдавать метаданные для безопасных точек только на обратных фронтах, а среда выполнения могла бы использовать аппаратную поддержку одношагового перехода для продвижения потока к безопасной точке (или точке, где компилятор предоставил ответвление для достижения безопасной точки, как в текущем подходе с вытеснением цикла). Это работает (несколько неожиданно), но полностью сбивает с толку отладчики, поскольку и отладчик, и операционная система предполагают, что отладчик владеет single-stepping , а не самим процессом. Это также потребовало бы от компилятора предоставления заглушек для очистки регистров для этих безопасных точек, что увеличивает размер кода (и, следовательно, объем кэша инструкций), а также размер стека, во многом подобно вытеснению кооперативного цикла. Однако, в отличие от вытеснения кооперативного цикла, этот подход никак не повлияет на размер или производительность основного кода.
Быстрое переписывание (Jump rewriting)
Мы можем решить проблемы одношагового выполнения, вместо этого переписав следующую инструкцию перехода к безопасной точке после точки прерывания, чтобы перейти к пути упреждающего выполнения и возобновить выполнение как обычно. Чтобы упростить это, компилятор мог бы оставить достаточно места (с помощью NOPS заполнения), поэтому необходимо изменить только цель перехода.
Этот подход имеет обычные недостатки изменяемого кода. Это угроза безопасности, он нарушает совместное использование текстовых страниц и просто не разрешен в iOS. Он также не может быть нацелен на отдельную подпрограмму (поскольку другая подпрограмма может выполнять тот же код) и может иметь странные взаимодействия с параллельным выполнением на других ядрах.
Нестандартное исполнение (Out-of-line execution)
Еще одна альтернатива в том же духе, но не требующая изменения существующего текста, - это выполнение вне строки. При таком подходе обработчик сигналов перемещает поток команд из точки прерывания в следующую безопасную точку перехода во временный буфер, исправляет его для перехода во время выполнения в конце и возобновляет выполнение в этой перемещенной последовательности.
Это решает большинство проблем с одношаговым и скачкообразным перезаписыванием, но довольно сложно реализовать и требует значительных усилий по внедрению для каждой платформы. Это также запрещено в iOS.
Прецедент такого подхода уже есть. Например, когда Linux uprobes вводит INT3, он перемещает перезаписанные инструкции в область “выполнить вне очереди”, чтобы избежать обычных проблем с возобновлением работы с инструкцией INT3. Реализация на удивление проста, учитывая сложность кодирования инструкций x86, но все еще довольно сложна.
