# Tapestry: Revealing Wait-For Dependencies Between Application Threads

Tomáš Faltin, Himadri Chhaya-Shailesh, Julia Lawall, Jean-Pierre Lozi

► To cite this version:

Tomáš Faltin, Himadri Chhaya-Shailesh, Julia Lawall, Jean-Pierre Lozi. Tapestry: Revealing Wait-For Dependencies Between Application Threads. PLOS 2025 - 13th Workshop on Programming Languages and Operating Systems, Oct 2025, Seoul, South Korea. pp.8, 10.1145/3764860.3768339. hal-05306363

HAL Id: hal-05306363

https://inria.hal.science/hal-05306363v1

Submitted on 9 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# TAPESTRY: Revealing Wait-For Dependencies
Between Application Threads

Tomáš Faltín*

Charles University
Prague, Czech Republic
tomas.faltin@matfyz.cuni.cz

Julia Lawall

Inria
Paris, France
julia.lawall@inria.fr

Himadri Chhaya-Shailesh

Inria
Paris, France
himadri.pandya@inria.fr

Jean-Pierre Lozi

Inria
Paris, France
jean-pierre.lozi@inria.fr

## Abstract

Application slowdowns that accumulate on the critical path significantly impact performance. Identifying them requires visualizing inter-thread wait-for dependencies, a task neglected by existing tools, especially regarding ad-hoc, busy-waiting synchronization. We present TAPESTRY, which efficiently traces these dependencies by dynamically switching between hardware watchpoints and software breakpoints. Using three use cases, we show that TAPESTRY is able to reveal NUMA effects and explain performance anomalies in oversubscribed and virtualized environments.

**CCS Concepts: Software and its engineering → Software defect analysis; Software performance; Synchronization; Dynamic analysis.**

**Keywords:** tracing, synchronization, busy-waiting, critical path, dynamic instrumentation

## ACM Reference Format:

