[Python-Dev] pymalloc killer

[Tim Peters]

After digesting some ideas from David Abrahams offlist, I believe I may have
a much simpler way to make a bulletproof "is or isn't this address from a
pymalloc pool?" test.  Described as a diff from current pymalloc:

1. Keep a contiguous vector of arena base addresses.  This is not
   sorted.  When a new arena is allocated, its base address is simply
   appended.  Space required is proportional to the # of arenas in
   use (4 bytes/arena on a 32-bit box; 8 bytes/arena on a 64-bit box).

2. Remove the "magic number" gimmick from pool headers.

3. In place of the pooladr member of a pool header, add an arenaindex
   member.  Every pool in an arena sets this to the index of its arena's
   base address, wrt the vector in #2.

4. To check an address p, find its pool header address just as now.
   Then read up arenaindex.  If that's out of bounds for the #2 vector,
   it's not a pymalloc address.  If it is in bounds, read the arena
   base address B out of the #2 vector, and see whether B <= p < B + 256KB
   (which can again be collapsed into a tricksy one-compare test via
   exploiting unsigned arithmetic).

In #4, it's quite possible that non-pymalloc memory will lead to an
in-bounds arenaindex -- but it can't pass the address test then.

Limitation:  if arenaindex is 32 bits, we can index at most 2**32 arenas,
covering at most 2**32 arenas * 2**18 bytes/arena = 2**50 bytes on a 64-bit
box.  At that point we'd be devoting 2**32 arenas * 8
bytes-for-address/arena = 32 gigabtyes to the base-address vector.  I assume
the program will die long before this for some other good reason <wink>.