Hi, Maxim!

Thanks for the fixes!

Please consider my comments below.

NB: Please add tests for this patch. I suggest tests that will cover 3
branches:
* ELF reading and parsing
* Dumping functions only from PT_DYNAMIC segment (includes 2 types of
  hashes)
* Dumping only .so name, as last fallback

Also, regarding code style: please, use quater-half tabs (8 whitespacses
should be replaced with 1 tab, and indentation level is 2) for all
LuaJIT C sources.

On 04.03.22, Maxim Kokryashkin wrote:
> This commit enriches memprof's symbol table with information

<snipped>

>
> Makefile.original | 2 +-
> src/lj_memprof.c | 330 ++++++++++++++++++
> src/lj_memprof.h | 7 +-
> test/tarantool-tests/tools-utils-avl.test.lua | 59 ++++
> tools/CMakeLists.txt | 2 +
> tools/utils/avl.lua | 118 +++++++

May be we can add avl.lua utils module with the corresponding tests in
the separate commit and mark this commit as "Needed for"?
Just trying to use the most atomic commit way.
Feel free to ignore.

> tools/utils/symtab.lua | 24 +-
> 7 files changed, 537 insertions(+), 5 deletions(-)
> create mode 100644 test/tarantool-tests/tools-utils-avl.test.lua
> create mode 100644 tools/utils/avl.lua
>
> diff --git a/Makefile.original b/Makefile.original
> index 33dc2ed5..0c92df9e 100644
> --- a/Makefile.original
> +++ b/Makefile.original

<snipped>

> diff --git a/src/lj_memprof.c b/src/lj_memprof.c
> index 2d779983..71c1da7f 100644
> --- a/src/lj_memprof.c
> +++ b/src/lj_memprof.c
> @@ -8,11 +8,22 @@
> #define lj_memprof_c
> #define LUA_CORE
>
> +#define _GNU_SOURCE
> +
> +#include <assert.h>

This include is excess.

> #include <errno.h>
> +#include <stdio.h>
> +#include <stdlib.h>
> +#include <string.h>

<string.h> and <stdlib.h> are included inside lj_def.h, so this include is excess.

>
> #include "lj_arch.h"
> #include "lj_memprof.h"
>
> +#if LUAJIT_OS != LUAJIT_OS_OSX
> +#include <elf.h>
> +#include <link.h>
> +#include <sys/auxv.h>
> +#endif
> #if LJ_HASMEMPROF
>
> #include "lj_obj.h"
> @@ -66,12 +77,327 @@ static void dump_symtab_trace(struct lj_wbuf *out, const GCtrace *trace)
>
> #endif
>
> +#if LUAJIT_OS != LUAJIT_OS_OSX
> +
> +struct ghashtab_header {
> + uint32_t nbuckets;
> + uint32_t symoffset;
> + uint32_t bloom_size;
> + uint32_t bloom_shift;
> +};
> +
> +uint32_t ghashtab_size(ElfW(Addr) ghashtab)

Please use `static` as far as this function shouldn't be public.
Here and below.

> +{
> + /*
> + ** There is no easy way to get count of symbols in GNU hashtable, so the
> + ** only way to do this is to take highest possible non-empty bucket and
> + ** iterate through its symbols until the last chain is over.
> + */
> + uint32_t last_entry = 0;
> + uint32_t *cur_bucket = NULL;
> +
> + const uint32_t *chain = NULL;
> + struct ghashtab_header *header = (struct ghashtab_header*)ghashtab;
> + /*
> + ** sizeof(size_t) returns 8, if compiled with 64-bit compiler, and 4 if
> + ** compiled with 32-bit compiler. It is the best option to determine which
> + ** kind of CPU we are running on.
> + */
> + const char *buckets = (char*)ghashtab + sizeof(struct ghashtab_header) +

Nit: Please, use `char *` instead `char*`.
Here and below for all casts.

> + sizeof(size_t) * header->bloom_size;
> +
> + cur_bucket = (uint32_t*)buckets;

AFAICS, `cur_bucket` can be declared here.

> + for (uint32_t i = 0; i < header->nbuckets; ++i) {
> + if (last_entry < *cur_bucket)
> + last_entry = *cur_bucket;
> + cur_bucket++;
> + }
> +
> + if (last_entry < header->symoffset)
> + return header->symoffset;
> +
> + chain = (uint32_t*)(buckets + sizeof(uint32_t) * header->nbuckets);
> + /* The chain ends with the lowest bit set to 1. */
> + while (!(chain[last_entry - header->symoffset] & 1)) {
> + last_entry++;
> + }

Nit: { } are excess.

> +
> + return ++last_entry;
> +}
> +
> +struct symbol_resolver_conf {
> + struct lj_wbuf *buf;
> + const uint8_t header;

I'm a little bit confused about this field: do we need it?
AFAICS below, it is always SYMTAB_CFUNC. So we can just use this
constant in the dump. Also, it reduces amount of parameters in all these
functions, doesn't it?

> +};

