From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from [87.239.111.99] (localhost [127.0.0.1]) by dev.tarantool.org (Postfix) with ESMTP id AAA8371239; Sat, 30 Oct 2021 16:26:31 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org AAA8371239 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=tarantool.org; s=dev; t=1635600391; bh=P7lKYVHOzIrfVEclZOQv48kHDaeVcqz7qa51CUj4BQg=; h=To:Date:In-Reply-To:References:Subject:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=eVoyOq3KnABwYZ7aaypKkE7t3NnVVtiSF+rNZJ/I+jNWWfKc7KL2czhgZ2Jcgy2G4 GvvOkD5X21W2xmwHpnkuo9nNlR3Wi+PHu3gTu8mhxe6AuFjUtfr5eNbbqV68JME3Wx ekAloK8OY5dgkrrzE1bbROoTktsuBBDZWp84Fh3M= Received: from mail-lj1-f176.google.com (mail-lj1-f176.google.com [209.85.208.176]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id 140AB71239 for ; Sat, 30 Oct 2021 16:25:34 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 140AB71239 Received: by mail-lj1-f176.google.com with SMTP id 188so21464617ljj.4 for ; Sat, 30 Oct 2021 06:25:34 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=7E+551yW8vKcMpjC7zJzPqg/O/8Jwm2MrbcURn68a9Y=; b=XlSfmrKjm1utzOybWxZ8eiACQYWiv7fOrxaK05fqfIOZR9QwQnRYU8QI+UsEJ7CYdc cD1mSnK0V8u8XPdZHn+xpumXwaqSONDRCjANVQYxgE/KhOK8uUfs9TxU1jIEQWUagJGP cLlRQgTi4k7KrEE/9G3Ri8IqqXrJf6PciZhNgWmSnD7Q8QtXOmtekGOfH72ARx6EmuiL p6Il9/drkNbqDNkko09fAZ/7FBZVDxctykVr5BqjrWIP/yO0szPxYMbvoX6hDNcXW1lf KiGyfNrVTxzgn80wnAxY1QU2iOJsCxbO87f8m/sc/cMdetJ7ZwBTV/lqaqwGAKXNstKq dDUg== X-Gm-Message-State: AOAM532zdy0AFAt2p2jk6zpauZDx6V7caMKFoS6ovNj7L7MGkXRQ3y0u KPIJRoi0jeCoUB0UcU8MHpzycaTj3QdQiA== X-Google-Smtp-Source: ABdhPJyQeomHQ045oqh6sgsDC9PW0u47tPW3rNiXDfAb5Sl9SqU9Izjt+sBzyU6tJmCMPk5MWp8K0w== X-Received: by 2002:a2e:1405:: with SMTP id u5mr3486059ljd.11.1635600333311; Sat, 30 Oct 2021 06:25:33 -0700 (PDT) Received: from localhost.localdomain ([93.175.11.59]) by smtp.gmail.com with ESMTPSA id y3sm637338ljg.47.2021.10.30.06.25.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 30 Oct 2021 06:25:32 -0700 (PDT) X-Google-Original-From: Maxim Kokryashkin To: tarantool-patches@dev.tarantool.org, imun@tarantool.org, skaplun@tarantool.org Date: Sat, 30 Oct 2021 16:25:25 +0300 Message-Id: X-Mailer: git-send-email 2.33.0 In-Reply-To: References: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Subject: [Tarantool-patches] [PATCH luajit v4 2/2] memprof: update memprof parser X-BeenThere: tarantool-patches@dev.tarantool.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , From: Maxim Kokryashkin via Tarantool-patches Reply-To: Maxim Kokryashkin Errors-To: tarantool-patches-bounces@dev.tarantool.org Sender: "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