[Tarantool-patches] [PATCH luajit v5 0/2] memprof: add resolving capabilities

[Tarantool-patches] [PATCH luajit v5 0/2] memprof: add resolving capabilities

[Maxim Kokryashkin via Tarantool-patches]

Changes in v5:
- Fixed comments as per review by Sergey
- Added resolution based on ELF sections
- Disabled resolution for OSX
- Rebased on `tarantool` branch

Also, there are a few comments in the following letters.

Maxim Kokryashkin (2):
  memprof: extend symtab with C-symbols
  memprof: enrich symtab with newly loaded symbols

 Makefile.original                             |   2 +-
 src/lj_memprof.c                              | 396 +++++++++++++++++-
 src/lj_memprof.h                              |  15 +-
 test/tarantool-tests/tools-utils-avl.test.lua |  59 +++
 tools/CMakeLists.txt                          |   2 +
 tools/memprof.lua                             |   5 +
 tools/memprof/parse.lua                       |  19 +
 tools/utils/avl.lua                           | 118 ++++++
 tools/utils/symtab.lua                        |  28 +-
 9 files changed, 631 insertions(+), 13 deletions(-)
 create mode 100644 test/tarantool-tests/tools-utils-avl.test.lua
 create mode 100644 tools/utils/avl.lua

-- 
2.35.1

[Tarantool-patches] [PATCH luajit v5 1/2] memprof: extend symtab with C-symbols

[Maxim Kokryashkin via Tarantool-patches]

This commit enriches memprof's symbol table with information
about C-symbols. The parser is updated correspondingly.

If there is .symtab section or at least .dynsym segment in
a shared library, then the following data is stored in symtab
for each symbol:

| SYMTAB_CFUNC | symbol address | symbol name |
  1 byte            8 bytes
  magic
  number

If none of those are present, then instead of a symbol name
and its address there will be name and address of a
shared library containing that symbol.

Part of tarantool/tarantool#5813
---
>> The following data is stored in event for each newly loaded symbol:
>> | (AEVENT_SYMTAB | ASOURCE_CFUNC) | symbol address | symbol name |
>> 1 byte 8 bytes
>> magic
>> number
>
> What do you think of dumping so name too for convenience?
> For example, dump an empty so name stands for Tarantool|LuaJIT sources,
> but the other one is related to some other .so library that is loaded by
> a user.
> CC-ed Igor here.

I don't think it's helpful, since one of the key ideas is to be
independent from .so libs on client-side. However, I agree that some
kind of a flag marking .so files, which are not related to Tarantool
sources, may provide some help during debugging.
Still, let's wait for Igor's opinion.

>> static const unsigned char ljs_header[] = {'l', 'j', 's', LJS_CURRENT_VERSION,
>> 0x0, 0x0, 0x0};
>
> Should we update LJS header due to the new format of the symtab stream?
I see no reason for that -- LJS version bump is sufficient.

 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 +++++++
 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
@@ -100,7 +100,7 @@ FILES_JITLIB= bc.lua bcsave.lua dump.lua p.lua v.lua zone.lua \
 	      dis_x86.lua dis_x64.lua dis_arm.lua dis_arm64.lua \
 	      dis_arm64be.lua dis_ppc.lua dis_mips.lua dis_mipsel.lua \
 	      dis_mips64.lua dis_mips64el.lua vmdef.lua
-FILES_UTILSLIB= bufread.lua symtab.lua
+FILES_UTILSLIB= avl.lua bufread.lua symtab.lua
 FILES_MEMPROFLIB= parse.lua humanize.lua
 FILES_TOOLSLIB= memprof.lua
 FILE_TMEMPROF= luajit-parse-memprof
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>
 #include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
 
 #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)
