1 files changed, 91 insertions, 0 deletions
diff --git a/js/src/gc/MallocedBlockCache.h b/js/src/gc/MallocedBlockCache.h
new file mode 100644
index 0000000000..546d7e50af
--- /dev/null
+++ b/js/src/gc/MallocedBlockCache.h
@@ -0,0 +1,91 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sw=2 et tw=80:
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this file,
+ * You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef gc_MallocedBlockCache_h
+#define gc_MallocedBlockCache_h
+
+#include "ds/PointerAndUint7.h"
+#include "js/AllocPolicy.h"
+#include "js/Vector.h"
+#include "util/Poison.h"
+
+namespace js {
+namespace gc {
+
+// MallocedBlockCache implements a lightweight wrapper around js_malloc/js_free.
+//
+// Blocks are requested by ::alloc and must be returned with ::free, at which
+// point the cache may decide to hold on to the block rather than hand it back
+// to js_free.  Subsequent ::alloc calls may be satisfied from the cached
+// blocks rather than calling js_malloc.  The mechanism is designed to be much
+// cheaper than calling js_malloc/js_free directly.  One consequence is that
+// there is no locking; it is essential therefore to use each cache only from
+// a single thread.
+//
+// The intended use is for lightweight management of OOL (malloc'd) storage
+// associated with WasmStructObject and WasmArrayObject.  The mechanism is
+// general and potentially has other uses.  Blocks of size STEP * NUM_LISTS
+// and larger are never cached, though.
+//
+// Request sizes are rounded up to a multiple of STEP.  There are NUM_LISTS-1
+// free lists, with a "List ID" indicating the multiple of STEP stored on the
+// list.  So for example, blocks of size 3 * STEP (after rounding up) are
+// stored on the list with ID 3.  List ID 0 indicates blocks which are too
+// large to live on any freelist.  With the default settings, this gives
+// separate freelists for blocks of size 16, 32, 48, .. 496.  Blocks of size
+// zero are not supported, and `lists[0]` will always be empty.
+//
+// Allocation of a block produces not only the block's address but also its
+// List ID.  When freeing, both values must be presented, because there is
+// otherwise no way for ::free to know the size of the original allocation,
+// and hence which freelist it should go on.  For this reason, the ::alloc and
+// ::free methods produce and take a `PointerAndUint7`, not a `void*`.
+//
+// Resizing of blocks is not supported.
+
+class MallocedBlockCache {
+ public:
+  static const size_t STEP = 16;
+
+  static const size_t NUM_LISTS = 32;
+  // This limitation exists because allocation returns a PointerAndUint7, and
+  // a List-ID value (viz, 0 .. NUM_LISTS-1) is stored in the Uint7 part.
+  static_assert(NUM_LISTS <= (1 << 7));
+
+  // list[0] must always remain empty.  List ID 0 indicates a block which
+  // cannot participate in the freelist machinery because it is too large.
+  //
+  // list[i], for 1 <= i < NUM_LISTS, holds blocks of size i * STEP only.
+  // All requests are rounded up to multiple of SIZE.
+  //
+  // We do not expect to be required to issue or accept blocks of size zero.
+  static const size_t OVERSIZE_BLOCK_LIST_ID = 0;
+  using MallocedBlockVector = Vector<void*, 0, SystemAllocPolicy>;
+
+  MallocedBlockVector lists[NUM_LISTS];
+
+  ~MallocedBlockCache();
+
+  // Allocation and freeing.
+  [[nodiscard]] PointerAndUint7 alloc(size_t size);
+  void free(PointerAndUint7 blockAndListID);
+
+  // Allows users to gradually hand blocks back to js_free, so as to avoid
+  // space leaks in long-running scenarios.  The specified percentage of
+  // blocks in each list is discarded.
+  void preen(float percentOfBlocksToDiscard);
+
+  // Return all blocks in the cache to js_free.
+  void clear();
+
+  size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const;
+};
+
+}  // namespace gc
+}  // namespace js
+
+#endif  // gc_MallocedBlockCache_h