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

Введение в проблему

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

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

Некоторые встроенные в язык операции генерируют какой-то понятный вызов. Например, операторы для работы с каналами (runtime.chanrecv, runtime.chansend).

Другие могут превращаться в несколько вызовов: append(b1, b2...) создаст вызовы runtime.growslice и runtime.memmove. Это уже усложняет анализ профилей, но у нас хотя бы есть, за что зацепиться.

Самое сложное — это операции, которые встраивают свой код прямо в место использования, без какого-либо вызова. Это эффективно в плане скорости исполнения, но профилирование таких конструкций штатными средствами становится невозможным. Машинный код этих операций смешивается с использующей их функцией, а в профиле эти значения будут увеличивать личное (flat/self) время этой функции.

Цена bound check'ов

Будем бенчмаркать довольно простую функцию получения последнего элемента слайса:

package bcbench

import "testing"

//go:noinline
func getlast(xs []int) int {
  return xs[len(xs)-1]
}

func BenchmarkGetLast(b *testing.B) {
  xs := []int{0, 2, 3, 5}
  for i := 0; i < b.N; i++ {
    getlast(xs)
    getlast(xs)
    getlast(xs)
    getlast(xs)
  }
}

Чтобы бинарник с тестом был доступен после бенчмарков (без него проблематичнее получить disasm), соберём его явно через -c. Нам потребуется много запусков (count), так как сами тестируемые операции очень быстрые — семплирующая природа профилирования требует более длинных интервалов, чтобы у нас был шанс снять стеки в нужные моменты.

$ go test -c
$ ./bcbench.test -test.count=60 -test.cpuprofile=cpu.out -test.bench=. .

Теперь откроем профиль в браузере:

$ go tool pprof -http=:8080 cpu.out

Я отметил строки, которые напрямую относятся к проверкам выхода за пределы слайса. Мы ещё вернёмся к этой структуре, но сначала я хочу обратить ваше внимание на то, что большая часть семплов вообще не покрыла связанные инструкции. Это не значит, что bound check в данном случае бесплатен. Это скорее признак того, что записывая семплы 100 раз в секунду нам очень сложно поймать некоторые участки машинного кода.

Перепишем функцию getlast так, чтобы там не было проверок, вставленных компилятором:

//go:noinline
func getlast(xs []int) int {
  if len(xs) != 0 {
    return xs[len(xs)-1]
  }
  return 0
}

Запустим аналогичные бенчмарки, соберём профиль, сравним быстродействие.

Можем видеть, что вставленных компилятором проверок нет. Вместо CMPQ у нас в коде TESTQ и, может показаться, что это работает медленнее, ведь целых 4 секунды мы провели на этой инструкции. Но это не так, нам просто "повезло".

При сравнении быстродействия видно, что вторая версия функции быстрее, хоть её исходники и более многословные:

$ benchstat old.txt new.txt 
name       old time/op  new time/op  delta
GetLast-8  12.5ns ± 2%   9.3ns ± 1%  -25.93%  (p=0.000 n=10+10)

И, снова, это скорее побочный эффект: версия без вызова panicindex имеет фрейм без пролога и эпилога (locals size=0), поэтому сама по себе функция более легковесная. Наша проблема в том, что даже имея всю информацию, замерять время, потраченное на bound check — не очень просто.

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

Откуда появляется bound check

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

Для массивов, частью типа которых является их длина, проверки вставляются только в случае неконстантных индексов.

func f(i int) {
  var a [8]int
  println(a[0]) // не требует проверок
  println(a[i]) // проверка i < len(a)
}

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

При слайсинге (взятии "срезов") массивов происходят те же самые проверки, поэтому для a[i:] компилятор будет вставлять проверку на i <= len(a).

func f(b []byte, i, j int) {
  println(b[i])   // проверка i < len(b)
  println(b[i:])  // проверка i <= len(b)
  println(b[:j])  // проверка j <= cap(b)
  println(b[i:j]) // проверка i <= len(b) && j <= cap(b)
}

Смотрим на дизассемблер bound check'ов

Все примеры кода актуальны для x86-64 (GOARCH=amd64).

Начнём с самого простого случая:

func indexing(i int, xs []int) int {
  return xs[i]
}

Посмотрим на сгенерированный код:

То же самое, только текстом

    SUBQ $24, SP
    MOVQ BP, 16(SP)
    LEAQ 16(SP), BP
    MOVQ BX, xs+40(FP)
    CMPQ CX, AX
    JLS bc_fail
    MOVQ (BX)(AX*8), AX
    MOVQ 16(SP), BP
    ADDQ $24, SP
    RET
bc_fail:
    CALL runtime.panicIndex(SB)

Это и есть довольно общая схема для bound check'а:

Инструкция сравнения (CMPQ или TEST в случае сравнения с 0)
Условный прыжок (JLS выше — это JBE)
В месте прыжка идёт вызов одной из паникующих функций

До инструкции CALL могут быть несколько инструкций типа MOV или LEA для передачи нужных аргументов.

Возьмём ещё несколько функций для экспериментов:

