ABSTRACT Data races are among the most difficult multithreading bugs to find, due to their non‐deterministic nature. This and the increasing popularity of multithreaded programming have led to the need for practical automated data race detection. In this context, dynamic data race detectors have received more attention, compared to static tools, owing to their higher accuracy and scalability. Yet, state‐of‐the‐art dynamic data race detectors cannot be used in many real‐world testing scenarios, since they cause significant slowdown and memory overhead. Notably, ThreadSanitizer (TSan), the default dynamic data race detector in both clang and gcc compilers, is reported to typically impose a – slowdown and a – memory overhead, which is not tolerable in many industrial use cases. To address this issue, this paper introduces ThreadMonitor (TMon), a low‐overhead postmortem data race detector for multithreaded C/C++ programs that use the Pthread library. At runtime, TMon traces the information required for detecting occurrences of data races (i.e., shared memory accesses and timing constraints among threads) using Intel Processor Trace (Intel PT), a non‐intrusive hardware feature dedicated to tracing software execution. Thereafter, its postmortem analyzer examines the collected trace data to determine whether the traced program execution exhibited data races, performing a verification similar to that carried out by TSan at runtime. Introducing algorithmic improvements in its postmortem analyzer, TMon can further achieve a higher data race detection coverage compared to TSan. TMon has no direct data memory overhead, incurs minimal instruction memory overhead, and causes a very small slowdown, making it an ideal choice in test environments with limited resources.

Dynamic Binary Instrumentation (DBI) in user space often suffers from low probe insertion success rates and high execution overhead, due to challenges in handling the compact instruction layouts ($\lt $5 bytes) and complex trampoline placement constraints. Existing techniques are either limited in scope, incur high runtime overhead, or rely on heavyweight code relocation. This paper introduces NOProbe, a lightweight, user-space DBI framework that enables safe and efficient probe insertion using two novel strategies. The first strategy locates trampoline sites by leveraging compiler-generated NOP paddings; the second employs pseudo-NOP instructions to support trampoline placement even when instructions overlap. Additionally, we propose a thread-safe patching algorithm,lock-redirect-load-arm, for safe runtime code modification. Experimental results show that NOProbe achieves 97%-99% probe effectiveness, reduces probe insertion latency, and maintains very low per-probe execution overhead, even under high probe density and multithreaded workloads.

[Problem] As industries increasingly depend on complex software systems, efficient log analysis is essential for maintaining reliability and privacy. However, Identifying problems through logs is often time-consuming and costly for developers. [Background] Large language models (LLMs) can automate parts of log analysis, but challenges like limited computational resources and the frequent need to retrain LLMs due to the dynamic nature of software logs persist. External LLMs, such as GPTs, along with in-context learning techniques, can help reduce some of these issues, but other challenges, including token limitations, high token costs, and data privacy, remain. [Method] To tackle these challenges, we developed an automated pipeline that extracts log files and employs in-context learning, allowing the model to efficiently adapt to changes without extensive retraining. Our approach introduces a novel flame-graph-like method that reduces token usage, thereby lowering token-related costs and response latency while maintaining high accuracy. [Results] This solution allows industries to automate log analysis, minimize system downtime, and enhance performance, all while keeping data privacy and maintaining operational efficiency. [Conclusion] Our flame-graph-like methodology reduces input tokens by 93.61 % and processing latency by 77.45 %. Our anonymization results show an improvement of 138.63 % over the baseline. This industrial experience report presents our approach to allow industries to balance token costs, maintain response accuracy, and ensure data privacy while relying on external LLMs without the need to manage computational resources directly.

[Context] Distributed cloud-native systems operated by our industrial partners, including Ericsson and Ciena, generate millions of trace spans daily. Capturing and analyzing this data at full granularity is infeasible due to excessive storage and computational overhead. [Objective] We aim to enable fast and accurate RCA with minimal trace volume and system overhead, quickly pinpointing the service causing a latency spike, making it practical for large-scale production environments. [Method] We present HybridRCA, a critical-path-aware RCA pipeline that (1) extracts the critical path of each request, (2) applies a PageRank-weighted spectrum analysis to identify suspicious spans, and (3) collects system metrics only for targeted spans. [Results] Across three microservice benchmarks (HotRod, TrainTicket, OnlineBoutique), HybridRCA improves recall by an average of$\text{0.45 \%}$over the best existing methods, while analyzing up to 22.6 % fewer spans and reducing kernel-level storage usage by over 99%. [Significance] HybridRCA addresses key observability challenges faced by our industry partners, enabling scalable, low-overhead RCA in real-world distributed systems.

