JEP 270: Reserved Stack Areas for Critical Sections

Аннотация

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

Цели

• Предоставить механизм, снижающий риск взаимных блокировок из-за повреждения критически важных данных, например блокировок java.util.concurrent (таких как ReentrantLock), когда в критической секции выбрасывается StackOverflowError.

• Решение должно быть в основном реализовано на уровне JVM, чтобы не требовать изменений ни в алгоритмах java.util.concurrent и опубликованных интерфейсах, ни в существующем коде библиотек и приложений.

• Решение не должно ограничиваться случаем ReentrantLock и должно быть применимо к любой критической секции в привилегированном коде.

Что не является целью

• Решение не ставит целью защитить непривилегированный код от переполнения стека.

• Решение не ставит целью избежать StackOverflowError. Его задача — снизить риск того, что такая ошибка будет выброшена внутри критической секции и тем самым повредит какие-либо структуры данных.

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

Мотивация

StackOverflowError — асинхронное исключение, которое виртуальная машина Java может выбросить, когда вычислениям в потоке требуется стек больше разрешённого (спецификация JVM, §2.5.2 и §2.5.6). The Java Language Specification разрешает синхронно выбрасывать StackOverflowError при вызове метода (JLS §11.1.3). HotSpot VM использует это свойство для реализации механизма «stack-banging» при входе в метод.

Механизм stack-banging — аккуратный способ сообщить о переполнении стека с сохранением целостности JVM, но он не даёт приложению безопасного способа восстановиться после такой ситуации. Переполнение стека может произойти посреди последовательности изменений, и если она не будет завершена, структура данных может остаться в несогласованном состоянии.

Например, если StackOverflowError выбрасывается в критической секции класса java.util.concurrent.locks.ReentrantLock, состояние блокировки может остаться несогласованным, что может привести к взаимным блокировкам. Класс ReentrantLock реализует свою критическую секцию с помощью экземпляра AbstractSynchronizerQueue. Его метод lock() реализован так:

final void lock() {
    if (compareAndSetState(0, 1))
        setExclusiveOwnerThread(Thread.currentThread());
    else
        acquire(1);
}

Метод пытается изменить слово состояния атомарной операцией. Если изменение прошло успешно, владелец устанавливается вызовом метода-сеттера, иначе вызывается медленный путь. Проблема в том, что если StackOverflowError выбрасывается после изменения слова состояния, но до фактической установки владельца, блокировкой больше нельзя пользоваться: её слово состояния говорит, что она захвачена, но владелец не установлен, поэтому ни один поток не может её освободить. Поскольку размер стека проверяется при вызове метода (по крайней мере, в HotSpot), StackOverflowError может быть выброшен либо при вызове Thread.currentThread(), либо при вызове setExclusiveOwnerThread(). В обоих случаях экземпляр ReentrantLock повреждается, и все потоки, пытающиеся захватить эту блокировку, блокируются навсегда.

Именно эта проблема вызвала серьёзные неполадки в JDK 7, потому что параллельная загрузка классов была реализована с помощью ConcurrentHashMap, а код ConcurrentHashMap в то время использовал экземпляры ReentrantLock. Если экземпляр ReentrantLock повреждался из-за StackOverflowError, взаимная блокировка могла возникнуть в самом механизме загрузки классов. (Это случалось в стресс-тестах (JDK-7011862), но могло случиться и в реальной эксплуатации.)

Реализация класса ConcurrentHashMap была полностью изменена в июне 2013 года. Новая реализация использует операторы synchronized вместо экземпляров ReentrantLock, поэтому в JDK 8 и последующих выпусках взаимная блокировка загрузки классов из-за повреждённых ReentrantLock не возникает. Однако любой код, использующий ReentrantLock, всё ещё может быть затронут и вызвать взаимную блокировку. О таких проблемах уже сообщалось в рассылке concurrency-interest@cs.oswego.edu.

Проблема не ограничивается классом ReentrantLock.

