US-12619449-B1 - System and method for generating a compact unwinding table for reconstructing call stacks to monitor program optimization

Abstract

A system and method for generating a compact unwinding table for call stack unwinding is provided. The method includes extracting a plurality of instruction entries and an offset value for each of the plurality of instruction entries from at least one frame description entry (FDE), wherein each of the at least one FDE contains information for the plurality of instruction entries; selecting a subset of the extracted plurality of instruction entries, wherein the subset includes relevant instruction entries for unwinding; generating the compact unwinding table based on the subset to include the instruction entries and respective offset values; and storing the generated compact unwinding table with respect to a source binary file.

Inventors

• Guy Franco
• Omer Yair

Assignees

• R.C.Raven Cloud LTD

Dates

Publication Date

20260505

Application Date

20240308

Claims (20)

1. 1 . A method for generating a compact unwinding table for call stack unwinding, comprising: extracting a plurality of instruction entries and an offset value for each of the plurality of instruction entries from at least one frame description entry (FDE), wherein each of the at least one FDE contains information for the plurality of instruction entries; selecting a subset of the extracted plurality of instruction entries, wherein the subset includes relevant instruction entries for unwinding; generating the compact unwinding table based on the subset to include the instruction entries and respective offset values; and storing the generated compact unwinding table with respect to a source binary file.
2. 2 . The method of claim 1 , further comprising: parsing and executing the at least one FDE that encodes the plurality of instruction entries as a virtual machine.
3. 3 . The method of claim 1 , further comprising: sorting the relevant instruction entries in the subset based on the respective offset values.
4. 4 . The method of claim 1 , wherein the generated compact unwinding table is associated with an index node (i-node) value that is unique to the source binary file.
5. 5 . The method of claim 1 , wherein the compact unwinding table is stored in a cache memory.
6. 6 . The method of claim 1 , wherein the plurality of instruction entries contains information to modify at least one register address.
7. 7 . The method of claim 6 , wherein the at least one register address is any one of: an instruction pointer (IP), a stack pointer (SP), and a base stack pointer (BSP).
8. 8 . The method of claim 1 , further comprising: identifying a binary for a current context received from a performance counter; retrieving the generated compact unwinding table of the source binary file by searching for the identified binary; and reconstructing an unwound call stack from the current context and the retrieved compact unwinding table of the source binary file.
9. 9 . The method of claim 8 , further comprising: matching a first address of the current context to a first instruction entry of the instruction entries in the compact unwinding table; and determining a second address by modifying at least one register address of the current context according to information in the first instruction entry.
10. 10 . The method of claim 1 , wherein the method is performed at a user mode of an operating system of a server.
11. 11 . A non-transitory computer readable medium having stored thereon instructions for causing a processing circuitry to execute a process, the process comprising: extracting a plurality of instruction entries and an offset value for each of the plurality of instruction entries from at least one frame description entry (FDE), wherein each of the at least one FDE contains information for the plurality of instruction entries; selecting a subset of the extracted plurality of instruction entries, wherein the subset includes relevant instruction entries for unwinding; generating a compact unwinding table based on the subset to include the instruction entries and respective offset values; and storing the generated compact unwinding table with respect to a source binary file.
12. 12 . A system for generating a compact unwinding table for call stack unwinding, comprising: a processing circuitry; and a memory, the memory containing instructions that, when executed by the processing circuitry, configure the system to: extract a plurality of instruction entries and an offset value for each of the plurality of instruction entries from at least one frame description entry (FDE), wherein each of the at least one FDE contains information for the plurality of instruction entries; select a subset of the extracted plurality of instruction entries, wherein the subset includes relevant instruction entries for unwinding; generate the compact unwinding table based on the subset to include the instruction entries and respective offset values; and store the generated compact unwinding table with respect to a source binary file.
13. 13 . The system of claim 12 , wherein the system is further configured to: parse and execute the at least one FDE that encodes the plurality of instruction entries as a virtual machine.
14. 14 . The system of claim 12 , wherein the system is further configured to: sort the relevant instruction entries in the subset based on the respective offset values.
15. 15 . The system of claim 12 , wherein the generated compact unwinding table is associated with an index node (i-node) value that is unique to the source binary file.
16. 16 . The system of claim 12 , wherein the compact unwinding table is stored in a cache memory.
17. 17 . The system of claim 12 , wherein the plurality of instruction entries contains information to modify at least one register address.
18. 18 . The system of claim 17 , wherein the at least one register address is any one of: an instruction pointer (IP), a stack pointer (SP), and a base stack pointer (BSP).
19. 19 . The system of claim 12 , wherein the system is further configured to: identify a binary for a current context received from a performance counter; retrieve the generated compact unwinding table of the source binary file by searching for the identified binary; and reconstruct an unwound call stack from the current context and the retrieved compact unwinding table of the source binary file.
20. 20 . The system of claim 19 , wherein the system is further configured to: match a first address of the current context to a first instruction entry of the instruction entries in the compact unwinding table; and determine a second address by modifying at least one register address of the current context according to information in the first instruction entry.

