* [10] Danny Calegari.  Stable commutator length is rational in free groups.  Jour. Amer. Math. Soc., 22(4):941–961, 2009.
  * [11] Danny Calegari and Alden Walker.  scallop.  Available at https://github.com/aldenwalker/scallop.
  * [12] Christopher H. Cashen.  Splitting line patterns in free groups.  Algebr. Geom. Topol., 16(2):621–673, 2016.
  * [13] Bruce Chandler and Wilhelm Magnus.  The history of combinatorial group theory, volume 9 of Studies in the History of Mathematics and Physical Sciences.  Springer-Verlag, New York, 1982.  A case study in the history of ideas.
  * [14] Ian M. Chiswell, Donald J. Collins, and Johannes Huebschmann.  Aspherical group presentations.  Math. Z., 178(1):1–36, 1981.
  * [15] W. H. Cockcroft.  On two-dimensional aspherical complexes.  Proc. London Math. Soc. (3), 4:375–384, 1954.
  * [16] Marc Culler.  Using surfaces to solve equations in free groups.  Topology, 20(2):133–145, 1981.
  * [17] Andrew J. Duncan and James Howie.  The genus problem for one-relator products of locally indicable groups.  Math. Z., 208(2):225–237, 1991.
  * [18] S. M. Gersten.  Dehn functions and $l_{1}$-norms of finite presentations.  In Algorithms and classification in combinatorial group theory (Berkeley, CA, 1989), volume 23 of Math. Sci. Res. Inst. Publ., pages 195–224. Springer, New York, 1992.
  * [19] Cameron Gordon and Henry Wilton.  On surface subgroups of doubles of free groups.  Jour. London Math. Soc., 82(1):17–31, 2010.
  * [20] M. Gromov.  Asymptotic invariants of infinite groups.  In Geometric group theory, Vol.\ 2 (Sussex, 1991), volume 182 of London Math. Soc. Lecture Note Ser., pages 1–295. Cambridge Univ. Press, Cambridge, 1993.
  * [21] Joseph Helfer and Daniel T. Wise.  Counting cycles in labeled graphs: the nonpositive immersion property for one-relator groups.  Int. Math. Res. Not. IMRN, 9:2813–2827, 2016.
  * [22] James Howie.  On pairs of $2$-complexes and systems of equations over groups.  J. Reine Angew. Math., 324:165–174, 1981.
  * [23] James Howie.  On locally indicable groups.  Math. Z., 180(4):445–461, 1982.
  * [24] Giovanni Italiano, Bruno Martelli, and Matteo Migliorini.  Hyperbolic 5-manifolds that fiber over ${S}^{1}$.  Inventiones Mathematicae, to appear.
  * [25] Marshall Hall Jr.  Subgroups of finite index in free groups.  Canadian Journal of Mathematics, 1:187–190, 1949.
  * [26] Marco Linton.  One-relator hierarchies.  arXiv:2202.11324, 2022.
  * [27] Larsen Louder and Henry Wilton.  Stackings and the $W$-cycles conjecture.  Canad. Math. Bull., 60(3):604–612, 2017.
  * [28] Larsen Louder and Henry Wilton.  One-relator groups with torsion are coherent.  Math. Res. Lett., 27(5):1499–1512, 2020.
  * [29] Larsen Louder and Henry Wilton.  Uniform negative immersions and the coherence of one-relator groups.  arXiv:2107.08911, 2021.
  * [30] Larsen Louder and Henry Wilton.  Negative immersions for one-relator groups.  Duke Math. J., 171(3):547–594, 2022.
  * [31] Roger C. Lyndon.  Cohomology theory of groups with a single defining relation.  Annals of Mathematics. Second Series, 52:650–665, 1950.
  * [32] Roger C. Lyndon and Paul E. Schupp.  Combinatorial group theory.  Springer-Verlag, Berlin, 1977.  Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89.
  * [33] W. Magnus.  Das Identitätsproblem für Gruppen mit einer definierenden Relation.  Math. Ann., 106(1):295–307, 1932.
  * [34] Jason Fox Manning.  Virtually geometric words and Whitehead’s algorithm.  Math. Res. Lett., 17(5):917–925, 2010.
  * [35] Charles F. Miller, III and Paul E. Schupp.  Some presentations of the trivial group.  In Groups, languages and geometry (South Hadley, MA, 1998), volume 250 of Contemp. Math., pages 113–115. Amer. Math. Soc., Providence, RI, 1999.
  * [36] B. B. Newman.  Some results on one-relator groups.  Bull. Amer. Math. Soc., 74:568–571, 1968.
  * [37] Yann Ollivier.  Some small cancellation properties of random groups.  Internat. J. Algebra Comput., 17(1):37–51, 2007.
  * [38] Luisa Paoluzzi and Bruno Zimmermann.  On a class of hyperbolic $3$-manifolds and groups with one defining relation.  Geom. Dedicata, 60(2):113–123, 1996.
  * [39] C. D. Papakyriakopoulos.  On Dehn’s lemma and the asphericity of knots.  Ann. of Math. (2), 66:1–26, 1957.
  * [40] Doron Puder.  Primitive words, free factors and measure preservation.  Israel J. Math., 201(1):25–73, 2014.
  * [41] Doron Puder and Ori Parzanchevski.  Measure preserving words are primitive.  J. Amer. Math. Soc., 28(1):63–97, 2015.
  * [42] G. P. Scott.  Finitely generated 3-manifold groups are finitely presented.  Journal of the London Mathematical Society. Second Series, 6:437–440, 1973.
  * [43] John Stallings.  Homology and central series of groups.  J. Algebra, 2:170–181, 1965.
  * [44] John R. Stallings.  Topology of finite graphs.  Inventiones Mathematicae, 71(3):551–565, 1983.
  * [45] William P. Thurston.  The geometry and topology of 3-manifolds.  Mimeographed lecture notes, 1979.
  * [46] J. H. C. Whitehead.  On equivalent sets of elements in a free group.  Ann. of Math. (2), 37(4):782–800, 1936.
  * [47] Henry Wilton.  One-ended subgroups of graphs of free groups.  Geom. Topol., 16:665–683, 2012.
  * [48] Henry Wilton.  Essential surfaces in graph pairs.  J. Amer. Math. Soc., 31(4):893–919, 2018.
  * [49] Henry Wilton.  Rationality theorems for curvature invariants of 2-complexes.  arXiv:2210.09841, 2022.
  * [50] Daniel T. Wise.  Nonpositive immersions, sectional curvature, and subgroup properties.  Electronic Research Announcements of the American Mathematical Society, 9:1—9, 2003.
  * [51] Daniel T. Wise.  Sectional curvature, compact cores, and local quasiconvexity.  Geom. Funct. Anal., 14(2):433–468, 2004.
  * [52] Daniel T. Wise.  An invitation to coherent groups.  In What’s next?—the mathematical legacy of William P. Thurston, volume 205 of Ann. of Math. Stud., pages 326–414. Princeton Univ. Press, Princeton, NJ, 2020.
  * [53] Daniel T. Wise.  Coherence, local indicability and nonpositive immersions.  J. Inst. Math. Jussieu, 21(2):659–674, 2022.

DPMMS, Centre for Mathematical Sciences, Wilberforce Road, Cambridge, CB3 0WB,
UK

E-mail address<EMAIL_ADDRESS>


# Towards a debuggable kernel design

Ashish Gupta, Chandrika Parimoo<EMAIL_ADDRESS>
###### Abstract

This paper describes what it means for a kernel to be debuggable and proposes
a kernel design with debuggability in mind. We evaluate the proposed kernel
design by comparing the iterations required in cyclic debugging for different
classes of bugs in a vanilla monolithic kernel to a variant enhanced with our
design rules for debuggability. We discuss the trade offs involved in
designing a debuggable kernel.

##  I INTRODUCTION

Operating system kernels generally consist of several subsystems that handle
memory management, process management, process scheduling, network, I/O and
peripheral devices. The interactions between and within different parts of the
kernel are asynchronous. The size of the kernel and the inherent asynchronous
concurrent model of programming makes the implementation of a robust kernel
challenging. When bugs arise, isolating and reproducing them is generally
harder than userspace programs due to the mentioned properties of a kernel.
Kernel development and debugging is arcane[1], therefore creating a high
barrier of entry for new kernel developers. Debugging is one of the most
costly phases in software development. Developers spend over 30% of their time
debugging and validating software[2]. The cost of debugging rises up as one
moves to lower layers of the software stack because of the increasing amounts
of guarantees provided to the layers above. Debugging as an early design
consideration can help make the process shorter, alleviating costs.