Abstract Due to the ever‐increasing number of computer nodes in distributed systems, efficient and effective tools have become crucial for their analysis. Although several efficient methods have been proposed to monitor and profile distributed systems, tracing remains the most effective solution for in‐depth system analysis. Tracing is the act of collecting a trace, which is a sequence of low‐level events generated by the kernel or the userspace. After data collection, the most important part is the event analysis. The paradigm and choice of graphs determine the ability of the user to detect abnormal behaviors and identify their root cause. Although tracing is a highly effective approach to analyzing complex systems, the scalability of the current analysis tools is limited. As a consequence, tracing is often impractical for large distributed systems. This paper identifies the shortcomings of the current approaches, most notably the critical path computation and the trace file transfer between nodes. Then, this paper proposes new solutions to these drawbacks, most notably a distributed algorithm to compute the critical path, that does not aggregate all traces in a single node, and an efficient architecture to perform tracing on distributed systems. These new solutions are made publically available.

Summary Today, the noticeable tendency of the software industry to break large software projects into loosely coupled modules through a microservice‐based architecture is more than ever. This is because of advantages such as scalability, independence, smaller and faster deployments, improved fault isolation, and flexibility. On the other hand, it should be noted that with the growth of microservice architecture, new complexities have emerged. We need to have a mature DevOps team to handle the complexity involved in maintaining and supporting systems, namely functional and non‐functional monitoring (anomaly monitoring and detection). This challenge can lead to a lot of software development time being spent monitoring and identifying anomalies. Existing approaches are not accurate enough to identify anomalies, and if they are able to identify them, they are unable to identify the category of the anomaly. Our approach in this research is to use distributed tracing with the help of machine learning algorithms to identify performance anomalies, the exact location of each anomaly, and predict its category. In this research, we implemented a software based on microservice architecture and then created a variety of anomalies over time (e.g., physical resources, virtual resources, database, application) to be able to evaluate the proposed model. The resulting dataset is publicly available. Our simulation results show that the proposed model is able to accurately identify the anomalies with 98% accuracy and their category with 99% accuracy.

Abstract As a key part of model‐driven development, modeling allows users to represent the application workflow or to automatically generate source code. This is convenient for developers, particularly to create or improve real‐time applications embedded in complex systems. Multicore systems are difficult to debug because the concurrently running processes can interfere with each other. In real‐time systems, timing constraints add to the complexity, invalidating results when a deadline is missed. Tracing is usually the most accurate and reliable tool to study the runtime behaviour of those applications. However, the interpretation of voluminous detailed execution traces requires a deep understanding of the operating system and application behaviour, and time to dig through the millions of trace events.In this paper, we present the use of model‐based constraints on top of user‐space and kernel traces to provide weighted analysis results. Our algorithms have been applied to multiple traces showing common problems for multi‐core real‐time systems. The experimental results show that our algorithms can quickly identify many different types of problems with a low runtime, even for traces with millions of events, thus helping to save time when analyzing thousands of trace events for complex systems.

Summary As the complexity of the toolchain increases for heterogeneous CPU‐GPU systems, the needs for comprehensive tracing and debugging tools also grows. Heterogeneous platforms bring new possibilities but also new performance issues that are hard to detect. Some techniques that were used on CPU programs are now adapted to GPUs. However, there are some concepts specific to GPUs, like SIMD processing, and the effects of the close interactions between the CPUs and the GPUs, with shared virtual memory and user‐level queues. Multiple sources of data need to be extracted and correlated to obtain a more global view of the performance. In this article, we introduce a novel approach for measuring and visualizing performance defects inside CPU‐GPU programs by combining kernel events, compute kernel events, user API calls and memory transfers. We created two new views that combine this information, to help provide a global view. This framework uses the open source user queue system described in the HSA standard. It can easily be adapted to any user queue system for heterogeneous computing devices. We compare this framework with current existing tools and test it against the Rodinia benchmark. We look at how the execution behavior affects the tracing and profiling overhead and we use Trace Compass to visualize the resulting trace.

The dynamic nature of applications in Virtual Machines (VMs) and the increasing demand for virtualized systems make the analysis of dynamic environments critical to achieve efficient operation of such complex distributed systems. In this article, we propose a precise host-based tracing and analysis method to retrieve execution flows, and dependency flows from virtualized environments, regardless of the level of nested virtualization. Given a host operating system level trace, the Any-Level vCPU Detection (ASD) algorithm and Guest Thread-state Analysis (GTA) algorithm detect the different states of vCPUs and threads for arbitrary nesting depths. Then, the Execution-graph Construction (HEC) algorithm extracts the waiting / wake-up dependencies chains out of the running processes across VMs, for any level of virtualization in a transparent manner. The process dependency graph, vCPU state, and VM process state are displayed in an interactive trace viewer, Trace Compass, for further inspection. Our proposed VM trace analysis algorithms have been open-sourced for further enhancements and collaborative research and development. Our new techniques were evaluated with workloads generated using several well-known server applications (e.g., Hadoop, Apache, MySQL, Linux apt-get, and IMS network). The proposed approaches are based on host hypervisor tracing, which brings a lower tracing overhead (around 1 percent), is easier to deploy, and presents fewer security issues as compared to other approaches.

