| Message ID | 20230505174204.2665599-33-Liam.Howlett@oracle.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | Maple tree mas_{next,prev}_range() and cleanup | expand |
在 2023/5/6 01:42, Liam R. Howlett 写道: > When there is a single entry tree (range of 0-0 pointing to an entry), > then ensure the limit is either 0-0 or 1-oo, depending on where the user > walks. Ensure the correct node setting as well; either MAS_ROOT or > MAS_NONE. > > Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com> > --- > lib/maple_tree.c | 21 +++++++++++---------- > 1 file changed, 11 insertions(+), 10 deletions(-) > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > index f060c71965c0d..914399519cf54 100644 > --- a/lib/maple_tree.c > +++ b/lib/maple_tree.c > @@ -5022,24 +5022,25 @@ void *mas_walk(struct ma_state *mas) > { > void *entry; > > + if (mas_is_none(mas) || mas_is_paused(mas)) if (mas_is_none(mas) || mas_is_paused(mas) || mas_is_ptr(mas)) > + mas->node = MAS_START; Hi, Liam There is an issue that it cannot pass the user space test program with this patchset. I tested it based on 47cba14ce6fc4(linux-next/master). The reason is that mas_walk() does not handle the state that mas is root. The root cause is that mas_start() only handles the start state, and returns NULL for the root state. When encountering the root state, we can reset to start so that it is handled in mas_start(). log: BUG at check_state_handling:3076 (1) maple_tree(0x55d6a9838ca0) flags 1, height 0 root 0x1234500 0: 0x1234500 Pass: 453406336 Run:453406337 maple: ../../../lib/test_maple_tree.c:3076: check_state_handling: Assertion `0' failed. Aborted (core dumped) > retry: > entry = mas_state_walk(mas); > - if (mas_is_start(mas)) > + if (mas_is_start(mas)) { > goto retry; > - > - if (mas_is_ptr(mas)) { > + } else if (mas_is_none(mas)) { > + mas->index = 0; > + mas->last = ULONG_MAX; > + } else if (mas_is_ptr(mas)) { > if (!mas->index) { > mas->last = 0; > - } else { > - mas->index = 1; > - mas->last = ULONG_MAX; > + return entry; > } > - return entry; > - } > > - if (mas_is_none(mas)) { > - mas->index = 0; > + mas->index = 1; > mas->last = ULONG_MAX; > + mas->node = MAS_NONE; > + return NULL; > } > > return entry;
* Peng Zhang <zhangpeng.00@bytedance.com> [230509 08:39]: > > > 在 2023/5/6 01:42, Liam R. Howlett 写道: > > When there is a single entry tree (range of 0-0 pointing to an entry), > > then ensure the limit is either 0-0 or 1-oo, depending on where the user > > walks. Ensure the correct node setting as well; either MAS_ROOT or > > MAS_NONE. > > > > Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com> > > --- > > lib/maple_tree.c | 21 +++++++++++---------- > > 1 file changed, 11 insertions(+), 10 deletions(-) > > > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > > index f060c71965c0d..914399519cf54 100644 > > --- a/lib/maple_tree.c > > +++ b/lib/maple_tree.c > > @@ -5022,24 +5022,25 @@ void *mas_walk(struct ma_state *mas) > > { > > void *entry; > > + if (mas_is_none(mas) || mas_is_paused(mas)) > if (mas_is_none(mas) || mas_is_paused(mas) || mas_is_ptr(mas)) > > + mas->node = MAS_START; > > Hi, Liam > There is an issue that it cannot pass the user space test program > with this patchset. > I tested it based on 47cba14ce6fc4(linux-next/master). > > The reason is that mas_walk() does not handle the state that mas is > root. The root cause is that mas_start() only handles the start state, > and returns NULL for the root state. When encountering the root state, > we can reset to start so that it is handled in mas_start(). Thanks. I'll have a look and adjust v3. > > log: > BUG at check_state_handling:3076 (1) > maple_tree(0x55d6a9838ca0) flags 1, height 0 root 0x1234500 > 0: 0x1234500 > Pass: 453406336 Run:453406337 > maple: ../../../lib/test_maple_tree.c:3076: check_state_handling: Assertion > `0' failed. > Aborted (core dumped) > > retry: > > entry = mas_state_walk(mas); > > - if (mas_is_start(mas)) > > + if (mas_is_start(mas)) { > > goto retry; > > - > > - if (mas_is_ptr(mas)) { > > + } else if (mas_is_none(mas)) { > > + mas->index = 0; > > + mas->last = ULONG_MAX; > > + } else if (mas_is_ptr(mas)) { > > if (!mas->index) { > > mas->last = 0; > > - } else { > > - mas->index = 1; > > - mas->last = ULONG_MAX; > > + return entry; > > } > > - return entry; > > - } > > - if (mas_is_none(mas)) { > > - mas->index = 0; > > + mas->index = 1; > > mas->last = ULONG_MAX; > > + mas->node = MAS_NONE; > > + return NULL; > > } > > return entry;
* Liam R. Howlett <Liam.Howlett@Oracle.com> [230512 11:54]: > * Peng Zhang <zhangpeng.00@bytedance.com> [230509 08:39]: > > > > > > 在 2023/5/6 01:42, Liam R. Howlett 写道: > > > When there is a single entry tree (range of 0-0 pointing to an entry), > > > then ensure the limit is either 0-0 or 1-oo, depending on where the user > > > walks. Ensure the correct node setting as well; either MAS_ROOT or > > > MAS_NONE. > > > > > > Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com> > > > --- > > > lib/maple_tree.c | 21 +++++++++++---------- > > > 1 file changed, 11 insertions(+), 10 deletions(-) > > > > > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > > > index f060c71965c0d..914399519cf54 100644 > > > --- a/lib/maple_tree.c > > > +++ b/lib/maple_tree.c > > > @@ -5022,24 +5022,25 @@ void *mas_walk(struct ma_state *mas) > > > { > > > void *entry; > > > + if (mas_is_none(mas) || mas_is_paused(mas)) > > if (mas_is_none(mas) || mas_is_paused(mas) || mas_is_ptr(mas)) > > > + mas->node = MAS_START; > > > > Hi, Liam > > There is an issue that it cannot pass the user space test program > > with this patchset. > > I tested it based on 47cba14ce6fc4(linux-next/master). > > > > The reason is that mas_walk() does not handle the state that mas is > > root. The root cause is that mas_start() only handles the start state, > > and returns NULL for the root state. When encountering the root state, > > we can reset to start so that it is handled in mas_start(). > > Thanks. I'll have a look and adjust v3. This was introduced with the fix for the race condition between v1 and v2. It is probably best to reset to MAS_START instead of the potential stale data. > > > > > log: > > BUG at check_state_handling:3076 (1) > > maple_tree(0x55d6a9838ca0) flags 1, height 0 root 0x1234500 > > 0: 0x1234500 > > Pass: 453406336 Run:453406337 > > maple: ../../../lib/test_maple_tree.c:3076: check_state_handling: Assertion > > `0' failed. > > Aborted (core dumped) > > > retry: > > > entry = mas_state_walk(mas); > > > - if (mas_is_start(mas)) > > > + if (mas_is_start(mas)) { > > > goto retry; > > > - > > > - if (mas_is_ptr(mas)) { > > > + } else if (mas_is_none(mas)) { > > > + mas->index = 0; > > > + mas->last = ULONG_MAX; > > > + } else if (mas_is_ptr(mas)) { > > > if (!mas->index) { > > > mas->last = 0; > > > - } else { > > > - mas->index = 1; > > > - mas->last = ULONG_MAX; > > > + return entry; > > > } > > > - return entry; > > > - } > > > - if (mas_is_none(mas)) { > > > - mas->index = 0; > > > + mas->index = 1; > > > mas->last = ULONG_MAX; > > > + mas->node = MAS_NONE; > > > + return NULL; > > > } > > > return entry;
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index f060c71965c0d..914399519cf54 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -5022,24 +5022,25 @@ void *mas_walk(struct ma_state *mas) { void *entry; + if (mas_is_none(mas) || mas_is_paused(mas)) + mas->node = MAS_START; retry: entry = mas_state_walk(mas); - if (mas_is_start(mas)) + if (mas_is_start(mas)) { goto retry; - - if (mas_is_ptr(mas)) { + } else if (mas_is_none(mas)) { + mas->index = 0; + mas->last = ULONG_MAX; + } else if (mas_is_ptr(mas)) { if (!mas->index) { mas->last = 0; - } else { - mas->index = 1; - mas->last = ULONG_MAX; + return entry; } - return entry; - } - if (mas_is_none(mas)) { - mas->index = 0; + mas->index = 1; mas->last = ULONG_MAX; + mas->node = MAS_NONE; + return NULL; } return entry;
When there is a single entry tree (range of 0-0 pointing to an entry), then ensure the limit is either 0-0 or 1-oo, depending on where the user walks. Ensure the correct node setting as well; either MAS_ROOT or MAS_NONE. Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com> --- lib/maple_tree.c | 21 +++++++++++---------- 1 file changed, 11 insertions(+), 10 deletions(-)