CN103761089B - The method that kinematic function call relation is determined based on register transfer language - Google Patents

Abstract

The invention discloses a method for determining a dynamic function call relationship based on a register transfer language, which is mainly designed for the problem that the static function call relationship cannot analyze the function pointer call and the loadable module function call relationship. The present invention detects a function call execution event during system operation. If a call instruction is detected, it analyzes the function name corresponding to the function entry address called by the instruction, counts the number of instructions, and outputs the function name, call occurrence time, process number, and The thread number, the pointer to the top of the stack and the module number to which it belongs, and save it to the tracking data file; if the detected instruction is to return the command, output the time, the process number, the thread number to it, and the pointer to the top of the stack to the tracking data file; The trace data file is processed to obtain a predetermined standard data format, and the trace data file is transmitted to the static function call relationship generation device to generate a dynamic function call graph describing the function call relationship.

Description

Method of determining dynamic function call relationship based on register transfer language

technical field

The invention relates to the technical field of function call relations, in particular to a method for determining dynamic function call relations based on a register transfer language.

Background technique

The reading and analysis of the source code can be realized through the function call graph. The function call graph can be macroscopic (the calling relationship between source code modules) or microscopic (specifically the call-in and call-out relationship of a certain function). The function call graph can show a static function call trend of the source code, and can also be used to show the function call status when the system or program is running. In order to analyze accurately, conveniently and efficiently, researchers have developed many function call graph generation tools.

Static function call graph generation tools refer to tools that are based on known source code and developed according to different analysis needs. Some of these tools only work on source code, such as Source Insight, Understand, etc., and some work objects are generated by the compilation process. Intermediate results such as Codeviz, Egypt, LLVM, and Open64.

The dynamic function call graph generation tool is a tool based on obtaining the function call relationship that occurs during the running of the system or software and drawing it into a call graph. In order to obtain the function call situation at runtime, some tools such as Systemtap, gprof, KCachegrind, ftrace, pprof tool, etc., some of them are for the kernel and some are for software, and their purposes are also different, but they are all based on function call relationship analysis.

Gprof allows each function to call the mcount function during compilation, and at the same time saves the function call graph in memory. This will reduce the performance of the system. If all function calls in the system are tracked, it will cause insufficient memory usage. The principle of Ftrace is similar to the principle of gprof, except that it does not save the function call graph in memory, and the use of mcount is also dynamic, and nop can be replaced by mcount instructions when needed according to user requirements. SystemTap is a dynamic method of monitoring and tracking the operation of the running Linux kernel. Instead of using tools to build a special kernel, SystemTap allows you to dynamically install the tool at runtime. It uses an application programming interface called Kprobes ( API) to achieve this. The pprof tool is mainly used to analyze the bottleneck of cpu operation and record relevant information after interrupting the application software. Gprof, ftrace, and KCachegrind are all based on static instrumentation technology. The essence of ftrace is also static instrumentation technology, but the implementation is different. The tracking tool that will be used in this article is based on the virtual machine, and will not insert code into the source code, so it will not affect the performance of the system execution itself.

KCachegrind cannot trace system calls, while gprof, ftrace, etc. can trace system calls but cannot trace the system startup process. These problems will be solved in the tools of this article. SimSight is based on Simics' dynamic tracking tool, which is the closest to the design concept of this paper, but SimSight cannot provide a function call graph combining static and dynamic.

Contents of the invention

In view of the above problems, the present invention provides a method for determining the dynamic function calling relationship based on register transfer language, which can clearly describe the calling relationship of pointer functions and loadable modules.

In order to achieve the above object, the present invention determines a method for dynamic function call relationship based on register transfer language, said method comprising:

Detect function call execution events during system operation,

If a call instruction is detected, analyze the function name corresponding to the function entry address called by the instruction, count the number of instructions, output the function name, call occurrence time, process number, thread number, stack top pointer and module number, and save to the trace data file;

If the detected command is after the return command, output the time, process number, thread number and stack top pointer to the tracking data file;

