diff options
| author | Ron Yorston <rmy@pobox.com> | 2023-08-22 09:38:03 +0100 |
|---|---|---|
| committer | Denys Vlasenko <vda.linux@googlemail.com> | 2023-08-31 09:41:53 +0200 |
| commit | 2cc9d436e80632157b99e18d413a62b2d44d321a (patch) | |
| tree | eb5c530d16cea5d37cff8e1f22e1cedfeadf0490 /coreutils | |
| parent | ed4a24dfd10539e144ed4b7de008f8791d09a551 (diff) | |
| download | busybox-w32-2cc9d436e80632157b99e18d413a62b2d44d321a.tar.gz busybox-w32-2cc9d436e80632157b99e18d413a62b2d44d321a.tar.bz2 busybox-w32-2cc9d436e80632157b99e18d413a62b2d44d321a.zip | |
tsort: avoid use-after-free
When the input data contained a cycle it was possible for tsort to
attempt to access freed nodes. This sometimes resulted in the
test case 'echo a b b a | tsort' crashing.
Don't free nodes when they're removed from the graph.
function old new delta
tsort_main 621 596 -25
------------------------------------------------------------------------------
(add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-25) Total: -25 bytes
Signed-off-by: Ron Yorston <rmy@pobox.com>
Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>
Diffstat (limited to 'coreutils')
| -rw-r--r-- | coreutils/tsort.c | 20 |
1 files changed, 17 insertions, 3 deletions
diff --git a/coreutils/tsort.c b/coreutils/tsort.c index a451ed2ff..e1ee6bcd7 100644 --- a/coreutils/tsort.c +++ b/coreutils/tsort.c | |||
| @@ -101,6 +101,10 @@ int tsort_main(int argc UNUSED_PARAM, char **argv) | |||
| 101 | ssize_t len; | 101 | ssize_t len; |
| 102 | struct node *a; | 102 | struct node *a; |
| 103 | int cycles; | 103 | int cycles; |
| 104 | unsigned i; | ||
| 105 | #if ENABLE_FEATURE_CLEAN_UP | ||
| 106 | unsigned max_len; | ||
| 107 | #endif | ||
| 104 | 108 | ||
| 105 | INIT_G(); | 109 | INIT_G(); |
| 106 | 110 | ||
| @@ -152,9 +156,11 @@ int tsort_main(int argc UNUSED_PARAM, char **argv) | |||
| 152 | * - if any nodes are left, they form cycles. | 156 | * - if any nodes are left, they form cycles. |
| 153 | */ | 157 | */ |
| 154 | cycles = 0; | 158 | cycles = 0; |
| 159 | #if ENABLE_FEATURE_CLEAN_UP | ||
| 160 | max_len = G.nodes_len; | ||
| 161 | #endif | ||
| 155 | while (G.nodes_len) { | 162 | while (G.nodes_len) { |
| 156 | struct node *n; | 163 | struct node *n; |
| 157 | unsigned i; | ||
| 158 | 164 | ||
| 159 | /* Search for first node with no incoming edges */ | 165 | /* Search for first node with no incoming edges */ |
| 160 | for (i = 0; i < G.nodes_len; i++) { | 166 | for (i = 0; i < G.nodes_len; i++) { |
| @@ -173,16 +179,24 @@ int tsort_main(int argc UNUSED_PARAM, char **argv) | |||
| 173 | /* Remove the node (need no longer maintain sort) */ | 179 | /* Remove the node (need no longer maintain sort) */ |
| 174 | n = G.nodes[i]; | 180 | n = G.nodes[i]; |
| 175 | G.nodes[i] = G.nodes[--G.nodes_len]; | 181 | G.nodes[i] = G.nodes[--G.nodes_len]; |
| 182 | #if ENABLE_FEATURE_CLEAN_UP | ||
| 183 | /* Keep reference to removed node so it can be freed */ | ||
| 184 | G.nodes[G.nodes_len] = n; | ||
| 185 | #endif | ||
| 176 | 186 | ||
| 177 | /* And remove its outgoing edges */ | 187 | /* And remove its outgoing edges */ |
| 178 | for (i = 0; i < n->out_count; i++) | 188 | for (i = 0; i < n->out_count; i++) |
| 179 | n->out[i]->in_count--; | 189 | n->out[i]->in_count--; |
| 180 | free(n->out); | ||
| 181 | 190 | ||
| 182 | puts(n->name); | 191 | puts(n->name); |
| 183 | free(n); | 192 | } |
| 193 | #if ENABLE_FEATURE_CLEAN_UP | ||
| 194 | for (i = 0; i < max_len; i++) { | ||
| 195 | free(G.nodes[i]->out); | ||
| 196 | free(G.nodes[i]); | ||
| 184 | } | 197 | } |
| 185 | free(G.nodes); | 198 | free(G.nodes); |
| 199 | #endif | ||
| 186 | 200 | ||
| 187 | fflush_stdout_and_exit(cycles ? 1 : 0); | 201 | fflush_stdout_and_exit(cycles ? 1 : 0); |
| 188 | } | 202 | } |