# Log20

### research question

Prior work mostly focused on automating what to log so as to improve the quality of exising log printing statements. However, where to place an LPS, which is a more fundamental and challenging problem, has not been adequately addressed. The only prior work on placing IPSes was Errlog that automatically places error LPSes at locations where error conditions may occur. So the difficulty is to know which program locations are more "log-worthy" than others.

### proposed approach

This paper proposed Log20, a tool that automates LPS placement without requiring any domain knowledge. Users can simply specify a performance overhead threshold, and Log20 is capable of computing a near optimal placement of LPSes whose overhead is within the specified threshold.

One fundamental difference between Log20 and other existing logging approaches is that Log20's placement is not static, but instead reacts to the workload.

### definition

**informativeness of a particular LPS placement:**
To measure its ability to differentiate between different execution paths

BB: a sets of basic blocks, BB = {bb1, bb2, ..., bbn}
EP: the set of all possible execution paths of a program, EP = {P1, P2, ..., Pm}
LPS placement - S: a subset of BB where a unique LPS is placed in each block.

Entropy of LPS Placement

The informativeness of an LPS placement.

### implementation

Computing the optimal placement using a brute force search requires enumerating every combination of basic blocks, and then selecting the one that offers the lowest entropy with a total weight that is under the threshold. The complexity of this brute force algorithm is 2N , where N is the number of basic blocks. Log20 solves this combinatorial optimization problem using a dynamic programming algorithm that approximates the optimal solution.

Log20 solves this combinatorial optimization problem us- ing a dynamic programming algorithm that approximates the optimal solution. Given all basic blocks, [bb1, bb2, .., bbN ], the algorithm first sorts them by their weights such that wi ≤wi+1,wherewi is the weight of bbi.Let S(i−1,w) be a near optimal placement of LPSes in [bb1,bb2, ..,bbi−1] within a total weight of w.For each basic block in[bbi,bbi+1,..,bbN],the algorithm adds it to the current placement, S(i − 1,w), if and only if it reduces the entropy of S(i − 1,w) while respecting the weight threshold. Formally,


### contribution

* An algorithm for placing LPSes that is near optimal
* A metric on the informativeness of LPS placement
* A low-overhead run-time tracing system which can be used for both continuous profiling and the logging library

### strength

*

### limitations

* First, Log20 does not assign a scalar verbosity level to each LPS.
* Second, Log20's placement algorithm treats each path as an unordered rather than ordered collection of basic blocks. (read after write vs write after read, they are totally different)
* The coverage of the trace is not exhaustive. Some functions or basic blocks will not be exercised by the workload, so they are excluded from LPS placement consideration.
* A change of workload can result in undesirable logging behavior because Log20's placement is optimized towards the old workload.
* Log20 is designed to work independently from developers' manual LPS placement. Log20 cannot learn from the logging patterns in existing LPSes and apply them to place LPSes on unlogged paths.

###