Kernel debugging has conventionally proceeded through the use of tools which
stand at various levels of maturity, but never from the perspective of the
kernel’s design itself. We define ”debuggability” as the kernel’s inherent
ability to lend itself to debugging. We argue that the kernel knows best about
itself and can be designed to provide well structured and relevant information
about the deviation in its behavior and make the process of debugging the
kernel (itself) more efficient. Debuggability can thus be considered an
intrinsic property of the kernel and taken into account during the design of
the kernel instead of being an afterthought.

##  II RELATED WORK

Existing debugging approaches include tracing and probing with the use of
tools such as DTrace[3] which allow live patching of instructions with
instrumentation code in order to get more information about instructions being
executed. This can be a useful technique for debugging, but only captures the
execution trace (where overhead can be as large as 100x for high frequency
function calls[4]). Our approach exposes the kernel’s high level information
to the developer in the form of data structures that the developer understands
instead of only relying on the execution stream and function arguments.

Kernel developers use forms of remote debugging (over a serial line)[5]. While
this technique has been an effective way for kernel debugging, it requires the
possession of an additional machine to run a master kernel on one machine
sending commands to the debugee kernel on another machine. We do away with the
requirement for additional hardware for debugging by incorporating the ability
for a kernel to help debug itself.

Hardware based approaches such as JTAG[6] are very powerful expose a lot of
detail about the execution with the help of a special controller. Although one
can get a large amount of information , the information provided can be too
low-level to be useful for debugging kernel design issues. Our approach, on
the other hand, focuses on the kernel’s high level structures providing means
to infer some low-level information as well.

Hypervisor based record and replay approaches such as Samsara[7] offer an
excellent way to tackle hard to reproduce bugs through the use of virtual
machines and hypervisors. Although effective, they inherently lack performance
as the use of virtual machines and hypervisors slows down performance (upto 6x
on a 4-core machine) limiting their usefulness. In our approach, we wish to
get rid of the overhead imposed by the use of virtual machines and exploit the
hardware the kernel runs on directly to provide a record-and-replay feature as
a part of d-mode.

Diagnosys[8] allows the automatic generation of debugging interfaces by
statically analyzing the kernel code for safety holes. This allows Diagnosys
to generate relevant logs at run time which help in debugging. The approach is
restricted to the identified safety holes and Diagnosys is added as a module
to the Linux kernel rather than being integrated in the design of the kernel.

The work on exposing bugs before having to debug them provides good examples
of the kind of bugs most likely to be found in a kernel. Landslide[9], in its
approach of systematic exploration of concurrency bugs provides insights into
which bugs frequently occur in the kernels created at CMU which follow the
Pebbles kernel specification. Since we modify Pebbles[10] to prototype our
kernel design, we found Landslide to be useful in guiding our attempts to
craft scenarios to reason about the design rules of a debuggable kernel.

Our approach differs from conventional tools in the sense that we want to make
the kernel a more active participant in the debugging activities of a
developer as the kernel has access to all of the information within itself and
can be presented in the right way to a developer which can be used to create a
mental model of the cause of the issue without the need to actually analyse
memory and step-wise debug.

##  III DEBUGGABLE KERNEL

###  III-A Debuggability

Cyclic debugging is the iterative process of narrowing down the reason for
program failure. In each iteration, the programmer gathers more information,
adding to the knowledge gained from previous debug iterations, finally zeroing
in on the root cause of the bug[11]. Fig 1 outlines the phases typically
involved in the process of isolating and fixing a bug. The investigation phase
is where most of the developer effort and time is spent. Within the kernel,
the investigation phase involves isolating the subsystem (the source of the
bug) and isolating relevant context about the subsystem in order to find the
root cause of the bug. This typically involves several iterations in cyclic
debugging as different aspects of the behavior must be logged and analyzed
before branching to investigating any callee functions. The process increases
in time and complexity when the bug’s source is the non-deterministic
execution within the kernel as it becomes much harder to reproduce, and
therefore isolate.

Figure 1: Phases of debugging

We define the debuggability of the kernel for a specific bug as the number of
iterations it took to find the root cause of the bug using cyclic debugging.
As each iteration of the debugging process involves recompiling and re-
executing the kernel, a higher number of iterations makes the ordeal of
debugging more expensive thus decreasing the debuggability of a kernel.

###  III-B Debuggability Scenarios

To motivate the design for our kernel, we came up with some common bugs that
can creep up during kernel development. These bugs are representative of some
of the classes of bugs encountered during kernel development. This allows us
to focus on one class of bugs at a time, and suggest features in a kernel’s
design to combat those issues. We use the experience gained through the
process of debugging these issues to come up with ”debuggability rules”. We
claim that a kernel designed with these rules in mind is more debuggable.

####  III-B1 Memory Exhaustion

In Listing 1, child processes are forked and the expectation from the program
is to print the message ”Another one bites the dust” endlessly, potentially
with a few ”Fork failed” messages. We introduce a bug in the kernel’s wait()
syscall implementation by removing free for the PCB of the waited for process
leading to a memory leak. This results in memory exhaustion which is evident
from the program’s behavior: It initially prints ”Another one bites the dust”
several times, but soon after only prints ”Fork failed”. While debugging we
felt the need for a global view of kernel data structures in memory, access to
which would have led us straight to the process subsystem. Since wait() is
responsible for cleaning up the exited children, there must be an issue in the
implementation of wait(). This led us to the first rule.

Debuggability Rule 1: A kernel which provides visibility into its data
structures and resource usage improves its debuggability. Ability to provide a
debugging interface under memory exhaustion increases debuggability as
otherwise it is hard to debug the kernel in such situations.

Listing 1: Fork bomb

⬇

// wait endlessly to reap exiting children

void reaper(void) {

while(1) {

wait(NULL);

}

}

// fork endlessly

void bomberman(void) {

while(1) {

pid_t pid = fork();

if(pid == 0) {

printf(“Another one bites the dust\n”);

exit(0);

} else if(pid == -1) {

printf(“Fork failed\n”);

}

}

}

// Spawn two threads, one doing all the fork()ing and

// the other doing all the wait()ing

int main() {

int tid = thr_fork();

if(tid == 0) {

bomberman();

}

else {

reaper();

}

}

####  III-B2 Use After Free

In Listing 2, a thread maps pages into its process address space and tries to
make the kernel copy file data into these pages using the readfile syscall.
Another thread unmaps the same pages in a loop to occasionally cause readfile
to fail and print the message ”Failed to read file” and occasionally
”Someone’s acing the exam”. The kernel should ideally check the virtual memory
mappings of user supplied pages in its readfile() implementation. We introduce
a bug by removing any such validation and one of the inter leavings on the run
results in readfile() trying to write file data into an unmapped memory
address causing the kernel to page fault, resulting in a kernel panic. In an
attempt to debug this, we enabled the logging of all VM operations which would
help us track this issue down. Once we had the logs, it was difficult to make
sense of them and we had to use external tools to process the logs into a
readable format, keeping the value of cr2 handy. We wondered if the kernel
itself could carry out all these steps, freeing us of the overhead of making
sense of this data. Based on this experience, we invented another rule.

Debuggability Rule 2: Keep history of the actions performed by a subsystem
along with the identifying information about the requesting process / thread.
This history should be available for navigation by a user in the event of a
kernel panic.

Listing 2: Pulling the rug from under the kernel’s feet

⬇

\label{lst:UAF}

void remove(void *addr) {

// continuously remove pages to

// create many possible inter-leavings

while(1) {

remove_pages(addr);

}

}

int main() {

void *addr = 0x13370000;

int size = 4096;

pid_t tid = thread_fork();

// newly spawned thread should do

// remove_pages endlessly

if(tid == 0) {

remove();

}

while(1) {

int failed = new_pages(addr, size);

if(failed)

continue;

// send buffer to kernel to read

// in contents of a file

int code = readfile(”exam_solution.txt”,

addr, size, 0);

if(code < 0) {

printf“Failed to read file\n”);

}

else {

printf(“Someone‘s acing the exam!\n”);

}

}

####  III-B3 Non determinism

Bugs that surface due to asynchronous interactions between kernel components
are the hardest to tackle. In Listing 3, a process’ thread invokes the yield()
syscall to yield the CPU to a different thread. We analyse an interleaving
where the timer fires when the kernel is processing the yield() request: the
kernel has obtained the caller’s TCB but the timer interrupt handling results
in the other thread of same process being scheduled. The other thread exits
deleting its TCB, while the kernel returns execution to the original
invocation of the yield syscall and continues the process of switching to the
thread would be to find the exact interleaving of events that causes the
issue. As logging alone seems ineffective at tackling such bugs, it seemed
crucial that there be a mechanism in the kernel which did most of the heavy
lifting required for investigation. This led us to the final rule.