+{
+    /*
+    ** 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) +
+                          sizeof(size_t) * header->bloom_size;
+
+    cur_bucket = (uint32_t*)buckets;
+    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++;
+    }
+
+    return ++last_entry;
+}
+
+struct symbol_resolver_conf {
+  struct lj_wbuf *buf;
+  const uint8_t header;
+};
+
+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) {
+  char *sym_name = NULL;
+
+  /*
+  ** Index 0 in ELF symtab is used to
+  ** 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)
+        /* Symbol has no name. */
+        continue;
+      sym_name = &strtab[sym[sym_index].st_name];
+      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)
+    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);
+  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) {
+        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. */
+  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);
+  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) {
+    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);
+
+      for(; dyn->d_tag != DT_NULL; dyn++) {
+        switch(dyn->d_tag) {
+          case DT_HASH:
+            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)
+        /* 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:
+      ** +-------------------+
+      ** | 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.
+      **
+      ** 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. */
+  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;
+  }
+
+  /*
+  ** 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
+
 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. */
+  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
@@ -25,13 +25,15 @@
 ** prologue       := 'l' 'j' 's' version reserved
 ** version        := <BYTE>
 ** reserved       := <BYTE> <BYTE> <BYTE>
-** sym            := sym-lua | sym-trace | sym-final
+** sym            := sym-lua | sym-cfunc | sym-trace | sym-final
 ** sym-lua        := sym-header sym-addr sym-chunk sym-line
 ** sym-trace      := sym-header trace-no trace-addr sym-addr sym-line
 ** sym-header     := <BYTE>
 ** sym-addr       := <ULEB128>
 ** sym-chunk      := string
 ** sym-line       := <ULEB128>
+** sym-cfunc      := sym-header sym-addr sym-name
+** sym-name       := string
 ** sym-final      := sym-header
 ** trace-no       := <ULEB128>
 ** trace-addr     := <ULEB128>
@@ -54,7 +56,8 @@
 */
 
 #define SYMTAB_LFUNC ((uint8_t)0)
-#define SYMTAB_TRACE ((uint8_t)1)
+#define SYMTAB_CFUNC ((uint8_t)1)
+#define SYMTAB_TRACE ((uint8_t)2)
 #define SYMTAB_FINAL ((uint8_t)0x80)
 
 #define LJM_CURRENT_FORMAT_VERSION 0x02
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"
+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
+    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)
+
+
+
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'
+
+local M = {}
+local max = math.max
+
+local function create_node(key, value)
+  return {
+    key = key,
+    value = value,
+    left = nil,
+    right = nil,
+    height = 1,
+  }
+end
+
+local function height(node)
+  if node == nil then
+    return 0
+  end
+  return node.height
+end
+
+local function update_height(node)
+  node.height = 1 + max(height(node.left), height(node.right))
+end
+
+local function get_balance(node)
+  if node == nil then
+    return 0
+  end
+  return height(node.left) - height(node.right)
+end
+
+local function rotate_left(node)
+    local r_subtree = node.right;
+    local rl_subtree = r_subtree.left;
+
+    r_subtree.left = node;
+    node.right = rl_subtree;
+
+    update_height(node)
+    update_height(r_subtree)
+
+    return r_subtree;
+end
+
+local function rotate_right(node)
+    local l_subtree = node.left
+    local lr_subtree = l_subtree.right;
+
+    l_subtree.right = node;
+    node.left = lr_subtree;
+
+    update_height(node)
+    update_height(l_subtree)
+
+    return l_subtree;
+end
+
+local function rebalance(node, key)
+  local balance = get_balance(node)
+
+  if -1 <= balance and balance <=1 then
+    return node
+  end
+
+  if balance > 1 and key < node.left.key then
+    return rotate_right(node)
+  elseif balance < -1 and key > node.right.key then
+    return rotate_left(node)
+  elseif balance > 1 and key > node.left.key then
+    node.left = rotate_left(node.left)
+    return rotate_right(node)
+  elseif balance < -1 and key < node.right.key then
+    node.right = rotate_right(node.right)
+    return rotate_left(node)
+  end
+end
+
+function M.insert(node, key, value)
+  if node == nil then
+    return create_node(key, value)
+  end
+
+  if key < node.key then
+    node.left = M.insert(node.left, key, value)
+  elseif key > node.key then
+    node.right = M.insert(node.right, key, value)
+  else
+    node.key = key
+    node.value = value
+  end
+
+  update_height(node)
+  return rebalance(node, key)
+end
+
+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
+
+
+return M
+
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
+
 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
