Add a test case to check whether the number of maple_alloc structures is
actually equal to mas->alloc->total.
Signed-off-by: Peng Zhang <[email protected]>
---
tools/testing/radix-tree/maple.c | 24 ++++++++++++++++++++++++
1 file changed, 24 insertions(+)
diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index 958ee9bdb316..26389e0dcfff 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -55,6 +55,28 @@ struct rcu_reader_struct {
struct rcu_test_struct2 *test;
};
+static int get_alloc_node_count(struct ma_state *mas)
+{
+ int count = 1;
+ struct maple_alloc *node = mas->alloc;
+
+ if (!node || ((unsigned long)node & 0x1))
+ return 0;
+ while (node->node_count) {
+ count += node->node_count;
+ node = node->slot[0];
+ }
+ return count;
+}
+
+static void check_mas_alloc_node_count(struct ma_state *mas)
+{
+ mas_node_count_gfp(mas, MAPLE_ALLOC_SLOTS + 1, GFP_KERNEL);
+ mas_node_count_gfp(mas, MAPLE_ALLOC_SLOTS + 3, GFP_KERNEL);
+ MT_BUG_ON(mas->tree, get_alloc_node_count(mas) != mas->alloc->total);
+ mas_destroy(mas);
+}
+
/*
* check_new_node() - Check the creation of new nodes and error path
* verification.
@@ -69,6 +91,8 @@ static noinline void check_new_node(struct maple_tree *mt)
MA_STATE(mas, mt, 0, 0);
+ check_mas_alloc_node_count(&mas);
+
/* Try allocating 3 nodes */
mtree_lock(mt);
mt_set_non_kernel(0);
--
2.20.1
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 <[email protected]>
Cc: <[email protected]>
---
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;
--
2.20.1
* Peng Zhang <[email protected]> [230407 00:09]:
> Add a test case to check whether the number of maple_alloc structures is
> actually equal to mas->alloc->total.
Please have a look at check_new_node() as there are tests there already
and see if it covers what you are trying to test.
>
> Signed-off-by: Peng Zhang <[email protected]>
> ---
> tools/testing/radix-tree/maple.c | 24 ++++++++++++++++++++++++
> 1 file changed, 24 insertions(+)
>
> diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
> index 958ee9bdb316..26389e0dcfff 100644
> --- a/tools/testing/radix-tree/maple.c
> +++ b/tools/testing/radix-tree/maple.c
> @@ -55,6 +55,28 @@ struct rcu_reader_struct {
> struct rcu_test_struct2 *test;
> };
>
> +static int get_alloc_node_count(struct ma_state *mas)
> +{
> + int count = 1;
> + struct maple_alloc *node = mas->alloc;
> +
> + if (!node || ((unsigned long)node & 0x1))
> + return 0;
> + while (node->node_count) {
> + count += node->node_count;
> + node = node->slot[0];
> + }
> + return count;
> +}
> +
> +static void check_mas_alloc_node_count(struct ma_state *mas)
> +{
> + mas_node_count_gfp(mas, MAPLE_ALLOC_SLOTS + 1, GFP_KERNEL);
> + mas_node_count_gfp(mas, MAPLE_ALLOC_SLOTS + 3, GFP_KERNEL);
> + MT_BUG_ON(mas->tree, get_alloc_node_count(mas) != mas->alloc->total);
> + mas_destroy(mas);
> +}
> +
> /*
> * check_new_node() - Check the creation of new nodes and error path
> * verification.
> @@ -69,6 +91,8 @@ static noinline void check_new_node(struct maple_tree *mt)
>
> MA_STATE(mas, mt, 0, 0);
>
> + check_mas_alloc_node_count(&mas);
> +
> /* Try allocating 3 nodes */
> mtree_lock(mt);
> mt_set_non_kernel(0);
> --
> 2.20.1
>
* Liam R. Howlett <[email protected]> [230407 23:17]:
> * Peng Zhang <[email protected]> [230407 00:09]:
> > Add a test case to check whether the number of maple_alloc structures is
> > actually equal to mas->alloc->total.
>
> Please have a look at check_new_node() as there are tests there already
> and see if it covers what you are trying to test.
Sorry, sent this too fast. I'll have a look after the holiday here.
>
> >
> > Signed-off-by: Peng Zhang <[email protected]>
> > ---
> > tools/testing/radix-tree/maple.c | 24 ++++++++++++++++++++++++
> > 1 file changed, 24 insertions(+)
> >
> > diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
> > index 958ee9bdb316..26389e0dcfff 100644
> > --- a/tools/testing/radix-tree/maple.c
> > +++ b/tools/testing/radix-tree/maple.c
> > @@ -55,6 +55,28 @@ struct rcu_reader_struct {
> > struct rcu_test_struct2 *test;
> > };
> >
> > +static int get_alloc_node_count(struct ma_state *mas)
> > +{
> > + int count = 1;
> > + struct maple_alloc *node = mas->alloc;
> > +
> > + if (!node || ((unsigned long)node & 0x1))
> > + return 0;
> > + while (node->node_count) {
> > + count += node->node_count;
> > + node = node->slot[0];
> > + }
> > + return count;
> > +}
> > +
> > +static void check_mas_alloc_node_count(struct ma_state *mas)
> > +{
> > + mas_node_count_gfp(mas, MAPLE_ALLOC_SLOTS + 1, GFP_KERNEL);
> > + mas_node_count_gfp(mas, MAPLE_ALLOC_SLOTS + 3, GFP_KERNEL);
> > + MT_BUG_ON(mas->tree, get_alloc_node_count(mas) != mas->alloc->total);
> > + mas_destroy(mas);
> > +}
> > +
> > /*
> > * check_new_node() - Check the creation of new nodes and error path
> > * verification.
> > @@ -69,6 +91,8 @@ static noinline void check_new_node(struct maple_tree *mt)
> >
> > MA_STATE(mas, mt, 0, 0);
> >
> > + check_mas_alloc_node_count(&mas);
> > +
> > /* Try allocating 3 nodes */
> > mtree_lock(mt);
> > mt_set_non_kernel(0);
> > --
> > 2.20.1
> >
* Peng Zhang <[email protected]> [230407 00:09]:
> Add a test case to check whether the number of maple_alloc structures is
> actually equal to mas->alloc->total.
Thanks for the test case. Can you please send the code to fix the issue
first in the future? This way the verification code can be used to
bisect any issues.
>
> Signed-off-by: Peng Zhang <[email protected]>
> ---
> tools/testing/radix-tree/maple.c | 24 ++++++++++++++++++++++++
> 1 file changed, 24 insertions(+)
>
> diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
> index 958ee9bdb316..26389e0dcfff 100644
> --- a/tools/testing/radix-tree/maple.c
> +++ b/tools/testing/radix-tree/maple.c
> @@ -55,6 +55,28 @@ struct rcu_reader_struct {
> struct rcu_test_struct2 *test;
> };
>
> +static int get_alloc_node_count(struct ma_state *mas)
> +{
> + int count = 1;
> + struct maple_alloc *node = mas->alloc;
> +
> + if (!node || ((unsigned long)node & 0x1))
> + return 0;
> + while (node->node_count) {
> + count += node->node_count;
> + node = node->slot[0];
> + }
> + return count;
> +}
> +
> +static void check_mas_alloc_node_count(struct ma_state *mas)
> +{
> + mas_node_count_gfp(mas, MAPLE_ALLOC_SLOTS + 1, GFP_KERNEL);
> + mas_node_count_gfp(mas, MAPLE_ALLOC_SLOTS + 3, GFP_KERNEL);
> + MT_BUG_ON(mas->tree, get_alloc_node_count(mas) != mas->alloc->total);
> + mas_destroy(mas);
> +}
> +
> /*
> * check_new_node() - Check the creation of new nodes and error path
> * verification.
> @@ -69,6 +91,8 @@ static noinline void check_new_node(struct maple_tree *mt)
>
> MA_STATE(mas, mt, 0, 0);
>
> + check_mas_alloc_node_count(&mas);
> +
> /* Try allocating 3 nodes */
> mtree_lock(mt);
> mt_set_non_kernel(0);
> --
> 2.20.1
>
* Peng Zhang <[email protected]> [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 <[email protected]>
> Cc: <[email protected]>
> ---
> 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
>
在 2023/4/10 20:43, Liam R. Howlett 写道:
> * Peng Zhang <[email protected]> [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 <[email protected]>
>> Cc: <[email protected]>
>> ---
>> 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.
>
>> requested -= count;
>> }
>> mas->alloc->total = allocated;
>> --
>> 2.20.1
>>
在 2023/4/10 20:41, Liam R. Howlett 写道:
> * Peng Zhang <[email protected]> [230407 00:09]:
>> Add a test case to check whether the number of maple_alloc structures is
>> actually equal to mas->alloc->total.
> Thanks for the test case. Can you please send the code to fix the issue
> first in the future? This way the verification code can be used to
> bisect any issues.
Ok, I will exchange the order of the two patches in the next version.
>
>> Signed-off-by: Peng Zhang <[email protected]>
>> ---
>> tools/testing/radix-tree/maple.c | 24 ++++++++++++++++++++++++
>> 1 file changed, 24 insertions(+)
>>
>> diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
>> index 958ee9bdb316..26389e0dcfff 100644
>> --- a/tools/testing/radix-tree/maple.c
>> +++ b/tools/testing/radix-tree/maple.c
>> @@ -55,6 +55,28 @@ struct rcu_reader_struct {
>> struct rcu_test_struct2 *test;
>> };
>>
>> +static int get_alloc_node_count(struct ma_state *mas)
>> +{
>> + int count = 1;
>> + struct maple_alloc *node = mas->alloc;
>> +
>> + if (!node || ((unsigned long)node & 0x1))
>> + return 0;
>> + while (node->node_count) {
>> + count += node->node_count;
>> + node = node->slot[0];
>> + }
>> + return count;
>> +}
>> +
>> +static void check_mas_alloc_node_count(struct ma_state *mas)
>> +{
>> + mas_node_count_gfp(mas, MAPLE_ALLOC_SLOTS + 1, GFP_KERNEL);
>> + mas_node_count_gfp(mas, MAPLE_ALLOC_SLOTS + 3, GFP_KERNEL);
>> + MT_BUG_ON(mas->tree, get_alloc_node_count(mas) != mas->alloc->total);
>> + mas_destroy(mas);
>> +}
>> +
>> /*
>> * check_new_node() - Check the creation of new nodes and error path
>> * verification.
>> @@ -69,6 +91,8 @@ static noinline void check_new_node(struct maple_tree *mt)
>>
>> MA_STATE(mas, mt, 0, 0);
>>
>> + check_mas_alloc_node_count(&mas);
>> +
>> /* Try allocating 3 nodes */
>> mtree_lock(mt);
>> mt_set_non_kernel(0);
>> --
>> 2.20.1
>>
* Peng Zhang <[email protected]> [230410 08:58]:
>
> 在 2023/4/10 20:43, Liam R. Howlett 写道:
> > * Peng Zhang <[email protected]> [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 <[email protected]>
> > > Cc: <[email protected]>
> > > ---
> > > 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 <[email protected]> [230410 08:58]:
>> 在 2023/4/10 20:43, Liam R. Howlett 写道:
>>> * Peng Zhang <[email protected]> [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 <[email protected]>
>>>> Cc: <[email protected]>
>>>> ---
>>>> 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 <[email protected]> [230410 09:28]:
>
> 在 2023/4/10 21:12, Liam R. Howlett 写道:
> > * Peng Zhang <[email protected]> [230410 08:58]:
> > > 在 2023/4/10 20:43, Liam R. Howlett 写道:
> > > > * Peng Zhang <[email protected]> [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 <[email protected]>
> > > > > Cc: <[email protected]>
> > > > > ---
> > > > > 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 <[email protected]> [230410 09:28]:
>> 在 2023/4/10 21:12, Liam R. Howlett 写道:
>>> * Peng Zhang <[email protected]> [230410 08:58]:
>>>> 在 2023/4/10 20:43, Liam R. Howlett 写道:
>>>>> * Peng Zhang <[email protected]> [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 <[email protected]>
>>>>>> Cc: <[email protected]>
>>>>>> ---
>>>>>> 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
>>>>>>