[Tarantool-patches] [PATCH luajit v4 0/2] memprof: add demangling capabilities for C functions

[Tarantool-patches] [PATCH luajit v4 0/2] memprof: add demangling capabilities for C functions

[Maxim Kokryashkin via Tarantool-patches]

Changes in v4:
- AVL tree in symtab.demangle
- Self-review

Maxim Kokryashkin (2):
  memprof: extend symtab with C-symbols
  memprof: update memprof parser

 Makefile.original                             |   2 +-
 src/lj_memprof.c                              | 159 +++++++++++++++++-
 src/lj_memprof.h                              |  17 +-
 .../misclib-memprof-lapi.test.lua             |   4 +-
 test/tarantool-tests/tools-utils-avl.test.lua |  59 +++++++
 tools/CMakeLists.txt                          |   2 +
 tools/memprof.lua                             |   5 +
 tools/memprof/parse.lua                       |  17 +-
 tools/utils/avl.lua                           | 118 +++++++++++++
 tools/utils/symtab.lua                        |  39 ++++-
 10 files changed, 401 insertions(+), 21 deletions(-)
 create mode 100644 test/tarantool-tests/tools-utils-avl.test.lua
 create mode 100644 tools/utils/avl.lua

---
GitHub branch:
https://github.com/tarantool/luajit/tree/fckxorg/gh-5813-demangling-of-c-symbols-v2

Issue:
https://github.com/tarantool/tarantool/issues/5813

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

[Maxim Kokryashkin via Tarantool-patches]

This commit enriches memprof's symbol table and event stream with
information about C-symbols. That information will provide demangling
capabilities to the parser.

The following data is stored in symtab for each symbol:
| SYMTAB_CFUNC | symbol address | symbol name |
  1 byte            8 bytes
  magic
  number

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

Part of tarantool/tarantool#5813
---
 src/lj_memprof.c | 159 ++++++++++++++++++++++++++++++++++++++++++++---
 src/lj_memprof.h |  17 +++--
 2 files changed, 165 insertions(+), 11 deletions(-)

diff --git a/src/lj_memprof.c b/src/lj_memprof.c
index 2c1ef3b8..30c9697c 100644
--- a/src/lj_memprof.c
+++ b/src/lj_memprof.c
@@ -5,10 +5,16 @@
 ** Copyright (C) 2015-2019 IPONWEB Ltd.
 */
 
+#define _GNU_SOURCE
+#include <elf.h>
+
 #define lj_memprof_c
 #define LUA_CORE
 
 #include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <link.h>
 
 #include "lj_arch.h"
 #include "lj_memprof.h"
@@ -24,7 +30,123 @@
 static const unsigned char ljs_header[] = {'l', 'j', 's', LJS_CURRENT_VERSION,
 					   0x0, 0x0, 0x0};
 
