Writing in freed memory in _PyMem_DebugRawRealloc() after shrinking a memory block

[serhiy-storchaka]

BPO	31626
Nosy	@vstinner, @larryhastings, @skrah, @xdegaye, @serhiy-storchaka, @applio
PRs	bpo-31626: Fixed a bug in debug memory allocator. #3844 [WIP] bpo-31626: Rewrite _PyMem_DebugRawRealloc() #3898 bpo-31626: Fix _PyMem_DebugRawRealloc() on OpenBSD #4119 [3.6] bpo-31626: Fixed a bug in debug memory allocator. (GH-3844) #4191 bpo-31626: Mark ends of the reallocated block in debug build. #4210 bpo-31626: Fix _PyObject_DebugReallocApi() #4310
Files	debug-realloc.diff

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2017-11-24.11:08:20.926>
created_at = <Date 2017-09-29.06:29:10.376>
labels = ['interpreter-core', '3.7', 'type-crash']
title = 'Writing in freed memory in _PyMem_DebugRawRealloc() after shrinking a memory block'
updated_at = <Date 2017-11-24.11:57:24.033>
user = 'https://github.com/serhiy-storchaka'

bugs.python.org fields:

activity = <Date 2017-11-24.11:57:24.033>
actor = 'serhiy.storchaka'
assignee = 'none'
closed = True
closed_date = <Date 2017-11-24.11:08:20.926>
closer = 'vstinner'
components = ['Interpreter Core']
creation = <Date 2017-09-29.06:29:10.376>
creator = 'serhiy.storchaka'
dependencies = []
files = ['47249']
hgrepos = []
issue_num = 31626
keywords = ['patch']
message_count = 30.0
messages = ['303302', '303307', '303457', '303460', '304752', '304987', '304988', '304991', '304992', '304993', '304998', '305041', '305043', '305060', '305162', '305163', '305291', '305296', '305332', '305334', '305349', '305736', '305737', '305738', '305743', '306866', '306867', '306877', '306887', '306891']
nosy_count = 6.0
nosy_names = ['vstinner', 'larry', 'skrah', 'xdegaye', 'serhiy.storchaka', 'davin']
pr_nums = ['3844', '3898', '4119', '4191', '4210', '4310']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue31626'
versions = ['Python 2.7', 'Python 3.6', 'Python 3.7']

[serhiy-storchaka]

I tried to build CPython on 64-bit OpenBSD. It was built successfully, but tests crash. They crash on importing hashlib. Actually on compiling hashlib docstring. Minimal reproducer is:

$ ./python -c 'import codecs; codecs.decode(r"\\"*15 + "x"*1906, "unicode-escape")'                  
assertion "maxchar < 128" failed: file "Objects/unicodeobject.c", line 474, function "_PyUnicode_CheckConsistency"
Abort trap (core dumped) 

_PyUnicodeWriter_Finish() calls resize_compact() for truncating the result, but the latter fills the last 15 bytes with \xdb. Since the string is tagged as ASCII, thus crashing in _PyUnicode_CheckConsistency.

[vstinner]

"_PyUnicodeWriter_Finish() calls resize_compact() for truncating the result, but the latter fills the last 15 bytes with \xdb. Since the string is tagged as ASCII, thus crashing in _PyUnicode_CheckConsistency."

Cool. My code works as expected to catch bugs :-)

[serhiy-storchaka]

There several bugs in the memory allocator.

Incorrectly detected the case when realloc() resizes a memory block in-place. Wrong address is used for filling the extra memory with DEADBYTE.

