Потрясающе быстрые теневые стеки для Go

Разберемся, как теневые стеки(shadow stacks) могут ускорить раскрутку указателя фрейма (frame pointer unwinding) и другие подходы к захвату стека вызовов в 8 раз.

Программные теневые стеки могут обеспечить до 8 раз более быструю трассировку стека в Go рантайме по сравнению с раскруткой указателя фрейма, которое было реализовано в go1.21. Это не означает, что данная идея должна сразу же вырваться из лаборатории, но она предлагает интересный взгляд на потенциальное будущее трассировки стека с аппаратным ускорением через теневые стеки.

Вдохновение

Пару дней назад я наткнулся на интересный комментарий автора Bytehound profiler на Hacker News. Комментарий был дан в ответ на вопрос о том, основана ли техника быстрого захвата трассы стека, упомянутая в README проекта, на указателях фрейма. Ответ был следующим:

Нет. Она основана на DWARF.

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

Справочная информация

Прежде чем мы перейдем к подробному описанию, давайте вспомним, что захват трассировки стека в нативном языке, таком как C/C++/Go/Rust, - это, по сути, обход всех фреймов вызовов в стеке и сбор адресов возврата, которые хранятся в них.

Проще всего это сделать с помощью компилятора (опция), который добавляет преамбулу в каждую функцию, заставляя ее помещать в стек указатель на предыдущий фрейм. Это эффективно превращает фреймы стека в связанный список и позволяет очень быстро перехватывать трассировку стека, что я и помог реализовать в go1.21.

Однако по историческим причинам, восходящим к тем временам, когда у нас были только 32-битные процессоры с ограниченным количеством регистров, компиляторы, отличные от Go, обычно не используют указатели фреймов в оптимизированных сборках (-O1 или выше). В настоящее время ситуация меняется, но пока во многих случаях для поиска расстояния между фреймами стека приходится использовать DWARF или другие таблицы раскрутки.

Поскольку таблицы DWARF-раскрутки выражаются в терминах опкодов для полной по Тьюрингу виртуальной машины (лучше бы я это выдумал), довольно распространена предварительная обработка этих данных для повышения производительности поиска. На самом деле, есть интересная статья, в которой доходит до прямой прекомпиляции этих таблиц в код x86_64. Я не уверен, что профилировщик Bytehound выполняет именно такую предварительную обработку, но это и не важно.

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

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

Теневые стеки

Итак, что я имею в виду, говоря о сокращении расстояния? Оказывается, многократный захват трассировки стека часто сопровождается большим количеством дублирующей работы. Это происходит потому, что в большинстве случаев между двумя трассировками изменилось всего несколько фреймов, но в итоге мы снова и снова обращаемся к неизменным фреймам. Это понимание естественным образом приводит к идее ведения кэша адресов возврата, который позволяет нам избежать этой дублирующей работы за счет затрат на поддержание кэша. Такой кэш также известен как «теневой стек».

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

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

Оказалось, что я ошибался. Альтернативный подход заключается в заполнении теневого стека при захвате трассировки стека. Это устраняет накладные расходы на обновление теневого стека при каждом вызове функции. Однако при этом все равно остается проблема выгрузки адресов возврата, когда функция, заполнившая кэш, возвращается. Вот тут-то и приходит на помощь хитроумный трюк с «батутом» от автора Bytehound. Идея заключается в том, чтобы использовать ту самую проблему безопасности, которую должны предотвратить аппаратные теневые стеки, и перезаписать адреса возврата в стеке, чтобы внедрить функцию-батут, которая вытаскивает адрес из теневого стека перед возвратом управления по этому адресу.

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

Реализация теневых стеков в Go

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

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

Полный исходный код можно посмотреть здесь, но суть реализации довольно проста. Сначала я добавил новое поле shadowStack в структуру стека горутины g. Я также объявил для него новый тип, думая, что мне понадобится несколько полей. Но в итоге мне понадобилось только одно поле pcs []uintptr.

type g struct {
  ...
  shadowStack
}

type shadowStack struct {
	pcs []uintptr
}

Функция ShadowFPCallers немного сложнее, но в целом это цикл раскручивания указателя фрейма, который вводит специальный адрес возврата shadowTrampolineASM и использует его в качестве маркера, чтобы понять, что остальные адреса возврата могут быть скопированы из теневого стека. Он также достаточно умен, чтобы инкрементально обновлять теневой стек при увеличении глубины стека.

