libselinux: Workaround for heap overhead of pcre
PATCH 1/1 libselinux: Workaround for heap overhead of pcre
pcre's behavior is changed so that pcre2_match always allocates heap for match_data, rather than stack, regardless of size. The heap isn't freed until explicitly calling pcre2_match_data_free. This new behavior may result in heap overhead, which may increase the peak memory usage about a few megabytes. It's because regex_match is first called for regex_data objects, and then regex_data objects are freed at once.
To workaround it, free and reallocate match_data whenever we call regex_match. It's fine because libselinux currently doesn't use match_data, but use only the return value.
--- libselinux/src/regex.c | 10 ++++++++++ 1 file changed, 10 insertions(+)
libselinux/src/regex.c +10 -0
@@ -213,10 +213,20 @@ void regex_data_free(struct regex_data *regex)int regex_match (struct regex_data *regex,char const *subject,int partial) {int rc; +pcre2_match_data *new_match_data;__pthread_mutex_lock (®ex->match_mutex); + new_match_data =pcre2_match_data_create_from_pattern ( + regex->regex,NULL ); rc =pcre2_match ( regex->regex, (PCRE2_SPTR )subject,PCRE2_ZERO_TERMINATED ,0 , partial ?PCRE2_PARTIAL_SOFT :0 , regex->match_data,NULL ); +// pcre2_match allocates heap and it won't be freed until +// pcre2_match_data_free, resulting in heap overhead. +// Reallocate match_data to prevent such overhead, whenever possible. +if (new_match_data) { +pcre2_match_data_free (regex->match_data); + regex->match_data = new_match_data; + }__pthread_mutex_unlock (®ex->match_mutex);if (rc >0 )return REGEX_MATCH ;
Signature · 1 line
2.39.0.314.g84b9a713c41-goog
Quoted 7 lines · Inseob Kim
pcre's behavior is changed so that
pcre2_matchalways allocates heap formatch_data, rather than stack, regardless of size. The heap isn't freed until explicitly callingpcre2_match_data_free. This new behavior may result in heap overhead, which may increase the peak memory usage about a few megabytes. It's becauseregex_matchis first called forregex_dataobjects, and thenregex_dataobjects are freed at once.
This approach trades peak memory usage for temporary allocations, which effects runtime performance. On modern systems memory is most of the time not a scarce resource.
Some examples:
# selabel_lookup -b file -k /etc/shadow -t file [heaptrack]
## current
total runtime: 0.07s.
calls to allocation functions: 28420 (406000/s)
temporary memory allocations: 16 (228/s)
peak heap memory consumption: 10.09M
peak RSS (including heaptrack overhead): 21.27M
total memory leaked: 1.02K
## proposed
total runtime: 0.06s.
calls to allocation functions: 23430 (366093/s)
temporary memory allocations: 675 (10546/s)
peak heap memory consumption: 9.48M
peak RSS (including heaptrack overhead): 18.59M
total memory leaked: 1.02K
# restorecon -vRn /etc [heaptrack]
## current
total runtime: 0.14s.
calls to allocation functions: 33873 (236874/s)
temporary memory allocations: 1877 (13125/s)
peak heap memory consumption: 10.09M
peak RSS (including heaptrack overhead): 21.58M
total memory leaked: 1.90K
## proposed
total runtime: 0.27s.
calls to allocation functions: 378762 (1423917/s)
temporary memory allocations: 351487 (1321379/s)
peak heap memory consumption: 9.48M
peak RSS (including heaptrack overhead): 20.99M
total memory leaked: 1.90K
# restorecon -vRn /usr [hyperfine]
## current
restorecon -vRn /usr
Benchmark 1: ~/destdir/sbin/restorecon -vRn /usr
Time (mean ± σ): 24.419 s ± 0.661 s [User: 23.480 s, System: 0.922 s]
Range (min … max): 23.399 s … 25.495 s 10 runs
## proposed
restorecon -vRn /usr
Benchmark 1: ~/destdir/sbin/restorecon -vRn /usr
Time (mean ± σ): 28.628 s ± 0.968 s [User: 27.688 s, System: 0.927 s]
Range (min … max): 27.674 s … 30.798 s 10 runs
So I would argue the performance impact for applications (like setfiles, restorecon) or daemon (like systemd, udev) is more critical than the 500K per application.
Quoted 14 lines
To workaround it, free and reallocate
match_datawhenever we callregex_match. It's fine because libselinux currently doesn't usematch_data, but use only the return value.Signed-off-by Inseob Kim <[email protected]>--- libselinux/src/regex.c | 10 ++++++++++ 1 file changed, 10 insertions(+)libselinux/src/regex.c +0
-0
libselinux/src/regex.c void regex_data_free(struct regex_data *regex) · line 219
Quoted 7 lines
libselinux/src/regex.c +3
-0@@ -213,10 +213,20 @@ void regex_data_free(struct regex_data *regex)int regex_match (struct regex_data *regex,char const *subject,int partial) {int rc; +pcre2_match_data *new_match_data;__pthread_mutex_lock (®ex->match_mutex); + new_match_data =pcre2_match_data_create_from_pattern ( + regex->regex,NULL );
Should be checked for failure (cause pcre2_match() expects a non-NULL match_data, which would be passed the second time).
Also with this change the member match_data of the struct regex_data becomes obsolete and should be removed.
Quoted 16 lines
libselinux/src/regex.c +7
-1rc =pcre2_match ( regex->regex, (PCRE2_SPTR )subject,PCRE2_ZERO_TERMINATED ,0 , partial ?PCRE2_PARTIAL_SOFT :0 , regex->match_data,NULL ); +// pcre2_match allocates heap and it won't be freed until +// pcre2_match_data_free, resulting in heap overhead. +// Reallocate match_data to prevent such overhead, whenever possible. +if (new_match_data) { +pcre2_match_data_free (regex->match_data); + regex->match_data = new_match_data; + }__pthread_mutex_unlock (®ex->match_mutex);if (rc >0 )return REGEX_MATCH ; --2.39.0.314.g84b9a713c41-goog
Quoted 74 lines · Christian Göttsche
Quoted 7 lines · Inseob Kim
pcre's behavior is changed so that
pcre2_matchalways allocates heap formatch_data, rather than stack, regardless of size. The heap isn't freed until explicitly callingpcre2_match_data_free. This new behavior may result in heap overhead, which may increase the peak memory usage about a few megabytes. It's becauseregex_matchis first called forregex_dataobjects, and thenregex_dataobjects are freed at once.This approach trades peak memory usage for temporary allocations, which effects runtime performance. On modern systems memory is most of the time not a scarce resource.
Some examples:
# selabel_lookup -b file -k /etc/shadow -t file [heaptrack]## current
total runtime: 0.07s.
calls to allocation functions: 28420 (406000/s)
temporary memory allocations: 16 (228/s)
peak heap memory consumption: 10.09M
peak RSS (including heaptrack overhead): 21.27M
total memory leaked: 1.02K## proposed
total runtime: 0.06s.
calls to allocation functions: 23430 (366093/s)
temporary memory allocations: 675 (10546/s)
peak heap memory consumption: 9.48M
peak RSS (including heaptrack overhead): 18.59M
total memory leaked: 1.02K# restorecon -vRn /etc [heaptrack]## current
total runtime: 0.14s.
calls to allocation functions: 33873 (236874/s)
temporary memory allocations: 1877 (13125/s)
peak heap memory consumption: 10.09M
peak RSS (including heaptrack overhead): 21.58M
total memory leaked: 1.90K## proposed
total runtime: 0.27s.
calls to allocation functions: 378762 (1423917/s)
temporary memory allocations: 351487 (1321379/s)
peak heap memory consumption: 9.48M
peak RSS (including heaptrack overhead): 20.99M
total memory leaked: 1.90K# restorecon -vRn /usr [hyperfine]## current
restorecon -vRn /usr
Benchmark 1: ~/destdir/sbin/restorecon -vRn /usr
Time (mean ± σ): 24.419 s ± 0.661 s [User: 23.480 s, System: 0.922 s]
Range (min … max): 23.399 s … 25.495 s 10 runs## proposed
restorecon -vRn /usr
Benchmark 1: ~/destdir/sbin/restorecon -vRn /usr
Time (mean ± σ): 28.628 s ± 0.968 s [User: 27.688 s, System: 0.927 s]
Range (min … max): 27.674 s … 30.798 s 10 runs
Quoted 3 lines
So I would argue the performance impact for applications (like setfiles, restorecon) or daemon (like systemd, udev) is more critical than the 500K per application.
I observed about 3~4MB increase on Android device. Which pcre2 version are you using? Does it include
https://github.com/PCRE2Project/pcre2/commit/d90fb238#diff-15ec3f4ed916f52c810daf305702985dda6d8d45e7ce22e2f309c95bd6ef32b7R74
?
And if this is difficult to apply, how about adding a new flag e.g. AGGRESSIVE_FREE_AFTER_REGEX_MATCH ?
Quoted 26 lines
Quoted 15 lines
To workaround it, free and reallocate
match_datawhenever we callregex_match. It's fine because libselinux currently doesn't usematch_data, but use only the return value.Signed-off-by Inseob Kim <[email protected]>--- libselinux/src/regex.c | 10 ++++++++++ 1 file changed, 10 insertions(+)libselinux/src/regex.c +0
-0libselinux/src/regex.c void regex_data_free(struct regex_data *regex) · line 219
Quoted 7 lines
libselinux/src/regex.c +3
-0@@ -213,10 +213,20 @@ void regex_data_free(struct regex_data *regex)int regex_match (struct regex_data *regex,char const *subject,int partial) {int rc; +pcre2_match_data *new_match_data;__pthread_mutex_lock (®ex->match_mutex); + new_match_data =pcre2_match_data_create_from_pattern ( + regex->regex,NULL );Should be checked for failure (cause
pcre2_match()expects a non-NULLmatch_data, which would be passed the second time).
Quoted 2 lines
Also with this change the member
match_dataof the structregex_databecomes obsolete and should be removed.
Thanks, this makes sense.
Quoted 17 lines
Quoted 17 lines
libselinux/src/regex.c +7
-1rc =pcre2_match ( regex->regex, (PCRE2_SPTR )subject,PCRE2_ZERO_TERMINATED ,0 , partial ?PCRE2_PARTIAL_SOFT :0 , regex->match_data,NULL ); +// pcre2_match allocates heap and it won't be freed until +// pcre2_match_data_free, resulting in heap overhead. +// Reallocate match_data to prevent such overhead, whenever possible. +if (new_match_data) { +pcre2_match_data_free (regex->match_data); + regex->match_data = new_match_data; + }__pthread_mutex_unlock (®ex->match_mutex);if (rc >0 )return REGEX_MATCH ; --2.39.0.314.g84b9a713c41-goog
Signature · 1 line
Inseob Kim | Software Engineer | [email protected]
Quoted 77 lines · Inseob Kim
Quoted 74 lines · Christian Göttsche
Quoted 7 lines · Inseob Kim
pcre's behavior is changed so that
pcre2_matchalways allocates heap formatch_data, rather than stack, regardless of size. The heap isn't freed until explicitly callingpcre2_match_data_free. This new behavior may result in heap overhead, which may increase the peak memory usage about a few megabytes. It's becauseregex_matchis first called forregex_dataobjects, and thenregex_dataobjects are freed at once.This approach trades peak memory usage for temporary allocations, which effects runtime performance. On modern systems memory is most of the time not a scarce resource.
Some examples:
# selabel_lookup -b file -k /etc/shadow -t file [heaptrack]## current
total runtime: 0.07s.
calls to allocation functions: 28420 (406000/s)
temporary memory allocations: 16 (228/s)
peak heap memory consumption: 10.09M
peak RSS (including heaptrack overhead): 21.27M
total memory leaked: 1.02K## proposed
total runtime: 0.06s.
calls to allocation functions: 23430 (366093/s)
temporary memory allocations: 675 (10546/s)
peak heap memory consumption: 9.48M
peak RSS (including heaptrack overhead): 18.59M
total memory leaked: 1.02K# restorecon -vRn /etc [heaptrack]## current
total runtime: 0.14s.
calls to allocation functions: 33873 (236874/s)
temporary memory allocations: 1877 (13125/s)
peak heap memory consumption: 10.09M
peak RSS (including heaptrack overhead): 21.58M
total memory leaked: 1.90K## proposed
total runtime: 0.27s.
calls to allocation functions: 378762 (1423917/s)
temporary memory allocations: 351487 (1321379/s)
peak heap memory consumption: 9.48M
peak RSS (including heaptrack overhead): 20.99M
total memory leaked: 1.90K# restorecon -vRn /usr [hyperfine]## current
restorecon -vRn /usr
Benchmark 1: ~/destdir/sbin/restorecon -vRn /usr
Time (mean ± σ): 24.419 s ± 0.661 s [User: 23.480 s, System: 0.922 s]
Range (min … max): 23.399 s … 25.495 s 10 runs## proposed
restorecon -vRn /usr
Benchmark 1: ~/destdir/sbin/restorecon -vRn /usr
Time (mean ± σ): 28.628 s ± 0.968 s [User: 27.688 s, System: 0.927 s]
Range (min … max): 27.674 s … 30.798 s 10 runs
Quoted 8 lines
Quoted 3 lines
So I would argue the performance impact for applications (like setfiles, restorecon) or daemon (like systemd, udev) is more critical than the 500K per application.
I observed about 3~4MB increase on Android device. Which pcre2 version are you using? Does it include
https://github.com/PCRE2Project/pcre2/commit/d90fb238#diff-15ec3f4ed916f52c810daf305702985dda6d8d45e7ce22e2f309c95bd6ef32b7R74
?
Those measurements were done against pcre2 version 10.40. Indeed with version 10.42 the peak memory usage of the current implementation has grown and is reduced by this patch:
# selabel_lookup -b file -k /etc/shadow -t file [heaptrack]
## current
total runtime: 0.07s.
calls to allocation functions: 29080 (421449/s) temporary memory allocations: 15 (217/s) peak heap memory consumption: 22.72M
peak RSS (including heaptrack overhead): 18.68M total memory leaked: 1.02K
## proposed
total runtime: 0.06s.
calls to allocation functions: 24090 (376406/s) temporary memory allocations: 675 (10546/s) peak heap memory consumption: 9.48M
peak RSS (including heaptrack overhead): 22.15M total memory leaked: 1.02K
# restorecon -vRn /etc [heaptrack]
## current
total runtime: 0.13s.
calls to allocation functions: 34720 (259104/s) temporary memory allocations: 1872 (13970/s) peak heap memory consumption: 26.66M
peak RSS (including heaptrack overhead): 25.59M total memory leaked: 1.90K
## proposed
total runtime: 0.43s.
calls to allocation functions: 729301 (1692113/s) temporary memory allocations: 351486 (815512/s) peak heap memory consumption: 9.48M
peak RSS (including heaptrack overhead): 20.98M total memory leaked: 1.90K
# restorecon -vRn /usr [hyperfine]
## current
Benchmark 1: ~/destdir/sbin/restorecon -vRn /usr
Time (mean ± σ): 31.053 s ± 1.491 s [User: 29.926 s, System: 1.105 s]
Range (min … max): 28.817 s … 33.679 s 10 runs
## proposed
Benchmark 1: ~/destdir/sbin/restorecon -vRn /usr
Time (mean ± σ): 37.829 s ± 0.416 s [User: 36.935 s, System: 0.875 s]
Range (min … max): 37.205 s … 38.764 s 10 runs
Quoted 57 lines
And if this is difficult to apply, how about adding a new flag e.g.
AGGRESSIVE_FREE_AFTER_REGEX_MATCH?Quoted 26 lines
Quoted 15 lines
To workaround it, free and reallocate
match_datawhenever we callregex_match. It's fine because libselinux currently doesn't usematch_data, but use only the return value.Signed-off-by Inseob Kim <[email protected]>--- libselinux/src/regex.c | 10 ++++++++++ 1 file changed, 10 insertions(+)libselinux/src/regex.c +0
-0libselinux/src/regex.c void regex_data_free(struct regex_data *regex) · line 219
Quoted 7 lines
libselinux/src/regex.c +3
-0@@ -213,10 +213,20 @@ void regex_data_free(struct regex_data *regex)int regex_match (struct regex_data *regex,char const *subject,int partial) {int rc; +pcre2_match_data *new_match_data;__pthread_mutex_lock (®ex->match_mutex); + new_match_data =pcre2_match_data_create_from_pattern ( + regex->regex,NULL );Should be checked for failure (cause
pcre2_match()expects a non-NULLmatch_data, which would be passed the second time).Quoted 2 lines
Also with this change the member
match_dataof the structregex_databecomes obsolete and should be removed.Thanks, this makes sense.
Quoted 17 lines
Quoted 15 lines
libselinux/src/regex.c +7
-1rc =pcre2_match ( regex->regex, (PCRE2_SPTR )subject,PCRE2_ZERO_TERMINATED ,0 , partial ?PCRE2_PARTIAL_SOFT :0 , regex->match_data,NULL ); +// pcre2_match allocates heap and it won't be freed until +// pcre2_match_data_free, resulting in heap overhead. +// Reallocate match_data to prevent such overhead, whenever possible. +if (new_match_data) { +pcre2_match_data_free (regex->match_data); + regex->match_data = new_match_data; + }__pthread_mutex_unlock (®ex->match_mutex);if (rc >0 )return REGEX_MATCH ; --Quoted 2 lines
2.39.0.314.g84b9a713c41-goog
--
Inseob Kim | Software Engineer | [email protected]