func slicingFrom(i int, xs []int) []int {
  return xs[i:]
}

func slicingTo(i int, xs []int) []int {
  return xs[:i]
}

func slicingFromTo(i, j int, xs []int) []int {
  return xs[i:j]
}

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

indexing — runtime.panicIndex()
slicingFrom — runtime.panicSliceB()
slicingTo — runtime.panicSliceAcap()
slicintFromTo — runtime.panicSliceB() и runtime.panicSliceAcap()

На самом деле, даже это не полный набор. Весь список функций можно подсмотреть в исходниках компилятора.

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

Если же машинный код матчится по алгоритму выше и завершается вызовом специальной функции-паники, типа panicSliceAcap, то мы можем быть уверенными, что перед нами bound check.

При этом считать семплы мы будем только для двух инструкций из всей распознанной последовательности: CMPQ и JLS.

Собираем адреса функций-паник

Я буду рассматривать пример с ELF бинарником.

В стандартной библиотеке Go есть пакет debug/elf. Им мы и воспользуемся.

// Этот список подойдёт для Go 1.17 и 1.18
var bcFuncNames = map[string]struct{}{
  "runtime.panicIndex":        {},
  "runtime.panicIndexU":       {},
  "runtime.panicSliceAlen":    {},
  "runtime.panicSliceAlenU":   {},
  "runtime.panicSliceAcap":    {},
  "runtime.panicSliceAcapU":   {},
  "runtime.panicSliceB":       {},
  "runtime.panicSliceBU":      {},
  "runtime.panicSlice3Alen":   {},
  "runtime.panicSlice3AlenU":  {},
  "runtime.panicSlice3Acap":   {},
  "runtime.panicSlice3AcapU":  {},
  "runtime.panicSlice3B":      {},
  "runtime.panicSlice3BU":     {},
  "runtime.panicSlice3C":      {},
  "runtime.panicSlice3CU":     {},
  "runtime.panicSliceConvert": {},
}

bcFuncAddresses := make(map[int64]struct{})

// exeBytes - []byte из нашего бинарника
f, err := elf.NewFile(bytes.NewReader(exeBytes))
if err != nil {
  return fmt.Errorf("parse ELF: %v", err)
}
symbols, err := f.Symbols()
if err != nil {
  return fmt.Errorf("fetch ELF symbols: %v", err)
}

for _, sym := range symbols {
  if _, ok := bcFuncNames[sym.Name]; !ok {
    continue
  }
  addr := sym.Value // !!! <----------------------------
  bcFuncAddresses[int64(addr)] = struct{}{}
}

К сожалению, этот код не совсем корректен. Обратите внимание на строку с отметкой.

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

Пакет github.com/google/pprof/profile идеально подходит для нашей задачи.

// Использую ReadFile, а не os.Open, чтобы не возиться с файлом,
// который потом нужно будет закрывать
data, err := os.ReadFile("cpu.out")
if err != nil {
  return fmt.Errorf("read profile: %v", err)
}
p, err := profile.Parse(bytes.NewReader(data))
if err != nil {
  return fmt.Errorf("parse profile: %v", err)
}

Теперь поменяем вычисления адреса:

- addr := sym.Value
+ addr := sym.Value + p.Mapping[0].Offset - p.Mapping[0].Start

Ура! Теперь мы можем определять CALL <panicfunc> по таблице адресов.

Разбираем машинный код

Обходя семплы, мы используем loc.Address, чтобы получить адрес текущей исполняемой инструкции. Затем мы проверяем, можно ли с этой позиции распознать bound check в функции markBoundCheck.

for _, sample := range p.Sample {
  if len(sample.Location) == 0 {
    continue
  }
  for _, loc := range sample.Location {
    if len(loc.Line) == 0 {
      continue
    }
    m := loc.Mapping
    addr := int64(loc.Address + m.Offset - m.Start)
    // ctx содержит подготовленный ранее bcFuncAddresses
    markBoundCheck(ctx, exeBytes, addr)
  }
}

Картинка ниже призвана помочь понять высокоуровневую структуру профилей. Семплы располагаются примерно так:

[]Location формируют стек вызовов, где Location[0] — это текущий фрейм. Внутри этого фрейма у нас есть []Line, который описывает вложенный стек. Line[len(Line)-1] — это сама функция, а остальное — это встроенные в неё вызовы.

Остаётся реализовать markBoundCheck. Для декодирования инструкций будем использовать golang.org/x/arch/x86/x86asm.

