diff options
author | Lennart Poettering <lennart@poettering.net> | 2019-12-09 18:30:00 +0100 |
---|---|---|
committer | Lennart Poettering <lennart@poettering.net> | 2019-12-09 18:36:03 +0100 |
commit | 6047637645ac8038edbca12bf91d030eddd59972 (patch) | |
tree | fc3566ca48276d021861da6412aedb7faf10cd10 | |
parent | 47ac31f792a8856f29ea4ac38d6b366e88ac7d34 (diff) | |
download | systemd-6047637645ac8038edbca12bf91d030eddd59972.tar.gz |
strv: when growing strv arrays piecemeal actually allocate memory in exponential steps
Let's improve memory allocation for call such as strv_extend() that just
one item to an strv: these are often called in a loop, where they used
to be very ineffecient, since we'd allocate byte-exact space. With this
change let's improve on that, by allocating exponentially by rounding up
to the next exponent of 2. This way we get GREEDY_REALLOC()-like
behaviour without passing around state.
In fact this should be good enough so that we could replace existing
loops around GREEDY_REALLOC() for strv build-up with plain strv_extend()
and get similar behaviour.
-rw-r--r-- | src/basic/strv.c | 28 |
1 files changed, 16 insertions, 12 deletions
diff --git a/src/basic/strv.c b/src/basic/strv.c index 30fab63074..92e528940a 100644 --- a/src/basic/strv.c +++ b/src/basic/strv.c @@ -193,7 +193,10 @@ int strv_extend_strv(char ***a, char **b, bool filter_duplicates) { p = strv_length(*a); q = strv_length(b); - t = reallocarray(*a, p + q + 1, sizeof(char *)); + if (p >= SIZE_MAX - q) + return -ENOMEM; + + t = reallocarray(*a, GREEDY_ALLOC_ROUND_UP(p + q + 1), sizeof(char *)); if (!t) return -ENOMEM; @@ -383,19 +386,18 @@ char *strv_join_prefix(char **l, const char *separator, const char *prefix) { int strv_push(char ***l, char *value) { char **c; - size_t n, m; + size_t n; if (!value) return 0; n = strv_length(*l); - /* Increase and check for overflow */ - m = n + 2; - if (m < n) + /* Check for overflow */ + if (n > SIZE_MAX-2) return -ENOMEM; - c = reallocarray(*l, m, sizeof(char*)); + c = reallocarray(*l, GREEDY_ALLOC_ROUND_UP(n + 2), sizeof(char*)); if (!c) return -ENOMEM; @@ -408,19 +410,19 @@ int strv_push(char ***l, char *value) { int strv_push_pair(char ***l, char *a, char *b) { char **c; - size_t n, m; + size_t n; if (!a && !b) return 0; n = strv_length(*l); - /* increase and check for overflow */ - m = n + !!a + !!b + 1; - if (m < n) + /* Check for overflow */ + if (n > SIZE_MAX-3) return -ENOMEM; - c = reallocarray(*l, m, sizeof(char*)); + /* increase and check for overflow */ + c = reallocarray(*l, GREEDY_ALLOC_ROUND_UP(n + !!a + !!b + 1), sizeof(char*)); if (!c) return -ENOMEM; @@ -846,8 +848,10 @@ int strv_extend_n(char ***l, const char *value, size_t n) { /* Adds the value n times to l */ k = strv_length(*l); + if (n >= SIZE_MAX - k) + return -ENOMEM; - nl = reallocarray(*l, k + n + 1, sizeof(char *)); + nl = reallocarray(*l, GREEDY_ALLOC_ROUND_UP(k + n + 1), sizeof(char *)); if (!nl) return -ENOMEM; |