[Python-Dev] Improving the Python Memory Allocator

[Evan Jones]

On Jan 24, 2005, at 18:16, Martin v. Löwis wrote:
> - please don't post patches here; post them to SF
>   You may ask for comments here after you posted them to SF.

Sure. This should be done even for patches which should absolutely not 
be committed?

> - please follow Python coding style. In particular, don't write
>     if ( available_arenas == NULL ) {
>   but write
>     if (available_arenas == NULL) {

Yikes! This is a "bad" habit of mine that is in the minority of coding 
style . Thank you for catching it.

>> Second, the previous allocator went out of its way to permit a module 
>> to call PyObject_Free while another thread is executing 
>> PyObject_Malloc. Apparently, this was a backwards compatibility hack 
>> for old Python modules which erroneously call these functions without 
>> holding the GIL. These modules will have to be fixed if this 
>> implementation is accepted into the core.
> I'm not certain it is acceptable to make this assumption. Why is it
> not possible to use the same approach that was previously used (i.e.
> leak the arenas array)?

This is definitely a very important point of discussion. The main 
problem is that leaking the "arenas" arena is not sufficient to make 
the memory allocator thread safe. Back in October, Tim Peters suggested 
that it might be possible to make the breakage easily detectable:

http://mail.python.org/pipermail/python-dev/2004-October/049502.html

> If we changed PyMem_{Free, FREE, Del, DEL} to map to the system
> free(), all would be golden (except for broken old code mixing
> PyObject_ with PyMem_ calls).  If any such broken code still exists,
> that remapping would lead to dramatic failures, easy to reproduce; and
> old code broken in the other, infinitely more subtle way (calling
> PyMem_{Free, FREE, Del, DEL} when not holding the GIL) would continue
> to work fine.

I'll be honest, I only have a theoretical understanding of why this 
support is necessary, or why it is currently correct. For example, is 
it possible to call PyMem_Free from two threads simultaneously? Since 
the problem is that threads could call PyMem_Free without holding the 
GIL, it seems to be that it is possible. Shouldn't it also be 
supported? In the current memory allocator, I believe that situation 
can lead to inconsistent state. For example, see obmalloc.c:746, where 
it has been determined that a block needs to be put on the list of free 
blocks:

		*(block **)p = lastfree = pool->freeblock;
		pool->freeblock = (block *)p;

Imagine two threads are simultaneously freeing blocks that belong to 
the same pool. They both read the same value for pool->freeblock, and 
assign that same value to p. The changes to pool->freeblock will have 
some arbitrary ordering. The result? You have just leaked a block of 
memory.

Basically, if a concurrent memory allocator is the requirement, then I 
think some other approach is necessary.

>> - When allocating a page, it is taken from the arena that is the most 
>> full. This gives arenas that are almost completely unused a chance to 
>> be freed.
> It would be helpful if that was documented in the data structures
> somewhere. The fact that the nextarena list is sorted by nfreepools
> is only mentioned in the place where this property is preserved;
> it should be mentioned in the introductory comments as well.

This is one of those rough edges I mentioned before. If there is some 
concensus that these changes should be accepted, then I will need to 
severely edit the comments at the beginning of obmalloc.c.

Thanks for your feedback,

Evan Jones