It is important to model and understand an application or system runtime behavior to identify potential performance problems. Execution tracing, the basis of various dynamic analysis methods includes the collection of events, metrics, and statistics about the runtime behaviors of systems and applications. However, comprehensive execution tracing can result in very large trace files, most of which are irrelevant to the problem at hand. This is compounded by the inflexibility and complexity of common tools in how the user specifies what to capture, making the collection of relevant statistics difficult. While existing solutions allow for an adaptive collection of metrics and statistics, they often require users to write large and complex scripts in a domain-specific language. In this paper, we propose a state machine based modeling tool that simplifies the creation of user-defined and data-driven trace-based analyses. The proposed method combines advanced kernel-space and user-space execution trace events with powerful and adaptable modeling in order to automatically generating event-based analysis based on users’ specific requirements and problems. The difficulty and complexity of user-defined event tracing is drastically reduced. We demonstrate the efficiency, effectiveness, and simplicity of our proposed tool through real use cases of multi-level dynamic execution tracing in the Linux kernel.

Summary Distributed storage systems are commonly used in modern computing. They are highly scalable and offer data replication and fault tolerance. The complexity of those systems makes them difficult to debug using traditional tools. The existing tools are able to evaluate the overall performance of such systems but they do not provide enough information to find the root cause of performance issues. In this article, we propose a tracing‐based performance analysis framework for storage clusters. We use a tracing strategy that reduces the tracing overhead in production systems. The traces collected from the different storage nodes are correlated and used to generate a data model that represents the cluster. Userspace tracing is used to gather data from the storage daemons, while Kernel tracing is used to provide detailed information about operating system internals such as disk queues, network queues and process scheduling. Efficient data structures are used to store the model and to generate metrics and graphical views. Our tool is used in different real world scenarios and is able to investigate interesting performance problems including I/O latencies, data replication and storage nodes failures.

Cloud computing enables on-demand access to remote computing resources. It provides dynamic scalability and elasticity with a low upfront cost. As the adoption of this computing model is rapidly growing, this increases the system complexity, since virtual machines (VMs) running on multiple virtualization layers become very difficult to monitor without interfering with their performance. In this paper, we present hypertracing, a novel method for tracing VMs by using various paravirtualization techniques, enabling efficient monitoring across virtualization boundaries. Hypertracing is a monitoring infrastructure that facilitates seamless trace sharing among host and guests. Our toolchain can detect latencies and their root causes within VMs, even for boot-up and shutdown sequences, whereas existing tools fail to handle these cases. We propose a new hypervisor optimization, for handling efficient nested paravirtualization, which allows hypertracing to be enabled in any nested environment without triggering VM exit multiplication. This is a significant improvement over current monitoring tools, with their large I/O overhead associated with activating monitoring within each virtualization layer.

Bug tracking systems (BTS) are widely used in software projects. An important task in such systems consists of identifying duplicate bug reports, i.e., distinct reports related to the same software issue. For several reasons, reporting bugs that have already been reported is quite frequent, making their manual triage impractical in large BTSs. In this paper, we present a novel deep learning network based on soft-attention alignment to improve duplicate bug report detection. For a given pair of possibly duplicate reports, the attention mechanism computes interdependent representations for each report, which is more powerful than previous approaches. We evaluate our model on four well-known datasets derived from BTSs of four popular open-source projects. Our evaluation is based on a ranking-based metric, which is more realistic than decision-making metrics used in many previous works. Achieved results demonstrate that our model outperforms state-of-the-art systems and strong baselines in different scenarios. Finally, an ablation study is performed to confirm that the proposed architecture improves the duplicate bug reports detection.

This paper addresses the challenge of understanding the waiting dependencies between the threads and hardware resources required to complete a task. The objective is to improve software performance by detecting the underlying bottlenecks caused by system-level blocking dependencies. In this paper, we use a system level tracing approach to extract a Waiting Dependency Graph that shows the breakdown of a task execution among all the interleaving threads and resources. The method allows developers and system administrators to quickly discover how the total execution time is divided among its interacting threads and resources. Ultimately, the method helps detecting bottlenecks and highlighting their possible causes. Our experiments show the effectiveness of the proposed approach in several industry-level use cases. Three performance anomalies are analysed and explained using the proposed approach. Evaluating the method efficiency reveals that the imposed overhead never exceeds 10.1%, therefore making it suitable for in-production environments.

