| Message ID | 20240814161944.55347-17-sidhartha.kumar@oracle.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | Introduce a store type enum for the Maple tree | expand |
On Wed, Aug 14, 2024 at 12:19:43PM -0400, Sidhartha Kumar wrote: >Users of mas_store_prealloc() enter this function with nodes already >preallocated. This means the store type must be already set. We can then >remove the call to mas_wr_store_type() and initialize the write state to >continue the partial walk that was done when determining the store type. > May I ask what is the partial walk here means? It is the mas_wr_walk() in mas_wr_store_type() which is stopped because of it is spanning write? I may lost some background, so the assumption here is mas_wr_store_type() has already been invoked and the store type has been decided, right? >Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com> >Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com> >--- > lib/maple_tree.c | 18 +++++++++++++----- > 1 file changed, 13 insertions(+), 5 deletions(-) > >diff --git a/lib/maple_tree.c b/lib/maple_tree.c >index 8c1a1a483395..73ce63d9c3a0 100644 >--- a/lib/maple_tree.c >+++ b/lib/maple_tree.c >@@ -3979,9 +3979,6 @@ static inline void mas_wr_end_piv(struct ma_wr_state *wr_mas) > wr_mas->end_piv = wr_mas->pivots[wr_mas->offset_end]; > else > wr_mas->end_piv = wr_mas->mas->max; >- >- if (!wr_mas->entry) >- mas_wr_extend_null(wr_mas); > } > > static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas) >@@ -5532,8 +5529,19 @@ void mas_store_prealloc(struct ma_state *mas, void *entry) > { > MA_WR_STATE(wr_mas, mas, entry); > >- mas_wr_prealloc_setup(&wr_mas); >- mas_wr_store_type(&wr_mas); >+ if (mas->store_type == wr_store_root) { >+ mas_wr_prealloc_setup(&wr_mas); >+ goto store; >+ } >+ >+ mas_wr_walk_descend(&wr_mas); This one does not descend the tree, just locate the offset in a node and adjust min/max. So not look like to continue the partial walk to me. >+ if (mas->store_type != wr_spanning_store) { >+ /* set wr_mas->content to current slot */ >+ wr_mas.content = mas_slot_locked(mas, wr_mas.slots, mas->offset); >+ mas_wr_end_piv(&wr_mas); If not a spanning write, the previous walk should reach a leaf node, right? I am not sure why we don't need to check extend null here. Because we have already done it? >+ } >+ >+store: > trace_ma_write(__func__, mas, 0, entry); > mas_wr_store_entry(&wr_mas); > MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas)); >-- >2.46.0 >
On 10/23/24 9:20 PM, Wei Yang wrote: > On Wed, Aug 14, 2024 at 12:19:43PM -0400, Sidhartha Kumar wrote: >> Users of mas_store_prealloc() enter this function with nodes already >> preallocated. This means the store type must be already set. We can then >> remove the call to mas_wr_store_type() and initialize the write state to >> continue the partial walk that was done when determining the store type. >> > May I ask what is the partial walk here means? > > It is the mas_wr_walk() in mas_wr_store_type() which is stopped because of it > is spanning write? Yes, this is what I meant by the partial walk that's already been started. It's the walk done by mas_wr_store_type(). > I may lost some background, so the assumption here is mas_wr_store_type() has > already been invoked and the store type has been decided, right? Ya users of mas_store_prealloc() should have already called mas_preallocate() which does: mas->store_type = mas_wr_store_type(&wr_mas); request = mas_prealloc_calc(&wr_mas, entry); to set the store type and allocate the nodes. >> Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com> >> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com> >> --- >> lib/maple_tree.c | 18 +++++++++++++----- >> 1 file changed, 13 insertions(+), 5 deletions(-) >> >> diff --git a/lib/maple_tree.c b/lib/maple_tree.c >> index 8c1a1a483395..73ce63d9c3a0 100644 >> --- a/lib/maple_tree.c >> +++ b/lib/maple_tree.c >> @@ -3979,9 +3979,6 @@ static inline void mas_wr_end_piv(struct ma_wr_state *wr_mas) >> wr_mas->end_piv = wr_mas->pivots[wr_mas->offset_end]; >> else >> wr_mas->end_piv = wr_mas->mas->max; >> - >> - if (!wr_mas->entry) >> - mas_wr_extend_null(wr_mas); >> } >> >> static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas) >> @@ -5532,8 +5529,19 @@ void mas_store_prealloc(struct ma_state *mas, void *entry) >> { >> MA_WR_STATE(wr_mas, mas, entry); >> >> - mas_wr_prealloc_setup(&wr_mas); >> - mas_wr_store_type(&wr_mas); >> + if (mas->store_type == wr_store_root) { >> + mas_wr_prealloc_setup(&wr_mas); >> + goto store; >> + } >> + >> + mas_wr_walk_descend(&wr_mas); > This one does not descend the tree, just locate the offset in a node and > adjust min/max. So not look like to continue the partial walk to me. > >> + if (mas->store_type != wr_spanning_store) { >> + /* set wr_mas->content to current slot */ >> + wr_mas.content = mas_slot_locked(mas, wr_mas.slots, mas->offset); >> + mas_wr_end_piv(&wr_mas); > If not a spanning write, the previous walk should reach a leaf node, right? Ya that's true. > I am not sure why we don't need to check extend null here. Because we have > already done it? Ya we extend null in mas_wr_store_type() which has already been called at this point. /* At this point, we are at the leaf node that needs to be altered. */ mas_wr_end_piv(wr_mas); if (!wr_mas->entry) mas_wr_extend_null(wr_mas); Thanks, Sid >> + } >> + >> +store: >> trace_ma_write(__func__, mas, 0, entry); >> mas_wr_store_entry(&wr_mas); >> MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas)); >> -- >> 2.46.0 >>
On Fri, Oct 25, 2024 at 03:54:04PM -0400, Sid Kumar wrote: > >On 10/23/24 9:20 PM, Wei Yang wrote: >> On Wed, Aug 14, 2024 at 12:19:43PM -0400, Sidhartha Kumar wrote: >> > Users of mas_store_prealloc() enter this function with nodes already >> > preallocated. This means the store type must be already set. We can then >> > remove the call to mas_wr_store_type() and initialize the write state to >> > continue the partial walk that was done when determining the store type. >> > >> May I ask what is the partial walk here means? >> >> It is the mas_wr_walk() in mas_wr_store_type() which is stopped because of it >> is spanning write? > >Yes, this is what I meant by the partial walk that's already been started. >It's the walk done by mas_wr_store_type(). > >> I may lost some background, so the assumption here is mas_wr_store_type() has >> already been invoked and the store type has been decided, right? > >Ya users of mas_store_prealloc() should have already called mas_preallocate() >which does: > > mas->store_type = mas_wr_store_type(&wr_mas); > request = mas_prealloc_calc(&wr_mas, entry); > >to set the store type and allocate the nodes. > > >> > Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com> >> > Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com> >> > --- >> > lib/maple_tree.c | 18 +++++++++++++----- >> > 1 file changed, 13 insertions(+), 5 deletions(-) >> > >> > diff --git a/lib/maple_tree.c b/lib/maple_tree.c >> > index 8c1a1a483395..73ce63d9c3a0 100644 >> > --- a/lib/maple_tree.c >> > +++ b/lib/maple_tree.c >> > @@ -3979,9 +3979,6 @@ static inline void mas_wr_end_piv(struct ma_wr_state *wr_mas) >> > wr_mas->end_piv = wr_mas->pivots[wr_mas->offset_end]; >> > else >> > wr_mas->end_piv = wr_mas->mas->max; >> > - >> > - if (!wr_mas->entry) >> > - mas_wr_extend_null(wr_mas); >> > } >> > >> > static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas) >> > @@ -5532,8 +5529,19 @@ void mas_store_prealloc(struct ma_state *mas, void *entry) >> > { >> > MA_WR_STATE(wr_mas, mas, entry); >> > >> > - mas_wr_prealloc_setup(&wr_mas); >> > - mas_wr_store_type(&wr_mas); >> > + if (mas->store_type == wr_store_root) { >> > + mas_wr_prealloc_setup(&wr_mas); >> > + goto store; >> > + } >> > + >> > + mas_wr_walk_descend(&wr_mas); >> This one does not descend the tree, just locate the offset in a node and >> adjust min/max. So not look like to continue the partial walk to me. >> >> > + if (mas->store_type != wr_spanning_store) { >> > + /* set wr_mas->content to current slot */ >> > + wr_mas.content = mas_slot_locked(mas, wr_mas.slots, mas->offset); >> > + mas_wr_end_piv(&wr_mas); >> If not a spanning write, the previous walk should reach a leaf node, right? > >Ya that's true. > >> I am not sure why we don't need to check extend null here. Because we have >> already done it? > > >Ya we extend null in mas_wr_store_type() which has already been called at >this point. > > > /* At this point, we are at the leaf node that needs to be altered. */ > mas_wr_end_piv(wr_mas); > if (!wr_mas->entry) > mas_wr_extend_null(wr_mas); > >Thanks, Hmm... if we have already done this, why we need to do mas_wr_end_piv() again? > >Sid > >> > + } >> > + >> > +store: >> > trace_ma_write(__func__, mas, 0, entry); >> > mas_wr_store_entry(&wr_mas); >> > MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas)); >> > -- >> > 2.46.0 >> >
On 10/25/24 7:58 PM, Wei Yang wrote: > On Fri, Oct 25, 2024 at 03:54:04PM -0400, Sid Kumar wrote: >> On 10/23/24 9:20 PM, Wei Yang wrote: >>> On Wed, Aug 14, 2024 at 12:19:43PM -0400, Sidhartha Kumar wrote: >>>> Users of mas_store_prealloc() enter this function with nodes already >>>> preallocated. This means the store type must be already set. We can then >>>> remove the call to mas_wr_store_type() and initialize the write state to >>>> continue the partial walk that was done when determining the store type. >>>> >>> May I ask what is the partial walk here means? >>> >>> It is the mas_wr_walk() in mas_wr_store_type() which is stopped because of it >>> is spanning write? >> Yes, this is what I meant by the partial walk that's already been started. >> It's the walk done by mas_wr_store_type(). >> >>> I may lost some background, so the assumption here is mas_wr_store_type() has >>> already been invoked and the store type has been decided, right? >> Ya users of mas_store_prealloc() should have already called mas_preallocate() >> which does: >> >> mas->store_type = mas_wr_store_type(&wr_mas); >> request = mas_prealloc_calc(&wr_mas, entry); >> >> to set the store type and allocate the nodes. >> >> >>>> Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com> >>>> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com> >>>> --- >>>> lib/maple_tree.c | 18 +++++++++++++----- >>>> 1 file changed, 13 insertions(+), 5 deletions(-) >>>> >>>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c >>>> index 8c1a1a483395..73ce63d9c3a0 100644 >>>> --- a/lib/maple_tree.c >>>> +++ b/lib/maple_tree.c >>>> @@ -3979,9 +3979,6 @@ static inline void mas_wr_end_piv(struct ma_wr_state *wr_mas) >>>> wr_mas->end_piv = wr_mas->pivots[wr_mas->offset_end]; >>>> else >>>> wr_mas->end_piv = wr_mas->mas->max; >>>> - >>>> - if (!wr_mas->entry) >>>> - mas_wr_extend_null(wr_mas); >>>> } >>>> >>>> static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas) >>>> @@ -5532,8 +5529,19 @@ void mas_store_prealloc(struct ma_state *mas, void *entry) >>>> { >>>> MA_WR_STATE(wr_mas, mas, entry); >>>> >>>> - mas_wr_prealloc_setup(&wr_mas); >>>> - mas_wr_store_type(&wr_mas); >>>> + if (mas->store_type == wr_store_root) { >>>> + mas_wr_prealloc_setup(&wr_mas); >>>> + goto store; >>>> + } >>>> + >>>> + mas_wr_walk_descend(&wr_mas); >>> This one does not descend the tree, just locate the offset in a node and >>> adjust min/max. So not look like to continue the partial walk to me. >>> >>>> + if (mas->store_type != wr_spanning_store) { >>>> + /* set wr_mas->content to current slot */ >>>> + wr_mas.content = mas_slot_locked(mas, wr_mas.slots, mas->offset); >>>> + mas_wr_end_piv(&wr_mas); >>> If not a spanning write, the previous walk should reach a leaf node, right? >> Ya that's true. >> >>> I am not sure why we don't need to check extend null here. Because we have >>> already done it? >> >> Ya we extend null in mas_wr_store_type() which has already been called at >> this point. >> >> >> /* At this point, we are at the leaf node that needs to be altered. */ >> mas_wr_end_piv(wr_mas); >> if (!wr_mas->entry) >> mas_wr_extend_null(wr_mas); >> >> Thanks, > Hmm... if we have already done this, why we need to do mas_wr_end_piv() again? The maple write state here is local to this function: void mas_store_prealloc(struct ma_state *mas, void *entry) { MA_WR_STATE(wr_mas, mas, entry); so we don't retain the wr_end information from the previous call to mas_preallocate() and have to repeat it here. The write state is not currently exposed so have to call mas_wr_end_piv() again. Thanks, Sid > >> Sid >> >>>> + } >>>> + >>>> +store: >>>> trace_ma_write(__func__, mas, 0, entry); >>>> mas_wr_store_entry(&wr_mas); >>>> MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas)); >>>> -- >>>> 2.46.0 >>>>
On Tue, Oct 29, 2024 at 11:46:58AM -0400, Sid Kumar wrote: > >On 10/25/24 7:58 PM, Wei Yang wrote: >> On Fri, Oct 25, 2024 at 03:54:04PM -0400, Sid Kumar wrote: >> > On 10/23/24 9:20 PM, Wei Yang wrote: >> > > On Wed, Aug 14, 2024 at 12:19:43PM -0400, Sidhartha Kumar wrote: >> > > > Users of mas_store_prealloc() enter this function with nodes already >> > > > preallocated. This means the store type must be already set. We can then >> > > > remove the call to mas_wr_store_type() and initialize the write state to >> > > > continue the partial walk that was done when determining the store type. >> > > > >> > > May I ask what is the partial walk here means? >> > > >> > > It is the mas_wr_walk() in mas_wr_store_type() which is stopped because of it >> > > is spanning write? >> > Yes, this is what I meant by the partial walk that's already been started. >> > It's the walk done by mas_wr_store_type(). >> > >> > > I may lost some background, so the assumption here is mas_wr_store_type() has >> > > already been invoked and the store type has been decided, right? >> > Ya users of mas_store_prealloc() should have already called mas_preallocate() >> > which does: >> > >> > mas->store_type = mas_wr_store_type(&wr_mas); >> > request = mas_prealloc_calc(&wr_mas, entry); >> > >> > to set the store type and allocate the nodes. >> > >> > >> > > > Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com> >> > > > Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com> >> > > > --- >> > > > lib/maple_tree.c | 18 +++++++++++++----- >> > > > 1 file changed, 13 insertions(+), 5 deletions(-) >> > > > >> > > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c >> > > > index 8c1a1a483395..73ce63d9c3a0 100644 >> > > > --- a/lib/maple_tree.c >> > > > +++ b/lib/maple_tree.c >> > > > @@ -3979,9 +3979,6 @@ static inline void mas_wr_end_piv(struct ma_wr_state *wr_mas) >> > > > wr_mas->end_piv = wr_mas->pivots[wr_mas->offset_end]; >> > > > else >> > > > wr_mas->end_piv = wr_mas->mas->max; >> > > > - >> > > > - if (!wr_mas->entry) >> > > > - mas_wr_extend_null(wr_mas); >> > > > } >> > > > >> > > > static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas) >> > > > @@ -5532,8 +5529,19 @@ void mas_store_prealloc(struct ma_state *mas, void *entry) >> > > > { >> > > > MA_WR_STATE(wr_mas, mas, entry); >> > > > >> > > > - mas_wr_prealloc_setup(&wr_mas); >> > > > - mas_wr_store_type(&wr_mas); >> > > > + if (mas->store_type == wr_store_root) { >> > > > + mas_wr_prealloc_setup(&wr_mas); >> > > > + goto store; >> > > > + } >> > > > + >> > > > + mas_wr_walk_descend(&wr_mas); >> > > This one does not descend the tree, just locate the offset in a node and >> > > adjust min/max. So not look like to continue the partial walk to me. >> > > >> > > > + if (mas->store_type != wr_spanning_store) { >> > > > + /* set wr_mas->content to current slot */ >> > > > + wr_mas.content = mas_slot_locked(mas, wr_mas.slots, mas->offset); >> > > > + mas_wr_end_piv(&wr_mas); >> > > If not a spanning write, the previous walk should reach a leaf node, right? >> > Ya that's true. >> > >> > > I am not sure why we don't need to check extend null here. Because we have >> > > already done it? >> > >> > Ya we extend null in mas_wr_store_type() which has already been called at >> > this point. >> > >> > >> > /* At this point, we are at the leaf node that needs to be altered. */ >> > mas_wr_end_piv(wr_mas); >> > if (!wr_mas->entry) >> > mas_wr_extend_null(wr_mas); >> > >> > Thanks, >> Hmm... if we have already done this, why we need to do mas_wr_end_piv() again? > >The maple write state here is local to this function: > >void mas_store_prealloc(struct ma_state *mas, void *entry) >{ > MA_WR_STATE(wr_mas, mas, entry); > >so we don't retain the wr_end information from the previous call to >mas_preallocate() and have to repeat it here. The write state is not >currently exposed so have to call mas_wr_end_piv() again. > Thanks, I missed this point. >Thanks, > >Sid > > >> >> > Sid >> > >> > > > + } >> > > > + >> > > > +store: >> > > > trace_ma_write(__func__, mas, 0, entry); >> > > > mas_wr_store_entry(&wr_mas); >> > > > MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas)); >> > > > -- >> > > > 2.46.0 >> > > >
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 8c1a1a483395..73ce63d9c3a0 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3979,9 +3979,6 @@ static inline void mas_wr_end_piv(struct ma_wr_state *wr_mas) wr_mas->end_piv = wr_mas->pivots[wr_mas->offset_end]; else wr_mas->end_piv = wr_mas->mas->max; - - if (!wr_mas->entry) - mas_wr_extend_null(wr_mas); } static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas) @@ -5532,8 +5529,19 @@ void mas_store_prealloc(struct ma_state *mas, void *entry) { MA_WR_STATE(wr_mas, mas, entry); - mas_wr_prealloc_setup(&wr_mas); - mas_wr_store_type(&wr_mas); + if (mas->store_type == wr_store_root) { + mas_wr_prealloc_setup(&wr_mas); + goto store; + } + + mas_wr_walk_descend(&wr_mas); + if (mas->store_type != wr_spanning_store) { + /* set wr_mas->content to current slot */ + wr_mas.content = mas_slot_locked(mas, wr_mas.slots, mas->offset); + mas_wr_end_piv(&wr_mas); + } + +store: trace_ma_write(__func__, mas, 0, entry); mas_wr_store_entry(&wr_mas); MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas));