Недавно я приступил к изучению подсистемы pmbus ядра Linux и начал вручную рисовать граф вызовов, чтобы показать себя. Излишне говорить, что это стало немного утомительно, поэтому я начал спрашивать Google, знает ли он о лучшем подходе. Google привел меня к вопросу StackOverflow в том же духе, и один из ответов указывал на tceetree.
tceetree выглядел как решение, которое мне подошло: он анализирует базы данных cscope для создания точечного орграфа представления графа вызовов. Я уже использую cscope как часть своего рабочего процесса, поэтому отсутствие необходимости использовать какой-либо другой инструмент для анализа кода было выигрышным решением. Генерация вывода graphviz также казалась отличным решением.
Учитывая, что это проект с открытым исходным кодом, я решил взять исходный код и построить его. На самом деле это оказалось более утомительно, чем я надеялся, поэтому, чтобы упростить доступ, я выложил это на github.
Кроме того, я обнаружил, что хотя tceetree полезен для небольших кодовых баз, он плохо работает с большими кодовыми базами, такими как ядро Linux. Запуск tceetree для базы данных cscope для ядра 4.12 потребовал 956 м37 с для создания выходного файла graphviz. Это неоптимально, поэтому я решил улучшить его и отправил результаты в мою ветку wip. Это требует дальнейшего тестирования, но некоторые быстрые эксперименты показали, что он создает графики, эквивалентные исходному источнику.
Итак, углубившись — чтобы выяснить, где что-то пошло не так, я обратился к perf, даже не взглянув на источник:
# Overhead Shared Object Symbol
# ........ ................ ...........................
#
66.93% libc-2.24.so [.] __strcmp_sse2_unaligned
28.01% tceetree.v1.0.1 [.] ttreefindnode
2.88% tceetree.v1.0.1 [.] _init
...
Это уже показывает несколько проблем: распределение времени сильно искажено, и, учитывая, что реализация интерфейса libc все время ворует, сам алгоритм неоптимален. Мы вряд ли выжмем сока из __strcmp_sse2_unaligned.
Детализируя анализ perf ttreefindnode(), мы видим, что 75% времени тратится на подготовку к вызову библиотеки, и около 20% времени приходится на разыменование указателя:
│5 0000000000002a00 <ttreefindnode>:
│6 ttreefindnode():
0.00 │ test %rsi,%rsi
│ push %r12
│ push %rbp
│ push %rbx
│ ↓ je 55
│ mov (%rdi),%rbx
│ mov %rdx,%r12
│ mov %rsi,%rbp
│ test %rbx,%rbx
│ ↓ je 4d
│ nop
10.98 │20: mov (%rbx),%rdi
75.33 │ mov %rbp,%rsi
1.40 │ → callq .plt.got+0x58
0.93 │ test %eax,%eax
0.15 │ ↓ jne 44
│ test %r12,%r12
│ ↓ je 4d
│ mov 0x8(%rbx),%rdi
0.00 │ mov %r12,%rsi
│ → callq .plt.got+0x58
│ test %eax,%eax
│ ↓ je 4d
10.75 │44: mov 0x20(%rbx),%rbx
0.25 │ test %rbx,%rbx
0.15 │ ↑ jne 20
│4d: mov %rbx,%rax
│ pop %rbx
0.05 │ pop %rbp
│ pop %r12
│ ← retq
│55: xor %ebx,%ebx
│ ↑ jmp 4d
Глядя на внедрение ttreefindnode и ttree.[ch] в целом, мы обнаруживаем, что стратегия реализации tceetree заключается в отслеживании «узлов», которые являются местоположениями определений функций, а затем создании списка «ветвей», которые фиксируют отношения вызывающего/вызываемого путем указания на соответствующие узлы. . В обоих случаях эти структуры объединены в два связанных списка — один для узлов и один для ветвей.
Возвращаясь к приведенному выше листингу сборки и профилированию, эта стратегия работы со списками работает так плохо, как можно было бы ожидать: при вставке нового узла в список мы сначала должны выяснить, присутствует ли он уже, что, если это не требует итерации всего списка.
Итак, к чертежной доске. Критические структуры следующие:
typedef struct ttreenode_st
{
char *funname;
char *filename;
...
ttreenode_st *next;
} ttreenode_t;
typedef struct ttreebranch_st
{
char *filename;
ttreenode_t *parent;
ttreenode_t *child;
...
ttreebranch_st *next;
} ttreebranch_t;
typedef struct ttree_st
{
ttreenode_t *firstnode;
ttreenode_t *lastnode;
ttreebranch_t *firstbranch;
ttreebranch_t *lastbranch;
} ttree_t;
Вот реализация ttreefindnode():
// find a node with specified function name and file name and
// return its pointer or NULL if not found
ttreenode_t* ttreefindnode(ttree_t *ptree, char *funname,
char *filename)
{
ttreenode_t *pnode;
if (!funname)
return NULL;
pnode = ptree->firstnode;
while (pnode != NULL)
{
if (strcmp(pnode->funname, funname) == 0 &&
(filename == NULL ||
strcmp(pnode->filename, filename) == 0))
break;
pnode = pnode->next;
}
return pnode;
}
Здесь мы видим, что аргумент имени файла является необязательным. Это используется для таких случаев, как библиотечные функции, когда имя функции становится известным, но исходный файл не включается в базу данных cscope. По определению они становятся листовыми узлами, поскольку мы не можем знать их реализацию.
Очень похоже, что это ttreefindbranch:
// find a branch with specified caller, callee and file name and
// return its pointer or NULL if not found; if pstart == NULL
// search will be performed over all branches, otherwise it will
// start from the specified branch
ttreebranch_t* ttreefindbranch(ttree_t *ptree, ttreenode_t *caller,
ttreenode_t *callee, char *filename,
ttreebranch_t *pstart)
{
ttreebranch_t *pbranch;
if (pstart == NULL)
pbranch = ptree->firstbranch;
else
pbranch = pstart;
if (caller == NULL && callee == NULL)
pbranch = NULL;
while (pbranch != NULL)
{
if ((caller == NULL || pbranch->parent == caller) &&
(callee == NULL || pbranch->child == callee) &&
(filename == NULL ||
strcmp(pbranch->filename, filename) == 0))
break;
pbranch = pbranch->next;
}
return pbranch;
}
Здесь видно, что вызывающий объект, вызываемый объект и имя файла потенциально могут быть NULL. Назначение всем им NULL для данного вызова не имеет особого смысла, поэтому в интересах ограничения случаев мы можем отследить сайты вызовов, что приведет нас к ttreeaddbranch() в ttree.c и outsubtree() в outtree.c:
// output of a subtree (forward and backward) starting from pnode
int outsubtree(ttree_t *ptree, treeparam_t *pparam,
ttreenode_t *pnode, int fdepth, int bdepth, int colr)
{
...
do {
// find all branches starting from this node
pbranch = ttreefindbranch(ptree, pnode, NULL,
pnode->filename, pbranch);
...
} while(pbranch != NULL);
...
do {
// find all branches with this node as destination
pbranch = ttreefindbranch(ptree, NULL, pnode, NULL,
pbranch);
...
} while(pbranch != NULL);
...
Таким образом, либо указывается вызывающий объект и его имя файла, либо указывается вызываемый объект. Согласно комментариям, первый случай находит все функции, которые вызывает вызывающий объект, а второй находит все функции, вызывающие вызываемый объект.
В случае ttreeaddbranch() предоставляются все три параметра, идентифицирующие конкретное отношение.
Интуитивно вызывающие могут вызывать несколько функций, поэтому нам все равно нужно будет поддерживать списки, чтобы удовлетворить запрос вызываемых. Точно так же у функции может быть несколько вызывающих объектов. Однако эти списки идентифицируются либо вызываемой, либо вызывающей стороной, и, таким образом, поддаются структуре данных карты.
Благодаря интеграции модуля strmap из CCAN и внесению единственного концептуального изменения от единственного использования связанных списков к картам карт или списков, ветвь wip сокращает время выполнения tceetree на ядре 4.12 с 956 м37 до 0 м23 с, для ускорения в 2495 раз. Я избавлю себя от утомительного описания деталей изменения, так как они довольно прямолинейны, как только будут поняты ограничения, изложенные выше.
Так как же сейчас tceetree проводит время? Ну, его время доминирует над фактической генерацией вывода graphviz:
# Overhead Shared Object Symbol
# ........ ................ ...................
#
45.12% tceetree [.] outtree
23.82% tceetree [.] closest
...
0.25% tceetree [.] ttreefindbranch
0.25% tceetree [.] ttreeaddbranch
И, как мы видим, ttreefindbranch() теперь незначительная точка в измерениях.
Итак: Следующая остановка — оптимизация outtree() и closest(). Но в целом это приводит к тому, что выбор подходящих структур данных крайне важен для производительности. А если вы используете C, то вам обязательно стоит уделить время изучению полного списка модулей CCAN!
