Unbounded memory growth resizing split-table dicts

[minrk]

BPO	28147
Nosy	@vstinner, @larryhastings, @ned-deily, @methane, @berkerpeksag, @serhiy-storchaka, @minrk, @jamadden, @zhangyangyu
PRs	[Do Not Merge] Convert Misc/NEWS so that it is managed by towncrier #552
Files	test-dict-pop.py: test illustrating dict resize memory leak 0001-Avoid-unbounded-growth-in-dict_resize.patch: patch to fix memory growth with regression test fix-28147.patch fix-28147.patch: Add missing file fix-28147-py35.patch fix28147-py36.patch fix28147-py36-2.patch fix28147-py36-3.patch fix28147-comment-update.patch fix-28147-py35-2.patch

^{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 2016-12-20.01:05:08.308>
created_at = <Date 2016-09-14.11:44:13.094>
labels = ['interpreter-core', 'deferred-blocker', '3.7', 'type-crash']
title = 'Unbounded memory growth resizing split-table dicts'
updated_at = <Date 2017-03-31.16:36:26.473>
user = 'https://github.com/minrk'

bugs.python.org fields:

activity = <Date 2017-03-31.16:36:26.473>
actor = 'dstufft'
assignee = 'none'
closed = True
closed_date = <Date 2016-12-20.01:05:08.308>
closer = 'methane'
components = ['Interpreter Core']
creation = <Date 2016-09-14.11:44:13.094>
creator = 'minrk'
dependencies = []
files = ['44658', '44659', '44665', '44666', '44696', '45796', '45797', '45910', '45911', '45968']
hgrepos = []
issue_num = 28147
keywords = ['patch']
message_count = 51.0
messages = ['276418', '276419', '276420', '276425', '276428', '276434', '276437', '276450', '276451', '276452', '276456', '276477', '276481', '276482', '276483', '276502', '276726', '276895', '276901', '276947', '277614', '282635', '282642', '282643', '282648', '282650', '282672', '282682', '282683', '282699', '282702', '282743', '283246', '283259', '283264', '283267', '283268', '283270', '283283', '283334', '283335', '283337', '283339', '283374', '283386', '283392', '283395', '283468', '283478', '283644', '283659']
nosy_count = 11.0
nosy_names = ['vstinner', 'larry', 'ned.deily', 'methane', 'python-dev', 'berker.peksag', 'serhiy.storchaka', 'minrk', 'jmadden', 'xiang.zhang', 'wenzel']
pr_nums = ['552']
priority = 'deferred blocker'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue28147'
versions = ['Python 3.5', 'Python 3.6', 'Python 3.7']

[minrk]

There is a memory leak in the new dictionary resizing in 3.6, which can cause memory exhaustion in just a few iterations.

I don't fully understand the details of the bug, but it happens when resizing a dict with a split table several times. The only way that I have found to trigger this is by popping items off of an object's __dict__ repeatedly.

I've attached a script to illustrate the issue. Be careful with it, because it will eat up all your memory if you don't interrupt it.

[minrk]

This patch fixes the memory leak in split-dict resizing.

Each time dict_resize is called, it gets a new, larger size > minused. If this is triggered many times, it will keep growing in size by a factor of two each time, as the previous size is passed as minused for the next call.

Set the lower bound at minused (inclusive), rather than exclusive, so that the size does not continue to increase for repeated calls.

A test is added to test_dict.py based on the earlier test script, but if someone has a simpler way to trigger the split-dict resize events, I'd be happy to see it.

[berkerpeksag]

Can you wrap the test with @support.cpython_only decorator? The patch fixes the memory leak demonstrated in test-dict-pop.py.

[minrk]

I can add the cpython_only decorator, but I'm not sure it is the right thing to do. I would expect the code in the test to pass on any Python implementation, which would suggest that it should not be cpython_only, right? If you still think so, I'll add it.

[methane]

I don't understand the leak yet.

Each time dict_resize is called, it gets a new, larger size > minused. If this is triggered many times, it will keep growing in size by a factor of two each time, as the previous size is passed as minused for the next call.

dictresize() is called for converting split table to combined table.
How is it triggered many times?

In your test code, which loop cause leak? new instance loop or re-use instance loop?

[vstinner]

The CPython test suite uses a counter on memory allocations. Please add an unit test which triggers the memory leak, but you don't need many iterations. One iteartion should be enough to be catched by the unit test. Try: ./python -m test -R 3:3 test_dict.

The memory allocation counter:
https://docs.python.org/dev/library/sys.html#sys.getallocatedblocks

Note: The tracemalloc module can also be used to track memory leak, but it's harder to use it to write unit tests because Python uses a lot of internal caches and tracemalloc really tracks every single bytes.

[methane]

Ah, is the leak happen in 3.6b1?
dict.pop() in 3.6b1 doesn't combine split table. It was a bug and
fixed in master branch already.

Regardless the leak, I agree that grow dict when popping is bad idea.
I'll improve your patch.

[minrk]

dictresize() is called for converting split table to combined table.
How is it triggered many times?

every self.__dict__.pop triggers a resize. According to https://www.python.org/dev/peps/pep-0412/#split-table-dictionaries obj.__dict__ is always a split-table dict. I do not understand the dict implementation enough to say precisely why, but pop forces a recombine via resize because split-table dicts don't support deletion. In dict_resize, due to a <=minused condition, the size is guaranteed to at least double every time dict_resize is called. It would appear that after this, __dict__ is again forced to be a split-table dict, though I'm not sure how or where this happens, but good old-fashioned printf debugging shows that dict_resize is called for every __dict__.pop because _PyDict_HasSplitTable is true every time pop is called.

In your test code, which loop cause leak? new instance loop or re-use instance loop?

Both loops cause the leak. If the pop_attr() is not in __init__, then only the re-used instance has the leak. if pop_attr is in __init__, then it happens across instances as well. I will try to add more comments in the code to make this clearer.

Does anyone have a handy way to create a split-table dict other than on obj.__dict__?

Please add an unit test which triggers the memory leak

I should not have used the term memory leak, and have updated the title to be more precise. It is not memory allocated without a corresponding free, instead it is unbounded growth of the memory owned by a split-table dict. Cleaning up the object does indeed clean up the memory associated with it. The included test exercises the bug with several iterations. Running the test several times with only one iteration would not exercise the bug.

[vstinner]

According to https://www.python.org/dev/peps/pep-0412/#split-table-dictionaries obj.__dict__ is always a split-table dict.

Hum, this PEP is now probably outdated since Python 3.6 beta 1 :-)

[minrk]

Ah, is the leak happen in 3.6b1?

The leak happens in 3.6b1 and master as of an hour ago (git: 3c06edf, hg:r103797)