-
   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

Re: [Tarantool-patches] [PATCH luajit v5 1/2] memprof: extend symtab with C-symbols

[Sergey Kaplun via Tarantool-patches]

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

Re: [Tarantool-patches] [PATCH luajit v5 1/2] memprof: extend symtab with C-symbols

[Maxim Kokryashkin via Tarantool-patches]

[-- Attachment #1: Type: text/plain, Size: 20940 bytes --]


Hi!
 
Thanks for the comments!
 
I have a question regarding tests: is it OK to bring a test .so file for each case
or should I do it in a different way?
--
Best regards,
Maxim Kokryashkin
 
 
> 
>>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
> 

[-- Attachment #2: Type: text/html, Size: 24598 bytes --]

[Tarantool-patches] [PATCH luajit v5 2/2] memprof: enrich symtab with newly loaded symbols

[Maxim Kokryashkin via Tarantool-patches]

This commit lets memprof extend its symtab when new
C-symbols appear after dlopen. The following data is
stored in event stream for each newly loaded symbol:

| (AEVENT_SYMTAB | ASOURCE_CFUNC) | symbol address | symbol name |
              1 byte                   8 bytes
              magic
              number

Resolves tarantool/tarantool#5813
---
 src/lj_memprof.c        | 70 +++++++++++++++++++++++++++++++++++------
 src/lj_memprof.h        |  8 ++++-
 tools/memprof.lua       |  5 +++
 tools/memprof/parse.lua | 19 +++++++++++
 tools/utils/symtab.lua  |  4 +++
 5 files changed, 96 insertions(+), 10 deletions(-)

diff --git a/src/lj_memprof.c b/src/lj_memprof.c
index 71c1da7f..2b609dfa 100644
--- a/src/lj_memprof.c
+++ b/src/lj_memprof.c
@@ -128,6 +128,11 @@ uint32_t ghashtab_size(ElfW(Addr) ghashtab)
 struct symbol_resolver_conf {
   struct lj_wbuf *buf;
   const uint8_t header;
+
+  uint32_t cur_lib;
+  uint32_t lib_cnt_prev;
+  uint32_t to_dump_cnt;
+  uint32_t *lib_cnt;
 };
 
 void write_c_symtab(ElfW(Sym*) sym, char *strtab, ElfW(Addr) so_addr,
@@ -353,22 +358,46 @@ int resolve_symbolnames(struct dl_phdr_info *info, size_t info_size, void *data)
   const uint8_t header = conf->header;
   struct lj_wbuf *buf = conf->buf;
 
-  UNUSED(info_size);
+  const uint32_t lib_cnt_prev = *conf->lib_cnt;
+  uint32_t lib_cnt = 0;
+
+  /*
+  ** Check that dlpi_adds and dlpi_subs fields are available.
+  ** Assertion was taken from the GLIBC tests:
+  ** https://code.woboq.org/userspace/glibc/elf/tst-dlmodcount.c.html#37
+  */
+  assert(info_size > offsetof(struct dl_phdr_info, dlpi_subs)
+      + sizeof(info->dlpi_subs));
+
+  lib_cnt = info->dlpi_adds - info->dlpi_subs;
+  conf->lib_cnt_prev = *conf->lib_cnt;
 
-    /* Skip vDSO library. */
+  /* Skip vDSO library. */
   if (info->dlpi_addr == getauxval(AT_SYSINFO_EHDR))
     return 0;
 
+  if ((conf->to_dump_cnt = info->dlpi_adds - lib_cnt_prev) == 0)
+    /* No new libraries, stop resolver. */
+    return 1;
+
+  if (conf->cur_lib < lib_cnt - conf->to_dump_cnt) {
+    /* That lib is already dumped, skip it. */
+    ++conf->cur_lib;
+    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) {
+    ++conf->cur_lib;
     return 0;
   }
 
   /* First fallback: dump functions only from PT_DYNAMIC segment. */
   if(dump_dyn_symtab(info, header, buf) == 0) {
+    ++conf->cur_lib;
     return 0;
   }
 
@@ -380,12 +409,13 @@ int resolve_symbolnames(struct dl_phdr_info *info, size_t info_size, void *data)
   lj_wbuf_addu64(buf, info->dlpi_addr);
   lj_wbuf_addstring(buf, info->dlpi_name);
 
+  ++conf->cur_lib;
   return 0;
 }
 
 #endif
 
-static void dump_symtab(struct lj_wbuf *out, const struct global_State *g)
+static void dump_symtab(struct lj_wbuf *out, const struct global_State *g, uint32_t *lib_cnt)
 {
   const GCRef *iter = &g->gc.root;
   const GCobj *o;
@@ -395,7 +425,13 @@ static void dump_symtab(struct lj_wbuf *out, const struct global_State *g)
   struct symbol_resolver_conf conf = {
     out,
     SYMTAB_CFUNC,
+    0,
+    *lib_cnt,
+    0,
+    lib_cnt
   };
+#else
+  UNUSED(lib_cnt);
 #endif
 
   /* Write prologue. */
@@ -454,6 +490,7 @@ struct memprof {
   struct alloc orig_alloc; /* Original allocator. */
   struct lj_memprof_options opt; /* Profiling options. */
   int saved_errno; /* Saved errno when profiler deinstrumented. */
+  uint32_t lib_cnt; /* Number of currently loaded libs. */
 };
 
 static struct memprof memprof = {0};
@@ -489,15 +526,30 @@ static void memprof_write_lfunc(struct lj_wbuf *out, uint8_t aevent,
 }
 
 static void memprof_write_cfunc(struct lj_wbuf *out, uint8_t aevent,
-				const GCfunc *fn)
+				const GCfunc *fn, uint32_t *lib_cnt)
 {
+#if LUAJIT_OS != LUAJIT_OS_OSX
+  /* Check if there are any new libs. */
+  struct symbol_resolver_conf conf = {
+    out,
+    AEVENT_SYMTAB | ASOURCE_CFUNC,
+    0,
+    *lib_cnt,
+    0,
+    lib_cnt
+  };
+  dl_iterate_phdr(resolve_symbolnames, &conf);
+#else
+  UNUSED(lib_cnt);
+#endif
+
   lj_wbuf_addbyte(out, aevent | ASOURCE_CFUNC);
   lj_wbuf_addu64(out, (uintptr_t)fn->c.f);
 }
 
 static void memprof_write_ffunc(struct lj_wbuf *out, uint8_t aevent,
 				GCfunc *fn, struct lua_State *L,
-				cTValue *frame)
+				cTValue *frame, uint32_t *lib_cnt)
 {
   cTValue *pframe = frame_prev(frame);
   GCfunc *pfn = frame_func(pframe);
@@ -510,7 +562,7 @@ static void memprof_write_ffunc(struct lj_wbuf *out, uint8_t aevent,
   if (pfn != NULL && isluafunc(pfn))
     memprof_write_lfunc(out, aevent, pfn, L, frame);
   else
-    memprof_write_cfunc(out, aevent, fn);
+    memprof_write_cfunc(out, aevent, fn, lib_cnt);
 }
 
 static void memprof_write_func(struct memprof *mp, uint8_t aevent)
@@ -523,9 +575,9 @@ static void memprof_write_func(struct memprof *mp, uint8_t aevent)
   if (isluafunc(fn))
     memprof_write_lfunc(out, aevent, fn, L, NULL);
   else if (isffunc(fn))
-    memprof_write_ffunc(out, aevent, fn, L, frame);
+    memprof_write_ffunc(out, aevent, fn, L, frame, &mp->lib_cnt);
   else if (iscfunc(fn))
-    memprof_write_cfunc(out, aevent, fn);
+    memprof_write_cfunc(out, aevent, fn, &mp->lib_cnt);
   else
     lua_assert(0);
 }
@@ -661,7 +713,7 @@ int lj_memprof_start(struct lua_State *L, const struct lj_memprof_options *opt)
 
   /* Init output. */
   lj_wbuf_init(&mp->out, mp_opt->writer, mp_opt->ctx, mp_opt->buf, mp_opt->len);
-  dump_symtab(&mp->out, mp->g);
+  dump_symtab(&mp->out, mp->g, &mp->lib_cnt);
 
   /* Write prologue. */
   lj_wbuf_addn(&mp->out, ljm_header, ljm_header_len);
diff --git a/src/lj_memprof.h b/src/lj_memprof.h
index 0327a205..ea8f2362 100644
--- a/src/lj_memprof.h
+++ b/src/lj_memprof.h
@@ -71,10 +71,11 @@
 ** prologue       := 'l' 'j' 'm' version reserved
 ** version        := <BYTE>
 ** reserved       := <BYTE> <BYTE> <BYTE>
-** event          := event-alloc | event-realloc | event-free
+** event          := event-alloc | event-realloc | event-free | event-symtab
 ** event-alloc    := event-header loc? naddr nsize
 ** event-realloc  := event-header loc? oaddr osize naddr nsize
 ** event-free     := event-header loc? oaddr osize
+** event-symtab   := event-header sym-addr sym-name
 ** event-header   := <BYTE>
 ** loc            := loc-lua | loc-c | loc-trace
 ** loc-lua        := sym-addr line-no
@@ -88,7 +89,11 @@
 ** naddr          := <ULEB128>
 ** osize          := <ULEB128>
 ** nsize          := <ULEB128>
+** sym-name       := string
 ** epilogue       := event-header
+** string         := string-len string-payload
+** string-len     := <ULEB128>
+** string-payload := <BYTE> {string-len}
 **
 ** <BYTE>   :  A single byte (no surprises here)
 ** <ULEB128>:  Unsigned integer represented in ULEB128 encoding
@@ -107,6 +112,7 @@
 */
 
 /* Allocation events. */
+#define AEVENT_SYMTAB  ((uint8_t)0)
 #define AEVENT_ALLOC   ((uint8_t)1)
 #define AEVENT_FREE    ((uint8_t)2)
 #define AEVENT_REALLOC ((uint8_t)(AEVENT_ALLOC | AEVENT_FREE))
diff --git a/tools/memprof.lua b/tools/memprof.lua
index 18b44fdd..805b7e74 100644
--- a/tools/memprof.lua
+++ b/tools/memprof.lua
@@ -101,6 +101,11 @@ local function dump(inputfile)
   local reader = bufread.new(inputfile)
   local symbols = symtab.parse(reader)
   local events = memprof.parse(reader, symbols)
+
+  for addr, event in pairs(events.symtab) do
+    symtab.add_cfunc(symbols, addr, event.name)
+  end
+
   if not leak_only then
     view.profile_info(events, symbols)
   end
diff --git a/tools/memprof/parse.lua b/tools/memprof/parse.lua
index 47dbaee4..36343e4a 100644
--- a/tools/memprof/parse.lua
+++ b/tools/memprof/parse.lua
@@ -17,6 +17,7 @@ local LJM_CURRENT_VERSION = 0x02
 
 local LJM_EPILOGUE_HEADER = 0x80
 
+local AEVENT_SYMTAB = 0
 local AEVENT_ALLOC = 1
 local AEVENT_FREE = 2
 local AEVENT_REALLOC = 3
@@ -41,6 +42,7 @@ local function new_event(loc)
     free = 0,
     alloc = 0,
     primary = {},
+    name = nil
   }
 end
 
