[go: up one dir, main page]

CN113157979A - Method, system and medium for constructing kernel module relational graph based on dummy module nodes - Google Patents

Method, system and medium for constructing kernel module relational graph based on dummy module nodes Download PDF

Info

Publication number
CN113157979A
CN113157979A CN202110281352.9A CN202110281352A CN113157979A CN 113157979 A CN113157979 A CN 113157979A CN 202110281352 A CN202110281352 A CN 202110281352A CN 113157979 A CN113157979 A CN 113157979A
Authority
CN
China
Prior art keywords
module
node
function
kernel
graph
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
CN202110281352.9A
Other languages
Chinese (zh)
Other versions
CN113157979B (en
Inventor
秦莹
马俊
李小玲
高珑
王静
谭郁松
阳娅婧
张雅媛
熊茂屹
张新举
武佳文
张玉栋
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
National University of Defense Technology
Original Assignee
National University of Defense Technology
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by National University of Defense Technology filed Critical National University of Defense Technology
Priority to CN202110281352.9A priority Critical patent/CN113157979B/en
Publication of CN113157979A publication Critical patent/CN113157979A/en
Application granted granted Critical
Publication of CN113157979B publication Critical patent/CN113157979B/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/901—Indexing; Data structures therefor; Storage structures
    • G06F16/9024—Graphs; Linked lists
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/28—Databases characterised by their database models, e.g. relational or object models
    • G06F16/284—Relational databases
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
    • Y02D10/00—Energy efficient computing, e.g. low power processors, power management or thermal management

Landscapes

  • Engineering & Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Data Mining & Analysis (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Software Systems (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

The invention discloses a method, a system and a medium for constructing a kernel module relational graph based on dummy module nodes, wherein the method comprises the steps of inputting a kernel module set M; establishing a module node for each kernel module in the kernel module set M to obtain a kernel module node set { NmIn which N ismRepresents the mth kernel module; introducing a dummy module node; extract kernel module node set { NmIn functions and out functions of all kernel modules in the database, reference relations among the kernel modules are established in the database based on symbol corresponding relations among the in functions and the out functions, reference relations among the kernel modules are established based on External data and Export data, and nodes without reference relations are recorded through dummy module nodes. The method supports the on-demand expansion and reduction of the kernel module function call relation graph and the kernel module data sharing relation graph, and has the advantages of quick and efficient reconstruction.

Description

Method, system and medium for constructing kernel module relational graph based on dummy module nodes
Technical Field
The invention relates to the technical field of operating system kernel and version compatibility guarantee during kernel module upgrading, in particular to a method, a system and a medium for constructing a kernel module relational graph based on dummy module nodes.
Background
In the application process of an information system, the problems of large workload, high complexity and the like of migration of peripheral hardware and upper-layer application caused by upgrading and upgrading of an operating system kernel exist, the main reason is that the upgrading brings changes of kernel functions and data structures, when functions and data in a kernel module are changed, other operating system components for calling the functions are affected, and the situation that execution cannot be carried out or is abnormal occurs, and the situation is the compatibility problem of the kernel module. Solving the kernel module compatibility problem requires accurate disambiguation functions and data change induced effects. Because an intricate relationship diagram is formed between kernel modules based on function calling and data structure sharing, the premise of accurately calculating compatibility influence caused by kernel module change is that the relationship between kernel module sets can be described.
From an implementation perspective, a kernel is composed of functions and data, and the functions contain program code that implements the functions. In order to reduce the complexity of implementing a single function, a large function is often split into multiple function implementations, and a subject function calls the functions to complete a complex function. Often, a function is split into multiple functions and encapsulated in multiple kernel modules. Function calls and data sharing across modules are very common.
Both functions and data exist in the form of symbols in the kernel. According to different functions, functions in the kernel module include two types, one is a kernel function, which is referred to as an in function (InFun) in this document, and is a function which is implemented in the kernel module and can be called by other kernel modules; one is a kernel call function, referred to herein as the out function (CallFun), which is a function that is implemented in other kernel modules and called by functions in the module. According to different scope of action, the data in the kernel module is divided into local data, global data and external data, wherein the local data is private data in the kernel module, cannot be sensed by the external module, and is not discussed in the scope of the text; the global data is defined in the module and is shared by a plurality of modules for use, and is referred to as Export data; the External data is the data defined in the External module used in this module and is referred to herein as External data.
A large number of function calling relations and data sharing relations exist among the kernel modules. In order to accurately describe the relationship set, the building of a module relationship graph through function calls and data sharing relationships among modules becomes a primary task. It is particularly worth noting that the kernel module graph is required to be reconstructed when the kernel is upgraded because the kernel module is increased or decreased and the kernel function is increased or decreased to cause the change of the kernel module graph. However, how to implement the above requirements for building the module relationship diagram is still a key technical problem to be solved.
Disclosure of Invention
The technical problems to be solved by the invention are as follows: aiming at the problems in the prior art, the invention provides a method, a system and a medium for constructing a kernel module relational graph based on dummy module nodes, the method, the system and the medium support the on-demand expansion and reduction of a kernel module function call relational graph and a kernel module data sharing relational graph by introducing the dummy module nodes, and have the advantages of quick and efficient reconstruction.
In order to solve the technical problems, the invention adopts the technical scheme that:
a method for constructing a kernel module relational graph based on dummy module nodes comprises the following steps:
1) inputting a kernel module set M;
2) establishing a module node for each kernel module in the kernel module set M to obtain a kernel module node set { NmIn which N ismRepresents the mth kernel module; introducing a dummy module node;
3) extract kernel module node set { NmObtaining an in function table and an out function table of each kernel module in the kernel module; establishing a reference relation between kernel modules in a graph database according to the symbol corresponding relation between any in function and any out function in the in function table and the out function table, establishing a reference relation between a dummy module node and a corresponding kernel module under the condition that the corresponding relation between the in function and the out function cannot be established, and obtaining a function call relation graph GFdep(ii) a According to kernel module node set { NmEstablishing an External data table and an Export data table according to External data and Export data, establishing a reference relationship between kernel modules in a graph database according to a symbol corresponding relationship between the External data and the Export data, establishing a reference relationship between a dummy module node and a corresponding kernel module under the condition that the corresponding relationship between the External data and the Export data cannot be established, and obtaining a data sharing relationship graph GDdep；
4) Calling a function to a relational graph GFdepAnd data sharing relationship diagram GDdepConstructing a kernel module dependency graph GM。
Optionally, the dummy module nodes introduced in step 2) include temporarily-undiscovered nodes for storing all temporarily-undefined function symbols and temporarily-unused nodes for storing function symbols that have not been referenced yet.
Optionally, the step of establishing, in step 3), a reference relationship between the kernel modules in the graph database according to a symbol correspondence between any in function and any out function in the in function table and the out function table, and establishing a reference relationship between a dummy module node and a corresponding kernel module in a case where the correspondence between the in function and the out function cannot be established includes: firstly, traversing each out function in an out function table as a current out function, searching a corresponding in function in the in function table aiming at the current out function, if the corresponding in function is found, establishing a reference relationship between a core module corresponding to the current out function and a core module corresponding to the found in function in a graph database, otherwise, establishing a reference relationship between the core module corresponding to the current out function and a node which is not found temporarily in the graph database; then, checking whether an in function table has an in function which is not matched, if so, establishing a reference relation between a kernel module corresponding to the in function and a node which is not used temporarily in a graph database, thereby obtaining a function call relation graph GFdep。
Optionally, the step of establishing a reference relationship between kernel modules in the graph database according to the symbol correspondence between the External data and the External data in step 3), and establishing a reference relationship between a dummy module node and a corresponding kernel module when the correspondence between the External data and the External data cannot be established includes: firstly, traversing each External data in the External data table as the current External data, searching corresponding External data in the External data table aiming at the current External data, if the corresponding External data is found, establishing a reference relationship between a kernel module corresponding to the current External data and a kernel module corresponding to the found External data in a graph database, otherwise, establishing a reference relationship between the kernel module corresponding to the current External data and a node which is not found temporarily in the graph database(ii) a Then, checking whether unmatched Export data exists in an Export data table, if the unmatched Export data exists, establishing a reference relationship between a kernel module corresponding to the Export data and a temporarily unused node in a graph database to obtain a data sharing relationship graph GDdep。
Optionally, after the step 4), updating the kernel module dependency graph G when a kernel module is newly addedMThe steps of (1):
A1) inputting a newly added kernel module m and a kernel module dependency graph G to be updatedM；
A2) Building module node n for kernel module mmAnd connecting the module node nmAdding to the kernel module dependency graph G to be updatedMModule node set of { N }MIn (1) };
A3) node n according to modulemIn function and out function updating function call relation graph GFdepObtaining the updated function call relation graph GFdepAccording to module node nmThe Export data and External data update data sharing relation graph GDdepObtaining an updated data sharing relation graph GDdep；
A4) The updated function call relation graph GFdepAnd the updated data sharing relation graph GDdepForming updated kernel module dependency graph GM。
Optionally, step a3) comprises: node n of modulemUpdate the in function to the set of module nodes { N }MIn the in function table of the module, the node n of the module is setmOut function of (2) updates to the set of module nodes NMIn the out function table of; building a module node nmOut function of and { NMIn function symbol corresponding relation in function table of the database, establishing reference relation between modules in the database; if module node nmThe in function of (2) has a corresponding out function in the node which is not found temporarily, and is a module node nmEstablishing a reference relation with a kernel module corresponding to an out function in a node which is not discovered temporarily; if module node nmThere are in functions in the set of in functions that are not matched,establishing a reference relationship between the kernel module corresponding to the in function which is not matched and the temporarily unused node in the graph database to obtain an updated function call relationship graph GFdep(ii) a Node n of modulemUpdate Export data to Module node set NMIn the Export data table of (1), module node n is storedmIs updated to the set of module nodes NMIn the External data sheet of; building a module node nmExternal data of (2) and { NMCorresponding relation of Export data symbols in an Export data table of the database is established, and reference relation among modules is established in a database; if module node nmThe Export data of (1) has corresponding External data in the node which is not discovered temporarily, and is a module node nmEstablishing a reference relation with a kernel module corresponding to External data in the node which is not discovered temporarily; if module node nmIf unmatched Export data exist in the Export data set, establishing a reference relationship between a kernel module corresponding to the unmatched Export data and a temporarily unused node in a graph database to obtain an updated data sharing relationship graph GDdep。
Optionally, after the step 4), updating the kernel module dependency graph G when the kernel module is deletedMThe steps of (1):
B1) inputting a kernel module m to be deleted and a kernel module dependency graph G to be updatedM；
B2) From the kernel module dependency graph G to be updatedMModule node set of { N }MDeleting module node n corresponding to kernel module m in the kernel modulem；
B3) Node n according to modulemIn function and out function updating function call relation graph GFdepObtaining the updated function call relation graph GFdepAccording to module node nmThe Export data and External data update data sharing relation graph GDdepObtaining an updated data sharing relation graph GDdep；
B4) The updated function call relation graph GFdepAnd the updated data sharing relation graph GDdepComposing updated kernel modelsBlock dependency graph GM。
Optionally, step B3) comprises: node n of modulemFrom the set of module nodes { N }MRemoving the in function table of the module, and connecting the node n of the modulemOut function of (2) from the set of module nodes NMRemove from the out function table of; for corresponding module node n in temporarily unused nodemIf the in function is not used, the in function is directly deleted from the temporarily unused node, otherwise, the kernel module j and the module node n are used for any other kernel module j using the in function in the graph databasemThe reference relationship between the kernel module j and the nodes which are not discovered temporarily is modified to obtain an updated function call relationship graph GFdep(ii) a Node n of modulemExport data Slave Module node set of { N }MRemove the Export data table of module node nmFrom the set of module nodes { N } of External dataMRemove from the External data table of }; for corresponding module node n in temporarily unused nodemIf the Export data is not used, the Export data is directly deleted from the temporarily unused nodes, otherwise, the kernel module j and the module node n are used in the graph database for any other kernel module j using the Export datamThe reference relationship between the kernel module j and the nodes which are not discovered temporarily is modified to obtain an updated data sharing relationship graph GDdep。
In addition, the invention also provides a system for constructing the kernel module relational graph based on the dummy module nodes, which comprises a microprocessor and a memory which are connected with each other, wherein the microprocessor is programmed or configured to execute the steps of the method for constructing the kernel module relational graph based on the dummy module nodes.
In addition, the present invention also provides a computer readable storage medium having stored therein a computer program programmed or configured to execute the method for constructing a kernel module relationship graph based on dummy module nodes.
Compared with the prior art, the invention has the following advantages: the invention includes an inputA core module set M; establishing a module node for each kernel module in the kernel module set M to obtain a kernel module node set { NmIn which N ismRepresents the mth kernel module; introducing a dummy module node; extract kernel module node set { NmObtaining an in function table and an out function table of each kernel module in the kernel module; establishing a reference relation between kernel modules in a graph database according to the symbol corresponding relation between any in function and any out function in the in function table and the out function table, establishing a reference relation between a dummy module node and a corresponding kernel module under the condition that the corresponding relation between the in function and the out function cannot be established, and obtaining a function call relation graph GFdep(ii) a According to kernel module node set { NmEstablishing an External data table and an Export data table according to External data and Export data, establishing a reference relationship between kernel modules in a graph database according to a symbol corresponding relationship between the External data and the Export data, establishing a reference relationship between a dummy module node and a corresponding kernel module under the condition that the corresponding relationship between the External data and the Export data cannot be established, and obtaining a data sharing relationship graph GDdep(ii) a Calling a function to a relational graph GFdepAnd data sharing relationship diagram GDdepConstructing a kernel module dependency graph GMIn the mode, a kernel module relation graph model based on function call relation and data sharing and a basic method for constructing the kernel module relation graph model are provided, and the kernel module function call relation graph and the kernel module data sharing relation graph are expanded and reduced as required by introducing dummy module nodes, so that the kernel module relation graph model has the advantages of being fast and efficient in reconstruction. Moreover, when the kernel module dependency directed graph is constructed according to the function call relation between the kernel and the kernel modules, and when the kernel module set changes, the method supports the construction of the changed module dependency graph by increasing or decreasing the kernel modules, the functions and the shared data symbols in the kernel module dependency graph based on the old version, and improves the construction efficiency of the module dependency graph.
Drawings
Fig. 1 is a schematic flowchart of a method for constructing a kernel module dependency graph based on dummy module nodes in an embodiment of the present invention.
Fig. 2 is a schematic flowchart of a method for extending a kernel module dependency graph based on dummy module nodes in an embodiment of the present invention.
Fig. 3 is a schematic flowchart of a method for reducing a kernel module dependency graph based on dummy module nodes in an embodiment of the present invention.
Detailed Description
As shown in fig. 1, the method for constructing a kernel module relationship graph based on dummy module nodes in this embodiment includes:
1) inputting a kernel module set M;
2) establishing a module node for each kernel module in the kernel module set M to obtain a kernel module node set { NmIn which N ismRepresents the mth kernel module; introducing a dummy module node;
3) extract kernel module node set { NmObtaining an in function table and an out function table of each kernel module in the kernel module; establishing a reference relation between kernel modules in a graph database according to the symbol corresponding relation between any in function and any out function in the in function table and the out function table, establishing a reference relation between a dummy module node and a corresponding kernel module under the condition that the corresponding relation between the in function and the out function cannot be established, and obtaining a function call relation graph GFdep(ii) a According to kernel module node set { NmEstablishing an External data table and an Export data table according to External data and Export data, establishing a reference relationship between kernel modules in a graph database according to a symbol corresponding relationship between the External data and the Export data, establishing a reference relationship between a dummy module node and a corresponding kernel module under the condition that the corresponding relationship between the External data and the Export data cannot be established, and obtaining a data sharing relationship graph GDdep；
4) Calling a function to a relational graph GFdepAnd data sharing relationship diagram GDdepConstructing a kernel module dependency graph GM。
In this embodiment, the dummy module nodes introduced in step 2) include a temporarily undiscovered node (notfound _ dummy) and a temporarily unused node (unused _ dummy), where the temporarily undiscovered node is used to store all temporarily undefined function symbols, and the temporarily unused node is used to store function symbols that have not been referenced yet.
In this embodiment, the step 3) of establishing, in the graph database, a reference relationship between the kernel modules according to a symbol correspondence between any in function and any out function in the in function table and the out function table, and establishing, in the case where the correspondence between the in function and the out function cannot be established, a reference relationship between the dummy module node and the corresponding kernel module includes: firstly, traversing each out function in an out function table as a current out function, searching a corresponding in function in the in function table aiming at the current out function, if the corresponding in function is found, establishing a reference relationship between a core module corresponding to the current out function and a core module corresponding to the found in function in a graph database, otherwise, establishing a reference relationship between the core module corresponding to the current out function and a node which is not found temporarily in the graph database; then, checking whether an in function table has an in function which is not matched, if so, establishing a reference relation between a kernel module corresponding to the in function and a node which is not used temporarily in a graph database, thereby obtaining a function call relation graph GFdep。
In this embodiment, the step 3) of establishing a reference relationship between kernel modules in the graph database according to the symbol correspondence between External data and External data, and establishing a reference relationship between a dummy module node and a corresponding kernel module for a case where the correspondence between External data and External data cannot be established includes: firstly, traversing each External data in an External data table as current External data, searching corresponding External data in an External data table aiming at the current External data, if the corresponding External data is found, establishing a reference relation between a kernel module corresponding to the current External data and a kernel module corresponding to the found External data in a graph database, and otherwise, establishing a reference relation between the kernel module corresponding to the current External data and nodes which are not found temporarily in the graph database; then, checking whether there is unmatched Export data in the Export data table, and if so, determining whether there is unmatched Export data in the graph databaseEstablishing a reference relationship between the kernel module corresponding to the Export data and the temporarily unused nodes to obtain a data sharing relationship graph GDdep。
As shown in fig. 2, after step 4), the method further includes updating a kernel module dependency graph G when a kernel module is newly addedMThe steps of (1):
A1) inputting a newly added kernel module m and a kernel module dependency graph G to be updatedM；
A2) Building module node n for kernel module mmAnd connecting the module node nmAdding to the kernel module dependency graph G to be updatedMModule node set of { N }MIn (1) };
A3) node n according to modulemIn function and out function updating function call relation graph GFdepObtaining the updated function call relation graph GFdepAccording to module node nmThe Export data and External data update data sharing relation graph GDdepObtaining an updated data sharing relation graph GDdep；
A4) The updated function call relation graph GFdepAnd the updated data sharing relation graph GDdepForming updated kernel module dependency graph GM。
In this embodiment, step a3) includes: node n of modulemUpdate the in function to the set of module nodes { N }MIn the in function table of the module, the node n of the module is setmOut function of (2) updates to the set of module nodes NMIn the out function table of; building a module node nmOut function of and { NMIn function symbol corresponding relation in function table of the database, establishing reference relation between modules in the database; if module node nmThe in function of (2) has a corresponding out function in the node which is not found temporarily, and is a module node nmEstablishing a reference relation with a kernel module corresponding to an out function in a node which is not discovered temporarily; if module node nmIf the in function set has the in function which is not matched, establishing the reference relation between the kernel module corresponding to the in function which is not matched and the temporarily unused node in the graph database to obtainTo updated function call relation graph GFdep(ii) a Node n of modulemUpdate Export data to Module node set NMIn the Export data table of (1), module node n is storedmIs updated to the set of module nodes NMIn the External data sheet of; building a module node nmExternal data of (2) and { NMCorresponding relation of Export data symbols in an Export data table of the database is established, and reference relation among modules is established in a database; if module node nmThe Export data of (1) has corresponding External data in the node which is not discovered temporarily, and is a module node nmEstablishing a reference relation with a kernel module corresponding to External data in the node which is not discovered temporarily; if module node nmIf unmatched Export data exist in the Export data set, establishing a reference relationship between a kernel module corresponding to the unmatched Export data and a temporarily unused node in a graph database to obtain an updated data sharing relationship graph GDdep。
As shown in fig. 3, the step 4) of this embodiment further includes updating the kernel module dependency graph G when deleting the kernel moduleMThe steps of (1):
B1) inputting a kernel module m to be deleted and a kernel module dependency graph G to be updatedM；
B2) From the kernel module dependency graph G to be updatedMModule node set of { N }MDeleting module node n corresponding to kernel module m in the kernel modulem；
B3) Node n according to modulemIn function and out function updating function call relation graph GFdepObtaining the updated function call relation graph GFdepAccording to module node nmThe Export data and External data update data sharing relation graph GDdepObtaining an updated data sharing relation graph GDdep；
B4) The updated function call relation graph GFdepAnd the updated data sharing relation graph GDdepForming updated kernel module dependency graph GM。
In this embodiment, step B3) includes: node n of modulemFrom the set of module nodes { N }MRemoving the in function table of the module, and connecting the node n of the modulemOut function of (2) from the set of module nodes NMRemove from the out function table of; for corresponding module node n in temporarily unused nodemIf the in function is not used, the in function is directly deleted from the temporarily unused node, otherwise, the kernel module j and the module node n are used for any other kernel module j using the in function in the graph databasemThe reference relationship between the kernel module j and the nodes which are not discovered temporarily is modified to obtain an updated function call relationship graph GFdep(ii) a Node n of modulemExport data Slave Module node set of { N }MRemove the Export data table of module node nmFrom the set of module nodes { N } of External dataMRemove from the External data table of }; for corresponding module node n in temporarily unused nodemIf the Export data is not used, the Export data is directly deleted from the temporarily unused nodes, otherwise, the kernel module j and the module node n are used in the graph database for any other kernel module j using the Export datamThe reference relationship between the kernel module j and the nodes which are not discovered temporarily is modified to obtain an updated data sharing relationship graph GDdep。
In summary, the kernel modules form an intricate and complex relationship diagram based on function call and data structure sharing. In this embodiment, the kernel module is used as a node in the graph, and if the kernel module a calls any kernel function in the kernel module B, a directed edge is connected between the kernel module a and the kernel module B, where a is a start node of the edge and B is a termination node of the edge, which indicates that the kernel module a depends on the kernel module B due to the function call. Executing the operation on all modules in the same kernel version to obtain a kernel module function dependency relationship graph GFdep. In this patent, the kernel module is used as a node in the graph, if the kernel modules a and B share the global data defined in B, a directed edge is connected between a and B, where a is the start node of the edge, B is the end node of the edge,this indicates that kernel module a depends on kernel module B for sharing data. Executing the above operations on all modules in the same kernel version to obtain a kernel module data sharing relation graph GDdep. Function call relation graph GFdepAnd data sharing relationship diagram GDdepJointly form a kernel module relation graph (G)M) Hence the kernel module relationship graph (G)M) Includes two relation graphs GDdepAnd GFdepThe structure of (1). According to the actual use requirement, the relation graph GDdepAnd GFdepThe construction process of the method comprises three processes of initialization, module addition and subtraction and module deletion. Through the mode, the kernel module relation graph model based on the function call relation and the data sharing and the basic method for constructing the kernel module relation graph model are provided, and the kernel module function call relation graph and the kernel module data sharing relation graph are expanded and reduced as required by introducing the dummy module node, so that the kernel module relation graph model has the advantages of being fast and efficient in reconstruction. Moreover, when the kernel module dependency directed graph is constructed according to the function call relation between the kernel and the kernel modules, when the kernel module set changes, the changed module dependency graph constructed by increasing or decreasing the kernel modules, the functions and the shared data symbols in the kernel module dependency graph based on the old version is supported, and the construction efficiency of the module dependency graph is improved.
In addition, the present embodiment also provides a system for constructing a kernel module relational graph based on dummy module nodes, which includes a microprocessor and a memory, which are connected to each other, and the microprocessor is programmed or configured to execute the steps of the method for constructing a kernel module relational graph based on dummy module nodes.
Furthermore, the present embodiment also provides a computer-readable storage medium in which a computer program is stored, the computer program being programmed or configured to execute the aforementioned method for constructing a kernel module relationship diagram based on dummy module nodes.
As will be appreciated by one skilled in the art, embodiments of the present application may be provided as a method, system, or computer program product. Accordingly, the present application may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects. Furthermore, the present application may take the form of a computer program product embodied on one or more computer-readable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, and the like) having computer-usable program code embodied therein. The present application is directed to methods, apparatus (systems), and computer program products according to embodiments of the application wherein instructions, which execute via a flowchart and/or a processor of the computer program product, create means for implementing functions specified in the flowchart and/or block diagram block or blocks. These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including instruction means which implement the function specified in the flowchart flow or flows and/or block diagram block or blocks. These computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.
The above description is only a preferred embodiment of the present invention, and the protection scope of the present invention is not limited to the above embodiments, and all technical solutions belonging to the idea of the present invention belong to the protection scope of the present invention. It should be noted that modifications and embellishments within the scope of the invention may occur to those skilled in the art without departing from the principle of the invention, and are considered to be within the scope of the invention.

