| Message ID | 20230217134422.14116-4-dakr@redhat.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | DRM GPUVA Manager & Nouveau VM_BIND UAPI | expand |
* Danilo Krummrich <dakr@redhat.com> [230217 08:44]: > Split up the MA_STATE() macro such that components using the maple tree > can easily inherit from struct ma_state and build custom tree walk > macros to hide their internals from users. > > Example: > > struct sample_iter { > struct ma_state mas; > struct sample_mgr *mgr; > struct sample_entry *entry; > }; > > \#define SAMPLE_ITER(name, __mgr) \ > struct sample_iter name = { \ > .mas = __MA_STATE(&(__mgr)->mt, 0, 0), > .mgr = __mgr, > .entry = NULL, > } I see this patch is to allow for anonymous maple states, this looks good. I've a lengthy comment about the iterator that I'm adding here to head off anyone that may copy your example below. > > \#define sample_iter_for_each_range(it__, start__, end__) \ > for ((it__).mas.index = start__, (it__).entry = mas_find(&(it__).mas, end__ - 1); \ > (it__).entry; (it__).entry = mas_find(&(it__).mas, end__ - 1)) I see you've added something like the above in your patch set as well. I'd like to point out that the index isn't the only state information that needs to be altered here, and in fact, this could go very wrong. The maple state has a node and an offset within that node. If you set the index to lower than the current position of your iterator and call mas_find() then what happens is somewhat undefined. I expect you will get the wrong value (most likely either the current value or the very next one that the iterator is already pointing to). I believe you have been using a fresh maple state for each iterator in your patches, but I haven't had a deep look into your code yet. We have methods of resetting the iterator and set the range (mas_set() and mas_set_range()) which are safe for what you are doing, but they will start the walk from the root node to the index again. So, if you know what you are doing is safe, then the way you have written it will work, but it's worth mentioning that this could occur. It is also worth pointing out that it would be much safer to use a function to do the above so you get type safety.. and I was asked to add this to the VMA interface by Linus [1], which is on its way upstream [2]. 1. https://lore.kernel.org/linux-mm/CAHk-=wg9WQXBGkNdKD2bqocnN73rDswuWsavBB7T-tekykEn_A@mail.gmail.com/ 2. https://lore.kernel.org/linux-mm/20230120162650.984577-1-Liam.Howlett@oracle.com/ > > Signed-off-by: Danilo Krummrich <dakr@redhat.com> > --- > include/linux/maple_tree.h | 7 +++++-- > 1 file changed, 5 insertions(+), 2 deletions(-) > > diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h > index e594db58a0f1..ca04c900e51a 100644 > --- a/include/linux/maple_tree.h > +++ b/include/linux/maple_tree.h > @@ -424,8 +424,8 @@ struct ma_wr_state { > #define MA_ERROR(err) \ > ((struct maple_enode *)(((unsigned long)err << 2) | 2UL)) > > -#define MA_STATE(name, mt, first, end) \ > - struct ma_state name = { \ > +#define __MA_STATE(mt, first, end) \ > + { \ > .tree = mt, \ > .index = first, \ > .last = end, \ > @@ -435,6 +435,9 @@ struct ma_wr_state { > .alloc = NULL, \ > } > > +#define MA_STATE(name, mt, first, end) \ > + struct ma_state name = __MA_STATE(mt, first, end) > + > #define MA_WR_STATE(name, ma_state, wr_entry) \ > struct ma_wr_state name = { \ > .mas = ma_state, \ > -- > 2.39.1 >
On Fri, Feb 17, 2023 at 02:44:09PM +0100, Danilo Krummrich wrote: > \#define SAMPLE_ITER(name, __mgr) \ > struct sample_iter name = { \ > .mas = __MA_STATE(&(__mgr)->mt, 0, 0), This is usually called MA_STATE_INIT() > #define sample_iter_for_each_range(it__, start__, end__) \ > for ((it__).mas.index = start__, (it__).entry = mas_find(&(it__).mas, end__ - 1); \ > (it__).entry; (it__).entry = mas_find(&(it__).mas, end__ - 1)) This is a bad iterator design. It's usually best to do this: struct sample *sample; SAMPLE_ITERATOR(si, min); sample_iter_for_each(&si, sample, max) { frob(mgr, sample); } I don't mind splitting apart MA_STATE_INIT from MA_STATE, and if you do that, we can also use it in VMA_ITERATOR.
On 2/17/23 20:45, Matthew Wilcox wrote: > On Fri, Feb 17, 2023 at 02:44:09PM +0100, Danilo Krummrich wrote: >> \#define SAMPLE_ITER(name, __mgr) \ >> struct sample_iter name = { \ >> .mas = __MA_STATE(&(__mgr)->mt, 0, 0), > > This is usually called MA_STATE_INIT() Yep, that's better. > >> #define sample_iter_for_each_range(it__, start__, end__) \ >> for ((it__).mas.index = start__, (it__).entry = mas_find(&(it__).mas, end__ - 1); \ >> (it__).entry; (it__).entry = mas_find(&(it__).mas, end__ - 1)) > > This is a bad iterator design. It's usually best to do this: > > struct sample *sample; > SAMPLE_ITERATOR(si, min); > > sample_iter_for_each(&si, sample, max) { > frob(mgr, sample); > } > The reason why I don't set index (and max) within SAMPLE_ITER() is that the range to iterate might not yet be known at that time, so I thought it could just be set in sample_iter_for_each_range(). However, I see that this might prevail users to assume that it's safe to iterate a range based on the same iterator instance multiple times though. Instead users should maybe move the tree walk to another function once the range is known. The reason for the payload structure to be part of the iterator is that I have two maple trees in the GPUVA manager and hence two different payload types. Within the iterator structure they're just within a union allowing me to implement the tree walk macro just once rather than twice. Anyway, I feel like your approach looks cleaner, hence I'll change it. > I don't mind splitting apart MA_STATE_INIT from MA_STATE, and if you > do that, we can also use it in VMA_ITERATOR. >
On 2/17/23 19:34, Liam R. Howlett wrote: > * Danilo Krummrich <dakr@redhat.com> [230217 08:44]: >> Split up the MA_STATE() macro such that components using the maple tree >> can easily inherit from struct ma_state and build custom tree walk >> macros to hide their internals from users. >> >> Example: >> >> struct sample_iter { >> struct ma_state mas; >> struct sample_mgr *mgr; >> struct sample_entry *entry; >> }; >> >> \#define SAMPLE_ITER(name, __mgr) \ >> struct sample_iter name = { \ >> .mas = __MA_STATE(&(__mgr)->mt, 0, 0), >> .mgr = __mgr, >> .entry = NULL, >> } > > I see this patch is to allow for anonymous maple states, this looks > good. > > I've a lengthy comment about the iterator that I'm adding here to head > off anyone that may copy your example below. > >> >> \#define sample_iter_for_each_range(it__, start__, end__) \ >> for ((it__).mas.index = start__, (it__).entry = mas_find(&(it__).mas, end__ - 1); \ >> (it__).entry; (it__).entry = mas_find(&(it__).mas, end__ - 1)) > > I see you've added something like the above in your patch set as well. > I'd like to point out that the index isn't the only state information > that needs to be altered here, and in fact, this could go very wrong. > > The maple state has a node and an offset within that node. If you set > the index to lower than the current position of your iterator and call > mas_find() then what happens is somewhat undefined. I expect you will > get the wrong value (most likely either the current value or the very > next one that the iterator is already pointing to). I believe you have > been using a fresh maple state for each iterator in your patches, but I > haven't had a deep look into your code yet. Yes, I'm aware that I'd need to reset the whole iterator in order to re-use it. Regarding the other considerations of the iterator design please see my answer to Matthew. > > We have methods of resetting the iterator and set the range (mas_set() > and mas_set_range()) which are safe for what you are doing, but they > will start the walk from the root node to the index again. > > So, if you know what you are doing is safe, then the way you have > written it will work, but it's worth mentioning that this could occur. > > It is also worth pointing out that it would be much safer to use a > function to do the above so you get type safety.. and I was asked to add > this to the VMA interface by Linus [1], which is on its way upstream [2]. > > 1. https://lore.kernel.org/linux-mm/CAHk-=wg9WQXBGkNdKD2bqocnN73rDswuWsavBB7T-tekykEn_A@mail.gmail.com/ > 2. https://lore.kernel.org/linux-mm/20230120162650.984577-1-Liam.Howlett@oracle.com/ You mean having wrappers like sample_find() instead of directly using mas_find()? > >> >> Signed-off-by: Danilo Krummrich <dakr@redhat.com> >> --- >> include/linux/maple_tree.h | 7 +++++-- >> 1 file changed, 5 insertions(+), 2 deletions(-) >> >> diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h >> index e594db58a0f1..ca04c900e51a 100644 >> --- a/include/linux/maple_tree.h >> +++ b/include/linux/maple_tree.h >> @@ -424,8 +424,8 @@ struct ma_wr_state { >> #define MA_ERROR(err) \ >> ((struct maple_enode *)(((unsigned long)err << 2) | 2UL)) >> >> -#define MA_STATE(name, mt, first, end) \ >> - struct ma_state name = { \ >> +#define __MA_STATE(mt, first, end) \ >> + { \ >> .tree = mt, \ >> .index = first, \ >> .last = end, \ >> @@ -435,6 +435,9 @@ struct ma_wr_state { >> .alloc = NULL, \ >> } >> >> +#define MA_STATE(name, mt, first, end) \ >> + struct ma_state name = __MA_STATE(mt, first, end) >> + >> #define MA_WR_STATE(name, ma_state, wr_entry) \ >> struct ma_wr_state name = { \ >> .mas = ma_state, \ >> -- >> 2.39.1 >> >
* Danilo Krummrich <dakr@redhat.com> [230220 09:38]: > On 2/17/23 19:34, Liam R. Howlett wrote: > > * Danilo Krummrich <dakr@redhat.com> [230217 08:44]: > > > Split up the MA_STATE() macro such that components using the maple tree > > > can easily inherit from struct ma_state and build custom tree walk > > > macros to hide their internals from users. > > > > > > Example: > > > > > > struct sample_iter { > > > struct ma_state mas; > > > struct sample_mgr *mgr; > > > struct sample_entry *entry; > > > }; > > > > > > \#define SAMPLE_ITER(name, __mgr) \ > > > struct sample_iter name = { \ > > > .mas = __MA_STATE(&(__mgr)->mt, 0, 0), > > > .mgr = __mgr, > > > .entry = NULL, > > > } > > > > I see this patch is to allow for anonymous maple states, this looks > > good. > > > > I've a lengthy comment about the iterator that I'm adding here to head > > off anyone that may copy your example below. > > > > > > > > \#define sample_iter_for_each_range(it__, start__, end__) \ > > > for ((it__).mas.index = start__, (it__).entry = mas_find(&(it__).mas, end__ - 1); \ > > > (it__).entry; (it__).entry = mas_find(&(it__).mas, end__ - 1)) > > > > I see you've added something like the above in your patch set as well. > > I'd like to point out that the index isn't the only state information > > that needs to be altered here, and in fact, this could go very wrong. > > > > The maple state has a node and an offset within that node. If you set > > the index to lower than the current position of your iterator and call > > mas_find() then what happens is somewhat undefined. I expect you will > > get the wrong value (most likely either the current value or the very > > next one that the iterator is already pointing to). I believe you have > > been using a fresh maple state for each iterator in your patches, but I > > haven't had a deep look into your code yet. > > Yes, I'm aware that I'd need to reset the whole iterator in order to re-use > it. Okay, good. The way you have it written makes it unsafe to just call without knowledge of the state and that will probably end poorly over the long run. If it's always starting from MAS_START then it's probably safer to just initialize when you want to use it to the correct start address. > > Regarding the other considerations of the iterator design please see my > answer to Matthew. > > > > > We have methods of resetting the iterator and set the range (mas_set() > > and mas_set_range()) which are safe for what you are doing, but they > > will start the walk from the root node to the index again. > > > > So, if you know what you are doing is safe, then the way you have > > written it will work, but it's worth mentioning that this could occur. > > > > It is also worth pointing out that it would be much safer to use a > > function to do the above so you get type safety.. and I was asked to add > > this to the VMA interface by Linus [1], which is on its way upstream [2]. > > > > 1. https://lore.kernel.org/linux-mm/CAHk-=wg9WQXBGkNdKD2bqocnN73rDswuWsavBB7T-tekykEn_A@mail.gmail.com/ > > 2. https://lore.kernel.org/linux-mm/20230120162650.984577-1-Liam.Howlett@oracle.com/ > > You mean having wrappers like sample_find() instead of directly using > mas_find()? I'm not sure you need to go that low level, but I would ensure I have a store/load function that ensures the correct type being put in/read from are correct on compile - especially since you seem to have two trees to track two different sets of things. That iterator is probably safe since the type is defined within itself. > > > > > > > > > Signed-off-by: Danilo Krummrich <dakr@redhat.com> > > > --- > > > include/linux/maple_tree.h | 7 +++++-- > > > 1 file changed, 5 insertions(+), 2 deletions(-) > > > > > > diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h > > > index e594db58a0f1..ca04c900e51a 100644 > > > --- a/include/linux/maple_tree.h > > > +++ b/include/linux/maple_tree.h > > > @@ -424,8 +424,8 @@ struct ma_wr_state { > > > #define MA_ERROR(err) \ > > > ((struct maple_enode *)(((unsigned long)err << 2) | 2UL)) > > > -#define MA_STATE(name, mt, first, end) \ > > > - struct ma_state name = { \ > > > +#define __MA_STATE(mt, first, end) \ > > > + { \ > > > .tree = mt, \ > > > .index = first, \ > > > .last = end, \ > > > @@ -435,6 +435,9 @@ struct ma_wr_state { > > > .alloc = NULL, \ > > > } > > > +#define MA_STATE(name, mt, first, end) \ > > > + struct ma_state name = __MA_STATE(mt, first, end) > > > + > > > #define MA_WR_STATE(name, ma_state, wr_entry) \ > > > struct ma_wr_state name = { \ > > > .mas = ma_state, \ > > > -- > > > 2.39.1 > > > > > >
diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index e594db58a0f1..ca04c900e51a 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -424,8 +424,8 @@ struct ma_wr_state { #define MA_ERROR(err) \ ((struct maple_enode *)(((unsigned long)err << 2) | 2UL)) -#define MA_STATE(name, mt, first, end) \ - struct ma_state name = { \ +#define __MA_STATE(mt, first, end) \ + { \ .tree = mt, \ .index = first, \ .last = end, \ @@ -435,6 +435,9 @@ struct ma_wr_state { .alloc = NULL, \ } +#define MA_STATE(name, mt, first, end) \ + struct ma_state name = __MA_STATE(mt, first, end) + #define MA_WR_STATE(name, ma_state, wr_entry) \ struct ma_wr_state name = { \ .mas = ma_state, \
Split up the MA_STATE() macro such that components using the maple tree can easily inherit from struct ma_state and build custom tree walk macros to hide their internals from users. Example: struct sample_iter { struct ma_state mas; struct sample_mgr *mgr; struct sample_entry *entry; }; \#define SAMPLE_ITER(name, __mgr) \ struct sample_iter name = { \ .mas = __MA_STATE(&(__mgr)->mt, 0, 0), .mgr = __mgr, .entry = NULL, } \#define sample_iter_for_each_range(it__, start__, end__) \ for ((it__).mas.index = start__, (it__).entry = mas_find(&(it__).mas, end__ - 1); \ (it__).entry; (it__).entry = mas_find(&(it__).mas, end__ - 1)) Signed-off-by: Danilo Krummrich <dakr@redhat.com> --- include/linux/maple_tree.h | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-)