Applied Science, Faculty of
Electrical and Computer Engineering, Department of
DSpace
UBCV
Jalalian, Sepehr
Master of Applied Science - MASc
University of British Columbia
For over forty years, researchers have demonstrated that operating system memory managers often fall short for memory-hungry applications. The problem is even more critical today, with disaggregated memory and new memory technologies and in the presence of tera-scale machine learning models, large-scale graph processing, and other memory-intensive applications. Past attempts to provide application-specific memory management either require significant in-kernel changes or suffer from high overhead. We present ExtMem, a flexible framework for providing application-specific memory management. It differs from prior solutions in three ways: (1) It is compatible with todayâs Linux deployments, (2) it is a general-purpose substrate for addressing various memory and storage backends, and (3) it is performant in multithreaded environments. Before presenting ExtMem, we study the Linux paging system, identifying its needs and challenges, and provide our insight in design. ExtMem allows for easy and rapid prototyping of new memory management algorithms, easy collection of memory patterns and statistics, and immediate deployment of isolated custom memory management. Our work demonstrates a new path for faster and more insightful memory management research in the future.
Flexible Application-directed Virtual MemoryManagement for Data-intensive Applications andHeterogeneous HardwarebySepehr JalalianB.Sc. in Electrical Engineering, Sharif University of Technology, 2021A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of Applied ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORALSTUDIES(Electrical and Computer Engineering)The University of British Columbia(Vancouver)April 2024© Sepehr Jalalian, 2024The following individuals certify that they have read, and recommend to the Fac-ulty of Graduate and Postdoctoral Studies for acceptance, the thesis entitled:Flexible Application-directed Virtual Memory Management for Data-intensive Applications and Heterogeneous Hardwaresubmitted by Sepehr Jalalian in partial fulfillment of the requirements for the de-gree of Master of Applied Science in Electrical and Computer Engineering.Examining Committee:Alexandra (Sasha) Fedorova, Professor, Electrical and Computer Engineering, UBCSupervisorSathish Gopalakrishnan, Associate Professor, Electrical and Computer Engineer-ing, UBCSupervisory Committee ChairMargo I. Seltzer, Professor, Computer Science, UBCSupervisory Committee MemberiiAbstractFor over forty years, researchers have demonstrated that operating system memorymanagers often fall short for memory-hungry applications. The problem is evenmore critical today, with disaggregated memory and new memory technologies andin the presence of tera-scale machine learning models, large-scale graph process-ing, and other memory-intensive applications. Past attempts to provide application-specific memory management either require significant in-kernel changes or sufferfrom high overhead. We present EXTMEM, a flexible framework for providingapplication-specific memory management. It differs from prior solutions in threeways: (1) It is compatible with todayâs Linux deployments, (2) it is a general-purpose substrate for addressing various memory and storage backends, and (3) itis performant in multithreaded environments. Before presenting EXTMEM , westudy the Linux paging system, identifying its needs and challenges, and provideour insight in design. EXTMEM allows for easy and rapid prototyping of newmemory management algorithms, easy collection of memory patterns and statis-tics, and immediate deployment of isolated custom memory management. Ourwork demonstrates a new path for faster and more insightful memory managementresearch in the future.iiiLay SummaryManaging computer memory is crucial as it profoundly affects program perfor-mance and operational expenses. As demands for memory escalate, particularlydriven by technologies such as big data processing and artificial intelligence, re-fined memory management solutions become necessary. This thesis investigatesone aspect of memory management related to applications that donât fit in localDRAM, probing existing methodologies and introducing a novel software sys-tem called EXTMEM. Our intuition behind the EXTMEM is to give applicationsmore control over their memory management and provide flexibility.Through ex-perimentation and real-world applications, we show how EXTMEM can signifi-cantly enhance program execution efficiency and computational resource utiliza-tion, while minimizing development effort and time. Our aspiration is to enhancethe landscape of memory management in computing environments, thereby facili-tating smoother and more efficient operation for all users.ivPrefaceThis thesis represents my original, independent work in memory management. Thework was mainly done by myself under supervision of Prof. Alexandra Fedorovaand feedback and guidance from Prof. Margo Seltzer.Main component of this thesis, focusing on the EXTMEM system is currentlyunder review for publication in the paper submitted with co-authors Shaurya Patel,Milad Rezaei, Margo Seltzer and Alexandra Fedorova. Chapters 4-10 partially in-clude material from this submission in addition to independent, unpublished workby myself. Alexandra Fedorova was the supervisory author and contributed valu-able guidance, editing, and writing. Margo Seltzer provided unwavering technicaland editorial support throughout the paper submission. Shaurya Patel providedfeedback and assisted in planning the experiments that appear in chapter 8. MiladRezaei collaborated on designing experiments in chapter 9 (application case study)and assisted in refining the material.I am thankful for the opportunity to contribute to this field and hope this thesisinspires further research.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xGlossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1 Memory Management Basics . . . . . . . . . . . . . . . . . . . . 62.2 Memory Disaggregation and Far Memory . . . . . . . . . . . . . 92.3 Microkernels and Semi-microkernels . . . . . . . . . . . . . . . . 113 Paging: A Hardware-Software Issue . . . . . . . . . . . . . . . . . . 133.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.2 Methodology: ZRAM and VRAM . . . . . . . . . . . . . . . . . 153.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16vi3.3.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . 163.3.2 Profiling . . . . . . . . . . . . . . . . . . . . . . . . . . 173.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.4.1 Performance and Runtime . . . . . . . . . . . . . . . . . 173.4.2 CPU Stack Trace . . . . . . . . . . . . . . . . . . . . . . 193.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 Enabling Application-Aware Memory Page Placement Policies andMechanisms with Extmem . . . . . . . . . . . . . . . . . . . . . . . 234.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.2 The 2024 Case for External Paging . . . . . . . . . . . . . . . . . 254.2.1 New Memory Architectures . . . . . . . . . . . . . . . . 264.2.2 Microkernels and Semikernels . . . . . . . . . . . . . . . 274.3 EXTMEM: Design . . . . . . . . . . . . . . . . . . . . . . . . . 274.3.1 The User View . . . . . . . . . . . . . . . . . . . . . . . 284.3.2 The Core Layer . . . . . . . . . . . . . . . . . . . . . . . 294.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 Upcall Userfaults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335.0.1 EXTMEM Upcall Path . . . . . . . . . . . . . . . . . . . 345.0.2 Correctness Conditions . . . . . . . . . . . . . . . . . . . 365.1 Upcall Performance . . . . . . . . . . . . . . . . . . . . . . . . . 376 Policy Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396.1 Observability Layer . . . . . . . . . . . . . . . . . . . . . . . . . 396.2 Policy Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406.3 Default Policy: 2Q-LRU . . . . . . . . . . . . . . . . . . . . . . 416.4 VMA-based Prefetcher . . . . . . . . . . . . . . . . . . . . . . . 447 EXTMEM Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 467.1 Random Access Microbenchmark . . . . . . . . . . . . . . . . . 477.2 Sequential Microbenchmark . . . . . . . . . . . . . . . . . . . . 487.3 Hot Set Microbenchmark . . . . . . . . . . . . . . . . . . . . . . 48vii8 Case Study: PageRank . . . . . . . . . . . . . . . . . . . . . . . . . 509 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539.1 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5610 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59viiiList of TablesTable 4.1 Implicit interface of EXTMEM binded with system call inter-ception to the explicit API calls. . . . . . . . . . . . . . . . . . 30Table 6.1 Set of core API connected to the policy layer in the currentEXTMEM implementation . . . . . . . . . . . . . . . . . . . . 42ixList of FiguresFigure 3.1 Runtime comparison of tpc-c benchmark running on VoltDBusing different swap devices. . . . . . . . . . . . . . . . . . . 18Figure 3.2 Throughput comparison of ycsb-c (read-only) benchmark run-ning on WiredTiger using different swap devices. . . . . . . . 19Figure 3.3 YCSB-C on WiredTiger . . . . . . . . . . . . . . . . . . . . 20Figure 3.4 TPC-C on VoltDB . . . . . . . . . . . . . . . . . . . . . . . 20Figure 3.5 Stack profile analyses of page faults in each execution. Per-centage of CPU cycles spent in page faults is shown for eachtask. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20Figure 5.1 Userfaultfd method: 1. Application registers a memory areawith the kernel and receives a file descriptor. 2. A handlerthread calls select/poll system call on the file descriptor. 3. Athread triggers a page fault and context switches into the ker-nel. 4. After verifying the faulting address, kernel submits thefault information to the file descriptor and blocks the faultingthread. 5. The user-level handler receives the fault, performsthe necessary IO and data preparation. 6. A user level makesa system call to map the new page and unblock the faultingthread. 7. Faulting thread goes back to continue the execution.The red arrows are inter-process-communication. . . . . . . . 34xFigure 5.2 Upcall method based on Linux signal path: 1. Applicationregisters a memory area with the kernel and registers an upcallhandler function. 2. A thread triggers a page fault and contextswitches into the kernel. 3. Kernel makes an upcall by register-ing the upcall handler context on the faulting threadâs stack 4.The faulting thread is back in userland, executes handler codeto perform the necessary IO and data preparation. 5. Faultingthread makes a system call to map the new page and returnfrom the upcall. 6. Faulting thread goes back to continue theexecution. No IPC is necessary. . . . . . . . . . . . . . . . . 35Figure 5.3 Average latency of resolving a single minor fault in a single-threaded execution . . . . . . . . . . . . . . . . . . . . . . . 38Figure 5.4 Average latency of resolving a minor fault in a multi-threadedsystem under pressure . . . . . . . . . . . . . . . . . . . . . 38Figure 7.1 Throughput of the system making byte-sized updates in thescenario of random updates when 50% of the working set fitsin memory. . . . . . . . . . . . . . . . . . . . . . . . . . . . 47Figure 7.2 Throughput of the system making byte-sized updates in thescenario of sequential updates when 50% of the working setfits in memory. . . . . . . . . . . . . . . . . . . . . . . . . . 48Figure 7.3 Throughput over time of evaluated systems for the workingset access microbenchmark. 90% of accesses go to 10% ofmemory while 50% of data fits in the memory. EXTMEM-2Q-LRU efficiently keeps working set in memory. . . . . . . . 49Figure 8.1 An example of representation of a graph in Compressed SparseRow (CSR). Using EXTMEM we apply custom policy to Ver-tex and Edge arrays. . . . . . . . . . . . . . . . . . . . . . . 51Figure 8.2 Average runtime of ten iterations of PageRank over twitterdataset with 50% of data fitting in memory . . . . . . . . . . 52xiGlossaryCPU Central Processing UnitDRAM Dynamic Random Access MemoryFIFO First In First OutIPC Inter-process CommunicationIPI Inter-processor InterruptJVM Java Virtual MachineLRU Least Recently UsedMMU Memory Management UnitNVME Non-Volatile Memory expressOOM Out of MemoryOS Operating SystemPIM Processing In MemorySSD Solid State DriveTLB Translation Lookaside BufferVMA Virtual Memory AreaxiiAcknowledgmentsI am deeply grateful to my many wonderful colleagues and friends, who con-tributed, each in their own way, to the research presented in this thesis.To Prof. Alexandra (Sasha) Fedorova, my supervisor, thank you for providingme with the opportunity to pursue my masterâs degree and learn to become anindependent researcher. I am truly grateful for your openness to my ideas, andallowing me to take risks and explore my interests. Your unwavering support andkindness have been instrumental in my journey.To Prof. Margo Seltzer, I am exceptionally thankful for your guidance and en-couragement that empowered me to strive for bold steps in my research. Thank youfor believing in me and providing your fullest support. Your enthusiastic assistanceand discussions have been invaluable in my path.To Prof. Sathish Gopalakrishnan, thank you for agreeing to chair my commit-tee and for providing your valuable feedback on my work and my thesis.I extend my profound gratitude to Milad Rezaei for his unwavering supportthat helped me navigate the toughest days and remain resilient until the end of theproject. I am sincerely thankful to Shaurya Patel for his invaluable collaboration,engaging discussions and optimism. My heartfelt appreciation goes to insight-ful members of my community: Reto Achermann, Rachel Pottinger, Joel Nider,Xuechun Cao, and Sepehr Noorafshan, whose discussions and feedback greatlyenriched my understanding.I am grateful to my friends for their support. Their presence has been a sourceof strength throughout this journey. I also express my gratitude to the vibrant com-munity in the Systopia lab and the ECE departmentâs grad community for fosteringan environment where I could forge friendships and create lasting memories.xiiiFinally, to my mother and father, I express my heartfelt thanks for your bound-less love, support, and understanding. To my brother Sahand, thank you for being aconstant source of joy from afar. I am appreciative of my caring and patient familywhose support made this journey possible for me.We acknowledge the support of the Natural Sciences and Engineering ResearchCouncil of Canada (NSERC). This research was enabled in part by support pro-vided by Intel and Huawei.xivChapter 1IntroductionMemory management is a crucial task in computer systems and operating systemdesign, significantly impacting application performance and operational cost [27,104, 110]. Due to the cost and scaling trends of DRAM, memory emerges as acostly and scarce resource in modern datacenters [72, 79, 105].This challenge has become even more critical today given workloads such astera-scale machine learning [20, 81, 91], large-scale graph processing [53, 97], in-memory databases [48, 101], and other memory-intensive applications [26, 61, 67].Operators have turned to innovative memory architectures such as disaggre-gated memory [24, 55, 79], tiered memory [77, 94, 112], and memory-centriccomputing [85, 86] to address the challenges presented by memory-hungry appli-cations. These approaches have produced a dynamic and diverse memory hardwarelandscape, with myraid ongoing developments [21, 66, 68, 88]. Consequently, sys-tem designers must not only incorporate core kernel support for these novel mem-ory devices but also revamp memory management policies. This transformationis essential to fully leverage hardware benefits and optimize memory utilization[25, 43].Memory management policies that aim to fit all scenarios are no longer prac-tical [46, 51]. Several instances have risen where general-purpose OS memorymanagers have failed to meet the demands of data-intensive applications [16, 31,69, 111, 113]. This challenge has been compounded by ongoing innovations inmemory architecture and the increasing diversity of hardware configurations [32,146, 63].In this thesis, our primary focus is on memory management in the contextof paging. While numerous efforts have concentrated on developing new hard-ware architectures to enhance memory performance, we concentrate on a criticalaspect: the memory management software stack provided by operating systems.Specifically, we show there is substantial potential in memory management poli-cies. Memory management and page faults, rather than device bandwidth, can besignificant bottlenecks in a system [22]. As a result, selecting appropriate mem-ory management policies has become a tailored process. For example, TMO [110]achieved a 20% memory saving in datacenters by optimizing kernel policies forSSD offloading, while other work [108, 109] achieved high performance gains bymodifying the kernel swap system behind the JVM runtime. However, such ap-proaches may not generalize well.In Chapter 2, we offer an overview of fundamental memory management con-cepts that are necessary for understanding this thesis. Additionally, we discuss theemerging trends of disaggregated and far memory, highlighting their significancein our context and their impact on the memory management landscape.Our initial exploration (chapter ??) begins with an examination of existing sys-tems. We analyze the Linux paging stack through experimentation and profiling.This process allows us to develop a deeper understanding of paging and far mem-ory systems, shedding light on the critical factors influencing their performance.The core of this thesis is the design and implementation of EXTMEM , whichcombines our efforts and experiences in kernel paging, memory management tech-niques, and user-level page fault handling. EXTMEM empowers applications toefficiently and flexibly manage their memory in user space. Throughout this thesiswe describe the design and evaluation of EXTMEM .Developing, testing, and deploying new memory managers in the kernel is chal-lenging due to the complexity of the Linux memory management system [9, 15,54]. This core kernel component must function effectively for multiple systemobjectives, leading to lengthy and intricate development processes [109]. For in-stance, even simple algorithms such as Leap prefetching [23] require extensivekernel modifications, often spanning multiple files. As a result, developers mayencounter significant hurdles in implementing and deploying specialized memory2management enhancements in the kernel [12, 14]. Some efforts have exploredalternative approaches, such as implementing memory optimizations in libraryOS environments like Dilos [114], to bypass kernel limitations. However, theseapproaches are also challenging to implement and deploy in production environ-ments.Prior work on user-space memory management or paging have significant short-comings, as they are either based on a runtime support [57, 95, 108], internal ap-plication modifications [42, 71, 99, 106], or specific memory back-ends [94], orcause high overheads [33, 90] and lack the functionality to accommodate flexiblepolicies.In Chapter 4, we describe the main principles of the EXTMEM . By shiftingmemory management policies and paging mechanisms to user space while op-erating alongside the Linux kernel, EXTMEM maintains security and isolation.EXTMEM is suitable for deployment in production environments and real-worldscenarios, serving both experimental and developmental purposes, as well as realuse cases. Notably, EXTMEM seamlessly integrates without necessitating modifi-cations to application code, facilitating its adoption.In chapter 5 we describe our method for efficiently handling page faults in userspace. We considered the design implications of the widely-used Linux subsystemfor user space paging, userfaultfd [2], which relies on file-based IPC and serverthreads to handle page faults, and thus scales poorly for multithreaded workloads.In contrast, the EXTMEM architecture is based on upcalls, allowing for scalableself-paging [58] even in highly multithreaded environments. We implemented ourapproach using existing userfaultfd and signaling interfaces in Linux. EXTMEMrequires modifications of only 200 lines of code localized to userfaultfd and sig-naling subsystems in Linux.In chapter 6 we demonstrate EXTMEM âs policy and observability layers thatprovide the information and operations needed for powerful policy design. Weshow how our layered design provides ease of development. The EXTMEM coreprovides the substrate and the policy layer uses that alongside with the data col-lection tools in observability layer to easily develop wide range of algorithms. Wealso explain the default eviction and prefetching policies that we implemented andplaced in the current implementation of EXTMEM . Default policies replicate the3same policies in Linux.In chapter 7 we evaluate the EXTMEM using microbenchmarks. We demon-strate its negligible overhead in user-space paging stack through its equivalent orbetter performance compared to Linux. We also show how EXTMEM âs defaultpolicy is effective in keeping the frequently accessed data in memory and performssame as its equivalent in Linux, thus, showing practicality of the EXTMEM âs pol-icy layer. Furthermore, we see that the closest prior work performs significantlyworse and does not scale.In Chapter 8, we showcase the practicality and efficacy of EXTMEM througha real-world application scenario. Specifically, we examine the PageRank algo-rithm as a representative example of large-scale graph processing applications. Wepresent a novel eviction and prefetching policy tailored for PageRank. Our eval-uation contrasts the outcomes against those of Linux swap and our default policy.We illustrate how, with minimal intervention and without additional hardware orprocessing resources, EXTMEM can deliver over 50% performance improvements.Overall, this thesis makes the following contributions:â¢ We study and demystify some of the internals of the Linux paging systemrelevant to the far memory systems.â¢ We design and implement EXTMEM , a framework for rapid development ofcustomized memory managers in user space.â¢ We propose an alternative mechanism for page fault handling in user spacethat is scalable and performant in native multithreaded environments.â¢ We demonstrate the applicability of our framework with the following casestudies:â Implementation of a Linux-like memory reclaim policy, written in only300 lines of code, with performance better or equivalent to native Linuxin memory-intensive workloads.â Achieving substantial 50% performance enhancement over native swap-based execution in the PageRank algorithm through the development of4a custom memory management policy in EXTMEM with minimal de-velopment effort.5Chapter 2BackgroundIn this chapter, we provide the background and context of this thesis. We begin byexplaining the fundamental principles of the virtual memory subsystem, as preva-lent in contemporary computing environments. We describe how hardware andsystem software (e.g., Linux) work together to enable the abstraction of virtualmemory. Subsequently, we explore some of the emerging memory architectures,notably memory disaggregation. We briefly report their transformative impact andthe challenges they impose on general purpose memory management in operatingsystems.2.1 Memory Management BasicsIn modern computer systems, main memory (DRAM) stands as a primary resource,managed by operating systems to facilitate efficient execution of processes. Oper-ating systems provide a virtual memory abstraction to processes to allow seamlessaccess to physical resources. Virtual memory is a crucial abstraction that enablesefficient utilization of physical memory resources by providing each process with auniform and contiguous address space. Through this abstraction, processes interactwith memory as if they have access to a large, continuous block of memory, eventhough physical memory is finite and fragmented.The primary tasks of a virtual memory system include address translation,memory allocation, and memory protection. Address translation involves map-6ping virtual addresses to physical addresses, enabling processes to access memorylocations consistently independent of their actual physical location. Memory al-location entails dynamically allocating and deallocating memory pages as needed,optimizing memory utilization. Memory protection mechanisms ensure that pro-cesses do not access unauthorized memory regions, safeguarding system integrityand security.Present operating systems manage and map memory in units known as pages.These pages serve as the basic unit of memory allocation and are typically a fewkilobytes in size. For example in x86 systems, all base pages are 4KB, with2MB and 1GB hugepages available. Operating systems maintain page mappingsin process-specific page tables, which are used to translate virtual addresses tophysical addresses during memory access operations. To expedite this transla-tion process, modern processors leverage dedicated hardware components, such asthe Memory Management Unit (MMU). The MMU efficiently walks page tablesand translates virtual addresses to physical addresses, enabling processes to ac-cess memory locations by virtual addresses regardless of their actual physical lo-cation. Additionally, the Translation Lookaside Buffer (TLB) is a hardware cachethat stores recently accessed virtual-to-physical address mappings. By cachingthese translations, the TLB facilitates instant access to memory locations withoutthe need for repeated lookups in the page tables, thereby enhancing system perfor-mance.Each process is provided with a full virtual memory address space, which mayexceed the total physical memory available in the system. However, the operatingsystem does not maintain mappings for the entire virtual address space of a pro-cess at all times. Instead, when a process requests memory allocation, the kernelreserves the corresponding virtual space but can defer the actual mapping of phys-ical pages to future. Consequently, when a process accesses an address within itsvirtual memory space that lacks a corresponding physical mapping, the MemoryManagement Unit (MMU) triggers a page fault, causing the process to transitioninto kernel mode for resolution. Page faults enable demand-paging, a mechanismwhere the operating system delays the allocation of physical memory until it is ex-plicitly required. Minor page faults occur when a page exists in system but notmapped in process page tables.7First touch major page faults occur when a page is accessed for the firsttime after allocation, prompting the kernel to allocate a physical page and createthe mappings in process page tables accordingly.Operating systems also leveragevirtual memory to provide memory larger than the physical capacity of the sys-tem. Through a process known as paging or swapping, the operating system movespages from local memory (DRAM) to a secondary storage (e.g., a disk) to free upphysical memory for other purposes. During this paging out procedure, the ex-isting physical mapping of the pages is removed. Consequently, when a processattempts to access data that has been swapped out to secondary storage, it alsoincurs a type of Major Page Fault, sometimes called missing fault. This typeof page fault requires the kernel to allocate a physical page and perform I/O op-erations to bring back the data local memory and remap the page for the process.Major page faults enable the kernel to transparently move data between memoryand secondary storage, thereby increasing memory utilization and mitigating therisk of out-of-memory (OOM) errors.Another mechanism provided by the virtual memory in modern operating sys-tems (like Linux) is directly mapping files residing in storage into the addressspace of a process. This technique, known as file-backed memory or memory-mapped I/O, allows processes to access file data as if it were in working memory.Consequently, accesses to file data residing on storage trigger major page faults,prompting the operating system to perform I/O operations to bring the data into in-memory pages (page cache) for subsequent accesses. The operating system has thecapability to remove or evict pages from the page cache, thereby freeing up mem-ory. Before discarding a page from memory, any modifications are written back tothe source file. This type of memory that is called file-backed memory stands incontrast to anonymous memory, which is the memory allocated and filled by theprocess without an associated file on disk and may be swapped instead. Nonethe-less, both types of memory are subject to the operating system paging and triggersimilar page faults.82.2 Memory Disaggregation and Far MemoryWith the trends in device cost and scaling, coupled with the increasing prevalenceof in-memory and data-intensive workloads, memory has become a scarce resourceand a crucial factor in system cost and performance. To enhance memory utiliza-tion, alleviate the memory wall bottleneck, and extend the scalability of applica-tions beyond the confines of on-chip memory, novel hardware and software archi-tectures are emerging. These advancements present fresh challenges and opportu-nities for innovation, continuously shaping the landscape of memory management.Memory disaggregation is an approach that enables a system to extend its mem-ory capacity beyond the confines of its physical DRAM space [79, 80]. Disaggre-gation technique enables servers to allocate and access memory on the DRAM ofother servers, thus decoupling memory from computation and facilitating elasticprovisioning among nodes. Disaggregated memory enables elastic memory provi-sioning and increases memory utilization.In a broader term, a technology that can provide a slower but cheaper layer ofmemory to the applications can be considered as far memory. Far memory can bedisaggregated memory on remote servers, fast storage devices or software definedmemory using compression. Placing less frequently accessed (cold) or possiblystale memory pages on far memory is beneficial to systems that may run out ofmemory as an alternative to terminating jobs or traditional swapping to slow disks.Furthermore, far memory can specifically help cloud systems with unbalanced andfluctuating workloads by reserving the most efficient amount of memory with min-imal performance loss rather than provisioning memory according to the peak de-mand.In the conventional disaggregation model, the pages residing in remote or farmemory are not directly mapped into the systemâs physical address space. Conse-quently, the system must retrieve blocks of data from far memory and map theminto local pages for program accesses [22, 55]. Effectively managing this dataplacement and movement between local and disaggregated memory becomes ob-jective of the memory manager [24]. While certain systems employ runtimes [95]or programming support [42, 106] to facilitate the use of disaggregated memory,the conventional approach has relied on kernel paging [55, 110]. This paging mech-9anism offers transparency and compatibility, wherein an access to far memory trig-gers a page fault, prompting the kernel swap system to retrieve the necessary page[23]. Swap system can effectively make the local memory a cache for the far mem-ory, with each cache miss causing data movement and page replacement. However,the traditional swap system that was designed for slow disks and out of memorysituations has proven insufficient for demanding disaggregation use cases.To develop a suitable paging stack for disaggregated and far memory, previousefforts have explored potential solutions, including proposing substantial kernelmodifications [22, 32, 112] or entirely new kernel architectures [73, 98]. Dilos[114] implemented prefetching in its library OS to circumvent kernel paging stacklimitations. While these conceptual advances hold value, they often prove hard toimplement and apply in real-world use cases. Prior attempts at user-space memorymanagement have significant shortcomings, as they either require runtime support[57, 95, 108], application modifications [42, 106, 115], are for specific applications[71, 99], or cause high overheads [33, 90].Another emerging architecture for accessing memory beyond DRAM is the di-rectly accessed byte-addressable model [38]. A significant breakthrough in thisarea is CXL (Compute Express Link) [3] technology, which enables CPUs to docache-coherent load/store accesses to off-chip memory connected via CXL ports.This possibility creates a novel class of remote memory known as âtiered mem-oryâ, which can be used in a manner akin to DRAM but offers increased capacity,likely at a slower speed and potentially lower cost [84]. Consequently, CXL effec-tively eliminates the expensive page faults from the data path, enabling fine-grainedmemory accesses and improving the system performance [112]. However, manag-ing memory attached via CXL requires a judicious approach, as frequent accessesto slow memory may incur higher costs than bringing the page to local memory andremapping it [76]. As a result, memory managers must consider paging policiessuch as access tracking and cold data eviction to effectively harness the capabilitiesof multiple memory devices [84, 94]. Previous research has demonstrated that, inthis context as well, there is no one-size-fits-all solution, rendering memory man-agement policy design an ongoing challenge [43, 46].102.3 Microkernels and Semi-microkernelsA microkernel is an operating system architecture that provides high modularity[93]. In contrast to monolithic kernels such as Linux that run all their functionalityin the kernel space, microkernels provide a minimal kernel software for low levelmechanisms and implement most of the operating system functionalities in user-space processes. Microkernels [93] offer improved code management [78, 92],enhanced security [64, 65], and isolation [59] by placing OS functionality in user-space servers. While early microkernels such as Mach [92] provided these benefits,concerns about their performance costs limited their adoption. Microkernels ad-dress the external paging problem by implementing memory pagers in user spaceand using Inter Process Communication (IPC) [64, 78]. However, these efforts weremostly focused on isolation rather than performance and heterogeneous memoryenvironments.In the same vein, researchers have proposed innovative architectures to tacklethe evolving demands and challenges faced by operating systems over time. Partic-ularly noteworthy are Exokernels [45], which shift more system software function-ality into applications, allowing them to carry most of the OS functionality withintheir library operating systems. For instance, Nemesis [58], an exokernel, imple-ments memory paging within applications to achieve higher isolation and preservequality of service.Although for decades microkernels were considered impractical for wide de-ployment [36, 59], we are witnessing a renewed interest in this architecture. No-tably, microkernels inspired a line of work called âsemi-microkernels.â The semi-microkernels, exemplified by projects like Snap [83], uFS [82], Shenango [87] andghOSt [60] are user-level processes that work alongside the conventional mono-lithic kernel while realizing either partial or entire OS subsystems, such as thenetworking stack. The introduction and increasing popularity of high-performanceuser-space I/O libraries such as DPDK [4] and SPDK [107] have further boostedthe adoption of user space system software. The semi-microkernel approach of-fers several advantages of microkernel techniques, such as enhanced code velocity,flexibility, and isolation as they are deployable alongside other processes in a pro-duction environment. Therefore, semi-microkernels allow for rapid development11and deployment of system software, on par with application code development.Moreover, semi-microkernels enable adaption of system services for specific work-loads.In chapter 7 we present the EXTMEM, a memory manager with semi-microkernelarchitecture. We draw inspiration from microkernels and exokernels to facilitatestreamlined development of bespoke management policies for memory-intensiveapplications, all while preserving the kernel virtual memory interface and ensuringthe seamless operation of the rest of the system.12Chapter 3Paging: A Hardware-SoftwareIssue3.1 IntroductionUtilizing far memory is a strategy to enhance memory provisioning and maintainperformance when system memory runs low. Industry has adapted various typesof far memory [24], including remote memory over networks [55], compressedmemory [67], and storage-class memory [110].Compression techniques, have proven beneficial in saving memory, I/O, andstorage and have created. While compressed far memory, also known as softwaredefined far memory, offers lower latency than traditional storage, accessing it stillincurs higher latency compared to DRAM.One sensible idea to improve performance of this memory would be to ac-celerate the compression/decompression using hardware. Specifically with the re-cent advances in Processing-in-memory, off-the shelf processor enabled DRAMchips have been able to achieve promising throughput in compression/decompres-sion [86]. Therefore, we are interested in finding out whether we can leverageprocessing-in-memory for a faster compressed far memory. In this chapter wepresent a performance study of the current compressed memory mechanisms mergedin the Linux kernel. These mechanisms are the basis of the software defined farmemory in production systems [67].13In this study, we want to answer the following questions:â¢ Does compression fit within a memory disaggregation system? Or would itbecome a serious bottleneck?â¢ Would placement of an In-memory compression/decompression chip be wor-thy and solve the bottlenecks?â¢ What optimizations are possible for the compressed far memory architec-ture?To answer whether hardware accelerated compression/decompression is a sen-sible choice we consider the upper bound of gains: If we had ideal compressionhardware that could compress/decompress at zero extra cost and cost of storingand loading data compressed far memory would become same as a memcpy op-eration. We emulate this setting based on the present compressed swap systemsin Linux that are used as compressed far memory in production and compare it tosame systems as baseline.Overall we make the following contributions in this chapter:â¢ We show that compression is feasible and we recommend it for memorydisaggregation systems.â¢ We show how kernel paging overheads are currently the main obstacle for farmemory, as the overheads can be up to 3x times the actual compression/de-compression latency.â¢ After analyzing the swap datapath, we make suggestions for future disaggre-gated memory and compressed far memory designs.Results show that contrary to the intuition, the latency caused by compres-sion/decompression does not become the bottleneck and is comparable to the restof swapping overhead. Therefore, processing-in-memory chips may not be a worth-while choice yet. Nevertheless, compression is recommended for all disaggregatedmemory solutions as the decompression overhead is dwarfed in rest of the systemoverhead.143.2 Methodology: ZRAM and VRAMCompressed swap modules have already been integrated within the Linux kernel.ZRAM [7] is a kernel module that creates compressed RAM-based block devices.Each ZRAM device loads as a block device. Data stored to that device is com-pressed and stored in memory. Therefore, ZRAM can be used as a swap device,saving multiple compressed swapped out pages in each single page, freeing upmemory for the system.Zswap [8] is a similar kernel module that connects to a backing storage deviceand stores pages in storage (similar to normal disk swap) upon necessity. As oftested kernel in this chapter (Linux 4.15 stable) Zswap and ZRAM have the sameinternal implementation. The only difference is that ZRAM is loaded as block de-vice whereas Zswap is called via frontswap module that connects it to the backingdevice and swap system.We analyze ZRAM as the representative of a compressed memory layer. Inour experiments, we limit the memory available to the target process with Cgroup.Since data in ZRAM is not accounted in processâ resident memory and we use asystem with sufficiently larger memory than the imposed Cgroup limit, ZRAM hasalmost unlimited memory available for its pool. This is a good thing since ZRAMwould not be competing over memory with the rest of the system and we will onlysee the base (ideal case) overheads. This implicit isolation means ZRAM in thisstudy can be representative of any swap based disaggregated memory.One of the main goals of this study is to see how beneficial it would be toplace an In-memory compression/decompression chip for compressed swap. Tothis end, we emulate an ideal far memory device by creating a custom in-RAMblock device that can be used as a swap device. This new device can be modifiedto represent any type of swap based disaggregated memory. Since we are interestedin accelerated compression/decompression, we use the structure and memory poolof ZRAM, except that instead of compression/decompression, we copy each pagedirectly to memory. This would emulate the case of ZRAM using an ideal com-pression accelerator. Thus, this new module which we call it VRAM, can emulateZRAM with accelerated compression/decompression.As a reference execution, we also compare to two baselines. First, we run tests15with a full working set in memory. In this run we turn off all swap devices andremove the cgroup limit. Although other swap devices are âIn-memoryâ as well,though the rest of the chapter we use the term In-mem to refer to this referenceexecution. Second, We use the case of swapping to disk for comparison and sanitycheck.3.3 ExperimentsTo investigate the swapping pipeline and measure different overheads we experi-ment with different swap devices. We run memory intensive applications and limitthe available memory by cgroups so the extra memory will be swapped out. Wekeep only one swap device open at each execution.We run experiments on a single server machine equipped with two sockets ofIntel Xeon E5-2407(2.40GHz) 4-core CPUs and 48GB of DDR3 RAM. We ensuretotal DRAM memory is always much higher than the workload size. The setupalso has a 600GB SSD disk.3.3.1 ApplicationsWe used the following applications in experiments and ran the aforementionedbenchmarks:VoltDB:VoltDB [101] is an in-memory transactional database. We set all VoltDB ware-houses on a single local node. We run TPC-C [75] benchmark for transactionalworkloads in our tests. TPC-C models a medium complexity online transactionprocessing (OLTP) workload, a pattern common for in-memory databases. Thisbenchmark takes 10.5GB of memory in peak load and we limit the available mem-ory to 5 GB with Cgroups. We record the runtime (excluding the warmup) andtransactions per second.WiredTiger:WiredTiger [47] is an open source high performance database engine which usesan in-memory cache with the main backing storage. WiredTiger is the default16database engine of MongoDB. WiredTiger manages its storage by itself but since inthis experiment we are interested in in-memory aspect of applications we configurethe size of the in-memory cache to 100GB (logical infinite) to make sure all data iscached and subsequently accessed through the memory. Then we limit the workingmemory with Cgroup to force the system to page the excess data to swap. Weuse the WTperf [19] utility, provided with the native implementation to test theperformance.For the workloads, we ran two benchmarks from Yahoo cloud benchmarkingsuite (YCSB) [39] on WiredTiger: ycsb-a and ycsb-c. ycsb-a is 50% read and 50%update (update heavy) and ycsb-c is 100% read (read-only). Therefore, in ycsb-amost of time is spent on writebacks to disk by WiredTiger, but ycsb-c is read-onlyis served fully from memory, making it a true in-memory workload. Therefore,we donât include the results from ycsb-a and only concentrate on the results of theycsb-c. Workloads follow a zipfian distribution. After the populate and warmupphase, we run ycsb-c for 600 seconds with 8 threads and 12M data entries andrecord their operation performance. The total data in memory takes approximately12GB. We limit the available memory with Cgroups to 6GB.We also tested Ligra-BFS and Memcached but due to similarity of the resultswe do not include them in this thesis.3.3.2 ProfilingAn important part of our instrumentation is profiling. We use Linux perf events [6]to capture CPU stats during the execution. We sample the CPU stack trace with1KHz frequency and filter the samples by PID of the target process. We also collectthe number of page faults during every 5 second period. From sample counts, wederive the code paths for which the most CPU cycles are consumed.3.4 Results3.4.1 Performance and RuntimeFirst we analyze the overall performance of tests with each block device runningthe mentioned benchmarks.17inmem vramzramzswapdiskDevice050100150200250Runtime (sec)tpc-c - Runtime ComparisonFigure 3.1: Runtime comparison of tpc-c benchmark running on VoltDB using dif-ferent swap devices.We can see the runtime results of VoltDB in figure 3.1. The benchmark makes5,800,000 total procedure calls. Overall, the workload is not too sensitive to swapdevices. We also observed a low number of page faults. This is mostly because ofnon-uniform access pattern of the benchmark, in which frequently accessed dataremains in memory.Another surprising pattern is insignificant advantage of VRAM over ZRAM.Biggest performance drops are seen from in-memory (no swap) execution to VRAMand then from compressed swap to swapping to disk. This indicates that simply theoperation of swapping triggers a high penalty. The software overhead of swapping,although way smaller than disk I/O, seem to be dominant compared to the com-pression/decompression.For WiredTiger we observe the average performance after the warmup phase.We see the performance results of ycsb-c in figure 3.2. Since ycsb-c is read-only, there are no external writes to disk and the results very well represent anin-memory workload. In-memory execution acheives a very high throuhgput ofmore than 1.5 M.Ops/sec. We see that using swap simply kills the performanceeven when using VRAM. The memory limited executions lead to an excessivenumber of page faults. Disk based swap causes around 99.7% performance degra-dation over in-memory execution. ZRAM perfroms 10 times better than disk swap.VRAM performs twice better than ZRAM which indicates that in ideal case we can18inmem vramzramzswapdiskDevice0.00.20.40.60.81.01.21.41.6Throughput (M.Ops/sec)ycsb-c - Throughput ComparisonFigure 3.2: Throughput comparison of ycsb-c (read-only) benchmark running onWiredTiger using different swap devices.get twice better performance by accelerating compression/decompression. How-ever, it is notable that VRAM still performs 6% of in-memory execution which isdetrimental.3.4.2 CPU Stack TraceThe timing results were different from the common expectations and mostly pointedtowards lack of performance in vram. Therefore we investigate this issue by ex-ploring how the CPU cycles are spent through each execution and what parts arecausing the bottlenecks. We collected the samples during the execution usng LinuxPerf events and accumulated the samples based on parent functions in the functioncall trace.VoltDB: We analyse the stack profile from execution of tpc-c benchmark onVoltDB. We see that VRAM accelerations help it spend at most 40% less timeservicing the major page faults. Though a significant difference, it does not seemto be a huge win over ZRAM. It is notable that in all executions the involved CPUshad close to 100% utilization with no I/O sleep.To observe in more details, we magnify the profile of page faults in figure3.4. As we can see around 38% of cycles in page faults are actually spent insidethe ZRAM module. Furthermore, compression/decompression functions make up19compression/decompression28.0%other ZRAM module7.0%rmap walks15.0%TLB flush20.0%shrink LRU lists15.0%others15.0%Figure 3.3: YCSB-C on WiredTigercompression/decompression30.0%other ZRAM module8.0%rmap walks8.0%TLB flush25.0%shrink LRU lists15.0%others14.0%Figure 3.4: TPC-C on VoltDBFigure 3.5: Stack profile analyses of page faults in each execution. Percent-age of CPU cycles spent in page faults is shown for each task.only 28% of page fault cycles. On the other hand, we recorded around 13% ofVRAM page fault cycles are spent in VRAM functions that are mainly memcpyand the rest of the VRAM stack profile is very similar to ZRAM. In both systems asignificant share of time is spent on the swap subsystem, mainly on page evictionmechanisms.We analyzed the profile for ycsb-c test. As expected from high number ofmajor faults, the effect page faults are exacerbated. The overall significance ofpage faults seem unchanged between ZRAM and VRAM. We look at the internalprofile of page faults in ZRAM and VRAM when running ycsb-c on WiredTiger.Figure 3.3 shows a breakdown of the CPU cycles spent during page faults. Contraryto our intuition and similarly to the previous test, less than 30% of cycles are spent20on compression/decompression. It is notable that inside ZRAM, other than totalcompression/decompression time, page allocation and bookkeeping time are alsosignificant.We observed from the performance profiling of our test that the cost of somefunctions on the swap path and especially on the page eviction path is exhaus-tive. Functions inside the eviction path (try charge and do free pages) forbookkeeping and modifying the page tables (unmapping the victim page) are com-parable to compression of a 4K page. Therefore, kernel paging stack can dominatethe compressed memory costs.3.5 DiscussionThis short study tried to shed light on the performance considerations of the swapsystem and showed us internals of the software-defined swap devices. We summa-rize our most important observations in this section.Firstly, we saw that compression is an efficient and low-cost way of acquiringextra memory. Even in a fully software-defined method like ZRAM the compres-sion/decompression costs are very reasonable compared to the rest of the memorysystem tasks and the compression ratios of above 2:1 are possible.Hardware acceleration of compression/decompression for these systems how-ever, may not be in high priority for system optimization. As we saw, even thoughthe compression/decompression of pages is a significant task, the actual operationsare not where the bulk of CPU cycles are spent. Noting the Amdahlâs law, acceler-ating decompression does not lead to huge immediate benefits.Another aspect that we should consider is the intricacies of the actual processing-in-memory (or near-memory) hardware that leveraging their full potential requirestechniques like batching and data-level parallelism [86]. This is unlikely to beachieved with current swap systems. Compressing/decompressing small set of 4Kpages using hardware accelerators is unlikely to improve the latency as the mainadvantage of typical devices is higher bandwidth.Overall, we believe several steps are necessary before processing-in-memoryaccelerated compression can be beneficial. The design space of memory manage-ment is wide and the memory management stack spans from higher level policies21all the way down to the hardware architecture. We recommend the following ap-proaches for future compressed far memory systems:Optimization of the swap path. To avoid hitting the bottleneck of page eviction,this process must be optimized and also moved off the critical path as much aspossible. Proactive eviction has been successful to some extent [110]. Still there isa lot of room for optimization of swap path.To make usage of accelerated far memory and amortize the paging overheads,the system has to evict and prefetch pages aggressively in bigger batches. Thiswould require redesigning swap policies with better insights and information de-rived from applications or hardware. Avoiding even a fraction of faults proveshighly beneficial, surpassing the advantages of accelerating internal functions offar memory.At lower levels of the system stack, architectures aimed at facilitating fasterpaging operations, such as expediting TLB invalidations (refer to [5]), can beimplemented. Additionally, alternative non-paging architectural approaches (asdiscussed in [89]) could be explored, albeit differing from the far memory con-cept. An intriguing avenue for hardware designers could involve the explorationof hardware-assisted paging through more advanced Memory Management Unit(MMU) architectures.3.6 ConclusionThis short study shed light on the overheads of compressed swap devices anddemonstrated the performance obstacles of such systems. Moving forward, in thisthesis we want to address the problem from upper layers of the memory man-agement stack. we want to revamp the paging path to accommodate widespreadutilization of far memory and potential acceleration. Achieving this requires a highdegree of flexibility in the memory management stack. In this thesis, as a step inthis direction, we propose delegating a portion of the paging stack to user spaceand applications. By this approach, we can design policies to optimize the evictionand prefetching path.22Chapter 4Enabling Application-AwareMemory Page Placement Policiesand Mechanisms with Extmem4.1 IntroductionAs mentioned in chapter 1, memory management is pivotal in computer systems,affecting performance and costs [27, 104, 110]. DRAM cost trends make memoryscarce in datacenters [72, 79, 105]. This is aggravated by demanding workloadslike machine learning and large-scale data processing [20, 26, 48, 53, 61, 81, 91, 97,101]. To tackle this, innovative memory architectures like disaggregated and tieredmemory [24, 77, 79, 94, 112], along with memory-centric computing [85, 86], arecrucial.As we explored in the previous chapter, memory management and paging poli-cies play a vital role in the performance of different memory architectures. Toutilize the far memory and other novel architectures we saw that we should opti-mize the paging path and develop new eviction and prefetching policies. However,in this evolving landscape, the concept of a one-size-fits-all memory managementpolicy is no longer tenable [43, 46, 51]. While researchers have illustrated instanceswhere general-purpose operating system memory managers fell short in catering to23the needs of data-intensive applications [16, 31, 69, 111, 113], this inadequacy hasbeen exacerbated with the ongoing innovations in memory architecture and theincreasingly diverse range of hardware configurations [32, 46, 63]. For example,researchers have shown that a major bottleneck in the system can be memory man-agement and page faults rather than device bandwidth [22]. Consequently, the se-lection of memory management policies has become a case-specific endeavor. Forinstance, in the context of datacenters, TMO [110] achieved 20% memory savingwithout significant performance penalties by tuning the kernel policies that offloadmemory to SSD devices. Canvas [109] proposes a prefetcher for JVM, Semeru[108] modifies the in-kernel swap system to support JVM runtime disaggregation,and Dilos [114] proposes a prefetcher for Redis [35]. Unfortunately, these ap-proaches do not work for the general case. Prior research has also underscored theinefficacy of traditional paging policies in tiered memory systems [46, 94], leadingto the development of specialized policies.Developing, testing, and deploying new memory managers in the kernel is chal-lenging [54]. The Linux memory management system is a core kernel componentthat must function effectively for multiple objectives in the system, and in the re-cent years, it has become increasingly complex, with some calling for emulators orsimulators to help [9, 15]. Developing new memory policies is a research-intensivetask that is further slowed by the kernel development process. For example, im-plementing the Leap prefetching algorithm [23] required modification of 20 kernelfiles, even though the algorithm itself can be expressed in 20 lines of code. Re-searchers that built Canvas [109] report spending 17 months on kernel develop-ment for paging policy optimizations. Furthermore, deployment of new systemsrequires rigorous testing to maintain system stability. Care must be taken to avoidaffecting other applications [14]. As a result, many developers are hesitant to addspecial-purpose memory management enhancements to the kernel [12].Previous efforts addressing memory management challenges either require sub-stantial kernel modifications [22, 32, 112] or entirely new kernel architectures[73, 98]. Dilos [114] implemented prefetching in its library OS to circumventkernel paging stack limitations. While these conceptual advances hold value, theyoften prove hard to implement and deploy.Prior attempts at user-space memory management have significant shortcom-24ings, as they either require runtime support [57, 95, 108], application modifications[42, 106], are for specific applications [71, 99] or specific memory back-ends [94],or cause high overheads [33, 84, 90] with severe limitation.We introduce EXTMEM, a framework designed for application-based memorymanagement in user space that avoids the shortcomings in prior work. EXTMEMelevates the task of memory management policies and paging mechanisms to userspace. By operating alongside the Linux kernel, our approach allows the kernelto maintain security and isolation while delegating memory management policiesto user space. Our framework provides ease of development and rapid testing inuser space. EXTMEM has high observability and offers data collection modules formetrics such as access bits and hardware counter samples.EXTMEM builds on well-known ideas and mechanisms, such as user-levelpage fault handling, kernel signals and upcalls, but it brings them together ina novel way to enable bespoke memory management policies in modern Linuxdeployments with overhead similar to that of in-kernel paging. EXTMEM oper-ates seamlessly without necessitating any modifications to application code, whilealso empowering application developers to implement application-specific mem-ory management policies, using EXTMEM .Developers can use EXTMEM for three main tasks:â¢ As a framework for development and testing new memory managersâ¢ Quick deployment of highly customized memory managers for specific usecasesâ¢ As a method to gain control and observability over working memory of soft-ware such as serverless frameworks, garbage collectors, and databases.EXTMEMis publicly available as open-source software.4.2 The 2024 Case for External PagingFor more than four decades, researchers have advocated the idea of granting ap-plications control over memory management [34, 100]. Even today, the majorityof large-scale commercial database servers continue to handle their memory man-agement independently [16, 62, 96]. Despite substantial advances in the Linux25memory management subsystem, situations where the kernelâs memory manageris inadequate still arise [40, 69, 114]. While micro-kernels offer an elegant so-lution to the external paging problem, their adoption for production use has beenhindered by complexities [36, 59]. In contrast, the monolithic paging model hasgained widespread acceptance due to its transparency, ease of use, and strong per-formance in a wide range of common use cases.Yet, memory management is even more important today than in the past, dueto new disaggregated memory architectures [22, 56] and new memory technology,such as CXL [102] and processing-in-memory (PIM) [50]. We first discuss howthe need for sophisticated memory management is even more pressing today thanit was in times past (section 4.2.1). We then discuss how microkernels addressedthis problem and how newer semi-kernels are a modern-day, deployable techniqueto leverage the benefits of the microkernel.4.2.1 New Memory ArchitecturesThe memory management issues have gained heightened interest in our era [43,110], due to the rapid evolution of memory architecture and increasing hetero-geneity of execution environments [51, 76, 77]. The landscape is continuouslyshaped by emerging devices featuring novel architectures. Prominent among theseare innovative memory architectures such as disaggregated memory [22, 55, 56],software-defined far memory [67], and memory-centric computing [50], all ofwhich are actively advancing. Each of these architectures present a unique array ofchallenges and advantages and have their own use cases.As mentioned in chapter 2, each environment and architecture presents uniquechallenges and advantages, necessitating specialized memory management approaches.This complexity underscores the need for tailored solutions to optimize memoryutilization and performance across diverse environments. Effective memory man-agement requires observing system behavior and memory access patterns, consid-ering application domains and hardware specifics, and making informed decisionsto optimize the performance and quality of service.264.2.2 Microkernels and SemikernelsMicrokernels are operating system architecture that have addressed memory man-agement differently by implementing page fault handlers and memory managersas servers in user space. Microkernels such as Mach [92], offer improved codemanagement, enhanced security, and isolation by placing OS functionality in user-space servers [59, 64, 65, 78]. However, their adoption has been limited. Thesemicrokernels implement their memory pagers in user space using Inter ProcessCommunication (IPC) [64, 78]. These microkernels and their memory managersmostly focus on isolation and security [64] and despite their configurability andflexibility, they have not been attractive solutions due to lack of adoption, perfor-mance problems, and contention in fault handler among threads.We want to design a framework deployable in production environments (e.g.Linux) with minimal disruption to the system. Therefore, we opt for an architec-ture that is inspired by microkernels but works alongside conventional monolithickernels to realize a partial memory management subsystem. This architecture thathas gained popularity is also known as a Semi-microkernel, exemplified by projectslike Snap [83], uFS [82], Shenango [87], and ghOSt [60], implements partial or en-tire OS subsystems, such as the networking stack in a user space process working inmonolithic kernel environment. Our system adopts a semi-microkernel structure tofacilitate streamlined development of bespoke management policies for memory-intensive applications.4.3 EXTMEM: DesignOur main design goals for EXTMEM is to:a) enable experimentation with advanced memory management policiesb) provide robust trace gathering capabilities to gain control and observabilityover the working memory of real executionsc) allow quick deployment of highly customized memory managers withoutkernel modification or kernel downtime, across a wide range of scenarios,excluding only the most latency-sensitive situations.27To realize these goals in a practical manner, EXTMEM must have the followingproperties:â¢ Non-intrusiveness: Any kernel modifications necessary to support EXTMEMmust be isolated, safe and transparent to applications.â¢ Ease of Development: Non-kernel programmers should be able to easilydeploy algorithms in EXTMEM .â¢ Transparency: EXTMEM should work with unmodified application code.â¢ Isolation and Safety: Application-specific memory managers should not beable to corrupt the kernel or applications that are not employing them.â¢ Efficiency: The framework should not introduce new performance bottle-necks.â¢ Faithful Implementation: Results obtained using EXTMEM should remainapplicable when the algorithms are implemented natively in the kernel.These criteria advocate a library-OS like design deployable in a Linux envi-ronment. Operating within a user address space ensures that an EXTMEM instancecannot access memory it doesnât manage, thus ensuring isolation. In the event ofa failure within an EXTMEM instance, its impact remains confined to its own do-main, allowing the kernel to manage and rectify the situation without disruptingrest of the system.4.3.1 The User ViewEXTMEM is designed as a dynamically linked library that seamlessly integratesinto a programâs address space and execution. An application developer can modifyand recompile the EXTMEM code and parameters before starting the applicationto optimize according to the use case.User code can interact with EXTMEM in two ways: explicitly through dedi-cated library calls and implicitly through native memory-related system calls suchas mmap, madvise, and others. The implicit interface is created to ensure com-patibility with unmodified code. In implicit interface, we intercept target system28calls and associate them with their corresponding EXTMEM API calls for transpar-ent interaction. Table 4.1 summarizes the API in the current version of EXTMEM .Addition of other system calls or custom calls are possible. While using the explicitAPI calls requires compiling the application with EXTMEM user header, existingapplications can plug into implicit interface without any header or recompilation.EXTMEM manages interaction with the kernel.Developers can create their memory management solutions in EXTMEM bymodifying the EXTMEM code and recompiling their customized EXTMEM in-stance. The EXTMEM library is loosely structured into three layers: the core,the observability, and the policy. The core layer encompasses functions responsi-ble for interacting with the kernel: making system calls and receiving page faults.The observability layer provides the functionality commonly used by memorymanagers, including access to page table access bits from the kernel and accessfrequency sampling with hardware counters. The policy layer is responsible formaking memory management decisions and implementing them by invoking corefunctions as needed. The storage backend is seen as a part of core layer but it isflexible and can be implemented according to each block device. It only has toconnect to the core layer by providing the required interface.This layered design facilitates rapid and customizable memory manager de-velopment by non-kernel developers. The core layer demands careful attention tocorrectness,. Nevertheless, changes to that layer are only needed for the rarer sys-tem layer optimization. Instead, developers can readily craft new policies withinthe policy layer by leveraging the pre-existing core functions.In this chapter and the next we mainly describe the design of the core layer. Inthe chapter 6 we will explain the observability and policy layers.4.3.2 The Core LayerThe core layer handles paging and interacts with the kernel. We utilize the ex-isting userfaultfd interface in Linux to securely register areas for user-levelpage faults. userfaultfd is a kernel subsystem that enables managing areasof program memory at user space by forwarding page faults to a user program.The application must inform the kernel via userfaultfd file descriptor if it29Intercepted system call API call Functionmmap extmem mmap map a virtual memory regionmunmap extmem munmap unmap a virtual memory regionmadvise extmem madvise passing memory management hintsTable 4.1: Implicit interface of EXTMEM binded with system call intercep-tion to the explicit API calls.wants it to manage specific pages by registering them. Registration is achieved viaioctl userfaultfd calls with UFFDIO REGISTER flags.For a registered memory area, physical pages can be allocated and filled withdata using ioctl calls with UFFDIO COPY or UFFD ZEROPAGE flags. Writeprotection for pages, such as before writing them back to storage, is accomplishedusing ioctl with UFFDIO WRITEPROTECT flag.To unmap pages, we employ madvisewith MADV DONTNEED flag. Althoughnot a POSIX standard, on Linux, this operation effectively removes the mappingand releases the physical backing while retaining the virtual allocation.System Call Interception: These registration calls are used in implementingthe core layer. We do not require application developers to add these registrationcalls to the application code, but transparently by intercepting the system calls thatgrow and shrink the heap area: mmap, munmap, madvise. For that purpose,we employ Intelâs libsyscall intercept [17] that enables us redirect targetsystem calls to the wrapper code in EXTMEM library. From there, EXTMEM cancollect metadata, make decisions and eventually if needed make a system call tothe kernel.We note that this interception method operates without modifying the kernel;instead, it hot-patches the libc code to introduce redirection into our library. Thisintroduces a minimal overhead of just one additional function call before each sys-tem call, which is negligible compared to the inherent cost of the system call itself.In our current work, we focus on handling large heap mappings that trigger mmapand leave stack mappings (and sbrk) to the kernel. The latter typically concernssmall, short-lived data that should not be subjected to swapping or demotion. Afuture work would be to explore hooking allocator calls such as malloc and free togain another level of insight and control over the memory allocations.30EXTMEM maintains direct control over storage space for swap or file backings.EXTMEM core is desired to be agnostic to backend implementation, provided itoffers essential synchronous and asynchronous read/write capabilities for optimalperformance. In our prototype, weâve implemented an interface to NVMe SSD,leveraging the Linux IO uring interface and liburing library. RDMA interfacesprovide similar asynchronous semantics.Second-tier memory devices, like CXL attached memory, are typically pre-sented as additional NUMA nodes without CPUs. We perform basic page migra-tion using the move pages system call. We defer further exploration of tieringto future work, and believe that more robust interfaces, including userfaultfd andmadvise options for direct page allocation on specific nodes, can be developedfor optimal performance. Tiering interfaces are under active development in kernelcommunity [11].Although we use userfaultfd interface to register user controlled memory areas,we donât actually use userfaultfd to take page faults in user space. Instead, we havedeveloped our upcall method for fast and scalable user-level page faults. Chapter5 explains this method. Nevertheless, userfaultfd has a well developed interfacethat have matured over time and we found it advantageous to reuse it rather thanreimplementing a new subsystem.4.4 ImplementationWe implemented the current prototype of EXTMEM as a C library for Linux envi-ronments. It can be dynamically linked to applications using LD PRELOAD. Ourimplementation is based on Linux kernel 5.15 and involves one-time changes tothe kernel, primarily within the userfaultfd subsystem to support our frameworkâsfeatures, along with the addition of a fast-path upcall to the signaling subsystem.In this thesis, our primary focus is on anonymous memory and swap systems.File-backed memory can be handled as a specific case of swap, and handling tieredmemory can follow previous work [94].Our implementation incorporates various techniques from prior literature, suchas page access bookkeeping, notably inspired by Hemem [94]. Additionally, wedraw inspiration from database management techniques [44], including strategies31like hashing and linking pages. In essence, the current prototype serves as ageneral-purpose database engine tailored for data-intensive non-DBMS applica-tions.32Chapter 5Upcall UserfaultsThe primary challenge for EXTMEM is effectively handling page faults within theuser space. In current architectures, when a thread triggers a page fault, it makes acontext switch to the kernel. There are two main approaches for forwarding thesepage faults to user space: IPC (Inter-Process Communication) and upcall.Microkernels, such as sel4 [64], utilize IPC to transmit fault information to anendpoint in a dedicated user-space fault handler. The response is then receivedthrough IPC as well. A similar approach is adopted by the Linux userfaultfd [2].When a program registers a memory area with userfaultfd, it receives a file descrip-tor. Threads encountering faults in that area submit their fault information to thisfile descriptor and wait in the kernel. A handler thread monitors the file descriptor,receives and handles the page faults. The handler wakes up the faulting thread byissuing a relevant ioctl system call. Userfaultfd finds common use cases in vir-tual machine hypervisors [1], databases [18], and runtime garbage collectors [52].While userfaultfd has been adopted in recent memory management research [33,94, 109], it exhibits two inherent performance issues that render it unsuitable forour purposes. First, the communication between faulting and handler threads es-sentially constitutes an IPC mechanism, incurring considerable overhead and bur-dening the scheduler. Second, userfaultfd becomes a point of serialization, limitingscalability. Even if multiple handler threads are active, they must synchronize overthe file descriptor and the wait queue of faulting threads. Consequently, userfaultfdis only useful in scenarios where page faults are infrequent, not latency-sensitive,33KernelApplication User fault endpoint1234856fdPage FaultFigure 5.1: Userfaultfd method: 1. Application registers a memory area withthe kernel and receives a file descriptor. 2. A handler thread calls se-lect/poll system call on the file descriptor. 3. A thread triggers a pagefault and context switches into the kernel. 4. After verifying the faultingaddress, kernel submits the fault information to the file descriptor andblocks the faulting thread. 5. The user-level handler receives the fault,performs the necessary IO and data preparation. 6. A user level makesa system call to map the new page and unblock the faulting thread. 7.Faulting thread goes back to continue the execution. The red arrows areinter-process-communication.or necessitate inter-process cooperation. Furthermore, this execution model signif-icantly differs from the kernel model, making it less suitable as an experimentalplatform for policy development.Another approach for handling a page fault in user space is through an upcall.Operating system architectures like exokernels [45, 58] and multi-kernels [28] useupcalls to handle page faults within the same process in user space. This approach,known as self-paging, offers advantages in terms of flexibility [62], scalability [28],and Quality of Service (QoS) [58].5.0.1 EXTMEM Upcall PathWe needed an upcall path within the Linux kernel for EXTMEMâs user-level pagefaults. The closest element to an upcall inside the Linux kernel is the signal han-dling path. The kernel can direct signals like SIGBUS to the same thread (task) and34KernelApplication User fault endpoint123645Page FaultFigure 5.2: Upcall method based on Linux signal path: 1. Application reg-isters a memory area with the kernel and registers an upcall handlerfunction. 2. A thread triggers a page fault and context switches intothe kernel. 3. Kernel makes an upcall by registering the upcall handlercontext on the faulting threadâs stack 4. The faulting thread is back inuserland, executes handler code to perform the necessary IO and datapreparation. 5. Faulting thread makes a system call to map the newpage and return from the upcall. 6. Faulting thread goes back to con-tinue the execution. No IPC is necessary.set up a new context on the threadâs stack before returning to user space. This waythe thread jumps to the the signal handler function, resembling an upcall to thatfunction. We therefore adopt the SIGBUS handling pathway for the implementa-tion of upcalls. Using the existing signal path instead of implementing an upcalldirectly results in needing very few isolated changes to the kernel for adoption ofEXTMEM.We use the signal pathway for upcalls as follows. Normally, userfaultfd blocksthe faulting thread upon a pagefault, but we modified it to generate a SIGBUSsignal instead. Our core layer provides a signal handler for intercepting this signal,which eventually calls the policy layer.Unfortunately, the SIGBUS path produces contention on the per-process signalhandler structure in the kernel and limits the signal only to handler async-safefunctions. We addressed these challenges as follows.We create an independent upcall path by reusing the Linux signal subsystem35and structs. We introduce an additional signal handler structure within the Linuxtask struct, localized to each thread, exclusively used for handling forced faultSIGBUS by the same task. Consequently, tasks no longer contend for access toa shared structure. This both avoids safety issues from contention with rest ofprocess signals and also enables us to minimize thread-level locking in this path,significantly reducing contention. Although this method incurs some overheadcompared to a pure upcall, it exhibits the same scalability benefits as a traditionalupcall. We refer to this extra forced signal path as our upcall.5.0.2 Correctness ConditionsA signal handler must, in the general case, only execute functions that are async-safe, i.e., functions that can be asynchronously interrupted and re-entered. Sepa-ration of our upcall path from the general signal handler reduces our case from ageneral asynchronous interrupt to a restricted trap. An upcall is only made from acertain kernel code that is only executed after a page fault on user registered mem-ory. Nevertheless, page faults on user memory can still happen at any point in theuser program. To address the safety and correctness issues and to avoid undefinedbehaviour, we impose the following conditions on EXTMEM. These condition af-fect only EXTMEM and have no effect on the user application.1. No re-entrance: No user-level page faults occur within the EXTMEM do-main, as EXTMEM doesnât register its own memory with userfaultfd, and itavoids dereferencing unlocked user memory. Consequently, EXTMEM func-tions need not be re-entrant, providing design flexibility.2. Logical Domain Isolation: The program is split into two domainsâapplicationand EXTMEM. No specific conditions are imposed on the application do-main, allowing it to operate as usual. Domain transitions only occur duringpage faults, facilitated by the kernel, or via API and system calls related tomemory operations like allocation.3. We keep a strict separation of state, including global variables and meta-data, between the application and EXTMEM. The application can only mod-ify EXTMEMâs data upon entering the EXTMEM domain, while EXTMEM36never changes application data. To maintain this isolation, we avoid modify-ing hidden global process state in EXTMEM and refrain from using statefullibc functions like malloc and printf in EXTMEM.We note that the conditions 2 and 3 are not realized by strict isolation abstrac-tions but rather taken as a guidance in design and implementation. Therefore, stateisolation in current version of EXTMEM is only conceptual. Actual isolation andverification of the above conditions would be a future work.Taking these conditions into account, EXTMEM only has to be thread safe.User level memory management policies can be written just like any multi-threadedapplication.5.1 Upcall PerformanceWe empirically assessed our upcall approach, focusing on scenarios with a highfault rate (Figure 5.4). In our microbenchmark, a varying number of threads con-tinually accessed pages in a newly allocated memory area to generate minor faults.We measured end-to-end latency for each memory access method and computedthe average page fault latency.The experiment was run on a 2-socket machine (16 cores, 32 hardware threadseach) with 2.30GHz Intel Xeon 5218 cores and 198GB of DDR4 DRAM, runninga modified Linux 5.15. All faults are minor and no I/O involved in this test.Our evaluation shows latency accumulation in the userfaultfd handler, whilethe default SIGBUS approach showed better scalability but some serialization. Incontrast, our upcall method exhibited superior scalability, mirroring the native ker-nelâs behavior until increased latencies were observed in both cases due to mmaplock contention. Ongoing developments in lockless paging [14, 37, 74] would ben-efit both in-kernel and user-level self-paging. Our approach effectively addressesprevious bottlenecks caused by user space methods.37Kernel SIGBUS UFFD Upcall024681012Latency(µs)Figure 5.3: Average latency of resolving a single minor fault in a single-threadedexecution1 2 4 8 16 32Number of Threads0255075100125150175Latency(µs)KernelSIGBUSUFFDUpcallFigure 5.4: Average latency of resolving a minor fault in a multi-threaded systemunder pressure38Chapter 6Policy DesignIn this chapter, we delve into how EXTMEM navigates memory management de-cisions via its policy layer. We also demonstrate the default policies currentlyimplemented in the EXTMEM prototype. The ability to practically implement andapply different policies stands as a key contribution of EXTMEM, as it empowersrobust and adaptable policy design. The application of a policy primarily entailsgathering insights from past memory accesses, performing calculations, makinginformed decisions, and subsequently guiding paging actions accordingly.A diverse array of data tracking tools can be employed in the observability layerto capture access patterns. The policy layer, in turn, assimilates this collected dataand invokes core functions to execute necessary operations. With a layered designapproach, the actual policy implementation remains concise, facilitating stream-lined development and experimentation of various methods across both layers.6.1 Observability LayerOne of the essential memory management tasks is tracking data accesses to differ-entiate frequently accessed (hot) and infrequently accessed (cold) data, enablingefficient data placement and cache replacement and prefetching strategies. Currentversion of EXTMEM exposes three primary types of access data used by the kernel.First, we capture page faults along with their faulting addresses. Each majorpage fault is equivalent of a cache miss in a caching algorithm and can be used39in the policy. Further information such as access type (read or write) and threadnumber can be derived from page faults as well.The second metric is checking the Access (A) and Dirty (D) bits set by theMMU in page table entries. Our current prototype uses simpler ioctl calls addedto the userfaultfd interface. While these calls are inefficient, they are mostly doneoff the critical path (unless under extreme reclaim pressure). Checking D bitsis also done with write protection upon write-back. Optimizing these calls withbatching or leveraging eBPF for access bit examination should be explored in thefuture. Specialized ioctl system calls for accessing these bits in user space arepending in the upstream kernel [10].The third metric for tracking pages relies on sampling CPU accesses with hard-ware performance counters, particularly useful for tiered memory systems thatdonât trigger major page faults [84]. We have implemented this metric using Linuxperf event interface. Sampling methods have potential for further development andoptimization, given their flexibility and relatively recent adoption.EXTMEMâs telemetry is not limited to the mentioned methods. Additionalapproaches, such as using eBPF for getting tracing information from the kernel orprogram-guided hints can be employed to complement EXTMEMâs capabilities infuture.6.2 Policy LayerWithin the policy layer, developers implement custom policies that identify coldpages for eviction or demotion and select potential pages for prefetching or pro-motion.Essentially the policy layer maintains a list of free pages and return them tofaulting threads for allocation or swap-in operations. EXTMEM keeps tabs onpages using page structs, and a policy can choose to maintain additional meta-data as necessary. Struct pages are hashed by their virtual address and kept inlinked lists. A policy can implement and use any extra data structures to applymore sophisticated algorithms.Since we use the upcall method for page faults, the working procedure of thepolicy layer is very similar to the Linux memory manager implementation. Each40faulting thread works to resolve its page fault and in case of multiple faults thethreads have to synchronize with each other. Therefore, each faulting thread startsfrom the faulting entry point and goes through the policy functions until it returnswith the filled physical page. Faulting threads can call the core functions for I/Oand low level operations. The core functions may call other helper threads for I/O.In addition to the faulting threads, policy layer can employ extra threads forinternal memory management work. For example, similar to the Linux kernel weimplemented a kswapd thread to examine page accesses and reclaim some pagesin the background to reduce the memory pressure. Other threads such as extraprefetchers (as we see in chapter 8) or access samplers can be leveraged.To keep the ease of development and reasoning, the policy does not touch onlow-level operations of the core that require careful synchronization and debug-ging. Instead, it is built on a set of functions exposed by the core. The core in-terface itself is flexible. Table 6.1 shows the set of core functions exposed to thepolicy layer in the current implementation of EXTMEM. A policy implementationcan be a set of data structures with calls to core and observability functions.One important point about core functions is the set of asynchronous I/O func-tions available to the policy. These functions enable a policy thread to plan itstasks and I/O requests for the desired performance. We also found that it matterswhether a thread blocks on I/O or polls for the result. The polling mode has betterlatency but increases CPU usage and therefore is suitable for latency-critical tasks.Blocking mode ensures better thread-level parallelism.Notable that policies are still implemented as multi-threaded code in EXTMEMframework (currently in C language)Code generation and synthesis of differentEXTMEM policies according to high-level specifications would be an interestingfuture work.6.3 Default Policy: 2Q-LRUImplementing a set of high-performing predefined policies in EXTMEM and al-lowing easy configuration changes to use them would offer significant advantages.Currently, our prototype includes a default policy, which is a recreation of theLinux 2-queue least recently used (2Q-LRU) algorithm known for its effectiveness41fault entry Entry point of upcall/ signal handlerhandle minor fault handle a minor faulthandle major fault handle a major faulthandle permission fault handle a permission (mostly write protection) faultuser mmap redirection point of mmap callsuser munmap redirection point of munmap callsuser madvise redirection point of madvise callscore sync read Synchronously read pages from backing devicecore sync write Synchronously write pages to backing devicecore async read start Start an asynchronous readcore async read finish Wait/poll an asynchronous read for completioncore async write start Start an asynchronous writecore async write finish Wait/poll an asynchronous write for completioncore writeprotect Write-protect given pagestry prefetch Prefetch requested pagestry prefault Prefault requested pagesTable 6.1: Set of core API connected to the policy layer in the currentEXTMEM implementationin typical scenarios. This default policy primarily utilizes access bits in OS pagetables to make informed eviction decisions.The 2Q-LRU algorithm extends the traditional Least Recently Used (LRU)cache eviction strategy. It prioritizes keeping frequently accessed pages in mem-ory while efficiently handling one-time scanning workloads, thereby demonstratingresilience. The key components of this algorithm are illustrated in Listing 1. Man-agement of active and inactive pages involves maintaining two FIFO lists, similarto the approach used in the Linux memory manager. A user-level kswapd threadoversees page scanning and memory balancing by reclaiming inactive pages. Ad-ditionally, when a specific threshold is reached, the user kswapd thread triggersevictor threads to write the least used pages to swap space.In Chapters 7 and 8, we will demonstrate how EXTMEM, equipped with itsLinux-like policy, performs comparably to the native Linux policy and even out-performs it most benchmarks due to the efficiency of its paging stack.42Algorithm 1: 2Q-LRU Reclaim AlgorithmFunction page reclaim (nr pages):Shrink inactive list(nr pages);Shrink active list(active shrink rate);Function Get free page ():while 1 doif free page available thenreturn free page;elseWake up kswapd();page reclaim(nr pages) // direct reclaim;Function Shrink inactive list(nr pages):while pages reclaimed < nr pages dopageâ dequeue from inactive list;if access bits = 1 thenif page accessed before thenenqueue page to active list();elseenqueue page to inactive list();elseReclaim page;pages reclaimed+= 1;43Function Shrink active list(nr pages):while nr pages removed dopageâ dequeue from active list();enqueue page to inactive list();Function Kswapd():while true do// Derive parameters from systemnr inactive shrink,nr active shrink =memory pressure();Shrink inactive list(nr inactive shrink);Shrink active list(nr active shrink);Sleep if high in memory;6.4 VMA-based PrefetcherWhile cache algorithms handle eviction decisions, prefetching represents anothercritical aspect of a policy aimed at efficiently accessing data residing outside ofprimary memory. EXTMEM, like the kernel, embraces prefetching as a policyfeature.Traditionally, page prefetching relied on the physical location of swapped pageson disk, leveraging sequential disk access to mitigate the high mechanical seektimes in old disks. However, with modern SSD storage perfromance constraintshave changed and there is a greater emphasis on program access patterns to en-sure effective prefetching (accuracy and coverage). Consequently, recent Linuxversions have adopted VMA-based (virtual memory areas-based) prefetchers.To demonstrate the ease of policy design in EXTMEM, in our current prototype,weâve implemented a simple virtual memory-based prefetcher. Like the LinuxVMA-based prefetcher, our prefetcher monitors faulting pages using their vir-tual addresses, keeping a brief history to identify recurring sequential patterns andprefetching a window of pages accordingly (2). Notably, this practical prefetcheris implemented in a mere 10 lines of code. In Chapter 7, We demonstrate that itsperformance matches that of Linux. We also highlight its flexibility through cus-44tomizable prefetching aggressiveness. Adding support for strided access patternsto this prefetcher is straightforward.Additionally, EXTMEM provides a good basis to develop prefetchers for moreintricate patterns, such as pointer-directed or machine learning-based prefetchingin future work.Algorithm 2: Virtual Address Based PrefetcherInput: Faulting AddressOutput: Enable or Disable PrefetchSaved State: previous fault[k];if previous fault members are sequential pages and faulting address =previous fault[0] + page size thenenable prefetch;elsedisable prefetch;Shift all previous fault up;previous fault[0] = faulting address;return;45Chapter 7EXTMEM EvaluationIn this chapter we demonstrate the functionality of EXTMEM in core and policy.We assess our upcall-based method for handling user-level page faults in Subsec-tion 5.1, minimal overhead of EXTMEMâs paging stack in Subsection 7.1, andprefetching functionality in a sequential workload in Subsection 7.2. In subsection7.3 we demonstrate EXTMEMâs ability to apply a policy and working set detectionwith a microbenchmark.EXTMEM delegates parts of the memory management to the user space andworks as a replacement of the native kernel stack. Therefore, we compare it tonative Linux kernel as the baseline. We show minimum overhead of the pagingstack and also practicality of the policy layer by demonstrating the equal or betterperformance of the EXTMEM given the equivalent policies and same microbench-marks.To the best of our knowledge, no other user-level memory management systemequivalent to EXTMEM currently exists. As a comparative baseline, we use Umap[90], a user-space buffer that provides an interface similar to mmap. Umap isconstructed upon Linux userfaultfd and is highly multithreaded to handle taskssuch as prefilling and write-back of memory pages. While lacking facilities forflexible policy implementation, such as observability, Umap exemplifies the use ofuserfaultfd for managing page faults. We focus on the common ground betweenEXTMEM and Umap, particularly in microbenchmarks on a memory-mapped file,to showcase the effectiveness of our upcall method compared to the traditional46userfaultfd approach. In our experiments, we execute Umap with 10 filler threadsand 10 evictor threads.We ran all experiments on a 2-socket machine (16 cores, 32 hardware threadseach) with 2.30GHz Intel Xeon 5218 cores and 198GB of DDR4 DRAM, running amodified Linux 5.15. We used a NVME SSD disk with 2700MB/S read rate as ourstorage/swap backend. For Linux baseline, we use Cgroups to limit the memory ineach execution. EXTMEM memory and Umap buffer size are limited through theirinternal parameters. In both EXTMEM and Umap, the storage space is opened withO DIRECT flag to avoid OS and filesystem caches.7.1 Random Access MicrobenchmarkOur first microbenchmarks stress tests the pure paging stack. We continuouslyupdate random bytes in a pre-filled memory area of 16GB while limiting DRAMto 8GB. Therefore, 50% of memory is paged out and each access has 50% chanceof causing a major page fault regardless of the policy. Figure 7.1 shows the memoryupdate throughput as a function of the number of threads. We see that EXTMEMperforms better than Linux and scales with multiple threads. This is a result of thedesign that was described in 5. On the other hand we see that Umap has muchlower throughput and does not scale well with higher threads.1 2 4 8 16Number of Threads050000100000150000200000250000300000350000Average throughput (updates/sec)System Throughput ComparisonLinuxExtMemUmapFigure 7.1: Throughput of the system making byte-sized updates in the sce-nario of random updates when 50% of the working set fits in memory.471 2 4 8 16Number of Threads0.00.10.20.30.40.50.60.70.8Average throughput (GB/sec)System Throughput ComparisonLinuxExtMemUmapFigure 7.2: Throughput of the system making byte-sized updates in the sce-nario of sequential updates when 50% of the working set fits in memory.7.2 Sequential MicrobenchmarkWe next examine the behavior of a benchmark similar to the one in the previoussection where we access the bytes sequentially rather than randomly. We imple-mented a simple virtual address based sequential prefetcher and show the resultsin figure 7.2. Once again, EXTMEM outperformâs Linux. This time, the perfor-mance improvement is due to our using a more aggressive prefetching policy thanthe Linux default. Umap falls behind even more in this benchmark due to absenceof prefetching.Throughput plateaus sooner than expected at about four threads, due to thewrite-back bottleneck and expensive write-protect and madvise operations whenevicting pages to storage. A faster page unmapping path can resolve this in future.This problem does not stem from user-space paging and upcalls, but it mostlycomes from TLB shootdowns and kernel page table contentions.7.3 Hot Set MicrobenchmarkOur last benchmark is another variant of the random microbenchmark. In this test,we ran a similar workload to those in previous sections but with a twist: 90% of up-480 20 40 60 80 100 120 140 160Time (seconds)0.00.51.01.52.02.53.03.54.0Throughput (Million updates/sec)Throughput Over Time for Different SystemslinuxextmemumapFigure 7.3: Throughput over time of evaluated systems for the working set accessmicrobenchmark. 90% of accesses go to 10% of memory while 50% of data fitsin the memory. EXTMEM-2Q-LRU efficiently keeps working set in memory.dates were aimed at randomly selected addresses within the first 10% of the mem-ory area, while the remaining 10% of updates targeted random addresses through-out the entire memory space. We used EXTMEM with the default Linux-like (2Q-LRU) policy explained in chapter 6. This experiment illustrated how EXTMEMefficiently identifies and keeps the working set in memory, much like Linux.Figure 7.3 shows system performance as a function of time, when we run witheight threads. In both systems, performance climbs quickly and then levels off,demonstrating that both Linux and EXTMEM loaded the working set into memoryand preserve it while swapping less frequently accessed data. Conversely, Umaplacks observability features and operates in a FIFO manner, occasionally leading tothe eviction of critical hotset pages and resulting in unexpected performance drops.49Chapter 8Case Study: PageRankGraph processing under memory constraints is an example of an application thatcan benefit from EXTMEM with application-specific memory management. Asa proof of concept, we implemented custom memory management for a graphprocessing application. Our goal is to achieve good runtime performance usingin-memory data structures, even if the graph exceeds available memory.Compressed Sparse Row (CSR) [41] is a prevalent data structure used for in-memory analytics. It consists of two arrays: a vertex array and an edge array (figure8.1). The vertex-array stores one pointer (index) for each vertex and indicates thestarting position in the edge array of the edges associated with the vertex. The edgearray stores all edges, sorted by vertex ID. Many graph analyses process vertexneighborhoods, so CSRâs sequential layout is attractive [49].We developed a custom memory manager based on two intuitions. First, edgesaccount for the majority of space consumed by a graph, because graphs typicallyhave many more edges than vertices.1 Second, many algorithms repeatedly iterateover neighborhoods. Our policy keeps all O(V )-sized arrays (where V is the num-ber of vertices) in memory. This includes the vertex array as well as arrays thatstore vertex-related attributes and intermediate values (e.g., the rank of vertices ina pagerank computation). In contrast, we store only a sliding window of the edgearray in memory. In each iteration over the edge array, we move this sliding win-1This proportion of edges to vertices is the average degree of a graph. For instance, in the Twittergraph, this proportion is equal to 35.504 1 5 1 3 2 4 7 1 5 51 3 4 5 6 7Vertex Array:Edge Array:572314 6GraphFigure 8.1: An example of representation of a graph in Compressed SparseRow (CSR). Using EXTMEM we apply custom policy to Vertex andEdge arrays.dow, evicting the pages that are no longer necessary and prefetch the next windowof pages in the background.We compare the runtime of pagerank using EXTMEM with specialized policycalled EXTMEM-PR, EXTMEM with default Linux-like policy and Linux Cgroups.We ran 10 iterations of the pagerank on the Twitter graph, using the standard GAP[29] benchmarking suite with 4 threads. We limited memory to 50% of the to-tal graph size. Figure 8.2 shows that using EXTMEM with an algorithm almostidentical to that of Linux (EXTMEM-2QLRU) produces a modest improvement,but when we deploy the custom algorithm (EXTMEM-PR), we obtain a speedupgreater than 2x. Surprisingly, using our user-level custom paging policy, whenonly 50% of the graph fits in memory, our runtime is only slighty over twice thatof a pure in-memory solution.51Linux ExtMem-2QLruExtMem-Pr InMemory0255075100125150175200Runtime(s)Figure 8.2: Average runtime of ten iterations of PageRank over twitter dataset with50% of data fitting in memory52Chapter 9DiscussionIn this thesis, we have demonstrated the feasibility and potential benefits of user-space application-directed memory management through the design and imple-mentation of EXTMEM.9.1 LimitationsEXTMEM represents an early-stage research prototype and many of the limitationswe have encountered are not fundamental obstacles but rather shortcomings of thecurrent implementation and also areas for improvement and expansion in futurework. In the following discussion, we will elucidate these key points.In-kernel page faults: Currently our upcall-based page fault handling pathcannot handle page faults on the user registered memory that happen in kernelspace. Though rare, these can happen when a system call involves copy from user(e.g. write system call). If the user page is controlled by EXTMEM and notpresent in memory, these system calls will fail with EFAULT. Userfaultfd also failssuch system calls in unprivileged mode but in general case is able to handle these.Incorporating this scenario into the upcall path is technically feasible but requirescareful implementation due to the complexities involved in transitioning from ker-nel to user space. Currently, we handle this problem by prefaulting the user bufferin the interception layer before invoking the actual system call.Small allocations: Currently, EXTMEM only intercepts large allocations trig-53gered by the mmap system call. Most allocators, such as malloc (whether useddirectly or by JVM), use mmap to handle large allocations. Intercepting smallerallocations through allocator libraries and assessing their impact remains a task forfuture investigation. Nonetheless, even among mmap calls, we have observed thebenefit of disregarding those allocations smaller than a few megabytes, as they con-stitute a minimal portion of memory but contribute significantly to overhead. Thisis partly attributable to the suboptimal implementation of the munmap system callin EXTMEM, resulting in excessive locking and performance bottlenecks, partic-ularly since smaller allocations are unmapped more frequently. Better implemen-tation of munmap and enhancing the efficiency of small mappings in EXTMEMshould thus be a priority in future iterations.Unmapping and TLB shootdowns: Currently, page eviction in EXTMEM re-lies on standard primitives in Linux, particularly madvise and userfaultfd writeprotect.However, these calls are not optimized, and each invocation triggers a TLB shoot-down, involving an inter-processor interrupt (IPI) that introduces system slow-downs. Microbenchmark experiments conducted in Chapter 7 revealed that theseevictions, rather than upcalls and user-space processing, are currently the limitingfactor in performance. The same bottleneck is observed in the Linux page cache,indicating a kernel-space limitation. Recent work by Leis et al. [74] has demon-strated that batching unmappings and TLB shootdowns can significantly alleviatethis issue and reduce its impact. Therefore, integrating these optimizations into thekernel to address performance limitations in EXTMEM should be considered forfuture development efforts.Memory Tiering: Second-tier memory devices, like CXL attached memory,are typically presented as additional NUMA nodes without CPUs. We can performbasic page migration using the move pages system call. Previously Hemem [94]has explored the memory tiering for in user space using DAX files. It would bestraightforward to integrate their method in future iterations of EXTMEM. How-ever, we defer further exploration of tiering to future work, and believe that morerobust interfaces, including userfaultfd and madvise options for direct page al-location on specific nodes, can be developed for optimal performance. Tieringinterfaces are under active development in kernel community [11, 84].549.2 Future WorkAs mentioned earlier, a crucial direction for future work involves addressing thelimitations of EXTMEM by enhancing and expanding its capabilities. Specifically,optimizing the unmapping process and TLB shootdowns appears to be the mostimmediate area for improvement.Also for several system calls and reading page table bits, though these opera-tions are currently expensive, there are huge optimization opportunities in the fu-ture, including batching, PMD-level operations, and interface enhancements withinthe evolving Linux ecosystem. EXTMEM internally keeps page metadata, a po-tential future development may explore sharing this metadata with the operatingsystem.In addition to performance enhancements, there are several other intriguingavenues for future research and development:Policy development: EXTMEM provides the perfect substrate for developmentof new application and domain-specific memory management policies. We canuse EXTMEM to get insight into the memory access patterns of an appliction orworkload. Then we can use this insight to apply new strategies. Implementation ofnew policies and testing them is fast in user space. One particular attractive methodwould be using machine learning for eviction and prefetching.Physical memory management: Currently, we rely on the kernel to managephysical addresses, limiting our focus to virtual addresses. Delving into physicaladdress presents intriguing research and optimization prospects but it also posessecurity and correctness challenges. Proposed system calls for moving physicalpages are in development within the kernel [13], making physical page handlinga potential avenue for future work. Additionally, the implementation of a user-space exposed physical memory allocator, possibly in hardware, has a significantpotential for exploration.On a higher level, another line of future work would be to explore hookingallocator calls such as malloc and free to gain another level of insight and controlover the memory allocations.559.3 Related WorkSeveral systems have been designed to pave the path for memory disaggregation.Inifniswap [55] took the native swapping with a block device over the network.G-swap [67] and TMO [110] proposed significant changes to the kernel memorymanager to make the swap subsystem ready for modern disaggregation. AIFM[95]tackles the problem with giving custom API to applications and a user spaceserver. Kona [32] proposes architectural changes with special software to reducethe effects of the paging. Canvas [109] creates a more application-aware swapsystem through extensive development in the kernel.The topic of multi-tier memory management for byte-addressable memory hasgained significant importance with the advent of NVM and CXL. Hemem [94] pro-poses a user space system for memory migration between two tiers. TMTS [43]also addresses different aspects of multi-tier memory. These systems have lever-aged moving certain components, particularly policies, to user space to facilitateeasier development.There has been a renaissance in microkernel-based approaches through Semi-microkernels [30, 87]. Snap [83] successfully implemented high-performance net-working in user space and has been in use in Google. uFS [82] is a highly scalablesemi-microkernel file system. ghOSt [60] delegates scheduling policies to userspace. All mentioned systems provide high code velocity and ease of deployment.U-swap takes a similar approach to explore the newer challenges of disaggregatedmemory and tries to further expand this experience.There are no practical user-space/semi-microkernel memory managers that canprovide the general purpose functionality that EXTMEM provides. Umap [90] isa user-space buffer (page cache) that might be the closest work to ours. Umap isimplemented by standard usage of userfaultfd virtual memory management and aswe saw in chapter 7 lacks in performance and does not provide a policy substratelike EXTMEM . Lightswap [115] resolves page faults in user space by contextswitching lightweight user-level threads (LWT) in an eBPF program. This methodonly works for programs using LWT environment, which are not common. Fur-thermore, we think context swtiching threads inside eBPF program is inherentlyproblematic. The lightswap prototype is not public to evaluate or confirm this.56Other works also have tried to address the lack of flexibility and difficulty ofdeveloping memory management systems in the kernel. FBMM [103] is a workparallel to our framework that proposes memory management inside a VFS kernelmodule. We are interested to see the comparison of two approaches (user space vs.VFS) in the future. P2Cache [70] customizes kernel page caches using eBPF. Wethink more advanced eBPF-based approaches can be promising in future. We areinterested to see how they can compliment EXTMEM or become an alternative toit.57Chapter 10ConclusionWe introduced EXTMEM, a versatile framework tailored for application-specificmemory management in user space. EXTMEM seamlessly integrates into Linux-based environments, offering developers a flexible platform with high code velocitywhile maintaining isolation by running in the applicationâs address space. Using anupcall approach, it establishes a scalable self-paging architecture, resolving short-comings of previous user-space paging systems. By reusing the signal handlingcode path for upcalls, EXTMEM requires only small isolated changes to Linux.EXTMEM still faces limitations stemming from scalability issues within theunderlying operating systemâs virtual memory system, particularly the mmap lock.Despite these limitations, EXTMEM empowers users to harness the performanceadvantages of application-aware memory management in real-world scenarios. Aswe continue to explore the workload and hardware-aware memory managementpolicies, EXTMEM provides a promising framework for future developments inthis domain.58Bibliography[1] Features/PostCopyLiveMigration - QEMU â wiki.qemu.org.https://wiki.qemu.org/Features/PostCopyLiveMigration. [Accessed11-01-2024]. â page 33[2] Userfaultfd(2). https://man7.org/linux/man-pages/man2/userfaultfd.2.html.[Accessed 15-03-2024]. â pages 3, 33[3] Cxl consortium â computeexpresslink.org.https://www.computeexpresslink.org. [Accessed 09-01-2024]. â page 10[4] Home - DPDK â dpdk.org. https://www.dpdk.org. [Accessed09-01-2024]. â page 11[5] Experimental Features speedup TLB shootdowns â saphire architecture.https://www.intel.com/content/www/us/en/developer/articles/technical/sdm-experimental-features-feedback-forum.html. [Accessed 12-04-2024].â page 22[6] Perf Wiki â perf.wiki.kernel.org.https://perf.wiki.kernel.org/index.php/Main Page, . [Accessed 23-02-2024].â page 17[7] zram: Compressed RAM-based block devices &x2014; The Linux Kerneldocumentation â docs.kernel.org.https://docs.kernel.org/admin-guide/blockdev/zram.html, . [Accessed23-02-2024]. â page 15[8] zswap &x2014; The Linux Kernel documentation â kernel.org.https://www.kernel.org/doc/html/v4.18/vm/zswap.html, . [Accessed23-02-2024]. â page 15[9] lpc.events. https://lpc.events/event/11/contributions/896/attachments/793/1493/slides-r2.pdf. [Accessed 09-01-2024]. â pages 2, 2459[10] Implement IOCTL to get and optionally clear info about PTEs [LWN.net]â lwn.net. https://lwn.net/Articles/934580/, . [Accessed 11-01-2024]. âpage 40[11] Memory-management changes for CXL [LWN.net] â lwn.net.https://lwn.net/Articles/931416/, . [Accessed 11-01-2024]. â pages 31, 54[12] Memory-management patch review [LWN.net] â lwn.net.https://lwn.net/Articles/718212/, . [Accessed 09-01-2024]. â pages 3, 24[13] Moving physical pages from user space [LWN.net] â lwn.net.https://lwn.net/Articles/944115/, . [Accessed 11-01-2024]. â page 55[14] The ongoing search for mmap lock â lwn.net.https://lwn.net/Articles/893906/, . [Accessed 09-01-2024]. â pages3, 24, 37[15] Readahead: the documentation I wanted to read [LWN.net] â lwn.net.https://lwn.net/Articles/888715/, . [Accessed 09-01-2024]. â pages 2, 24[16] Database Concepts â docs.oracle.com. https://docs.oracle.com/en/database/oracle/oracle-database/19/cncpt/memory-architecture.html.[Accessed 15-03-2024]. â pages 1, 24, 25[17] syscall intercept. https://github.com/pmem/syscall intercept. [Accessed15-03-2024]. â page 30[18] https://tech.nextroll.com/blog/data/2016/11/29/traildb-mmap-s3.html.[Accessed 10-01-2024]. â page 33[19] WiredTiger: Simulating workloads with wtperf â source.wiredtiger.com.https://source.wiredtiger.com/2.5.2/wtperf.html. [Accessed 23-02-2024].â page 17[20] M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin,S. Ghemawat, G. Irving, M. Isard, et al. {TensorFlow}: a system for{Large-Scale} machine learning. In 12th USENIX symposium on operatingsystems design and implementation (OSDI 16), pages 265â283, 2016. âpages 1, 23[21] A. Abulila, V. S. Mailthody, Z. Qureshi, J. Huang, N. S. Kim, J. Xiong, andW.-m. Hwu. Flatflash: Exploiting the byte-accessibility of ssds within aunified memory-storage hierarchy. In Proceedings of the Twenty-FourthInternational Conference on Architectural Support for ProgrammingLanguages and Operating Systems, pages 971â985, 2019. â page 160[22] M. K. Aguilera, N. Amit, I. Calciu, X. Deguillard, J. Gandhi,P. Subrahmanyam, L. Suresh, K. Tati, R. Venkatasubramanian, and M. Wei.Remote memory in the age of fast networks. In Proceedings of the 2017Symposium on Cloud Computing, pages 121â127, 2017. â pages2, 9, 10, 24, 26[23] H. Al Maruf and M. Chowdhury. Effectively prefetching remote memorywith leap. In 2020 USENIX Annual Technical Conference (USENIX ATC20), pages 843â857, 2020. â pages 2, 10, 24[24] E. Amaro, C. Branner-Augmon, Z. Luo, A. Ousterhout, M. K. Aguilera,A. Panda, S. Ratnasamy, and S. Shenker. Can far memory improve jobthroughput? In Proceedings of the Fifteenth European Conference onComputer Systems, pages 1â16, 2020. â pages 1, 9, 13, 23[25] S. Angel, M. Nanavati, and S. Sen. Disaggregation and the application. In12th USENIX Workshop on Hot Topics in Cloud Computing (HotCloud 20),2020. â page 1[26] B. Atikoglu, Y. Xu, E. Frachtenberg, S. Jiang, and M. Paleczny. Workloadanalysis of a large-scale key-value store. In Proceedings of the 12th ACMSIGMETRICS/PERFORMANCE joint international conference onMeasurement and Modeling of Computer Systems, pages 53â64, 2012. âpages 1, 23[27] L. A. Barroso, U. Ho¨lzle, and P. Ranganathan. The datacenter as acomputer: Designing warehouse-scale machines. Springer Nature, 2019.â pages 1, 23[28] A. Baumann, P. Barham, P.-E. Dagand, T. Harris, R. Isaacs, S. Peter,T. Roscoe, A. Schu¨pbach, and A. Singhania. The multikernel: a new osarchitecture for scalable multicore systems. In Proceedings of the ACMSIGOPS 22nd symposium on Operating systems principles, pages 29â44,2009. â page 34[29] S. Beamer, K. Asanovic´, and D. Patterson. The gap benchmark suite. arXivpreprint arXiv:1508.03619, 2015. â page 51[30] A. Belay, A. Bittau, A. Mashtizadeh, D. Terei, D. Mazie`res, andC. Kozyrakis. Dune: Safe user-level access to privileged {CPU} features.In 10th USENIX Symposium on Operating Systems Design andImplementation (OSDI 12), pages 335â348, 2012. â page 5661[31] A. Borg, A. Wellings, C. Gill, and R. K. Cytron. Real-time memorymanagement: Life and times. In 18th Euromicro Conference on Real-TimeSystems (ECRTSâ06), pages 11âpp. IEEE, 2006. â pages 1, 24[32] I. Calciu, M. T. Imran, I. Puddu, S. Kashyap, H. A. Maruf, O. Mutlu, andA. Kolli. Rethinking software runtimes for disaggregated memory. InProceedings of the 26th ACM International Conference on ArchitecturalSupport for Programming Languages and Operating Systems, pages 79â92,2021. â pages 1, 10, 24, 56[33] B. Caldwell, S. Goodarzy, S. Ha, R. Han, E. Keller, E. Rozner, and Y. Im.Fluidmem: Full, flexible, and fast memory disaggregation for the cloud. In2020 IEEE 40th International Conference on Distributed ComputingSystems (ICDCS), pages 665â677. IEEE, 2020. â pages 3, 10, 25, 33[34] P. Cao, E. W. Felten, A. R. Karlin, and K. Li. A study of integratedprefetching and caching strategies. ACM SIGMETRICS PerformanceEvaluation Review, 23(1):188â197, 1995. â page 25[35] J. Carlson. Redis in action. Simon and Schuster, 2013. â page 24[36] J. B. Chen and B. N. Bershad. The impact of operating system structure onmemory system performance. In Proceedings of the fourteenth ACMsymposium on Operating systems principles, pages 120â133, 1993. âpages 11, 26[37] A. T. Clements, M. F. Kaashoek, and N. Zeldovich. Scalable addressspaces using rcu balanced trees. ACM SIGPLAN Notices, 47(4):199â210,2012. â page 37[38] J. Condit, E. B. Nightingale, C. Frost, E. Ipek, B. Lee, D. Burger, andD. Coetzee. Better i/o through byte-addressable, persistent memory. InProceedings of the ACM SIGOPS 22nd symposium on Operating systemsprinciples, pages 133â146, 2009. â page 10[39] B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears.Benchmarking cloud serving systems with ycsb. In Proceedings of the 1stACM symposium on Cloud computing, pages 143â154, 2010. â page 17[40] A. Crotty, V. Leis, and A. Pavlo. Are you sure you want to use mmap inyour database management system. In CIDR 2022, Conference onInnovative Data Systems Research. https://db. cs. cmu.edu/papers/2022/p13-crotty. pdf, 2022. â page 2662[41] J. Dongarra, P. Koev, X. Li, J. Demmel, and H. van der Vorst. 10. CommonIssues, pages 315â336. doi:10.1137/1.9780898719581.ch10. URLhttps://epubs.siam.org/doi/abs/10.1137/1.9780898719581.ch10. â page50[42] A. Dragojevic´, D. Narayanan, M. Castro, and O. Hodson. {FaRM}: Fastremote memory. In 11th USENIX Symposium on Networked SystemsDesign and Implementation (NSDI 14), pages 401â414, 2014. â pages3, 9, 10, 25[43] P. Duraisamy, W. Xu, S. Hare, R. Rajwar, D. Culler, Z. Xu, J. Fan,C. Kennelly, B. McCloskey, D. Mijailovic, et al. Towards an adaptablesystems architecture for memory tiering at warehouse-scale. InProceedings of the 28th ACM International Conference on ArchitecturalSupport for Programming Languages and Operating Systems, Volume 3,pages 727â741, 2023. â pages 1, 10, 23, 26, 56[44] W. Effelsberg and T. Haerder. Principles of database buffer management.ACM Transactions on Database Systems (TODS), 9(4):560â595, 1984. âpage 31[45] D. R. Engler, M. F. Kaashoek, and J. OâToole Jr. Exokernel: An operatingsystem architecture for application-level resource management. ACMSIGOPS Operating Systems Review, 29(5):251â266, 1995. â pages 11, 34[46] S. B. P. Faldu and B. G. L. V. M. Silberstein. Reconsidering os memoryoptimizations in the presence of disaggregated memory. 2022. â pages1, 2, 10, 23, 24[47] A. Fedorova, C. Mustard, I. Beschastnikh, J. Rubin, A. Wong, S. Miucin,and L. Ye. Performance comprehension at wiredtiger. In Proceedings ofthe 2018 26th ACM Joint Meeting on European Software EngineeringConference and Symposium on the Foundations of Software Engineering,pages 83â94, 2018. â page 16[48] B. Fitzpatrick. Distributed caching with memcached. Linux journal, 2004(124):5, 2004. â pages 1, 23[49] P. Fuchs, D. Margan, and J. Giceva. Sortledton: a universal, transactionalgraph data structure. Proceedings of the VLDB Endowment, 15(6):1173â1186, 2022. â page 5063[50] S. Ghose, K. Hsieh, A. Boroumand, R. Ausavarungnirun, and O. Mutlu.The processing-in-memory paradigm: Mechanisms to enable adoption.Beyond-CMOS Technologies for Next Generation Computer Design, pages133â194, 2019. â page 26[51] C. Giannoula, K. Huang, J. Tang, N. Koziris, G. Goumas, Z. Chishti, andN. Vijaykumar. Daemon: Architectural support for efficient data movementin fully disaggregated systems. Proceedings of the ACM on Measurementand Analysis of Computing Systems, 7(1):1â36, 2023. â pages 1, 23, 26[52] L. Gidra, H.-J. Boehm, and J. Fernandes. Utilizing the linux userfaultfdsystem call in a compaction phase of a garbage collection process. 2020.â page 33[53] J. E. Gonzalez, R. S. Xin, A. Dave, D. Crankshaw, M. J. Franklin, andI. Stoica. {GraphX}: Graph processing in a distributed dataflowframework. In 11th USENIX symposium on operating systems design andimplementation (OSDI 14), pages 599â613, 2014. â pages 1, 23[54] M. Gorman. Understanding the Linux virtual memory manager. PrenticeHall Upper Saddle River, 2004. â pages 2, 24[55] J. Gu, Y. Lee, Y. Zhang, M. Chowdhury, and K. G. Shin. Efficient memorydisaggregation with infiniswap. In 14th USENIX Symposium on NetworkedSystems Design and Implementation (NSDI 17), pages 649â667, 2017. âpages 1, 9, 13, 26, 56[56] Z. Guo, Y. Shan, X. Luo, Y. Huang, and Y. Zhang. Clio: Ahardware-software co-designed disaggregated memory system. InProceedings of the 27th ACM International Conference on ArchitecturalSupport for Programming Languages and Operating Systems, pages417â433, 2022. â page 26[57] Z. Guo, Z. He, and Y. Zhang. Mira: A program-behavior-guided farmemory system. In Proceedings of the 29th Symposium on OperatingSystems Principles, pages 692â708, 2023. â pages 3, 10, 25[58] S. M. Hand. Self-paging in the nemesis operating system. In OSDI,volume 99, pages 73â86, 1999. â pages 3, 11, 34[59] G. Heiser and K. Elphinstone. L4 microkernels: The lessons from 20 yearsof research and deployment. ACM Transactions on Computer Systems(TOCS), 34(1):1â29, 2016. â pages 11, 26, 2764[60] J. T. Humphries, N. Natu, A. Chaugule, O. Weisse, B. Rhoden, J. Don,L. Rizzo, O. Rombakh, P. Turner, and C. Kozyrakis. ghost: Fast & flexibleuser-space delegation of linux scheduling. In Proceedings of the ACMSIGOPS 28th Symposium on Operating Systems Principles, pages588â604, 2021. â pages 11, 27, 56[61] C. Jiang, Y. Qiu, W. Shi, Z. Ge, J. Wang, S. Chen, C. Ce´rin, Z. Ren, G. Xu,and J. Lin. Characterizing co-located workloads in alibaba clouddatacenters. IEEE Transactions on Cloud Computing, 10(4):2381â2397,2020. â pages 1, 23[62] M. F. Kaashoek, D. R. Engler, G. R. Ganger, H. M. Briceno, R. Hunt,D. Mazieres, T. Pinckney, R. Grimm, J. Jannotti, and K. Mackenzie.Application performance and flexibility on exokernel systems. InProceedings of the sixteenth ACM symposium on Operating systemsprinciples, pages 52â65, 1997. â pages 25, 34[63] J. Kim, W. Choe, and J. Ahn. Exploring the design space of pagemanagement for {Multi-Tiered} memory systems. In 2021 USENIXAnnual Technical Conference (USENIX ATC 21), pages 715â728, 2021. âpages 2, 24[64] G. Klein, K. Elphinstone, G. Heiser, J. Andronick, D. Cock, P. Derrin,D. Elkaduwe, K. Engelhardt, R. Kolanski, M. Norrish, et al. sel4: Formalverification of an os kernel. In Proceedings of the ACM SIGOPS 22ndsymposium on Operating systems principles, pages 207â220, 2009. âpages 11, 27, 33[65] G. Klein, J. Andronick, K. Elphinstone, T. Murray, T. Sewell, R. Kolanski,and G. Heiser. Comprehensive formal verification of an os microkernel.ACM Transactions on Computer Systems (TOCS), 32(1):1â70, 2014. âpages 11, 27[66] M. Kwon, S. Lee, and M. Jung. Cache in hand: Expander-driven cxlprefetcher for next generation cxl-ssd. In Proceedings of the 15th ACMWorkshop on Hot Topics in Storage and File Systems, pages 24â30, 2023.â page 1[67] A. Lagar-Cavilla, J. Ahn, S. Souhlal, N. Agarwal, R. Burny, S. Butt,J. Chang, A. Chaugule, N. Deng, J. Shahid, et al. Software-defined farmemory in warehouse-scale computers. In Proceedings of theTwenty-Fourth International Conference on Architectural Support for65Programming Languages and Operating Systems, pages 317â330, 2019.â pages 1, 13, 26, 56[68] M. Lanza, A. Sebastian, W. D. Lu, M. Le Gallo, M.-F. Chang,D. Akinwande, F. M. Puglisi, H. N. Alshareef, M. Liu, and J. B. Roldan.Memristive technologies for data storage, computation, encryption, andradio-frequency communication. Science, 376(6597):eabj9979, 2022. âpage 1[69] N. Lebeck, A. Krishnamurthy, H. M. Levy, and I. Zhang. End the senselesskilling: Improving memory management for mobile operating systems. In2020 USENIX Annual Technical Conference (USENIX ATC 20), pages873â887, 2020. â pages 1, 24, 26[70] D. Lee, I. Choi, C. Lee, S. Lee, and J. Kim. P2cache: Anapplication-directed page cache for improving performance ofdata-intensive applications. In Proceedings of the 15th ACM Workshop onHot Topics in Storage and File Systems, pages 31â36, 2023. â page 57[71] S. Lee, S. Ponnapalli, S. Singhal, M. K. Aguilera, K. Keeton, andV. Chidambaram. Dinomo: an elastic, scalable, high-performancekey-value store for disaggregated persistent memory. Proceedings of theVLDB Endowment, 15(13):4023â4037, 2022. â pages 3, 10, 25[72] S.-H. Lee. Technology scaling challenges and opportunities of memorydevices. In 2016 IEEE International Electron Devices Meeting (IEDM),pages 1â1. IEEE, 2016. â pages 1, 23[73] S.-s. Lee, Y. Yu, Y. Tang, A. Khandelwal, L. Zhong, and A. Bhattacharjee.Mind: In-network memory management for disaggregated data centers. InProceedings of the ACM SIGOPS 28th Symposium on Operating SystemsPrinciples, pages 488â504, 2021. â pages 10, 24[74] V. Leis, A. Alhomssi, T. Ziegler, Y. Loeck, and C. Dietrich.Virtual-memory assisted buffer management. Proceedings of the ACM onManagement of Data, 1(1):1â25, 2023. â pages 37, 54[75] S. T. Leutenegger and D. Dias. A modeling study of the tpc-c benchmark.ACM Sigmod Record, 22(2):22â31, 1993. â page 16[76] P. Levis, K. Lin, and A. Tai. A case against cxl memory pooling. InProceedings of the 22nd ACM Workshop on Hot Topics in Networks, pages18â24, 2023. â pages 10, 2666[77] H. Li, D. S. Berger, S. Novakovic, L. Hsu, D. Ernst, P. Zardoshti, M. Shah,S. Rajadnya, S. Lee, I. Agarwal, et al. Pond: Cxl-based memory poolingsystems for cloud platforms. In Proc. Int. Conf. Archit. Support Program.Lang. Oper. Syst, 2023. â pages 1, 23, 26[78] J. Liedtke. On micro-kernel construction. ACM SIGOPS OperatingSystems Review, 29(5):237â250, 1995. â pages 11, 27[79] K. Lim, J. Chang, T. Mudge, P. Ranganathan, S. K. Reinhardt, and T. F.Wenisch. Disaggregated memory for expansion and sharing in bladeservers. ACM SIGARCH computer architecture news, 37(3):267â278,2009. â pages 1, 9, 23[80] K. Lim, Y. Turner, J. R. Santos, A. AuYoung, J. Chang, P. Ranganathan,and T. F. Wenisch. System-level implications of disaggregated memory. InIEEE International Symposium on High-Performance Comp Architecture,pages 1â12. IEEE, 2012. â page 9[81] J. Lin and A. Kolcz. Large-scale machine learning at twitter. InProceedings of the 2012 ACM SIGMOD International Conference onManagement of Data, pages 793â804, 2012. â pages 1, 23[82] J. Liu, A. Rebello, Y. Dai, C. Ye, S. Kannan, A. C. Arpaci-Dusseau, andR. H. Arpaci-Dusseau. Scale and performance in a filesystemsemi-microkernel. In Proceedings of the ACM SIGOPS 28th Symposium onOperating Systems Principles, pages 819â835, 2021. â pages 11, 27, 56[83] M. Marty, M. de Kruijf, J. Adriaens, C. Alfeld, S. Bauer, C. Contavalli,M. Dalton, N. Dukkipati, W. C. Evans, S. Gribble, et al. Snap: Amicrokernel approach to host networking. In Proceedings of the 27th ACMSymposium on Operating Systems Principles, pages 399â413, 2019. âpages 11, 27, 56[84] H. A. Maruf, H. Wang, A. Dhanotia, J. Weiner, N. Agarwal,P. Bhattacharya, C. Petersen, M. Chowdhury, S. Kanaujia, and P. Chauhan.Tpp: Transparent page placement for cxl-enabled tiered-memory. InProceedings of the 28th ACM International Conference on ArchitecturalSupport for Programming Languages and Operating Systems, Volume 3,pages 742â755, 2023. â pages 10, 25, 40, 54[85] O. Mutlu, S. Ghose, J. Go´mez-Luna, and R. Ausavarungnirun. Processingdata where it makes sense: Enabling in-memory computation.Microprocessors and Microsystems, 67:28â41, 2019. â pages 1, 2367[86] J. Nider, C. Mustard, A. Zoltan, J. Ramsden, L. Liu, J. Grossbard,M. Dashti, R. Jodin, A. Ghiti, J. Chauzi, et al. A case study of{Processing-in-Memory} in {off-the-Shelf} systems. In 2021 USENIXAnnual Technical Conference (USENIX ATC 21), pages 117â130, 2021. âpages 1, 13, 21, 23[87] A. Ousterhout, J. Fried, J. Behrens, A. Belay, and H. Balakrishnan.Shenango: Achieving high {CPU} efficiency for latency-sensitivedatacenter workloads. In 16th USENIX Symposium on Networked SystemsDesign and Implementation (NSDI 19), pages 361â378, 2019. â pages11, 27, 56[88] S. Patel, S. Agrawal, A. Fedorova, and M. Seltzer. Cheri-picking:Leveraging capability hardware for prefetching. In Proceedings of the 12thWorkshop on Programming Languages and Operating Systems, pages58â65, 2023. â page 1[89] G. Pekhimenko, V. Seshadri, Y. Kim, H. Xin, O. Mutlu, P. B. Gibbons,M. A. Kozuch, and T. C. Mowry. Linearly compressed pages: Alow-complexity, low-latency main memory compression framework. InProceedings of the 46th Annual IEEE/ACM International Symposium onMicroarchitecture, pages 172â184, 2013. â page 22[90] I. Peng, M. McFadden, E. Green, K. Iwabuchi, K. Wu, D. Li, R. Pearce,and M. Gokhale. Umap: Enabling application-driven optimizations forpage management. In 2019 IEEE/ACM Workshop on Memory Centric HighPerformance Computing (MCHPC), pages 71â78. IEEE, 2019. â pages3, 10, 25, 46, 56[91] S. Rajbhandari, O. Ruwase, J. Rasley, S. Smith, and Y. He. Zero-infinity:Breaking the gpu memory wall for extreme scale deep learning. InProceedings of the International Conference for High PerformanceComputing, Networking, Storage and Analysis, pages 1â14, 2021. â pages1, 23[92] R. Rashid, A. Tevanian, M. Young, D. Golub, R. Baron, D. Black,W. Bolosky, and J. Chew. Machine-independent virtual memorymanagement for paged uniprocessor and multiprocessor architectures. InProceedings of the second international conference on Architectual supportfor programming languages and operating systems, pages 31â39, 1987. âpages 11, 2768[93] R. F. Rashid. From rig to accent to mach: The evolution of a networkoperating system. In Proceedings of 1986 ACM Fall joint computerconference, pages 1128â1137, 1986. â page 11[94] A. Raybuck, T. Stamler, W. Zhang, M. Erez, and S. Peter. Hemem:Scalable tiered memory management for big data applications and realnvm. In Proceedings of the ACM SIGOPS 28th Symposium on OperatingSystems Principles, pages 392â407, 2021. â pages1, 3, 10, 23, 24, 25, 31, 33, 54, 56[95] Z. Ruan, M. Schwarzkopf, M. K. Aguilera, and A. Belay.{AIFM}:{High-Performance},{Application-Integrated} far memory. In14th USENIX Symposium on Operating Systems Design andImplementation (OSDI 20), pages 315â332, 2020. â pages 3, 9, 10, 25, 56[96] rwestMSFT. Memory Management Architecture Guide - SQL Server âlearn.microsoft.com. https://learn.microsoft.com/en-us/sql/relational-databases/memory-management-architecture-guide. [Accessed09-01-2024]. â page 25[97] S. Sakr, A. Bonifati, H. Voigt, A. Iosup, K. Ammar, R. Angles, W. Aref,M. Arenas, M. Besta, P. A. Boncz, et al. The future is big graphs: acommunity view on graph processing systems. Communications of theACM, 64(9):62â71, 2021. â pages 1, 23[98] Y. Shan, Y. Huang, Y. Chen, and Y. Zhang. {LegoOS}: A disseminated,distributed {OS} for hardware resource disaggregation. In 13th USENIXSymposium on Operating Systems Design and Implementation (OSDI 18),pages 69â87, 2018. â pages 10, 24[99] J. Shen, P. Zuo, X. Luo, T. Yang, Y. Su, Y. Zhou, and M. R. Lyu.{FUSEE}: A fully {Memory-Disaggregated}{Key-Value} store. In 21stUSENIX Conference on File and Storage Technologies (FAST 23), pages81â98, 2023. â pages 3, 10, 25[100] M. Stonebraker. Operating system support for database management.Communications of the ACM, 24(7):412â418, 1981. â page 25[101] M. Stonebraker and A. Weisberg. The voltdb main memory dbms. IEEEData Eng. Bull., 36(2):21â27, 2013. â pages 1, 16, 23[102] Y. Sun, Y. Yuan, Z. Yu, R. Kuper, I. Jeong, R. Wang, and N. S. Kim.Demystifying cxl memory with genuine cxl-ready systems and devices.arXiv preprint arXiv:2303.15375, 2023. â page 2669[103] B. Tabatabai, M. Mansi, and M. M. Swift. Fbmm: Using the vfs forextensibility in kernel memory management. In Proceedings of the 19thWorkshop on Hot Topics in Operating Systems, pages 181â187, 2023. âpage 57[104] A. S. Tanenbaum and A. S. Woodhull. Operating systems: design andimplementation, volume 68. Prentice Hall Englewood Cliffs, 1997. âpages 1, 23[105] T. N. Theis and H.-S. P. Wong. The end of mooreâs law: A new beginningfor information technology. Computing in science & engineering, 19(2):41â50, 2017. â pages 1, 23[106] S.-Y. Tsai and Y. Zhang. Lite kernel rdma support for datacenterapplications. In Proceedings of the 26th Symposium on Operating SystemsPrinciples, pages 306â324, 2017. â pages 3, 9, 10, 25[107] B. Walker. Storage Performance Development Kit â spdk.io.https://spdk.io. [Accessed 09-01-2024]. â page 11[108] C. Wang, H. Ma, S. Liu, Y. Li, Z. Ruan, K. Nguyen, M. D. Bond,R. Netravali, M. Kim, and G. H. Xu. Semeru: A {Memory-Disaggregated}managed runtime. In 14th USENIX Symposium on Operating SystemsDesign and Implementation (OSDI 20), pages 261â280, 2020. â pages2, 3, 10, 24, 25[109] C. Wang, Y. Qiao, H. Ma, S. Liu, W. Chen, R. Netravali, M. Kim, andG. H. Xu. Canvas: Isolated and adaptive swapping for{Multi-Applications} on remote memory. In 20th USENIX Symposium onNetworked Systems Design and Implementation (NSDI 23), pages 161â179,2023. â pages 2, 24, 33, 56[110] J. Weiner, N. Agarwal, D. Schatzberg, L. Yang, H. Wang, B. Sanouillet,B. Sharma, T. Heo, M. Jain, C. Tang, et al. Tmo: transparent memoryoffloading in datacenters. In Proceedings of the 27th ACM InternationalConference on Architectural Support for Programming Languages andOperating Systems, pages 609â621, 2022. â pages1, 2, 9, 13, 22, 23, 24, 26, 56[111] L. Xu, M. Li, L. Zhang, A. R. Butt, Y. Wang, and Z. Z. Hu. Memtune:Dynamic memory management for in-memory data analytic platforms. In2016 IEEE international parallel and distributed processing symposium(IPDPS), pages 383â392. IEEE, 2016. â pages 1, 2470[112] Z. Yan, D. Lustig, D. Nellans, and A. Bhattacharjee. Nimble pagemanagement for tiered memory systems. In Proceedings of theTwenty-Fourth International Conference on Architectural Support forProgramming Languages and Operating Systems, pages 331â345, 2019.â pages 1, 10, 23, 24[113] T. Yang, E. D. Berger, S. F. Kaplan, and J. E. B. Moss. Cramm: Virtualmemory support for garbage-collected applications. In Proceedings of the7th symposium on Operating systems design and implementation, pages103â116, 2006. â pages 1, 24[114] W. Yoon, J. Ok, J. Oh, S. Moon, and Y. Kwon. Dilos: Do not tradecompatibility for performance in memory disaggregation. In Proceedingsof the Eighteenth European Conference on Computer Systems, pages266â282, 2023. â pages 3, 10, 24, 26[115] K. Zhong, W. Cui, X. Chen, Q. Li, Z. Yang, Y. Lu, X. Yan, S. Luo,Q. Yuan, and K. Huang. Revisiting swapping in user-space withlightweight threading. IEEE Transactions on Computer-Aided Design ofIntegrated Circuits and Systems, 2023. â pages 10, 5671
Thesis/Dissertation
eng
Electrical and Computer Engineering
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Fedorova, Alexandra
Flexible application-directed virtual memory management for data-intensive applications and heterogeneous hardware
Text