Published papers

In virtualized environments, oversubscribing virtual CPUs (vCPUs) on physical CPUs (pCPUs) is common to utilize CPU resources efficiently. Unfortunately, excessive vCPU spinning, which occurs when a vCPU is waiting in a spin loop for an event from a descheduled vCPU, causes serious performance degradation. Usually, the VM-Agnostic hypervisor tries to prevent excessive vCPU spinning by rescheduling vCPUs when an excessive spin is detected by hardware support for virtualization. This paper investigates the effectiveness of KVM vCPU scheduler and shows it fails to avoid excessive vCPU spinning in many opportunities. Our in-depth analysis reveals simple modifications to KVM (41 LOC) improve the mitigation of excessive vCPU spinning. We have identified three problems: 1) scheduler mismatch, 2) lost opportunity, and 3) overboost. The first problem comes from the mismatch between the KVM vCPU scheduler and the Linux scheduler. The second and third problems come from an inefficient algorithm for choosing the next candidate vCPU to be scheduled. Our simple modifications gracefully resolves the problems and the performance improves by up to 80 %. Our results imply the VM-Agnostic hypervisor can resolve excessive vCPU spinning more gracefully than previously believed.

Persistent Memory(PM) has non-volatilability and byte-addressability, and it can be used in many situations due to its high reliability and high performance. However, the persis-tent nature of PM has great impact on 'rejuvenation'. Crash consistency bugs, which result in inconsistent data structures inside PM after system crashes, cannot be recovered by restarting the crashed program because the data structures in PM are not initialized with the restarts. Most of existing tools for detecting crash consistency bugs adopt static analysis that can explore a wider range of PM code regions and can detect bugs effectively, but it is hard for these tools to consider all the possible states because of the combinatorial explosion. In addition, PM programs usually have recovery code, which recovers PM data from inconsistent states, hence a crash consistency bug can be recovered to a correct state and it should not be reported as a bug. To simulate the execution of PM programs and detect crash consistency bugs dynamically, we propose PM Crash Injector, the first crash injection tool for PM programs to check the correctness of the recovery code. Like fault injection tools, PM Crash Injector injects system crashes into PM programs to cause crash consistency bugs intentionally. If the recovery code works correctly, inconsistent states in PM will be recovered, but if not, they will be left in PM regions and detected as unexpected behavior the program. PM Crash Injector has found 3 bugs in real-world PM systems and 6 manually inserted bugs in the sample programs of PMDK.

Data analysis applications are recently developed by combining multiple programming languages to utilize the advantage of each of them. Such applications are called multilingual applications and can accelerate data-intensive tasks such as data preprocessing and machine learning. However, multilingual applications require time-consuming serialization and deserialization (S/D) processes to exchange data between different programming languages. Although state-of-the-art mechanisms have developed to reduce the time overheads of S/D processes, the overheads are still not trivial due to memory copy of shared data. In this paper, for multilingual applications combining Python and Julia, we propose an in-memory array sharing method that serializes/deserializes only lightweight metadata and directly shares heavy data arrays in a shared memory space. It completely eliminates memory copy of numeric arrays by using a common in-memory metadata format between Python and Julia. Our evaluation shows that the proposed method reduces the execution times of three multilingual machine learning applications by 40.8% to 44.5% compated to a state-of-the-art S/D mechanism. Consequently, it brings the benefit of combining Python and Julia to develop machine learning applications. In addition, we demonstrate that the proposed method has a high scalability to the larger amount of data.