Tomáš Faltín, Himadri Chhaya-Shailesh, Julia Lawall, and Jean-Pierre Lozi. 2025. TAPESTRY: Revealing Wait-For Dependencies Between Application Threads. In *13th Workshop on Programming Languages and Operating Systems (PLOS '25), October 13–16, 2025, Seoul, Republic of Korea*. ACM, New York, NY, USA, 8 pages. https://doi.org/10.1145/3764860.3768339

# 1 Introduction

In the past decades, computer systems have featured a steadily rising number of CPU cores. As stated by Amdahl's law [1], the non-parallel part of an application becomes the primary performance bottleneck as the number of cores and

threads increases. Unfortunately, multithreaded applications are rarely fully parallel. They rely on synchronization, creating *wait-for dependencies* where the progress of one or more threads is paused, pending an action from another thread such as releasing a lock, updating a condition variable, or signaling that it arrived last at a barrier. The execution of a compute-heavy workload can be viewed as a directed dependency graph in which edges represent wait-for dependencies and vertices the execution of individual threads between them. The path with the longest execution time is the *critical path*, and its duration determines the total execution time of the application. Finding bottlenecks on the critical path is the most rewarding way of improving performance.

Existing profiling and tracing tools [7, 20, 21, 32] target typical application bottlenecks, such as functions that take up a large part of the execution [14, 15, 35], hardware-level slowdowns [4, 29], or specific bottlenecks related to e.g., memory [19] or lock contention [10, 31]. Such tools do not focus on *where* bottlenecks are located in the dependency graph, making it unclear whether the critical path is impacted. This calls for a tracing tool that focuses on dependencies.

Tracing inter-thread wait-for dependencies that are implemented with blocking synchronization can be achieved using some existing tools, by tracing the system call that parks a thread inside the kernel until a condition is met, such as *futex* in Linux. However, this approach misses all busy-waiting synchronization, in which application threads spin in user space instead of blocking inside the kernel. Busy-waiting is commonplace in performance-oriented applications, as it outperforms blocking synchronization by removing the overhead of threads going to sleep and waking up along the critical path. With a traditional tracing tool, however, busy-waiting looks identical to regular thread execution. All threads will be shown as constantly running from the beginning to the end of the application, resulting in a trace that looks identical to that of a perfectly parallel application. Consequently, with existing tools, performance profiling for applications that use busy-waiting is hard.

<figure><img src="image_2.png" /></figure>

<footnote>*This work was carried out while the author was at Inria.</footnote>
We present TAPESTRY, a tracing framework for Linux that enables observing wait-for dependencies between application threads regardless of whether the application uses blocking, busy-waiting, or a combination of both. TAPESTRY traces blocking using trace-cmd [32] to monitor calls to the futex system call. For busy-waiting, more infrastructure is required. Prior to runtime, TAPESTRY leverages binary-level static analysis and rewriting to find and instrument busy-wait loops. At runtime, TAPESTRY traces entries and exits of all such loops. Additionally, at the first execution of a busy-wait loop, it places a store hardware watchpoint on the memory address that, when written, may resolve the dependency, i.e., make the waiting thread exit the loop. On the execution of the store that resolves the dependency, the hardware watchpoint is triggered, and TAPESTRY records which thread resolved it. With the dependency store's code address now known, TAPESTRY replaces the hardware watchpoint with a software breakpoint in the form of a uprobe. This approach allows TAPESTRY to scale to the number of dependencies, despite the scarcity of hardware watchpoints (four on x86), as the number of software breakpoints is unlimited. Post-execution, TAPESTRY merges trace data about blocking and busy-waiting events with extra profiling data from trace-cmd to show sources of slowdown such as thread preemptions. It produces graphs that allow visualizing the dependency graph of applications with slowdowns along the way.

We showcase the usefulness of TAPESTRY in three use cases. In the first use case, TAPESTRY is able to show thread slowdowns caused by remote NUMA accesses. In the second use case, TAPESTRY reveals that the surprisingly low performance of the LU benchmark from the NAS suite [27] when run alongside another application is caused by a busy-wait loop that is present even when the OpenMP wait policy is set to PASSIVE, due to the loop being implemented at the application level. Finally, in the third use case, TAPESTRY reveals that the execution of the NAS benchmarks can be faster inside a virtual machine than on bare metal due to a surprising hardware effect: the virtualized, user-space execution of the PAUSE spinloop hint is faster when Pause-Loop Exiting (PLE) is enabled on (at least some) Intel machines, despite the fact that PLE is not supposed to impact user-space applications.

Our contributions can be summarized as follows:

* We present a *dependency model* that unifies the concept of inter-thread wait-for dependencies for blocking and busy-waiting synchronization.

* We design and implement TAPESTRY, a tracing framework that allows observing such dependencies by combining the use of hardware watchpoints and software breakpoints.

* We show the usefulness of TAPESTRY by investigating performance anomalies in three use cases.

* Through the third use case, we discover an undocumented hardware effect on Intel machines that causes user-space PAUSE instructions to execute faster in virtualized environments than on bare metal when PLE is enabled.

Section 2 presents our dependency model. Section 3 details the design and implementation of TAPESTRY. Section 4 demonstrates its use in three use cases. Section 5 discusses related work. Finally, Section 6 concludes.

# 2 Dependency Model

We propose a model that unifies inter-thread wait-for dependencies implemented with either blocking or busy-waiting.

## 2.1 Ordinary inter-thread wait-for dependencies

**Definition.** An ordinary inter-thread wait-for dependency is a triple `<addr, ⚜, val>`, where: (i) *addr* is the memory address of a shared variable, (ii) ⚜ is a comparison operator (e.g., ==, !=, or >=), and (iii) *val* is a constant value against which the memory content is compared, such that a thread's forward progress is predicated on the condition *addr ⚜ val*. The dependency is resolved when this condition is met.

**Blocking synchronization.** On Linux, all blocking synchronization is implemented through the futex system call. futex has two operations: FUTEX_WAIT and FUTEX_WAKE. The semantics of futex(*addr*, FUTEX_WAIT, *val*, ...) is that, if the value pointed to by *addr* is not equal to *val*, the thread blocks. Multiple threads can call FUTEX_WAIT with the same *addr* and *val* arguments. The blocked thread(s) will be woken up by another thread that will typically set *addr* to *val*, and call the FUTEX_WAKE operation. We represent such dependencies using the triple `<addr, ==, val>`, as thread progress requires the value pointed to by *addr* to be equal to *val*. The blocked thread can also be woken due to various exceptional conditions, such as a timeout or a signal, in which case the dependency is not resolved.

**Busy-waiting synchronization.** As shown in Listing 1, busy-waiting commonly uses a simple loop with a body that is empty, save for a potential PAUSE spinloop hint, and a loop condition that compares a pointed value (*barrier-end*, *lock*, or *tkt* in the listing) to a constant value (*true*, *0*, or *tkt* in the listing) using an operator. The loop may only read the pointed value in the condition (Listing 1(a)), or also write it with an atomic instruction (*atomic_test_and_set* in Listing 1(b) or *atomic_add* in Listing 1(d)). As shown in Listing 1(c), in the loop condition, the same pointed value may be compared twice to the same value using the same operator in order to issue fewer atomic instructions.

## 2.2 Other inter-thread wait-for dependencies

Assuming proper use of the futex API, all blocking dependencies are ordinary inter-thread wait-for dependencies.
```c
# (a) Barrier, dependency triple: <barrier_end, ==, true>
if (atomic_inc(thr_count) < n thr)
    while (!barrier_end) PAUSE;
else *barrier_end = true;

# (b) Simple lock: <lock, ==, 0>
while (!atomic_test_and_set.lock(0, 1)) PAUSE;

# (c) Test-and-test-and-set lock: <lock, ==, 0>
while (!*lock && !atomic_test_and_set.lock(0, 1)) PAUSE;

# (d) Ticket lock: <cur_tkt, >=, tkt>
tkt = atomic_inc(max_tkt);
while (*cur_tkt < tkt) PAUSE;

# (e) Other inter-thread wait dependency
while (fn1(*addr1) != fn2(*addr2)) PAUSE;
```

<caption>**Listing 1.** Busy-wait loops and their dependency triples.</caption>

With busy-waiting, as illustrated by Listing 1(e), some dependencies go beyond ordinary inter-thread wait-for dependencies. One possibility is that the value of the busy-wait loop's condition may depend on several pointed variables. Another possibility is that the busy-wait-loop condition may involve a complex operation, which may involve function calls and/or have side effects. In both cases, while only storing specific values into a specific pointed variable will cause the loop to exit, it may be hard or impossible to determine which ones.

## 2.3 Real-world inter-thread wait-for dependencies

In the literature proposing synchronization primitives [2, 3, 5, 11, 16, 18, 22–26], we found 44 example spinloops. Of these, 35 are busy-wait loops, of which 34 exclusively use ordinary inter-thread wait-for dependencies. An additional 9 loops do not model wait-for dependencies; instead, a thread repeatedly executes an atomic operation until success (no conflict from another thread). In the rest of this paper, we exclusively focus on ordinary inter-thread wait-for dependencies, and simply refer to them as *dependencies*.

# 3 Design

TAPESTRY aims to efficiently trace dependencies, a challenging task in the case of busy-waiting synchronization.

## 3.1 Architecture

The architecture of TAPESTRY has three components: (i) an *Analyzer*, (ii) a *Tracer*, and (iii) a *Viewer*.

The *Analyzer* finds all busy-wait loops in the application's binaries. Their locations then guide the *Tracer*'s binary instrumentation. To find busy-wait loops, the *Analyzer* relies on previously proposed heuristics [17], identifying loops where (i) the loop exit condition depends on a memory load (possibly due to an atomic instruction), and (ii) the condition's value is not changed by the loop body.

The *Tracer* traces application execution and captures dependencies. It uses `trace-cmd` to capture blocking synchronization via `futex` system calls. It uses static and dynamic instrumentation for busy-waiting synchronization to detect

the beginning and end of busy-wait loops and their dependencies. We describe busy-waiting detection in Section 3.2.

To minimize tracing overhead, the *Tracer* only captures raw events, which are later used in offline dependency reconstruction. Each record, an *output tracepoint tuple*, contains an event's timestamp and type (e.g., `WAIT_BEGIN/END`, `DEP_STORE`), the ID of the executing thread, a synchronization identifier (`syncID`) implemented as the busy-wait loop's entry point address or the *futex*'s wait variable address, and a dependency triple (`depID`). The `syncID` and `depID` uniquely identify a synchronization instance, allowing the *Viewer* to link a waiting thread to its corresponding resolving store.

The *Viewer* post-processes raw traces to reconstruct and visualize dependencies. For busy-waiting synchronization, it reconstructs a dependency by linking a `DEP_STORE` event to preceding `WAIT_BEGIN` events using their shared `depID`. It calculates wait durations by matching each pair of `WAIT_BEGIN` and `WAIT_END` events that have the same `syncID` and `depID`. For blocking synchronization, the necessary data is extracted from the intercepted *futex* system call arguments.

The *Viewer* produces a visualization of the resulting dependencies. A thread $T_A$ resolving a dependency thread $T_B$ was waiting on is visualized as an arrow from $T_A$ to $T_B$. The critical path is computed using a longest path algorithm, starting from the end of this graph, where most (or all) dependencies have been found.

For readability, threads are vertically sorted using a topological sort of a different graph $G = (V, E)$, where each vertex $v \in V$ represents a thread and an edge $(T_A, T_B) \in E$ exists iff $T_A$ resolved at least one dependency $T_B$ was waiting on. The edge's weight is the total count of such dependencies. The sort prioritizes exploring paths with higher-weight edges first, to minimize dependency edge crossings and highlight the primary data flow.

## 3.2 Tracing busy-waiting synchronization

We now present our technique for capturing busy-waiting dependencies with low overhead.

*Capturing where busy-wait loops start/end.* Using addresses from the *Analyzer*, we statically patch the beginning and end of each busy-wait loop. The injected code writes the `WAIT_BEGIN` and `WAIT_END` tracepoint tuples directly into a per-thread, pre-allocated, extensible buffer.

*Capturing dependencies.* To capture a dependency, the *Tracer* monitors the shared variable's memory address (`wait-VarAddr`) to detect the resolving write. The *Analyzer* identifies the register that holds this address at runtime by inspecting the busy-wait loop's conditional branch. While memory can be monitored with software watchpoints, their prohibitive overhead makes them unsuitable for tracing [28]. This leaves hardware watchpoints as the only viable mechanism. However, their scarcity (e.g., modern Intel CPUs provide only four) presents the core challenge our design must overcome.
Our solution is to dynamically *replace* hardware watchpoints with software breakpoints. After a watchpoint captures the first instance of a dependency-resolving store, we record the instruction address of that store. We then disable the hardware watchpoint and place a software breakpoint on the store instruction instead. This frees the hardware watchpoint to monitor a new, not-yet-observed dependency. While this design initially captures only the first-observed code path that resolves a dependency, we discuss a mitigation for this limitation at the end of this section.

Implementing this dynamic swapping requires a low-overhead interface. The standard Linux `ptrace` system call is unsuitable for this purpose. Designed for interactive debugging, it imposes significant overhead by requiring a separate tracer thread. To overcome this limitation, we implement a custom kernel module that exposes a lightweight API for managing watchpoints and breakpoints directly from user space.

**Dependency-capturing algorithm.** Our logic for capturing dependencies, presented in Algorithm 1, orchestrates the dynamic replacement of watchpoints with breakpoints. It relies on four primary data structures, of which two - DEPS and HWBPS - must reside in user-kernel shared memory to allow setting watchpoints across all CPUs.

* DEPS: A hash table mapping a dependency address (`waitVarAddr`) to its state and metadata.

* HWBPS: A resource pool managing the available hardware watchpoint registers.

* BREAKS: A set containing the addresses of all active software breakpoints, to prevent redundant insertions.

* WQ: A high-priority work queue deferring preemptible work from the non-preemptible watchpoint callback.

A call to `CatchDependency` (Algorithm 1) is injected at each busy-wait loop's entry. This function checks the DEPS table; if the dependency address (`waitVarAddr`) is not already monitored, it attempts to reserve a hardware watchpoint from the HWBPS pool. Upon success, it updates DEPS and sets the watchpoint using our lightweight API.

A write to the variable triggers a two-phase interrupt handler. The non-preemptible top-half, `watchClbkTop`, records the writer's instruction address and uses WQ to schedule the bottom-half, `watchClbkBottom`, to run. The bottom-half performs the handoff in a preemptible context, a necessity as the kernel functions for disabling the watchpoint and placing a new breakpoint can sleep (e.g., while acquiring mutexes). A set of active breakpoints (BREAKS) prevents redundant instrumentation. Subsequent writes from the same instruction are captured by a lightweight `breakClbk` handler, avoiding the high overhead of repeated hardware traps.

**Limitations and mitigations.** Our design has two primary limitations, each addressed with a specific mitigation. First, to address the possibility of missing writes from multiple code paths, we introduce a short *discovery window* (e.g.,

<caption>**Algorithm 1:** Dependency capturing algorithm.</caption>

1. **Function CatchDependency**(*waitVarAddr*)
2. &nbsp;&nbsp;&nbsp;&nbsp;if *DEPS*.exists(*waitVarAddr*) **then** return
3. &nbsp;&nbsp;&nbsp;&nbsp;else if *HWBPS*.tryReserve(*&hwbp*) **then**
4. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*DEPS*.add(*waitVarAddr*, HAS WATCH, now())
5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**setWatch**(*hwbp*, *waitVarAddr*, watchClbkTop)
6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**// Kernel-space callbacks**
7. &nbsp;&nbsp;&nbsp;&nbsp;**Function watchClbkTop**(*waitVarAddr*, *storeCodeAddr*, *hwbp*)
8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**storeTraceTuple**(*DEP_STORE*, *storeCodeAddr*)
9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**DEPS.setAddr**(*waitVarAddr*, *storeCodeAddr*, HAS_BREAK)
10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**WQ.enqueue**(*watchClbkBottom*(*waitVarAddr*, *storeCodeAddr*, *hwbp*))
11. &nbsp;&nbsp;&nbsp;&nbsp;**Function watchClbkBottom**(*waitVarAddr*, *storeCodeAddr*, *hwbp*)
12. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**unsetWatch**(*waitVarAddr*)
13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**HWBPS.release**(*hwbp*)
14. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if !BREAKS.exists(*storeCodeAddr*) **then**
15. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**BREAKS.add**(*storeCodeAddr*)
16. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**setBreak**(*waitVarAddr*, breakClbk)
17. &nbsp;&nbsp;&nbsp;&nbsp;**Function breakClbk**(*storeCodeAddr*)
18. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**storeTraceTuple**(*DEP_STORE*, *storeCodeAddr*)

200ms). During this window, the initial watchpoint remains active to capture multiple unique store instructions, placing a breakpoint on each one. Second, to prevent a watchpoint from being held indefinitely by an unresolved dependency, we implement a *timestamp-based reclamation policy*. If the watchpoint pool is exhausted, this policy forcibly reclaims any active watchpoints that have exceeded a reservation timeout (e.g., 500ms).

# 4 Evaluation

Our evaluation uses three case studies to demonstrate how TAPESTRY's ability to visualize busy-waiting and blocking synchronization, along with their dependencies, can diagnose complex performance bugs in real-world applications.

## 4.1 Experimental settings

Our primary test machine is an 18-core, hyperthreaded Intel Xeon Gold 5220 (§4.3) with an 18-core, hyperthreaded 50GB KVM guest for the VM experiment (§4.4). Additionally, we use a dual-socket, 2×32-core AMD EPYC 7452 for the NUMA experiment (§4.2). All environments use Ubuntu 24.04 (Linux kernel 6.12.0, powersave governor), GCC 13.2.0, OpenMP 14.2.0, and the NAS Parallel Benchmarks 3.4.3 with the Class A dataset [27]. Instrumentation leverages e9patch v1.0.0 [12], and visualizations use Jgraph [30].

In TAPESTRY visualizations, the X-axis shows time (in seconds) and the Y-axis shows thread IDs. A black line represents a running thread, and a colored line above shows busy-waits. Arrows depict resolved dependencies, starting from the thread that resolved them. The critical path is highlighted in yellow. All reported metrics are medians over 10 runs.
<figure><img src="image_3.png" /><figcaption>Figure 1. Barriers in NAS/BT on a NUMA machine.</figcaption></figure>

<table><thead><tr><th>Bench.</th><th>Single</th><th>Parallel</th></tr></thead><tbody><tr><td>BT</td><td>2.67</td><td>5.72</td></tr><tr><td>CG</td><td>0.09</td><td>0.20</td></tr><tr><td>EP</td><td>0.25</td><td>0.52</td></tr><tr><td>FT</td><td>0.18</td><td>0.35</td></tr><tr><td>IS</td><td>0.02</td><td>0.05</td></tr><tr><td>LU</td><td>2.22</td><td>100.09</td></tr><tr><td>MG</td><td>0.14</td><td>0.26</td></tr><tr><td>SP</td><td>1.58</td><td>3.86</td></tr><tr><td>UA</td><td>3.58</td><td>7.23</td></tr></tbody></table>

(a) Single vs. Parallel.

<table><thead><tr><th>Bench.</th><th>BM</th><th>VM</th></tr></thead><tbody><tr><td>BT</td><td>13.22</td><td>11.94</td></tr><tr><td>CG</td><td>8.44</td><td>5.02</td></tr><tr><td>EP</td><td>0.53</td><td>0.45</td></tr><tr><td>FT</td><td>0.57</td><td>0.54</td></tr><tr><td>IS</td><td>0.23</td><td>0.16</td></tr><tr><td>LU</td><td>190.75</td><td>138.44</td></tr><tr><td>MG</td><td>2.51</td><td>1.6</td></tr><tr><td>SP</td><td>31.9</td><td>22.57</td></tr><tr><td>UA</td><td>300.2</td><td>185.7</td></tr></tbody></table>

(b) Bare Metal (BM) vs. VM.

<caption>Table 1. Execution time (s) of NAS in different scenarios.</caption>

## 4.2 Observing NUMA effects of spinning barriers

This experiment shows that TAPESTRY is precise enough to capture subtle performance effects such as thread delays caused by NUMA. We run the NAS/BT application on our dual-socket NUMA machine with 64 cores. We use OpenMP's active wait policy, meaning that all barriers use busy-waiting.

Figure 1 shows the visualization produced by TAPESTRY. For clarity, we disabled the rendering of dependency arrows, as showing up to $N-1$ arrows for a barrier would clutter the view; the single resolving store is instead marked with a di-amond symbol. The visualization clearly shows that threads on one NUMA node consistently complete their work and arrive at the barrier, where they begin busy-waiting, ear-lier than threads on the other node. CPU placement data from trace-cmd confirmed these visual groups directly cor-respond to the machine's two NUMA nodes. This work im-balance, a direct consequence of NUMA locality, leads to extended, wasteful busy-waiting for the faster threads. This case study shows that TAPESTRY precisely visualizes fine-grained, hardware-induced performance phenomena, pro-viding insights that can guide NUMA-aware optimizations.

<figure><img src="image_4.png" /></figure>

(a) Waiting dependencies and the highlighted critical path.

<figure><img src="image_5.png" /></figure>

(b) Zoomed-in view of the dependency chain in the red box.

<caption>Figure 2. Visualization of a single LU instance running under contention from a parallel LU instance.</caption>

## 4.3 Diagnosing pathological busy-waiting

This case study shows how TAPESTRY helps diagnose a se-vere scalability bug caused by the inappropriate use of busy-waiting in an overloaded system. By visualizing the complete set of synchronization dependencies, TAPESTRY reveals the root cause of a performance degradation that is difficult to pinpoint with conventional profilers.

We investigate a performance anomaly discovered while running NAS benchmarks in an environment simulating a multi-tenant cloud server. As shown in Table 1a, when running two instances of the same application in parallel with a blocking wait policy, most benchmarks exhibit an ex-pected $2 \times$ slowdown. LU, however, suffers a catastrophic $45 \times$ slowdown. To diagnose it, we trace one LU instance under contention created by running a second instance in parallel.

Figure 2a shows TAPESTRY's visualization. The zoomed-in view (Figure 2b) reveals a clear pattern of dependency chains ($T_{i+1} \rightarrow T_i \rightarrow T_{i-1}...$), which represent the application's critical path (highlighted in yellow). Ideally, these chains should be vertically aligned, indicating efficient handoffs. However, the visualization shows that preemption frequently breaks this alignment. A waiting thread can be descheduled, and if the dependency is resolved while it is preempted, the
thread cannot immediately proceed. This stall prevents it from resolving the next dependency in the chain, creating a visible gap in the visualization and a cascading delay down the pipeline. The global view (Figure 2a) confirms that this pathological pattern occurs across all busy-wait loops.

While performance degradation due to oversubscribing cores is a known issue, pinpointing the specific primitives at fault is non-trivial. TAPESTRY facilitates this diagnosis by visualizing the dependency chains that form the critical path. After we replace the ad-hoc busy-waiting in LU with blocking condition variables, the performance falls into the expected range. This case study highlights the power of TAPESTRY's dependency view in debugging complex performance bugs.

## 4.4 Faster busy-waiting in VMs vs. bare metal

This case study demonstrates TAPESTRY's ability to diagnose counterintuitive performance phenomena from hardware optimizations. We investigate why some NAS benchmarks run faster inside a VM than on bare metal when the physical host is overloaded (Table 1b). This setup simulates a common multi-tenant cloud scenario where co-located VMs contend for CPU cores.

We focus on BT, running two 36-thread instances on a 36-core machine, comparing two configurations: (i) both instances running directly on bare metal, and (ii) each instance running inside a separate VM, each with 36 virtual CPUs. The OpenMP runtime uses its default hybrid barrier, which busy-waits for a fixed number of iterations before blocking on a futex. In our visualizations, the blocking phase is colored red, and, as in the NUMA use case (§ 4.2), resolving stores are marked with diamond symbols.

Figure 3 reveals the root cause. On bare metal (Figure 3a), threads remain entirely in the busy-waiting phase of the barriers. In the VM (Figure 3b), however, threads busy-wait faster, frequently exhausting their iteration budget and falling back to blocking. Since blocking is more efficient in an overloaded system, the VM execution completes faster.

Further investigation reveals that the shorter busy-waiting time is due to PAUSE-Loop Exiting (PLE), a hardware feature from the Intel Virtual Machine Extensions (VMX). PLE triggers VM exits when the guest kernel executes spinloops in order to help the hypervisor mitigate guest-kernel lock holder/waiter preemption issues [33]. While PLE is not supposed to have an effect on userland spinloops, disabling it (with ple-gap=0) eliminates the performance gap.

To investigate further, we profile a 10⁹-iteration userland spinloop that uses PAUSE. Table 2 reports the results. The spinloop executes more than twice as fast in a VM with PLE enabled than on the host or in a VM with PLE disabled. The average CPU frequency of the core executing the spinloop is the same in all configurations, ruling out adaptive frequency scaling as the cause. The experiment does not trigger extra VM exits. The spinloop executes 5 instructions per iteration where it runs (host or guest). On the host and in the guest

<figure><img src="image_6.png" /><figcaption>(a) Trace of one of two parallel instances on bare metal.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(b) Trace of one of two parallel instances inside a separate VM.</figcaption></figure>

<table><caption>**Figure 3.** Comparing hybrid barrier behavior in the BT benchmark on bare metal vs. inside a VM.</caption><thead><tr><th rowspan="2">Config.</th><th rowspan="2">Rt (s)</th><th rowspan="2">f (GHz)</th><th colspan="2">10<sup>9</sup> Instr.</th><th colspan="2">10<sup>9</sup> PAUSEs</th></tr><tr><th>H</th><th>G</th><th>H</th><th>G</th></tr></thead><tbody><tr><td>H</td><td>14.12</td><td>3.89</td><td>5.0</td><td>0</td><td>1.0</td><td>0</td></tr><tr><td>G PLE</td><td>6.19</td><td>3.89</td><td>0</td><td>5.0</td><td>0</td><td>0</td></tr><tr><td>G no PLE</td><td>14.17</td><td>3.89</td><td>0</td><td>5.0</td><td>0</td><td>1.0</td></tr></tbody></table>

<caption>**Table 2.** Impact of PLE on a userland busy-wait loop with 10⁹ iterations (Rt=runtime, f=CPU frequency, H=host, G=guest).</caption>

without PLE, one of these instructions is a PAUSE. On the guest with PLE enabled, however, the instruction count per iteration remains 5, but no PAUSEs are executed. This contradicts the Intel documentation, which states that the PLE VM-execution control is ignored in userspace (ring > 0) [8, §36.7.3]. We experimented with multiple Intel Skylake and Cascade Lake machines; all exhibit this behavior.
## 4.5 Overhead

For all NAS benchmarks but LU, TAPESTRY's overhead is negligible (<1%). These benchmarks mainly synchronize through barriers, paying the tracing overhead only once per barrier. In contrast, LU, which has long 1-to-1 dependency chains, experiences a ~15% overhead, as it pays the tracing overhead for each dependency, and dependencies occur at a high frequency on the critical path. This overhead is significant as we use uprobes, which trigger costly software interrupts.

The overhead of the uprobe mechanism could be avoided in at least some cases by live patching the dependency store instruction. If the store instruction is large enough, it can be replaced by a JMP to a code trampoline. This trampoline would execute the original store logic, perform the tracing action, and then return control flow to the program. For instructions too small to be replaced by a JMP, more advanced live patching techniques, such as punning [6], would be required. We will investigate this approach in future work.

## 5 Related Work

Analyses have been developed to detect busy-waiting synchronization in order to reduce the set of interleavings that should be taken into account in static analyses, such as static race detection, or in testing. An early approach is that of Tian et al. [34], who used heuristics to find “spinning read” loops by detecting a threshold of repeated memory reads to the same memory location. Helgrind+ [17] uses a hybrid static-dynamic analysis of binaries to find and instrument candidate loops, allowing it to detect synchronization even if a loop executes only once. RAProducer uses trace analysis to recognize race- and bug-related elements, including synchronization through locks and shared variables. Other works have focused on analyzing busy-waiting synchronization patterns with a focus on application correctness. SyncFinder [37] and the more specialized BarrierFinder [36] are purely static approaches that aim to annotate code by matching patterns of ad-hoc synchronization. SyncTester [38] uses behavioral testing to infer synchronization dependencies. Unlike these works, TAPESTRY makes it possible to visualize busy-waiting as well as blocking synchronization in a specific run of an application without prior knowledge, revealing the impact of wait-for dependencies between threads on application performance.

DataCollider [13] is a race detector that uses hardware watchpoints like TAPESTRY, but for a different purpose. Specifically, to detect a race, DataCollider randomly samples a memory access, pauses the thread it originated from, and sets a watchpoint to detect a collision, i.e., a conflicting access from another thread in a small time window. In contrast, TAPESTRY begins with a known busy-wait loop and uses a watchpoint to find the resolving store that allows the waiting thread to proceed by satisfying the dependency. This enables TAPESTRY to construct a directed graph of dependencies that

can be studied by the user to identify and understand potential performance bottlenecks.

Traditional profilers and tracers [4, 7, 10, 14, 15, 20, 21, 29, 31, 32, 35] can help find a wide range of performance bottlenecks, but distinguishing busy-waiting and productive computation with these tools is either impossible or only achievable through indirect and imprecise measurements (e.g., high IPC), making it hard to identify the impact of busy-wait dependencies. Causal profilers such as Coz [9] can identify code on the critical path but require many speculative runs and, unlike TAPESTRY, do not produce a visualization of the dependency graph.

## 6 Conclusion

We have introduced TAPESTRY, a tracing framework that reveals inter-thread wait-for dependencies, dynamically switching between using hardware watchpoints and software breakpoints to efficiently support busy-waiting synchronization. TAPESTRY makes it possible to see how threads influence one another's progress, giving insights into the most critical performance bottlenecks in multithreaded applications.

TAPESTRY is available at https://gitlab.inria.fr/tapestry.

## Acknowledgments

We thank the anonymous reviewers for their valuable feedback. This work was partially supported by Agence Nationale de la Recherche convention ANR-23-PECL-0004 (PEPR Cloud, DiVa project) and Inria's Défi OS.

## References

[1] Gene M. Amdahl. 1967. Validity of the single processor approach to achieving large scale computing capabilities. In *Spring Joint Computer Conference (SJCC)*. Atlantic City, NJ, USA.

[2] Thomas E. Anderson. 1990. The performance of spin lock alternatives for shared-memory multiprocessors. *IEEE Trans. Parallel Distrib. Syst.* 1, 1 (Jan. 1990), 6-16.

[3] Oana Balmau, Rachid Guerraoui, Vasileios Trigonakis, and Igor Zablotchi. 2017. FloDB: Unlocking memory in persistent key-value stores. In *European Conference on Computer Systems (EuroSys)*. Belgrade, Serbia.

[4] Shirley Browne, Jack Dongarra, Nathan Garner, George Ho, and Philip Mucci. 2000. A portable programming interface for performance evaluation on modern processors. *Int. J. High Perform. Comput. Appl.* 14, 3 (Aug. 2000), 189-204.

[5] Irina Calciu, Siddhartha Sen, Mahesh Balakrishnan, and Marcos K. Aguilera. 2017. Black-box concurrent data structures for NUMA architectures. In *International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)*. Xi'an, China.

