Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit bce6b17

Browse filesBrowse files
RossComputerGuyRossComputerGuy
committed
[libc] add basic arena allocator
1 parent 80079de commit bce6b17
Copy full SHA for bce6b17
Expand file treeCollapse file tree

23 files changed

+525
-0
lines changed

‎libc/CMakeLists.txt

Copy file name to clipboardExpand all lines: libc/CMakeLists.txt
+6Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -386,6 +386,12 @@ else()
386386
set(libc_opt_high_flag "-O3")
387387
endif()
388388

389+
if(${LIBC_CONF_ALLOC_TYPE} MATCHES "LIBC_ALLOC_TYPE_SCUDO")
390+
set(LLVM_LIBC_INCLUDE_SCUDO ON)
391+
elseif(LLVM_LIBC_INCLUDE_SCUDO)
392+
message(FATAL_ERROR "Cannot include scudo and use a different allocator.")
393+
endif()
394+
389395
add_subdirectory(include)
390396
add_subdirectory(config)
391397
add_subdirectory(hdr)

‎libc/config/config.json

Copy file name to clipboardExpand all lines: libc/config/config.json
+4Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -115,6 +115,10 @@
115115
"LIBC_ADD_NULL_CHECKS": {
116116
"value": true,
117117
"doc": "Add nullptr checks in the library's implementations to some functions for which passing nullptr is undefined behavior."
118+
},
119+
"LIBC_CONF_ALLOC_TYPE": {
120+
"value": "LIBC_ALLOC_TYPE_ARENA",
121+
"doc": "The implementation used for allocations, acceptable values are LIBC_ALLOC_TYPE_EXTERN, LIBC_ALLOC_TYPE_SCUDO, LIBC_ALLOC_TYPE_ARENA."
118122
}
119123
},
120124
"unistd": {

‎libc/docs/configure.rst

Copy file name to clipboardExpand all lines: libc/docs/configure.rst
+1Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,7 @@ to learn about the defaults for your platform and target.
3232
- ``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.
3333
* **"general" options**
3434
- ``LIBC_ADD_NULL_CHECKS``: Add nullptr checks in the library's implementations to some functions for which passing nullptr is undefined behavior.
35+
- ``LIBC_CONF_ALLOC_TYPE``: The implementation used for allocations, acceptable values are LIBC_ALLOC_TYPE_EXTERN, LIBC_ALLOC_TYPE_SCUDO, LIBC_ALLOC_TYPE_ARENA.
3536
* **"math" options**
3637
- ``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.
3738
- ``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.

‎libc/src/__support/CMakeLists.txt

Copy file name to clipboardExpand all lines: libc/src/__support/CMakeLists.txt
+2Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -370,3 +370,5 @@ add_subdirectory(HashTable)
370370
add_subdirectory(fixed_point)
371371

372372
add_subdirectory(time)
373+
374+
add_subdirectory(alloc)

‎libc/src/__support/alloc/CMakeLists.txt

Copy file name to clipboard
+57Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
add_object_library(
2+
base
3+
SRCS
4+
base.cpp
5+
HDRS
6+
base.h
7+
DEPENDS
8+
libc.hdr.types.size_t
9+
libc.src.__support.macros.config
10+
)
11+
12+
if(EXISTS ${CMAKE_CURRENT_SOURCE_DIR}/${LIBC_TARGET_OS})
13+
add_subdirectory(${LIBC_TARGET_OS})
14+
endif()
15+
16+
if(TARGET libc.src.__support.alloc.${LIBC_TARGET_OS}.page)
17+
add_object_library(
18+
page
19+
ALIAS
20+
DEPENDS
21+
.${LIBC_TARGET_OS}.page
22+
)
23+
endif()
24+
25+
add_object_library(
26+
arena
27+
SRCS
28+
arena.cpp
29+
HDRS
30+
arena.h
31+
COMPILE_OPTIONS
32+
-DLIBC_PAGE_SIZE=${LIBC_CONF_PAGE_SIZE}
33+
DEPENDS
34+
.base
35+
.page
36+
libc.include.llvm-libc-macros.stdint_macros
37+
libc.src.string.memmove
38+
libc.src.unistd.getpagesize
39+
)
40+
41+
if(NOT ${LIBC_CONF_ALLOC_TYPE} MATCHES "LIBC_ALLOC_TYPE_SCUDO" AND NOT ${LIBC_CONF_ALLOC_TYPE} MATCHES "LIBC_ALLOC_TYPE_EXTERN")
42+
string(TOLOWER ${LIBC_CONF_ALLOC_TYPE} LIBC_CONF_ALLOC_TYPE_NAME)
43+
string(REPLACE "libc_alloc_type_" "" LIBC_CONF_ALLOC_TYPE_NAME "${LIBC_CONF_ALLOC_TYPE_NAME}")
44+
if(TARGET libc.src.__support.alloc.${LIBC_CONF_ALLOC_TYPE_NAME})
45+
add_object_library(
46+
alloc
47+
SRCS
48+
alloc.cpp
49+
HDRS
50+
alloc.h
51+
COMPILE_OPTIONS
52+
-DLIBC_CONF_ALLOC_TYPE=${LIBC_CONF_ALLOC_TYPE_NAME}
53+
DEPENDS
54+
.${LIBC_CONF_ALLOC_TYPE_NAME}
55+
)
56+
endif()
57+
endif()

‎libc/src/__support/alloc/alloc.cpp

Copy file name to clipboard
+13Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
#include <src/__support/alloc/alloc.h>
2+
#include <src/__support/alloc/arena.h>
3+
4+
namespace LIBC_NAMESPACE_DECL {
5+
6+
#define CONCAT(a, b) a##b
7+
#define EXPAND_AND_CONCAT(a, b) CONCAT(a, b)
8+
9+
#define ALLOCATOR EXPAND_AND_CONCAT(LIBC_CONF_ALLOC_TYPE, _allocator)
10+
11+
BaseAllocator *allocator = reinterpret_cast<BaseAllocator *>(&ALLOCATOR);
12+
13+
} // namespace LIBC_NAMESPACE_DECL

‎libc/src/__support/alloc/alloc.h

Copy file name to clipboard
+22Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
//===-- libc-wide allocator -------------------------------------*- C++ -*-===//
2+
//
3+
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4+
// See https://llvm.org/LICENSE.txt for license information.
5+
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6+
//
7+
//===----------------------------------------------------------------------===//
8+
9+
#ifndef LLVM_LIBC_SRC___SUPPORT_ALLOC_ALLOC_H
10+
#define LLVM_LIBC_SRC___SUPPORT_ALLOC_ALLOC_H
11+
12+
#include "src/__support/alloc/base.h"
13+
#include "src/__support/macros/config.h"
14+
15+
namespace LIBC_NAMESPACE_DECL {
16+
17+
// The primary allocator to use
18+
extern BaseAllocator *allocator;
19+
20+
} // namespace LIBC_NAMESPACE_DECL
21+
22+
#endif

‎libc/src/__support/alloc/arena.cpp

Copy file name to clipboard
+71Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
#include "src/__support/alloc/arena.h"
2+
#include "src/__support/alloc/page.h"
3+
#include "src/__support/common.h"
4+
#include "src/__support/macros/config.h"
5+
#include "src/__support/macros/page_size.h"
6+
#include "src/__support/memory_size.h"
7+
#include "src/string/memmove.h"
8+
#include "src/unistd/getpagesize.h"
9+
10+
namespace LIBC_NAMESPACE_DECL {
11+
12+
void *arena_allocate(BaseAllocator *base, size_t alignment, size_t size) {
13+
ArenaAllocator *self = reinterpret_cast<ArenaAllocator *>(base);
14+
15+
if (self->buffer == nullptr) {
16+
self->buffer = reinterpret_cast<uint8_t *>(page_allocate(1));
17+
self->buffer_size = self->get_page_size();
18+
}
19+
20+
uintptr_t curr_ptr = (uintptr_t)self->buffer + (uintptr_t)self->curr_offset;
21+
uintptr_t offset = internal::align_forward<uintptr_t>(curr_ptr, alignment);
22+
offset -= (uintptr_t)self->buffer;
23+
24+
if (offset + size > self->buffer_size) {
25+
self->buffer = reinterpret_cast<uint8_t *>(
26+
page_expand(self->buffer, self->buffer_size / self->get_page_size()));
27+
self->buffer_size += self->get_page_size();
28+
}
29+
30+
if (offset + size <= self->buffer_size) {
31+
void *ptr = &self->buffer[offset];
32+
self->prev_offset = offset;
33+
self->curr_offset = offset + size;
34+
return ptr;
35+
}
36+
return nullptr;
37+
}
38+
39+
void *arena_expand(BaseAllocator *base, void *ptr, size_t alignment,
40+
size_t size) {
41+
ArenaAllocator *self = reinterpret_cast<ArenaAllocator *>(base);
42+
43+
if (self->buffer + self->prev_offset == ptr) {
44+
self->curr_offset = self->prev_offset + size;
45+
return ptr;
46+
} else {
47+
void *new_mem = arena_allocate(base, alignment, size);
48+
memmove(new_mem, ptr, size);
49+
return new_mem;
50+
}
51+
return nullptr;
52+
}
53+
54+
bool arena_free(BaseAllocator *base, void *ptr) {
55+
(void)base;
56+
(void)ptr;
57+
return true;
58+
}
59+
60+
size_t ArenaAllocator::get_page_size() {
61+
if (page_size == LIBC_PAGE_SIZE_SYSTEM) {
62+
page_size = getpagesize();
63+
}
64+
return page_size;
65+
}
66+
67+
static ArenaAllocator default_arena_allocator(LIBC_PAGE_SIZE,
68+
2 * sizeof(void *));
69+
BaseAllocator *block_allocator = &default_arena_allocator;
70+
71+
} // namespace LIBC_NAMESPACE_DECL

‎libc/src/__support/alloc/arena.h

Copy file name to clipboard
+47Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
//===-- An arena allocator using pages. -------------------------*- C++ -*-===//
2+
//
3+
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4+
// See https://llvm.org/LICENSE.txt for license information.
5+
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6+
//
7+
//===----------------------------------------------------------------------===//
8+
9+
#ifndef LLVM_LIBC_SRC___SUPPORT_ALLOC_ARENA_H
10+
#define LLVM_LIBC_SRC___SUPPORT_ALLOC_ARENA_H
11+
12+
#include "hdr/types/size_t.h"
13+
#include "include/llvm-libc-macros/stdint-macros.h"
14+
#include "src/__support/alloc/base.h"
15+
16+
namespace LIBC_NAMESPACE_DECL {
17+
18+
void *arena_allocate(BaseAllocator *base, size_t alignment, size_t size);
19+
void *arena_expand(BaseAllocator *base, void *ptr, size_t alignment,
20+
size_t size);
21+
bool arena_free(BaseAllocator *base, void *ptr);
22+
23+
class ArenaAllocator : public BaseAllocator {
24+
public:
25+
uint8_t *buffer;
26+
size_t buffer_size;
27+
size_t prev_offset;
28+
size_t curr_offset;
29+
30+
private:
31+
size_t page_size;
32+
33+
public:
34+
constexpr ArenaAllocator(size_t page_size, size_t default_alignment)
35+
: BaseAllocator(arena_allocate, arena_expand, arena_free,
36+
default_alignment),
37+
buffer(nullptr), buffer_size(0), prev_offset(0), curr_offset(0),
38+
page_size(page_size) {}
39+
40+
size_t get_page_size();
41+
};
42+
43+
extern BaseAllocator *arena_allocator;
44+
45+
} // namespace LIBC_NAMESPACE_DECL
46+
47+
#endif

‎libc/src/__support/alloc/baremetal/CMakeLists.txt

Copy file name to clipboard
+13Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
add_object_library(
2+
page
3+
SRCS
4+
page.cpp
5+
HDRS
6+
../page.h
7+
DEPENDS
8+
libc.src.__support.alloc.base
9+
libc.src.sys.mman.mmap
10+
libc.src.sys.mman.mremap
11+
libc.src.sys.mman.munmap
12+
libc.src.unistd.getpagesize
13+
)

‎libc/src/__support/alloc/baremetal/page.cpp

Copy file name to clipboard
+22Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
#include "src/__support/alloc/page.h"
2+
#include "src/__suport/macros/config.h"
3+
4+
namespace LIBC_NAMESPACE_DECL {
5+
6+
extern "C" void *__llvm_libc_page_allocate(size_t n_pages);
7+
extern "C" void *__llvm_libc_page_expand(void *ptr, size_t n_pages);
8+
extern "C" bool __llvm_libc_page_free(void *ptr, size_t n_pages);
9+
10+
void *page_allocate(size_t n_pages) {
11+
return __llvm_libc_page_allocate(n_pages);
12+
}
13+
14+
void *page_expand(void *ptr, size_t n_pages) {
15+
return __llvm_libc_page_expand(ptr, n_pages);
16+
}
17+
18+
bool page_free(void *ptr, size_t n_pages) {
19+
return __llvm_libc_page_free(ptr, n_pages);
20+
}
21+
22+
} // namespace LIBC_NAMESPACE_DECL

‎libc/src/__support/alloc/base.cpp

Copy file name to clipboard
+16Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
#include "src/__support/alloc/base.h"
2+
#include "src/__support/macros/config.h"
3+
4+
namespace LIBC_NAMESPACE_DECL {
5+
6+
void *BaseAllocator::alloc(size_t alignment, size_t size) {
7+
return impl_alloc(this, alignment, size);
8+
}
9+
10+
void *BaseAllocator::expand(void *ptr, size_t alignment, size_t size) {
11+
return impl_expand(this, ptr, alignment, size);
12+
}
13+
14+
bool BaseAllocator::free(void *ptr) { return impl_free(this, ptr); }
15+
16+
} // namespace LIBC_NAMESPACE_DECL

‎libc/src/__support/alloc/base.h

Copy file name to clipboard
+44Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
//===-- A generic base allocator. -------------------------------*- C++ -*-===//
2+
//
3+
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4+
// See https://llvm.org/LICENSE.txt for license information.
5+
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6+
//
7+
//===----------------------------------------------------------------------===//
8+
9+
#ifndef LLVM_LIBC_SRC___SUPPORT_ALLOC_BASE_H
10+
#define LLVM_LIBC_SRC___SUPPORT_ALLOC_BASE_H
11+
12+
#include "hdr/types/size_t.h"
13+
#include "src/__support/macros/config.h"
14+
15+
namespace LIBC_NAMESPACE_DECL {
16+
17+
class BaseAllocator {
18+
public:
19+
using AllocFunc = void *(BaseAllocator *self, size_t, size_t);
20+
using ExpandFunc = void *(BaseAllocator *self, void *, size_t, size_t);
21+
using FreeFunc = bool(BaseAllocator *self, void *);
22+
23+
private:
24+
// Implementation specific functions
25+
AllocFunc *impl_alloc;
26+
ExpandFunc *impl_expand;
27+
FreeFunc *impl_free;
28+
29+
public:
30+
constexpr BaseAllocator(AllocFunc *ia, ExpandFunc *ie, FreeFunc *ifr,
31+
size_t default_alignment)
32+
: impl_alloc(ia), impl_expand(ie), impl_free(ifr),
33+
default_alignment(default_alignment) {}
34+
35+
size_t default_alignment;
36+
37+
void *alloc(size_t alignment, size_t size);
38+
void *expand(void *ptr, size_t alignment, size_t size);
39+
bool free(void *ptr);
40+
};
41+
42+
} // namespace LIBC_NAMESPACE_DECL
43+
44+
#endif // LLVM_LIBC_SRC___SUPPORT_ALLOC_BASE_H

‎libc/src/__support/alloc/linux/CMakeLists.txt

Copy file name to clipboard
+16Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
add_object_library(
2+
page
3+
SRCS
4+
page.cpp
5+
HDRS
6+
../page.h
7+
DEPENDS
8+
libc.hdr.types.size_t
9+
libc.include.llvm-libc-macros.stdlib_macros
10+
libc.include.llvm-libc-macros.stdint_macros
11+
libc.src.__support.alloc.base
12+
libc.src.sys.mman.mmap
13+
libc.src.sys.mman.mremap
14+
libc.src.sys.mman.munmap
15+
libc.src.unistd.getpagesize
16+
)

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.