The trace data file is processed to obtain a predetermined standard data format, and the processed trace data file is transmitted to the static function call relationship generation device to generate a dynamic function call graph describing the function call relationship.

Further, the method for generating the tracking data file includes:

Obtain the function name corresponding to the function entry address, the list of the file where the function is located and the line number by parsing the target file;

Analyze the kernel symbol table of the operating system, obtain the function entry address and function name, search for the obtained function file and line number to complete the function information according to the address and function name, and record it in the function list array;

Read the module symbol table, obtain the function symbol table of the module, and record it into the module function list array;

If the given address is found in the function list array, return the module name and function name;

If the given address is found in the module function list array, return the module name and function name of the system;

If the given address cannot be found in both the function list array and the module function list array, it is judged whether the function exists in the memory,

If it exists in the memory, read the memory address from the memory, read the symbolic address sequentially after this address to judge whether it is consistent with the address to be queried, and record the memory location, read the memory information from the recorded location as the function name index address, If it is found, read the length of the symbol name according to the index address and the start address of the symbol address, calculate the offset of the searched address, obtain the length of the function name, and then return the function name;

If it does not exist in the memory, read the corresponding function name in the symbol table of the loaded module, read the memory address from the module, and obtain the function name of the module through the module address.

Further, the function call relationship is added to the recorded tracking data file and converted into a standard format, and the data is uploaded to the static function call relationship generation device,

The supplementary function call relationship includes: pairing the call and return of the function according to the process number, thread number and stack top pointer of the call and return, simultaneously obtaining the execution time of the function, and converting the data into a standard format;

The data uploaded to the static function call relationship generation device includes:

According to the directory and file name provided by the FROM field, copy the records to the dynamic function call relationship file of the corresponding source code file;

Determine whether the function call originates from the file according to the TO field in each dynamic function call relationship file,

If it is not the file, write the dynamic function external call relationship file to the corresponding source code file, and judge whether the file originates from the directory at the same time, if it is not the dynamic function external call relationship file written to the corresponding directory;

Return to the upper-level directory layer by layer according to the external-call relationship file of the last-level directory to fill in the external-call relationship file of the upper-level directory.

Further, the method further includes a step of displaying the function call relationship diagram, and a step of caching the generated function call relationship diagram and list.

In the present invention, the dynamic tool combined with the function call graph tool can express the call relationship between files and modules within a specified time in the form of connections, and can find the pointer function call bound at runtime and the function call of the loadable module . Moreover, because the dynamic tracking method gives call and return instructions, it can track the function call relationship during a part of the system startup time, and this tool can also be combined with other dynamic function tracking tools to display the results of other tools.

Description of drawings

FIG. 1 is a flow chart of obtaining function names and module names by a method for determining a dynamic function call relationship based on a register transfer language in the present invention.

FIG. 2 is a flow chart of the data acquisition algorithm of the method for determining the dynamic function call relationship based on the register transfer language of the present invention.

detailed description

The present invention will be further described below in conjunction with the accompanying drawings.

In this embodiment, a method for determining a dynamic function call relationship based on a register transfer language, the method includes:

Detect function call execution events during system operation,

If a call instruction is detected, analyze the function name corresponding to the function entry address called by the instruction, count the number of instructions, output the function name, call occurrence time, process number, thread number, stack top pointer and module number, and save to the trace data file;

If the detected command is after the return command, output the time, process number, thread number and stack top pointer to the tracking data file;

The trace data file is processed to obtain a predetermined standard data format, and the processed trace data file is transmitted to the static function call relationship generation device to generate a dynamic function call graph describing the function call relationship.

As shown in Figure 1, it is determined in turn whether the function is in the kernel or in each loadable module. The generation method of described tracking data file comprises:

Obtain the function name corresponding to the function entry address, the list of the file where the function is located and the line number by parsing the target file;

Analyze the operating system kernel (system.map) symbol table, obtain the function entry address and function name, search for the obtained function file and line number to complete the function information according to the address and function name, and record it in the function list array;

Read the module symbol table, obtain the function symbol table of the module, and record it into the module function list array;