[6] Buddhika Chamith, Bo Joel Svensson, Luke Dalessandro, and Ryan R. Newton. 2017. Instruction punning: Lightweight instrumentation for x86-64. In *Conference on Programming Language Design and Implementation (PLDI)*. Barcelona, Spain.

[7] Intel Corporation. 2024. Intel VTune profiler. https://www.intel.com/content/www/us/en/developer/tools/oneapi/vtune-profiler.html.
[8] Intel Corporation. 2024. *Intel® 64 and IA-32 Architectures Software Developer's Manual*. Vol. 3C. https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html

[9] Charlie Curtsinger and Emery D. Berger. 2015. Coz: Finding code that counts with causal profiling. In *Symposium on Operating Systems Principles (SOSP)*. Monterey, CA, USA.

[10] Florian David, Gael Thomas, Julia Lawall, and Gilles Muller. 2014. Continuously measuring critical section pressure with the free-lunch profiler. In *Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA)*. Portland, OR, USA.

[11] Dave Dice and Alex Kogan. 2019. Compact NUMA-aware locks. In *European Conference on Computer Systems (EuroSys)*. Dresden, Germany.

[12] Gregory J. Duck, Xiang Gao, and Abhik Roychoudhury. 2020. Binary rewriting without control flow recovery. In *Conference on Programming Language Design and Implementation (PLDI)*. London, United Kingdom.