Корректная работа Java-приложений и библиотек часто зависит от согласованности структур данных. Любое изменение этих структур данных — критическая секция: до её выполнения структуры данных согласованы, и после её выполнения они тоже согласованы. Однако во время её выполнения структура данных может проходить через временные несогласованные состояния.

Если критическая секция состоит из одного Java-метода, который не вызывает других методов, текущий механизм обработки переполнения стека работает хорошо: либо доступного стека достаточно и метод выполняется без проблем, либо его недостаточно, и тогда StackOverflowError выбрасывается до выполнения первого байт-кода метода.

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

Описание

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

Основной механизм будет реализован в JVM. Единственное изменение, которое требуется в исходном коде на Java, — аннотация, которой должны помечаться критические секции. Эта аннотация, сейчас называемая jdk.internal.vm.annotation.ReservedStackAccess, — аннотация метода времени выполнения, которую может использовать любой класс привилегированного кода (о доступности этой аннотации см. абзац ниже).

Чтобы предотвратить повреждение общих структур данных, JVM будет пытаться отложить выброс StackOverflowError до тех пор, пока соответствующий поток не выйдет из всех своих критических секций. У каждого Java-потока на стеке выполнения определяется новая зона — зарезервированная зона. Ею можно пользоваться, только если в текущем стеке вызовов Java-потока есть метод с аннотацией jdk.internal.vm.annotation.ReservedStackAccess. Когда JVM обнаруживает переполнение стека, а в стеке вызовов потока есть аннотированный метод, JVM временно открывает доступ к зарезервированной зоне, пока в стеке вызовов не останется аннотированных методов. Когда доступ к зарезервированной зоне отзывается, выбрасывается отложенный StackOverflowError. Если в момент обнаружения переполнения стека в стеке вызовов потока нет аннотированного метода, StackOverflow выбрасывается немедленно (так JVM ведёт себя сейчас).

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

По умолчанию аннотация jdk.internal.vm.annotation.ReservedStackAccess действует только для привилегированного кода (кода, загруженного начальным загрузчиком классов или загрузчиком классов расширений). Этой аннотацией можно пометить и привилегированный, и непривилегированный код, но по умолчанию JVM будет игнорировать её для непривилегированного кода. Такая политика по умолчанию обоснована тем, что зарезервированное место на стеке для критических секций — ресурс, общий для всех критических секций. Если этим местом сможет пользоваться любой произвольный код, оно перестанет быть зарезервированным, и всё решение потеряет смысл. Есть флаг JVM, доступный даже в продуктовых сборках, который ослабляет эту политику и позволяет любому коду пользоваться этой возможностью.

Реализация

В HotSpot VM у каждого Java-потока в конце стека выполнения определены две зоны: жёлтая и красная. Обе области памяти защищены от любого доступа.

Если во время выполнения поток пытается обратиться к памяти в жёлтой зоне, возникает ошибка защиты, защита жёлтой зоны временно снимается, а StackOverflowError создаётся и выбрасывается. Перед раскруткой стека выполнения потока для распространения StackOverflowError защита жёлтой зоны восстанавливается.

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

Новая зона, которую определяет предлагаемое решение, располагается непосредственно перед жёлтой зоной. Эта зарезервированная зона будет вести себя как обычное место на стеке, если в стеке вызовов потока есть метод с аннотацией ReservedStackAccess, а в противном случае — как жёлтая зона.

При настройке стека выполнения Java-потока зарезервированная зона защищается так же, как жёлтая и красная зоны. Если во время выполнения поток достигает своей зарезервированной зоны, генерируется сигнал SIGSEGV, и обработчик сигнала применяет следующий алгоритм:

• Если адрес ошибки находится в красной зоне, сформировать отчёт об ошибке JVM и аварийный дамп.

• Если адрес ошибки находится в жёлтой зоне, создать и выбросить StackOverflowError.

• Если адрес ошибки находится в зарезервированной зоне, выполнить обход стека и проверить, есть ли в стеке вызовов метод с аннотацией jdk.internal.vm.annotation.ReservedStackAccess. Если нет, создать и выбросить StackOverflowError. Если аннотированный метод найден, снять защиту критической зоны и сохранить в C++-объекте Thread указатель стека самой внешней активации (фрейма), относящейся к аннотированному методу.