If the given address is found in the function list array, return the module name and function name;

If the given address is found in the module function list array, return the module name (kernel) and function name of the system, and the function name is obtained by looking up the table;

If the given address cannot be found in both the function list array and the module function list array, it is judged whether the function exists in the memory,

If it exists in the memory, read the memory address from the memory, read the symbolic address sequentially after this address to judge whether it is consistent with the address to be queried, and record the memory location, read the memory information from the recorded location as the function name index address, If it is found, read the length of the symbol name according to the index address and the start address of the symbol address, calculate the offset of the searched address, obtain the length of the function name, and then return the function name;

If it does not exist in the memory, read the corresponding function name in the symbol table of the loaded module, read the memory address from the module, and obtain the function name of the module through the module address.

In this embodiment, the kernel function call detection plug-in (LinuxCallMonitor) is used to obtain the call and return instructions generated in the function call process, and then the obtained kernel symbols and the function path and line number information obtained by parsing the elf file are corresponding to the instruction information to obtain the update subsequent records. The implementation of the LinuxCallMonitor plug-in function depends on the kernel symbol table resolution plug-in (SymbolResolver) and the FunctionMonitor plug-in (virtual machine-S2E provides detection for obtaining function call instructions in the system), and the CallSignal can be used to detect functions after registering block translation events Call execution event, after the call command is detected, the function entry address called by the command is parsed to obtain the function name corresponding to the address, the number of commands is counted, and the function name, call occurrence time, process number, thread number, stack top pointer and module number, and save to the trace data file. When the detected instruction is a return instruction, only the time, process number, thread number and stack top pointer are output to the trace data file

Use the module symbol table provided by the SymbolResovler plug-in and kernel compilation and parse the elf format of the operating system executable file (vmlinux) to obtain the function name and line number of the file where the function is located, and obtain a symbol table including the function entry address, function name, and line number. The function call obtained by the virtual machine-S2E is only the function entry address. How to correctly resolve the function name corresponding to the address is the key issue of dynamic tracking. The way to obtain the symbol table can be mainly divided into two types: the symbol table in the object file and the symbol table in the memory when the system is running. The symbol table in the object file can be divided into three categories: global symbols in this file, global symbols in other files referenced by this file, and local symbols in this file. For these symbol tables, nm provided by GNU binutils can be used. Obtain, but can only obtain the symbol table of the kernel itself, and can't do anything about the symbols in the modules loaded when the kernel is running, and S2E is a virtual machine running on the host, we can directly obtain and find symbols from the memory of the client surface.

The version after Linux2.6 introduces the kallsyms function. Kallsyms connects all symbol addresses and names used in the kernel into the kernel file, so that after the kernel starts, the information of kallsyms will be loaded into the memory to facilitate kernel debugging. Therefore, the implementation of the kallsyms mechanism makes the memory also store a System.map, so the principle of the kallsyms mechanism can be used to extract the symbol table in the kernel, and this table contains the symbol information of the modules loaded after the system starts.

Supplement the function call relationship to the recorded tracking data file and convert the standard format, upload the data to the static function call relationship generation device,

The supplementary function call relationship includes: pairing the call and return of the function according to the process number, thread number and stack top pointer of the call and return, simultaneously obtaining the execution time of the function, and converting the data into a standard format;

As shown in FIG. 2 , after being processed into standard data, each file and the dynamic function call relationship files in the directory are processed sequentially. The data uploaded to the static function call relationship generation device includes:

Copy the records to the dynamic function call relationship file (.dynfctrlt) of the corresponding source code file according to the directory and file name provided by the FROM field;

According to whether the TO field function in each dynamic function call relation file (.dynfctrlt) file originates from this file,

If it is not the file, then write the dynamic function external call relationship file (. .dynDoutlst);

According to the dynamic function external call relation file (.dynDoutlst) file of the last level directory, return the upper level directory layer by layer to fill in the .dynDoutlst file of the upper level directory.

Further, the method further includes a step of displaying the function call relationship diagram, and a step of caching the generated function call relationship diagram and list, and this step is realized through a browser.