[13] John Erickson, Madan Musuvathi, Sebastian Burckhardt, and Kirk Olynyk. 2010. Effective data-race detection for the kernel. In *Symposium on Operating Systems Design and Implementation (OSDI)*. Vancouver, Canada.

[14] Susan L. Graham, Peter B. Kessler, and Marshall K. McKusick. 1982. Gprof: A call graph execution profiler. In *SIGPLAN Symposium on Compiler Construction (SIGPLAN)*. Boston, MA, USA.

[15] Brendan Gregg. 2016. The Flame Graph: This visualization of software execution is a new necessity for performance profiling and debugging. *Queue* 14, 2 (March 2016), 91–110.

[16] Timothy L. Harris. 2001. A pragmatic implementation of non-blocking linked-lists. In *International Symposium on Distributed Computing (DISC)*. Mesa, AZ, USA.

[17] Ali Jannesari and Walter F. Tichy. 2010. Identifying ad-hoc synchronization for enhanced race detection. In *International Parallel and Distributed Processing Symposium (IPDPS)*. Atlanta, GA, USA.

[18] Sanidhya Kashyap, Irina Calciu, Xiaohe Cheng, Changwoo Min, and Taesoo Kim. 2019. Scalable and practical locking with shuffling. In *Symposium on Operating Systems Principles (SOSP)*. Huntsville, Canada.

