Some wild-ass thoughts: On Fri, 29 Mar 2002, Tim Peters wrote:

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 make multiple thread-specific fingers, which will presumably result in higher hit rates due to better locality. To prevent fingers from being invalidated, do not remove arenas that are deallocated from the tree -- just mark them inactive.

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.

Why not use a smaller (non-global) lock to protect arena modification and finger flushing? Ideally, the lock should be cheap for readers (which I presume will be the vast majority of accesses) and relatively expensive for writers (which I assume will occur only when arenas are added or deactivated). -Kevin -- Kevin Jacobs The OPAL Group - Enterprise Systems Architect Voice: (216) 986-0710 x 19 E-mail: jacobs@theopalgroup.com Fax: (216) 986-0714 WWW: http://www.theopalgroup.com

There may be hope for this, and another strong reason for pursuing it. [good stuff snipped]

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.

I know of two places that calls PyMem_Malloc outside the GIL: PyOS_StdioReadline in Parser/myreadline.c and call_readline() in Modules/readline.c. The memory thus allocated is returned by PyOS_Readline() (which calls either function through a hook pointer), and both its callers (the tokenizer and raw_input()) free the result using PyMem_DEL or PyMem_FREE (these two seem to be used synonymically). The tokenizer code may also apply PyMem_RESIZE to it (it incorporated the input line in its buffer structure). This would have to be fixed by changing the allocations to use malloc() (as they did up to 1.5.2 :-) and by changing the consumers to use free() and realloc(). (An alternative would be to let PyOS_Readline() copy the memory to PyMem_Malloc'ed memory.) This is part of a "hook" API that allows 3rd parties to provide their own alternative to PyOS_Readline. This was put in at the request of some folks at LLNL who were providing their own GUI that fed into Python and who had some problems with sending it to stdin. I don't think anybody else has used this. There is not a single mention of PyOS_Readline in the entire set of Python documentation. Given the alternatives: 1. introduce new APIs PyMalloc_{New,Del}Object and tell all extension writers that they have to changes their extensions once again to use these brand new APIs if they want to benefit from pymalloc; or 2. fix the issues with PyOS_Readline, make PyMem_{DEL,FREE,Del,Free} synonyms for Tim's clever PyMem_NukeIt, and continue to promote using PyObject_{New,Del} for use by extension writers; I'm all for #2. --Guido van Rossum (home page: http://www.python.org/~guido/)

[Tim]

This is the kind of heroic effort I don't want to impose on users: you have encyclopedic knowledge of how the Python implementation may be abusing this stuff, and you *invented* the rules <wink>. Random extension authors are going to have a much harder time of it -- as far as they're concerned, PyMem_{DEL, FREE, Del, Free} are all just ways to spell "platform free(), but I'm not supposed to call free() directly for some reason I don't understand -- I think it might have had something to do with DLLs on Windows".

On the other hand, the less sophisticated extension writers never release the GIL at all. [me]

...

Given the alternatives:

1. introduce new APIs PyMalloc_{New,Del}Object and tell all extension writers that they have to changes their extensions once again to use these brand new APIs if they want to benefit from pymalloc; or

2. fix the issues with PyOS_Readline, make PyMem_{DEL,FREE,Del,Free} synonyms for Tim's clever PyMem_NukeIt, and continue to promote using PyObject_{New,Del} for use by extension writers;

I'm all for #2.

You're presenting #1 as user-hostile and #2 as user-friendly. But if part of #2 is also saying that it's now definitely illegal to call PyMem_{Free, FREE, Del, DEL} without holding the GIL, and horrible things may start to happen in 2.3 if you're doing so, then it's also user-hostile in that respect. #1 is user-friendly in the "nothing breaks" sense. I haven't given up on combining the best of both, but I am getting close <wink>.

All I can do is encourage you to keep trying. I find it quite encouraging that you found a constant-time test for non-arena memory at all. Making it thread-safe should only add a tiny constant time. --Guido van Rossum (home page: http://www.python.org/~guido/)

[martin@v.loewis.de]

Are we discussing using PyMalloc even when not holding the GIL? That can't possibly work: pymalloc maintains linked lists of free memory; if two allocate or deallocate objects in the same pool simultaneously, bad things will happen.

I checked in obmalloc changes sufficient so that PyObject_XXX *could* be changed to use pymalloc again, and not break if a PyObject "get memory" function is mixed with a PyMem "free memory" function. This requires (in part) that all the latter be redirected to use the (new, as of a couple hours ago) pymalloc free. This leaves one known hole for backward compatibility: some people call a PyMem "get memory" routine when not holding the GIL. That's still no problem, because the PyMem "get memory" routines would still call the system malloc without pymalloc getting involved. Some people also call a PyMem "free memory" routine when not holding the GIL, but only on memory that was obtained from a PyMem "get memory" routine. That's the potential problem. The PyMem "free memory" routines would invoke pymalloc's free, and the mere act of *checking* the address passed to PyMem free() is vulnerable if the GIL isn't held. It's not obvious how it's vulnerable, so I'll spell it out: Some thread that does hold the GIL and simultaneously calls a PyObject "get memory" routine ends up in the pymalloc malloc, and *if* that needs to allocate a new arena, and *if* that in turn requires growing the vector of arena base addresses, then there appears to be no way (short of slopping locks on everything) to guarantee that the *other* thread (in pymalloc free) won't pick up an address for the arena-base-address vector that's invalid by the time it gets around to indexing into it. It's an extremely small hole (just a couple machine instructions), and requires an extremely unlikely set of circumstances to make it possible to fall into it, but it is a real hole all the same. There wouldn't be a hole if the vector of arena base addresses were statically allocated.

...

There wouldn't be a hole if the vector of arena base addresses were statically allocated.

[David Abrahams]

This could be a reason to use the 2-level arena vector we were discussing earlier. I was just assuming you wouldn't ever want to reallocate it or move anything that big...

A 2-level vector would complicate the code in ways that slow it down in the usual cases, so is unattractive. These vectors are generally *small*: on a 32-bit box, 1024 bytes of base-address vector is enough for that over 4 = 256 base addresses, which is enough to cover 2*8 * 2**18 = 64 megabytes of arena memory. Most programs will never go above that, and a one-time cost of moving 1KB per 64MB is trivial. It's quite attractive to just let the old vectors leak.

Heh -- letting old vectors leak may still not be good enough. Martin posted the relevant code: ((I) < narenas && (uptr)(P) - arenas[I] < (uptr)ARENA_SIZE) The problem remaining is that narenas can get out of synch with arenas, and if narenas refers to a later arena size, arenas[I] may be an out-of-bounds reference. This may be a good reason to make "narenas" and "arenas" volatile, in order to ensure that the former is read up before the latter.

[martin@v.loewis.de]

It would not be vulnerable if you would not free the old arena list, right?

Bingo! That occurred to me when I woke up. As I went to sleep, I was picturing an elaborate scheme of saving the "last N" vectors, and recycling them in tricky ways. Overnight, sleep simplified the recycling scheme into an empty statement <wink>.

Although I'd declare arenas as volatile...

Why? Thread problems aren't solved by superstition, and that's what adding "volatile" *usually* is. It's generally no more of a cure than adding a sleep(). More on that in my reply to Guido.

Guido van Rossum writes:

How about if the PyMem_Free guy saved the address of the vector before using it, and checked that it was still the same afterwards, *and* if the PyMem_Malloc guy didn't use realloc to resize the vector but copied it to a newly malloc'ed vector, stored the new vector's address, and then freed the old vector?

That doesn't really help. The code currently does ((I) < narenas && (uptr)(P) - arenas[I] < (uptr)ARENA_SIZE) So if the PyMem_Free thread blocks (yields by OS command) after fetching arenas, but before fetching arenas[i], then the PyMem_Malloc thread could still free the memory under it. Regards, Martin

[Guido]

On the other hand, the less sophisticated extension writers never release the GIL at all.

That's an excellent point! I don't know how much to bank it, but it's semi-reassuring.

All I can do is encourage you to keep trying. I find it quite encouraging that you found a constant-time test for non-arena memory at all.

David Abrahams had the key insight there. Those C++ guys really do have some good ideas, if you can whittle away all the baffling syntax to get at the pure tiny thoughts they're thinking <wink>.

Making it thread-safe should only add a tiny constant time.

It does now, although it's balancing on a nanometer pinhead. That's good enough so long as nobody sneezes in the general direction of the code.

[martin@v.loewis.de]

I would not like to see such a binary search performed.

Instead, if anything needs to be done, I'd be in favour of using a constant-time algorithm, even if it means that a littler more memory overhead is necessary.

I have the following idea: each chunk allocated by ought ^ Allocated by what? Some crucial words are missing here. Note that I am *not* proposing to change PyMem_{MALLOC, Malloc): that continues to map

Duh <wink>. directly to system malloc(), so we have no control over, nor even knowledge of, the memory allocated by PyMem_{MALLOC, Malloc}. We can't redirect those to pymalloc's malloc without introducing locks to prevent multithreaded insanity, or "declaring by fiat" that existing working code is now horribly broken in ways we can't help users detect.

to have a pointer to its pool, immediately preceding the memory block.

In what fundamental way does this differ from pymalloc's current scheme of storing the pool address at an address calculated *from* the pointer address? I suspect the real difference resides in the next point:

This will make an overhead of 4 bytes per allocation. Chunks allocated by the system allocator will have a null pointer preceding them.

That's the killer. We have no control over "the system allocator", by which I mean libc's malloc() and realloc(). As above, trying to hijack them is unattractive due to thread issues, even for just the PyMem_{Malloc, MALLOC, Realloc, REALLOC, New, NEW, Resize, RESIZE} spellings.

To deal with alignment, the size classes would increase each by 4 bytes, so they would be spaced at 12, 20, 28, etc. bytes. With the 4 byte overallocation, each chunk would be 8-aligned, if the previous chunk in the same pool is.

*If* we take over the system malloc, we need also to mimic the platform malloc's alignment. Pymalloc's object allocator can get away with 8-byte alignment because the core never requires worse-than-double alignment, and I'm willing to say that this is a language implementation restriction. I don't believe we can also restrict PyMem_umpteen_ways_to_spell_get_memory that way: they have always given platform-malloc alignment. If we could, I agree your scheme is fine, although I'm not sure why it stores a whole pointer when it's making a 1-bit distinction ("does or does not reside in a pymalloc pool").

This approach would allow to remove the requirement that each pool must be 4k-aligned.

OK, that's why it really stores a whole pointer. Agreed then, but the memory lost to achieve page alignment once per-arena is likely small compared to adding 4 bytes to every allocation unit. The former loses at most 4KB per 256KB.

To support the NULL pointer in a system-malloc'ed chunk, pymalloc would overallocate 8 bytes if it defers to system malloc, to preserve alignment.

What do you think?

Primarily that hijacking the system malloc is fraught with new difficulties. If we *can* hijack it, so that pymalloc's free always knows that addresses passed to it came from pymalloc's malloc/realloc originally, then I agree it's easy to do something cheap to distinguish pool from non-pool memory. The scheme I sketched is as hairy as it is exactly because it does the right thing even when freeing an address obtained directly from the platform malloc/realloc.

[Tim]

...

Note that I am *not* proposing to change PyMem_{MALLOC, Malloc)

[martin@v.loewis.de]

I understand that (I think). Neither do I.

I think you have to under this scheme, although I'm not clear on what "the problem" is you're trying to solve. I'm trying to cater to allocating via PyMem_{MALLOC, Malloc} then free'ing via _PyMalloc_Free. That latter is because mixing PyObject_New with PyMem_{DEL, FREE, Del, Free} is frequent in real-life code now. If Guido is to get his wish that we keep the PyObject_XXX interface and not introduce a new PyMalloc_XXX object interface, and I'm to get my wish that we don't break mountains of existing works-fine code, that means PyObject_XXX *and* PyMem_{DEL, FREE, Del, Free} have to funnel thru the pymalloc package. Else existing "get object" and "free object" mixtures will break. That in turn means memory allocated by PyMem_{Malloc, MALLOC, Realloc, REALLOC, Resize, RESIZE, New, NEW} *also* has to be suitable for feeding into pymalloc's free. But I'm not proposing to change PyMem_{Malloc, MALLOC, Realloc, REALLOC, Resize, RESIZE, New, NEW} at all, meaning they'll continue to call platform malloc() and realloc() directly without any tricky wrappers.

...

That's the killer. We have no control over "the system allocator", by which I mean libc's malloc() and realloc().

We sure do. In _PyMalloc_Malloc, replace the line

This can't affect anything obtained via PyMem_{MALLOC, Malloc}, because they call the platform malloc() directly. We don't "wrap" them in any significant way.

return (void *)PyMem_MALLOC(nbytes);

with

void **result;

result = (void**)PyMem_MALLOC(nbytes+8); result[1] = NULL; return (result+2);

Yes, _PyMalloc_Malloc can do anything at all, but PyMem_{MALLOC, Malloc} don't go thru this code.

Likewise, replace

offset = (off_t )p & POOL_SIZE_MASK; pool = (poolp )((block *)p - offset); if (pool->pooladdr != pool || pool->magic != (uint )POOL_MAGIC) { PyMem_FREE(p); return; }

with

void **block = (void**)p; if(block[-1] == NULL){ PyMem_FREE(block-2); return; }

Something allocated via PyMem_{MALLOC, Malloc} that goes through this code will read random gibberish (or carefully constructed hostile gibberish) at block[-1]. So it's not safe for what I'm trying to accomplish.

...

As above, trying to hijack them is unattractive due to thread issues, even for just the PyMem_{Malloc, MALLOC, Realloc, REALLOC, New, NEW, Resize, RESIZE} spellings.

I can't see how this approach would add thread issues.

That's because it seems you're not trying to make PyMem_{MALLOC, Malloc} safe for mixed use at all. If you did, I suppose they could funnel through a wrapper other than _PyMalloc_Malloc (at the cost of other complications).

...

*If* we take over the system malloc, we need also to mimic the platform malloc's alignment.

I'm not sure what you mean by "take over".

I mean stop PyMem_XXX from calling platform malloc/realloc/free directly, so that they can be made safe for mixing with _PyMalloc_Free.

It will still be used as an allocator for arenas, and for large requests.

... Indeed, this approach might be slightly more expensive. In return, it is safe and (time-)efficient.

It's safe under some set of assumptions I'm not sure about, but not safe enough under the assumptions I am sure about <wink>.

...

Primarily that hijacking the system malloc is fraught with new difficulties.

That might be, but I'm not proposing this (or I don't understand the work "hijacking").

It means "take over" <wink>. If a scheme can't handle free'ing memory safely when that memory was returned directly from the platform malloc/realloc, it can't handle the sum of the things Guido and I want here (he's keener to preserve PyObject_XXX; I'm keener not to break existing code, even code that doesn't play by what some subset of Python-Dev'vers thinks might be "the rules").

... That safe-guard isn't needed, IMO. Returning memory allocated directly through malloc (and not via _PyMalloc_Malloc) to _PyMalloc_Free is clearly a bug,

Then you either have to change PyMem_{Malloc, MALLOC, etc etc etc} too, or you have to tell extension authors that every extension type they wrote for 1.5.2 will now fail in horrible ways (data-dependent and intermittent segfaults, data corruption, etc), and tell users that every "old" extension they pick up on the web may suffer such problems too even if it compiles cleanly for 2.3.

and there are more efficient ways to detect this kind of bug (like your pymalloc debug mechanism). In addition, there are so many other kinds of bugs that this doesn't protect against (like not taking the GC header into account when releasing memory) that this alone isn't convincing.

The difference is that I don't consider mixing PyObject_XXX with PyMem_XXX to be "a bug". In 1.5.2 such mixing was necessary, and still works fine in 2.2. I worry about extension authors who *do* bother to fix code that works fine <wink>.

[Tim]

I'm trying to cater to allocating via PyMem_{MALLOC, Malloc} then free'ing via _PyMalloc_Free.

[Martin]

Is *that* the motivation?

One of them.

I thought you were trying to accommodate your killer.py where Python code can trick pymalloc into believing that it owned the memory which it actually had allocated by forwarding to system malloc

That's another one. There are only two, so we can stop now <wink>.

(see the subject).

That came from the first msg in the thread. The second msg in the thread came a couple days later, and broadened the scope at its start: http://mail.python.org/pipermail/python-dev/2002-March/021905.html It was too easy to *just* fix killer.py <wink>.

----- Original Message ----- From: "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

Fine so far...

, and see whether B <= p < B + 256KB (which can again be collapsed into a tricksy one-compare test via exploiting unsigned arithmetic).

...isn't this part just a little too complicated? If I understand correctly, arenas are 4K aligned pages. Given an address, when you find its pool header, you either find a valid arena header that covers all 4K subsequent addresses, or some alien memory. I think you just have to look for the address of the pool header at the appropriate index in the vector. IOW, there should be no need to look at the address you're deallocating after finding its putative arena. -Dave

----- Original Message ----- From: "Martin v. Loewis"

"David Abrahams" writes:

...

...isn't this part just a little too complicated? If I understand correctly, arenas are 4K aligned pages.

No, arenas are 256k areas which are split into 4k pools.

...

Given an address, when you find its pool header, you either find a valid arena header that covers all 4K subsequent addresses, or some alien memory. I think you just have to look for the address of the pool header at the appropriate index in the vector. IOW, there should be no need to look at the address you're deallocating after finding its putative arena.

The pool in question and the arena it belongs to may have different starting addresses (in 63 of 64 cases, they will be different).

Of course, you could also build the table for pool addresses, assigning pool indices - but that would require 64 times as much memory.

OK, but I guess my question still holds: can't you just round down to find a supposed arena address, look up the index, and see if that arena is in the vector? -Dave

[David Abrahams]

OK, but I guess my question still holds: can't you just round down to find a supposed arena address,

No, and this is the point at which you get stuck. The arena base address is whatever the heck libc malloc returned when we asked for 256KB. There's no way to deduce that from the addresses *within* the arena.

look up the index, and see if that arena is in the vector?

It would be possible to store both the arena index *and* the arena base address in each pool header. Then we could check that poolheader* p = pool_address(some_memory_address); if (p->arenaindex < narenas && arenas[p->arenaindex] == p->arenabase) { it's a pymalloc address } else { it isn't } I like that. Thanks!

[martin@v.loewis.de]

... The pool in question and the arena it belongs to may have different starting addresses (in 63 of 64 cases, they will be different).

Currently, they always have different addresses, as at least the first 4 bytes of an arena are used to link arenas together. If we save the arena base addresses in a vector instead, the link becomes unnecessary (well, it's not actually *used* for anything now anyway), and then the arena-rounding logic can be changed so that the first pool can coincide with the arena start if malloc just happens to return a page-aligned address for the arena (as the code is now, in that case the entire first page is devoted to holding s next-arena pointer).

Of course, you could also build the table for pool addresses, assigning pool indices - but that would require 64 times as much memory.

Bingo -- I don't want to do that.

Arenas are 256KB chunks with no known alignment. They're carved into 4KB-aligned pages (also called "pools") of 4KB each. Some number of

From: "Tim Peters" the

leading and trailing memory addresses in an arena are sacrificed to get page alignment in the smaller pieces (pools/pages). A given pool is in turn carved into some number of continguous, equal-sized, 8-byte aligned small blocks.

Okay, 'nuf said. I see why you need to do it that way, now. -Dave

[martin@v.loewis.de]

This sounds quite good. The only flaw is that you need to trust that the machine has paged memory - otherwise, rounding down an arbitrary address to a 4k boundary, and then reading a value may cause an access violation (or may, say, fetch data from some peripheral device, thus starting the coffee machine :-).

pymalloc always relied on that assumption, so that part isn't new.

For the architectures we care about, this seems to be guaranteed; on other architectures, people will need to disable pymalloc.

Either that or buy a reasonable machine <wink>. A fair number of people have tried pymalloc by now, and nobody has reported a problem. I suppose they may have been lucky, and that feeding PyMem_{FREE, Free, DEL, Del} into PyMalloc_Free too may greatly strain their luck if so.