что такое глубина стека
Что такое стек
И почему так страшен стек-оверфлоу.
Постепенно осваиваем способы организации и хранения данных. Уже было про деревья, попробуем про стеки. Это для тех, кто хочет в будущем серьёзно работать в ИТ: одна из фундаментальных концепций, которая влияет на качество вашего кода, но не касается какого-то конкретного языка программирования.
👉 Стек — это одна из структур данных. Структура данных — это то, как хранятся данные: например, связанные списки, деревья, очереди, множества, хеш-таблицы, карты и даже кучи (heap).
Как устроен стек
Стек хранит последовательность данных. Связаны данные так: каждый элемент указывает на тот, который нужно использовать следующим. Это линейная связь — данные идут друг за другом и нужно брать их по очереди. Из середины стека брать нельзя.
👉 Главный принцип работы стека — данные, которые попали в стек недавно, используются первыми. Чем раньше попал — тем позже используется. После использования элемент стека исчезает, и верхним становится следующий элемент.
Классический способ объяснения принципов стека звучит так: представьте, что вы моете посуду и складываете одинаковые чистые тарелки стопкой друг на друга. Каждая новая тарелка — это элемент стека, а вы просто добавляете их по одной в стек.
Когда кому-то понадобится тарелка, он не будет брать её снизу или из середины — он возьмёт первую сверху, потом следующую и так далее.
🤔 Есть структура данных, похожая на стек, — называется очередь, или queue. Если в стеке кто последний пришёл, того первым заберут, то в очереди наоборот: кто раньше пришёл, тот раньше ушёл. Можно представить очередь в магазине: кто раньше её занял, тот первый дошёл до кассы. Очередь — это тоже линейный набор данных, но обрабатывается по-другому.
Стек вызовов
В программировании есть два вида стека — стек вызовов и стек данных.
Когда в программе есть подпрограммы — процедуры и функции, — то компьютеру нужно помнить, где он прервался в основном коде, чтобы выполнить подпрограмму. После выполнения он должен вернуться обратно и продолжить выполнять основной код. При этом если подпрограмма возвращает какие-то данные, то их тоже нужно запомнить и передать в основной код.
Чтобы это реализовать, компьютер использует стек вызовов — специальную область памяти, где хранит данные о точках перехода между фрагментами кода.
Допустим, у нас есть программа, внутри которой есть три функции, причём одна из них внутри вызывает другую. Нарисуем, чтобы было понятнее:
Программа запускается, потом идёт вызов синей функции. Она выполняется, и программа продолжает с того места, где остановилась. Потом выполняется зелёная функция, которая вызывает красную. Пока красная не закончит работу, все остальные ждут. Как только красная закончилась — продолжается зелёная, а после её окончания программа продолжает свою работу с того же места.
А вот как стек помогает это реализовать на практике:
Программа дошла до синей функции, сохранила точку, куда ей вернуться после того, как закончится функция, и если функция вернёт какие-то данные, то программа тоже их получит. Когда синяя функция закончится и программа получит верхний элемент стека, он автоматически исчезнет. Стек снова пустой.
С зелёной функцией всё то же самое — в стек заносится точка возврата, и программа начинает выполнять зелёную функцию. Но внутри неё мы вызываем красную, и вот что происходит:
При вызове красной функции в стек помещается новый элемент с информацией о данных, точке возврата и указанием на следующий элемент. Это значит, что когда красная функция закончит работу, то компьютер возьмёт из стека адрес возврата и вернёт управление снова зелёной функции, а красный элемент исчезнет. Когда и зелёная закончит работу, то компьютер из стека возьмёт новый адрес возврата и продолжит работу со старого места.
Переполнение стека
Почти всегда стек вызовов хранится в оперативной памяти и имеет определённый размер. Если у вас будет много вложенных вызовов или рекурсия с очень большой глубиной вложенности, то может случиться такая ситуация:
Переполнение — это плохо: данные могут залезать в чужую область памяти и записывать себя вместо прежних данных. Это может привести к сбою в работе других программ или самого компьютера. Ещё таким образом можно внедрить в оперативную память вредоносный код: если программа плохо работает со стеком, можно специально вызвать переполнение и записать в память что-нибудь вредоносное.
Стек данных
Стек данных очень похож на стек вызовов: по сути, это одна большая переменная, похожая на список или массив. Его чаще всего используют для работы с другими сложными типами данных: например, быстрого обхода деревьев, поиска всех возможных маршрутов по графу, — и для анализа разветвлённых однотипных данных.
Стек данных работает по такому же принципу, как и стек вызовов — элемент, который добавили последним, должен использоваться первым.
Что дальше
А дальше поговорим про тип данных под названием «куча». Да, такой есть, и с ним тоже можно эффективно работать. Стей тюнед.
Powershell и глубина стека
Как разработчик, я часто разрабатываю скрипты развертывания. В одном из проектов передо мной возникла задача автоматизировать развертывание проекта, которое состояло из нескольких десятков заданий, с возможностью настраивать состав разворачиваемых на стенд компонентов.
В первую очередь была проведена работа по унификации интерфейсов заданий и были выделены следующие методы:
Учитывая, что подобных шагов становилось все больше и больше, поддерживать в таком виде скрипты становилось все сложнее. Изучив возможные решения, было принято решение реализовать каждое задание как отдельный объект:
В таком виде скрипты развертывания работали продолжительное время и ничто не предвещало беды. В один прекрасный момент передо мной встала задача провести развертывание на удаленном сервере. В powershell есть очень удобный механизм WinRM, который мы ранее очень активно использовали, и, соответственно, для решения поставленной задачи остановился на нем-же.
Решение работало нестабильно. На некоторых заданиях развертывания возникали либо ошибка либо Invoke-Command показывал, что удаленный скрипт выполнился корректно, но по факту он прерывался.
Не удалось обработать данные удаленной команды. Сообщение об ошибке: Ведущий процесс поставщика WSMan не вернул правильный ответ. Поставщик в ведущем процессе может вести себя неправильно
Processing data for a remote command failed with the following error message: The WSMan provider host process did not return a proper response. A provider in the host process may have behaved improperly.
В EventViewer смог найти, что процесс на удаленной машине завершался с ошибкой 1726, но никакой вразумительной информации об ошибке обнаружить не удавалось. При этом запуск того-же самого задания на удаленной машине всегда завершалось успешно.
В ходе многочисленных экспериментов поймал в ошибку The script failed due to call depth overflow которая определила дальнейшее направление исследований.
Со времен PowerShell v2 максимальная глубина стека в скриптах powershell составляет 1000 вызовов, в последующих версиях это значение было еще существенно поднято и ошибок типа stack overflow никогда не возникало.
Решил провести несколько тестов для определения глубины стека при вызове локально и через WinRM. Для этого подготовил инструментарий тестирования.
Первый тест определял возможную глубину рекурсии:
По результату — локально глубина стека более 3000, удаленно — немного больше 150.
150 — довольно большое значение. Достичь его в реальной работе скриптов развертывания нереально.
Второй тест определяет возможную глубину рекурсии при использовании объектов:
Результаты немного хуже. Удаленно глубина стека 130-133. Но для работы это тоже очень большое значение.
Дальнейшее изучение исходных скриптов развертывания натолкнуло на мысль проверить, как работают try-catch блоки:
И вот тут меня ожидал огромный сюрприз. При использовании «объектов» и генерации исключительной ситуации возможная глубина стека локально составила около 130, а удаленно всего 5.
Но при отказе от использования «объектов» проблема исчезала. Значения глубины стека оказались на уровне первого теста.
В powershell 5 появились классы. Провел тест с их использованием:
Особого выигрыша не получили. При вызове через WinRM глубина стека составила всего 7 хопов. Чего так-же недостаточно для нормальной работы скриптов.
Работая со скриптами тестирования пришла мысль реализовать объекты при помощи hash + script block.
Глубина стека в 55 хопов — это уже вполне достаточное значение.
О стеке простыми словами — для студентов и просто начинающих
Привет, я студент второго курса технического университета. После пропуска нескольких пар программирования по состоянию здоровья, я столкнулся с непониманием таких тем, как «Стек» и «Очередь». Путем проб и ошибок, спустя несколько дней, до меня наконец дошло, что это такое и с чем это едят. Чтобы у вас понимание не заняло столько времени, в данной статье я расскажу о том что такое «Стек», каким образом и на каких примерах я понял что это такое. Если вам понравится, я напишу вторую часть, которая будет затрагивать уже такое понятие, как «Очередь»
Теория
На Википедии определение стека звучит так:
Стек (англ. stack — стопка; читается стэк) — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).
Поэтому первое, на чем бы я хотел заострить внимание, это представление стека в виде вещей из жизни. Первой на ум мне пришла интерпретация в виде стопки книг, где верхняя книга — это вершина.
На самом деле стек можно представить в виде стопки любых предметов будь то стопка листов, тетрадей, рубашек и тому подобное, но пример с книгами я думаю будет самым оптимальным.
Итак, из чего же состоит стек.
Стек состоит из ячеек(в примере — это книги), которые представлены в виде структуры, содержащей какие-либо данные и указатель типа данной структуры на следующий элемент.
Сложно? Не беда, давайте разбираться.
На данной картинке схематично изображен стек. Блок вида «Данные/*next» и есть наша ячейка. *next, как мы видим, указывает на следующий элемент, другими словами указатель *next хранит адрес следующей ячейки. Указатель *TOP указывает на вершину стек, то есть хранит её адрес.
С теорией закончили, перейдем к практике.
Практика
Для начала нам нужно создать структуру, которая будет являться нашей «ячейкой»
Новичкам возможно будет не понятно, зачем наш указатель — типа comp, точнее сказать указатель типа структуры comp. Объясню, для того чтобы указатель *next мог хранить структуру comp, ей нужно обозначить тип этой структуры. Другими словами указать, что будет хранить указатель.
После того как у нас задана «Ячейка», перейдем к созданию функций.
Функции
Функция создания «Стека»/добавления элемента в «Стек»
При добавлении элемента у нас возникнет две ситуации:
Разберем чуть чуть по-подробнее.
Во-первых, почему функция принимает **top, то есть указатель на указатель, для того чтобы вам было наиболее понятно, я оставлю рассмотрение этого вопроса на потом. Во-вторых, по-подробнее поговорим о q->next = *top и о том, что же означает ->.
-> означает то, что грубо говоря, мы заходим в нашу структуру и достаем оттуда элемент этой структуры. В строчке q->next = *top мы из нашей ячейки достаем указатель на следующий элемент *next и заменяем его на указатель, который указывает на вершину стека *top. Другими словами мы проводим связь, от нового элемента к вершине стека. Тут ничего сложного, все как с книгами. Новую книгу мы кладем ровно на вершину стопки, то есть проводим связь от новой книги к вершине стопки книг. После этого новая книга автоматически становится вершиной, так как стек не стопка книг, нам нужно указать, что новый элемент — вершина, для этого пишется: *top = q;.
Функция удаления элемента из «Стека» по данным
Данная функция будет удалять элемент из стека, если число Data ячейки(q->Data) будет равна числу, которое мы сами обозначим.
Здесь могут быть такие варианты:
Для лучшего понимания удаления элемента проведем аналогии с уже привычной стопкой книг. Если нам нужно убрать книгу сверху, мы её убираем, а книга под ней становится верхней. Тут то же самое, только в начале мы должны определить, что следующий элемент станет вершиной *top = q->next; и только потом удалить элемент free(q);
Если книга, которую нужно убрать находится между двумя книгами или между книгой и столом, предыдущая книга ляжет на следующую или на стол. Как мы уже поняли, книга у нас-это ячейка, а стол получается это NULL, то есть следующего элемента нет. Получается так же как с книгами, мы обозначаем, что предыдущая ячейка будет связана с последующей prev->next = q->next;, стоит отметить что prev->next может равняться как ячейке, так и нулю, в случае если q->next = NULL, то есть ячейки нет(книга ляжет на стол), после этого мы очищаем ячейку free(q).
Так же стоит отметить, что если не провести данную связь, участок ячеек, который лежит после удаленной ячейки станет недоступным, так как потеряется та самая связь, которая соединяет одну ячейку с другой и данный участок просто затеряется в памяти
Функция вывода данных стека на экран
Самая простая функция:
Здесь я думаю все понятно, хочу сказать лишь то, что q нужно воспринимать как бегунок, он бегает по всем ячейкам от вершины, куда мы его установили вначале: *q = top;, до последнего элемента.
Главная функция
Хорошо, основные функции по работе со стеком мы записали, вызываем.
Посмотрим код:
Вернемся к тому, почему же в функцию мы передавали указатель на указатель вершины. Дело в том, что если бы мы ввели в функцию только указатель на вершину, то «Стек» создавался и изменялся только внутри функции, в главной функции вершина бы как была, так и оставалась NULL. Передавая указатель на указатель мы изменяем вершину *top в главной функции. Получается если функция изменяет стек, нужно передавать в нее вершину указателем на указатель, так у нас было в функции s_push,s_delete_key. В функции s_print «Стек» не должен изменяться, поэтому мы передаем просто указатель на вершину.
Вместо цифр 1,2,3,4,5 можно так-же использовать переменные типа int.
Заключение
Полный код программы:
Так как в стек элементы постоянно добавляются на вершину, выводиться элементы будут в обратном порядке
В заключение хотелось бы поблагодарить за уделенное моей статье время, я очень надеюсь что данный материал помог некоторым начинающим программистам понять, что такое «Стек», как им пользоваться и в дальнейшем у них больше не возникнет проблем. Пишите в комментариях свое мнение, а так же о том, как мне улучшить свои статьи в будущем. Спасибо за внимание.
Go: как изменяется размер стека горутины?
Эта статья берет за основу Go 1.12.
Go радует нас легким и умным управлением горутинами. Легким, поскольку стек горутин изначально весит всего 2 КБ, а умным, потому что горутины могут автоматически увеличиваться/уменьшаться в соответствии с нашими потребностями.
Что касается размера стека, мы можем найти его в runtime/stack.go :
Следует отметить, что с течением времени он менялся:
Go 1.2: стек горутины был увеличен с 4 КБ до 8 КБ.
Go 1.4: стек горутины уменьшился с 8 КБ до 2 КБ.
Размер стека изменялся из-за стратегии его аллокации (мы вернемся к этой теме чуть позже).
Иногда для работы нашей программы дефолтного размера стека недостаточно. В таком случае Go автоматически подстраивает размер стека под нужный.
Динамический размер стека
Если Go способен автоматически наращивать размер стека, то это также означает, что он может определять, когда размер выделяемой памяти менять не нужно. Давайте проанализируем, как это работает, на следующем примере:
Среди них есть две инструкции, связанные с изменением размера стека:
— CALL runtime.morestack_noctxt : этот метод увеличивает размер стека, если тому нужно больше памяти.
Затем текущий размер умножается на 2 и проверяется, не превышает ли он максимально допустимый размер — этот размер зависит от архитектуры:
Инструкция //go:noinline позволит избежать встраивания всех этих функций в main. Если компилятору не запретить инлайнинг, то мы не будем наблюдать динамического роста стеков в каждом прологе функции.
Вот часть результатов нашего дебага:
Здесь мы видим, что стек вырос в 4 раза. Действительно, пролог функции будет увеличивать стек настолько, насколько это необходимо для того, чтобы соответствовать его потребностям. Как мы видели в коде, размер стека определяется его границами, т.е. мы можем вычислить новый размер стека для каждого конкретного случая — инструкция newstack stack=[. ] возвращает указатели на текущие границы стека:
Исследование внутреннего устройства показало нам, что стек горутины имеет начальный размер в 2 Кб и по необходимости увеличивается в прологе функции, добавляемом при компиляции, до тех пор, пока памяти не станет достаточно или не будет достигнут максимальный размер стека.
Управление аллокацией стека
Система динамической аллокации — не единственное, что может повлиять на наши приложения. То, каким образом была выделена память, также может оказывать существенное влияние. Давайте попробуем понять, как это происходит, на основе полной трассировки двух первых увеличений размера стека:
Рост стека при непрерывном стеке
Инструкция copystack копирует весь стек и перемещает все адреса в новый стек. Мы можем легко в этом убедиться с помощью небольшой модификации нашего кода:
Теперь он выводит адрес значения:
Интересно отметить, что при запуске процесса сборки мусора стек будет уменьшен если это необходимо.
В нашем примере после вызова функции в стеке нет других валидных фреймов, кроме main, поэтому система будет в состоянии уменьшить его при запуске сборщика мусора. Мы можем принудительно запустить процесс сборки мусора для этого:
Дебажные трейсы теперь отражают уменьшение размера стека:
Непрерывный (contiguous) стек VS сегментированный (segmented) стек
Непрерывный стек — это стратегия копирования стека в большее пространство, в противоположность сегментированному стеку. Go перешел на непрерывный стек в релизе 1.3. Чтобы увидеть разницу, давайте запустим тот же пример только на Go 1.2. И нам снова необходимо будет обновить константу stackDebug для отображения трейсов. Для этого, поскольку рантайм для этой версии был написан на C, нам придется скомпилировать исходный код. Результат следующий:
Текущий стек stack=[0x7f8875952000, 0x7f8875953fa0] имеет размер 8 КБ (8192 байт + размер верхушки стека), а размер нового созданного стека составляет 18864 байт (18768 байт + размер верхушки стека). Распределение памяти следующее:
Таким образом, наш новый стек скомпонован следующим образом: 16016 (размер фрейма) + 800 (аргументы) + 2048 (StackExtra) + 0 (StackSystem).
После вызова всех функций новый стек высвобождается (лог runtime: oldstack ). Такое поведение было одной из причин, которая подтолкнула команду Golang к переходу на непрерывный стек:
Действующий механизм разделения стека имеет проблему «горячего разделения» — если стек почти заполнен, вызов результирует в выделении нового фрагмента стека. Когда этот вызов возвращается, новый фрагмент стека высвобождается. Если один и тот же вызов происходит неоднократно в коротком цикле, накладные расходы на аллокацию/высвобождение будут ощутимыми.
По этой причине Go пришлось увеличить минимальный размер стека в версии 1.2 до 8 КБ, а позже, после реализации непрерывного стека, его удалось уменьшить обратно до 2 КБ.
Взгляните на нашу предыдущую диаграмму только уже с сегментированным стеком:
Рост стека при сегментированном стеке
Заключение
Управление стеком в Go является эффективным и довольно простым для понимания. Golang — не единственный язык, который предпочел не использовать сегментированный стек, Rust также приняли решение не использовать его по тем же причинам.
Если вы хотите глубже погрузится во все тонкости стека, я рекомендую вам прочитать статью Дэйва Чейни, в которой говорится о красной зоне (redzone), а также статью Билла Кеннеди, посвященную фреймам в стеке.
Всех желающих приглашаем на demo-занятие «Примитивы синхронизации. Часть 1». После занятия вы сможете: пользоваться частью механизмов синхронизации в Go и бороться с «гонками» в Go. >> РЕГИСТРАЦИЯ
Всё, что вы хотели знать о стек-трейсах и хип-дампах. Часть 1
Практика показала, что хардкорные расшифровки с наших докладов хорошо заходят, так что мы решили продолжать. Сегодня у нас в меню смесь из подходов к поиску и анализу ошибок и крэшей, приправленная щепоткой полезных инструментов, подготовленная на основе доклада Андрея Паньгина aka apangin из Одноклассников на одном из JUG’ов (это была допиленная версия его доклада с JPoint 2016). В без семи минут двухчасовом докладе Андрей подробно рассказывает о стек-трейсах и хип-дампах.
Пост получился просто огромный, так что мы разбили его на две части. Сейчас вы читаете первую часть, вторая часть лежит здесь.
Сегодня я буду рассказывать про стек-трейсы и хип-дампы — тему, с одной стороны, известную каждому, с другой — позволяющую постоянно открывать что-то новое (я даже багу нашел в JVM, пока готовил эту тему).
Когда я делал тренировочный прогон этого доклада у нас в офисе, один из коллег спросил: «Все это очень интересно, но на практике это кому-нибудь вообще полезно?» После этого разговора первым слайдом в свою презентацию я добавил страницу с вопросами по теме на StackOverflow. Так что это актуально.
Сам я работаю ведущим программистом в Одноклассниках. И так сложилось, что зачастую мне приходится работать с внутренностями Java — тюнить ее, искать баги, дергать что-то через системные классы (порой не совсем легальными способами). Оттуда я и почерпнул большую часть информации, которую сегодня хотел вам представить. Конечно, в этом мне очень помог мой предыдущий опыт: я 6 лет работал в Sun Microsystems, занимался непосредственно разработкой виртуальной Java-машины. Так что теперь я знаю эту тему как изнутри JVM, так и со стороны пользователя-разработчика.
Стек-трейсы
Стек-трейсы exception
Когда начинающий разработчик пишет свой «Hello world!», у него выскакивает эксепшн и ему демонстрируется стек-трейс, где произошла эта ошибка. Так что какие-то представления о стек-трейсах есть у большинства.
Перейдем сразу к примерам.
Я написал небольшую программку, которая в цикле 100 миллионов раз производит такой эксперимент: создает массив из 10 случайных элементов типа long и проверяет, сортированный он получился или нет.
Что произойдет? Эксепшн, выход за пределы массива.
Давайте разбираться, в чем дело. У нас в консоль выводится:
но стек-трейсов никаких нет. Куда делись?
В HotSpot JVM есть такая оптимизация: у эксепшенов, которые кидает сама JVM из горячего кода, а в данном случае код у нас горячий — 100 миллионов раз дергается, стек-трейсы не генерируются.
Это можно исправить с помощью специального ключика:
Теперь попробуем запустить пример. Получаем все то же самое, только все стек-трейсы на месте.
Подобная оптимизация работает для всех неявных эксепшенов, которые бросает JVM: выход за границы массива, разыменование нулевого указателя и т.д.
Раз оптимизацию придумали, значит она зачем-то нужна? Понятно, что программисту удобнее, когда стек-трейсы есть.
Давайте измерим, сколько «стоит» у нас создание эксепшена (сравним с каким-нибудь простым Java-объектом, вроде Date).
С помощью JMH напишем простенькую бенчмарку и измерим, сколько наносекунд занимают обе операции.
Оказывается, создать эксепшн в 150 раз дороже, чем обычный объект.
И тут не все так просто. Для виртуальной машины эксепшн не отличается от любого другого объекта, но разгадка кроется в том, что практически все конструкторы эксепшн так или иначе сводятся к вызову метода fillInStackTrace, который заполняет стек-трейс этого эксепшена. Именно заполнение стек-трейса отнимает время.
Этот метод в свою очередь нативный, падает в VM рантайм и там гуляет по стеку, собирает все фреймы.
Метод fillInStackTrace публичный, не final. Давайте его просто переопределим:
Теперь создание обычного объекта и эксепшена без стек-трейса отнимают одинаковое время.
Есть и другой способ создать эксепшн без стек-трейса. Начиная с Java 7, у Throwable и у Exception есть protected-конструктор с дополнительным параметром writableStackTrace:
Если туда передать false, то стек-трейс генерироваться не будет, и создание эксепшена будет очень быстрым.
Зачем нужны эксепшены без стек-трейсов? К примеру, если эксепшн используется в коде в качестве способа быстро выбраться из цикла. Конечно, лучше так не делать, но бывают случаи, когда это действительно дает прирост производительности.
А сколько стоит бросить эксепшн?
Рассмотрим разные случаи: когда он бросается и ловится в одном методе, а также ситуации с разной глубиной стека.
Вот, что дают измерения:
Т.е. если у нас глубина небольшая (эксепшн ловится в том же фрейме или фреймом выше — глубина 0 или 1), эксепшн ничего не стоит. Но как только глубина стека становится большой, затраты совсем другого порядка. При этом наблюдается четкая линейная зависимость: «стоимость» исключения почти линейно зависит от глубины стека.
Дорого стоит не только получение стек-трейса, но и дальнейшие манипуляции — распечатка, отправка по сети, запись, — все, для чего используется метод getStackTrace, который переводит сохраненный стек-трейс в объекты Java.
Видно, что преобразование стек-трейса в 10 раз «дороже» его получения:
Почему это происходит?
Вот метод getStackTrace в исходниках JDK:
Сначала через вызов нативного метода мы узнаем глубину стека, потом в цикле до этой глубины вызываем нативный метод, чтобы получить очередной фрейм и сконвертировать его в объект StackTraceElement (это нормальный объект Java с кучей полей). Мало того, что это долго, процедура отнимает много памяти.
Более того, в Java 9 этот объект дополнен новыми полями (в связи с известным проектом модуляризации) — теперь каждому фрейму приписывается отметка о том, из какого он модуля.
Привет тем, кто парсит эксепшены с помощью регулярных выражений. Готовьтесь к сюрпризам в Java 9 — появятся еще и модули.
Давайте подведем итоги
Пара советов:
Стек-трейсы в тред дампах
Чтобы узнать, что же делает программа, проще всего взять тред дамп, например, утилитой jstack.
Фрагменты вывода этой утилиты:
Что здесь видно? Какие есть потоки, в каком они состоянии и их текущий стек.
Более того, если потоки захватили какие-то локи, ожидают входа в synchronized-секцию или взятия ReentrantLock, это также будет отражено в стек-трейсе.
Порой полезным оказывается малоизвестный идентификатор:
Он напрямую связан с ID потока в операционной системе. Например, если вы смотрите программой top в Linux, какие треды у вас больше всего едят CPU, pid потока — это и есть тот самый nid, который демонстрируется в тред дампе. Можно тут же найти, какому Java-потоку он соответствует.
В случае с мониторами (с synchronized-объектами) прямо в тред дампе будет написано, какой тред и какие мониторы держит, кто пытается их захватить.
В случае с ReentrantLock это, к сожалению, не так. Здесь видно, как Thread 1 пытается захватить некий ReentrantLock, но при этом не видно, кто этот лок держит. На этот случай в VM есть опция:
Если мы запустим то же самое с PrintConcurrentLocks, в тред дампе увидим и ReentrantLock.
Здесь указан тот самый id лока. Видно, что его захватил Thread 2.
Если опция такая хорошая, почему бы ее не сделать «по умолчанию»?
Она тоже чего-то стоит. Чтобы напечатать информацию о том, какой поток какие ReentrantLock’и держит, JVM пробегает весь Java heap, ищет там все ReentrantLock’и, сопоставляет их с тредами и только потом выводит эту информацию (у треда нет информации о том, какие локи он захватил; информация есть только в обратную сторону — какой лок связан с каким тредом).
В указанном примере по названиям потоков (Thread 1 / Thread 2) непонятно, к чему они относятся. Мой совет из практики: если у вас происходит какая-то длинная операция, например, сервер обрабатывает клиентские запросы или, наоборот, клиент ходит к нескольким серверам, выставляйте треду понятное имя (как в случае ниже — прямо IP того сервера, к которому клиент сейчас идет). И тогда в дампе потока сразу будет видно, ответа от какого сервера он сейчас ждет.
Хватит теории. Давайте опять к практике. Этот пример я уже не раз приводил.
Запускаем программку 3 раза подряд. 2 раза она выводит сумму чисел от 0 до 100 (не включая 100), третий — не хочет. Давайте смотреть тред дампы:
Первый поток оказывается RUNNABLE, выполняет наш reduce. Но смотрите, какой интересный момент: Thread.State вроде как RUNNABLE, но при этом написано, что поток in Object.wait().
Мне тоже это было не понятно. Я даже хотел сообщить о баге, но оказывается, такая бага заведена много лет назад и закрыта с формулировкой: «not an issue, will not fix».
В этой программке действительно есть дедлок. Его причина — инициализация классов.
Выражение выполняется в статическом инициализаторе класса ParallelSum:
Но поскольку стрим параллельный, исполнение происходит в отдельных потоках ForkJoinPool, из которых вызывается тело лямбды:
Код лямбды записан Java-компилятором прямо в классе ParallelSum в виде приватного метода. Получается, что из ForkJoinPool мы пытаемся обратиться к классу ParallelSum, который в данный момент находится на этапе инициализации. Поэтому потоки начинают ждать, когда же закончится инициализация класса, а она не может закончиться, поскольку ожидает вычисления этой самой свертки. Дедлок.
Почему вначале сумма считалась? Просто повезло. У нас небольшое количество элементов суммируется, и иногда все исполняется в одном потоке (другой поток просто не успевает).
Но почему же тогда поток в стек-трейсе RUNNABLE? Если почитать документацию к Thread.State, станет понятно, что никакого другого состояния здесь быть не может. Не может быть состояния BLOCKED, поскольку поток не заблокирован на Java-мониторе, нет никакой synchronized-секции, и не может быть состояния WAITING, потому что здесь нет никаких вызовов Object.wait(). Синхронизация происходит на внутреннем объекте виртуальной машины, который, вообще говоря, даже не обязан быть Java-объектом.
Стек-трейс при логировании
Представьте себе ситуацию: в куче мест в нашем приложении что-то логируется. Было бы полезно узнать, из какого места появилась та или иная строчка.
В Java нет препроцессора, поэтому нет возможности использовать макросы __FILE__, __LINE__, как в С (эти макросы еще на этапе компиляции преобразуются в текущее имя файла и строку). Поэтому других способов дополнить вывод именем файла и номером строки кода, откуда это было напечатано, кроме как через стек-трейсы, нет.
Генерим эксепшн, у него получаем стек-трейс, берем в данном случае второй фрейм (нулевой — это метод getLocation, а первый — вызывает метод warning).
Как мы знаем, получение стек-трейса и, тем более, преобразование его в стек-трейс элементы очень дорого. А нам нужен один фрейм. Можно ли как-то проще сделать (без эксепшн)?
Помимо getStackTrace у исключения есть метод getStackTrace объекта Thread.
Будет ли так быстрее?
Нет. JVM никакой магии не делает, здесь все будет работать через тот же эксепшн с точно таким же стек-трейсом.
Но хитрый способ все-таки есть:
Я люблю всякие приватные штуки: Unsafe, SharedSecrets и т.д.
Есть аксессор, который позволяет получить StackTraceElement конкретного фрейма (без необходимости преобразовывать весь стек-трейс в Java-объекты). Это будет работать быстрее. Но есть плохая новость: в Java 9 это работать не будет. Там проделана большая работа по рефакторингу всего, что связано со стек-трейсами, и таких методов там теперь просто нет.
Конструкция, позволяющая получить какой-то один фрейм, может быть полезна в так называемых Caller-sensitive методах — методах, чей результат может зависеть от того, кто их вызывает. В прикладных программах с такими методами приходится сталкиваться нечасто, но в самой JDK подобных примеров немало:
В зависимости от того, кто вызывает Class.forName, поиск класса будет осуществляться в соответствующем класс-лоадере (того класса, который вызвал этот метод); аналогично — с получением ResourceBundle и загрузкой библиотеки System.loadLibrary. Также информация о том, кто вызывает, полезна при использовании различных методов, которые проверяют пермиссии (а имеет ли данный код право вызывать этот метод). На этот случай в «секретном» API предусмотрен метод getCallerClass, который на самом деле является JVM-интринсиком и вообще почти ничего не стоит.
Как уже много раз говорилось, приватный API — это зло, использовать которое крайне не рекомендуется (сами рискуете нарваться на проблемы, подобные тем, что ранее вызвал Unsafe). Поэтому разработчики JDK задумались над тем, что раз этим пользуются, нужна легальная альтернатива — новый API для обхода потоков. Основные требования к этому API:
Простейший пример, как этим пользоваться:
Берем StackWalker и вызываем метод forEach, чтобы он обошел все фреймы. В результате получим такой простой стек-трейс:
То же самое с опцией SHOW_REFLECT_FRAMES:
В этом случае добавятся методы, относящиеся к вызову через рефлекшн:
Если добавить опцию SHOW_HIDDEN_FRAMES (она, кстати, включает в себя SHOW_REFLECT_FRAMES, т.е. рефлекшн-фреймы тоже будут показаны):
В стек-трейсе появятся методы динамически-сгенерированных классов лямбд:
А теперь самый главный метод, который есть в StackWalker API — метод walk с такой хитрой непонятной сигнатурой с кучей дженериков:
Метод walk принимает функцию от стек-фрейма.
Его работу проще показать на примере.
Несмотря на то, что все это выглядит страшно, как этим пользоваться — очевидно. В функцию передается стрим, а уже над стримом можно проводить все привычные операции. К примеру, вот так выглядел бы метод getCallerFrame, который достает только второй фрейм: пропускаются первые 2, потом вызывается findFirst:
Метод walk возвращает тот результат, который возвращает эта функция стрима. Все просто.
Для данного конкретного случая (когда нужно получить просто Caller класс) есть специальный shortcut метод:
Еще один пример посложнее.
Обходим все фреймы, оставляем только те, которые относятся к пакету org.apache, и выводим первые 10 в список.
Интересный вопрос: зачем такая длинная сигнатура с кучей дженериков? Почему бы просто не сделать у StackWalker метод, который возвращает стрим?
Если дать API, который возвращает стрим, у JDK теряется контроль над тем, что дальше над этим стримом делают. Можно дальше этот стрим положить куда-то, отдать в другой поток, попробовать его использовать через 2 часа после получения (тот стек, который мы пытались обойти, давно потерян, а тред может быть давно убит). Таким образом будет невозможно обеспечить «ленивость» Stack Walker API.
Основной поинт Stack Walker API: пока вы находитесь внутри walk, у вас зафиксировано состояние стека, поэтому все операции на этом стеке можно делать lazy.
На десерт еще немного интересного.
Как всегда, разработчики JDK прячут от нас кучу сокровищ. И помимо обычных стек-фреймов они для каких-то своих нужд сделали живые стек-фреймы, которые отличаются от обычных тем, что имеют дополнительные методы, позволяющие не только получить информацию о методе и классе, но еще и о локальных переменных, захваченных мониторах и значениях экспрешн-стека данного стек-фрейма.
Пробуем на таком примере. Есть программа, которая рекурсивным методом ищет выход из лабиринта. У нас есть квадратное поле size x size. Есть метод visit с текущими координатами. Мы пытаемся из текущей клетки пойти влево / вправо / вверх / вниз (если они не заняты). Если дошли из правой-нижней клетки в левую-верхнюю, считаем, что нашли выход и распечатываем стек.
Если я делаю обычный dumpStack, который был еще в Java 8, получаем обычный стек-трейс, из которого ничего не понятно. Очевидно — рекурсивный метод сам себя вызывает, но интересно, на каком шаге (и с какими значениями координат) вызывается каждый метод.
Заменим стандартный dumpStack на наш StackTrace.dump, который через рефлекшн использует live стек-фреймы:
В первую очередь надо получить соответствующий StackWalker, вызвав метод getStackWalker. Все фреймы, которые будут передаваться в getStackWalker, на самом деле будут экземплярами лайв стек-фрейма, у которого есть дополнительные методы, в частности, getLocals для получения локальных переменных.
Запускаем. Получаем то же самое, но у нас отображается весь путь из лабиринта в виде значений локальных переменных:
На этом мы заканчиваем первую часть поста. Вторая часть здесь.
Лично встретиться с Андреем в Москве можно будет уже совсем скоро — 7-8 апреля на JPoint 2017. В этот раз он выступит с докладом «JVM-профайлер с чувством такта», в котором расскажет, как можно получить честные замеры производительности приложения, комбинируя несколько подходов к профилированию. Доклад будет «всего» часовой, зато в дискуссионной зоне никто не будет ограничивать вас от вопросов и горячих споров!
Кроме этого, на JPoint есть целая куча крутых докладов практически обо всем из мира Java — обзор планируемых докладов мы давали в другом посте, а просто программу конференции вы найдете на сайте мероприятия.