Claims (10)

1.一种基于哑模块节点的内核模块关系图构建方法，其特征在于，包括：1. a method for constructing a kernel module relationship diagram based on a dumb module node, is characterized in that, comprising: 1)输入内核模块集合M；1) Input the kernel module set M; 2)对内核模块集合M中的每一个内核模块建立模块节点，得到内核模块节点集合{Nm}，其中Nm表示第m个内核模块；引入哑模块节点；2) establishing a module node for each kernel module in the kernel module set M, obtaining a kernel module node set {N m }, wherein N m represents the mth kernel module; introducing a dummy module node; 3)提取内核模块节点集合{Nm}中各个内核模块的in函数和out函数，得到in函数表和out函数表；根据in函数表和out函数表中任意in函数和out函数之间的符号对应关系在图数据库中建立内核模块之间的引用关系，且对无法建立in函数和out函数对应关系的情况建立哑模块节点和对应内核模块之间的引用关系，得到函数调用关系图GFdep；根据内核模块节点集合{Nm}中的External数据和Export数据建立External数据表和Export数据表，根据External数据和Export数据之间的符号对应关系在图数据库中建立内核模块之间的引用关系，且对无法建立External数据和Export数据对应关系的情况建立哑模块节点和对应内核模块之间的引用关系，得到数据共享关系图GDdep；3) Extract the in function and out function of each kernel module in the kernel module node set {N m }, and obtain the in function table and the out function table; according to the symbols between any in function and out function in the in function table and the out function table Correspondence relationship establishes the reference relationship between the kernel modules in the graph database, and establishes the reference relationship between the dummy module node and the corresponding kernel module for the situation where the corresponding relationship between the in function and the out function cannot be established, and obtains the function call relationship graph G Fdep ; The External data table and the Export data table are established according to the External data and the Export data in the kernel module node set {N m }, and the reference relationship between the kernel modules is established in the graph database according to the symbol correspondence between the External data and the Export data, And for the situation that the correspondence between the External data and the Export data cannot be established, the reference relationship between the dummy module node and the corresponding kernel module is established, and the data sharing relationship graph G Ddep is obtained; 4)将函数调用关系图GFdep和数据共享关系图GDdep构成内核模块依赖关系图GM。4) The function call relation graph G Fdep and the data sharing relation graph G Ddep form the kernel module dependency graph G M . 2.根据权利要求1所述的基于哑模块节点的内核模块关系图构建方法，其特征在于，步骤2)中引入的哑模块节点包括暂未发现节点和暂未使用节点，所述暂未发现节点用于存放所有暂未被定义的函数符号，所述暂未使用节点用于存放还未被引用的函数符号。2. the method for constructing the kernel module relationship diagram based on the dummy module node according to claim 1, is characterized in that, the dummy module node introduced in step 2) comprises temporarily undiscovered node and temporarily unused node, and described temporarily undiscovered node The node is used to store all function symbols that are not yet defined, and the temporarily unused node is used to store function symbols that have not been referenced yet. 3.根据权利要求2所述的基于哑模块节点的内核模块关系图构建方法，其特征在于，步骤3)中根据in函数表和out函数表中任意in函数和out函数之间的符号对应关系在图数据库中建立内核模块之间的引用关系，且对无法建立in函数和out函数对应关系的情况建立哑模块节点和对应内核模块之间的引用关系的步骤包括：首先，遍历out函数表中的每一个out函数作为当前out函数，针对当前out函数在in函数表中寻找对应的in函数，如果找到对应的in函数，则在图数据库中建立当前out函数对应的内核模块、找到的in函数对应的内核模块之间的引用关系，否则在图数据库中建立当前out函数对应的内核模块、暂未发现节点之间的引用关系；然后，检查in函数表中是否存在未被匹配的in函数，如果存在未被匹配的in函数，则在图数据库中建立该in函数对应的内核模块、暂未使用节点之间的引用关系，从而，得到函数调用关系图GFdep。3. the kernel module relation diagram construction method based on dummy module node according to claim 2, is characterized in that, in step 3), according to the symbol correspondence between any in function and out function in in function table and out function table The steps of establishing the reference relationship between the kernel modules in the graph database, and establishing the reference relationship between the dummy module node and the corresponding kernel module in the case where the corresponding relationship between the in function and the out function cannot be established, include: first, traversing the out function table. For each out function of , as the current out function, look for the corresponding in function in the in function table for the current out function. If the corresponding in function is found, the kernel module corresponding to the current out function and the found in function are established in the graph database. The reference relationship between the corresponding kernel modules, otherwise the kernel module corresponding to the current out function is established in the graph database, and the reference relationship between the nodes has not been found yet; then, check whether there is an unmatched in function in the in function table, If there is an unmatched in function, a reference relationship between the kernel module corresponding to the in function and the temporarily unused nodes is established in the graph database, thereby obtaining a function call relationship graph G Fdep . 4.根据权利要求2所述的基于哑模块节点的内核模块关系图构建方法，其特征在于，步骤3)中根据External数据和Export数据之间的符号对应关系在图数据库中建立内核模块之间的引用关系，且对无法建立External数据和Export数据对应关系的情况建立哑模块节点和对应内核模块之间的引用关系的步骤包括：首先，遍历External数据表中的每一个External数据作为当前External数据，针对当前External数据在Export数据表中寻找对应的Export数据，如果找到对应的Export数据，则在图数据库中建立当前External数据对应的内核模块、找到的Export数据对应的内核模块之间的引用关系，否则在图数据库中建立当前External数据对应的内核模块、暂未发现节点之间的引用关系；然后，检查Export数据表中是否存在未被匹配的Export数据，如果存在未被匹配的Export数据，则在图数据库中建立该Export数据对应的内核模块、暂未使用节点之间的引用关系，得到数据共享关系图GDdep。4. the method for constructing the kernel module relationship diagram based on the dumb module node according to claim 2, is characterized in that, in step 3), according to the symbol correspondence between External data and Export data, establish between kernel modules in the graph database The steps of establishing the reference relationship between the dummy module node and the corresponding kernel module include: first, traverse each External data in the External data table as the current External data , look for the corresponding Export data in the Export data table for the current External data, if the corresponding Export data is found, then establish the reference relationship between the kernel module corresponding to the current External data and the kernel module corresponding to the found Export data in the graph database , otherwise the kernel module corresponding to the current External data is established in the graph database, and the reference relationship between nodes has not been found yet; then, check whether there is unmatched Export data in the Export data table, if there is unmatched Export data, Then, establish the reference relationship between the kernel module corresponding to the Export data and the unused nodes in the graph database, and obtain the data sharing relationship graph G Ddep . 5.根据权利要求2所述的基于哑模块节点的内核模块关系图构建方法，其特征在于，步骤4)之后还包括在新增内核模块时更新内核模块依赖关系图GM的步骤：5. the method for constructing the kernel module relationship graph based on the dumb module node according to claim 2, is characterized in that, after step 4), also comprise the step of updating kernel module dependency graph GM when adding new kernel module: A1)输入新增的内核模块m，以及待更新的内核模块依赖关系图GM；A1) Input newly added kernel module m, and kernel module dependency graph G M to be updated; A2)为内核模块m建立模块节点nm，并将模块节点nm加入到待更新的内核模块依赖关系图GM的模块节点集合{NM}中；A2) establish a module node n m for the kernel module m, and add the module node n m to the module node set {N M } of the kernel module dependency graph GM to be updated; A3)根据模块节点nm的in函数、out函数更新函数调用关系图GFdep，得到更新后的函数调用关系图GFdep，根据模块节点nm的Export数据、External数据更新数据共享关系图GDdep，得到更新后的数据共享关系图GDdep；A3) Update the function call relationship graph G Fdep according to the in function and out function of the module node n m to obtain the updated function call relationship graph G Fdep , and update the data sharing relationship graph G Ddep according to the Export data and External data of the module node n m , obtain the updated data sharing relationship graph G Ddep ; A4)将更新后的函数调用关系图GFdep和更新后的数据共享关系图GDdep构成更新后的内核模块依赖关系图GM。A4) The updated function call relation graph G Fdep and the updated data sharing relation graph G Ddep are formed into an updated kernel module dependency relation graph G M . 6.根据权利要求5所述的基于哑模块节点的内核模块关系图构建方法，其特征在于，步骤A3)包括：将模块节点nm的in函数更新到模块节点集合{NM}的in函数表中，将模块节点nm的out函数更新到模块节点集合{NM}的out函数表中；建立模块节点nm的out函数与{NM}的in函数表中in函数符号对应关系，在图数据库中建立模块间的引用关系；如果模块节点nm的in函数在暂未发现节点中存在对应的out函数，为模块节点nm和暂未发现节点中out函数对应的内核模块建立引用关系；如果模块节点nm在in函数集存在未被匹配的in函数，则在图数据库中建立未被匹配的in函数对应的内核模块、暂未使用节点之间的引用关系，得到更新后的函数调用关系图GFdep；将模块节点nm的Export数据更新到模块节点集合{NM}的Export数据表中，将模块节点nm的External数据更新到模块节点集合{NM}的External数据表中；建立模块节点nm的External数据与{NM}的Export数据表中Export数据符号对应关系，在图数据库中建立模块间的引用关系；如果模块节点nm的Export数据在暂未发现节点中存在对应的External数据，为模块节点nm和暂未发现节点中External数据对应的内核模块建立引用关系；如果模块节点nm在Export数据集存在未被匹配的Export数据，则在图数据库中建立未被匹配的Export数据对应的内核模块、暂未使用节点之间的引用关系，得到更新后的数据共享关系图GDdep。6. The method for constructing a kernel module relationship diagram based on a dummy module node according to claim 5, wherein step A3) comprises: the in function of module node n m is updated to the in function of module node set {N M } In the table, update the out function of the module node n m to the out function table of the module node set {N M }; establish the correspondence between the out function of the module node n m and the in function symbol in the in function table of {N M }, Establish a reference relationship between modules in the graph database; if the in function of the module node n m has a corresponding out function in the node that has not yet been found, create a reference for the module node n m and the kernel module corresponding to the out function in the node that has not been found yet. relationship; if the module node n m has an unmatched in function in the in function set, establish a reference relationship between the kernel module corresponding to the unmatched in function and the temporarily unused node in the graph database, and get the updated Function call relationship graph G Fdep ; update the Export data of the module node n m to the Export data table of the module node set {N M }, and update the External data of the module node n m to the External data of the module node set {N M } In the table; establish the corresponding relationship between the External data of the module node n m and the Export data symbol in the Export data table of {N M }, and establish the reference relationship between the modules in the graph database; if the Export data of the module node n m has not been found yet There is corresponding External data in the node, and a reference relationship is established between the module node n m and the kernel module corresponding to the External data in the node that has not yet been found; if the module node n m has unmatched Export data in the Export data set, it will be stored in the graph database. Establish the reference relationship between the kernel modules corresponding to the unmatched Export data and the nodes that are not used for the time being, and obtain the updated data sharing relationship graph G Ddep . 7.根据权利要求2所述的基于哑模块节点的内核模块关系图构建方法，其特征在于，步骤4)之后还包括在删除内核模块时更新内核模块依赖关系图GM的步骤：7. the kernel module relation graph construction method based on dumb module node according to claim 2, is characterized in that, also comprises the step of updating kernel module dependency graph GM when deleting kernel module after step 4): B1)输入待删除的内核模块m，以及待更新的内核模块依赖关系图GM；B1) input the kernel module m to be deleted, and the kernel module dependency graph G M to be updated; B2)从待更新的内核模块依赖关系图GM的模块节点集合{NM}中删除内核模块m对应的模块节点nm；B2) delete the module node n m corresponding to the kernel module m from the module node set {N M } of the kernel module dependency graph GM to be updated; B3)根据模块节点nm的in函数、out函数更新函数调用关系图GFdep，得到更新后的函数调用关系图GFdep，根据模块节点nm的Export数据、External数据更新数据共享关系图GDdep，得到更新后的数据共享关系图GDdep；B3) Update the function call relationship graph G Fdep according to the in function and out function of the module node n m to obtain the updated function call relationship graph G Fdep , and update the data sharing relationship graph G Ddep according to the Export data and External data of the module node n m , obtain the updated data sharing relationship graph G Ddep ; B4)将更新后的函数调用关系图GFdep和更新后的数据共享关系图GDdep构成更新后的内核模块依赖关系图GM。B4) The updated function call relation graph G Fdep and the updated data sharing relation graph G Ddep are formed into an updated kernel module dependency relation graph G M . 8.根据权利要求7所述的基于哑模块节点的内核模块关系图构建方法，其特征在于，步骤B3)包括：将模块节点nm的in函数从模块节点集合{NM}的in函数表中移除，将模块节点nm的out函数从模块节点集合{NM}的out函数表中移除；针对暂未使用节点中对应模块节点nm包含的in函数，若该in函数未被使用，则直接将其从暂未使用节点中删除，否则针对使用该in函数的其他任意内核模块j，在图数据库中将内核模块j、模块节点nm之间的引用关系修改为内核模块j、暂未发现节点之间的引用关系，得到更新后的函数调用关系图GFdep；将模块节点nm的Export数据从模块节点集合{NM}的Export数据表中移除，将模块节点nm的External数据从模块节点集合{NM}的External数据表中移除；针对暂未使用节点中对应模块节点nm包含的Export数据，若该Export数据未被使用，则直接将其从暂未使用节点中删除，否则针对使用该Export数据的其他任意内核模块j，在图数据库中将内核模块j、模块节点nm之间的引用关系修改为内核模块j、暂未发现节点之间的引用关系，得到更新后的数据共享关系图GDdep。8. the method for constructing a kernel module relationship diagram based on a dummy module node according to claim 7, wherein step B3) comprises: by the in function of module node n m from the in function table of module node set {N M } Remove the out function of the module node n m from the out function table of the module node set {N M }; for the in function contained in the corresponding module node n m in the unused node, if the in function has not been used If it is used, it is directly deleted from the temporarily unused node, otherwise, for any other kernel module j that uses the in function, the reference relationship between kernel module j and module node n m in the graph database is modified to kernel module j , The reference relationship between the nodes has not been found, and the updated function call relationship graph G Fdep is obtained ; the Export data of the module node n m is removed from the Export data table of the module node set {N M }, and the module node n The External data of m is removed from the External data table of the module node set {N M }; for the Export data contained in the corresponding module node n m in the node that is not used for the time being, if the Export data is not used, it will be directly removed from the temporary data table. Delete from unused nodes, otherwise, for any other kernel module j that uses the Export data, modify the reference relationship between kernel module j and module node n m to kernel module j in the graph database, and no relationship between nodes has been found yet. Refer to the relationship to obtain the updated data sharing relationship graph G Ddep . 9.一种基于哑模块节点的内核模块关系图构建系统，包括相互连接的微处理器和存储器，其特征在于，所述微处理器被编程或配置以执行权利要求1～8中任意一项所述基于哑模块节点的内核模块关系图构建方法的步骤。9. A kernel module relation graph building system based on a dumb module node, comprising an interconnected microprocessor and a memory, wherein the microprocessor is programmed or configured to execute any one of claims 1 to 8 The steps of the method for constructing the kernel module relationship graph based on the dummy module node. 10.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质中存储有被编程或配置以执行权利要求1～8中任意一项所述基于哑模块节点的内核模块关系图构建方法的计算机程序。10. A computer-readable storage medium, wherein the computer-readable storage medium stores therein a relationship diagram of a kernel module that is programmed or configured to execute the dummy module node-based kernel module according to any one of claims 1 to 8. Computer programs for constructing methods.
CN202110281352.9A 2021-03-16 2021-03-16 Method, system and medium for constructing kernel module relation graph based on dummy module node Active CN113157979B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202110281352.9A CN113157979B (en) 2021-03-16 2021-03-16 Method, system and medium for constructing kernel module relation graph based on dummy module node

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202110281352.9A CN113157979B (en) 2021-03-16 2021-03-16 Method, system and medium for constructing kernel module relation graph based on dummy module node