Если защита зарезервированной зоны была снята, чтобы критическая секция могла завершить выполнение, защиту нужно восстановить, а отложенный StackOverflowError выбросить, как только поток выйдет из критической секции. Интерпретатор HotSpot изменён так, чтобы проверять, не происходит ли выход из зарегистрированного самого внешнего аннотированного метода. Проверка выполняется при каждом удалении активации фрейма: восстанавливаемое значение указателя стека сравнивается со значением, сохранённым в C++-объекте Thread. Если восстановленный указатель стека выше сохранённого значения (стеки растут вниз), выполняется вызов среды выполнения, который меняет защиту памяти и сбрасывает значение указателя стека в объекте Thread, после чего происходит переход к коду генерации StackOverflowError. Оба компилятора изменены так, чтобы выполнять ту же проверку при выходе из метода, но только для методов с аннотацией ReservedStackAccess или методов, в скомпилированный код которых встроены аннотированные методы.

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

Выброс StackOverflowError — это способ, которым Java уведомляет приложение о том, что поток достиг предела стека. Однако исключения и ошибки иногда перехватываются кодом на Java, и уведомление теряется или обрабатывается некорректно, из-за чего расследовать проблему бывает очень трудно. Чтобы упростить диагностику ошибок переполнения стека при наличии зарезервированной области стека, JVM выдаёт ещё два уведомления, когда предоставляется доступ к зарезервированной области стека: первое — предупреждение, которое печатает JVM (в тот же поток вывода, что и все остальные сообщения JVM), второе — событие JFR. Обратите внимание: даже если отложенный StackOverflowError не выбрасывается, потому что в критической секции было выброшено другое исключение, предупреждение JVM и событие JFR всё равно формируются и доступны для диагностики.

Механизм зарезервированного стека управляется двумя флагами JVM: один задаёт размер зарезервированной зоны (у всех потоков он одинаковый), другой разрешает использовать механизм непривилегированному коду. Если задать размер зарезервированной зоны равным нулю, механизм полностью отключается. В отключённом состоянии интерпретируемый и скомпилированный код не выполняют проверку при выходе из метода.

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

Затраты производительности: измерения, выполненные с помощью тестов JSR-166 на ReentrantLock, не показали сколько-нибудь заметного влияния на производительность на платформах x86.

Производительность

Ниже описано, как это решение может повлиять на производительность.

Самая затратная операция в этом решении — обход стека при поиске аннотированного метода в стеке вызовов. Эта операция выполняется, только когда JVM обнаружила возможное переполнение стека. Без этого исправления JVM выбросила бы StackOverflowError. Поэтому, даже если операция относительно затратна, это лучше текущего поведения, поскольку она предотвратит повреждение данных. Чаще всего выполняемая часть этого решения — проверка при выходе из аннотированного метода, которая определяет, нужно ли снова включать защиту зарезервированной зоны. Критичная для производительности версия этой проверки находится в компиляторе. Текущая реализация добавляет в скомпилированный код аннотированного метода следующую последовательность кода:

0x00007f98fcef5809: cmp    rsp,QWORD PTR [r15+0x298]
0x00007f98fcef5810: jle    0x00007f98fcef583c
0x00007f98fcef5816: mov    rdi,r15
0x00007f98fcef5819: test   esp,0xf
0x00007f98fcef581f: je     0x00007f98fcef5837
0x00007f98fcef5825: sub    rsp,0x8
0x00007f98fcef5829: call   0x00007f9910f62670  ;   {runtime_call}
0x00007f98fcef582e: add    rsp,0x8
0x00007f98fcef5832: jmp    0x00007f98fcef583c
0x00007f98fcef5837: call   0x00007f9910f62670  ;   {runtime_call}

Этот код предназначен для платформы x86_64. В быстрых случаях (когда не нужно снова включать защиту зарезервированной зоны) он добавляет две инструкции, включая короткий переход. Версия для x86_32 больше, поскольку на этой платформе адрес объекта Thread не всегда доступен в регистре. Механизм также реализован для Solaris/SPARC.