-static void dump_symtab(struct lj_wbuf *out, const struct global_State *g)
+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 iterate over it.
+     */
+    uint32_t last_entry = 0;
+    uint32_t *cur_bucket = NULL;
+    uint32_t *entry = NULL;
+
+    const void *chain_address = NULL;
+    struct ghashtab_header *header = (struct ghashtab_header*)ghashtab;
+    const void *buckets = (void*)ghashtab + sizeof(struct ghashtab_header) +
+                          sizeof(uint64_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_address = buckets + sizeof(uint32_t) * header->nbuckets;
+    do {
+        entry = (uint32_t*)(chain_address + (last_entry - header->symoffset) *
+                sizeof(uint32_t));
+        last_entry++;
+    } while (!(*entry & 1));
+
+    return last_entry;
+}
+
+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;
+};
+
+int resolve_symbolnames(struct dl_phdr_info *info, size_t info_size, void *data)
+{
+  if (strcmp(info->dlpi_name, "linux-vdso.so.1") == 0) {
+    return 0;
+  }
+
+  ElfW(Dyn*) dyn = NULL;
+  ElfW(Sym*) sym = NULL;
+  ElfW(Word*) hashtab = NULL;
+  ElfW(Word) sym_cnt = 0;
+
+  char *strtab = 0;
+  char *sym_name = 0;
+
+  struct symbol_resolver_conf *conf = data;
+  const uint8_t header = conf->header;
+  struct lj_wbuf *buf = conf->buf;
+
+  conf->lib_cnt_prev = *conf->lib_cnt;
+  uint32_t lib_cnt_prev = conf->lib_cnt_prev;
+
+  if ((conf->to_dump_cnt = info->dlpi_adds - lib_cnt_prev) == 0)
+    /* No new libraries, stop resolver. */
+    return 1;
+
+  uint32_t lib_cnt = info->dlpi_adds - info->dlpi_subs;
+  if (conf->cur_lib < lib_cnt - conf->to_dump_cnt) {
+    /* That lib is already dumped, skip it. */
+    ++conf->cur_lib;
+    return 0;
+  }
+
+  for (size_t header_index = 0; header_index < info->dlpi_phnum; ++header_index) {
+    if (info->dlpi_phdr[header_index].p_type == PT_DYNAMIC) {
+      dyn = (ElfW(Dyn)*)(info->dlpi_addr +  info->dlpi_phdr[header_index].p_vaddr);
+
+      while(dyn->d_tag != DT_NULL) {
+        if (dyn->d_tag == DT_HASH) {
+          hashtab = (ElfW(Word*))dyn->d_un.d_ptr;
+          sym_cnt = hashtab[1];
+        }
+        else if (dyn->d_tag == DT_GNU_HASH && sym_cnt == 0)
+          sym_cnt = ghashtab_size(dyn->d_un.d_ptr);
+        else if (dyn->d_tag == DT_STRTAB)
+          strtab = (char*)dyn->d_un.d_ptr;
+        else if (dyn->d_tag == DT_SYMTAB) {
+          sym = (ElfW(Sym*))dyn->d_un.d_ptr;
+
+          for (ElfW(Word) sym_index = 0; sym_index < sym_cnt; sym_index++) {
+              sym_name = &strtab[sym[sym_index].st_name];
+              lj_wbuf_addbyte(buf, header);
+              lj_wbuf_addu64(buf, sym[sym_index].st_value + info->dlpi_addr);
+              lj_wbuf_addstring(buf, sym_name);
+          }
+        }
+        dyn++;
+      }
+    }
+  }
+
+  ++conf->cur_lib;
+  return 0;
+}
+
+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;
@@ -49,6 +171,17 @@ static void dump_symtab(struct lj_wbuf *out, const struct global_State *g)
     iter = &o->gch.nextgc;
   }
 
+  /* Write symbols. */
+  struct symbol_resolver_conf conf = {
+    out,
+    SYMTAB_CFUNC,
+    0,
+    *lib_cnt,
+    0,
+    lib_cnt
+  };
+  dl_iterate_phdr(resolve_symbolnames, &conf);
+
   lj_wbuf_addbyte(out, SYMTAB_FINAL);
 }
 