Publications (2)

Publication Number Publication Date
CN113157979A true CN113157979A (en) 2021-07-23
CN113157979B CN113157979B (en) 2023-09-29

Family

ID=76887271

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202110281352.9A Active CN113157979B (en) 2021-03-16 2021-03-16 Method, system and medium for constructing kernel module relation graph based on dummy module node

Country Status (1)

Country Link
CN (1) CN113157979B (en)

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5581768A (en) * 1995-02-27 1996-12-03 Intel Corporation Method and apparatus for executing applications in place from write once/seldom memories
CN110659085A (en) * 2019-09-27 2020-01-07 泉州华中科技大学智能制造研究院 Method and device for overloading limited number of functions in Linux kernel module

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5581768A (en) * 1995-02-27 1996-12-03 Intel Corporation Method and apparatus for executing applications in place from write once/seldom memories
CN110659085A (en) * 2019-09-27 2020-01-07 泉州华中科技大学智能制造研究院 Method and device for overloading limited number of functions in Linux kernel module

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
高珑; 戴华东; 杨沙洲; 丁滟: "并行帧缓存设备:基于多核CPU的Xorg并行显示优化", 软件学报, vol. 31, no. 10, pages 3309 - 3320 *

Also Published As

Publication number Publication date
CN113157979B (en) 2023-09-29