An agent-less technique to understand virtual machines (VMs) behavior and their changes during the VM life-cycle is essential for many performance analysis and debugging tasks in the cloud environment. Because of privacy and security issues, ease of deployment and execution overhead, the method preferably limits its data collection to the physical host level, without internal access to the VMs. We propose a host-based, precise method to recover execution flow of virtualized environments, regardless of the level of virtualization. Given a VM, the Any-Level VM Detection Algorithm (ADA) and Nested VM State Detection (NSD) Algorithm compute its execution path along with the state of virtual CPUs (vCPUs) from the host kernel trace. The state of vCPUs is displayed in an interactive trace viewer (TraceCompass) for further inspection. Then, a new approach for profiling threads and processes inside the VMs is proposed. Our proposed VM trace analysis algorithms have been open-sourced for further enhancements and to the benefit of other developers. Our new techniques are being evaluated with workloads generated by different benchmarking tools. These approaches are based on host hypervisor tracing, which brings a lower overhead (around 1 percent) as compared to other approaches.

The efficient operation and resource management of multi-tenant data centers hosting thousands of services is a demanding task, that requires precise and detailed information regarding the behaviour of each and every virtual machine (VM). Often, coarse measures such as CPU, memory, disk and network usage by VMs are considered in grouping them onto the same physical server, as detailed measures would require access to the guest operating system (OS), which is not feasible in a multi-tenant setting. In this paper, we propose host-level hypervisor tracing as a non-intrusive means to extract useful features, that can provide for fine grain characterization of VM behaviour. In particular, we extract VM blocking periods as well as virtual interrupt injection rates to detect multiple levels of resource intensiveness. In addition, we consider the resource contention rate due to other VMs and the host, along with reasons for exit from non-root to root privileged mode, revealing useful information about the nature of the underlying VM workload. We also use tracing to get information about the rate of process and thread preemption in each VM, extracting process and thread contention as another feature set. We then employ various feature selection strategies and assess the quality of the resulting workload clustering. Notably, we adopt a two-stage feature selection approach in addition to a one shot clustering scheme. Moreover, we consider inter-cluster and intra-cluster similarity metrics, such as the silhouette score, to discover distinct groups of workloads as well as workload groups with significant overlap. This information can be used by 1) data center administrators to gain deeper visibility into the nature of various VMs running on their infrastructure, 2) performance engineers to assist root cause analysis of VM issues and 3) IaaS providers to help in resource management based on VM behavior.

Summary In this paper, we propose LTTng‐HSA, a set of tools that allow for the collection of a single, unified software graphics processing unit (GPU) trace in ROCr, a Heterogeneous System Architecture (HSA)‐based API and runtime. HSA is a cross‐vendor standard facilitating the programming of heterogeneous systems that include CPUs, GPUs, and possibly other types of devices. Our open‐source solution is generic and easily adaptable to diverse GPU runtimes or APIs. Using Linux Trace Toolkit Next Generation (LTTng), a highly efficient Linux tracer, it collects different types of events over multiple executions of an application and aims to gather all the data into a single trace, offering an easy way to generate GPU‐related traces. Our instrumentation is achieved simply by preloading libraries, without recompiling the target application, which makes it flexible and easy to use. The resulting traces, which include API call stack information, GPU hardware metrics, command queue, and compute kernel profiling, are well adapted for postprocessing and further analysis. Our solution also includes tracing data from the Linux kernel and proposes views for Trace Compass, an interactive trace visualizer.

Heterogeneous multi-core and many-core processors are increasingly common in personal computers and industrial systems. Efficient software development on these platforms needs suitable debugging tools, beyond traditional interactive debuggers . An alternative, to interactively follow the execution flow of a program, is tracing within the debugging environment , as long as the tracer has a minimal overhead. In this paper, the dynamic tracing infrastructure of GNU debugger (GDB) was investigated to understand its performance limitations. Thereafter, we propose an improved architecture for dynamic tracing on many-core processors within GDB, and demonstrate its scalability on highly parallel platforms. In addition, the scalability of the thread data collection and presentation component was studied and new views were proposed within the Eclipse Debugging Service Framework and the Trace Compass visualization tool. With these scalability enhancements, debuggers such as GDB can more efficiently help debugging multi-threaded programs on heterogeneous many-core processors composed of multi-core CPUs, and GPUs containing thousands of cores.

Summary Tracing is often the most effective technique for analyzing the performance of complex multithreaded applications. This paper presents an improvement on existing techniques for dynamic tracepoint insertion. To add a tracepoint, the technique inserts a jump at the tracing point, possibly replacing several shorter instructions. This jump embeds trap instructions inside its offset at the address of every replaced instruction. This makes the jump thread safe if any thread is about to execute a replaced instruction. It also makes it jump safe if a jump landing pad is at one of the replaced instructions. In both cases, a trap will be raised, and the thread can be redirected to the out‐of‐line equivalent instruction. The use of a jump instead of a trap to execute the tracepoint improves the performance of the execution. It also adds the flexibility to place the tracepoint at almost any instruction, since multiple instructions can be replaced atomically and safely. The downside of this technique is the increased memory usage, since it requires unaligned allocations with high external fragmentation.