-    if (q == oldq && nbytes < original_nbytes) {
+    if (q == oldq - 2*SST && nbytes < original_nbytes) {
         /* shrinking:  mark old extra memory dead */
-        memset(q + nbytes, DEADBYTE, original_nbytes - nbytes);
+        memset(q + 2*SST + nbytes, DEADBYTE, original_nbytes - nbytes);
     }

But fixing this exposes other problem. _PyMem_DebugRawRealloc() is called recursively. _PyMem_DebugRawRealloc calls api->alloc.realloc which is _PyMem_DebugRawRealloc. There are two nested debug allocators. The block is nested in other block, both have their own header and footer.

|header1|header2|------------------------------|footer2|footer1|

_PyMem_DebugRawRealloc fills the extra memory with DEADBYTE.

|header|---------------------------..unused..|footer|
|header|---------------------------|footer|XXXXXXXXX|

But in case of nested _PyMem_DebugRawRealloc's, the outer one (which reallocates the inner block), overwrites the footer of the outer block.

|header1|header2|--------------------..unused..|footer2|footer1|
|header1|header2|--------------------..unused|footer1|XXXXXXXXX| after inner realloc
|header1|header2|--------------------|footer2|YYYYYYYYY|XXXXXXX| after outher realloc

XXX are DEADBYTEs written by the inner allocator, YYY are DEADBYTEs written by the outer allocator.

[serhiy-storchaka]

Using nested _PyMem_DebugRawRealloc() looks suspicions to me. This may be a bug.

But even without nested _PyMem_DebugRawRealloc() writing to the extra memory after using realloc() looks wrong to me. This can break other non-trivial system allocators which write an information past the allocated block. This can cause a segfault if unused memory pages are returned to OS.

After creating the PR I have found that it literally restores the code of 2.7 and 3.3. 3.4 and later contain this bug. The bug looks enough serious to me for fixing it in 3.4 and 3.5.

[serhiy-storchaka]

Ping.

[vstinner]

Using nested _PyMem_DebugRawRealloc() looks suspicions to me. This may be a bug.

PyObject_Malloc() calls PyMem_RawMalloc() for allocations larger than 512 bytes.

When debug hooks are enabled, PyObject_Malloc() and PyMem_RawMalloc() both call _PyMem_DebugRawRealloc(). The behaviour that you saw is expected.

It was simpler to reuse _PyMem_DebugRawRealloc() PyObject and PyMem_Raw allocator families, rather than duplicating the code.

[vstinner]

"I tried to build CPython on 64-bit OpenBSD. It was built successfully, but tests crash."

It's the first time that anyone complains about _PyMem_DebugRawRealloc(). The behaviour seems to be very specific to OpenBSD.

Even if the current code is "weird", it works very well and is effecient.

I proposed attached PR 4119 which makes _PyMem_DebugRawRealloc() behaves correctly: erase bytes *before* calling realloc(), but keeps a copy if realloc() fails. My PR only changes the behaviour on OpenBSD. It keeps the current behaviour (erase bytes *after* realloc, if realloc succeeded) on other platforms for performance reasons.

[serhiy-storchaka]

The current code in not correct on all platforms. We don't know how many of random bugs, hangs and crashes on other platforms are caused by this bug. I'm not surprised that it was caught on OpenBSD since the robustness and security of software is the goal of OpenBSD.

PR 3844 restores the behavior of 2.7 and 3.3. I propose to merge it first, and develop other enhancements later.

[vstinner]

PR 3844 restores the behavior of 2.7 and 3.3. I propose to merge it first, and develop other enhancements later.

Please don't. This PR reintroduced a bug that I fixed in bpo-18408:

commit c426636
Author: Victor Stinner <victor.stinner@gmail.com>
Date: Tue Jul 9 00:44:43 2013 +0200

Issue bpo-18408: Fix _PyMem_DebugRealloc()

Don't mark old extra memory dead before calling realloc(). realloc() can fail
and realloc() must not touch the original buffer on failure.

So mark old extra memory dead only on success if the new buffer did not move
(has the same address).

[vstinner]

The current code in not correct on all platforms.

My PR 4119 only changes the behaviour on OpenBSD, but I'm not sure about that. Maybe it's simpler to apply this fix on all platforms, as I asked on the PR itself?

[serhiy-storchaka]

In this case it would be safe to not erase bytes at all.

PR 4119 is too complex for a bugfix (especially if backport it to 3.5 and 3.4). It can introduce other regressions. The performance hit is not the only issue. Allocating a temporary buffer can change the structure of "holes" in memory. As result some memory related bugs can be reproducible only in release mode.

Maybe it is enough to erase only few bytes at the start and end of the freed area. The copy can be saved in local variables, without involving the heap. This solution still will be enough complex, and I think it can be applied only to 3.7. But the bug should be fixed in all affected versions.