symmetryinvestments · schveiguy · Jul 12, 2025 · Jul 10, 2025 · Jul 10, 2025 · Jul 10, 2025
diff --git a/source/d/gc/arena.d b/source/d/gc/arena.d
@@ -139,6 +139,7 @@ public:
 		ubyte sizeClass,
 		void** top,
 		void** bottom,
+		void** requested,
 		size_t slotSize,
 	) shared {
 		// TODO: in contracts
@@ -147,8 +148,8 @@ public:
 		import d.gc.slab;
 		assert(slotSize == binInfos[sizeClass].slotSize, "Invalid slot size!");
 
-		return bins[sizeClass]
-			.batchAllocate(&filler, emap, sizeClass, top, bottom, slotSize);
+		return bins[sizeClass].batchAllocate(&filler, emap, sizeClass, top,
+											 bottom, requested, slotSize);
 	}
 
 	uint batchFree(ref CachedExtentMap emap, inout(void)*[] worklist,
@@ -163,12 +164,7 @@ public:
 		auto doTheRest() nothrow {
 			try {
 				uint ndalloc = 0;
-				scope(success) if (ndalloc > 0) {
-					foreach (i; 0 .. ndalloc) {
-						// FIXME: batch free to go through the lock once using freeExtentLocked.
-						filler.freeExtent(emap, dallocSlabs[i]);
-					}
-				}
+				scope(success) filler.batchFreeExtents(emap, dallocSlabs[0 .. ndalloc]);
 
 				auto ec = pds[0].extentClass;
 				auto sc = ec.sizeClass;

diff --git a/source/d/gc/bin.d b/source/d/gc/bin.d
@@ -27,6 +27,7 @@ struct Bin {
 		ubyte sizeClass,
 		void** top,
 		void** bottom,
+		void** requested,
 		size_t slotSize,
 	) shared {
 		import d.gc.sizeclass;
@@ -38,6 +39,9 @@ struct Bin {
 		assert(bottom < top, "Invalid stack boundaries!");
 		assert((top - bottom) < uint.max, "Invalid stack size!");
 
+		assert(bottom < requested && requested <= top,
+				"Invalid requested slot count!");
+
 		/**
 		 * When we run out of slab with free space, we allocate a fresh slab.
 		 * However, while we do so, another thread may have returned slabs to
@@ -112,8 +116,20 @@ struct Bin {
 		assert(freshSlab is null);
 		assert(progressed);
 
-		freshSlab = filler.allocSlab(emap, sizeClass);
+		/**
+		 * We want to avoid leaving partially filled slabs behind us,
+		 * so, before allocating a new slab, we make sure that it'll
+		 * either be required to meet the requested number of slot,
+		 * or that it'll be completely filled.
+		 */
+		assert(bottom <= insert && insert < top, "Invalid insertion point!");
+		auto navailable = top - insert;
 		auto nslots = binInfos[sizeClass].nslots;
+		if (requested <= insert && navailable <= nslots) {
+			return insert;
+		}
+
+		freshSlab = filler.allocSlab(emap, sizeClass);
 		assert(freshSlab is null || freshSlab.nfree == nslots);
 
 		progressed = false;

diff --git a/source/d/gc/emap.d b/source/d/gc/emap.d
@@ -11,10 +11,11 @@ import symgc.intrinsics;
 shared ExtentMap gExtentMap;
 
 alias ExtentMapCache = RTreeCache!PageDescriptor;
+alias ExtentMapTree = RTree!PageDescriptor;
 
 struct ExtentMap {
 private:
-	RTree!PageDescriptor tree;
+	ExtentMapTree tree;
 
 public:
 	PageDescriptor lookup(ref ExtentMapCache cache, void* address) shared {
@@ -27,6 +28,26 @@ public:
 		return BlockExtentMap(block, tree.get(cache, block));
 	}
 
+	void batchLookup(ref ExtentMapCache cache, void*[] addresses,
+	                 PageDescriptor* pds) shared {
+		// Just resuse the same buffer.
+		alias Leaf = ExtentMapTree.Leaf;
+		auto leaves = cast(shared(Leaf)**) pds;
+
+		// Fetch all the leaves in one scoop.
+		foreach (i, ptr; addresses) {
+			import d.gc.util;
+			auto aptr = alignDown(ptr, PageSize);
+			leaves[i] = tree.get(cache, aptr);
+		}
+
+		// Generate the page descriptors.
+		foreach (i, ptr; addresses) {
+			auto leaf = leaves[i];
+			pds[i] = leaf is null ? PageDescriptor(0) : leaf.load();
+		}
+	}
+
 	bool map(ref shared Base base, ref ExtentMapCache cache, void* address,
 	         uint pages, PageDescriptor pd) shared {
 		return tree.setRange(cache, address, pages, pd, base);
@@ -46,23 +67,23 @@ public:
  * After all, we are trading one lookup in the cache vs one lookup in the
  * base level of the ExtentMap, so it's not obvious where the win is.
  *
- * Each entry in the cache maps to 1GB of address space, so we expect the hiy
+ * Each entry in the cache maps to 1GB of address space, so we expect the hit
  * rate in the cache to be close to 100% . Realistically, most applications
  * won't use more than 16GB of address space, and for these which do, you'd
- * still need scattered access access accross this huge address space for the
+ * still need scattered access access across this huge address space for the
  * hit rate to degrade, in which case the performance of this cache is unlikely
  * to be of any significant importance.
  *
  * Each page that we expect to be hot in the GC is one less page that can be
- * hot for the applciation itself. So in general, we try to avoid touching
+ * hot for the application itself. So in general, we try to avoid touching
  * memory when we don't need to. We know the thread cache has to be hot as it
  * is the entry point for every GC operation. Adding this cache in the thread
  * cache ensures that we can have a close to 100% hit rate by only touching
  * memory that has to be hot no matter what. This turns out to be a win.
  *
  * If later on we want to support system with more than 48 bits of address
  * space, then we will need an extent map with 3 levels, and this cache will
- * avoid 2 lookups insteaf of 1, which is much more obvious win.
+ * avoid 2 lookups instead of 1, which is much more obvious win.
  */
 struct CachedExtentMap {
 private:
@@ -86,6 +107,10 @@ public:
 		return emap.blockLookup(cache, address);
 	}
 
+	void batchLookup(void*[] addresses, PageDescriptor* pds) {
+		emap.batchLookup(cache, addresses, pds);
+	}
+
 	bool map(void* address, uint pages, PageDescriptor pd) {
 		return emap.map(*base, cache, address, pages, pd);
 	}
@@ -143,12 +168,6 @@ public:
 		data |= ulong(extent.arenaIndex) << 48;
 	}
 
-	this(Extent* extent) {
-		// FIXME: in contract.
-		assert(!extent.isSlab(), "Extent is a slab!");
-		this(extent, ExtentClass.large());
-	}
-
 	auto toLeafPayload() const {
 		return data;
 	}
@@ -215,7 +234,7 @@ private:
 	void* block;
 	shared(Leaf[PagesInBlock])* leaves;
 
-	alias Leaf = RTree!PageDescriptor.Leaf;
+	alias Leaf = ExtentMapTree.Leaf;
 
 public:
 	this(void* block, shared(Leaf)* leaf) {
@@ -240,6 +259,32 @@ public:
 	emapStorage.initialize(base);
 	auto emap = CachedExtentMap(&emapStorage, &base);
 
+	void checkExtentMapping(Extent* e) {
+		auto npages = e.npages + 2;
+		import core.stdc.stdlib : alloca;
+		auto ptrs = cast(void**) alloca(npages * PointerSize);
+
+		auto ptr = e.address - PageSize;
+		foreach (i; 0 .. npages) {
+			ptrs[i] = ptr;
+			ptr += PageSize;
+		}
+
+		auto pds = cast(PageDescriptor*) alloca(npages * PageDescriptor.sizeof);
+		emap.batchLookup(ptrs[0 .. npages], pds);
+
+		// Check before and after.
+		assert(pds[0].extent !is e);
+		assert(pds[npages - 1].extent !is e);
+
+		// Check the extent itself is mapped.
+		auto pd = PageDescriptor(e, e.extentClass);
+		foreach (i; 1 .. npages - 1) {
+			assert(pds[i].data == pd.data);
+			pd = pd.next();
+		}
+	}
+
 	// We have not mapped anything.
 	auto ptr = cast(void*) 0x56789abcd000;
 	assert(emap.lookup(ptr).data == 0);
@@ -250,14 +295,10 @@ public:
 
 	// Map a range.
 	emap.remap(e);
-	auto pd = PageDescriptor(e);
+	checkExtentMapping(e);
 
+	// Check that we have nothing after the extent.
 	auto end = ptr + e.size;
-	for (auto p = ptr; p < end; p += PageSize) {
-		assert(emap.lookup(p).data == pd.data);
-		pd = pd.next();
-	}
-
 	assert(emap.lookup(end).data == 0);
 
 	// Clear a range.
@@ -266,26 +307,26 @@ public:
 		assert(emap.lookup(p).data == 0);
 	}
 
+	// Same test, but with a slab.
 	auto ec = ExtentClass.slab(0);
 	e.at(ptr, 5, null, ec);
 	emap.remap(e, ec);
-	pd = PageDescriptor(e, ec);
 
-	for (auto p = ptr; p < end; p += PageSize) {
-		assert(emap.lookup(p).data == pd.data);
-		pd = pd.next();
-	}
+	checkExtentMapping(e);
+	assert(emap.lookup(end).data == 0);
 
 	emap.clear(e);
+	for (auto p = ptr; p < end; p += PageSize) {
+		assert(emap.lookup(p).data == 0);
+	}
 
 	// Shrink a range.
 	e.at(ptr, 5, null, ec);
 	emap.remap(e, ec);
-	pd = PageDescriptor(e, ec);
-
 	emap.clear(e.address + 3 * PageSize, 2);
 	e.at(ptr, 3, null, ec);
 
+	auto pd = PageDescriptor(e, ec);
 	for (auto p = ptr; p < e.address + 3 * PageSize; p += PageSize) {
 		assert(emap.lookup(p).data == pd.data);
 		pd = pd.next();

diff --git a/source/d/gc/page.d b/source/d/gc/page.d
@@ -242,8 +242,33 @@ public:
 	}
 
 	void freeExtent(ref CachedExtentMap emap, Extent* e) shared {
-		emap.clear(e);
-		freePages(e);
+		assert(e.arenaIndex == arena.index, "Invalid arena!");
+		batchFreeExtents(emap, (&e)[0 .. 1]);
+	}
+
+	void batchFreeExtents(ref CachedExtentMap emap, Extent*[] extents) shared {
+		// FIXME: in contract.
+		foreach (e; extents) {
+			assert(e.arenaIndex == arena.index, "Invalid arena!");
+		}
+
+		// Avoid locking if there is nothing to do.
+		if (extents.length == 0) {
+			return;
+		}
+
+		// Clear the emap.
+		foreach (e; extents) {
+			emap.clear(e);
+		}
+
+		// Free the pages.
+		mutex.lock();
+		scope(exit) mutex.unlock();
+
+		foreach (e; extents) {
+			(cast(PageFiller*) &this).freePagesImpl(e);
+		}
 	}
 
 	void freePages(Extent* e) shared {
@@ -346,6 +371,16 @@ private:
 		return e.at(ptr, npages, block);
 	}
 
+	void freePagesImpl(Extent* e) {
+		assert(mutex.isHeld(), "Mutex not held!");
+		assert(isAligned(e.address, PageSize), "Invalid extent address!");
+
+		uint n = e.blockIndex;
+		uint pages = modUp(e.npages, PagesInBlock);
+
+		freePagesImpl(e, n, pages);
+	}
+
 	void freePagesImpl(Extent* e, uint n, uint pages) {
 		assert(mutex.isHeld(), "Mutex not held!");
 		assert(pages > 0 && pages <= PagesInBlock, "Invalid number of pages!");
@@ -1034,11 +1069,7 @@ private:
 		assert(isAligned(e.address, PageSize), "Invalid extent address!");
 
 		emap.clear(e);
-
-		uint n = e.blockIndex;
-		uint pages = modUp(e.npages, PagesInBlock);
-
-		(cast(PageFiller*) &this).freePagesImpl(e, n, pages);
+		freePagesImpl(e);
 	}
 }
 

diff --git a/source/d/gc/rtree.d b/source/d/gc/rtree.d
@@ -87,19 +87,6 @@ public:
 		return &(*leaves)[subKey(address, 1)];
 	}
 
-	shared(Leaf)* getOrAllocate(ref Cache cache, void* address,
-	                            ref shared Base base) shared {
-		// FIXME: in contract.
-		assert(isValidAddress(address));
-
-		auto leaves = getOrAllocateLeaves(cache, address, base);
-		if (unlikely(leaves is null)) {
-			return null;
-		}
-
-		return &(*leaves)[subKey(address, 1)];
-	}
-
 	bool set(ref Cache cache, void* address, T value,
 	         ref shared Base base) shared {
 		// FIXME: in contract.
@@ -210,6 +197,19 @@ public:
 	}
 
 private:
+	shared(Leaf)* getOrAllocate(ref Cache cache, void* address,
+	                            ref shared Base base) shared {
+		// FIXME: in contract.
+		assert(isValidAddress(address));
+
+		auto leaves = getOrAllocateLeaves(cache, address, base);
+		if (unlikely(leaves is null)) {
+			return null;
+		}
+
+		return &(*leaves)[subKey(address, 1)];
+	}
+
 	auto getLeaves(ref Cache cache, void* address) shared {
 		return getLeavesImpl!false(cache, address, null);
 	}