Performance has become an important and difficult issue for software development and maintenance on increasingly parallel systems. To address this concern, teams of developers use tracing tools to improve the performance, or track performance related bugs. In this work, we developed an automated technique to find the root cause of performance issues, which does not require deep knowledge of the system. This approach is capable of highlighting the performance cause, using a comparative methodology on slow and fast execution runs. We applied the solution on some use cases and were able to find the specific cause of issues. Furthermore, we implemented the solution in a framework to help developers working with similar problems.

Summary Block devices such as magnetic disks are nonvolatile data storage devices that transfer data in fixed‐size chunks. They are the main nonvolatile memory that holds the file system, and they are also used in virtual memory mechanisms such swapping and page fault handling. Investigating storage performance issues requires a full insight into the operating system internals. Kernel tracing offers an efficient mechanism to gather information about the storage subsystem at runtime. Still, the tracing output is often huge and difficult to analyze manually. In this paper, we introduce a framework to compute meaningful storage performance metrics from low‐level trace events generated by LTTng. A stateful approach is used to model the state of the storage subsystem. Efficient data structures and algorithms are proposed to offer a reasonable response time, allowing the user to navigate throughout the trace and to retrieve metrics from any time range. The framework includes a visualization system that provides different graphical views that represent the collected information in a convenient way. These views are synchronized together, forming a comprehensive perspective that makes storage performance investigation a much more comfortable task. Different use cases are presented to show the usefulness of the framework in real‐world applications.

Summary Hardware tracing has emerged as a low‐cost technique to analyze systems at a very fine granularity, thus mitigating the need for software‐only trace approaches for performance analysis. State‐of‐the‐art trace hardware on modern Intel and ARM processors allows recording change‐of‐flow instructions in executable binaries, such as branches, for off‐line reconstruction. This conventional userspace–based trace reconstruction, however, is not robust enough in the common scenarios where runtime code is being generated, compiled, and executed. We therefore propose a novel kernel‐assisted mechanism called FlowJIT to reconstruct hardware traces with a low overhead of around 1.3 μs per code page modification event. We further show the efficacy or our technique with the help of 2 illustrative usecases that cover the JIT compiled code scenario and a same‐page instruction modification scenario. Our implementation has been open sourced as a patch for the Linux kernel.

Nowadays, nested VMs are often being used to address compatibility issues, security concerns, software scaling and continuous integration scenarios. With the increased adoption of nested VMs, there is a need for newer techniques to troubleshoot any unexpected behavior. Because of privacy and security issues, ease of deployment and execution overhead, these investigation techniques should preferably limit their data collection in most cases to the physical host level, without internal access to the VMs. This paper introduces the Nested Virtual Machine Detection Algorithm (NDA) - a host hypervisor based analysis method which can investigate the performance of nested VMs. NDA can uncover the CPU overhead entailed by the host hypervisor and guest hypervisors, and compare it to the CPU usage of Nested VMs. We further developed several graphical views, for the TraceCompass trace visualization tool, to display the virtual CPUs of VMs and their corresponding nested VMs, along with their states. These approaches are based on host hypervisor tracing, which brings a lower overhead (around 1%) as compared to other approaches. Based on our analysis and the implemented graphical views, our techniques can quickly detect different problems and their root causes, such as unexpected delays inside nested VMs.

Performance is an important aspect and critical requirement in multi-process software architecture systems such as Google Chrome. While interacting closely with members of the Google Chrome engineering team, we observed that they face a major challenge in detecting performance deviations between releases, because of their very high release frequency and therefore limited amount of data on each. This paper describes a deep analysis on the data distributions followed by a comparative approach using median based confidence interval for software evaluation. This technique is capable of detecting performance related deviations. It is substantially different from the standard confidence interval, in that it can be used in the presence of outliers and random external influences since the median is less influenced by them. We conducted a bottom-up analysis, using stack traces in a very large pool of releases. The results show that our approach can accurately localize performance deviations at a function-level granularity, using a very small number of trace samples, nearby 5 runs.

Summary Dynamic analysis through execution traces is frequently used to analyze the runtime behavior of software systems. However, tracing long running executions generates voluminous data, which are complicated to analyze and manage. Extracting interesting performance or correctness characteristics out of large traces of data from several processes and threads is a challenging task. Trace abstraction and visualization are potential solutions to alleviate this challenge. Several efforts have been made over the years in many subfields of computer science for trace data collection, maintenance, analysis, and visualization. Many analyses start with an inspection of an overview of the trace, before digging deeper and studying more focused and detailed data. These techniques are common and well supported in geographical information systems, automatically adjusting the level of details depending on the scale. However, most trace visualization tools operate at a single level of representation, which are not adequate to support multilevel analysis. Sophisticated techniques and heuristics are needed to address this problem. Multi‐scale (multilevel) visualization with support for zoom and focus operations is an effective way to enable this kind of analysis. Considerable research and several surveys are proposed in the literature in the field of trace visualization. However, multi‐scale visualization has yet received little attention. In this paper, we provide a survey and methodological structure for categorizing tools and techniques aiming at multi‐scale abstraction and visualization of execution trace data and discuss the requirements and challenges faced to be able to meet evolving user demands.

