FixedRangeConfig loses every batched remote deallocation: open_free_ring() runs the ring's bit-packed length through capptr_domesticate()

[sblessing]

Summary

With FixedRangeConfig (or any config whose capptr_domesticate() rejects addresses outside the heap) and batched remote deallocation enabled (DEALLOC_BATCH_RINGS > 0, the default whenever [[no_unique_address]] is available), every object freed by an allocator other than its owner is leaked. The receiving allocator decodes each incoming ring as length 0, never decrements the slab's needed count, and the slab sleeps forever. A fixed region is exhausted by remote frees alone even though the program frees everything it allocates.

Root cause

BatchedRemoteMessage::mk_from_freelist_builder() (src/snmalloc/mem/remoteallocator.h) closes the ring by storing a bit-packed word in the message's next field:

auto n = freelist::HeadPtr::unsafe_from(
  unsafe_from_uintptr<freelist::Object::T<>>(
    (static_cast<uintptr_t>(pointer_diff_signed(self, first)) << MAX_CAPACITY_BITS) + size));
freelist::Object::store_nextish(&self->free_ring.next_object, first, key, key_tweak, n);

That word is (displacement << 11) + length; it is not an address. On the receiving side, open_free_ring() and ring_size() read it back with

uintptr_t encoded =
  m->free_ring.read_next(key, key_tweak, domesticate).unsafe_uintptr();

and freelist::Object::T::read_next() (src/snmalloc/mem/freelist.h) is domesticate(Object::decode_next(...)). So the packed word is handed to the config's domesticator as if it were a pointer.

FixedRangeConfig::capptr_domesticate() (src/snmalloc/backend/fixedglobalconfig.h) does what a domesticator is supposed to do and returns nullptr for anything outside Pagemap::get_bounds(). A small displacement shifted left by 11 plus a small length is never inside the heap, so encoded becomes 0: decoded_size is 0 and the derived next pointer is the message itself. Back in Allocator::dealloc_local_objects_fast() (src/snmalloc/mem/corealloc.h) the slab receives append_segment(curr, msg, 0, ...) and return_objects(0). needed never reaches zero, the slab is never woken, and the other objects of the ring are unreachable.

The default StandardConfig does not set HasDomesticate, so its domesticator is the identity and the word passes through untouched, which is why the mainstream configuration is unaffected. The domestication test in src/test/func/domestication/domestication.cc installs a domesticator that never returns nullptr either, so it does not catch this. Its comment // TODO This fails when we add a second remote deallocation. Is this a sign that we are missing places where we should domesticate? appears to be the same defect seen from the other side: with two remote frees of the same slab the message is a batched ring, and the ring's length word is what gets mangled.

Environment

• snmalloc b7fd8a3, header-only, unmodified
• Apple clang 21.0.0, arm64 macOS; also observed in a freestanding aarch64 kernel build with SNMALLOC_USE_SELF_VENDORED_STL
• -std=c++20 and -std=c++17 both fail: with this compiler __has_cpp_attribute(no_unique_address) is true in C++17 mode as well, so DEALLOC_BATCH_RING_ASSOC is 2 in both (MIN_ALLOC_SIZE=16, DEALLOC_BATCH_RINGS=16, MAX_CAPACITY_BITS=11, freelist_backward_edge=0)

Reproducer

Allocator A allocates 64 objects of 64 bytes from a 32 MiB fixed region, allocator B frees them and flushes, repeat. Everything allocated is freed, so the loop should run forever.

repro.cc

// Reproducer: FixedRangeConfig (range-checking capptr_domesticate) loses every
// batched remote deallocation. Allocator A allocates small objects, allocator B
// frees them and flushes; the objects never return to A's slabs, so a fixed
// region is exhausted after a bounded number of rounds. Without the bug the
// loop runs until the round limit.
#include <snmalloc/backend/fixedglobalconfig.h>
#include <snmalloc/snmalloc.h>

#include <cstdio>
#include <cstdlib>

using namespace snmalloc;

using RangeConfig = FixedRangeConfig<PALNoAlloc<DefaultPal>>;
using RangeAlloc = Allocator<RangeConfig>;

int main()
{
  const size_t size = bits::one_at_bit(25);   // 32 MiB region
  void* base = DefaultPal::reserve(size);
  DefaultPal::notify_using<NoZero>(base, size);
  RangeConfig::init(nullptr, base, size);

  auto a = get_scoped_allocator<RangeAlloc>();
  auto b = get_scoped_allocator<RangeAlloc>();

  const size_t objsize = 64, batch = 64, max_rounds = 200000;
  void* objs[batch];
  size_t round = 0;
  for (; round < max_rounds; round++) {
    for (size_t i = 0; i < batch; i++) {
      objs[i] = a->alloc(objsize);
      if (objs[i] == nullptr) {
        printf("FAIL: allocator A returned nullptr in round %zu after %zu remote frees "
               "(%zu KiB of %zu KiB region, all of it freed)\n",
               round, round * batch, round * batch * objsize / 1024, size / 1024);
        return 1;
      }
    }
    for (size_t i = 0; i < batch; i++)
      b->dealloc(objs[i]);   // remote: B is not the owner
    b->flush();              // push the batched message to A's queue
  }
  printf("OK: %zu rounds, %zu remote frees of %zu-byte objects, region still healthy\n",
         round, round * batch, objsize);
  return 0;
}