Linux, a battle-tested codebase, is known to suffer from many bugs despite its extensive testing mechanisms. While many of these bugs require domain-specific knowledge for detection, a significant portion matches well-known bug patterns. Even though these bugs can be found with existing tools, our simple check of Linux kernel patches suggests that these tools are not used much in the developer’s daily workflow. The lack of usage is probably due to the well-known trade-off between analysis time and bug detection capabilities: tools typically employ complex analysis to effectively and comprehensively find bugs in return for a long analysis time, or focus on a short analysis time by only employing elementary analyses and thus can only find a very limited number of bugs. Ideally, developers expect the tools to incur short analysis time, while still finding many bugs to use them in daily development. This paper explores an approach that balances this tradeoff by focusing on bugs that can be found with less computationally-complex analysis methods, and limiting the scope to each source code. To achieve this, we propose a combination of computationally lightweight analyses and demonstrate our claim by designing FiTx, a framework for generating daily development-friendly bug checkers that focus on well-known patterns. Despite its simplicity, FiTx successfully identified 47 new bugs in the Linux kernel version 5.15 within 2.5 hours, outperforming Clang Static Analyzer and CppCheck in both speed and bug detection. It demonstrates that focusing on less complex bug patterns can still significantly contribute to the improvement of codebase health. FiTx can be embedded into the daily development routine, enabling early bug detection without sacrificing developers’ time.

This paper explores a practical means to employ Data Plane Development Kit (DPDK), a kernel-bypassing framework for packet processing, in resource-limited multi-tenant edge data centers. The problem is that the traditional virtual CPU (vCPU) schedulers are not well compatible with the event detection model of DPDK, which needs to monopolize a physical CPU (pCPU) for NIC register polling. Consequently, DPDK-applied systems running on consolidated Virtual Machines (VMs), a common setup at edges, fail to achieve low serving latencies regardless of the use of DPDK. Toward edge data center providers, this work presents a new vCPU scheduling policy named Polling vCPU Consolidation (PvCC) which runs DPDK-applied systems on dedicated pCPUs adopting microsecond-scale time slices. Along with this, we introduce a mechanism to determine an appropriate number of dedicated pCPUs according to customers’ demands represented through a newly introduced vCPU scaling API enabling customers to scale up/down the vCPUs of their VMs at runtime. Our experiments show that PvCC allows DPDK-applied systems running on consolidated VMs to achieve low serving latencies, and our vCPU scaling API enables customers to adjust CPU resource assignment according to the incoming request rate and providers to effectively assign spare pCPUs to VMs executing non-latency-sensitive best-effort tasks.

Big-memory applications which have huge memory footprints, such as machine learning and key-value store, are playing important roles in various real-world services. Compute Express Link-based memory (CXL memory) is nowadays attracting a lot of attention for such applications, because it can expand memory capacity on a single machine with fast memory semantic accesses to memory devices attached to PCIe slots. On the other hand, memory swapping is another traditional technique to expand memory capacity by using storage devices as a swap space. It is well known that memory swapping causes a large latency overhead to swap-in/out memory pages from/to storage devices, while it can efficiently utilize main memory when workloads have skewed memory access patterns.In this paper, we quantitatively compare the throughput of 14 macro-benchmarks between CXL memory emulated with a remote NUMA node and memory swapping with an NVMe SSD. Through this evaluation, the benchmarks are classified into three categories, where memory swapping achieves a comparable or higher throughput compared to emulated CXL memory for 9 benchmarks. This result reminds us that memory swapping with SSDs, which are much cheaper than CXL memory devices, is still a good option for memory capacity expansion. In addition, we conduct an in-depth analysis on the characteristics of emulated CXL memory and memory swapping using our synthetic benchmark. The analysis shows that memory swapping is not sensitive to the initial placement of hot data and achieves a comparable throughput to emulated CXL memory when hot data is accessed intensively.

This paper explores a practical means to employ Data Plane Development Kit (DPDK), a kernel-bypassing framework for packet processing, in resource-limited multi-tenant edge data centers. Traditional virtual CPU (vCPU) schedulers are not compatible with the event detection model of DPDK, because each DPDK-applied VM (virtual machine) monopolizes one physical CPU (pCPU) for NIC register polling. Toward edge data center providers, this paper presents a new vCPU scheduling policy named Polling vCPU Consolidation (PvCC). PvCC enables DPDK-applied VMs to be consolidated on dedicated pCPUs by adopting microsecond-scale time slices. Along with this, PvCC provides vCPU scaling API that enables to scale up/down vCPUs of VMs at runtime. Our experiments show that PvCC allows consolidated DPDK-applied VMs to achieve low serving latencies, and our vCPU scaling API allows us to adjust CPU resource assignment according to the incoming request rate. It also enables to assign spare pCPUs to VMs executing non-latency-sensitive tasks.

