[libc] Add a resizable container with constexpr constructor and destructor.

[sivachandra]

Summary

The new container is used to store atexit callbacks. This way, we avoid
the possibility of the destructor of the container itself getting added
as an at exit callback.

[abrachet]

The new container is used to store atexit callbacks. This way, we avoid
the possibility of the destructor of the container itself getting added
as at exit callback.

Ah I didn't think about that, we would run into this when we implement __cxa_atexit. That would have been a confusing sanitizer error! Good catch.

libc/src/__support/CPP/blobstore.h

31 ↗

(On Diff #414265)

Could we just have a reverse_iterator [rbegin|rend]() instead of this REVERSE_ORDER template parameter? Maybe it makes more sense for BlobStore<T>::iterator to have REVERSE_ORDER?

libc/src/stdlib/CMakeLists.txt

280

From what I understand, as long as T is POD and BlobStore<T>::~BlobStore() is defaulted, then there shouldn't be a destructor emitted because then BlobStore will be a POD too. Do you see __cxa_atexit` being called in this TU?

We could in the future when we add an analogue to is_trivially_destructible in our type_traits, add static_assert(cpp::IsTriviallyDestructibleV<ExitCallbackList>)

libc/src/stdlib/atexit.cpp

31

If we keep BlobStore with REVERSE_ORDER this could just be for (auto callback : exit_callbacks)

35

It may not be worth deallocating this when we are going to exit soon anyway. But it might not be worth the trouble of needing to make sanitizers ignore this

[sivachandra]

Use range for-loop.

[sivachandra]

libc/src/__support/CPP/blobstore.h

31 ↗

(On Diff #414265)

If we have to support bidirectional iteration, then we need a doubly-linked list. Not sure if we will ever need bidirectional iteration so I have chosen to keep it a simple linked list with the direction attached to the type.

Maybe it makes more sense for BlobStore<T>::iterator to have REVERSE_ORDER?

Do you mean, it enables range-for-loop? Or, something else?

libc/src/stdlib/CMakeLists.txt

280

You are correct. I think I misread or checked it with the previous mutex handling still present that I did see a call to __cxa_atexit. I don't see it now.

That said, in a debug build, I surprisingly see a call to the constructor (via __cxx_global_var_init) if I don't use -O3 [may be -O2 is sufficient, I did not check]. In a release build, everything works as expected without -O3 - I don't see calls to the constructor or __cxa_atexit. So, I have kept the -O3 for now.

libc/src/stdlib/atexit.cpp

31

Ah, yes. Done now.

[abrachet]

libc/src/__support/CPP/blobstore.h

1 ↗

(On Diff #414298)

Do you think the name BlockStore better describes what this data structure does? It may not be worth the churn to change the name everywhere, no strong preference.

31 ↗

(On Diff #414265)

No strong preference because we would need to add one pointer overhead with a new prev pointer to Blob, but it would be much more ergonomic if BlobStore could iterate both ways.

REVERSE_ORDER could be changed to only be used in the iterator. So maybe it could be like

template <bool REVERSE_ORDER> class iterator_impl { ... };
using iterator = iterator_impl<false>;
using reverse_iterator = iterator_impl<true>;
iterator rbegin() {
  return reverse_iterator(current, fill_count);
}
...

libc/src/stdlib/CMakeLists.txt

280

That said, in a debug build, I surprisingly see a call to the constructor (via __cxx_global_var_init) if I don't use -O3

We just bumped up to C++17 and we already need C++20's constinit! :)

Specifying O3 here makes this TU basically impossible to debug and generally limits options. Maybe we want to optimize hard for size with Oz but atexit will always be O3.

Are global constructors something we need to avoid? The destructor was going to affect correctness, but unless I'm missing something the same isn't true for constructors. Is it worth the downside above if this will be optimized away during release builds anyway?

libc/src/stdlib/atexit.cpp

22

I don't know why I made this static before when it is already in an anonymous namespace

30

Not needed anymore

40

I think this is how we would normally format this. But if clang-format get's confused because of the parentheses then we should just go with what clang-format says.

[sivachandra]

• Change the name from BlobStore to BlockStore.
• Use c++ 20 to compile atexit.cpp.

[sivachandra]

libc/src/__support/CPP/blobstore.h

1 ↗

(On Diff #414298)

I like BlockStore better so I changed it.

31 ↗

(On Diff #414265)

I agree that having a forward and reverse iterator would be aesthetically/"ergonomically" ideal. Also, while I do not see today as to why we would need bidirectional iteration, I won't be surprised we actually make it a doubly linked list and allow bidirectional iteration in future. But, until then, I personally prefer to keep it restrictive.

libc/src/stdlib/CMakeLists.txt

280

The high level design goal is that, the runtime should iterate over init array (which is how the constructors will get called) and fini array to facilitate certain language features. If the runtime itself starts requiring them, we will soon end up with chicken and egg problems.

We can make an exception here because it is affecting debug builds only. But, a difference in behavior between debug and release builds will be hard to debug when we have to.

There are two options here - use C++ 20 (for constinit) for this TU or use a higher optimization level for this TU. I personally do not have problems with either of them. By the time this gets used in real production systems, C++ 20 will be acceptable. I preferred -O3 because I am not sure if our bots will like the C++ 20 feature. I have changed now to use C++ 20 instead of -O3. If the bots don't like it, I can switch back to -O3.

libc/src/stdlib/atexit.cpp

40

Yes, that was done by clang-format.

[abrachet]

Thanks, this is much more correct than what I had and more performant too.

libc/src/__support/CPP/blobstore.h

31 ↗

(On Diff #414265)

Sounds good.

libc/src/stdlib/CMakeLists.txt

280

You're right, it's actually very likely that a C++ object will have it's constructor and __cxa_atexit registration before this constructor is called. I don't know why I didn't see that... There is no way for us to control the order .init_array elements will be ordered across TU's so yes we need to make sure exit_callbacks is constructed statically.

I was actually joking about constinit, but it might be our best option here. O3 doesn't guarantee that this object will be constructed statically. I was thinking this would be easy enough to optimize that any compiler would do it and it would be as good as a guarantee, but actually GCC doesn't at any optimization level but clang get's it even at O1. https://godbolt.org/z/4Pv3TdG77

Using a C++20 compiler isn't that big of an ask because there's one in the same repo as this, and we could recommend the runtimes build for this case. Let's discuss further offline

libc/src/__support/CPP/CMakeLists.txt

DEPENDS
     libc.include.stdlib
 )
 
 add_header_library(
   atomic
   HDRS
     atomic.h
 )
+
+add_header_library(
+  blockstore
+  HDRS
+    blockstore.h
+)

libc/src/__support/CPP/blockstore.h

+//===-- A data structure which stores data in blocks  -----------*- 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_BLOCKSTORE_H
+#define LLVM_LIBC_SUPPORT_CPP_BLOCKSTORE_H
+
+#include <stddef.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+namespace __llvm_libc {
+namespace cpp {
+
+// The difference between BlockStore a traditional vector types is that,
+// when more capacity is desired, a new block is added instead of allocating
+// a larger sized array and copying over existing items to the new allocation.
+// Also, the initial block does not need heap allocation. Hence, a BlockStore 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 <typename T, size_t BLOCK_SIZE, bool REVERSE_ORDER = false>
+class BlockStore {
+protected:
+  struct Block {
+    alignas(T) uint8_t data[BLOCK_SIZE * sizeof(T)] = {0};
+    Block *next = nullptr;
+  };
+
+  Block first;
+  Block *current = &first;
+  size_t fill_count = 0;
+
+public:
+  constexpr BlockStore() = default;
+  ~BlockStore() = default;
+
+  class iterator {
+    Block *block;
+    size_t index;
+
+  public:
+    constexpr iterator(Block *b, size_t i) : block(b), index(i) {}
+
+    iterator &operator++() {
+      if (REVERSE_ORDER) {
+        if (index == 0)
+          return *this;
+
+        --index;
+        if (index == 0 && block->next != nullptr) {
+          index = BLOCK_SIZE;
+          block = block->next;
+        }
+      } else {
+        if (index == BLOCK_SIZE)
+          return *this;
+
+        ++index;
+        if (index == BLOCK_SIZE && block->next != nullptr) {
+          index = 0;
+          block = block->next;
+        }
+      }
+
+      return *this;
+    }
+
+    T &operator*() {
+      size_t true_index = REVERSE_ORDER ? index - 1 : index;
+      return *reinterpret_cast<T *>(block->data + sizeof(T) * true_index);
+    }
+
+    bool operator==(const iterator &rhs) const {
+      return block == rhs.block && index == rhs.index;
+    }
+
+    bool operator!=(const iterator &rhs) const {
+      return block != rhs.block || index != rhs.index;
+    }
+  };
+
+  static void destroy(BlockStore<T, BLOCK_SIZE, REVERSE_ORDER> *block_store);
+
+  T *new_obj() {
+    if (fill_count == BLOCK_SIZE) {
+      auto new_block = reinterpret_cast<Block *>(::malloc(sizeof(Block)));
+      if (REVERSE_ORDER) {
+        new_block->next = current;
+      } else {
+        new_block->next = nullptr;
+        current->next = new_block;
+      }
+      current = new_block;
+      fill_count = 0;
+    }
+    T *obj = reinterpret_cast<T *>(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 <typename T, size_t BLOCK_SIZE, bool REVERSE_ORDER>
+void BlockStore<T, BLOCK_SIZE, REVERSE_ORDER>::destroy(
+    BlockStore<T, BLOCK_SIZE, REVERSE_ORDER> *block_store) {
+  if (REVERSE_ORDER) {
+    auto current = block_store->current;
+    while (current->next != nullptr) {
+      auto temp = current;
+      current = current->next;
+      free(temp);
+    }
+  } else {
+    auto current = block_store->first.next;
+    while (current != nullptr) {
+      auto temp = current;
+      current = current->next;
+      free(temp);
+    }
+  }
+  block_store->current = nullptr;
+  block_store->fill_count = 0;
+}
+
+// A convenience type for reverse order block stores.
+template <typename T, size_t BLOCK_SIZE>
+using ReverseOrderBlockStore = BlockStore<T, BLOCK_SIZE, true>;
+
+} // namespace cpp
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SUPPORT_CPP_BLOCKSTORE_H

libc/src/stdlib/CMakeLists.txt

 )
 
 add_entrypoint_object(
   atexit
   SRCS
     atexit.cpp
   HDRS
     atexit.h
+  CXX_STANDARD
+    20 # For constinit of the atexit callback list.
   DEPENDS
-    libc.src.__support.CPP.vector
+    libc.src.__support.CPP.blockstore
     libc.src.__support.threads.thread
 )
 
 add_entrypoint_object(
   exit
   SRCS
     exit.cpp
   HDRS

libc/src/stdlib/atexit.cpp

 //===-- Implementation of atexit ------------------------------------------===//
 //
 // 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/stdlib/atexit.h"
-#include "src/__support/CPP/vector.h"
+#include "src/__support/CPP/blockstore.h"
 #include "src/__support/common.h"
 #include "src/__support/threads/mutex.h"
 
 namespace __llvm_libc {
 
 namespace {
 
 Mutex handler_list_mtx(false, false, false);
 
-// TOOD should we make cpp::vector like llvm::SmallVector<T, N> where it will
-// allocate at least N before needing dynamic allocation?
-static cpp::vector<void (*)(void)> handlers;
+using AtExitCallback = void(void);
+using ExitCallbackList = cpp::ReverseOrderBlockStore<AtExitCallback *, 32>;
+constinit 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--) {
+  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;
 }
 
 } // namespace __llvm_libc

libc/src/stdlib/exit.cpp

 //===-- Implementation of exit --------------------------------------------===//
 //
 // 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/stdlib/exit.h"
 #include "src/__support/common.h"
 #include "src/stdlib/_Exit.h"
 
 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);
 }
 
 } // namespace __llvm_libc

libc/test/src/__support/CPP/CMakeLists.txt

add_libc_unittest(
   atomic_test
   SUITE
     libc_cpp_utils_unittests
   SRCS
     atomic_test.cpp
   DEPENDS
     libc.src.__support.CPP.atomic
 )
+
+add_libc_unittest(
+  blockstore_test
+  SUITE
+    libc_cpp_utils_unittests
+  SRCS
+    blockstore_test.cpp
+  DEPENDS
+    libc.src.__support.CPP.blockstore
+)

libc/test/src/__support/CPP/blockstore_test.cpp

+//===-- Unittests for BlockStore ------------------------------------------===//
+//
+// 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/blockstore.h"
+#include "utils/UnitTest/Test.h"
+
+struct Element {
+  int a;
+  long b;
+  unsigned c;
+};
+
+class LlvmLibcBlockStoreTest : public __llvm_libc::testing::Test {
+public:
+  template <size_t BLOCK_SIZE, size_t ELEMENT_COUNT, bool REVERSE>
+  void populate_and_iterate() {
+    __llvm_libc::cpp::BlockStore<Element, BLOCK_SIZE, REVERSE> block_store;
+    for (int i = 0; i < int(ELEMENT_COUNT); ++i)
+      block_store.push_back({i, 2 * i, 3 * unsigned(i)});
+    auto end = block_store.end();
+    int i = 0;
+    for (auto iter = block_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(LlvmLibcBlockStoreTest, PopulateAndIterate4) {
+  populate_and_iterate<4, 4, false>();
+}
+
+TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterate8) {
+  populate_and_iterate<4, 8, false>();
+}
+
+TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterate10) {
+  populate_and_iterate<4, 10, false>();
+}
+
+TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterateReverse4) {
+  populate_and_iterate<4, 4, true>();
+}
+
+TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterateReverse8) {
+  populate_and_iterate<4, 8, true>();
+}
+
+TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterateReverse10) {
+  populate_and_iterate<4, 10, true>();
+}