Debuggability Rule 3: A kernel which allows a replay mechanism which performs
operations exactly in the order as they happened in the original run has
higher debuggability than a kernel which does not. A mechanism must exist that
can reliably reproduce a bug for investigation even if the initial cause of
the bug was non deterministic inter leavings in the kernel’s execution.

Listing 3: Dead Yield

⬇

// Code running in userspace

int main {

int tid = thread_fork();

if(tid == 0) {

// This is thread 0

vanish();

}

else {

// This is thread 1

int failed = yield(pid);

if(failed)

printf(“Yielding failed\n”);

}

}

// Code in kernel space

// Implementation of vanish system call

// Called by thread 0 from above

void vanish_impl(void) {

pcb_t *my_pcb = find_pcb_by_tid(gettid());

remove_from_lists(pcb);

unmap_destroy_process(pcb);

run_some_other_thread();

}

// Implementation of yield system call

int yield_impl(int tid) {

pcb_t *target_pcb = find_pcb_by_tid(tid);

// —–> Timer interrupt fired here

// do the context switch to target_pcb

stack_switch(target_pcb);

pop_gp_registers();

return_to_user_mode();

}

###  III-C Design and Implementation

Based on the experiences gathered by analyzing the debugging process of the
bugs described in the previous section, we designed an extension ”d-mode” to
the Pebbles[10] kernel, the combination of which we call ”dPebbles”. d-mode
lives within the kernel and records various pieces of information during the
run of the kernel so that it can present this information later to a developer
for debugging. We now describe different components of d-mode which work
together to provide the full debugging experience. d-mode currently runs on
x86 hardware, and therefore some design is dependent on features of the x86
hardware. These features are commonly found on most architectures and d-mode
can be easily ported to other architectures as a result.

####  III-C1 debugMode

When the kernel panics, or a special key combination is pressed, d-mode
presents itself interactively to the user in a familiar shell which serves as
a single point of control. The shell accepts various commands, and lists out
the information the user asks for. A stack switch is performed to d-mode’s own
stack to not have stack overflows or overwrite data on another process’ stack.

####  III-C2 Kernel data Structures

d-mode augments the allocation routines of a kernel (through the use of a
wrapper) and maintains a count for the number of data structure objects
allocated. Only the number of allocated objects needs to be tracked as it can
be converted to the actual number of bytes in use by multiplying with the size
of the relevant object type. This information serves as an overview of the
entire system and can help guide development efforts into the right kernel
subsystem. More complex views around this theme can be developed for more fine
grained view into the kernel’s memory usage.

####  III-C3 Virtual Memory operations

Kernel panics often result from accessing unmapped memory regions in a
process’ address space while in kernel mode (Page fault in kernel mode).
d-mode deals with these by facilitating viewing past interactions between a
process and the VM subsystem. Each function of the Pebbles VM subsystem was
augmented by the addition of a function call which records the type of VM
operation being performed along with the calling process / thread identifiers
and the address being modified. This information is maintained within d-mode
and can be viewed by the user when the kernel panics due to a page fault. As
d-mode is currently based on x86 systems, the cr2 control register (which
contains the address whose access resulted in a page fault) is also shown to
the user to have higher debuggability. We use the following format for
maintaining VM operations:

⟨ pid, tid, VM operation ID, Virtual Address ⟩

####  III-C4 Safety

When a kernel is buggy, all bets are off as it can overwrite critical data
structures (for example by writing data to wild pointers). In order to ensure
that a user can still access d-mode, it is imperative to have a reserved
memory area that remains safe for use even when the kernel can no longer be
trusted. The history of VM operations, as well as the counters for data
structures remain resident in this safe area. It must also be ensured that
d-mode has enough working area apart from the storage space in order to
perform its own functions. As a result, d-mode has a reserved space for using
as a stack area. The stack pointer (ESP) is switched whenever entries and
exits occur to d-mode’s own stack. It must also be possible for a user to
quickly identify if certain data structures have been corrupted. d-mode
ensures this through the use of contract validators where it can use kernel
exported interfaces to ensure (on a best effort basis) that data structures
are intact.

####  III-C5 Non Determinism

Please note that the current implementation does not contain this record-and-
replay module. We still present the design here for completeness. A kernel
being highly concurrent through the occurence of interrupts and interactions
with the userspace (via syscalls) results in a class of bugs which are a
result of complex interleavings of various subsystems which can be highly
elusive to track down. In order to deal with such non determinism, d-mode has
a record-and-replay module which runs alongside the kernel collecting enough
information in order to be able to restore the kernel to an arbitrary past
state (”replay”), ensuring that the kernel progresses exactly in the manner it
progressed when the elusive bug was encountered. Every time an ISR (interrupt
service routine) is executed, the EIP of the interrupted instruction is
recorded along with the ECX register (as the interrupted instruction could be
within a loop and therefore different instructions could have the had the same
EIP but did not get interrupted) is recorded along with any input that the ISR
received (such as a key stroke). During replay, we make use of debug registers
(on x86) in order to set breakpoints at recorded EIP locations where the
kernel’s execution was interrupted. d-mode then modifies the registers to
result in a stack switch and restarts execution after setting up the ISR’s
stack so that it does exactly what it did previously. On each breakpoint,
control is returned to the user for examination so that the user can set
additional breakpoints or look into data structures or memory akin to a
conventional debugger (like KGDB[12]).

####  III-C6 Interrupts

While executing, d-mode disables all interrupts apart from the keyboard
interrupts as that is required for user interaction. While replaying it mimcs
the interrupt arrival but reconstructing the interrupt stack from the records.

##  IV EVALUATION

We evaluate the debuggability score of d-Pebbles and Pebbles and the memory
overhead incurred for maintaining d-mode’s state in d-Pebbles. The Pebbles
kernel only allows a single process to perform allocations, deallocations to
protect the memory manager’s data structures. We increment, decrement the data
structure counters within these locks and observed that the addition of these
counters had no execution overhead. As a result, we only present evaluation
for the execution overhead of d-Pebbles incurred by the VM logging module
using two benchmarks: 712bench and mutex712bench [13].

###  IV-A Debuggability

We measure the number of iterations it takes for d-Pebbles to debug issues in
each of the scenarios listed in Debuggability Scenarios. We use these
iteration counts in cyclic debugging of the listed bugs to quantify the
debuggability of each kernel. Table I shows the resulting Debuggability
scores. We find that d-Pebbles improves the debuggability of Pebbles by at
least 66.6%.

####  IV-A1 Memory Exhaustion

Pebbles
Iteration 1: Observe fork() fails and turn on debugging in fork()
Iteration 2: Observe fork failure due to memory exhaustion, turn on logging in
VM
Iteration 3: Observe no deallocations of PCB, infer that the bug must be in
wait()
d-Pebbles
Iteration 1: Get memory stats and running processes after observing that
fork() failed due to memory exhaustion. Large number of PCB allocations and no
running processes suggests memory leaks in the implementation of wait()

####  IV-A2 Use after free

Pebbles
Iteration 1: Examine the crash dump from kernel panic and observe that
readfile() caused the page fault
Iteration 2: Enable syscall and VM logging to relate the faulting buffer’s
address and what operations were conducted on that address
Iteration 3: Re-run the kernel and examine the logs to find the use-after-free
issue
d-Pebbles
Iteration 1: Drop into d-mode after the kernel panics. Check the VM operations
on the address in the cr2 register, EIP from readfile syscall. Note that the
faulting address was deallocated by another thread from the VM operation logs,
infer that readline does not handle use-after-free issues

####  IV-A3 Non-determinism

Pebbles
Iteration 1: Examine stack trace of the crashing process and enable logging in
the stack switch code path along with yield.
Iteration 2: Wonder what might have caused the error, and re-run the kernel
with logging enabled.
Iteration 3: … Unable to reproduce the exact bug, enable more logging in the
system to understand what’s going on and run the system with logging enabled
to catch the bug when it resurfaces.
Iteration X: Observe that the timer was fired in between the yield
implementation and vanish was called shortly afterwards. Fix the issue.
d-Pebbles
Iteration 1: Drop into d-Mode as a result of a kernel panic. Observe that the
crash happened due to yield() and stack switch.
Iteration 2: Go back far enough to a point in the past (N time earlier) and
rerun the kernel adding breakpoints to understand what might have caused the
bug. Repeat with shorter time intervals to the past.
Iteration log(N): After binary searching over the time space of the past N
time units, should be able to zero in on the bug and fix the issue.

Bug Class | d-Pebbles | Pebbles
---|---|---
Memory Exhaustion | 1 | 3
Use After Free | 1 | atleast 3
Non-Determinism | log(N) | Unbounded
TABLE I: Debuggability Score.