@@ -78,6 +211,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};
@@ -105,15 +239,26 @@ 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)
 {
+  /* 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);
+
   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);
@@ -126,7 +271,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)
@@ -139,9 +284,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);
 }
@@ -249,7 +394,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 3417475d..337fa76a 100644
--- a/src/lj_memprof.h
+++ b/src/lj_memprof.h
@@ -16,7 +16,7 @@
 #include "lj_def.h"
 #include "lj_wbuf.h"
 
-#define LJS_CURRENT_VERSION 0x1
+#define LJS_CURRENT_VERSION 0x2
 
 /*
 ** symtab format:
@@ -25,12 +25,14 @@
 ** prologue       := 'l' 'j' 's' version reserved
 ** version        := <BYTE>
 ** reserved       := <BYTE> <BYTE> <BYTE>
-** sym            := sym-lua | sym-final
+** sym            := sym-lua | sym-cfunc | sym-final
 ** sym-lua        := sym-header sym-addr sym-chunk 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
 ** string         := string-len string-payload
 ** string-len     := <ULEB128>
@@ -51,9 +53,10 @@
 */
 
 #define SYMTAB_LFUNC ((uint8_t)0)
+#define SYMTAB_CFUNC ((uint8_t)1)
 #define SYMTAB_FINAL ((uint8_t)0x80)
 
-#define LJM_CURRENT_FORMAT_VERSION 0x01
+#define LJM_CURRENT_FORMAT_VERSION 0x02
 
 /*
 ** Event stream format:
@@ -64,10 +67,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-lua        := sym-addr line-no
@@ -78,7 +82,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
@@ -97,6 +105,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))
-- 
2.33.0

[Tarantool-patches] [PATCH luajit v4 2/2] memprof: update memprof parser

[Maxim Kokryashkin via Tarantool-patches]

This commit introduces demangling of C symbols to memprof parser.

As symbol table format has changed, parser needed to be updated too.
Now the parser supports new symbol table entries, containing data
about symbols from shared objects, that were loaded at the moment of
data collection. Also, now the parser supports symtab events in the
event stream and extends the symtab corresponding to them.

Closes tarantool/tarantool#5813
---
 Makefile.original                             |   2 +-
 .../misclib-memprof-lapi.test.lua             |   4 +-
 test/tarantool-tests/tools-utils-avl.test.lua |  59 +++++++++
 tools/CMakeLists.txt                          |   2 +
 tools/memprof.lua                             |   5 +
 tools/memprof/parse.lua                       |  17 ++-
 tools/utils/avl.lua                           | 118 ++++++++++++++++++
 tools/utils/symtab.lua                        |  39 +++++-
 8 files changed, 236 insertions(+), 10 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/test/tarantool-tests/misclib-memprof-lapi.test.lua b/test/tarantool-tests/misclib-memprof-lapi.test.lua
index 06d96b3b..bdb77549 100644
--- a/test/tarantool-tests/misclib-memprof-lapi.test.lua
+++ b/test/tarantool-tests/misclib-memprof-lapi.test.lua
@@ -61,10 +61,10 @@ local function fill_ev_type(events, symbols, event_type)
         name = "INTERNAL",
         num = event.num,
     }
-    elseif symbols[addr] then
+    elseif symbols.SYMTAB_LFUNC[addr] then
       ev_type[event.loc.line] = {
         name = string.format(
-          "%s:%d", symbols[addr].source, symbols[addr].linedefined
+          "%s:%d", symbols.SYMTAB_LFUNC[addr].source, symbols.SYMTAB_LFUNC[addr].linedefined
         ),
         num = event.num,
       }
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..22f7a373
--- /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/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 12e2758f..61a95d0f 100644
--- a/tools/memprof/parse.lua
+++ b/tools/memprof/parse.lua
@@ -11,10 +11,11 @@ local lshift = bit.lshift
 local string_format = string.format
 
 local LJM_MAGIC = "ljm"
-local LJM_CURRENT_VERSION = 1
+local LJM_CURRENT_VERSION = 2
 
 local LJM_EPILOGUE_HEADER = 0x80
 
+local AEVENT_SYMTAB = 0
 local AEVENT_ALLOC = 1
 local AEVENT_FREE = 2
 local AEVENT_REALLOC = 3
@@ -36,6 +37,7 @@ local function new_event(loc)
     free = 0,
     alloc = 0,
     primary = {},
+    name = nil
   }
 end
 
@@ -77,6 +79,17 @@ local function parse_location(reader, asource)
   error("Unknown asource "..asource)
 end
 
+local function parse_symtab(reader, asource, events, 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)
 
@@ -134,6 +147,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},
@@ -174,6 +188,7 @@ function M.parse(reader)
     realloc = {},
     free = {},
     heap = {},
+    symtab = {}
   }
 
   local magic = reader:read_octets(3)
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 3ed1dd13..b889980e 100644
--- a/tools/utils/symtab.lua
+++ b/tools/utils/symtab.lua
@@ -6,15 +6,18 @@
 
 local bit = require "bit"
 
+local avl = require "utils.avl"
+
 local band = bit.band
 local string_format = string.format
 
 local LJS_MAGIC = "ljs"
-local LJS_CURRENT_VERSION = 1
+local LJS_CURRENT_VERSION = 2
 local LJS_EPILOGUE_HEADER = 0x80
 local LJS_SYMTYPE_MASK = 0x03
 
 local SYMTAB_LFUNC = 0
+local SYMTAB_CFUNC = 1
 
 local M = {}
 
@@ -24,18 +27,33 @@ local function parse_sym_lfunc(reader, symtab)
   local sym_chunk = reader:read_string()
   local sym_line = reader:read_uleb128()
 
-  symtab[sym_addr] = {
+  symtab.SYMTAB_LFUNC[sym_addr] = {
     source = sym_chunk,
     linedefined = sym_line,
   }
 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.SYMTAB_CFUNC = avl.insert(symtab.SYMTAB_CFUNC, addr, {
+    name = name
+  })
+end
+
 local parsers = {
   [SYMTAB_LFUNC] = parse_sym_lfunc,
+  [SYMTAB_CFUNC] = parse_sym_cfunc
 }
 
 function M.parse(reader)
-  local symtab = {}
+  local symtab = {
+    SYMTAB_LFUNC = {},
+    SYMTAB_CFUNC = nil
+  }
+
   local magic = reader:read_octets(3)
   local version = reader:read_octets(1)
 
@@ -69,7 +87,6 @@ function M.parse(reader)
       parsers[sym_type](reader, symtab)
     end
   end
-
   return symtab
 end
 
@@ -80,11 +97,21 @@ function M.demangle(symtab, loc)
     return "INTERNAL"
   end
 
-  if symtab[addr] then
-    return string_format("%s:%d", symtab[addr].source, loc.line)
+  if symtab.SYMTAB_LFUNC[addr] then
+    return string_format("%s:%d", symtab.SYMTAB_LFUNC[addr].source, loc.line)
+  end
+
+  local key, value = avl.upper_bound(symtab.SYMTAB_CFUNC, addr)
+
+  if key then
+    return string_format("%s:%#x", value.name, key)
   end
 
   return string_format("CFUNC %#x", addr)
 end
 
+function M.add_cfunc(symtab, addr, name)
+  symtab.SYMTAB_CFUNC = avl.insert(symtab.SYMTAB_CFUNC, addr, {name = name})
+end
+
 return M
-- 
2.33.0

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

[Sergey Kaplun via Tarantool-patches]

Hi, Maxim!

Thanks for the patch! Please consider my comments below.

On 30.10.21, Maxim Kokryashkin wrote:
> This commit enriches memprof's symbol table and event stream with
> information about C-symbols. That information will provide demangling
> capabilities to the parser.

I suggest to reorganize patches:
1) One patch for C symbols dumping in symtab and their demangling in
   parser with corresponding tests.
2) The other patch for symtab extension on dlopen with corresponding
   tests.

So, the first patch increases only LJS_VERSION (for dumper and parser).
The second one increases only LJM_VERSION, since symtab format is the
same, but the stream format from memprof is changed.

I've reviewed only the first part of this patch about C symbols dumping.

> 
> The following data is stored in symtab for each symbol:
> | SYMTAB_CFUNC | symbol address | symbol name |
>   1 byte            8 bytes
>   magic
>   number
> 
> 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.

> 
> Part of tarantool/tarantool#5813
> ---
>  src/lj_memprof.c | 159 ++++++++++++++++++++++++++++++++++++++++++++---
>  src/lj_memprof.h |  17 +++--
>  2 files changed, 165 insertions(+), 11 deletions(-)
> 
> diff --git a/src/lj_memprof.c b/src/lj_memprof.c
> index 2c1ef3b8..30c9697c 100644
> --- a/src/lj_memprof.c
> +++ b/src/lj_memprof.c
> @@ -5,10 +5,16 @@
>  ** Copyright (C) 2015-2019 IPONWEB Ltd.
>  */
>  
> +#define _GNU_SOURCE
> +#include <elf.h>
> +

Nit: I suggest to move it down after LUA_CORE.

>  #define lj_memprof_c
>  #define LUA_CORE
>  
>  #include <errno.h>
> +#include <stdio.h>
> +#include <stdlib.h>
> +#include <link.h>
>  
>  #include "lj_arch.h"
>  #include "lj_memprof.h"
> @@ -24,7 +30,123 @@
>  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?

>  
> -static void dump_symtab(struct lj_wbuf *out, const struct global_State *g)
> +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 iterate over it.
> +     */

Nit: please use LuaJIT style for comments.

> +    uint32_t last_entry = 0;
> +    uint32_t *cur_bucket = NULL;
> +    uint32_t *entry = NULL;
> +
> +    const void *chain_address = NULL;
> +    struct ghashtab_header *header = (struct ghashtab_header*)ghashtab;
> +    const void *buckets = (void*)ghashtab + sizeof(struct ghashtab_header) +

What is the size of data pointed by (void *)? What is the result of this
pointer arithmetic? Also, the compiler warns about this too:

| /home/burii/reviews/luajit/csymbols/src/lj_memprof.c: In function 'ghashtab_size':
| /home/burii/reviews/luajit/csymbols/src/lj_memprof.c:52:43: warning: pointer of type 'void *' used in arithmetic [-Wpointer-arith]
|    52 |     const void *buckets = (void*)ghashtab + sizeof(struct ghashtab_header) +
|       |                                           ^
| /home/burii/reviews/luajit/csymbols/src/lj_memprof.c:52:76: warning: pointer of type 'void *' used in arithmetic [-Wpointer-arith]
|    52 |     const void *buckets = (void*)ghashtab + sizeof(struct ghashtab_header) +
|       |                                                                            ^
| /home/burii/reviews/luajit/csymbols/src/lj_memprof.c:65:29: warning: pointer of type 'void *' used in arithmetic [-Wpointer-arith]
|    65 |     chain_address = buckets + sizeof(uint32_t) * header->nbuckets;
|       |                             ^
| /home/burii/reviews/luajit/csymbols/src/lj_memprof.c:67:43: warning: pointer of type 'void *' used in arithmetic [-Wpointer-arith]
|    67 |         entry = (uint32_t*)(chain_address + (last_entry - header->symoffset) *

> +                          sizeof(uint64_t) * header->bloom_size;

I believe that it is not uint64_t for 32bit build.

> +
> +    cur_bucket = (uint32_t*)buckets;

Also, please drop a comment about .gnu.hash. structure:

Am I understanding correctly that:
We take the highest possible *non empty* bucket (the first cycle) and
iterate through its symbols until the last chain is over (the LSB is set
to 1).

> +    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_address = buckets + sizeof(uint32_t) * header->nbuckets;
> +    do {

Can we just write that part like the follwing:
| while ((chain[last_entry - header->symoffset] & 1) == 0)
|   last_entry++;
Where `uint32_t *chain = (uint32_t *)chain_address;`?

> +        last_entry++;

It is good to leave a comment, that chain ends with the lowest bit set
to 1.

> +    } while (!(*entry & 1));
> +
> +    return last_entry;
> +}
> +
> +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;
> +};
> +
> +int resolve_symbolnames(struct dl_phdr_info *info, size_t info_size, void *data)
> +{
> +  if (strcmp(info->dlpi_name, "linux-vdso.so.1") == 0) {
> +    return 0;
> +  }

For some arches it has different names (see `man 7 vdso`).
I suggest to define its name with a macro.

Side note: Also, why .hash and .gnu.hash seems different in format for this
library? Why does parsing crash if comments those lines?

Nit: {} are excess.

> +
> +  ElfW(Dyn*) dyn = NULL;
> +  ElfW(Sym*) sym = NULL;
> +  ElfW(Word*) hashtab = NULL;
> +  ElfW(Word) sym_cnt = 0;
> +
> +  char *strtab = 0;
> +  char *sym_name = 0;
> +
> +  struct symbol_resolver_conf *conf = data;
> +  const uint8_t header = conf->header;
> +  struct lj_wbuf *buf = conf->buf;

Nit: please move all declarations to the corresponding scopes.
Also, please add `const` type qualifier, where it is possible.

> +
> +  conf->lib_cnt_prev = *conf->lib_cnt;
> +  uint32_t lib_cnt_prev = conf->lib_cnt_prev;

Please, fix the following warnings too:

| /home/burii/reviews/luajit/csymbols/src/lj_memprof.c: In function 'resolve_symbolnames':
| /home/burii/reviews/luajit/csymbols/src/lj_memprof.c:106:3: warning: ISO C90 forbids mixed declarations and code [-Wdeclaration-after-statement]
|   106 |   uint32_t lib_cnt_prev = conf->lib_cnt_prev;
|       |   ^~~~~~~~
| /home/burii/reviews/luajit/csymbols/src/lj_memprof.c:112:3: warning: ISO C90 forbids mixed declarations and code [-Wdeclaration-after-statement]
|   112 |   uint32_t lib_cnt = info->dlpi_adds - info->dlpi_subs;

> +
> +  if ((conf->to_dump_cnt = info->dlpi_adds - lib_cnt_prev) == 0)

Nit: AFAICS, dlpi_adds field was added in glibc 2.4. Manual recommends
to check the size of the structure if we use those fields. At least we
can add assert on size for glibc version.

Also, you should fix the following warning:

| /home/burii/reviews/luajit/csymbols/src/lj_memprof.c:87:59: warning: unused parameter 'info_size' [-Wunused-parameter]
|    87 | int resolve_symbolnames(struct dl_phdr_info *info, size_t info_size, void *data)
|       |

> +    /* No new libraries, stop resolver. */
> +    return 1;
> +
> +  uint32_t lib_cnt = info->dlpi_adds - info->dlpi_subs;
> +  if (conf->cur_lib < lib_cnt - conf->to_dump_cnt) {
> +    /* That lib is already dumped, skip it. */
> +    ++conf->cur_lib;
> +    return 0;
> +  }
> +
> +  for (size_t header_index = 0; header_index < info->dlpi_phnum; ++header_index) {
> +    if (info->dlpi_phdr[header_index].p_type == PT_DYNAMIC) {
> +      dyn = (ElfW(Dyn)*)(info->dlpi_addr +  info->dlpi_phdr[header_index].p_vaddr);
> +
> +      while(dyn->d_tag != DT_NULL) {
> +        if (dyn->d_tag == DT_HASH) {

Only the ELF header has a fixed position in the file. The flexibility of
the ELF format requires no specified order for header tables, sections
or segments [1]. So, we can't rely on their order and first we need to
list all program headers and safe their addresses we need and only after
start working with them (like it is done in readelf, for example).

Also, switch-case operator looks preferable here.

> +          hashtab = (ElfW(Word*))dyn->d_un.d_ptr;
> +          sym_cnt = hashtab[1];

OK, this part is not obvious. So please drop a comment about that. Something
like that:

| 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 [2].

Side note: man ld says about the type of hash (.hash or .gnu.hash):
| for most Linux based systems it will be "both"
But gcc by default used (behind the scenes) `-Wl,--hash=gnu`, AFAICS.

> +        }

Please use {} everywhere in else if statements if you use it in any of
them [3].

> +        else if (dyn->d_tag == DT_GNU_HASH && sym_cnt == 0)
> +          sym_cnt = ghashtab_size(dyn->d_un.d_ptr);

OK, there are several more simple (for me) options:

-1) Not calculate .gnu.hash tab size by iterating the whole symtab. We
    can take the highest possible bucket (nbuckets - 1) and iterate
    through its symbols until the last chain is over. It is better
    because we don't need to iterate through all buckets.
0) We can dump all necessary information while we iterating through the
   dyn symtab. So we have no need to walk through it twice.
1) If we have access to section headers, we can simply calculate the
   total number of symbols from section's header: just divide the section
   size by an entry size.

> +        else if (dyn->d_tag == DT_STRTAB)
> +          strtab = (char*)dyn->d_un.d_ptr;
> +        else if (dyn->d_tag == DT_SYMTAB) {
> +          sym = (ElfW(Sym*))dyn->d_un.d_ptr;
> +
> +          for (ElfW(Word) sym_index = 0; sym_index < sym_cnt; sym_index++) {

Index 0 both designates the first entry in the table and serves as the
undefined symbol index [4]. So we can just start from the 1st index for the
symtab in the dynamic section.

> +              sym_name = &strtab[sym[sym_index].st_name];

Should we dump *all* symbols? Why we can't just dump symbols with type, that
equals STT_FUNC?

> +              lj_wbuf_addbyte(buf, header);
> +              lj_wbuf_addu64(buf, sym[sym_index].st_value + info->dlpi_addr);
> +              lj_wbuf_addstring(buf, sym_name);
> +          }
> +        }
> +        dyn++;
> +      }