Summary Event tracing is a reliable and a low‐intrusiveness method to debug and optimize systems and processes. Low overhead is particularly important in embedded systems where resources and energy consumption is critical. The most advanced tracing infrastructures achieve a very low footprint on the traced software, bringing each tracepoint overhead to less than a microsecond. To reduce this still non‐negligible impact, the use of dedicated hardware resources is promising. In this paper, we propose complementary methods for tracing that rely on hardware modules to assist software tracing. We designed solutions to take advantage of CoreSight STM, CoreSight ETM, and Intel BTS, which are present on most newer ARM‐based systems‐on‐chip and Intel x86 processors. Our results show that the time overhead for tracing can be reduced by up to 10 times when assisted by hardware, as compared to software tracing with LTTng, a high‐performance tracer for Linux. We also propose a modification to the Perf tool to speed BTS execution tracing up to 65%.

Tracing allows the analysis of task interactions with each other and with the operating system. Locating performance problems in a trace is not trivial because of their large size. Furthermore, deep knowledge of all components of the observed system is required to decide whether observed behavior is normal. We introduce TraceCompare, a framework that automatically identifies differences between groups of executions of the same task at the user space and kernel levels. Many performance problems manifest themselves as variations that are easily identified by our framework. Our comparison algorithm takes into account all threads that affect the completion time of analyzed executions. Differences are correlated with application code to facilitate the correction of identified problems. Performance characteristics of task executions are represented by a new data structure called enhanced calling context tree (ECCT). We demonstrate the efficiency of our approach by presenting four case studies in which TraceCompare was used to uncover serious performance problems in enterprise and open source applications, without any prior knowledge of their codebase. We also show that the overhead of our tracing solution is between 0.2 and 9 percent depending on the type of application.

Summary Detecting latency‐related problems in production environments is usually carried out at the application level with custom instrumentation. This is enough to detect high latencies in instrumented applications but does not provide all the information required to understand the source of the latency and is dependent on manually deployed instrumentation. The abnormal latencies usually start in the operating system kernel because of contention on physical resources or locks. Hence, finding the root cause of a latency may require a kernel trace. This trace can easily represent hundreds of thousands of events per second. In this paper, we propose and evaluate a methodology, efficient algorithms, and concurrent data structures to detect and analyze latency problems that occur at the kernel level. We introduce a new kernel‐based approach that enables developers and administrators to efficiently track latency problems in production and trigger actions when abnormal conditions are detected. The result of this study is a working scalable latency tracker and an efficient approach to perform stateful tracing in production. Copyright © 2016 John Wiley & Sons, Ltd.

We propose a new class of profiler for distributed and heterogeneous systems. In these systems, a task may wait for the result of another task, either locally or remotely. Such wait dependencies are invisible to instruction profilers. We propose a host-based, precise method to recover recursively wait causes across machines, using blocking as the fundamental mechanism to detect changes in the control flow. It relies solely on operating system events, namely scheduling, interrupts and network events. It is therefore capable of observing kernel threads interactions and achieves user-space runtime independence. Given a task, the algorithm computes its active path from the trace, which is presented in an interactive viewer for inspection. We validated our new method with workloads representing major architecture and operating conditions found in distributed programs. We then used our method to analyze the execution behavior of five different distributed systems. We found that the worst case tracing overhead for a distributed application is 18 percent and that the typical average overhead is about 5 percent. The analysis implementation has linear runtime according to the trace size.

Summary Execution trace logs are used to analyze system run‐time behaviour and detect problems. Trace analysis tools usually read the input logs and gather either a detailed or brief summary of them to later process and inspect in the analysis steps. However, continuous and lengthy trace streams contained in the live tracing mode make it difficult to indefinitely record all events or even a detailed summary of the whole stream. This situation is further complicated when the system aims to compare different parts of the trace and provide a multilevel and multidimensional analysis. This paper presents an architecture with corresponding data structures and algorithms to process stream events, generate an adequate summary—detailed enough for recent data and succinct enough for old data—and organize them to enable an efficient multilevel and multidimensional analysis, similar to online analytical processing analyses in the database applications. The proposed solution arranges data in a compact manner using interval forms and enables the range queries for any arbitrary time durations. Because this feature makes it possible to compare of different system parameters in different time areas, it significantly influences the system's ability to provide a comprehensive trace analysis. Although the Linux operating system trace logs are used to evaluate the solution, we propose a generic architecture that can be used to summarize various types of stream data. Copyright © 2014 John Wiley & Sons, Ltd.

