Precise Calling Context Encoding
- Authors
- Nick Sumner
- Yunhui Zheng
- Dasarath Weeratunge
- Xiangyu Zhang
- Abstract
- Calling contexts are very important for a wide range of applications such as
profiling, debugging, and event logging. Most applications perform expensive
stack walking to recover contexts. The resulting contexts are often
explicitly represented as a sequence of call sites and hence bulky.
We propose a technique to encode the current calling context of any point
during an execution. In particular, an acyclic call path is
encoded into one number through only integer additions. Recursive call
paths are divided into acyclic subsequences and encoded independently.
We leverage stack depth in a safe way to optimize encoding: if a calling
context can be safely and uniquely identified by its stack depth, we do not perform
encoding. We propose an algorithm to seamlessly fuse encoding and stack
depth based identification. The algorithm is safe because different contexts
are guaranteed to have different IDs. It also ensures contexts can be
faithfully decoded. Our experiments show that our technique
incurs negligible overhead (1.89% on average). For most medium-sized programs,
it can encode all contexts with just one number. For large programs, we are
able to encode most calling contexts to a few numbers.
- Available code
- Module for CIL
- External resources:
- CIL