###  IV-B Memory Overhead

d-Pebbles reserves an additional 20.216 KB for supporting d-mode. This 1%
overhead comes from a 4 KB kernel stack. for d-Mode, and a 120 bytes array of
counters for counting allocations of kernel data structures. The rest is used
for a ring buffer for logging VM operations, which we currently limit to a
size of 1000 log entries. Although this overhead is fairly small, we expect it
to grow when the record and replay engine is implemented in the kernel which
would log more operations than just VM operations. The size of the required
log will grow to accomodate a larger log of the past operations.

###  IV-C Execution overhead without contention

The 712bench performs N VM allocations and N deallocations in a single
unithreaded process. We measure the time to perform these N allocations and N
deallocations in d-Pebbles with VM logging and compare it with vanilla
Pebbles. We use the getticks() system call to measure elapsed time in CPU
timer ticks. Fig 2a shows the relative overhead of d-Pebbles by varying the
total operations, 2N. We observe a low overhead of less than 1.5% of d-Pebbles
over Pebbles.

Fig 2a. Execution Overhead of d-Pebbles for 712bench

While running the 712bench the authors ran into an unexpected memory
exhaustion at the 780759th allocation in vanilla Pebbles. Running the bench
with d-Pebbles allowed us to step into the debug shell at failure and use the
’memstat’ command in d-Mode to find an over-population of mem region t
objects, exactly 780759 of them to be precise, hinting a memory leak in remove
pages.

###  IV-D Execution Overhead with contention

Writing VM logs by multiple threads requires synchronization. mutex712bench
creates C child processes and each process performs N memory allocations and N
deallocations. As each child spawned child process does memory allocations,
they all contend for a slot on the VM log list, with a higher C implying
higher contention. We measure the time to perform these C*N allocation in
d-Pebbles with VM logging and compare it with vanilla Pebbles using getticks()
to measure elapsed time. Fig 2b. shows the relative overhead of d-Pebbles by
varying C and keeping N fixed at 100. We observe that the overhead due to
locking is less than 4%.

Fig 2b. Relative execution overhead with contention of d-Pebbles for
mutex712bench.

##  V Conclusion and Future Work

By designing, implementing and evaluating d-Pebbles, we conclude that a kernel
with ”debuggability” as a design principle can indeed be constructed and it is
effective in guiding its own debugging. We demonstrate that making use of our
recommendations can improve the debuggability of a kernel without severe
overhead. We expect the recording overhead and interrupt latency related to
our record-and-replay to have high cost, but believe that exploiting hardware
support would help optimize away the runtime overheads. We would also like to
explore the exciting nature of record-and-replay in a multiprocessor setting
as the degree of nondeterminism increases sharply when compared to a
uniprocessor. Trusting a kernel to not corrupt the reserved memory area is a
general concern whilst debugging without external support. We plan to look
into cryptographic hashing (signing) to check integrity, and also explore
hardware extensions for enclaves such as Intel’s SGX to guarantee integrity.
As an end result, we would like to obviate the need for external debugging
tools for kernel development and enable the kernel to be self sufficient in
this regard.

##  VI Acknowledgements

We would like to thank Phil Gibbons and Andrew Chung for constant guidance
right from the ideation phase for this endeavour. We were able to convert an
initial unpolished idea that was something along the lines of ”the kernel
debugging itself” to a full fledged study of how a kernel’s design affect its
debuggability thanks to their guidance. The research papers that we studied as
a part of the 15-712 course has enabled us to conduct research with a critical
eye for detail.

## References

  * [1] G. Lehey, “Debugging Kernel Problems.” http://www.lemis.com/grog/Papers/Debug-tutorial/tutorial.pdf/, 2006.
  * [2] D. H. O’Dell, “The debugging mindset,” Queue, vol. 15, p. 71–90, Feb. 2017.
  * [3] “DTrace.” http://dtrace.org/blogs/about.
  * [4] “Dtrace pid provider overhead.” http://dtrace.org/blogs/brendan/2011/02/18/dtrace-pid-provider-overhead/.
  * [5] “Freebsd doc: On-line kernel debugging.” https://www.freebsd.org/doc/enus.iso8859-1/books/developers-handbook/kerneldebug-online-gdb.htmlusinggdb/.
  * [6] “Jtag technologies.” https://www.jtag.com.
  * [7] S. Ren, L. Tan, C. Li, Z. Xiao, and W. Song, “Samsara: Efficient deterministic replay in multiprocessor environments with hardware virtualization extensions,” in Proceedings of the 2016 USENIX Conference on Usenix Annual Technical Conference, USENIX ATC ’16, (USA), p. 551–564, USENIX Association, 2016.
  * [8] T. F. Bissyandé, L. Réveillère, J. L. Lawall, and G. Muller, “Diagnosys: Automatic generation of a debugging interface to the linux kernel,” in Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering, ASE ’12, (New York, NY, USA), p. 60–69, Association for Computing Machinery, 2012.
  * [9] B. Blum, “Parallel data lab project: Landslide: Systematic dynamic race detection in kernel space..” https://www.pdl.cmu.edu/PDL-FTP/associated/CMU-CS-12-118.pdf/, 2012.
  * [10] “Operating system design and implementation pebbles kernel specification.” https://www.cs.cmu.edu/410/p2/kspec.pdf.
  * [11] Y. Wang, H. Patil, C. Pereira, G. Lueck, R. Gupta, and I. Neamtiu, “Drdebug: Deterministic replay based cyclic debugging with dynamic slicing,” in Proceedings of Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO ’14, (New York, NY, USA), p. 98–108, Association for Computing Machinery, 2014.
  * [12] “kgdb.” https://www.freebsd.org/cgi/man.cgi?query=kgdbsektion=1.
  * [13] “d-Pebbles.” https://github.com/lrx33/p3410/tree/dmode.


-\alpha\sum_{i=1}^{d}\frac{(g_{k}^{(i)})^{2}}{\sqrt{v_{k}^{(i)}+\max\big{(}\big{(}{g}_{0}^{(i)}\big{)}^{2},\phi^{2}\big{)}\delta_{k}^{2}}}\Bigg{(}1-\frac{\alpha
L_{i}}{2\sqrt{v_{k}^{(i)}+\max\big{(}\big{(}{g}_{0}^{(i)}\big{)}^{2},\phi^{2}\big{)}\delta_{k}^{2}}}\Bigg{)}.$
(151)

Now until $1-\frac{\alpha
L_{i}}{2\sqrt{v_{k}^{(i)}+\max\big{(}\big{(}{g}_{0}^{(i)}\big{)}^{2},\phi^{2}\big{)}\delta_{k}^{2}}}\geq\frac{1}{2}$
for each $i\in[d]$, i.e.,

$v_{k}^{(i)}+\max\big{(}\big{(}{g}_{0}^{(i)}\big{)}^{2},\phi^{2}\big{)}\delta_{k}^{2}\geq\alpha^{2}L_{i}^{2}\text{
for each }i\in[d],$ (152)

we have:

$\displaystyle f(\bm{x}_{k+1})-f^{*}$ $\displaystyle\leq
f(\bm{x}_{k})-f^{*}-\frac{\alpha}{2}\sum_{i=1}^{d}\frac{(g_{k}^{(i)})^{2}}{\sqrt{v_{k}^{(i)}+\max\big{(}\big{(}{g}_{0}^{(i)}\big{)}^{2},\phi^{2}\big{)}\delta_{k}^{2}}}.$
(153)

For ease of notation, let us define $\Delta_{k}:=f(\bm{x}_{k})-f^{*}$. With
this, the above becomes:

$\displaystyle\Delta_{k+1}$
$\displaystyle\leq\Delta_{k}-\frac{\alpha}{2}\sum_{i=1}^{d}\frac{(g_{k}^{(i)})^{2}}{\sqrt{v_{k}^{(i)}+\max\big{(}\big{(}{g}_{0}^{(i)}\big{)}^{2},\phi^{2}\big{)}\delta_{k}^{2}}}.$
(154)

Clearly,
$v_{k}^{(i)}+\max\big{(}\big{(}{g}_{0}^{(i)}\big{)}^{2},\phi^{2}\big{)}\delta_{k}^{2}\geq\alpha^{2}L_{i}^{2}$
holds for all $i\in[d]$ until at least:

$\max\big{(}\big{(}{g}_{0}^{(i)}\big{)}^{2},\phi^{2}\big{)}\delta_{k}^{2}\geq\alpha^{2}L_{i}^{2}\text{
}\forall\text{ }i\in[d].$ (155)