@@ -85,6 +87,21 @@ local function parse_location(reader, asource)
   return symtab.id(loc), loc
 end
 
+local function parse_symtab(reader, asource, events, heap)
+  -- That instruction supresses unused variable warning
+  -- from luacheck.
+  local _ = asource or heap
+
+  local id = reader:read_uleb128()
+  local name = reader:read_string()
+
+  if not events[id] then
+    events[id] = new_event(0)
+  end
+
+  events[id].name = name
+end
+
 local function parse_alloc(reader, asource, events, heap)
   local id, loc = parse_location(reader, asource)
 
@@ -142,6 +159,7 @@ local function parse_free(reader, asource, events, heap)
 end
 
 local parsers = {
+  [AEVENT_SYMTAB] = {evname = "symtab", parse = parse_symtab},
   [AEVENT_ALLOC] = {evname = "alloc", parse = parse_alloc},
   [AEVENT_FREE] = {evname = "free", parse = parse_free},
   [AEVENT_REALLOC] = {evname = "realloc", parse = parse_realloc},
@@ -182,6 +200,7 @@ function M.parse(reader)
     realloc = {},
     free = {},
     heap = {},
+    symtab = {}
   }
 
   local magic = reader:read_octets(3)
diff --git a/tools/utils/symtab.lua b/tools/utils/symtab.lua
index aa66269c..75b0285b 100644
--- a/tools/utils/symtab.lua
+++ b/tools/utils/symtab.lua
@@ -158,4 +158,8 @@ function M.demangle(symtab, loc)
   return string_format("CFUNC %#x", addr)
 end
 