func markBoundCheck(ctx *context, code []byte, addr int64) bool {
  // 1. Инструкция сравнения
  cmp, err := x86asm.Decode(code[addr:], 64)
  if err != nil {
    return false
  }
  if cmp.Op != x86asm.CMP && cmp.Op != x86asm.TEST {
    return false
  }

  // 2. Условный прыжок
  jmp, err := x86asm.Decode(code[addr+int64(cmp.Len):], 64)
  if err != nil {
    return false
  }
  jumpFrom := int64(addr) + int64(cmp.Len)
  var jumpTo int64
  switch jmp.Op {
  case x86asm.JBE, x86asm.JB, x86asm.JA:
    rel, ok := jmp.Args[0].(x86asm.Rel)
    if !ok {
      return false
    }
    jumpTo = jumpFrom + int64(rel) + int64(jmp.Len)
  default:
    return false
  }

  // 3. Вызов паникующей функции
  call, err := x86asm.Decode(code[jumpTo:], 64)
  if err != nil {
    return false
  }
  if inst.Op != x86asm.CALL {
    return false
  }
  funcRel, ok := call.Args[0].(x86asm.Rel)
  if !ok {
    return false
  }
  funcAddr := jumpTo + int64(funcRel) + int64(call.Len)
  if _, ok := ctx.bcFuncAddresses[funcAddr]; !ok {
    return false
  }

  // Записываем, что CMPQ (addr) и прыжок (addr+cmp.Len) относятся
  // к bound check операции
  ctx.bcAddresses[addr] = struct{}{}
  ctx.bcAddresses[addr+int64(cmp.Len)] = struct{}{}

  return true
}

Этот код немного упрощён. Ссылку на полную реализацию я привожу в конце статьи.

Теперь можем по любому адресу инструкции из CPU профиля сказать, относится ли она к bound check или нет.

Добавляем runtime.boundcheck в профиль

Самый простой способ — это добавить новые inline фреймы в уже существующие profile.Location объекты.

Но сначала нам нужно добавить в профиль информацию о новой функции. Назовём её runtime.boundcheck:

// ID начинаются с 1, то есть p.Function[i].ID == i+1
id := len(p.Function) + 1
boundcheckFunc := &profile.Function{
  ID:         uint64(id),
  Name:       "runtime.boundcheck",
  SystemName: "runtime.boundcheck",
  Filename:   "builtins.go", // Не имеет значения
  StartLine:  1,             // Не имеет значения
}
p.Function = append(p.Function, boundcheckFunc)

Теперь пройдёмся по всем семплам ещё раз и будем вставлять runtime.boundcheck для всех семплов, которые сейчас исполняют связанный с этим код.

for _, sample := range p.Sample {
  if len(sample.Location) == 0 {
    continue
  }
  loc := sample.Location[0]
  if len(loc.Line) == 0 {
    continue
  }
  m := loc.Mapping
  addr := int64(loc.Address + m.Offset - m.Start)
  if _, ok := ctx.bcAddresses[addr]; ok {
    insertLine(loc, boundcheckFunc)
  }
}

Функцию insertLine можно реализовать так:

func insertLine(loc *profile.Location, fn *profile.Function) {
  if loc.Line[0].Function == fn {
    return // Видимо, мы уже вставляли сюда новый вызов
  }
  newLine := profile.Line{
    Function: fn,
    // Номер строки не важен, ведь функция runtime.boundcheck
    // по-настоящему нигде не определена и не реализована
    Line: fn.StartLine, 
  }
  loc.Line = append([]profile.Line{newLine}, loc.Line...)
}

Вставляя вызов runtime.boundcheck в profile.Location.Line[0], смещая все остальные вызовы, мы расширяем стек inlined функций. Если бы мы добавляли новый profile.Location, то это бы означало non-inlined вызов.

Line[0] getlast => Line[0] runtime.boundcheck
                   Line[1] getlast

После работы с объектов профиля нам остаётся вызвать метод Write и сохранить его в новый файл:

f, err := os.Create("cpu2.out")
if err != nil {
  return err
}
defer f.Close()
if err := p.Write(f); err != nil {
  return err
}

Работаем с новым, дополненным профилем

Попробуем открыть новый профиль в pprof:

$ go tool pprof cpu2.out

Ожидаемо, runtime.boundcheck имеет отметку inline.

На скриншоте можно так же видеть runtime.nilcheck. Добавить эту информацию в профиль не сложно, а алгоритм будет абсолютно идентичен. Отличается только mark фаза, где мы пытаемся матчить машинный код. Чаще всего nil check в Go выглядит так: TESTB AX, (reg).

Во флеймграфе тоже можно что-то разглядеть:

Заключение и qpprof

Добавление в профиль псевдо-функций runtime.nilcheck и runtime.boundcheck реализовано в qpprof. Полные версии исходников из примеров можно найти там же.

Чтобы создать расширенный профиль, нужно использовать команду enrich:

$ qpprof enrich -exe=binary -o=cpu2.out cpu.out

-exe указывает путь к исполняемому файлу
-o задаёт имя выходного (расширенного) профиля
cpu.out — это наш исходный CPU профиль

На данном этапе я не могу сказать, что мы получаем очень точные значения, но, по крайней мере, мы научились дополнять профили чем-то новым. Если использовать альтернативный профилировщик для Go, который имеет более высокий hz для профилирования, либо вообще является не семплирующим, то наши шансы получить более точные метрики возрастают. Если эти другие профилировщики умеют экспортировать данные в формате pprof (profile.proto), то все приёмчики из этой статьи будут актуальны. В противном случае мы можем попробовать конвертировать профиль в родной для Go формат.

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

Анализируем bound checks в Go по CPU профилю