Next, recall that
$v_{k}^{(i)}=\sum_{l=0}^{k}\beta_{2}^{k-l}(g_{l}^{(i)})^{2}$. Also from Lemma
11, we have $(g_{l}^{(i)})^{2}\leq
2L_{i}(f(\bm{x}_{l})-f^{*})=2L_{i}\Delta_{l}$. Using this, we get:

$v_{k}^{(i)}\leq 2L_{i}\sum_{l=0}^{k}\beta_{2}^{k-l}\Delta_{l}.$ (156)

From Lemma 11, we also have $(g_{0}^{(i)})^{2}\leq
2L_{i}(f(\bm{x}_{0})-\bar{f}^{*}_{i}(\bm{x}_{0}))$ where
$\bar{f}^{*}_{i}(\bm{x}_{0})={\min}_{h\in\mathbb{R}}\text{
}f(\bm{x}_{0}+h\bm{e}_{i})$. Let
$\bar{\Delta}_{i,0}:=f(\bm{x}_{0})-\bar{f}^{*}_{i}(\bm{x}_{0})$; note that
$\bar{\Delta}_{i,0}\leq\Delta_{0}$ for all $i\in[d]$. Then,

$(g_{0}^{(i)})^{2}\leq 2L_{i}\bar{\Delta}_{i,0}.$ (157)

Plugging all of this into eq. 154, we get:

$\Delta_{k+1}\leq\Delta_{k}-\sum_{i=1}^{d}\Bigg{(}\frac{\alpha}{2\sqrt{\sum_{l=0}^{k}\beta_{2}^{k-l}\Delta_{l}+\max\big{(}\bar{\Delta}_{i,0},\frac{\phi^{2}}{2L_{i}}\big{)}\delta_{k}^{2}}}\Bigg{)}\frac{(g_{k}^{(i)})^{2}}{\sqrt{2L_{i}}}.$
(158)

Let $R=\max_{i\in[d]}\frac{\phi^{2}}{2L_{i}}=\frac{\phi^{2}}{2L_{\text{min}}}$
and $\bar{\Delta}^{*}_{0}=\max_{i\in[d]}\bar{\Delta}_{i,0}$. Then the above
can be bounded as:

$\Delta_{k+1}\leq\Delta_{k}-\Bigg{(}\frac{\alpha}{2\sqrt{\sum_{l=0}^{k}\beta_{2}^{k-l}\Delta_{l}+\max\big{(}\bar{\Delta}^{*}_{0},R\big{)}\delta_{k}^{2}}}\Bigg{)}\sum_{i=1}^{d}\frac{(g_{k}^{(i)})^{2}}{\sqrt{2L_{i}}}.$
(159)

Next, using the fact that $f$ satisfies the smoothness-dependent
$\tilde{\mu}$-global-PL condition above, we get:

$\displaystyle\Delta_{k+1}\leq\Bigg{(}1-\frac{\alpha\sqrt{({\tilde{\mu}}/{2})}}{\sqrt{{\sum_{l=0}^{k}\beta_{2}^{k-l}\Delta_{l}+\max\big{(}\bar{\Delta}^{*}_{0},R\big{)}\delta_{k}^{2}}}}\Bigg{)}\Delta_{k}.$
(160)

Now note that we will have descent in each iteration or continuous descent
(similar to Theorems 2 and 3) until at least
$\sqrt{\sum_{l=0}^{k}\beta_{2}^{k-l}\Delta_{l}+\max\big{(}\bar{\Delta}^{*}_{0},R\big{)}\delta_{k}^{2}}\geq\alpha\sqrt{\frac{\tilde{\mu}}{2}}$.
This will hold until at least:

$\max\big{(}\bar{\Delta}^{*}_{0},R\big{)}\delta_{k}^{2}\geq\alpha^{2}\Big{(}\frac{\tilde{\mu}}{2}\Big{)}.$
(161)

But recall our earlier constraint in eq. 155, i.e.,
$\max\big{(}\big{(}{g}_{0}^{(i)}\big{)}^{2},\phi^{2}\big{)}\delta_{k}^{2}\geq\alpha^{2}L_{i}^{2}$
for all $i\in[d]$. We shall show that eq. 155 is stricter than the condition
in eq. 161. Note that eq. 155 can be rewritten as:

$\alpha^{2}\leq\max\Bigg{(}\frac{\big{(}{g}_{0}^{(i)}\big{)}^{2}}{L_{i}^{2}},\frac{\phi^{2}}{L_{i}^{2}}\Bigg{)}\delta_{k}^{2}\text{
}\forall\text{ }i\in[d].$ (162)

On the other hand, recalling that $R=\frac{\phi^{2}}{2L_{\text{min}}}$, eq.
161 can be rewritten as:

$\alpha^{2}\leq\Bigg{(}\frac{2\bar{\Delta}^{*}_{0}}{\tilde{\mu}},\frac{\phi^{2}}{\tilde{\mu}L_{\text{min}}}\Bigg{)}\delta_{k}^{2}.$
(163)

Using eq. 157, we get for any $i\in[d]$:

$\frac{\big{(}{g}_{0}^{(i)}\big{)}^{2}}{L_{i}^{2}}\leq\frac{2\bar{\Delta}_{i,0}}{L_{i}}\leq\frac{2\bar{\Delta}^{*}_{0}}{\tilde{\mu}},$
(164)

where the last inequality follows because
$\bar{\Delta}^{*}_{0}=\max_{i\in[d]}\bar{\Delta}_{i,0}$ and $\tilde{\mu}\leq
L_{i}$ $\forall$ $i\in[d]$. Also,

$\frac{\phi^{2}}{L_{i}^{2}}\leq\frac{\phi^{2}}{\tilde{\mu}L_{\text{min}}},$
(165)

because $\tilde{\mu}\leq L_{\text{min}}\leq L_{i}$ $\forall$ $i\in[d]$. Thus,
eq. 162 is stricter than eq. 163 implying that eq. 155 is stricter than eq.
161.

For concise notation, let us define
$\widehat{v}_{k}:=\sum_{l=0}^{k}\beta_{2}^{k-l}\Delta_{l}$. With that, we have
(from eq. 160):

$\Delta_{k+1}\leq\Bigg{(}1-\frac{\alpha\sqrt{({\tilde{\mu}}/{2})}}{\sqrt{{\widehat{v}_{k}+\max\big{(}\bar{\Delta}^{*}_{0},R\big{)}\delta_{k}^{2}}}}\Bigg{)}\Delta_{k},$
(166)

until at least
$\max\big{(}\big{(}{g}_{0}^{(i)}\big{)}^{2},\phi^{2}\big{)}\delta_{k}^{2}\geq\alpha^{2}L_{i}^{2}$
for all $i\in[d]$; note that this can be rewritten as:

$\alpha^{2}\leq\max\Bigg{(}\min_{i\in[d]}\frac{\big{(}{g}_{0}^{(i)}\big{)}^{2}}{L_{i}^{2}},\min_{i\in[d]}\frac{\phi^{2}}{L_{i}^{2}}\Bigg{)}\delta_{k}^{2}=\max\Bigg{(}\min_{i\in[d]}\frac{\big{(}{g}_{0}^{(i)}\big{)}^{2}}{L_{i}^{2}},\frac{\phi^{2}}{L_{\text{max}}^{2}}\Bigg{)}\delta_{k}^{2}.$
(167)

Suppose the above holds for the first $\tilde{K}$ iterations. Let us choose
$\phi\leq\sqrt{2L_{\textup{min}}\Delta_{0}}$,
$\alpha\leq\sqrt{\frac{\Delta_{0}}{\tilde{\mu}}}$,
$\beta_{2}=1-\frac{\alpha^{2}\tilde{\mu}}{16\Delta_{0}}$ and
$\delta_{k}=\frac{1}{\sqrt{2(1-\beta_{2})}}\beta_{2}^{\frac{k}{2}}$. Then from
Lemma 9,

$\tilde{K}=\frac{\log\Big{(}\max\Big{(}\min_{i\in[d]}\frac{({g}_{0}^{(i)})^{2}}{L_{i}^{2}},\frac{\phi^{2}}{L_{\textup{max}}^{2}}\Big{)}\frac{1}{2(1-\beta_{2})\alpha^{2}}\Big{)}}{\log\frac{1}{\beta_{2}}}=\frac{\log\Big{(}\max\Big{(}\min_{i\in[d]}\frac{({g}_{0}^{(i)})^{2}}{L_{i}^{2}},\frac{\phi^{2}}{L_{\textup{max}}^{2}}\Big{)}\frac{8\Delta_{0}}{\alpha^{4}\tilde{\mu}}\Big{)}}{\log\frac{1}{\beta_{2}}},$
(168)

where the last step follows by plugging in
$\beta_{2}=1-\frac{\alpha^{2}\tilde{\mu}}{16\Delta_{0}}$. Also from Lemma 8,
we have for any $k\leq\tilde{K}$:

$\Delta_{k}\leq\exp\Bigg{(}-2\Big{(}\beta_{2}^{-\frac{k}{2}}-1\Big{)}\Bigg{)}\Delta_{0}.$
(169)

Now in order to have $\Delta_{K^{*}}\leq\varepsilon$, we can choose:

$K^{*}=\frac{\log\big{(}\frac{1}{4}\log^{2}\big{(}\frac{e^{2}\Delta_{0}}{\varepsilon}\big{)}\big{)}}{\log\frac{1}{\beta_{2}}}.$
(170)

Now in order for our result to be applicable, let us ensure
$K^{*}\leq\tilde{K}$; this yields:

$\alpha\leq\mathcal{O}\Bigg{(}\Bigg{(}\max\Bigg{(}\min_{i\in[d]}\frac{({g}_{0}^{(i)})^{2}}{L_{i}^{2}},\frac{\phi^{2}}{L_{\textup{max}}^{2}}\Bigg{)}\frac{\Delta_{0}}{\tilde{\mu}}\Bigg{)}^{1/4}\log^{-1/2}\Big{(}\frac{\Delta_{0}}{\varepsilon}\Big{)}\Bigg{)}.$
(171)

Per eq. 197 (in the proof of Lemma 9),
$\max\Big{(}\min_{i\in[d]}\frac{({g}_{0}^{(i)})^{2}}{L_{i}^{2}},\frac{\phi^{2}}{L_{\textup{max}}^{2}}\Big{)}\leq\frac{2\Delta_{0}}{\tilde{\mu}}$.
Hence, the constraint in eq. 171 satisfies our earlier condition on $\alpha$,
namely $\alpha\leq\sqrt{\frac{\Delta_{0}}{\tilde{\mu}}}$. From 3,
$({g}_{0}^{(i)})^{2}\geq 2\mu_{i,0}{\Delta}_{0}$. Using this in eq. 171 and
choosing $\phi=\sqrt{2L_{\textup{min}}\Delta_{0}}$, the following is a valid
range for $\alpha$:

$\alpha\leq\mathcal{O}\Bigg{(}\Bigg{(}\max\Bigg{(}\min_{i\in[d]}\frac{\mu_{i,0}}{L_{i}^{2}},\frac{L_{\text{min}}}{L_{\textup{max}}^{2}}\Bigg{)}\frac{\Delta_{0}^{2}}{\tilde{\mu}}\Bigg{)}^{1/4}\log^{-1/2}\Big{(}\frac{\Delta_{0}}{\varepsilon}\Big{)}\Bigg{)}.$
(172)

Further, using 3, we have that
$\frac{\mu_{i,0}}{L_{i}}\geq\frac{1}{{\kappa}_{\textup{max},0}}$ for all
$i\in[d]$. Using this above along with the fact that
$\min_{i\in[d]}\frac{1}{L_{i}}=\frac{1}{L_{\text{max}}}$, we can pick the
following value of $\alpha$:

$\alpha=\mathcal{O}\Bigg{(}\Bigg{(}\max\Bigg{(}\frac{1}{\kappa_{\text{max},0}},\frac{L_{\text{min}}}{L_{\textup{max}}}\Bigg{)}\frac{\Delta_{0}^{2}}{\tilde{\mu}L_{\textup{max}}}\Bigg{)}^{1/4}\log^{-1/2}\Big{(}\frac{\Delta_{0}}{\varepsilon}\Big{)}\Bigg{)}.$
(173)

Next, recalling that $\beta_{2}=1-\frac{\alpha^{2}\tilde{\mu}}{16\Delta_{0}}$,
$\log\frac{1}{\beta_{2}}\geq\frac{\alpha^{2}\tilde{\mu}}{16\Delta_{0}}$ using
1. Plugging this in the expression of $K^{*}$ (eq. 170), we get:

$K^{*}=\mathcal{O}\Bigg{(}\frac{\Delta_{0}}{\alpha^{2}\tilde{\mu}}{\log\Big{(}\log\Big{(}\frac{\Delta_{0}}{\varepsilon}\Big{)}\Big{)}}\Bigg{)}.$
(174)

Plugging in the value of $\alpha$ from eq. 173, we get:

$K^{*}=\mathcal{O}\Bigg{(}\sqrt{\frac{L_{\text{max}}}{\tilde{\mu}}}\min\Bigg{(}\sqrt{{\kappa_{\text{max},0}}},\sqrt{\frac{L_{\text{max}}}{L_{\text{min}}}}\Bigg{)}\log\Big{(}\frac{\Delta_{0}}{\varepsilon}\Big{)}{\log\Big{(}\log\Big{(}\frac{\Delta_{0}}{\varepsilon}\Big{)}\Big{)}}\Bigg{)}.$
(175)

∎

######  Lemma 8 (Similar to Lemma 2).

Suppose eq. 166 holds:

$\Delta_{k+1}\leq\Bigg{(}1-\frac{\alpha\sqrt{({\tilde{\mu}}/{2})}}{\sqrt{{\widehat{v}_{k}+\max\big{(}\bar{\Delta}^{*}_{0},R\big{)}\delta_{k}^{2}}}}\Bigg{)}\Delta_{k},$

for $k=0$ through to $k=\tilde{K}$, where
$\alpha^{2}\leq\max\Big{(}\min_{i\in[d]}\frac{({g}_{0}^{(i)})^{2}}{L_{i}^{2}},\frac{\phi^{2}}{L_{\textup{max}}^{2}}\Big{)}\delta_{k}^{2}$
for all $k\in\\{0,\ldots,\tilde{K}\\}$. Suppose we set
$\phi\leq\sqrt{2L_{\textup{min}}\Delta_{0}}$,
$\alpha\leq\sqrt{\frac{\Delta_{0}}{\tilde{\mu}}}$,
$\beta_{2}=1-\frac{\alpha^{2}\tilde{\mu}}{16\Delta_{0}}$ and
$\delta_{k}=\frac{1}{\sqrt{2(1-\beta_{2})}}\beta_{2}^{\frac{k}{2}}$ for $k\geq
0$. Then for any $k\leq\tilde{K}$, we have:

$\Delta_{k+1}\leq\exp\Bigg{(}-2\Big{(}\beta_{2}^{-(k+1)/2}-1\Big{)}\Bigg{)}\Delta_{0}.$

###### Proof.

Similar to Lemma 2, we perform the analysis in two stages.

First Stage. From eq. 166,
$\Delta_{0}\geq\Delta_{1}\geq\ldots\geq\Delta_{\tilde{K}+1}$. So for any
$k\leq\tilde{K}$:

$\widehat{v}_{k}={\sum_{l=0}^{k}\beta_{2}^{k-l}\Delta_{l}}\leq{\sum_{l=0}^{k}\beta_{2}^{k-l}\Delta_{0}}\leq\frac{\Delta_{0}}{1-\beta_{2}}.$
(176)

Further, we have chosen the ${\delta}_{k}$’s so that
${\delta}_{k}\leq{\delta}_{0}\leq\frac{1}{\sqrt{1-\beta_{2}}}$ for all $k\geq
1$. Also, with our restriction on $\phi$, we have that
$R=\frac{\phi^{2}}{2L_{\text{min}}}\leq\Delta_{0}$. Moreover,
$\bar{\Delta}^{*}_{0}\leq\Delta_{0}$ by definition. Thus:

$\max\big{(}\bar{\Delta}^{*}_{0},R\big{)}\leq\Delta_{0},$ (177)

and hence

$\widehat{v}_{k}+\max\big{(}\bar{\Delta}^{*}_{0},R\big{)}\delta_{k}^{2}\leq\widehat{v}_{k}+\Delta_{0}\delta_{k}^{2}\leq\frac{2\Delta_{0}}{1-\beta_{2}}.$
(178)

Plugging this into eq. 166 gives us:

$\Delta_{k+1}\leq\Bigg{(}1-\frac{{\alpha}\sqrt{\tilde{\mu}(1-\beta_{2})}}{2\sqrt{\Delta_{0}}}\Bigg{)}\Delta_{k}.$
(179)

Define
$\gamma:=\Big{(}1-\frac{{\alpha}\sqrt{\tilde{\mu}(1-\beta_{2})}}{2\sqrt{\Delta_{0}}}\Big{)}$.
Unfolding the recursion in eq. 179 yields:

$\Delta_{k+1}\leq\gamma^{k+1}\Delta_{0}.$ (180)

This bound is loose but we shall obtain a tighter bound using this bound.