[19] Renaud Lachaize, Baptiste Lepers, and Vivien Quéma. 2012. MemProf: A memory profiler for NUMA multicore systems. In *USENIX Annual Technical Conference (ATC)*. Boston, MA, USA.

[20] Dmitry Levin et al. 2025. strace - Linux syscall tracer. https://strace.io/.

[21] John Levon et al. 2020. OProfile – A system profiler for Linux. https://oprofile.sourceforge.net/.

[22] Jean-Pierre Lozi, Florian David, Gaël Thomas, Julia Lawall, and Gilles Muller. 2012. Remote Core Locking: Migrating critical-section execution to improve the performance of multithreaded applications. In *USENIX Annual Technical Conference (ATC)*. Boston, MA, USA.

[23] Victor Luchangco, Dan Nussbaum, and Nir Shavit. 2006. A hierarchical CLH queue lock. In *International European Conference on Parallel Processing (Euro-Par)*. Dresden, Germany.

[24] Peter Magnusson, Anders Landin, and Erik Hagersten. 1994. Queue locks on cache coherent multiprocessors. In *International Parallel Processing Symposium (IPPS)*. Cancún, Mexico.

[25] John M. Mellor-Crummey and Michael L. Scott. 1991. Algorithms for scalable synchronization on shared-memory multiprocessors. *ACM Trans. Comput. Syst.* 9, 1 (Feb. 1991), 21–65.