func ShadowFPCallers(pcs []uintptr) (i int) {
	const shadowDepth = 2
	var (
		gp           = getg()
		fp           = unsafe.Pointer(getfp())
		oldShadowPtr unsafe.Pointer
		newShadowPtr unsafe.Pointer
	)
	for i = 0; i < len(pcs) && fp != nil; i++ {
		pcPtr := unsafe.Pointer(uintptr(fp) + goarch.PtrSize)
		pc := *(*uintptr)(pcPtr)
		if i == shadowDepth {
			newShadowPtr = pcPtr
		}
		if pc == abi.FuncPCABIInternal(shadowTrampolineASM) {
			i += copy(pcs[i:], gp.shadowStack.pcs)
			oldShadowPtr = pcPtr
			break
		}
		pcs[i] = pc
		fp = unsafe.Pointer(*(*uintptr)(fp))
	}
	if oldShadowPtr == newShadowPtr {
		return
	}
	if oldShadowPtr != nil {
		*(*uintptr)(oldShadowPtr) = gp.shadowStack.pcs[0]
	}
	gp.shadowStack.pcs = append(gp.shadowStack.pcs[0:0], pcs[shadowDepth:i]...)
	*(*uintptr)(newShadowPtr) = abi.FuncPCABIInternal(shadowTrampolineASM)
	return
}

Сама функция shadowTrampolineASM является тонкой оберткой вокруг функции shadowTrampolineGo. Вместе они заботятся о том, чтобы выдернуть адрес из теневого стека, инжектить «батут» в родительскую вызывающую функцию и восстановить выдернутый адрес в регистре R30 (arm64).

TEXT ·shadowTrampolineASM<ABIInternal>(SB),NOSPLIT|NOFRAME,$0-0
	CALL runtime·shadowTrampolineGo<ABIInternal>(SB)
	MOVD R0, R30
	RET

func shadowTrampolineGo() (retpc uintptr) {
	gp := getg()
	retpc = gp.shadowStack.pcs[0]
	gp.shadowStack.pcs = gp.shadowStack.pcs[1:]
	*(*uintptr)(unsafe.Pointer(getcallersp())) = abi.FuncPCABIInternal(shadowTrampolineASM)
	return
}

И последнее, но не менее важное: мне пришлось научить гошную таблицу поиска ориентироваться в инжектированных батутных функциях. Без этого изменения panic(), copystack() и профилировщик cpu/memory сломались бы из-за того, что размотка застряла бы.

func (u *unwinder) resolveInternal(innermost, isSyscall bool) {
    // ...
	if f.funcID == abi.FuncID_shadowTrampolineASM || f.funcID == abi.FuncID_shadowTrampolineGo {
		frame.pc = gp.shadowStack.pcs[0]
		frame.fn = findfunc(frame.pc)
		f = frame.fn
	}
    // ...

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

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

Но, как и предполагалось, производительность оказывается неоднозначной, когда речь заходит о наихудшем бенчмарке, где глубина стека увеличивается до предела, а затем уменьшается обратно, при этом ведется трассировка стека при входе на определенный уровень глубины и при выходе из него. Здесь кажется, что подход с теневым стеком конкурентоспособен только для стеков глубиной чуть больше 32 фреймов. При меньшей глубине стека подход оказывается в 4 раза медленнее 🐌.

Я могу предложить несколько способов смягчить худший сценарий. Например, теневой стек может быть отключен при глубине стека менее 32 фреймов. Или, возможно, мы могли бы вести некоторую статистику о глубине стека и использовать более продвинутую эвристику. Сама реализация, вероятно, также может быть оптимизирована. Но поскольку это был всего лишь небольшой side-проект, у меня не было времени на дальнейшее изучение этого вопроса.

Заключение

Программные теневые стеки - потенциально жизнеспособная техника для ускорения перехвата трассировки стека. Я проверил этот подход только на раскрутке указателя фрейма в Go, но я могу предположить, что раскрутка DWARF также станет очень конкурентоспособной с таким ускорением. И хотя было нелегко добиться правильного результата, подход требует относительно немного дополнительного кода.

Однако такой подход имеет и множество минусов, в частности:

• В худшем случае производительность может быть сомнительной при меньшей глубине стека. (Но неясно, насколько часто это будет встречаться в природе).

• Новые функции аппаратной безопасности, скорее всего, сломают этот подход.

• Внешние средства раскрутки (например, linux perf) будут выдавать битые трассировки стека при встрече с измененными адресами возврата.

• Программы, использующие аналогичные нестандартные методы управления потоком, могут сломаться при запуске их с теневыми стеками.

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

• Теневые стеки требуют 8 байт дополнительной памяти на каждый фрейм стека. Обычно это вполне нормально, но некоторые программы могут не захотеть идти на такой компромисс.

Учитывая, что раскрутка указателя фрейма составляет менее нескольких процентов накладных расходов для трассировщика, а это самый ресурсоемкий вариант использования, я пришел к выводу, что техника интересная, но на данный момент не оправданная.

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