Nit: please move this declaration below (nearby its usage).

> +
> +void write_c_symtab(ElfW(Sym*) sym, char *strtab, ElfW(Addr) so_addr,
> + size_t sym_cnt, const uint8_t header, struct lj_wbuf *buf) {

Nit: please to format this line (it should starts after opening
"(" with parameters declarations.
Also, please move `{` to the next line.

| static void write_c_symtab(ElfW(Sym*) sym, char *strtab, ElfW(Addr) so_addr,
| size_t sym_cnt, const uint8_t header,
| struct lj_wbuf *buf)
| {

Here and below for other functions.

> + char *sym_name = NULL;
> +
> + /*
> + ** Index 0 in ELF symtab is used to

Nit: something strange with line break here.

> + ** represent undefined symbols. Hence, we can just
> + ** start with index 1.
> + **
> + ** For more information, see:
> + ** https://docs.oracle.com/cd/E23824_01/html/819-0690/chapter6-79797.html
> + */
> +
> + for (ElfW(Word) sym_index = 1; sym_index < sym_cnt; sym_index++) {
> + /*
> + ** ELF32_ST_TYPE and ELF64_ST_TYPE are the same, so we can use
> + ** ELF32_ST_TYPE for both 64-bit and 32-bit ELFs.
> + **
> + ** For more, see https://github.com/torvalds/linux/blob/9137eda53752ef73148e42b0d7640a00f1bc96b1/include/uapi/linux/elf.h#L135
> + */
> + if (ELF32_ST_TYPE(sym[sym_index].st_info) == STT_FUNC) {
> + if (sym[sym_index].st_name == 0)

Nit: I suppose that these conditions can be joined via &&.

> + /* Symbol has no name. */
> + continue;
> + sym_name = &strtab[sym[sym_index].st_name];

Nit: Also, after fixing the previous comment you can move declaration for
`sym_name` here.

> + lj_wbuf_addbyte(buf, header);
> + lj_wbuf_addu64(buf, sym[sym_index].st_value + so_addr);
> + lj_wbuf_addstring(buf, sym_name);
> + }
> + }
> +}
> +
> +int dump_sht_symtab(const char *elf_name, struct lj_wbuf *buf,
> + const uint8_t header, const ElfW(Addr) so_addr) {
> + int status = 0;
> +
> + char *strtab = NULL;
> + ElfW(Shdr*) section_headers = NULL;
> + ElfW(Sym*) sym = NULL;
> + ElfW(Ehdr) elf_header = {};
> +
> + ElfW(Off) sym_off = 0;
> + ElfW(Off) strtab_off = 0;
> +
> + size_t sym_cnt = 0;
> + size_t symtab_size = 0;
> + size_t strtab_size = 0;
> + size_t strtab_index = 0;
> +
> + size_t shoff = 0; /* Section headers offset. */
> + size_t shnum = 0; /* Section headers number. */
> + size_t shentsize = 0; /* Section header entry size. */
> +
> + FILE *elf_file = fopen(elf_name, "rb");
> +
> + if (elf_file == NULL)
> + return -1;
> +
> + fread(&elf_header, sizeof(elf_header), 1, elf_file);
> + if (ferror(elf_file) != 0)

Nit: I suppose we should check amount of readen bytes and call
`ferrror()` only if we read not enough bytes.
Here and below.

> + goto error;
> + if (memcmp(elf_header.e_ident, ELFMAG, SELFMAG) != 0)
> + /* Not a valid ELF file. */
> + goto error;
> +
> + shoff = elf_header.e_shoff;
> + shnum = elf_header.e_shnum;
> + shentsize = elf_header.e_shentsize;
> +
> + if (shoff == 0 || shnum == 0 || shentsize == 0)
> + /* No sections in ELF. */
> + goto error;
> +
> + /*
> + ** Memory occupied by section headers is unlikely to be more than 160B, but
> + ** 32-bit and 64-bit ELF files may have sections of different sizes and some
> + ** of the sections may duiplicate, so we need to take that into account.
> + */
> + section_headers = calloc(shnum, shentsize);

It's better to use LuaJIT allocator here and below.

> + if (section_headers == NULL)
> + goto error;
> +
> + if (fseek(elf_file, shoff, SEEK_SET) != 0)
> + goto error;
> +
> + fread(section_headers, shentsize, shnum, elf_file);
> + if (ferror(elf_file) != 0)
> + goto error;
> +
> + for (size_t header_index = 0; header_index < shnum; ++header_index) {
> + if(section_headers[header_index].sh_type == SHT_SYMTAB) {

Nit: Pattern `section_headers[header_index]` is repeaten often below. I
suggest to use additional variable for it.

> + sym_off = section_headers[header_index].sh_offset;
> + symtab_size = section_headers[header_index].sh_size;
> + sym_cnt = symtab_size / section_headers[header_index].sh_entsize;
> +
> + strtab_index = section_headers[header_index].sh_link;
> +
> + strtab_off = section_headers[strtab_index].sh_offset;
> + strtab_size = section_headers[strtab_index].sh_size;
> + break;
> + }
> + }
> +
> + if (sym_off == 0 || strtab_off == 0 || sym_cnt == 0)
> + goto error;
> +
> + /* Load strtab and symtab into memory. */

Nit: I would like to see this comments separated -- current format is
too hard-readable due to similar structure. It will be nice to join into
one block loading of symtab and in the other one loading of strtab.

> + sym = calloc(sym_cnt, sizeof(ElfW(Sym)));
> + if (sym == NULL)
> + goto error;
> +
> + strtab = calloc(strtab_size, sizeof(char));
> + if (strtab == NULL)
> + goto error;
> +
> + if (fseek(elf_file, sym_off, SEEK_SET) != 0)
> + goto error;
> +
> + fread(sym, sizeof(ElfW(Sym)), sym_cnt, elf_file);
> + if (ferror(elf_file) != 0)
> + goto error;
> +
> + if (fseek(elf_file, strtab_off, SEEK_SET) != 0)
> + goto error;
> +
> + fread(strtab, sizeof(char), strtab_size, elf_file);
> + if (ferror(elf_file) != 0)
> + goto error;
> +
> + write_c_symtab(sym, strtab, so_addr, sym_cnt, header, buf);
> +
> + goto end;
> +
> + error:
> + status = -1;
> +
> + end:
> + free(sym);

`sym` may be not allocated when this line is reached (for example on
fread error earlier). Same for `strtab`.

> + free(strtab);
> + free(section_headers);
> + fclose(elf_file);
> +
> + return status;
> +}
> +
> +int dump_dyn_symtab(struct dl_phdr_info *info, const uint8_t header,
> + struct lj_wbuf *buf) {
> + for (size_t header_index = 0; header_index < info->dlpi_phnum; ++header_index) {

Nit: linewidth should be 120 symbols max.

> + if (info->dlpi_phdr[header_index].p_type == PT_DYNAMIC) {
> + ElfW(Dyn*) dyn = NULL;
> + ElfW(Sym*) sym = NULL;
> + ElfW(Word*) hashtab = NULL;
> + ElfW(Addr) ghashtab = 0;
> + ElfW(Word) sym_cnt = 0;
> +
> + char *strtab = 0;
> +
> + dyn = (ElfW(Dyn)*)(info->dlpi_addr + info->dlpi_phdr[header_index].p_vaddr);

Ditto.

> +
> + for(; dyn->d_tag != DT_NULL; dyn++) {
> + switch(dyn->d_tag) {
> + case DT_HASH:

Nit: swich case should have same indent.

> + hashtab = (ElfW(Word*))dyn->d_un.d_ptr;
> + break;
> + case DT_GNU_HASH:
> + ghashtab = dyn->d_un.d_ptr;
> + break;
> + case DT_STRTAB:
> + strtab = (char*)dyn->d_un.d_ptr;
> + break;
> + case DT_SYMTAB:
> + sym = (ElfW(Sym*))dyn->d_un.d_ptr;
> + break;
> + default:
> + break;
> + }
> + }
> +
> + if ((hashtab == NULL && ghashtab == 0)
> + || strtab == NULL || sym == NULL)

Nit: Looks like these lines may be joined.

> + /* Not enough data to resolve symbols. */
> + return 1;
> +
> + /*
> + ** A hash table consists of Elf32_Word or Elf64_Word objects that provide for
> + ** symbol table access. Hash table has the following organization:
> + ** +-------------------+

Nit: something strange with formating of table:).

> + ** | nbucket |
> + ** +-------------------+
> + ** | nchain |
> + ** +-------------------+
> + ** | bucket[0] |
> + ** | ... |
> + ** | bucket[nbucket-1] |
> + ** +-------------------+
> + ** | chain[0] |
> + ** | ... |
> + ** | chain[nchain-1] |
> + ** +-------------------+
> + ** Chain table entries parallel the symbol table. The number of symbol
> + ** table entries should equal nchain, so symbol table indexes also select
> + ** chain table entries. Since the chain array values are indexes for not only
> + ** the chain array itself, but also for the symbol table, the chain array must
> + ** be the same size as the symbol table. This makes nchain equal to the length
> + ** of the symbol table.

Nit: Please format this comment to fit linewidth 120 symbols.

> + **
> + ** For more, see https://docs.oracle.com/cd/E23824_01/html/819-0690/chapter6-48031.html
> + */
> + sym_cnt = ghashtab == 0 ? hashtab[1] : ghashtab_size(ghashtab);
> + write_c_symtab(sym, strtab, info->dlpi_addr, sym_cnt, header, buf);
> + return 0;
> + }
> + }
> +
> + return 1;
> +}
> +
> +int resolve_symbolnames(struct dl_phdr_info *info, size_t info_size, void *data)
> +{
> + struct symbol_resolver_conf *conf = data;
> + const uint8_t header = conf->header;
> + struct lj_wbuf *buf = conf->buf;
> +
> + UNUSED(info_size);
> +
> + /* Skip vDSO library. */

Nit: something strange with indentation here.

> + if (info->dlpi_addr == getauxval(AT_SYSINFO_EHDR))
> + return 0;
> +
> + /*
> + ** Main way: try to open ELF and read SHT_SYMTAB, SHT_STRTAB and SHT_HASH
> + ** sections from it.
> + */
> + if (dump_sht_symtab(info->dlpi_name, buf, header, info->dlpi_addr) == 0) {
> + return 0;
> + }
> +
> + /* First fallback: dump functions only from PT_DYNAMIC segment. */
> + if(dump_dyn_symtab(info, header, buf) == 0) {
> + return 0;
> + }

Nit: I suggest to refactor this section like the following:
| if () {
| /* ... */
| } elseif () {
| /* ... */
| } else {
| /* ... */
| }
| return 0;

Feel free to ignore.

> +
> + /*
> + ** Last resort: dump ELF size and address to show .so name for its functions
> + ** in memprof output.
> + */
> + lj_wbuf_addbyte(buf, header);
> + lj_wbuf_addu64(buf, info->dlpi_addr);
> + lj_wbuf_addstring(buf, info->dlpi_name);
> +
> + return 0;
> +}
> +
> +#endif

Nit: Please, add inline comment that this is `LUAJIT_OS != LUAJIT_OS_OSX`

> +
> static void dump_symtab(struct lj_wbuf *out, const struct global_State *g)
> {
> const GCRef *iter = &g->gc.root;
> const GCobj *o;
> const size_t ljs_header_len = sizeof(ljs_header) / sizeof(ljs_header[0]);
>
> +#if LUAJIT_OS != LUAJIT_OS_OSX
> + struct symbol_resolver_conf conf = {
> + out,
> + SYMTAB_CFUNC,
> + };
> +#endif
> +
> /* Write prologue. */
> lj_wbuf_addn(out, ljs_header, ljs_header_len);
>
> @@ -95,6 +421,10 @@ static void dump_symtab(struct lj_wbuf *out, const struct global_State *g)
> iter = &o->gch.nextgc;
> }
>
> +#if LUAJIT_OS != LUAJIT_OS_OSX
> + /* Write symbols. */

Typo? Do you mean C symbols?

> + dl_iterate_phdr(resolve_symbolnames, &conf);
> +#endif
> lj_wbuf_addbyte(out, SYMTAB_FINAL);
> }
>
> diff --git a/src/lj_memprof.h b/src/lj_memprof.h
> index 395fb429..0327a205 100644
> --- a/src/lj_memprof.h
> +++ b/src/lj_memprof.h

<snipped>

> diff --git a/test/tarantool-tests/tools-utils-avl.test.lua b/test/tarantool-tests/tools-utils-avl.test.lua
> new file mode 100644
> index 00000000..17cc7a85
> --- /dev/null
> +++ b/test/tarantool-tests/tools-utils-avl.test.lua
> @@ -0,0 +1,59 @@
> +local avl = require "utils.avl"

Nit: Please, use require("modulename") for consistency.
Also, for our tests we are using '' instead "" for strings.

> +local tap = require("tap")
> +
> +local test = tap.test("tools-utils-avl")
> +test:plan(7)
> +
> +local function traverse(node, result)
> + if node ~= nil then
> + table.insert(result, node.key)
> + traverse(node.left, result)
> + traverse(node.right, result)
> + end
> + return result
> +end
> +
> +local function batch_insert(root, values)
> + for i = 1, #values do
> + root = avl.insert(root, values[i])
> + end
> +
> + return root
> +end
> +
> +local function compare(arr1, arr2)
> + for i, v in pairs(arr1) do

Nit: this tab looks confusing.

> + if v ~= arr2[i] then
> + return false
> + end
> + end
> + return true
> +end
> +
> +-- 1L rotation test.
> +local root = batch_insert(nil, {1, 2, 3})
> +test:ok(compare(traverse(root, {}), {2, 1, 3}))
> +
> +-- 1R rotation test.
> +root = batch_insert(nil, {3, 2, 1})
> +test:ok(compare(traverse(root, {}), {2, 1, 3}))
> +
> +-- 2L rotation test.
> +root = batch_insert(nil, {1, 3, 2})
> +test:ok(compare(traverse(root, {}), {2, 1, 3}))
> +
> +-- 2R rotation test.
> +root = batch_insert(nil, {3, 1, 2})
> +test:ok(compare(traverse(root, {}), {2, 1, 3}))
> +
> +-- Exact upper bound.
> +test:ok(avl.upper_bound(root, 1) == 1)
> +
> +-- No upper bound.
> +test:ok(avl.upper_bound(root, -10) == nil)
> +
> +-- Not exact upper bound.
> +test:ok(avl.upper_bound(root, 2.75) == 2)
> +
> +
> +

Nit: Please, remove unnecessary empty lines.
Nit: Please, and os.exit() like it is done in other tests.

> diff --git a/tools/CMakeLists.txt b/tools/CMakeLists.txt
> index 61830e44..c6803d00 100644
> --- a/tools/CMakeLists.txt
> +++ b/tools/CMakeLists.txt
> @@ -30,6 +30,7 @@ else()
> memprof/humanize.lua
> memprof/parse.lua
> memprof.lua
> + utils/avl.lua
> utils/bufread.lua
> utils/symtab.lua
> )
> @@ -46,6 +47,7 @@ else()
> COMPONENT tools-parse-memprof
> )
> install(FILES
> + ${CMAKE_CURRENT_SOURCE_DIR}/utils/avl.lua
> ${CMAKE_CURRENT_SOURCE_DIR}/utils/bufread.lua
> ${CMAKE_CURRENT_SOURCE_DIR}/utils/symtab.lua
> DESTINATION ${LUAJIT_DATAROOTDIR}/utils
> diff --git a/tools/utils/avl.lua b/tools/utils/avl.lua
> new file mode 100644
> index 00000000..98c15bd7
> --- /dev/null
> +++ b/tools/utils/avl.lua
> @@ -0,0 +1,118 @@
> +local math = require'math'

Nit: this require is excess.

> +
> +local M = {}
> +local max = math.max

<snipped>

> +function M.upper_bound(node, key)
> + if node == nil then
> + return nil, nil
> + end
> + -- Explicit match.
> + if key == node.key then
> + return node.key, node.value
> + elseif key < node.key then
> + return M.upper_bound(node.left, key)
> + elseif key > node.key then
> + local right_key, value = M.upper_bound(node.right, key)
> + right_key = right_key or node.key
> + value = value or node.value
> +
> + return right_key, value
> + end
> +end
> +

Nit: This empty line is excess.

> +
> +return M
> +

Nit: This empty line is excess.

> diff --git a/tools/utils/symtab.lua b/tools/utils/symtab.lua
> index c7fcf77c..aa66269c 100644
> --- a/tools/utils/symtab.lua
> +++ b/tools/utils/symtab.lua
> @@ -6,6 +6,8 @@
>
> local bit = require "bit"
>
> +local avl = require "utils.avl"
> +
> local band = bit.band
> local string_format = string.format
>
> @@ -15,7 +17,8 @@ local LJS_EPILOGUE_HEADER = 0x80
> local LJS_SYMTYPE_MASK = 0x03
>
> local SYMTAB_LFUNC = 0
> -local SYMTAB_TRACE = 1
> +local SYMTAB_CFUNC = 1
> +local SYMTAB_TRACE = 2
>
> local M = {}
>
> @@ -50,15 +53,27 @@ local function parse_sym_trace(reader, symtab)
> }
> end
>
> +-- Parse a single entry in a symtab: .so library
> +local function parse_sym_cfunc(reader, symtab)
> + local addr = reader:read_uleb128()
> + local name = reader:read_string()
> +
> + symtab.cfunc = avl.insert(symtab.cfunc, addr, {
> + name = name
> + })
> +end

Side note: Does it sufficient for all 3 cases mentioned above as far as
format is the same?

> +
> local parsers = {
> [SYMTAB_LFUNC] = parse_sym_lfunc,
> [SYMTAB_TRACE] = parse_sym_trace,
> + [SYMTAB_CFUNC] = parse_sym_cfunc
> }
>
> function M.parse(reader)
> local symtab = {
> lfunc = {},
> trace = {},
> + cfunc = nil,
> }
> local magic = reader:read_octets(3)
> local version = reader:read_octets(1)
> @@ -93,7 +108,6 @@ function M.parse(reader)
> parsers[sym_type](reader, symtab)
> end
> end
> -

Nit: This change is unnecessary.

> return symtab
> end
>
> @@ -135,6 +149,12 @@ function M.demangle(symtab, loc)
> return string_format("%s:%d", symtab.lfunc[addr].source, loc.line)
> end
>
> + local key, value = avl.upper_bound(symtab.cfunc, addr)
> +
> + if key then
> + return string_format("%s:%#x", value.name, key)
> + end
> +
> return string_format("CFUNC %#x", addr)
> end
>
> --
> 2.35.1
>

--
Best regards,
Sergey Kaplun