Method and Apparatus for Logical Stack Activity Profiling
Publication Date: 2011-Sep-06
The IP.com Prior Art Database
In a complex system such as a database management system, users interacting with that system put faith in it, that it is 'spending it time' in efficient and productive ways. When the timescale of interaction with the system goes beyond a few tens of seconds, the system should be able to account for where it spends its time on behalf of the user. Is time being spent on calculation, or I/O, or synchronization, or elsewhere? This knowledge greatly benefits the user, enabling them to have a better understanding of where resources (esp. time) are being consumed, and how those resources might be redistributed by tuning the system or otherwise adjusting the workload. This goes beyond a 'nice-to-have' feature, and respresents a critical tool in extracting maximum value from an IT investment. One current partial solution is the use of timestamps. These are captured at regular intervals during execution of the program, to record when certain parts of the code were executed. In aggregate, they provide an idea of where time is spent, however this introduces a significant and generally unacceptable overhead, particularly if the timestamps are take frequently enough to provide a good picture of overall execution. Another current solution is the use of statistical profiling, by tools such as tprof, oprofile, and Solaris Workshop. This involves periodic sampling of the Program Counter (PC), which indicates what particular machine instruction is being executed at any given instant. By taking such samples fairly frequently (e.g. 100 to 1000 times per second), and using them to construct a histogram of samples per each area of interest (e.g. per function), a profile of activity is built up. The first main problem with this approach is that deciphering the execution profile requires intimate knowledge of the program being profiled. Source code and/or deep knowledge of the internals of the system is not generally available to users, so the profile data is not helpful to many. An additional shortcoming is that for some important classes of program functionality, such as I/O and interprocess synchronization, it is as important to know the circumstances (call path) by which the program arrived at its current location, as it is to know the current location itself. A lesser-known variant which solves some of the problems of statistical profiling is the collection & aggregation of stack tracebacks. This involves the use of an instantaneous processor stack traceback, collected by the execution thread itself, which reports not only the current location of execution, but the various function calls that were made in order to arrive at that current location. Similar to statistical profiling, by considering a large number of stack tracebacks, we can develop an overall impression of where time is being spent. In practice, this method can destabilize an executing system, in the event that the stack traceback code is not perfect, or that the request to take a traceback occurs at an inopportune instant (for example, during a system call or other signal handling code.) Note that this approach generally imposes a larger overhead than even timestamp collection, and is platform dependent.
Page 01 of 4
Method and Apparatus for Logical Stack Activity Profiling
The direct goal of this invention is to show where time is being spent in a system. Indirect goals include bottleneck detection, and prediction of system growth and resource consumption.
Base requirements for this mechanism are: ability to identify where time is being spent; low overhead; user-consumability, portability,
Key functions within the system are instrumented to record entry and exit, by pushing an identifier onto a logical stack (on entry) and by popping it off again (on exit). Each stack frame pushed/popped also contains an optional parameter to provide context for the call. Relatively few functions will be instrumented, in order to minimize overhead and help ensure the stack can be understood by end users. A typical depth of 5 to 10 frames might be typical within a single stream of execution.
When logical stack profiling is enabled, each thread of execution being profiled maintains its own stack as described. This eliminates the complexity and overhead of concurrnency control on a single shared structure. The stack is located in shared memory to allow access by a profiling thread (see below)
During execution, entry and exit from instrumented function(s) by the execution thread will result in entries constantly being pushed onto and popped off its logical stack. These will generally go unrecorded in any other way. One or more separate threads of execution (profiling threads) are created when profiling is enabled. Each profiling thread registers an alarm signal. This alarm fires periodically, perhaps as frequently as 10 or more times per second, and perhaps only once per second. The rate would be configurable. When the alarm signal is received, the profiling thread takes a copy of the execution thread's logical stack. This can either be used as an instantaeous value (a single sample), or merged with other samples to form an activity profile.
Merging of a sample stack with the existing activity profile occurs from the bottom up. The sample stack consists of stack frames. The activity profile conisists of one or more trees of stack frames.
1. start at the bottom of the stack sample and the bottom of the current merged stack profile
2. WHILE the current frame from the sample stack and the frame from the stack profile at the same depth are the same
- Move the pointer / iterator to the next frame up in both the stack sample and in the stack profile
3. Copy the remaining stack frames from the sample stack (if any) into the stack profile, forming a new branch anchored at the current frame in the profile stack.
If no frames from the sample stack match with any frames in the stack profile, the sample
becomes a new disjoint tree in the stack profile.
4. Increment the count in the stack profile frame matching the top-most frame of the sample stack. This count is
the number of samples collected where the program counter was within the scope of the code represented by that