Second Stage. With our choice of
$\beta_{2}=1-\frac{\alpha^{2}\tilde{\mu}}{16\Delta_{0}}$, we have
$\gamma=1-\frac{\alpha^{2}\tilde{\mu}}{8\Delta_{0}}$ and
$\beta_{2}-\gamma={1-\beta_{2}}$. Now for any $k\leq\tilde{K}$, we have:

$\displaystyle\widehat{v}_{k}=\sum_{l=0}^{k}\beta_{2}^{k-l}\Delta_{l}$
$\displaystyle\leq\sum_{l=0}^{k}\beta_{2}^{k-l}\gamma^{l}\Delta_{0}$ (181)
$\displaystyle=\Bigg{(}\frac{\beta_{2}^{k+1}-\gamma^{k+1}}{\beta_{2}-\gamma}\Bigg{)}\Delta_{0}$
(182)
$\displaystyle\leq\Big{(}\frac{\beta_{2}^{k+1}}{1-\beta_{2}}\Big{)}\Delta_{0},$
(183)

where the last step follows from the fact that
$\beta_{2}-\gamma={1-\beta_{2}}$. Note that with our constraint of
$\alpha\leq\sqrt{\frac{\Delta_{0}}{\tilde{\mu}}}$, we have:

$\beta_{2}\geq\frac{1}{2}.$ (184)

Thus, we have
$\delta_{k}=\frac{1}{\sqrt{2(1-\beta_{2})}}\beta_{2}^{\frac{k}{2}}\leq\frac{1}{\sqrt{1-\beta_{2}}}\beta_{2}^{\frac{k+1}{2}}$
for all $k$. Hence:

$\widehat{v}_{k}+\max\big{(}\bar{\Delta}^{*}_{0},R\big{)}\delta_{k}^{2}\leq\widehat{v}_{k}+\Delta_{0}\delta_{k}^{2}\leq\Big{(}\frac{2\beta_{2}^{k+1}}{1-\beta_{2}}\Big{)}\Delta_{0}.$
(185)

Plugging this into eq. 166, we get:

$\displaystyle\Delta_{k+1}$
$\displaystyle\leq\Bigg{(}1-\frac{\alpha\sqrt{\tilde{\mu}(1-\beta_{2})}\beta_{2}^{-{(k+1)/2}}}{2\sqrt{\Delta_{0}}}\Bigg{)}\Delta_{k}.$
(186)

Our condition in Lemma 9 will ensure
$\frac{\alpha\sqrt{\tilde{\mu}(1-\beta_{2})}\beta_{2}^{-{(k+1)/2}}}{2\sqrt{\Delta_{0}}}\leq
1$ for all $k\leq\tilde{K}$; refer to its statement. Next, using the fact that
$\exp(-z)\geq 1-z$ for $z\in\mathbb{R}$ above, we get:

$\Delta_{k+1}\leq\exp\Bigg{(}-\frac{\alpha\sqrt{\tilde{\mu}(1-\beta_{2})}\beta_{2}^{-{(k+1)/2}}}{2\sqrt{\Delta_{0}}}\Bigg{)}\Delta_{k}.$
(187)

Unfolding the recursion in eq. 187 gives us:

$\displaystyle\Delta_{k+1}$
$\displaystyle\leq\exp\Bigg{(}-\frac{\alpha\sqrt{\tilde{\mu}(1-\beta_{2})}\beta_{2}^{-1/2}}{2\sqrt{\Delta_{0}}}\sum_{l=0}^{k}\big{(}\beta_{2}^{-1/2}\big{)}^{l}\Bigg{)}\Delta_{0}$
(188)
$\displaystyle=\exp\Bigg{(}-\frac{\alpha\sqrt{\tilde{\mu}(1-\beta_{2})}}{2\sqrt{\Delta_{0}}}\Bigg{(}\frac{\beta_{2}^{-(k+1)/2}-1}{1-\sqrt{\beta_{2}}}\Bigg{)}\Bigg{)}\Delta_{0}.$
(189)

Recall that $\beta_{2}=1-\frac{\alpha^{2}\tilde{\mu}}{16\Delta_{0}}$. Using
the fact that $\sqrt{\beta_{2}}\geq\beta_{2}$ above, we get:

$\Delta_{k+1}\leq\exp\Bigg{(}-2\Big{(}\beta_{2}^{-(k+1)/2}-1\Big{)}\Bigg{)}\Delta_{0}.$
(190)

∎

######  Lemma 9 (Similar to Lemma 3).

In the setting of Lemma 8,
$\alpha^{2}\leq\max\Big{(}\min_{i\in[d]}\frac{({g}_{0}^{(i)})^{2}}{L_{i}^{2}},\frac{\phi^{2}}{L_{\textup{max}}^{2}}\Big{)}\delta_{k}^{2}$
until:

$\tilde{K}=\frac{\log\Big{(}\max\Big{(}\min_{i\in[d]}\frac{({g}_{0}^{(i)})^{2}}{L_{i}^{2}},\frac{\phi^{2}}{L_{\textup{max}}^{2}}\Big{)}\frac{1}{2(1-\beta_{2})\alpha^{2}}\Big{)}}{\log\frac{1}{\beta_{2}}}$

iterations. Further, this value of $\tilde{K}$ also ensures the condition
after eq. 186 in the proof of Lemma 8, i.e.,

$\frac{\alpha\sqrt{\tilde{\mu}(1-\beta_{2})}\beta_{2}^{-{(k+1)/2}}}{2\sqrt{\Delta_{0}}}\leq
1\text{ }\forall\text{ }k\leq\tilde{K},$ (191)

also holds.

###### Proof.

Plugging in our choice of $\delta_{k}$ from Lemma 8 into our requirement of

$\alpha^{2}\leq\max\Big{(}\min_{i\in[d]}\frac{({g}_{0}^{(i)})^{2}}{L_{i}^{2}},\frac{\phi^{2}}{L_{\textup{max}}^{2}}\Big{)}\delta_{k}^{2},$

we conclude that as long as

$\max\Bigg{(}\min_{i\in[d]}\frac{({g}_{0}^{(i)})^{2}}{L_{i}^{2}},\frac{\phi^{2}}{L_{\textup{max}}^{2}}\Bigg{)}\Big{(}\frac{\beta_{2}^{{k}}}{{2(1-\beta_{2})}}\Big{)}\geq{\alpha^{2}},$
(192)

we are good. Let us verify that eq. 192 ensures the condition in eq. 191. To
that end, note that eq. 191 is equivalent to:

$\frac{4\Delta_{0}\beta_{2}^{k+1}}{\tilde{\mu}(1-\beta_{2})}\geq\alpha^{2}.$
(193)

But from eq. 184, we have $\beta_{2}\geq\frac{1}{2}$ and therefore, the above
is ensured by:

$\frac{2\Delta_{0}\beta_{2}^{k}}{\tilde{\mu}(1-\beta_{2})}\geq\alpha^{2}.$
(194)

From eq. 164, recall that
$\frac{({g}_{0}^{(i)})^{2}}{L_{i}^{2}}\leq\frac{2\bar{\Delta}^{*}_{0}}{\tilde{\mu}}$
for any $i\in[d]$. Since $\bar{\Delta}^{*}_{0}\leq\Delta_{0}$, we have:

$\min_{i\in[d]}\frac{\big{(}{g}_{0}^{(i)}\big{)}^{2}}{L_{i}^{2}}\leq\frac{2\Delta_{0}}{\tilde{\mu}}.$
(195)

Also, with our restriction of $\phi\leq\sqrt{2L_{\textup{min}}\Delta_{0}}$
from Lemma 8, we have:

$\frac{\phi^{2}}{L_{\textup{max}}^{2}}\leq\frac{2L_{\textup{min}}\Delta_{0}}{L_{\textup{max}}^{2}}\leq\frac{2\Delta_{0}}{L_{\textup{max}}}\leq\frac{2\Delta_{0}}{\tilde{\mu}}.$
(196)

Therefore,

$\max\Bigg{(}\min_{i\in[d]}\frac{({g}_{0}^{(i)})^{2}}{L_{i}^{2}},\frac{\phi^{2}}{L_{\textup{max}}^{2}}\Bigg{)}\leq\frac{2\Delta_{0}}{\tilde{\mu}}.$
(197)

and so:

$\max\Bigg{(}\min_{i\in[d]}\frac{({g}_{0}^{(i)})^{2}}{L_{i}^{2}},\frac{\phi^{2}}{L_{\textup{max}}^{2}}\Bigg{)}\Big{(}\frac{\beta_{2}^{{k}}}{{2(1-\beta_{2})}}\Big{)}\leq\frac{\Delta_{0}\beta_{2}^{k}}{\tilde{\mu}(1-\beta_{2})}.$
(198)

Hence, the condition in eq. 192 is stricter than the one in eq. 194. In other
words, the condition in eq. 192 ensures eq. 191. Finally, note that eq. 192
holds till