[26] Maged M. Michael and Michael L. Scott. 1996. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In *Symposium on Principles of Distributed Computing (PODC)*. Philadelphia, PA, USA.

[27] NASA. 2024. NAS parallel benchmarks. https://www.nas.nasa.gov/software/npb.html.

[28] Mathias Payer, Enrico Kravina, and Thomas R. Gross. 2013. Lightweight memory tracing. In *USENIX Annual Technical Conference (ATC)*. San Jose, CA, USA.

[29] Linux perf wiki Contributors. 2024. perf: Linux profiling with performance counters. https://perf.wiki.kernel.org/.

[30] James S. Plank. 1992. Jgraph – A filter for plotting graphs in PostScript. In *USENIX Winter Technical Conference*. San Francisco, CA, USA.

[31] Lennart Poettering. 2009. Measuring lock contention. https://0pointer.de/blog/projects/mutrace.html.

[32] Steven Rostedt et al. 2025. trace-cmd. https://www.trace-cmd.org/.

[33] Boris Teabe, Vlad Nitu, Alain Tchana, and Daniel Hagimont. 2017. The lock holder and the lock waiter pre-emption problems: Nip them in the bud using informed spinlocks (I-Spinlock). In *European Conference on Computer Systems (EuroSys)*. Belgrade, Serbia.

