GeezerVison is showing github.com — Memory leak in Modules/sre_lib.h · Issue #67877 · python/cpython
Memory leak in Modules/sre_lib.h #67877Description
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 = 'https://github.com/serhiy-storchaka'
closed_at = <Date 2022-04-03.16:21:31.788>
created_at = <Date 2015-03-17.16:56:20.153>
labels = ['expert-regex', '3.11', 'performance']
title = 'Memory leak in Modules/sre_lib.h'
updated_at = <Date 2022-04-03.16:21:31.787>
user = 'https://bugs.python.org/abacabadabacaba' bugs.python.org fields:
activity = <Date 2022-04-03.16:21:31.787>
actor = 'serhiy.storchaka'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2022-04-03.16:21:31.788>
closer = 'serhiy.storchaka'
components = ['Regular Expressions']
creation = <Date 2015-03-17.16:56:20.153>
creator = 'abacabadabacaba'
dependencies = []
files = ['38529']
hgrepos = []
issue_num = 23689
keywords = ['patch']
message_count = 13.0
messages = ['238313', '238320', '238324', '238326', '238328', '238343', '238388', '335889', '337113', '416266', '416269', '416630', '416631']
nosy_count = 7.0
nosy_names = ['vstinner', 'ezio.melotti', 'mrabarnett', 'abacabadabacaba', 'serhiy.storchaka', 'malin', 'alexei.romanov']
pr_nums = ['11926', '12160', '32188', '32223', '32283']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'resource usage'
url = 'https://bugs.python.org/issue23689'
versions = ['Python 3.11'] Linked PRs
Activityabacabadabacaba commented on Mar 17, 2015 MannequinAuthor More actions vstinner commented on Mar 17, 2015 There is maybe a bug. Can you show an example of regex and a text where the memory leak occurs? You can use the tracemalloc module to check if there is a memory leak. Or use sys.getcounts() if you compiled Python in debug mode.
sre_lib.h is very complex, it uses the C instruction "goto" with regex bytecodes.
"DO_JUMP(JUMP_REPEAT, jump_repeat, ctx->pattern+ctx->pattern[0]);" calls "goto entrace" to execute following bytecodes, but later it comes back after DO_JUMP() with the "jump_repeat:" label:
https://hg.python.org/cpython/file/c89f7c34e356/Modules/sre_lib.h#l1180 abacabadabacaba commented on Mar 17, 2015 MannequinAuthor More actions Memory leak only happens if match operation terminates abruptly, e.g. because of SIGINT. In this case, DO_JUMP doesn't come back. abacabadabacaba commented on Mar 17, 2015 MannequinAuthor More actions Tracemalloc code:
import re
import signal
import tracemalloc
class AlarmError(Exception):
pass
def handle_alarm(signal, frame):
raise AlarmError
signal.signal(signal.SIGALRM, handle_alarm)
s1 = tracemalloc.take_snapshot()
for _ in range(20):
try:
signal.alarm(1)
re.match('(?:a|a|(?=b)){1000}', 'a'*999)
raise RuntimeError
except AlarmError:
pass
s2 = tracemalloc.take_snapshot()
res = s2.compare_to(s1, 'lineno')
for e in res[:10]:
print(e)For me, it shows almost 3 MiB allocated in re.py. serhiy-storchaka commented on Mar 17, 2015 vstinner commented on Mar 17, 2015 Oh cool, you wrote a script to reproduce the issue! And Serhiy wrote a patch, great! Great job guys.
sre_clean_repeat_data.patch looks good to me.
@serhiy: Can you try the example to ensure that it fixes the issue? If yes, go ahead! abacabadabacaba commented on Mar 18, 2015 MannequinAuthor More actions animalize commented on Feb 19, 2019 animalize commented on Mar 4, 2019 PR11926 (closed) tried to allocate SRE_REPEAT on state's stack.
It's feasible, but messes up the code in sre_lib.h, and reduces performance a little (roughly 6% slower), so I gave up this solution.
PR12160 uses a memory pool, this solution doesn't mess up the code.
🔸For infrequent alloc/free scenes, it adds a small overhead:
s = 'a'
p = re.compile(r'(a)?')
p.match(s) # <- measure this statement before patch: 316 ns +- 19 ns
after patch: 324 ns +- 11 ns, 2.5% slower.
(by perf module)
🔸For very frequent alloc/free scenes, it brings a speedup:
s = 200_000_000 * 'a'
p = re.compile(r'.*?(?:bb)+')
p.match(s) # <- measure this statement before patch: 7.16 sec
after patch: 5.82 sec, 18.7% faster.
(best of 10 tests)
🔸I tested in a real case that use 17 patterns to process 100MB data:
before patch: 27.09 sec
after patch: 26.78 sec, 1.1% faster.
(best of 4 tests) serhiy-storchaka commented on Nov 14, 2024 #126840 and #126843 are two alternate PRs. They are based on my earlier patch, but extend it in different ways. #126840 maintains a double-linked list of all repeat contexts. #126843 maintains two single-linked lists of repeat contexts. #126843 looks simpler, but I am not sure about performance.
Both PRs also add private method _fail_after() in the re.Pattern class which allows to simulate user interruption. After calling _fail_after(n, E) the next matching operation with this pattern will raise exception E after processing n opcodes. This allows stable reproduction of memory leaks.
Example from #91404 (comment) which could not finish in a hour with previous attempt (#32283), now return the result instantly.
re.findall(r'(?:(?:/[^\n]*)?\n)*/', '../utils/common":3}],15:[function(t,e,a){"use strict";e.exports=function(){this.input=null,this.next_in=0,this.avail_in=0,this.total_in=0,this.output=null,this.next_out=0,this.avail_out=0,this.total_out=0,this.msg="",this.state=null,this.data_type=2,this.adler=0}},{}],"/":[function(t,e,a){"use strict";var i={};(0,t("./lib/utils/common").assign)(i,t("./lib/deflate"),t("./lib/inflate"),t("./lib/zlib/constants")),e.exports=i},{"./lib/deflate":1,"./lib/inflate":2,"./lib/utils/common":3,"./lib/zlib/constants":6}]},{},[])("/")});\n')Example from #91404 (comment) also returns an expected result.
m = re.match(r'((a)?)*', 'aaaaa')
assert m.span(0) == (0, 5)
assert m.span(1) == (5, 5) @wjssz, could you please take a look at these PRs? wjssz commented on Nov 15, 2024 #126843 is not feasible. If a SRE_REPEAT struct was not registered in state->repstack, and a signal aborts the matching, then it can't be released.
Maybe #126843 works. But it requires a deeper understanding of the hiberarchy of SRE_REPEAT and bringing this complexity into the engine code. This may confuse readers of the code.
#126840 should works. But add_repeat()/remove_repeat() functions always malloc/free the struct, this may be inefficient.
Below is my patch, it uses a doubly-linked list for used pool, a singly-linked list for unused pool. It puts released structs to unused pool, so that these structs can be reused. It's faster when malloc/free structs very frequently.
My patch compare to #126840 (On Windows, MSVC2022, non-PGO release build):
### regex_dna ###
Mean +- std dev: 139 ms +- 1 ms -> 139 ms +- 1 ms: 1.00x slower
Not significant
### regex_effbot ###
Mean +- std dev: 2.45 ms +- 0.04 ms -> 2.20 ms +- 0.01 ms: 1.11x faster
Significant (t=47.54)
### regex_v8 ###
Mean +- std dev: 21.6 ms +- 0.2 ms -> 22.0 ms +- 0.2 ms: 1.02x slower
Not significant
My benchmark (it uses 16 patterns to process 100MB real data):
baseline: 12.104 sec
#126840: 12.767 sec
My patch: 12.597 sec
Both PRs also add private method _fail_after() in the re.Pattern class which allows to simulate user interruption. After calling _fail_after(n, E) the next matching operation with this pattern will raise exception E after processing n opcodes. This allows stable reproduction of memory leaks.
IMO _fail_after() method is not necessary. It makes the code complex, for situations where it's almost never used again. The code above triggers the memory leak with signal, maybe it can be included in unit-test? But I don't think it's necessary either.
This GitHub account can't upload file, you can save the patch, and apply it to main branch:
click to see my patch
Modules/_sre/sre.c | 88 ++++++++++++++++++++++++++++++++++++++++++++++++++
Modules/_sre/sre.h | 6 ++++
Modules/_sre/sre_lib.h | 9 ++----
3 files changed, 97 insertions(+), 6 deletions(-)
diff --git a/Modules/_sre/sre.c b/Modules/_sre/sre.c
index 2c86f8869d..aea051c636 100644
--- a/Modules/_sre/sre.c
+++ b/Modules/_sre/sre.c
@@ -267,6 +267,86 @@ data_stack_grow(SRE_STATE* state, Py_ssize_t size)
return 0;
}
+/* memory pool functions for SRE_REPEAT, this can avoid memory
+ leak when SRE(match) function terminates abruptly.
+ state->repeat_pool_used is a doubly-linked list, so that we
+ can remove a SRE_REPEAT node from it.
+ state->repeat_pool_unused is a singly-linked list, we put/get
+ node at the head. */
+static SRE_REPEAT*
+repeat_pool_malloc(SRE_STATE *state)
+{
+ SRE_REPEAT *repeat, *temp;
+
+ if (state->repeat_pool_unused) {
+ /* remove from unused pool (singly-linked list) */
+ repeat = state->repeat_pool_unused;
+ state->repeat_pool_unused = repeat->pool_next;
+ } else {
+ repeat = PyMem_Malloc(sizeof(SRE_REPEAT));
+ if (!repeat) {
+ return NULL;
+ }
+ }
+
+ /* add to used pool (doubly-linked list) */
+ temp = state->repeat_pool_used;
+ if (temp) {
+ temp->pool_prev = repeat;
+ }
+ repeat->pool_prev = NULL;
+ repeat->pool_next = temp;
+ state->repeat_pool_used = repeat;
+
+ return repeat;
+}
+
+static void
+repeat_pool_free(SRE_STATE *state, SRE_REPEAT *repeat)
+{
+ SRE_REPEAT* const prev = repeat->pool_prev;
+ SRE_REPEAT* const next = repeat->pool_next;
+
+ /* remove from used pool (doubly-linked list) */
+ if (prev) {
+ prev->pool_next = next;
+ } else {
+ state->repeat_pool_used = next;
+ }
+
+ if (next) {
+ next->pool_prev = prev;
+ }
+
+ /* add to unused pool (singly-linked list) */
+ repeat->pool_next = state->repeat_pool_unused;
+ state->repeat_pool_unused = repeat;
+}
+
+static void
+repeat_pool_clear(SRE_STATE *state)
+{
+ SRE_REPEAT *next;
+
+ /* clear used pool */
+ next = state->repeat_pool_used;
+ while (next) {
+ SRE_REPEAT *temp = next;
+ next = temp->pool_next;
+ PyMem_Free(temp);
+ }
+ state->repeat_pool_used = NULL;
+
+ /* clear unused pool */
+ next = state->repeat_pool_unused;
+ while (next) {
+ SRE_REPEAT *temp = next;
+ next = temp->pool_next;
+ PyMem_Free(temp);
+ }
+ state->repeat_pool_unused = NULL;
+}
+
/* generate 8-bit version */
#define SRE_CHAR Py_UCS1
@@ -502,6 +582,11 @@ state_init(SRE_STATE* state, PatternObject* pattern, PyObject* string,
state->must_advance = 0;
state->debug = ((pattern->flags & SRE_FLAG_DEBUG) != 0);
+ /* SRE_REPEAT pool */
+ state->repeat = NULL;
+ state->repeat_pool_used = NULL;
+ state->repeat_pool_unused = NULL;
+
state->beginning = ptr;
state->start = (void*) ((char*) ptr + start * state->charsize);
@@ -533,6 +618,9 @@ state_fini(SRE_STATE* state)
/* See above PyMem_Free() for why we explicitly cast here. */
PyMem_Free((void*) state->mark);
state->mark = NULL;
+
+ /* SRE_REPEAT pool */
+ repeat_pool_clear(state);
}
/* calculate offset from start of string */
diff --git a/Modules/_sre/sre.h b/Modules/_sre/sre.h
index 83d89d57b1..acf73a91e6 100644
--- a/Modules/_sre/sre.h
+++ b/Modules/_sre/sre.h
@@ -68,6 +68,9 @@ typedef struct SRE_REPEAT_T {
const SRE_CODE* pattern; /* points to REPEAT operator arguments */
const void* last_ptr; /* helper to check for infinite loops */
struct SRE_REPEAT_T *prev; /* points to previous repeat context */
+ /* for SRE_REPEAT pool */
+ struct SRE_REPEAT_T *pool_prev;
+ struct SRE_REPEAT_T *pool_next;
} SRE_REPEAT;
typedef struct {
@@ -95,6 +98,9 @@ typedef struct {
size_t data_stack_base;
/* current repeat context */
SRE_REPEAT *repeat;
+ /* SRE_REPEAT pool */
+ SRE_REPEAT *repeat_pool_used;
+ SRE_REPEAT *repeat_pool_unused;
unsigned int sigcount;
} SRE_STATE;
diff --git a/Modules/_sre/sre_lib.h b/Modules/_sre/sre_lib.h
index 97fbb0a75e..1757987f5d 100644
--- a/Modules/_sre/sre_lib.h
+++ b/Modules/_sre/sre_lib.h
@@ -1120,12 +1120,9 @@ SRE(match)(SRE_STATE* state, const SRE_CODE* pattern, int toplevel)
pattern[1], pattern[2]));
/* install new repeat context */
- /* TODO(https://github.com/python/cpython/issues/67877): Fix this
- * potential memory leak. */
- ctx->u.rep = (SRE_REPEAT*) PyMem_Malloc(sizeof(*ctx->u.rep));
+ ctx->u.rep = repeat_pool_malloc(state);
if (!ctx->u.rep) {
- PyErr_NoMemory();
- RETURN_FAILURE;
+ RETURN_ERROR(SRE_ERROR_MEMORY);
}
ctx->u.rep->count = -1;
ctx->u.rep->pattern = pattern;
@@ -1136,7 +1133,7 @@ SRE(match)(SRE_STATE* state, const SRE_CODE* pattern, int toplevel)
state->ptr = ptr;
DO_JUMP(JUMP_REPEAT, jump_repeat, pattern+pattern[0]);
state->repeat = ctx->u.rep->prev;
- PyMem_Free(ctx->u.rep);
+ repeat_pool_free(state, ctx->u.rep);
if (ret) {
RETURN_ON_ERROR(ret);
serhiy-storchaka commented on Nov 15, 2024 Yes, the issue can be reproduced with signals, but it is less reliable. We need to use long running regexps to be sure that signal will be raised before the matching finished, and we cannot predict the place of interruption. With _fail_after() we can test all places.
I was going to add a pool for freed SRE_REPEAT blocks later, as optimization. But it will not harm to add it now. On my computer, with optimized build, #126843 is ~10% slower than #126840 in regex_dna and your patch is ~20% faster than #126840 in regex_effbot. So I chose your patch. serhiy-storchaka commented on Nov 18, 2024
MetadataMetadataDevelopmentNo branches or pull requestsIssue actions
|