[libc] add basic arena allocator

llvm · RossComputerGuy · Dec 26, 2024 · Dec 27, 2024 · Jan 7, 2025 · 63c5bf84650bbd4808f05418ba69c14b0a945b8a
commit 63c5bf84650bbd4808f05418ba69c14b0a945b8a
diff --git a/.github/workflows/libc-fullbuild-tests.yml b/.github/workflows/libc-fullbuild-tests.yml
@@ -54,7 +54,7 @@ jobs:
        echo "build-output-dir=${{ github.workspace }}/build" >> "$GITHUB_OUTPUT"
        echo "build-install-dir=${{ github.workspace }}/install" >> "$GITHUB_OUTPUT"

-    # Configure libc fullbuild with scudo.
+    # Configure libc fullbuild.
    # Use MinSizeRel to reduce the size of the build.
    - name: Configure CMake
      run: >
@@ -65,12 +65,8 @@ jobs:
        -DCMAKE_C_COMPILER_LAUNCHER=sccache
        -DCMAKE_CXX_COMPILER_LAUNCHER=sccache
        -DCMAKE_INSTALL_PREFIX=${{ steps.strings.outputs.build-install-dir }}
-        -DLLVM_ENABLE_RUNTIMES="libc;compiler-rt"
+        -DLLVM_ENABLE_RUNTIMES="libc"
        -DLLVM_LIBC_FULL_BUILD=ON
-        -DLLVM_LIBC_INCLUDE_SCUDO=ON
-        -DCOMPILER_RT_BUILD_SCUDO_STANDALONE_WITH_LLVM_LIBC=ON
-        -DCOMPILER_RT_BUILD_GWP_ASAN=OFF
-        -DCOMPILER_RT_SCUDO_STANDALONE_BUILD_SHARED=OFF
        -G Ninja
        -S ${{ github.workspace }}/runtimes


diff --git a/.github/workflows/libc-overlay-tests.yml b/.github/workflows/libc-overlay-tests.yml
@@ -87,6 +87,7 @@ jobs:
        -DCMAKE_POLICY_DEFAULT_CMP0141=NEW
        -DCMAKE_MSVC_DEBUG_INFORMATION_FORMAT=Embedded
        -DLLVM_ENABLE_RUNTIMES=libc
+        -DLIBC_CONF_ALLOC_TYPE=LIBC_ALLOC_TYPE_EXTERN
        -G Ninja
        -S ${{ github.workspace }}/runtimes


diff --git a/libc/CMakeLists.txt b/libc/CMakeLists.txt
@@ -384,6 +384,12 @@ else()
  set(libc_opt_high_flag "-O3")
 endif()

+if(${LIBC_CONF_ALLOC_TYPE} MATCHES "LIBC_ALLOC_TYPE_SCUDO")
+  set(LLVM_LIBC_INCLUDE_SCUDO ON)
+elseif(LLVM_LIBC_INCLUDE_SCUDO)
+  message(FATAL_ERROR "Cannot include scudo and use a different allocator.")
+endif()
+
 add_subdirectory(include)
 add_subdirectory(config)
 add_subdirectory(hdr)

diff --git a/libc/config/config.json b/libc/config/config.json
@@ -115,6 +115,10 @@
    "LIBC_ADD_NULL_CHECKS": {
      "value": true,
      "doc": "Add nullptr checks in the library's implementations to some functions for which passing nullptr is undefined behavior."
+    },
+    "LIBC_CONF_ALLOC_TYPE": {
+      "value": "LIBC_ALLOC_TYPE_ARENA",
+      "doc": "The implementation used for allocations, acceptable values are LIBC_ALLOC_TYPE_EXTERN, LIBC_ALLOC_TYPE_SCUDO, LIBC_ALLOC_TYPE_ARENA."
    }
  },
  "unistd": {

diff --git a/libc/config/linux/x86_64/entrypoints.txt b/libc/config/linux/x86_64/entrypoints.txt
@@ -322,6 +322,7 @@ set(TARGET_LIBC_ENTRYPOINTS
    libc.src.unistd.ftruncate
    libc.src.unistd.getcwd
    libc.src.unistd.geteuid
+    libc.src.unistd.getpagesize
    libc.src.unistd.getpid
    libc.src.unistd.getppid
    libc.src.unistd.gettid

diff --git a/libc/docs/configure.rst b/libc/docs/configure.rst
@@ -32,6 +32,7 @@ to learn about the defaults for your platform and target.
    - ``LIBC_CONF_ERRNO_MODE``: The implementation used for errno, acceptable values are LIBC_ERRNO_MODE_DEFAULT, LIBC_ERRNO_MODE_UNDEFINED, LIBC_ERRNO_MODE_THREAD_LOCAL, LIBC_ERRNO_MODE_SHARED, LIBC_ERRNO_MODE_EXTERNAL, and LIBC_ERRNO_MODE_SYSTEM.
 * **"general" options**
    - ``LIBC_ADD_NULL_CHECKS``: Add nullptr checks in the library's implementations to some functions for which passing nullptr is undefined behavior.
+    - ``LIBC_CONF_ALLOC_TYPE``: The implementation used for allocations, acceptable values are LIBC_ALLOC_TYPE_EXTERN, LIBC_ALLOC_TYPE_SCUDO, LIBC_ALLOC_TYPE_ARENA.
 * **"math" options**
    - ``LIBC_CONF_FREXP_INF_NAN_EXPONENT``: The value written back to the second parameter when calling frexp/frexpf/frexpl` with `+/-Inf`/`NaN` is unspecified.  Configue an explicit exp value for Inf/NaN inputs.
    - ``LIBC_CONF_MATH_OPTIMIZATIONS``: Configures optimizations for math functions. Values accepted are LIBC_MATH_SKIP_ACCURATE_PASS, LIBC_MATH_SMALL_TABLES, LIBC_MATH_NO_ERRNO, LIBC_MATH_NO_EXCEPT, and LIBC_MATH_FAST.

diff --git a/libc/src/__support/CMakeLists.txt b/libc/src/__support/CMakeLists.txt
@@ -370,3 +370,5 @@ add_subdirectory(HashTable)
 add_subdirectory(fixed_point)

 add_subdirectory(time)
+
+add_subdirectory(alloc)
diff --git a/libc/src/__support/alloc/CMakeLists.txt b/libc/src/__support/alloc/CMakeLists.txt
@@ -0,0 +1,54 @@
+add_object_library(
+  base
+  SRCS
+    base.cpp
+  HDRS
+    base.h
+  DEPENDS
+    libc.hdr.types.size_t
+    libc.src.__support.macros.config
+)
+
+if(EXISTS ${CMAKE_CURRENT_SOURCE_DIR}/${LIBC_TARGET_OS})
+  add_subdirectory(${LIBC_TARGET_OS})
+endif()
+
+if(TARGET libc.src.__support.alloc.${LIBC_TARGET_OS}.page)
+  add_object_library(
+    page
+    ALIAS
+    DEPENDS
+      .${LIBC_TARGET_OS}.page
+  )
+
+  add_object_library(
+    arena
+    SRCS
+      arena.cpp
+    HDRS
+      arena.h
+    COMPILE_OPTIONS
+      -DLIBC_PAGE_SIZE=${LIBC_CONF_PAGE_SIZE}
+    DEPENDS
+      .base
+      .page
+      libc.src.string.memmove
+      libc.src.unistd.getpagesize
+  )
+endif()
+
+if(NOT ${LIBC_CONF_ALLOC_TYPE} MATCHES "LIBC_ALLOC_TYPE_SCUDO" AND NOT ${LIBC_CONF_ALLOC_TYPE} MATCHES "LIBC_ALLOC_TYPE_EXTERN")
+  string(TOLOWER ${LIBC_CONF_ALLOC_TYPE} LIBC_CONF_ALLOC_TYPE_NAME)
+  string(REPLACE "libc_alloc_type_" "" LIBC_CONF_ALLOC_TYPE_NAME "${LIBC_CONF_ALLOC_TYPE_NAME}")
+  add_object_library(
+    alloc
+    SRCS
+      alloc.cpp
+    HDRS
+      alloc.h
+    COMPILE_OPTIONS
+      -DLIBC_CONF_ALLOC_TYPE=${LIBC_CONF_ALLOC_TYPE_NAME}
+    DEPENDS
+      .${LIBC_CONF_ALLOC_TYPE_NAME}
+  )
+endif()
diff --git a/libc/src/__support/alloc/alloc.cpp b/libc/src/__support/alloc/alloc.cpp
@@ -0,0 +1,13 @@
+#include <src/__support/alloc/alloc.h>
+#include <src/__support/alloc/arena.h>
+
+namespace LIBC_NAMESPACE_DECL {
+
+#define CONCAT(a, b) a##b
+#define EXPAND_AND_CONCAT(a, b) CONCAT(a, b)
+
+#define ALLOCATOR EXPAND_AND_CONCAT(LIBC_CONF_ALLOC_TYPE, _allocator)
+
+BaseAllocator *allocator = reinterpret_cast<BaseAllocator *>(&ALLOCATOR);
+
+} // namespace LIBC_NAMESPACE_DECL
diff --git a/libc/src/__support/alloc/alloc.h b/libc/src/__support/alloc/alloc.h
@@ -0,0 +1,22 @@
+//===-- libc-wide allocator -------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC___SUPPORT_ALLOC_ALLOC_H
+#define LLVM_LIBC_SRC___SUPPORT_ALLOC_ALLOC_H
+
+#include "src/__support/alloc/base.h"
+#include "src/__support/macros/config.h"
+
+namespace LIBC_NAMESPACE_DECL {
+
+// The primary allocator to use
+extern BaseAllocator *allocator;
+
+} // namespace LIBC_NAMESPACE_DECL
+
+#endif
diff --git a/libc/src/__support/alloc/arena.cpp b/libc/src/__support/alloc/arena.cpp
@@ -0,0 +1,71 @@
+#include "src/__support/alloc/arena.h"
+#include "src/__support/alloc/page.h"
+#include "src/__support/common.h"
+#include "src/__support/macros/config.h"
+#include "src/__support/macros/page_size.h"
+#include "src/__support/memory_size.h"
+#include "src/string/memmove.h"
+#include "src/unistd/getpagesize.h"
+
+namespace LIBC_NAMESPACE_DECL {
+
+void *arena_allocate(BaseAllocator *base, size_t alignment, size_t size) {
+  ArenaAllocator *self = reinterpret_cast<ArenaAllocator *>(base);
+
+  if (self->buffer == nullptr) {
+    self->buffer = reinterpret_cast<uint8_t *>(page_allocate(1));
+    self->buffer_size = self->get_page_size();
+  }
+
+  uintptr_t curr_ptr = (uintptr_t)self->buffer + (uintptr_t)self->curr_offset;
+  uintptr_t offset = internal::align_forward<uintptr_t>(curr_ptr, alignment);
+  offset -= (uintptr_t)self->buffer;
+
+  if (offset + size > self->buffer_size) {
+    self->buffer = reinterpret_cast<uint8_t *>(
+        page_expand(self->buffer, self->buffer_size / self->get_page_size()));
+    self->buffer_size += self->get_page_size();
+  }
+
+  if (offset + size <= self->buffer_size) {
+    void *ptr = &self->buffer[offset];
+    self->prev_offset = offset;
+    self->curr_offset = offset + size;
+    return ptr;
+  }
+  return nullptr;
+}
+
+void *arena_expand(BaseAllocator *base, void *ptr, size_t alignment,
+                   size_t size) {
+  ArenaAllocator *self = reinterpret_cast<ArenaAllocator *>(base);
+
+  if (self->buffer + self->prev_offset == ptr) {
+    self->curr_offset = self->prev_offset + size;
+    return ptr;
+  } else {
+    void *new_mem = arena_allocate(base, alignment, size);
+    memmove(new_mem, ptr, size);
+    return new_mem;
+  }
+  return nullptr;
+}
+
+bool arena_free(BaseAllocator *base, void *ptr) {
+  (void)base;
+  (void)ptr;
+  return true;
+}
+
+size_t ArenaAllocator::get_page_size() {
+  if (page_size == LIBC_PAGE_SIZE_SYSTEM) {
+    page_size = getpagesize();
+  }
+  return page_size;
+}
+
+static ArenaAllocator default_arena_allocator(LIBC_PAGE_SIZE,
+                                              2 * sizeof(void *));
+BaseAllocator *arena_allocator = &default_arena_allocator;
+
+} // namespace LIBC_NAMESPACE_DECL
diff --git a/libc/src/__support/alloc/arena.h b/libc/src/__support/alloc/arena.h
@@ -0,0 +1,47 @@
+//===-- An arena allocator using pages. -------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC___SUPPORT_ALLOC_ARENA_H
+#define LLVM_LIBC_SRC___SUPPORT_ALLOC_ARENA_H
+
+#include "hdr/types/size_t.h"
+#include "src/__support/alloc/base.h"
+#include <stdint.h>
+
+namespace LIBC_NAMESPACE_DECL {
+
+void *arena_allocate(BaseAllocator *base, size_t alignment, size_t size);
+void *arena_expand(BaseAllocator *base, void *ptr, size_t alignment,
+                   size_t size);
+bool arena_free(BaseAllocator *base, void *ptr);
+
+class ArenaAllocator : public BaseAllocator {
+public:
+  uint8_t *buffer;
+  size_t buffer_size;
+  size_t prev_offset;
+  size_t curr_offset;
+
+private:
+  size_t page_size;
+
+public:
+  constexpr ArenaAllocator(size_t page_size, size_t default_alignment)
+      : BaseAllocator(arena_allocate, arena_expand, arena_free,
+                      default_alignment),
+        buffer(nullptr), buffer_size(0), prev_offset(0), curr_offset(0),
+        page_size(page_size) {}
+
+  size_t get_page_size();
+};
+
+extern BaseAllocator *arena_allocator;
+
+} // namespace LIBC_NAMESPACE_DECL
+
+#endif
diff --git a/libc/src/__support/alloc/baremetal/CMakeLists.txt b/libc/src/__support/alloc/baremetal/CMakeLists.txt
@@ -0,0 +1,13 @@
+add_object_library(
+  page
+  SRCS
+    page.cpp
+  HDRS
+    ../page.h
+  DEPENDS
+    libc.src.__support.alloc.base
+    libc.src.sys.mman.mmap
+    libc.src.sys.mman.mremap
+    libc.src.sys.mman.munmap
+    libc.src.unistd.getpagesize
+)
diff --git a/libc/src/__support/alloc/baremetal/page.cpp b/libc/src/__support/alloc/baremetal/page.cpp
@@ -0,0 +1,22 @@
+#include "src/__support/alloc/page.h"
+#include "src/__suport/macros/config.h"
+
+namespace LIBC_NAMESPACE_DECL {
+
+extern "C" void *__llvm_libc_page_allocate(size_t n_pages);
+extern "C" void *__llvm_libc_page_expand(void *ptr, size_t n_pages);
+extern "C" bool __llvm_libc_page_free(void *ptr, size_t n_pages);
+
+void *page_allocate(size_t n_pages) {
+  return __llvm_libc_page_allocate(n_pages);
+}
+
+void *page_expand(void *ptr, size_t n_pages) {
+  return __llvm_libc_page_expand(ptr, n_pages);
+}
+
+bool page_free(void *ptr, size_t n_pages) {
+  return __llvm_libc_page_free(ptr, n_pages);
+}
+
+} // namespace LIBC_NAMESPACE_DECL
diff --git a/libc/src/__support/alloc/base.cpp b/libc/src/__support/alloc/base.cpp
@@ -0,0 +1,16 @@
+#include "src/__support/alloc/base.h"
+#include "src/__support/macros/config.h"
+
+namespace LIBC_NAMESPACE_DECL {
+
+void *BaseAllocator::alloc(size_t alignment, size_t size) {
+  return impl_alloc(this, alignment, size);
+}
+
+void *BaseAllocator::expand(void *ptr, size_t alignment, size_t size) {
+  return impl_expand(this, ptr, alignment, size);
+}
+
+bool BaseAllocator::free(void *ptr) { return impl_free(this, ptr); }
+
+} // namespace LIBC_NAMESPACE_DECL
diff --git a/libc/src/__support/alloc/base.h b/libc/src/__support/alloc/base.h
@@ -0,0 +1,44 @@
+//===-- A generic base allocator. -------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC___SUPPORT_ALLOC_BASE_H
+#define LLVM_LIBC_SRC___SUPPORT_ALLOC_BASE_H
+
+#include "hdr/types/size_t.h"
+#include "src/__support/macros/config.h"
+
+namespace LIBC_NAMESPACE_DECL {
+
+class BaseAllocator {
+public:
+  using AllocFunc = void *(BaseAllocator *self, size_t, size_t);
+  using ExpandFunc = void *(BaseAllocator *self, void *, size_t, size_t);
+  using FreeFunc = bool(BaseAllocator *self, void *);
+
+private:
+  // Implementation specific functions
+  AllocFunc *impl_alloc;
+  ExpandFunc *impl_expand;
+  FreeFunc *impl_free;
+
+public:
+  constexpr BaseAllocator(AllocFunc *ia, ExpandFunc *ie, FreeFunc *ifr,
+                          size_t default_alignment)
+      : impl_alloc(ia), impl_expand(ie), impl_free(ifr),
+        default_alignment(default_alignment) {}
+
+  size_t default_alignment;
+
+  void *alloc(size_t alignment, size_t size);
+  void *expand(void *ptr, size_t alignment, size_t size);
+  bool free(void *ptr);
+};
+
+} // namespace LIBC_NAMESPACE_DECL
+
+#endif // LLVM_LIBC_SRC___SUPPORT_ALLOC_BASE_H
-Original file line number
+Diff line change
@@ -115,6 +115,10 @@
         "LIBC_ADD_NULL_CHECKS": {
           "value": true,
           "doc": "Add nullptr checks in the library's implementations to some functions for which passing nullptr is undefined behavior."
+        },
+        "LIBC_CONF_ALLOC_TYPE": {
+          "value": "LIBC_ALLOC_TYPE_ARENA",
+          "doc": "The implementation used for allocations, acceptable values are LIBC_ALLOC_TYPE_EXTERN, LIBC_ALLOC_TYPE_SCUDO, LIBC_ALLOC_TYPE_ARENA."
             Copy link

  
      
    
  

  
      

  
    Contributor


      

  

  
    
      

      
            mysterymath
  

      

      

      


        Jan 8, 2025


      
  •

  
    
      
        
          edited
          
        
        
      
    
    
      
  
        
      Loading


  
    
  
    
      

              Uh oh!

              
There was an error while loading. Please reload this page.


  
  
    
  


    

  


        
      
  
  
  
    

    There was a problem hiding this comment.


  

 
  
    

    Choose a reason for hiding this comment

    
      The reason will be displayed to describe this comment to others. Learn more.
    

    
      
      


  


  
    
      How does this interact with the existing embedded allocator present in the libc? Immediately it's unusual that it isn't present in a list of allocators.
The allocator doesn't currently work for Linux, but that's something I'm planning to fix in the near future. It's just for lack of a __morecore abstraction hooked up to e.g. sbrk, plus the plumbing for that sycall.
    
  
  


    

        
      
  
  
    
  
  
  
    
    Sorry, something went wrong.
  

  
    
  
    
      

              Uh oh!

              
There was an error while loading. Please reload this page.


  
  


          
      
  
    
    
      
        
            
    All reactions
  


          
          
        
      
    

    



  
        
  
    
        
    
  


      
          
  
      
            Copy link

  
      
    
  

  
      

  
  Member


      

  Author


  

  
    
      

      
            RossComputerGuy
  

      

      

      


        Jan 8, 2025


      
    

  


        
      
  
  
  
    

    There was a problem hiding this comment.


  

 
  
    

    Choose a reason for hiding this comment

    
      The reason will be displayed to describe this comment to others. Learn more.
    

    
      
      


  


  
    
      I'm not familiar with existing allocators being implemented. I could hook them up to support the option and general interface.
    
  
  


    

        
      
  
  
    
  
  
  
    
    Sorry, something went wrong.
  

  
    
  
    
      

              Uh oh!

              
There was an error while loading. Please reload this page.


  
  


          
      
  
    
    
      
        
            
    All reactions
         }
       },
       "unistd": {
-          Expand Down