I think it's time to change what address_in_range() tries to answer. It currently gives a precise answer to "is this byte address in a region obmalloc owns?". But that's stronger than what it needs to do its job: the real question is "is this an address that obmalloc could return from its malloc() or realloc() functions?". Because it's only used by free() and realloc(), and they only care where the address they're _passed_ came from.

The difference is when an arena is not pool-aligned. Oddball chunks outside of full pools, at both ends of the arena, are never returned by obmalloc then.

Instead the tree could be changed to record the starting addresses of the _full_ pools obmalloc controls.  Those contain the only addresses obmalloc will ever pass out (from malloc() or realloc()).

Like so, where p is the arena base address. This hasn't been tested, and may contain typos or logical errors. I'm far more interested in the latter for now ;-)

ideal1 = p & ~ARENA_SIZE_MASK # round down to ideal
ideal2 = ideal1 + ARENA_SIZE
offset = p - ideal1
b1 = bottom_node(ideal1)
b2 = bottom_node(ideal2)
if not offset:
    # already ideal
    b1.hi = -1
    assert b2.lo == 0
elif offset & POOL_SIZE_MASK == 0:
    # arena is pool-aligned
    b1.hi = b2.lo = offset
else:
    # Not pool-aligned.
    # obmalloc won't pass out an address higher than in
    # the last full pool.
    # Round offset down to next lower pool address.
    offset &= ~POOL_SIZE_MASK
    b2.lo = offset
    # And won't pass out an address lower than in the
    # first full pool.
    offset += POOL_SIZE # same as rounding original offset up
    # That's almost right for b1.hi, but one exception: if
    # offset is ARENA_SIZE now, the first full pool is at the
    # start of ideal2, and no feasible address is in ideal1.
    assert offset <= ARENA_SIZE
    b1.hi = offset & ARENA_SIZE_MASK 

Note that, except for the oddball -1, everything stored in a bottom node is a pool address then, and so there's no need to store their all-zero lowest POOL_BITS bits. .lo and .hi can be shrunk to a signed 8-bit int with the current settings (20 arena bits and 14 pool bits).

And caching pool addresses wouldn't have any obscure failing end-cases either: address_in_range() could just as well be passed a pool address to begin with. It would only care about pool addresses, not byte addresses.