The global online video game industry has become a more than one hundred billion dollar market. Cheating is one of the major issues in multiplayer online video games. Cheat prevention is challenging because of the unique threat model of online games. Because the cheaters physically possess their own game computers, they can install cheat tools at the user level and OS and can access the physical DRAM bus to tamper with the game process. This paper aims to efficiently prevent memory tampering cheats by leveraging a trusted execution environment (TEE), Intel Client SGX. It provides strong integrity protection against memory tampering. Unfortunately, its strong protection comes with a severe size limitation of the available enclave memory. Running the entire game process inside the enclave exceeds the memory limit. This paper presents Gangi, a library that efficiently protects the integrity-sensitive game state that exceeds the available enclave memory. Gangi places the game state outside the enclave to reduce memory consumption inside the enclave while ensuring the integrity of the game state by hash-based validation. Our benchmarking results show that a Gangi-protected game outperforms the EPC swapping approach with the entire game state being inside the enclave.

Despite many efforts made to detect memory leaks in large-scale software systems such as the Linux Kernel, state-of-the-art tools fail to find some common patterns of leaks due to the limitation incurred to achieve scalability. Memory leak of a struct member is one of the commonly found patterns neglected in these tools. This pattern occurs when a struct member remains allocated even when the struct is released. Detecting such patterns requires correlating the struct and its members, requiring complex inter-procedural, points-to analysis, known to be non-scalable. In this paper, we present a scalable approach that focuses on detecting these struct member-related leaks in the Linux Kernel. Unlike state-of-the-art tools that analyze the value flow using Value Flow Graph (VFG) or Sparse Value Flow Graph (SVFG), our approach conducts a field-based flow analysis using the Control Flow Graph (CFG). To reduce false positives, we also check two types of branch conditions (NULL condition check and error code condition check) to determine what to propagate to each basic block in the CFG. Using our approach, we found 12 previously unknown leaks in Linux, with a precision of 59.1% in approximately 1 hour of analysis time. Some of the bugs were found in the core component, affecting many other components as well. We further created 9 fix patches for the bugs, all of them were reviewed and confirmed by the developers.

Past studies have demonstrated that one can achieve high-performance TCP/IP communication by using a packet I/O framework that allows a user-space TCP/IP stack to bypass most kernel-space networking subsystems. However, most publicly available implementations only support one packet I/O framework. This paper points out the importance of supporting multiple packet I/O frameworks in a single TCP/IP stack implementation through our development experience for enabling a TCP/IP stack implementation called iip to support the use of the widely used packet I/O frameworks, DPDK, netmap, and AF XDP.

In virtualized environments, virtual CPUs (vCPUs) are commonly oversubscribed on physical CPUs (pCPUs) to utilize CPU resources efficiently. However, excessive vCPU spinning, which occurs when a vCPU is waiting in a spin loop for an event from a descheduled vCPU, greatly degrades application performance in virtualized environments. VM-agnostic hypervisors aim to prevent excessive vCPU spinning by rescheduling vCPUs when an excessive spin is detected by hardware support for virtualization. We investigate the effectiveness of the KVM vCPU scheduler and show that it fails to avoid excessive vCPU spinning under various situations. We identify three problems: 1) scheduler mismatch, 2) aggressive limitation of candidate vCPUs, and 3) IPI context misuse. The first problem stems from the mismatch between the KVM vCPU scheduler and the Linux scheduler. The second and third problems come from failures in choosing candidate vCPUs to be scheduled next. Our in-depth analysis reveals simple modification to KVM (89 LoC) can mitigate excessive vCPU spinning. Our simple modification reduces excessive vCPU spinning by up to 96% and improves benchmark performance by up to 2.6×. Part of the proposed mitigation has been integrated with KVM from Linux KVM v5.13 onward.

