[PATCH 2/2] maple_tree: Fix a potential memory leak, OOB access, or other unpredictable bug
In mas_alloc_nodes(), there is such a piece of code: while (requested) { ... node->node_count = 0; ... } "node->node_count = 0" means to initialize the node_count field of the new node, but the node may not be a new node. It may be a node that existed before and node_count has a value, setting it to 0 will cause a memory leak. At this time, mas->alloc->total will be greater than the actual number of nodes in the linked list, which may cause many other errors. For example, out-of-bounds access in mas_pop_node(), and mas_pop_node() may return addresses that should not be used. Fix it by initializing node_count only for new nodes.
Fixes: 54a611b60590 ("Maple Tree: add new data structure") Signed-off-by: Peng Zhang zhangpeng.00@bytedance.com Cc: stable@vger.kernel.org --- lib/maple_tree.c | 16 ++++------------ 1 file changed, 4 insertions(+), 12 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 65fd861b30e1..9e25b3215803 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1249,26 +1249,18 @@ static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp) node = mas->alloc; node->request_count = 0; while (requested) { - max_req = MAPLE_ALLOC_SLOTS; - if (node->node_count) { - unsigned int offset = node->node_count; - - slots = (void **)&node->slot[offset]; - max_req -= offset; - } else { - slots = (void **)&node->slot; - } - + max_req = MAPLE_ALLOC_SLOTS - node->node_count; + slots = (void **)&node->slot[node->node_count]; max_req = min(requested, max_req); count = mt_alloc_bulk(gfp, max_req, slots); if (!count) goto nomem_bulk;
+ if (node->node_count == 0) + node->slot[0]->node_count = 0; node->node_count += count; allocated += count; node = node->slot[0]; - node->node_count = 0; - node->request_count = 0; requested -= count; } mas->alloc->total = allocated;
* Peng Zhang zhangpeng.00@bytedance.com [230407 00:10]:
In mas_alloc_nodes(), there is such a piece of code: while (requested) { ... node->node_count = 0; ... }
You don't need to quote code in your commit message since it is available in the change log or in the file itself.
"node->node_count = 0" means to initialize the node_count field of the new node, but the node may not be a new node. It may be a node that existed before and node_count has a value, setting it to 0 will cause a memory leak. At this time, mas->alloc->total will be greater than the actual number of nodes in the linked list, which may cause many other errors. For example, out-of-bounds access in mas_pop_node(), and mas_pop_node() may return addresses that should not be used. Fix it by initializing node_count only for new nodes.
Fixes: 54a611b60590 ("Maple Tree: add new data structure") Signed-off-by: Peng Zhang zhangpeng.00@bytedance.com Cc: stable@vger.kernel.org
lib/maple_tree.c | 16 ++++------------ 1 file changed, 4 insertions(+), 12 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 65fd861b30e1..9e25b3215803 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1249,26 +1249,18 @@ static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp) node = mas->alloc; node->request_count = 0; while (requested) {
max_req = MAPLE_ALLOC_SLOTS;if (node->node_count) {unsigned int offset = node->node_count;slots = (void **)&node->slot[offset];max_req -= offset;} else {slots = (void **)&node->slot;}
max_req = MAPLE_ALLOC_SLOTS - node->node_count;slots = (void **)&node->slot[node->node_count];
Thanks, this is much cleaner.
max_req = min(requested, max_req); count = mt_alloc_bulk(gfp, max_req, slots); if (!count) goto nomem_bulk;
if (node->node_count == 0)node->slot[0]->node_count = 0;
node->node_count = 0;node->request_count = 0;
Why are we not clearing request_count anymore?
requested -= count;} mas->alloc->total = allocated; -- 2.20.1
在 2023/4/10 20:43, Liam R. Howlett 写道:
- Peng Zhang zhangpeng.00@bytedance.com [230407 00:10]:
In mas_alloc_nodes(), there is such a piece of code: while (requested) { ... node->node_count = 0; ... }
You don't need to quote code in your commit message since it is available in the change log or in the file itself.
Ok, I will change it in the next version.
"node->node_count = 0" means to initialize the node_count field of the new node, but the node may not be a new node. It may be a node that existed before and node_count has a value, setting it to 0 will cause a memory leak. At this time, mas->alloc->total will be greater than the actual number of nodes in the linked list, which may cause many other errors. For example, out-of-bounds access in mas_pop_node(), and mas_pop_node() may return addresses that should not be used. Fix it by initializing node_count only for new nodes.
Fixes: 54a611b60590 ("Maple Tree: add new data structure") Signed-off-by: Peng Zhang zhangpeng.00@bytedance.com Cc: stable@vger.kernel.org
lib/maple_tree.c | 16 ++++------------ 1 file changed, 4 insertions(+), 12 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 65fd861b30e1..9e25b3215803 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1249,26 +1249,18 @@ static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp) node = mas->alloc; node->request_count = 0; while (requested) {
max_req = MAPLE_ALLOC_SLOTS;if (node->node_count) {unsigned int offset = node->node_count;slots = (void **)&node->slot[offset];max_req -= offset;} else {slots = (void **)&node->slot;}
max_req = MAPLE_ALLOC_SLOTS - node->node_count;slots = (void **)&node->slot[node->node_count];Thanks, this is much cleaner.
max_req = min(requested, max_req); count = mt_alloc_bulk(gfp, max_req, slots); if (!count) goto nomem_bulk;
if (node->node_count == 0)node->slot[0]->node_count = 0;
node->node_count = 0;node->request_count = 0;Why are we not clearing request_count anymore?
Because the node pointed to by the variable "node" must not be the head node of the linked list at this time, we only need to maintain the information of the head node.
requested -= count;} mas->alloc->total = allocated; -- 2.20.1
* Peng Zhang perlyzhang@gmail.com [230410 08:58]:
在 2023/4/10 20:43, Liam R. Howlett 写道:
- Peng Zhang zhangpeng.00@bytedance.com [230407 00:10]:
In mas_alloc_nodes(), there is such a piece of code: while (requested) { ... node->node_count = 0; ... }
You don't need to quote code in your commit message since it is available in the change log or in the file itself.
Ok, I will change it in the next version.
"node->node_count = 0" means to initialize the node_count field of the new node, but the node may not be a new node. It may be a node that existed before and node_count has a value, setting it to 0 will cause a memory leak. At this time, mas->alloc->total will be greater than the actual number of nodes in the linked list, which may cause many other errors. For example, out-of-bounds access in mas_pop_node(), and mas_pop_node() may return addresses that should not be used. Fix it by initializing node_count only for new nodes.
Fixes: 54a611b60590 ("Maple Tree: add new data structure") Signed-off-by: Peng Zhang zhangpeng.00@bytedance.com Cc: stable@vger.kernel.org
lib/maple_tree.c | 16 ++++------------ 1 file changed, 4 insertions(+), 12 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 65fd861b30e1..9e25b3215803 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1249,26 +1249,18 @@ static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp) node = mas->alloc; node->request_count = 0; while (requested) {
max_req = MAPLE_ALLOC_SLOTS;if (node->node_count) {unsigned int offset = node->node_count;slots = (void **)&node->slot[offset];max_req -= offset;} else {slots = (void **)&node->slot;}
max_req = MAPLE_ALLOC_SLOTS - node->node_count;slots = (void **)&node->slot[node->node_count];Thanks, this is much cleaner.
max_req = min(requested, max_req); count = mt_alloc_bulk(gfp, max_req, slots); if (!count) goto nomem_bulk;
if (node->node_count == 0)node->slot[0]->node_count = 0;
node->node_count = 0;node->request_count = 0;Why are we not clearing request_count anymore?
Because the node pointed to by the variable "node" must not be the head node of the linked list at this time, we only need to maintain the information of the head node.
Right, at this time it is not the head node, but could it become the head node with invalid data? I think it can, because we don't explicitly set it in mas_pop_node()?
In any case, be sure to mention that you make a change like this in the change log, like "Drop setting the resquest_count as it is unnecessary because.." in a new paragraph, so that it is not missed.
requested -= count;} mas->alloc->total = allocated; -- 2.20.1
在 2023/4/10 21:12, Liam R. Howlett 写道:
- Peng Zhang perlyzhang@gmail.com [230410 08:58]:
在 2023/4/10 20:43, Liam R. Howlett 写道:
- Peng Zhang zhangpeng.00@bytedance.com [230407 00:10]:
In mas_alloc_nodes(), there is such a piece of code: while (requested) { ... node->node_count = 0; ... }
You don't need to quote code in your commit message since it is available in the change log or in the file itself.
Ok, I will change it in the next version.
"node->node_count = 0" means to initialize the node_count field of the new node, but the node may not be a new node. It may be a node that existed before and node_count has a value, setting it to 0 will cause a memory leak. At this time, mas->alloc->total will be greater than the actual number of nodes in the linked list, which may cause many other errors. For example, out-of-bounds access in mas_pop_node(), and mas_pop_node() may return addresses that should not be used. Fix it by initializing node_count only for new nodes.
Fixes: 54a611b60590 ("Maple Tree: add new data structure") Signed-off-by: Peng Zhang zhangpeng.00@bytedance.com Cc: stable@vger.kernel.org
lib/maple_tree.c | 16 ++++------------ 1 file changed, 4 insertions(+), 12 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 65fd861b30e1..9e25b3215803 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1249,26 +1249,18 @@ static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp) node = mas->alloc; node->request_count = 0; while (requested) {
max_req = MAPLE_ALLOC_SLOTS;if (node->node_count) {unsigned int offset = node->node_count;slots = (void **)&node->slot[offset];max_req -= offset;} else {slots = (void **)&node->slot;}
max_req = MAPLE_ALLOC_SLOTS - node->node_count;slots = (void **)&node->slot[node->node_count];Thanks, this is much cleaner.
max_req = min(requested, max_req); count = mt_alloc_bulk(gfp, max_req, slots); if (!count) goto nomem_bulk;
if (node->node_count == 0)node->slot[0]->node_count = 0; node->node_count += count; allocated += count; node = node->slot[0];
node->node_count = 0;node->request_count = 0;Why are we not clearing request_count anymore?
Because the node pointed to by the variable "node" must not be the head node of the linked list at this time, we only need to maintain the information of the head node.
Right, at this time it is not the head node, but could it become the head node with invalid data? I think it can, because we don't explicitly set it in mas_pop_node()?
1. Actually in mas_pop_node(), when a node becomes the head node, we initialize its total field and request_count field.
2. The total field and request_count field of any non-head node, even if we initialize it, cannot be considered a valid value. Imagine if the request_count of the head node is changed, then we don't actually change the request_count of the non-head nodes, so it is an invalid value anyway.
In any case, be sure to mention that you make a change like this in the change log, like "Drop setting the resquest_count as it is unnecessary because.." in a new paragraph, so that it is not missed.
I thought it was a small change that wasn't written in the changelog. In the next version and any future patches, I will write down the details of any changes.
Thanks.
requested -= count; } mas->alloc->total = allocated;-- 2.20.1
* Peng Zhang perlyzhang@gmail.com [230410 09:28]:
在 2023/4/10 21:12, Liam R. Howlett 写道:
- Peng Zhang perlyzhang@gmail.com [230410 08:58]:
在 2023/4/10 20:43, Liam R. Howlett 写道:
- Peng Zhang zhangpeng.00@bytedance.com [230407 00:10]:
In mas_alloc_nodes(), there is such a piece of code: while (requested) { ... node->node_count = 0; ... }
You don't need to quote code in your commit message since it is available in the change log or in the file itself.
Ok, I will change it in the next version.
"node->node_count = 0" means to initialize the node_count field of the new node, but the node may not be a new node. It may be a node that existed before and node_count has a value, setting it to 0 will cause a memory leak. At this time, mas->alloc->total will be greater than the actual number of nodes in the linked list, which may cause many other errors. For example, out-of-bounds access in mas_pop_node(), and mas_pop_node() may return addresses that should not be used. Fix it by initializing node_count only for new nodes.
Fixes: 54a611b60590 ("Maple Tree: add new data structure") Signed-off-by: Peng Zhang zhangpeng.00@bytedance.com Cc: stable@vger.kernel.org
lib/maple_tree.c | 16 ++++------------ 1 file changed, 4 insertions(+), 12 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 65fd861b30e1..9e25b3215803 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1249,26 +1249,18 @@ static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp) node = mas->alloc; node->request_count = 0; while (requested) {
max_req = MAPLE_ALLOC_SLOTS;if (node->node_count) {unsigned int offset = node->node_count;slots = (void **)&node->slot[offset];max_req -= offset;} else {slots = (void **)&node->slot;}
max_req = MAPLE_ALLOC_SLOTS - node->node_count;slots = (void **)&node->slot[node->node_count];Thanks, this is much cleaner.
max_req = min(requested, max_req); count = mt_alloc_bulk(gfp, max_req, slots); if (!count) goto nomem_bulk;
if (node->node_count == 0)node->slot[0]->node_count = 0; node->node_count += count; allocated += count; node = node->slot[0];
node->node_count = 0;node->request_count = 0;Why are we not clearing request_count anymore?
Because the node pointed to by the variable "node" must not be the head node of the linked list at this time, we only need to maintain the information of the head node.
Right, at this time it is not the head node, but could it become the head node with invalid data? I think it can, because we don't explicitly set it in mas_pop_node()?
- Actually in mas_pop_node(), when a node becomes the head node,
we initialize its total field and request_count field.
Only if there is a request_count to begin with, right?
- The total field and request_count field of any non-head node,
even if we initialize it, cannot be considered a valid value. Imagine if the request_count of the head node is changed, then we don't actually change the request_count of the non-head nodes, so it is an invalid value anyway.
When we pop a node, we record the requested value and only initialize it to the recorded value + 1 if it wasn't zero. So if there are no requests, we don't initialize it.
This works because of the zeroing of that request_count that you removed here. But it was, as you pointed out, not always using the right node. I think this needs to be moved to your new 'if' statement.
In any case, be sure to mention that you make a change like this in the change log, like "Drop setting the resquest_count as it is unnecessary because.." in a new paragraph, so that it is not missed.
I thought it was a small change that wasn't written in the changelog. In the next version and any future patches, I will write down the details of any changes.
Thanks.
requested -= count; } mas->alloc->total = allocated;-- 2.20.1
在 2023/4/10 23:00, Liam R. Howlett 写道:
- Peng Zhang perlyzhang@gmail.com [230410 09:28]:
在 2023/4/10 21:12, Liam R. Howlett 写道:
- Peng Zhang perlyzhang@gmail.com [230410 08:58]:
在 2023/4/10 20:43, Liam R. Howlett 写道:
- Peng Zhang zhangpeng.00@bytedance.com [230407 00:10]:
In mas_alloc_nodes(), there is such a piece of code: while (requested) { ... node->node_count = 0; ... }
You don't need to quote code in your commit message since it is available in the change log or in the file itself.
Ok, I will change it in the next version.
"node->node_count = 0" means to initialize the node_count field of the new node, but the node may not be a new node. It may be a node that existed before and node_count has a value, setting it to 0 will cause a memory leak. At this time, mas->alloc->total will be greater than the actual number of nodes in the linked list, which may cause many other errors. For example, out-of-bounds access in mas_pop_node(), and mas_pop_node() may return addresses that should not be used. Fix it by initializing node_count only for new nodes.
Fixes: 54a611b60590 ("Maple Tree: add new data structure") Signed-off-by: Peng Zhang zhangpeng.00@bytedance.com Cc: stable@vger.kernel.org
lib/maple_tree.c | 16 ++++------------ 1 file changed, 4 insertions(+), 12 deletions(-)diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 65fd861b30e1..9e25b3215803 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1249,26 +1249,18 @@ static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp) node = mas->alloc; node->request_count = 0; while (requested) {
max_req = MAPLE_ALLOC_SLOTS;if (node->node_count) {unsigned int offset = node->node_count;slots = (void **)&node->slot[offset];max_req -= offset;} else {slots = (void **)&node->slot;}
max_req = MAPLE_ALLOC_SLOTS - node->node_count;slots = (void **)&node->slot[node->node_count];Thanks, this is much cleaner.
max_req = min(requested, max_req); count = mt_alloc_bulk(gfp, max_req, slots); if (!count) goto nomem_bulk;
if (node->node_count == 0)node->slot[0]->node_count = 0; node->node_count += count; allocated += count; node = node->slot[0];
node->node_count = 0;node->request_count = 0;Why are we not clearing request_count anymore?
Because the node pointed to by the variable "node" must not be the head node of the linked list at this time, we only need to maintain the information of the head node.
Right, at this time it is not the head node, but could it become the head node with invalid data? I think it can, because we don't explicitly set it in mas_pop_node()?
- Actually in mas_pop_node(), when a node becomes the head node,
we initialize its total field and request_count field.
Only if there is a request_count to begin with, right?
- The total field and request_count field of any non-head node,
even if we initialize it, cannot be considered a valid value. Imagine if the request_count of the head node is changed, then we don't actually change the request_count of the non-head nodes, so it is an invalid value anyway.
When we pop a node, we record the requested value and only initialize it to the recorded value + 1 if it wasn't zero. So if there are no requests, we don't initialize it.
Yes, you are right. I neglected that if request_count is equal to 0, the request_count field of the new head node will not be set. There are many implementation details of maple_tree, which is quite error-prone. I will modify it in the next version.
Thanks.
This works because of the zeroing of that request_count that you removed here. But it was, as you pointed out, not always using the right node. I think this needs to be moved to your new 'if' statement.
In any case, be sure to mention that you make a change like this in the change log, like "Drop setting the resquest_count as it is unnecessary because.." in a new paragraph, so that it is not missed.
I thought it was a small change that wasn't written in the changelog. In the next version and any future patches, I will write down the details of any changes.
Thanks.
requested -= count; } mas->alloc->total = allocated;-- 2.20.1
linux-stable-mirror@lists.linaro.org
-
Liam R. Howlett -
Peng Zhang -
Peng Zhang