$\tilde{K}=\frac{\log\Big{(}\max\Big{(}\min_{i\in[d]}\frac{({g}_{0}^{(i)})^{2}}{L_{i}^{2}},\frac{\phi^{2}}{L_{\textup{max}}^{2}}\Big{)}\frac{1}{2(1-\beta_{2})\alpha^{2}}\Big{)}}{\log\frac{1}{\beta_{2}}}$
(199)

iterations. ∎

######  Lemma 10 (“Descent Lemma” for Per-Coordinate Smoothness).

Suppose $f$ is $\\{L_{i}\\}_{i=1}^{d}$-smooth. Then for any
$\bm{x},\bm{y}\in\mathbb{R}^{d}$, we have:

$f(\bm{y})\leq f(\bm{x})+\nabla
f(\bm{x})^{\top}(\bm{y}-\bm{x})+\frac{1}{2}\sum_{i=1}^{d}{L_{i}}\big{(}{y}^{(i)}-{x}^{(i)}\big{)}^{2}.$

###### Proof.

Let $\bm{x}_{\tau}=\bm{x}+\tau(\bm{y}-\bm{x})$ for $\tau\in[0,1]$. Using the
fundamental theorem of calculus, we have:

$\displaystyle\big{|}f(\bm{y})-\big{(}f(\bm{x})+\nabla
f(\bm{x})^{\top}(\bm{y}-\bm{x})\big{)}\big{|}$
$\displaystyle=\Big{|}\int_{0}^{1}\big{(}\nabla f(\bm{x}_{\tau})-\nabla
f(\bm{x})\big{)}^{\top}(\bm{y}-\bm{x})d\tau\Big{|}$ (200)
$\displaystyle\leq\int_{0}^{1}\sum_{i=1}^{d}\Big{|}\Big{(}\nabla
f(\bm{x}_{\tau})^{(i)}-\nabla
f(\bm{x})^{(i)}\Big{)}({y}^{(i)}-{x}^{(i)})\Big{|}d\tau$ (201)
$\displaystyle\leq\int_{0}^{1}\sum_{i=1}^{d}L_{i}\big{|}{x}_{\tau}^{(i)}-x^{(i)}\big{|}\big{|}{y}^{(i)}-{x}^{(i)}\big{|}d\tau$
(202)
$\displaystyle\leq\int_{0}^{1}\sum_{i=1}^{d}L_{i}\big{(}{y}^{(i)}-{x}^{(i)}\big{)}^{2}\tau
d\tau$ (203)
$\displaystyle=\frac{1}{2}\sum_{i=1}^{d}{L_{i}}\big{(}{y}^{(i)}-{x}^{(i)}\big{)}^{2}$
(204)

Thus,

$f(\bm{y})\leq f(\bm{x})+\nabla
f(\bm{x})^{\top}(\bm{y}-\bm{x})+\frac{1}{2}\sum_{i=1}^{d}{L_{i}}\big{(}{y}^{(i)}-{x}^{(i)}\big{)}^{2}.$
(205)

∎

######  Lemma 11.

Suppose $f:\mathbb{R}^{d}\xrightarrow{}\mathbb{R}$ is
$\\{L_{i}\\}_{i=1}^{d}$-smooth. Then for any $\bm{x}\in\mathbb{R}^{d}$ and
$i\in[d]$, we have:

${(\nabla f(\bm{x})^{(i)})^{2}}\leq
2L_{i}\big{(}f(\bm{x})-\bar{f}^{*}_{i}(\bm{x})\big{)},$

where $\bar{f}^{*}_{i}(\bm{x})={\min}_{h\in\mathbb{R}}\text{
}f(\bm{x}+h\bm{e}_{i})$. As a result, we also have:

${(\nabla f(\bm{x})^{(i)})^{2}}\leq 2L_{i}\big{(}f(\bm{x})-{f}^{*}\big{)},$

where $f^{*}=\min_{\bm{z}\in\mathbb{R}^{d}}f(\bm{z})$.

###### Proof.

From Lemma 10, we have for any $\bm{x},\bm{y}$:

$f(\bm{y})\leq g(\bm{y}):=f(\bm{x})+\sum_{i=1}^{d}\nabla
f(\bm{x})^{(i)}\big{(}{y}^{(i)}-{x}^{(i)}\big{)}+\frac{1}{2}\sum_{i=1}^{d}{L_{i}}\big{(}{y}^{(i)}-{x}^{(i)}\big{)}^{2}.$
(206)

Let $\bar{f}^{*}_{i}(\bm{x}):={\min}_{h\in\mathbb{R}}\text{
}f(\bm{x}+h\bm{e}_{i})$ and
$\bar{g}^{*}_{i}(\bm{x}):={\min}_{h\in\mathbb{R}}\text{
}g(\bm{x}+h\bm{e}_{i})$; note that
$\bar{f}^{*}_{i}(\bm{x})\leq\bar{g}^{*}_{i}(\bm{x})$ $\forall$
$\bm{x}\in\mathbb{R}^{d}$. Since $g(\bm{x}+h\bm{e}_{i})=f(\bm{x})+\nabla
f(\bm{x})^{(i)}h+\frac{{L_{i}}h^{2}}{2}$, we obtain:

$\bar{g}^{*}_{i}(\bm{x})=f(\bm{x})-\frac{\big{(}\nabla
f(\bm{x})^{(i)}\big{)}^{2}}{2L_{i}}.$ (207)

Thus,

$\bar{f}^{*}_{i}(\bm{x})\leq f(\bm{x})-\frac{\big{(}\nabla
f(\bm{x})^{(i)}\big{)}^{2}}{2L_{i}}.$ (208)

Rearranging this, we get:

${(\nabla f(\bm{x})^{(i)})^{2}}\leq
2L_{i}\big{(}f(\bm{x})-\bar{f}^{*}_{i}(\bm{x})\big{)}.$ (209)

The other bound follows from the fact that
$f_{i}^{*}\leq\bar{f}^{*}_{i}(\bm{x})$ for all $\bm{x}\in\mathbb{R}^{d}$. ∎

##  Appendix J Proof of Corollary 1

###### Proof.

For any $\bm{x},\bm{y}\in\mathbb{R}^{d}$, we have for each $i\in[d]$:

$|\nabla f(\bm{y})^{(i)}-\nabla f(\bm{x})^{(i)}|\leq L_{i}|y^{(i)}-x^{(i)}|.$
(210)

Thus:

$\displaystyle\|\nabla f(\bm{y})-\nabla
f(\bm{x})\|_{2}^{2}=\sum_{i=1}^{d}|\nabla f(\bm{y})^{(i)}-\nabla
f(\bm{x})^{(i)}|^{2}$
$\displaystyle\leq\sum_{i=1}^{d}L_{i}^{2}|y^{(i)}-x^{(i)}|^{2}$ (211)
$\displaystyle\leq L_{\text{max}}^{2}\sum_{i=1}^{d}|y^{(i)}-x^{(i)}|^{2}$
(212) $\displaystyle=L_{\text{max}}^{2}\|\bm{y}-\bm{x}\|_{2}^{2}.$ (213)

Hence, $\|\nabla f(\bm{y})-\nabla f(\bm{x})\|_{2}\leq
L_{\text{max}}\|\bm{y}-\bm{x}\|_{2}$. So $f$ is $L_{\text{max}}$-smooth.

We also have:

$\sqrt{2\tilde{\mu}}\big{(}f(\bm{x})-f^{*}\big{)}\leq\sum_{i=1}^{d}\frac{(\nabla
f(\bm{x})^{(i)})^{2}}{\sqrt{2L_{i}}}\text{ }\forall\text{
}\bm{x}\in\mathbb{R}^{d}.$ (214)

Note that $\frac{(\nabla f(\bm{x})^{(i)})^{2}}{\sqrt{2L_{i}}}\leq\frac{(\nabla
f(\bm{x})^{(i)})^{2}}{\sqrt{2L_{\text{min}}}}$. Using this above, we get:

$\sqrt{2\tilde{\mu}}\big{(}f(\bm{x})-f^{*}\big{)}\leq\sum_{i=1}^{d}\frac{(\nabla
f(\bm{x})^{(i)})^{2}}{\sqrt{2L_{\text{min}}}}\leq\frac{\|\nabla
f(\bm{x})\|_{2}^{2}}{\sqrt{2L_{\text{min}}}}\implies\|\nabla
f(\bm{x})\|_{2}^{2}\geq 2\sqrt{\tilde{\mu}L_{\text{min}}}.$ (215)

Hence, $f$ is $\sqrt{\tilde{\mu}L_{\text{min}}}$-PL. ∎