Build systems are essential tools for developing large software projects. Traditionally, build systems have been designed for high incremental-build performance. However, the longer build times of recent large C++ projects have imposed a requirement on build systems: i.e., unity builds. Unity builds are a build technique for speeding up sequential compilation of many source files by bundling multiple source files into one. Unity builds lead to a significant reduction in build time through removal of redundant parsing of shared header files. However, unity builds have a negative effect on incremental builds because each compiler task gets larger. Our previous study reported existing unity builds overlook many better bundle configurations that improve unity-build performance without increasing the incremental-build time. Motivated by the problem, we present a novel build system for better performance in unity builds. Our build system aims to achieve competitive unity-build performance in full builds with mitigating the negative effect on incremental builds. To accomplish this goal, our build system uses sophisticated bundle strategies developed on the basis of hints extracted from the preprocessed code of each source file. Thanks to the strategies, our build system finds better bundle configurations that improve both of the full-build performance and the incremental-build performance in unity builds. For example, in comparison with the state-of-the-art unity builds of WebKit, our build system improves build performance by 9% in full builds, by 39% in incremental builds, and by 23% in continuous builds that include both types of the builds.

Containers offer a lightweight alternative over virtual machines and become a preferable choice for application consolidation in the clouds. However, the sharing of kernel components can violate the I/O performance and isolation in containers. It is widely recognized that file system journaling has terrible performance side effects in containers, especially when consolidating database management systems (DBMSs). The sharing of journaling modules among containers causes performance dependency among them. This dependency violates resource consumption enforced by the resource controller, and degrades I/O performance due to the contention of the journaling module. The operating system developers have been working on novel designs of file systems or new journaling mechanisms to solve the journaling problems. This paper shows that it is possible to overcome journaling problems without re-designing file systems or implementing a new journaling method. A careful configuration of containers in existing file systems can gracefully solve the problems. Our recommended configuration consists of 1) per-container journaling by presenting each container with a virtual block device to have its own journaling module, and 2) accounting journaling I/Os separately for each container. Our experimental results show that our configuration resolves journalingrelated problems, improves MySQL performance by 3.4x, and achieves reasonable performance isolation among containers.

Hypervisor vulnerabilities cause severe security issues in multi-tenant cloud environments because hypervisors guarantee isolation among virtual machines (VMs). Unfortunately, hypervisor vulnerabilities are continuously reported, and device emulation in hypervisors is one of the hotbeds because of its complexity. Although applying patches to fix the vulnerabilities is a common way to protect hypervisors, it takes time to develop the patches because the internal knowledge on hypervisors is mandatory. The hypervisors are exposed to the threat of the vulnerabilities exploitation until the patches are released.This paper proposes Nioh-PT, a framework for filtering illegal I/O requests, which reduces the vulnerability windows of the device emulation. The key insight of Nioh-PT is that malicious I/O requests contain illegal I/O sequences, a series of I/O requests that are not issued during normal I/O operations. Nioh-PT filters out those illegal I/O sequences and protects device emulators against the exploitation. The filtering rules, which define illegal I/O sequences for virtual device exploits, can be specified without the knowledge on the internal implementation of hypervisors and virtual devices, because Nioh-PT is decoupled from hypervisors and the device emulators. We develop 11 filtering rules against four real-world vulnerabilities in device emulation, including CVE-2015-3456 (VENOM) and CVE-2016-7909. We demonstrate that Nioh-PT with these filtering rules protects against the virtual device exploits and introduces negligible overhead by up to 8% for filesystem and storage benchmarks.

C++ has been widely used for developing various system software such as compilers, web browsers, and so on. However, as software is growing in size and complexity, long build times of the C++ projects has been problematic. This article introduces and discusses three effective methods to improve build times of the C++ projects (i.e., Unity Builds, Zapcc, and C++ Modules). First, we introduce the background of long build times in large C++ projects and analyze breakdowns of the build times to identify the bottleneck in the build processing. Then, we describe each method and indicate how much it can improve the build performance. We also discuss future work in this research area.