[34] Chen Tian, Vijay Nagarajan, Rajiv Gupta, and Sriraman Tallam. 2008. Dynamic recognition of synchronization operations for improved data race detection. In *International Symposium on Software Testing and Analysis (ISSTA)*. Seattle, WA, USA.

[35] Valgrind Developers. 2025. Callgrind: A call-graph generating cache and branch prediction profiler. https://valgrind.org/docs/manual/cl-manual.html.

[36] Tao Wang, Xiao Yu, Zhengyi Qiu, Guoliang Jin, and Frank Mueller. 2020. BarrierFinder: Recognizing ad hoc barriers. *Empirical Software Engineering* 25, 6 (Nov. 2020), 4676–4706.

[37] Weiwei Xiong, Soyeon Park, Jiaqi Zhang, Yuanyuan Zhou, and Zhiqiang Ma. 2010. Ad hoc synchronization considered harmful. In *Symposium on Operating Systems Design and Implementation (OSDI)*. Vancouver, Canada.

[38] Xiang Yuan, Zhenjiang Wang, Chenggang Wu, Pen-Chung Yew, Wen-wen Wang, Jianjun Li, and Di Xu. 2013. Synchronization identification through on-the-fly test. In *International European Conference on Parallel Processing (Euro-Par)*. Aachen, Germany.