The specific operation process of the method is as follows:

The first step, environmental requirements and installation of necessary software packages:

1. Host environment ubuntu64 12.04 64 bits

2. Packages that need to be installed:

$ sudo apt-get install build-essential

$ sudo apt-get install subversion

$ sudo apt-get install git

$ sudo apt-get install gettext

$ sudo apt-get install liblua5.1-dev

$ sudo apt-get install libsdl1.2-dev

$ sudo apt-get install libsigc++-2.0-dev

$ sudo apt-get install binutils-dev

$ sudo apt-get install python-docutils

$ sudo apt-get install python-pygments

$ sudo apt-get install nasm

$ sudo apt-get build-dep llvm-3.0

$ sudo apt-get build-dep qemu

3. Download the s2e installation package and install s2e

$ mkdir S2EDIR

$cd $S2EDIR

$ git clone https://github.com/dslab-epfl/s2e.git $mkdir build

$ cd build

$ make –f ../s2e/Makefile

The second step, environmental requirements and installation of necessary software packages:

1. LinuxCallMonitor plugin

A. Register the onTranslateBlockStart event

B. Get call and return instructions

C. Call the symbol table to obtain the function name and module name

D. The output call event includes function name, module name, event occurrence time, current process number, current thread number and current stack top pointer

The specific content is as follows:

1.1 initialization initialize

Load SymbolResolver, FunctionMonitor:(s2e()->getPlugin(""));

Open the first write file XXX-FuncTracer_00000.dat

Register block translation event (onTranslateBlockStart)

1.2 slotTranslateBlockStart event

Detect call execution events through CallSignal,

The call event is detected and processed through callHandler

1.3 callHandler

Obtain the corresponding function name through the address: the symtab_search function implementation in SymbolResolver;

Simultaneously count the number of call and ret events. If the number exceeds 20000000, open a new write file and clear the count at the same time;

Register the callback function executed by ret, detect the return of the function and process the return information retHandler;

Output event occurrence time, process number, thread number, stack top pointer, module name, function name.

1.4 retHandler

Count the number of call and ret, if the number exceeds 20000000, open a new write file, and clear the count at the same time;

Output the event occurrence time, process ID, thread ID, and stack top pointer.

2. SymbolResolver plugin

A. Obtain the kernel and module symbol table

B. Analyze the elf format of the vmlinux file to obtain the function name and line number where the function is located

C. Form a symbol list: address, function name, line number of the function

2.1 initialization initialize

Load system.map, vmlinux;

Call read_vm() to obtain the function name corresponding to the function entry address, the list of the file where the function is located and the line number;

Read system.map, parse the symbol table, complete the function information according to the address and function name and the file and line number of the function obtained by read_vm(), and record it in the function list array addrsym_tab[]; record symbols according to the symbol information The start and end of the table and other address information mainly include: __start__ksymtab, __stop__ksmtab, kallsyms_addresses (all symbol addresses), kallsyms_num_syms (total number of symbols), kallsyms_names, kallsyms_markers, kallsyms_token_table, kallsyms_token_index, modules, and their corresponding address information.

Read the module symbol table, get the function symbol table of the module, and record it in the array addrmod_tab[].

2.2 symtab_search

Return the function name, the file where the function is located and the line number according to the address.

If the given address is found in addrsym_tab[], return the kernel (module name) and function name;

If the given address is found in addrmod_tab[], return the module name (system) and function name;

otherwise:

Read kallsyms_num_syms (total number of symbols) from the memory; read the symbol address once after kallsyms_addresses in the memory to judge whether it is consistent with the address to be queried, and record the memory location; read the memory information from the record location as the function name index address, if found Then read the length of the symbol name according to the index address and the start address of the symbol address, calculate the offset of the searched address, obtain the length of the function name, and then return the function name; otherwise, read the corresponding function name in the symbol table of the loaded module