+function M.add_cfunc(symtab, addr, name)
+  symtab.cfunc = avl.insert(symtab.cfunc, addr, {name = name})
+end
+
 return M
-- 
2.35.1

Re: [Tarantool-patches] [PATCH luajit v5 0/2] memprof: add resolving capabilities

[Maxim Kokryashkin via Tarantool-patches]

[-- Attachment #1: Type: text/plain, Size: 1133 bytes --]


Sorry, I forgot to add the link to the branch:
https://github.com/tarantool/luajit/tree/fckxorg/gh-5813-resolving-of-c-symbols-full-ci
--
Best regards,
Maxim Kokryashkin
 
  
>Пятница, 4 марта 2022, 22:22 +03:00 от Maxim Kokryashkin <max.kokryashkin@gmail.com>:
> 
>Changes in v5:
>- Fixed comments as per review by Sergey
>- Added resolution based on ELF sections
>- Disabled resolution for OSX
>- Rebased on `tarantool` branch
>
>Also, there are a few comments in the following letters.
>
>Maxim Kokryashkin (2):
>  memprof: extend symtab with C-symbols
>  memprof: enrich symtab with newly loaded symbols
>
> Makefile.original | 2 +-
> src/lj_memprof.c | 396 +++++++++++++++++-
> src/lj_memprof.h | 15 +-
> test/tarantool-tests/tools-utils-avl.test.lua | 59 +++
> tools/CMakeLists.txt | 2 +
> tools/memprof.lua | 5 +
> tools/memprof/parse.lua | 19 +
> tools/utils/avl.lua | 118 ++++++
> tools/utils/symtab.lua | 28 +-
> 9 files changed, 631 insertions(+), 13 deletions(-)
> create mode 100644 test/tarantool-tests/tools-utils-avl.test.lua
> create mode 100644 tools/utils/avl.lua
>
>--
>2.35.1
 

[-- Attachment #2: Type: text/html, Size: 1795 bytes --]