[Tim]
> Recall that pymalloc delegates requests for "not small" blocks to
> the system malloc. This means that when pymalloc's free() is called,
> it has to figure out whether the address passed to it was one it
> allocated itself, or came from the system malloc.
> ...
> However, the question remained whether a hostile user could study
> the source code to mount a successful attack. Alas, it turns out
> that's easy.
There may be hope for this, and another strong reason for pursuing it.
Guido pointed out that *if* pymalloc's free() could know for sure whether an
address passed to it did or didn't come from the system malloc, then we
could also (probably -- needs some more thought) continue to use the
PyObject interface, *without* breaking most "illegal by fiat" old code, via
also mapping PyMem_{Free, FREE, Del, DEL} to the pymalloc free (when
pymalloc is enabled): then the various PyMem_NukeIt spellings would *know*
whether to pass a piece of memory on to the system free().
So I have a variant of pymalloc that doesn't use magic cookies -- it knows
"for sure", by maintaining a sorted (by address) contiguous vector of the
base addresses of the (256KB each) "arenas" allocated by pymalloc. A given
address A either does or doesn't satisfy
B <= A < B+256KB
for some base address B in this list. At worst, a binary search is needed
to see whether any such B exists. For a typical 2**31 byte VM address
space, we can get at most 2**31/2**18 == 2**13 arenas, so at worst this
vector can grow to a measly 8K entries (typically far fewer), and 13 is a
reasonable upper bound on the number of compares needed.
So it can't be a disaster, but neither is it dirt cheap. A promising
candidate for saving grace: in tests so far, frees tend to hit the same
arena many times in a row. By saving a search finger into the vector that
remembers the last hit index, and checking that location first, I'm seeing
hit rates over 85%. The two-sided range test at the finger index can be
inlined, and the two compares it requires are exactly as many compares as
the current magic-cookie tests do. So, most of the time, it may run as fast
as now.
For an address pymalloc *doesn't* handle on its own, though, a full binary
search is required to discover that it's not a pymalloc address. Leaving at
least one magic-cookie gimmick in could slash that (if the magic cookie
isn't there, we know for sure it's not a pymalloc address). So the test
becomes something like
def PyMalloc_Free(thisaddr):
# ... weed out NULL ...
# not NULL
if (addrs[finger] <= thisaddr < addrs[finger] + 256KB
or (thisaddr_has_magic_cookie and binary_search_for(thisaddr)):
it's a pymalloc addr
else
it goes to the system free()
That gives a likely fast-path for each class of address, and should never
err (provided we're passed legitimate addresses, and user code doesn't write
out of bounds, etc).
A nasty subtlety: if PyMem_NukeIt is called when the GIL isn't held, it's
going to take a lot of thought to see whether this can be made safe when
called simultaneously by multiple threads; e.g., the finger can change
"mid-stream" then, and, worse, some thread that *does* hold the GIL may
legitimately cause a new arena to be allocated midstream, mutating the
address vector during the search. This may be intractable enough to kill
the idea of mapping PyMem_XXX to this.
A nasty trick: due to the wonders of unsigned arithmetic, the two-sided
range test can be reduced to one compare:
(Py_uintptr)thisaddr - (Py_uintptr)addrs[finger] < 256KB
In other news, "it's obvious" that the small object threshhold is too small
for 2.3. I'm still inclined to max it out.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4