Similar Documents

Publication Publication Date Title
JP6875557B2 (en) Methods and devices for writing service data to the blockchain system
CN106325933B (en) Batch data synchronous method and device
CN108319623B (en) A data redistribution method, device and database cluster
Łącki Improved deterministic algorithms for decremental reachability and strongly connected components
CN105955843B (en) A kind of method and apparatus for database recovery
WO2021047541A1 (en) Method and device for obtaining transaction dependency relationship in blockchain
CN110597912B (en) Block storage method and device
CN114020840A (en) A data processing method, device, server, storage medium and product
WO2017045491A1 (en) Method and system for upgrading sqlite3 embedded database
US10931749B2 (en) Efficient configuration combination selection in migration
CN107391033A (en) Data migration method and device, computing device, computer-readable storage medium
CN105718468A (en) Method and device for building ODS layer of data warehouse
CN107357691B (en) Method and device for processing mirror image file
EP2933739B1 (en) Database management method
WO2016177075A1 (en) Method of checking associative relationship of service data, device and readable storage medium utilizing same
CN111324373A (en) Method, device and computing device for uploading multiple engineering files to code warehouse
CN113157979A (en) Method, system and medium for constructing kernel module relational graph based on dummy module nodes
CN107643959A (en) Image file treating method and apparatus
CN108073584B (en) Data processing method and server
CN116010345A (en) Method, device and equipment for realizing table service scheme of flow batch integrated data lake
CN110309149B (en) Data table processing method and device, electronic equipment and storage medium
CN115481103A (en) Method, device, and computer-readable storage medium for database expansion and contraction
WO2016095491A1 (en) Equipment upgrading method and transport network equipment
CN105740095A (en) Method and apparatus for restoring factory settings
CN106933657B (en) Database deadlock processing method and device

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant