diff --git a/libc/src/__support/CPP/CMakeLists.txt b/libc/src/__support/CPP/CMakeLists.txt --- a/libc/src/__support/CPP/CMakeLists.txt +++ b/libc/src/__support/CPP/CMakeLists.txt @@ -67,3 +67,9 @@ HDRS atomic.h ) + +add_header_library( + blobstore + HDRS + blobstore.h +) diff --git a/libc/src/__support/CPP/blobstore.h b/libc/src/__support/CPP/blobstore.h new file mode 100644 --- /dev/null +++ b/libc/src/__support/CPP/blobstore.h @@ -0,0 +1,160 @@ +//===-- A data structure which stores data in blobs ------------*- 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_SUPPORT_CPP_BLOBSTORE_H +#define LLVM_LIBC_SUPPORT_CPP_BLOBSTORE_H + +#include +#include +#include + +namespace __llvm_libc { +namespace cpp { + +// The difference between BlobStore a traditional vector types is that, +// when more capacity is desired, a new blob is added instead of allocating +// a larger sized array and copying over existing items to the new allocation. +// Also, the initial blob does not need heap allocation. Hence, a BlobStore is +// suitable for global objects as it does not require explicit construction. +// Also, the destructor of this class does nothing, which eliminates the need +// for an atexit global object destruction. But, it also means that the global +// object should be explicitly cleaned up at the appropriate time. +// +// If REVERSE_ORDER is true, the iteration of elements will in the reverse +// order. Also, since REVERSE_ORDER is a constexpr, conditionals branching +// on its value will be optimized out in the code below. +template +class BlobStore { +protected: + struct Blob { + alignas(T) uint8_t data[BLOB_SIZE * sizeof(T)]; + Blob *next = nullptr; + }; + + Blob first; + Blob *current = &first; + size_t fill_count = 0; + +public: + constexpr BlobStore() = default; + ~BlobStore() = default; + + class iterator { + Blob *blob; + size_t index; + + public: + constexpr iterator(Blob *b, size_t i) : blob(b), index(i) {} + + iterator &operator++() { + if (REVERSE_ORDER) { + if (index == 0) + return *this; + + --index; + if (index == 0 && blob->next != nullptr) { + index = BLOB_SIZE; + blob = blob->next; + } + } else { + if (index == BLOB_SIZE) + return *this; + + ++index; + if (index == BLOB_SIZE && blob->next != nullptr) { + index = 0; + blob = blob->next; + } + } + + return *this; + } + + T &operator*() { + size_t true_index = REVERSE_ORDER ? index - 1 : index; + return *reinterpret_cast(blob->data + sizeof(T) * true_index); + } + + bool operator==(const iterator &rhs) const { + return blob == rhs.blob && index == rhs.index; + } + + bool operator!=(const iterator &rhs) const { + return blob != rhs.blob || index != rhs.index; + } + }; + + static void destroy(BlobStore *blob_store); + + T *new_obj() { + if (fill_count == BLOB_SIZE) { + auto new_blob = reinterpret_cast(::malloc(sizeof(Blob))); + if (REVERSE_ORDER) { + new_blob->next = current; + } else { + new_blob->next = nullptr; + current->next = new_blob; + } + current = new_blob; + fill_count = 0; + } + T *obj = reinterpret_cast(current->data + fill_count * sizeof(T)); + ++fill_count; + return obj; + } + + void push_back(const T &value) { + T *ptr = new_obj(); + *ptr = value; + } + + iterator begin() { + if (REVERSE_ORDER) + return iterator(current, fill_count); + else + return iterator(&first, 0); + } + + iterator end() { + if (REVERSE_ORDER) + return iterator(&first, 0); + else + return iterator(current, fill_count); + } +}; + +template +void BlobStore::destroy( + BlobStore *blob_store) { + if (REVERSE_ORDER) { + auto current = blob_store->current; + while (current->next != nullptr) { + auto temp = current; + current = current->next; + free(temp); + } + } else { + auto current = blob_store->first.next; + while (current != nullptr) { + auto temp = current; + current = current->next; + free(temp); + } + } + blob_store->current = nullptr; + blob_store->fill_count = 0; +} + +// A convenience type for reverse order blob stores. +template +using ReverseOrderBlobStore = BlobStore; + +} // namespace cpp +} // namespace __llvm_libc + +#endif // LLVM_LIBC_SUPPORT_CPP_BLOBSTORE_H diff --git a/libc/src/stdlib/CMakeLists.txt b/libc/src/stdlib/CMakeLists.txt --- a/libc/src/stdlib/CMakeLists.txt +++ b/libc/src/stdlib/CMakeLists.txt @@ -276,8 +276,10 @@ atexit.cpp HDRS atexit.h + COMPILE_OPTIONS + -O3 # To prevent constexpr constructors from getting emitted in debug mode. DEPENDS - libc.src.__support.CPP.vector + libc.src.__support.CPP.blobstore libc.src.__support.threads.thread ) diff --git a/libc/src/stdlib/atexit.cpp b/libc/src/stdlib/atexit.cpp --- a/libc/src/stdlib/atexit.cpp +++ b/libc/src/stdlib/atexit.cpp @@ -7,7 +7,7 @@ //===----------------------------------------------------------------------===// #include "src/stdlib/atexit.h" -#include "src/__support/CPP/vector.h" +#include "src/__support/CPP/blobstore.h" #include "src/__support/common.h" #include "src/__support/threads/mutex.h" @@ -17,29 +17,30 @@ Mutex handler_list_mtx(false, false, false); -// TOOD should we make cpp::vector like llvm::SmallVector where it will -// allocate at least N before needing dynamic allocation? -static cpp::vector handlers; +using AtExitCallback = void(void); +using ExitCallbackList = cpp::ReverseOrderBlobStore; +static ExitCallbackList exit_callbacks; } // namespace namespace internal { -void call_exit_handlers() { +void call_exit_callbacks() { handler_list_mtx.lock(); - // TODO: implement rbegin() + rend() for cpp::vector - for (int i = handlers.size() - 1; i >= 0; i--) { + auto end = exit_callbacks.end(); + for (auto callback : exit_callbacks) { handler_list_mtx.unlock(); - handlers[i](); + callback(); handler_list_mtx.lock(); } + ExitCallbackList::destroy(&exit_callbacks); } } // namespace internal -LLVM_LIBC_FUNCTION(int, atexit, (void (*function)())) { +LLVM_LIBC_FUNCTION(int, atexit, (AtExitCallback * callback)) { handler_list_mtx.lock(); - handlers.push_back(function); + exit_callbacks.push_back(callback); handler_list_mtx.unlock(); return 0; } diff --git a/libc/src/stdlib/exit.cpp b/libc/src/stdlib/exit.cpp --- a/libc/src/stdlib/exit.cpp +++ b/libc/src/stdlib/exit.cpp @@ -13,11 +13,11 @@ namespace __llvm_libc { namespace internal { -void call_exit_handlers(); +void call_exit_callbacks(); } LLVM_LIBC_FUNCTION(void, exit, (int status)) { - internal::call_exit_handlers(); + internal::call_exit_callbacks(); _Exit(status); } diff --git a/libc/test/src/__support/CPP/CMakeLists.txt b/libc/test/src/__support/CPP/CMakeLists.txt --- a/libc/test/src/__support/CPP/CMakeLists.txt +++ b/libc/test/src/__support/CPP/CMakeLists.txt @@ -69,3 +69,13 @@ DEPENDS libc.src.__support.CPP.atomic ) + +add_libc_unittest( + blobstore_test + SUITE + libc_cpp_utils_unittests + SRCS + blobstore_test.cpp + DEPENDS + libc.src.__support.CPP.blobstore +) diff --git a/libc/test/src/__support/CPP/blobstore_test.cpp b/libc/test/src/__support/CPP/blobstore_test.cpp new file mode 100644 --- /dev/null +++ b/libc/test/src/__support/CPP/blobstore_test.cpp @@ -0,0 +1,66 @@ +//===-- Unittests for blobstore -------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#include "src/__support/CPP/blobstore.h" +#include "utils/UnitTest/Test.h" + +struct Element { + int a; + long b; + unsigned c; +}; + +class LlvmLibcBlobStoreTest : public __llvm_libc::testing::Test { +public: + template + void populate_and_iterate() { + __llvm_libc::cpp::BlobStore blob_store; + for (int i = 0; i < int(ELEMENT_COUNT); ++i) + blob_store.push_back({i, 2 * i, 3 * unsigned(i)}); + auto end = blob_store.end(); + int i = 0; + for (auto iter = blob_store.begin(); iter != end; ++iter, ++i) { + Element &e = *iter; + if (REVERSE) { + int j = ELEMENT_COUNT - 1 - i; + ASSERT_EQ(e.a, j); + ASSERT_EQ(e.b, long(j * 2)); + ASSERT_EQ(e.c, unsigned(j * 3)); + } else { + ASSERT_EQ(e.a, i); + ASSERT_EQ(e.b, long(i * 2)); + ASSERT_EQ(e.c, unsigned(i * 3)); + } + } + ASSERT_EQ(i, int(ELEMENT_COUNT)); + } +}; + +TEST_F(LlvmLibcBlobStoreTest, PopulateAndIterate4) { + populate_and_iterate<4, 4, false>(); +} + +TEST_F(LlvmLibcBlobStoreTest, PopulateAndIterate8) { + populate_and_iterate<4, 8, false>(); +} + +TEST_F(LlvmLibcBlobStoreTest, PopulateAndIterate10) { + populate_and_iterate<4, 10, false>(); +} + +TEST_F(LlvmLibcBlobStoreTest, PopulateAndIterateReverse4) { + populate_and_iterate<4, 4, true>(); +} + +TEST_F(LlvmLibcBlobStoreTest, PopulateAndIterateReverse8) { + populate_and_iterate<4, 8, true>(); +} + +TEST_F(LlvmLibcBlobStoreTest, PopulateAndIterateReverse10) { + populate_and_iterate<4, 10, true>(); +}