2.3search_func_line、read_vm、describe_elf_hdr、dir_file_table、describe_one_section、describe_elf_sections、dwarf_tag_name、dwarf_attr_name、is_compile_unit、output_compilation_unit_header、read_1_byte、read_signed_leb128、describe_one_compile_unit等是解析vmlinux文件的elf格式获取函数入口地址以及对应函数名及函数所在文件行号的函数And dependent functions, the principle and process are not described here.

The third step is to compile s2e and run s2e:

1. Modify Makefile.target

2. Modify the s2e/qemu/Makefile.target file:

Add two lines after s2eobj-y+=s2e/Plugins/ConsistencyModels.o:

s2eobj-y+=s2e/Plugins/LinuxCallMonitor.o

s2eobj-y+=s2e/Plugins/SymboleResolver.o

3. Compile s2e

4. Compile the corresponding version of the kernel, this project is linux-3.5.4, the cpu is 32 bits: namely make i386_defconfig.

In order to obtain the function definition line number, you need to check the debug information when compiling the kernel: Kernel hacking option in menuconfig, select kernel debugging and Compile kernel with debug info.

After the compilation is complete, arch/x86/boot/bzIamge, vmliux, and System.map need to be used in s2e operation.

5. Configure config.lua

6. Create system s2e running system disk

A. Complex system:

a. Create an empty disk

qemu-img create–f raw name.raw*G; name image name, *G What is the size of the disk in G

b. Install the system, use qemu without s2e

qemu-system-i386name.raw–cdrom***.iso; ***.iso system installation file, installed from cdrom.

c. Disk type conversion; s2e can only accept qcow2 type disks

qemu-img convert –c name.raw –o qcow2new-name.qcow2

d. Test whether the system can start normally; without s2e

qemu-system-i386–kernel bzImage–hdc name.raw-append “/root/sda1”; the kernel image compiled before bzImage

B. Simple system busybox (www.cnblogs.com/senix/archive/2013/02/21/2921221.html)

a. Download busybox source code:

I downloaded busybox-1.21.0,

Decompression: tar–xf busybox-1.21.0.tar.bz2

b. Compile busybox

make deconfig

make menuconfig: Modify Busybox Settings Build Option[*]Build Busybox asa static binary(no shared libs)

make

make install

c. Simulate linux through qemu

(1), write initrd startup script

(2), write the script to build the initrd image

(3), write startup script, test busybox

7. Run s2e to record execution trace

Write an automatic run script run.sh

A. Complex system

"#!/bin/sh

i386-s2e-softmmu/qemu-system-i386-kernel arch/x86/boot/bzImage-hdcnew-name.qcow2-append "root=/dev/sda1"-s2e-config-file config.lua-s2e-verbose

"

B. Simple system

"#!/bin/sh

LINUX＝$(find linux*-maxdepth 0)

i386-s2e-softmmu/qemu-system-i386 --kernel $LINUX/arch/i386/boot/bzImage --initrd rootfs.img --append "root=/dev/ram rdinit=sbin/init" --s2e-config-file config .lua – rtc clock=vm

"

8. trace result

At present, the result is fixedly named and placed in /mnt/freenas/dyn-trace-log/b-FuncTracer_*.dat. No line in the result only displays the call function or return, and each file records 20000000 instructions. Format:

calltime, pid, module, pc/call name

9. Result processing

It is considered that there is only one stack, and the top of the stack is the function caller.

a. Complete the function call relationship: process.py. The intermediate result format is:

calltime, pid, module, tid, exp, pc/call name, from, pc/call name algorithm:

If the top of the stack is empty, scan the results line by line. If it is a call line, push the function corresponding to the call onto the stack. Whoever calls the function will obtain the previous content on the top of the stack; if it is ret, the thread, process number, and stack top pointer The same stack content is popped; until the end.

b. Conversion standard format: s2eout-standardout.rb. The format is:

PID:pid TID:tid CALL_TIME:time RETURN_TIME:NULL FROM:call name,/file.c:line TO:call name1,/file1.c:line1 AT:NULL time:function run time

Note: There is currently no place to call this function.

c. Store the data in the dynamic function call relationship file (.dynfctrlt file) of the corresponding source code file in the corresponding directory according to the FROM field: systemtapdata.rb