It is good to use .dynsym symbol table to get CFUNC locations, but
it doesn't provide LOCAL symbols. It is better to parse .symtab to get
them. Why it is useful:

Assume, we have the following code:

| static __attribute__((noinline)) lib_func1(lua_State *L)
| {
| 	/* Allocations here. */
| }
|
| static  __attribute__((noinline)) lib_func2(lua_State *L)
| {
| 	/* Allocations here. */
| }
|
| static lib_func3(lua_State *L)
| {
| 	/* Allocations here. */
| 	if (...)
| 		lib_func1(L);
| 	else
| 		lib_func2(L);
| 	/* More allocations. */
| }

IINM, without .symtab information we can't determine the source of
allocation for now? As I believe the most common usage of LuaC library
is the following [5]:

|  static int l_dir (lua_State *L) {
|     ...  /* as before */
|  }
|
|
|  static const struct luaL_reg mylib [] = {
|    {"dir", l_dir},
|    {NULL, NULL}  /* sentinel */
|  };
|
|
|  int luaopen_mylib (lua_State *L) {
|    luaL_openlib(L, "mylib", mylib, 0);
|    return 1;
|  }

For that case user can't see the source of allocation, AFAICS.
So, we must dump symtab (if it is not stripped), else try to dump
only dynsym hoping for the best. Or even don't try to demangle these
libraries at all.

