14 KiB
- Plan
- Current experiments:
- Experiment cancelled:
- Link to the Previous PhD Plan
- Summary of the Previous Plan
- Current Research Plan
- Appendix
- (Experiment 3)Allocator evaluation based on stripping instruction calls for larger allocators
Plan
This document outlines the proposed PhD research plan for the forthcoming academic year, building upon the outcomes and insights gained during the preceding year.
Current experiments:
- (Experiment 1)FAT allocator with huge pages (EuroSys26 paper draft)
- (Experiment 2)FAT allocator to bypass TLB. (Proposal of ongoing expirement)
- (Experiment 3)Allocator evaluation based on stripping instruction calls from larger allocators. (Appendix)
Experiment cancelled:
- Uni-Kernel Development (Reason): Work scaled down to fit within the allocated within PhD timeframe and instead introduced an extension of the FAT allocator as the third experiment.
Link to the Previous PhD Plan
Summary of the Previous Plan
Phase 1: FAT-Pointer Mechanism (July–September 2024)
1st to 15th July 2024
- Investigated causes of L1 TLB misses associated with contiguous memory allocation.
- Executed performance benchmarking using COZ\cite{coz} on selected C programs.
- Ported the kernel module to support SnMalloc, the default allocator in CheriBSD.
15th to 30th July 2024
- Conducted benchmarking using the SPEC and XSBench suites.
- Performed comparative analysis with both baseline and modified SnMalloc implementations.
August 2024
- Initiated drafting of a paper for submission to EuroSys, focusing on the FAT-Pointer memory allocator (Current: On review stage).
September 2024
- Compiled and structured thesis chapter related to the FAT-Pointer architecture.
- Finalised and submitted the EuroSys paper.
Phase 2: RISC-V Integration (October 2024 – May 2025)
October to December 2024
- Modified the Bluespec implementation to enable TLB bypass in the memory access pipeline (Current: On progress).
- Configured the experimental platform and evaluation toolchain (Current: On progress).
January to February 2025
- Undertook experimental evaluation of the FAT-Pointer system on RISC-V (Toooba) (Current: Todo).
- Commenced drafting of a technical paper for ISMM based on RISC-V integration results (Current: Todo).
March to May 2025
- Addressed outstanding tasks and technical backlog.
- Continued development of the corresponding thesis chapter.
Phase 3: Uni-Kernel Deployment (May 2025 – September 2026)
May to December 2025
- Ported the memory allocator to a CHERI-enabled Uni-Kernel environment (Current: Cancelled)
- Designed and implemented a unified memory allocator to support both kernel and user-level allocations (Current: Cancelled)
- Initiated drafting of a manuscript targeted at OSDI (Current: Cancelled)
January to September 2026
- Finalised documentation and submission of the PhD thesis (Current: New plan to still keep these dates unchanged)
- Submitted third research paper based on extended evaluation (Current: Replaced with "Allocator evaluation based on stripping instruction calls from larger allocators")
Current Research Plan
This section outlines a comprehensive timeline of research activities and academic milestones to be undertaken between June 2025 and September 2026 as part of the PhD to be focused on the CHERI Toooba architecture\cite{Toooba}. It includes the refactoring of BlueSpec\cite{bluespec} SystemVerilog\cite{bsv} modules and the development of a bare-metal C benchmark suite. The work involves in-depth debugging of the Toooba memory subsystem, the design and evaluation of in-depth analyses of the FAT allocator and performance analysis at the instruction level. Alongside these technical efforts, the timeline reflects the structured drafting of academic publications and the ongoing development of the PhD thesis.
June to July 2025
- Refactor BlueSpec SystemVerilog (BSV)\cite{bsv} modules within the CHERI Toooba architecture.
- Set up a bare-metal C benchmark suite for execution on the Bluespec simulation platform.
- Incorporate supervisory team feedback into revisions of the EuroSys paper.
- Undertake formal progression review requirements.
- Submit EuroSys paper to the CHERI research team at the University of Glasgow for preliminary feedback.
July to August 2025
- Engage in extensive debugging of the Toooba memory pipeline, specifically targeting the TLB bypass path.
- Finalise and validate the C benchmark suite for the Toooba evaluation.
- Begin technical documentation of the Toooba workflow, to support a 2nd publication.
- Conclude revisions to the EuroSys paper by the end of July.
August to September 2025
- Continue debugging efforts within the Toooba memory subsystem.
- Draft the abstract, introduction, and methodology sections of the second research paper.
- Aim to generate preliminary experimental results for inclusion in the evaluation for the 2nd experiment.
September to October 2025
- Publish the EuroSys paper detailing the FAT-Pointer allocator.
- Commence benchmarking of the Toooba design.
- Simultaneously draft the evaluation and analysis sections of the 2nd paper.
October to November 2025
- Initiate 3rd experimental phase, aimed at deeper evaluation of prior experiments.
- Modify memory allocators (TcMalloc and Mesh) to remove reliance on system `mmap` call.
November to December 2025
- Finalise 2nd paper for peer review.
- Strip away huge-page-specific optimisations from JeMalloc, TcMalloc, and Mesh.
- Analyse instruction-level reductions and performance implications.
- Commence drafting of the 3rd research paper, building on contributions from the EuroSys paper.
December 2025 to January 2026
- Conduct evaluation and profiling for the 3rd paper.
- Commence thesis chapter write-up for Experiments 1 and 2.
January to September 2026
- Continue thesis development and refinement across all experimental chapters.
- Finalise and submitted 3rd paper for peer review.
- Prepare complete PhD dissertation for submission.
\bibliographystyle{IEEEtran} \bibliography{FuturePlan.bib}
Appendix
(Experiment 3)Allocator evaluation based on stripping instruction calls for larger allocators
Box 1 (Transparent huge pages)
The diagram above mentions 3 particular implementations. The first box which is the standard THP(Transparent huge pages) utilised by modern allocators. THP initially emphasises on doing smalled allocations and as the number of allocations grows uses a technique which groups all smaller allocations together and when done converts them into a large page of size 4mb in allocators such as jemalloc.
The diagram fig:MEMALLOC highlights three specific implementations, the first of which is the standard Transparent Huge Pages (THP) mechanism employed by modern memory allocators. THP initially focuses on handling smaller memory allocations. As the volume of allocations increases, it employs a strategy that consolidates these smaller allocations into contiguous memory regions. Once aggregated, these regions are subsequently converted into larger memory pages, typically of size 4MB, as seen in allocators like jemalloc. This approach optimises memory management by reducing fragmentation and improving performance through the use of larger page sizes.
This approach does incur addtional operations such as grouping smaller allocations chaging the TLB entries (Adding more oppurtunity for TLB misses). Only once the huge page is created the TLB misses are reduced.
This approach, however, introduces additional overhead, including the operations required to consolidate smaller allocations and modify Translation Lookaside Buffer (TLB) entries. These modifications can initially increase the likelihood of TLB misses, as the process of grouping and reorganizing memory allocations temporarily disrupts the efficiency of TLB utilization. It is only after the successful creation of the huge page that the benefits materialize, leading to a reduction in TLB misses due to the improved alignment of memory access patterns with the larger page size.
Box 2 (Our current implementation)
Box 2 which refers to our current implementation always pre-allocates huge pages and untilises CHERI bounds to track each allocation inside the huge page. Allowing a single entry with the combination of bounds to provide block based behavoir in physically contigous memory while ensuring a pointer can only access a regoin within it's defined bounds.
Box 2 outlines the current implementation, which involves the pre-allocation of huge pages and leverages CHERI (Capability Hardware Enhanced RISC Instructions) bounds to meticulously track each allocation within these pages. This approach enables a single TLB entry, combined with the precise bounds defined by CHERI capabilities, to facilitate block-based memory management within physically contiguous regions. By enforcing strict bounds on pointers, the system ensures that each pointer can only access memory within its explicitly defined region.
Another aspect to note is that the bounds can be of a dynamic size when defined. This is in contrast to defining multiple page entries which need to be fixed sizes which means they always incur multiple entries. In the current approach when the huge page size is hit a new one is created. The limitaton of this is appraoch being we are limited to the huge page set by the processor implementation (In our case the CHERI ARM v8.1).
Another critical aspect of this implementation is the ability to define bounds of dynamic sizes, which stands in contrast to traditional approaches that rely on fixed-size page entries. Fixed-size entries inherently require multiple TLB entries, regardless of the actual memory usage, leading to inefficiencies. In the current approach, when the allocated memory within a huge page reaches its capacity, a new huge page is allocated. However, a notable limitation of this method is its dependence on the maximum huge page size supported by the underlying processor architecture. In this case, the system is constrained by the huge page size defined by the CHERI-enhanced ARM v8.1\cite{noauthor_arm_nodate} architecture. While this approach offers flexibility in memory allocation and reduces the need for multiple TLB entries, it is ultimately bounded by the hardware's architectural specifications.
Box 3 (RISC-V implementation)
The 3rd box specifies an alternate appraoch by not using huge pages and required memory is not required to be physically contigous. In this approach the pointer stores all the metadata to the translation from virtual to physical addresses.
The third approach, as outlined in Box 3, deviates from the use of huge pages and does not require memory to be physically contiguous. In this model, each pointer is designed to store comprehensive metadata at the pointer necessary for the translation from virtual to physical addresses. This metadata enables the system to manage memory allocations without the constraints of physical contiguity, thereby offering greater flexibility in memory utilization. By embedding translation information directly within the pointers, this approach eliminates the need for large, contiguous memory regions and allows for more granular and dynamic memory management.
Building up from the work of Box 2 and Box 3 (Side effects we can strip away)
Box 2 and 3 from a high overview there is only minor difference which can be noted which is 1 uses huge pages and other does not. Both approaches can strip down the number intructions needed in modern allocators (Stripping away the need transitioning from smaller to larger pages). This document is yet to give an exact breakdown.
From a high-level perspective, the primary distinction between Box 2 and Box 3 lies in the use of huge pages in the former and their absence in the latter. Both approaches share the common advantage of reducing the number of instructions required in modern memory allocators by eliminating the need for transitioning between smaller and larger pages. This simplification streamlines memory management processes. However, this document has not yet provided a detailed breakdown or quantitative analysis of the specific performance implications or trade-offs.
As seen to the right of the diagram is a sample snippet of TC malloc from the paper (Beyond malloc efficiency to fleet allocators). This whole span function would not be required in our approach. The other benefit being easier get the approach by getting mmap embedded inside the allocator.
As illustrated to the right of the diagram, a sample snippet of TC malloc from the paper "Beyond malloc Efficiency to Fleet Efficiency"\cite{FleetAllocator} is provided. In the proposed approach, the entire span function, which is essential in TC malloc, would become unnecessary. Additionally, the approach offers the advantage of simplifying memory management by integrating mmap directly within the allocator. This integration eliminates the need for separate mechanisms to handle memory mapping.
Evaluation:
- Amount of instructions that can be stripped away from the page aware memory allocator.
- Comparing memory allocator with wall clock run time with the modified mmap and without the modified mmap.
- CHERI purecap does incur additional instruction such as bound checks. Does this approach as a whole reduce the number of instructions as whole (Comparing CHERIpurecap instructions with memory allocator emitted vs regular ARMv8 clang program with the same allocator).
- The number of instructions that can be eliminated from a page-aware memory allocator by adopting the proposed approach.
- A comparative analysis of the memory allocator's performance using wall-clock runtime measurements, both with and without the modified mmap implementation.
- While CHERI Purecap introduces additional instructions, such as bounds checks, the overall approach aims to determine whether it reduces the total number of instructions when compared to a traditional ARMv8 Clang program using the same allocator. This involves evaluating the trade-offs between the overhead of CHERI-specific instructions and the potential reductions in allocator-emitted instructions.