Read-copy update (RCU) is a synchronization technique that often replaces reader-writer locking because RCU's read-side primitives are both wait-free and an order of magnitude faster than uncontended locking. Although RCU updates are relatively heavy weight, the importance of read-side performance is increasing as computing systems become more responsive to changes in their environments. RCU is heavily used in several kernel-level environments. Unfortunately, kernel-level implementations use facilities that are often unavailable to user applications. The few prior user-level RCU implementations either provided inefficient read-side primitives or restricted the application architecture. This paper fills this gap by describing efficient and flexible RCU implementations based on primitives commonly available to user-level applications. Finally, this paper compares these RCU implementations with each other and with standard locking, which enables choosing the best mechanism for a given workload. This work opens the door to widespread user-application use of RCU.

In many existing synchronization protocols within wireless sensor networks, the effect of routing algorithm in synchronization precision of two remote nodes is not being considered. In several protocols such as SLTP, this issue is considered for local time estimation of a remote node. Cluster creation is according to ID technique. This technique incurs an increase in cluster overlapping and eventually the routing algorithm will be affected and requires more hops to move from one cluster to another remote cluster. In this article, we present L-SYNC method, which creates large degree clusters for wireless sensor networks synchronization. Using large degree clustering, L-SYNC can reduce path hops. Also, LSYNC uses linear regression method to calculate clock offset and skew in each cluster. Therefore, it is capable to compute skew and offset intervals between each node and its head cluster and, in other words, it can estimate the local time of remote nodes in future and past. To estimate the local time for remote nodes, routing algorithm is used and conversion technique is performed in each time changing hop. The fewer L-SYNC hops could increase the precision. Simulation results illustrate that monotonous clustering formation can increase the precision in synchronization. However, more overhead and time period are needed for clustering formation.

Abstract To effectively trace an operating system, a performance monitoring and debugging infrastructure needs the ability to trace various execution contexts. These contexts range from kernel running as a thread toNon‐Maskable Interrupt(NMI) contexts. Given that any part of the kernel infrastructure used by a kernel tracer could lead to infinite recursion if traced, and because most kernel primitives require synchronization unsuitable for some execution contexts, all interactions of the tracing code with the existing kernel infrastructure must be considered in order to correctly inter‐operate with the existing operating system kernel. This paper presents a new low overhead tracing mechanism and motivates the choice of synchronization sequences suitable for operating system kernel tracing, namelylocal atomic instructionsas main buffer synchronization primitive and theRead–Copy Update(RCU) mechanism to control tracing. It also proposes a wait‐free algorithm extending the time‐base needed by the tracer to 64‐bit on architectures that lack hardware 64‐bit time‐base support. Copyright © 2010 John Wiley & Sons, Ltd.

Traditionally the telecom industry has used clusters to meet its carrier-class requirements of high availability, reliability, and scalability, while relying on cost-effective hardware and software. Efficient cluster security is now an essential requirement and has not yet been addressed in a coherent fashion on clustered systems. This paper presents an approach for distributed security architecture that supports advanced security mechanisms for current and future security needs, targeted for carrier-class application servers running on clustered systems.

Large multi-platform, multi-million lines of codes software systems evolve to cope with new platform or to meet user ever changing needs. While there has been several studies focused on the similarity of code fragments or modules, few studies addressed the need to monitor the overall system evolution. Meanwhile, the decision to evolve or to re-factor a large software system needs to be supported by high level information, representing the system overall picture, abstracting from unnecessary details. This paper proposes to extend the concept of similarity of code fragments to quantify similarities at the release/system level. Similarities are captured by four software metrics representative of the commonalities and differences within and among software artifacts. To show the feasibility of characterizing large software system with the new metrics, 365 releases of the Linux kernel were analyzed. The metrics, the experimental results as well as the lessons learned are presented in the paper.

In the context of software quality assessment, the paper proposes two new kinds of data which can be extracted from source code. The first, definitely blocked statements, can never be executed because preceding code prevents the execution of the program. The other data, called possibly blocked statements, may be blocked by blocking code. The paper presents original flow equations to compute definitely and possibly blocked statements in source code. The experimental context is described and results are shown and discussed. Suggestions for further research are also presented.

Conditional compilation is one of the most powerful parts of a C/C++ environment available for building software for different platforms with different feature sets. Although conditional compilation is powerful, it can be difficult to understand and is error-prone. In large software systems, file inclusion, conditional compilation and macro substitution are closely related and are often largely interleaved. Without adequate tools, understanding complex header files is a tedious task. This practice may even be complicated as the hierarchies of header files grow with projects. This paper presents our experiences of studying conditional compilation based on the symbolic execution of preprocessing directives. Our two concrete goals are: for any given preprocessor directive or C/C++ source code line, finding the simplest sufficient condition to reach/compile it, and finding the full condition to reach/compile that code line. Two different strategies were used to achieve these two goals. A series of experiments conducted on the Linux kernel are presented.

