| Message ID | 20230407040718.99064-2-zhangpeng.00@bytedance.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | [1/2] maple_tree: Add a test case to check maple_alloc | expand |
* 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 += count; > allocated += count; > node = node->slot[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 >
* 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()? 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()? > 1. 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? > > 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. 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()? >> 1. 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? > >> 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. > 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 >>>>>>
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;
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(-)