Description

TECHNICAL FIELD The present disclosure relates generally to computer processing, and in particular, to systems and methods for unwinding call stacks to monitor program optimization. BACKGROUND Cloud computing refers to the delivery of various services over the Internet. These services include storage, databases, servers, networking, software, analytics, intelligence, and more. Cloud computing offers faster innovation, flexible resources, and economies of scale. Infrastructure as a Service (IaaS) is the most basic category of cloud computing services. With IaaS, the IT infrastructure—servers and virtual machines, storage, networks, and operating systems—are rented on a pay-as-you-go basis. Cloud resources cost refers to the expenses associated with using various services and infrastructure provided by cloud computing vendors. These costs can vary significantly based on numerous factors. Such factors include the type of resource, the usage of the resource, a region where the resource is deployed, and so on. The cost of cloud resources is a significant expense of companies providing SaaS over cloud infrastructure. Traditional ways to reduce costs include, for example, and without limitation, using saving plans, changing resource types to reserve from on-demand instances, and the like, and more, as some providers offer options to reserve instances for a longer-term, often at a reduced rate compared to on-demand pricing. Other approaches for reducing costs include resizing an instance (e.g., reducing the compute power or memory of an instance). Yet another approach for reducing is a spot instance. A spot instance in cloud computing refers to a temporary, on-demand computing capacity that can be obtained at a significant discount compared to regular on-demand instances. Spot instances allow you to use spare computing capacity in a cloud provider's data center. Though such techniques may offer some savings, these do not address the core problems of close compute power, which include the bottleneck in the execution of software. For example, an unoptimized piece of code may consume unnecessary computing power, thereby increasing the utilization of instances of cloud resources, which, in return, increases the overall cost. To this end, methods to optimize the bottlenecks in the workload (e.g., application, service, tasks, etc.) are desired for efficient processing, use of resources, and budget management. Currently implemented methods to detect program optimizations and/or resource utilizations involve monitoring the execution of workloads through profiling such as, but not limited to continuous profiling, sample-based profiling, and the like. Profiling tracks the amount of time, power, memory, and the like, that are spent on the execution of workloads and their sub-components (e.g., function calls, call stacks, etc.) which are advantageous in diagnosing program and resource efficiency. To this end, methods to monitor and analyze performance at low overload without additional computational load are desired. Unwinding of call stacks to backtrace and reconstruct call stacks may be performed to monitor the performance of workloads. It has been identified as a processor intensive process and remains a challenge for efficient and accurate diagnosis of program optimizations. It would therefore be advantageous to provide a solution that would overcome the challenges noted above. SUMMARY A summary of several example embodiments of the disclosure follows. This summary is provided for the convenience of the reader to provide a basic understanding of such embodiments and does not wholly define the breadth of the disclosure. This summary is not an extensive overview of all contemplated embodiments, and is intended to neither identify key or critical elements of all embodiments nor to delineate the scope of any or all aspects. Its sole purpose is to present some concepts of one or more embodiments in a simplified form as a prelude to the more detailed description that is presented later. For convenience, the term “some embodiments” or “certain embodiments” may be used herein to refer to a single embodiment or multiple embodiments of the disclosure. Certain embodiments disclosed herein include a method for generating a compact unwinding table for call stack unwinding. The method comprises: extracting a plurality of instruction entries and an offset value for each of the plurality of instruction entries from at least one frame description entry (FDE), wherein each of the at least one FDE contains information for the plurality of instruction entries; selecting a subset of the extracted plurality of instruction entries, wherein the subset includes relevant instruction entries for unwinding; generating the compact unwinding table based on the subset to include the instruction entries and respective offset values; and storing the generated compact unwinding table with respect to a source binary file. Certain embodiments disclosed herei