Also, in this case we should to work with parsing carefully -- we can't
just find the nearest symbol. First, we should check, that .symtab for
the library is not stripped and dumped to memprof's symtab. If it isn't
we can only report that allocation was in the libname.so with
corresponding address (if we want to dump so name).

> +    }
> +  }
> +
> +  ++conf->cur_lib;
> +  return 0;
> +}
> +
> +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;
> @@ -49,6 +171,17 @@ static void dump_symtab(struct lj_wbuf *out, const struct global_State *g)

<snipped>

> @@ -78,6 +211,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. */

I've not dived deeply, but I'm not sure in the usage of this:
What happens if 2 libraries was unloaded, one load again and one new
load instead the old one?

>  };
>  
>  static struct memprof memprof = {0};
> @@ -105,15 +239,26 @@ static void memprof_write_lfunc(struct lj_wbuf *out, uint8_t aevent,
>  }
>  

<snipped>

> diff --git a/src/lj_memprof.h b/src/lj_memprof.h
> index 3417475d..337fa76a 100644
> --- a/src/lj_memprof.h
> +++ b/src/lj_memprof.h

<snipped>

> -- 
> 2.33.0
> 

[1]: https://docs.oracle.com/cd/E19683-01/816-1386/6m7qcoblj/index.html
[2]: https://docs.oracle.com/cd/E23824_01/html/819-0690/chapter6-48031.html
[3]: https://www.kernel.org/doc/html/v4.10/process/coding-style.html#placing-braces-and-spaces
[4]: https://docs.oracle.com/cd/E23824_01/html/819-0690/chapter6-79797.html
[5]: https://www.lua.org/pil/26.2.html

-- 
Best regards,
Sergey Kaplun