Открытые вопросы

Размер зарезервированной зоны по умолчанию всё ещё остаётся открытым вопросом. Этот размер будет зависеть от самой длинной критической зоны в коде JDK, которая использует аннотацию ReservedStackAccess, а также от архитектуры платформы. Можно также рассмотреть разные значения по умолчанию в зависимости от того, работает ли JVM на мощном сервере или в среде с ограниченной виртуальной памятью.

Чтобы смягчить проблему выбора размера, добавлена функция для отладки и диагностики. Она включена по умолчанию в отладочных сборках и доступна как диагностическая опция JVM в продуктовых сборках. Если она активирована, она запускается, когда JVM собирается выбросить StackOverflowError: она обходит стек вызовов и, если находит один или несколько методов с аннотацией ReservedStackAccess, печатает их имена вместе с предупреждением в стандартный вывод JVM. Флаг JVM, управляющий этой функцией, называется PrintReservedStackAccessOnStackOverflow.

Размер зарезервированной области по умолчанию — одна страница (4K), и эксперименты показали, что этого достаточно, чтобы покрыть критические секции блокировок java.util.concurrent, аннотированных на данный момент.

Зарезервированная область стека поддерживается на платформах Windows не полностью. При разработке механизма для Windows была найдена ошибка в том, как управляются специальные зоны стека (JDK-8067946). Эта ошибка не позволяет JVM предоставить доступ к зарезервированной области стека. Поэтому, когда на Windows обнаруживается переполнение стека и в стеке вызовов есть аннотированный метод, JVM печатает предупреждение, генерируется событие JFR и сразу выбрасывается StackOverflowError. Для приложения поведение JVM не меняется. Однако предупреждение JVM и событие JFR могут помочь при диагностике, указывая, что возникла потенциально опасная ситуация.

Альтернативы

Рассматривалось несколько альтернативных подходов, и некоторые из них были реализованы и протестированы. Ниже приведён список этих подходов.

Решения на уровне языка:

• Конструкции try/catch/finally: они ничего не решают, поскольку нет гарантии, что блок finally тоже не вызовет переполнение стека.

• Новые конструкции, например:

  new CriticalSection(
         () -> {
             // do critical section code
          }).enter();

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

Решения на основе преобразования кода:

• Избегать вызовов методов (поскольку проверки переполнения стека выполняются в момент вызова метода), заставив JIT встраивать все вызываемые методы: встраивание может потребовать загрузки и инициализации классов, которые приложение не использует, принудительное встраивание может противоречить правилам компилятора (размер кода, глубина встраивания), и встраивание применимо не ко всем шаблонам кода (например, к рефлексии).

• Рефакторинг кода, чтобы избежать вызовов методов на уровне исходного кода: рефакторинг потребовал бы изменения и без того сложного кода (java.util.concurrent), а такой рефакторинг нарушил бы инкапсуляцию.

Решения на уровне стека:

• Расширенный stack banging: выполнять stack banging на большую глубину перед входом в критическую секцию. Это решение снижает производительность, даже когда переполнения стека нет, и его трудно поддерживать при вложенных критических секциях.

• Расширяемые стеки: строить стеки из нескольких несмежных фрагментов памяти, добавляя новый фрагмент при обнаружении переполнения стека. Это решение значительно усложняет JVM из-за необходимости управлять несмежными стеками (включая всю логику управления стеком, которая сейчас основана на сравнении указателей); кроме того, оно может потребовать копирования или перемещения некоторых участков стека и создаёт дополнительную нагрузку на механизм выделения памяти из-за фрагментации.

Тестирование

Это изменение сопровождается надёжным модульным тестом, который воспроизводит повреждение java.util.concurrent.lock.ReentrantLock, вызванное переполнением стека.

Зависимости

Зарезервированная область стека опирается на механизм «жёлтых страниц» (yellow pages). Сейчас этот механизм частично неисправен на Windows JDK-8067946, поэтому зарезервированная область стека на этой платформе поддерживается не полностью.