Neal Norwitz schrieb:

at 0x44FA06: Py_ADDRESS_IN_RANGE (obmalloc.c:1741)

Note that the free is inside qsort. The memory freed under qsort should definitely not be the bases which we allocated under PyType_Ready. I'll file a bug report with valgrind to help determine if this is a problem in Python or valgrind. http://bugs.kde.org/show_bug.cgi?id=136989

As Tim explains, a read from Py_ADDRESS_IN_RANGE is fine, and by design. If p is the pointer, we do

pool = ((poolp)((Py_uintptr_t)(p) & ~(Py_uintptr_t)((4 * 1024) - 1)));

i.e. round down p to the start of the page, to obtain "pool". Then we do

f (((pool)->arenaindex < maxarenas && (Py_uintptr_t)(p) - arenas[(pool)->arenaindex].address < (Py_uintptr_t)(256 << 10) && arenas[(pool)->arenaindex].address != 0))

i.e. access pool->arenaindex. If this is our own memory, we really find a valid arena index there. If this is malloc'ed memory, we read garbage - due to the page size, we are guaranteed to read successfully, still. To determine whether it's garbage, we look it up in the arenas array.

One other thing that is weird is that the complaint is about 4 bytes which should not be possible. All pointers should be 8 bytes AFAIK since this is amd64.

That's because the arenaindex is unsigned int. We could widen it to size_t, if we don't, PyMalloc can "only" manage 1 PiB (with an arena being 256kiB, and 4Gi arena indices being available).

I also ran this on x86. There were 32 errors and all of their addresses were 0x4...010.

That's because we round down to the beginning of the page.

Regards, Martin

[Herman Geza]

...

Here python reads from an already-freed memory area, right?

[Martin v. Löwis]

It looks like it, yes. Of course, it could be a flaw in valgrind, too. To find out, one would have to understand what the memory block is, and what part of PyObject_Free accesses it.

When PyObject_Free is handed an address it doesn't control, the "arena base address" it derives from that address may point at anything the system malloc controls, including uninitialized memory, memory the system malloc has allocated to something, memory the system malloc has freed, or internal system malloc bookkeeping bytes. The Py_ADDRESS_IN_RANGE macro has no way to know before reading it up.

So figure out which line of code valgrind is complaining about (doesn't valgrind usually produce that?). If it's coming from the expansion of Py_ADDRESS_IN_RANGE, it's not worth more thought.

Herman Geza schrieb:

...

So figure out which line of code valgrind is complaining about (doesn't valgrind usually produce that?). If it's coming from the expansion of Py_ADDRESS_IN_RANGE, it's not worth more thought.

Hmm. I don't think that way. What if free() does other things?

It can't, as the hardware won't support it.

For example if free(addr) sees that the memory block at addr is the last block then it may call brk with a decreased end_data_segment.

It can't. In brk, you can only manage memory in chunks of "one page" (i.e. 4kiB on x86). Since we only access memory on the same page, access is guaranteed to succeed.

Or the last block in an mmap'd area - it calls unmap. So when Py_ADDRESS_IN_RANGE tries to read from this freed memory block it gets SIGSEGV. However, I've never got SIGSEGV from python.

Likewise. This is guaranteed to work, by the processor manufacturers.

I don't really think that reading from an already-freed block is ever legal.

Define "legal". There is no law against it; you don't go to jail for doing it. What other penalties would you expect (other than valgrind spitting out error messages, and users complaining from time to time that it's "illegal")?

I asked my original question because I saw that I'm not the only one who sees "Illegal reads" from python. Is valgrind wrong in this case?

If it is this case, then no, valgrind is right. Notice that valgrind doesn't call them "illegal"; it calls them "invalid".

I just want to be sure that I'll never get SIGSEGV from python.

You least won't get SIGSEGVs from that part of the code.

Note that Misc/valgrind-python.supp contains suppressions "Invalid read"'s at Py_ADDRESS_IN_RANGE.

Right. This is to tell valgrind that these reads are known to work as designed.

Regards, Martin

Herman Geza schrieb:

...

It can't. In brk, you can only manage memory in chunks of "one page" (i.e. 4kiB on x86). Since we only access memory on the same page, access is guaranteed to succeed.

Yes, I'm aware of it. But logically, it is possible, isn't it?

No, it isn't.

At malloc(), libc recognizes that brk needed, it calls sbrk(4096). Suppose that python releases this very same block immediately. At free(), libc recognizes that sbrk(-4096) could be executed, so the freed block not available anymore (even for reading)

That can't happen for a different reason. When this access occurs, we still have a pointer to allocated memory (either allocated through malloc, or obmalloc - we don't know at the pointer where the access is made). The access is "invalid" only if the memory was allocated through malloc. So when the access is made, we have a pointer p, which is allocated through malloc, and access p-3000 (say, assuming that p-3000 is a page boundary). Since p is still allocated, libc *cannot* have made sbrk(p-3000), since that would have released the still-allocated block.

...

...

Or the last block in an mmap'd area - it calls unmap. So when Py_ADDRESS_IN_RANGE tries to read from this freed memory block it gets SIGSEGV. However, I've never got SIGSEGV from python.

Likewise. This is guaranteed to work, by the processor manufacturers.

The same: if the freed block is the last one in the mmap'd area, libc may unmap it, doesn't it?

But it isn't. We still have an allocated block of memory on the same page. The C library can't have released it.

...

...

I just want to be sure that I'll never get SIGSEGV from python.

You least won't get SIGSEGVs from that part of the code.

That's what I still don't understand. If valgrind is right then how can python be sure that it can still reach a freed block?

valgrind knows the block is released. We know that the block is still "mapped" to memory by the operating system. These are different properties. To write to memory, you better have allocated it. To read from memory, it ought to be mapped (in most applications, it is also an error to read from released memory, even if the read operation succeeds; valgrind reports this error as "invalid read").

...

...

Note that Misc/valgrind-python.supp contains suppressions "Invalid read"'s at Py_ADDRESS_IN_RANGE.

Right. This is to tell valgrind that these reads are known to work as designed.

Does this mean that python strongly depends on libc?

No. It strongly depends on a lower estimate of the page size, and that memory is mapped on page boundaries.

If I want to port python to another platform which uses a totally different malloc, is Py_ADDRESS_IN_RANGE guaranteed to work or do I have to make some changes?

It's rather unimportant how malloc is implemented. The real question is whether you have a flat address space (Python likely won't work at all if you don't have a flat address space), and whether the system either doesn't have virtual memory, or, if it does, whether obmalloc's guess of the page size is either right or an underestimation. If some constraints fail, you can't use obmalloc (you could still port Python, to not use obmalloc).

Notice that on a system with limited memory, you probably don't want to use obmalloc, even if it worked. obmalloc uses arenas of 256kiB, which might be expensive on the target system.

Out of curiosity: what is your target system?

Regards, Martin

[Martin v. Löwis]

Thanks for explaining all this! One counterpoint:

Notice that on a system with limited memory, you probably don't want to use obmalloc, even if it worked. obmalloc uses arenas of 256kiB, which might be expensive on the target system.

OTOH, Python allocates a lot of small objects, and one of the reasons for obmalloc's existence is that it typically uses memory more efficiently (less bookkeeping space overhead and less fragmentation) for mounds of small objects than the all-purpose system malloc.

In a current (trunk) debug build, simply starting Python hits an arena highwater mark of 9, and doing "python -S" instead hits a highwater mark of 2. Given how much memory Python needs to do nothing ;-), it's doubtful that the system malloc would be doing better.