The proliferation of electronic document formats impedes the dissemination and management of documents. Indeed, a common format with structural information is required to obtain document indexing and navigation. While in some formats it is easy to decode and preserve the document structure information, often the only easily obtainable representation is Postscript, where only the geometrical information remains. Even if an organization is willing to convert all its document producing activities to a structure preserving format such as HTML, the existing documents need to be converted. The paper addresses the difficult problem of extracting the structure of a document from a geometrical representation. An interactive tool to extract the document content and structure from a geometric representation (Postscript) has been developed. It successfully analyzes several documents produced with different tools, and produces structural information using the HyperText Markup Language (HTML). The end user, when presented with the extracted document structure, can interactively modify it, if needed. The tool is easily extended to recognize new constructs and is aimed at organizations needing to convert numerous documents for searching and browsing on intranets or on the Internet.

In this paper, we examine the impact of using the hierarchy of the design and multiple delay models defined at different abstraction levels to speed up the timing performance evaluation of VLSI circuits. The algorithms implemented in the Dynamic and Hierarchical Timing Analysis (DHTA) tool are described. DHTA rapidly identifies the critical portions of the circuit at high hierarchical levels with rough delay models. These portions are then successively studied at more detailed levels for maximal accuracy. The effects on processing time of exploiting the design hierarchy and using several delay models are characterized. The implementation of DHTA demonstrates experimentally the benefits of using a mixed-mode approach for timing analysis. We show that considering all available hierarchical levels may degrade the computing time and heuristics are proposed to select the hierarchical levels which generally lead to a speed-up.

The authors present three algorithms for efficient worst-case delay estimation in transistor groups using transistor-level delay models and timing simulation techniques. The first algorithm, dynamic path selection (DPS), determines the path with the longest delay in a transistor group. If the group consists of series-parallel transistor combinations, the time complexity is linear. The second algorithm, delay subnetwork enumeration (DSE), complements the DPS method by taking into account logic dependencies. The paths with the shortest delay are computed using the dynamic cut selection (DCS) algorithm. These techniques have been implemented in the static timing analyzer TAMIA to provide fast and accurate worst-case delay estimation for digital CMOS circuits.>

This paper presents two algorithms for performing worst-case delay estimation using transistor-level timing simulation techniques. The first algorithm, Dynamic Path Selection (DPS), determines in linear time the slowest paths in series-parallel transistor groups; the exponential complexity remains for transistor groups with bridges. The second algorithm, Delay Subnetwork Enumeration (DSE), complements the DPS method by taking into account logic dependencies within transistor groups. The two methods are combined in the static timing analyzer TAMIA, to provide accurate worst-case delay estimation of digital CMOS circuits.

An algorithm has been developed for the automatic determination of the optimal clock waveforms for synchronous circuits containing level-sensitive latches. From a specification of only the number of clock phases, the rise and fall times of the clock phase transitions, and the order in which they occur, the algorithm computes the minimum time interval between the transitions, while accounting for the clock skew. Timing errors, such as incorrect hold times, are also detected. Existing procedures, in contrast, either verify if a circuit meets a given specification of these clock intervals, or they work with a very restricted set of clocking schemes. The procedure is iterative, and can be formulated as a linear programming problem. It yields an upper bound on the shortest valid clock period at each iteration. Results are presented for a simplified form of this algorithm, implemented in the transistor-level timing analysis program TAMIA.>

A new logic minimization algorithm is presented. It finds a minimal cover for a multiple-output boolean function expressed as a list of cubes. A directed graph is used to speed up the selection of a minimal cover. Covering cycles are partitioned and branched independently to reduce greatly the branching depth. The resulting minimized list of cubes is guaranteed to be minimal in the sense that no cover with less cubes can exist. The don't care at output is handled properly. This algorithm was implemented in C language under UNIX BSD4.2. An extensive comparison with ESPRESSO IIC shows that the new algorithm is particularly attractive for functions with less than 20 input and 20 output variables.

A new logic minimization algorithm is presented. It finds a minimal cover for a multiple-output Boolean function expressed as a list of cubes. A directed graph is used to speed up the selection of a minimal cover. Covering cycles are partitioned and branched independently to reduce greatly the branching depth. The resulting minimized list of cubes is guaranteed to be minimal in the sense that no cover with less cubes can exist. The dont care at output is handled properly. This algorithm was implemented in C under UNIX BSD4.2. An extensive comparison with ESPRESSO IIC shows that the new algorithm is particularly attractive for functions with less than 20 input and 20 output variables.