The data format remains unchanged. First, according to the directory and file name provided by the FROM field, copy the results of record b to the .dynfctrlt file of the corresponding source code file. Secondly, according to whether the TO field function in each .dynfctrlt file originates from the file, if not, write it into the .dynoutlst file of the corresponding source code file, and judge whether the file originates from the directory, or write it to The .dynDoutlst file of the corresponding directory. Finally, according to the .dynDoutlst file of the last layer directory, return to the upper level directory layer by layer to fill in the .dynDoutlst file of the upper level directory.

The above are only preferred embodiments of the present invention, but the scope of protection of the present invention is not limited thereto. Any changes or substitutions that can be easily conceived by those skilled in the art within the technical scope disclosed in the present invention are all Should be covered within the protection scope of the present invention. Therefore, the protection scope of the present invention should be defined by the claims.

Claims (4)

1. a kind of method that kinematic function call relation is determined based on register transfer language, it is characterised in that：

Methods described includes：

Detection function calls execution event in system operation,

If detecting after call instruction, the corresponding function name in function entrance address of the instruction calls is parsed, statistics instructs number of times, Output function name, time of origin, affiliated process number, affiliated thread number, affiliated top-of-stack pointer and module No. are called, and be saved in Track data file；

If after the instruction of detection is return instruction, output time, affiliated process number, affiliated thread number and affiliated top-of-stack pointer are arrived Track data file；

The data format that processing obtains preassigned is carried out to the track data file, the track data file after processing is passed Transport in static function call relation generating means, generate the kinematic function calling figure of described function call relation.

2. the method according to claim 1 that kinematic function call relation is determined based on register transfer language, its feature It is：The generation method of the track data file includes：

File and the row of line number where obtaining the corresponding function name in function entrance address, function by the parsing to file destination Table；

Operating system nucleus symbol table is parsed, function entrance address and function name is obtained, is searched and obtained according to address and function name Function where file and line number completion function information, and recorded in function list array；

Read module symbol table, the functional symbol table of acquisition module, and recorded in modularity function list array；

If given address is found in function list array, module name and function name are returned；

If given address is found in modularity function list array, the module name and function name of return system；

If given address can not find in the function list array and the modularity function list array, discriminant function is It is no to exist in internal memory,

If existing in internal memory, memory address is read from internal memory, be successively read after this address symbolic address judge with Address need to be inquired about whether consistent, and record core position, it is function name index address to read memory information from record position, if looking into To then symbolic name length is read according to index address and symbolic address initial address, the skew of looked into address is calculated, letter is obtained Several length, and then return function name；

If being not present in internal memory, read in the symbol table of load-on module in corresponding function name, slave module and read internal memory Address, passes through the function name of module's address acquisition module.

3. the method according to claim 1 that kinematic function call relation is determined based on register transfer language, its feature It is：To the track data file supplement function calling relationship and transformation standard form of record, data are uploaded to static function Call relation generating means,

Wherein described supplement function calling relationship includes：According to the process number for calling and returning, thread number and top-of-stack pointer come Function is called and come back for pairing, while the execution time of function is obtained, while data are converted into reference format；

The data, which are uploaded to static function call relation generating means, to be included：

The catalogue and filename provided by FROM fields, the kinematic function that record is copied to corresponding source code file respectively is called In relational file；

Judge whether the function call is derived from this document according to the TO fields in each kinematic function call relation file,

If not the external call relation file of kinematic function for being then written to correspondence source code file of this document, while judging to be somebody's turn to do Whether file is derived from the catalogue, if not being written to the external call relation file of kinematic function of correspondence catalogue；

Upper level catalogue is successively returned to according to the external call relation file of the kinematic function of last layer of catalogue and fills in upper level mesh The external call relation file of kinematic function of record.

4. the method according to claim 1 that kinematic function call relation is determined based on register transfer language, its feature It is：The step of methods described also includes showing the function call relationship graph, and the function call relationship graph to having generated The step of being cached with list.