Build and run (no CMake needed):

c++ -std=c++20 -O2 -DNDEBUG -DSNMALLOC_USE_WAIT_ON_ADDRESS=0 -I snmalloc/src -o repro repro.cc && ./repro

Results on the unmodified tree:

-std=c++20:                                    FAIL: allocator A returned nullptr in round 8144 after 521216 remote frees (32576 KiB of 32768 KiB region, all of it freed)
-std=c++17:                                    FAIL: allocator A returned nullptr in round 8144 after 521216 remote frees (32576 KiB of 32768 KiB region, all of it freed)
-std=c++20 -DSNMALLOC_DEALLOC_BATCH_RING_ASSOC=0:  OK: 200000 rounds, 12800000 remote frees of 64-byte objects, region still healthy

8144 rounds times 64 objects times 64 bytes is the whole region: every remotely freed byte was lost.

Proposed fix

Read the packed word without domesticating it. It is an opaque value, and the pointer that is later derived from it is already domesticated separately in open_free_ring(). The patch adds a read_next_raw() next to read_next() and uses it in the two places that read the ring word:

diff --git a/src/snmalloc/mem/freelist.h b/src/snmalloc/mem/freelist.h
index db059c5..9868943 100644
--- a/src/snmalloc/mem/freelist.h
+++ b/src/snmalloc/mem/freelist.h
@@ -235,6 +235,24 @@ namespace snmalloc
             key_tweak));
         }
 
+        /**
+         * Read the next field as an opaque word rather than as a pointer.
+         *
+         * BatchedRemoteMessage stores the bit-packed (displacement, length)
+         * of its free ring in this field; it is not an address, so it must
+         * not be passed through a domesticator, which may legitimately
+         * reject anything outside the heap.
+         */
+        uintptr_t read_next_raw(const FreeListKey& key, address_t key_tweak)
+        {
+          return Object::decode_next(
+                   address_cast(&this->next_object),
+                   this->next_object,
+                   key,
+                   key_tweak)
+            .unsafe_uintptr();
+        }
+
         /**
          * Check the signature of this free Object
          */
diff --git a/src/snmalloc/mem/remoteallocator.h b/src/snmalloc/mem/remoteallocator.h
index 57d7c31..31b766a 100644
--- a/src/snmalloc/mem/remoteallocator.h
+++ b/src/snmalloc/mem/remoteallocator.h
@@ -112,8 +112,7 @@ namespace snmalloc
       address_t key_tweak,
       Domesticator_queue domesticate)
     {
-      uintptr_t encoded =
-        m->free_ring.read_next(key, key_tweak, domesticate).unsafe_uintptr();
+      uintptr_t encoded = m->free_ring.read_next_raw(key, key_tweak);
 
       uint16_t decoded_size =
         static_cast<uint16_t>(encoded) & bits::mask_bits(MAX_CAPACITY_BITS);
@@ -155,8 +154,7 @@ namespace snmalloc
       address_t key_tweak,
       Domesticator_queue domesticate)
     {
-      uintptr_t encoded =
-        m->free_ring.read_next(key, key_tweak, domesticate).unsafe_uintptr();
+      uintptr_t encoded = m->free_ring.read_next_raw(key, key_tweak);
 
       uint16_t decoded_size =
         static_cast<uint16_t>(encoded) & bits::mask_bits(MAX_CAPACITY_BITS);

With the patch the reproducer runs to its 200 000 round limit, and the existing fixed_region and domestication tests still pass (domesticate_count drops from 5 to 4 in the latter, because the ring word is no longer domesticated; the test no longer asserts that number). A slightly larger change would be to give the ring word its own accessor on BatchedRemoteMessage rather than on freelist::Object::T, if you prefer to keep Object::T free of message-specific knowledge.

It may also be worth turning the domestication test's domesticator into a range-checking one (as FixedRangeConfig has) and adding a second remote dealloc of the same size class, so the batched path is covered by CI.

Workarounds

• Configure with SNMALLOC_DEALLOC_BATCH_RING_ASSOC=0 (disables batching everywhere), or
• use a config without HasDomesticate.

[nwf]

Oh good find and thank you for the very thorough, easily-read report! I think your proposed fix is correct. Please raise it as a PR, and add your reproducer to the test harness.

ETA: In the interest of DRY, can your PR also redefine snmalloc::freelist::Object::read_next in terms of the new read_next_raw? I know it's a very little bit of code, but the inliner should DTRT and it will make the difference between the two readily apparent.

[sblessing]

Sure thing. Thanks for the feedback re DRY. PR created!