[PATCH 1/2] rcu: introduce list_last_or_null_rcu

[PATCH 1/2] rcu: introduce list_last_or_null_rcu

[Dan Streetman]

Add list_last_or_null_rcu(), to simplify getting the last entry from a
rcu-protected list.  The standard list_last_entry() can't be used as it
is not rcu-protected; the list may be modified concurrently.  And the
->prev pointer can't be used, as only the ->next pointers are protected
by rcu.

This simply iterates forward through the entire list, to get to the last
entry.  If the list is empty, it returns NULL.

Signed-off-by: Dan Streetman <ddstreet@ieee.org>
---
 include/linux/rculist.h | 21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)

diff --git a/include/linux/rculist.h b/include/linux/rculist.h
index a18b16f..954fde5 100644
--- a/include/linux/rculist.h
+++ b/include/linux/rculist.h
@@ -293,6 +293,27 @@ static inline void list_splice_init_rcu(struct list_head *list,
 })
 
 /**
+ * list_last_or_null_rcu - get the last element from a list
+ * @ptr:        the list head to take the element from.
+ * @type:       the type of the struct this is embedded in.
+ * @member:     the name of the list_head within the struct.
+ *
+ * Note that if the list is empty, it returns NULL.
+ *
+ * This primitive may safely run concurrently with the _rcu list-mutation
+ * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
+ */
+#define list_last_or_null_rcu(ptr, type, member) \
+({ \
+	struct list_head *__ptr = (ptr); \
+	struct list_head *__last = __ptr; \
+	struct list_head *__entry = list_next_rcu(__ptr); \
+	for (; __entry != __ptr; __entry = list_next_rcu(__entry)) \
+		__last = __entry; \
+	likely(__ptr != __last) ? list_entry_rcu(__last, type, member) : NULL; \
+})
+
+/**
  * list_for_each_entry_rcu	-	iterate over rcu list of given type
  * @pos:	the type * to use as a loop cursor.
  * @head:	the head for your list.
-- 
2.1.0

[PATCH 2/2] list: introduce list_last_entry_or_null

[Dan Streetman]

non-rcu variant of list_last_or_null_rcu

Signed-off-by: Dan Streetman <ddstreet@ieee.org>
---
 include/linux/list.h | 11 +++++++++++
 1 file changed, 11 insertions(+)

diff --git a/include/linux/list.h b/include/linux/list.h
index feb773c..38577f89 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -385,6 +385,17 @@ static inline void list_splice_tail_init(struct list_head *list,
 	(!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL)
 
 /**
+ * list_last_entry_or_null - get the last element from a list
+ * @ptr:	the list head to take the element from.
+ * @type:	the type of the struct this is embedded in.
+ * @member:	the name of the list_head within the struct.
+ *
+ * Note that if the list is empty, it returns NULL.
+ */
+#define list_last_entry_or_null(ptr, type, member) \
+	(!list_empty(ptr) ? list_last_entry(ptr, type, member) : NULL)
+
+/**
  * list_next_entry - get the next element in list
  * @pos:	the type * to cursor
  * @member:	the name of the list_head within the struct.
-- 
2.1.0

Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[josh]

On Thu, May 28, 2015 at 04:35:27PM -0400, Dan Streetman wrote:
> Add list_last_or_null_rcu(), to simplify getting the last entry from a
> rcu-protected list.  The standard list_last_entry() can't be used as it
> is not rcu-protected; the list may be modified concurrently.  And the
> ->prev pointer can't be used, as only the ->next pointers are protected
> by rcu.
> 
> This simply iterates forward through the entire list, to get to the last
> entry.  If the list is empty, it returns NULL.
> 
> Signed-off-by: Dan Streetman <ddstreet@ieee.org>

The list iteration functions are macros because they introduce a loop
with attached loop block.  For this, is there any reason not to make it
an inline function instead of a macro?

>  include/linux/rculist.h | 21 +++++++++++++++++++++
>  1 file changed, 21 insertions(+)
> 
> diff --git a/include/linux/rculist.h b/include/linux/rculist.h
> index a18b16f..954fde5 100644
> --- a/include/linux/rculist.h
> +++ b/include/linux/rculist.h
> @@ -293,6 +293,27 @@ static inline void list_splice_init_rcu(struct list_head *list,
>  })
>  
>  /**
> + * list_last_or_null_rcu - get the last element from a list
> + * @ptr:        the list head to take the element from.
> + * @type:       the type of the struct this is embedded in.
> + * @member:     the name of the list_head within the struct.
> + *
> + * Note that if the list is empty, it returns NULL.
> + *
> + * This primitive may safely run concurrently with the _rcu list-mutation
> + * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
> + */
> +#define list_last_or_null_rcu(ptr, type, member) \
> +({ \
> +	struct list_head *__ptr = (ptr); \
> +	struct list_head *__last = __ptr; \
> +	struct list_head *__entry = list_next_rcu(__ptr); \
> +	for (; __entry != __ptr; __entry = list_next_rcu(__entry)) \
> +		__last = __entry; \
> +	likely(__ptr != __last) ? list_entry_rcu(__last, type, member) : NULL; \
> +})
> +
> +/**
>   * list_for_each_entry_rcu	-	iterate over rcu list of given type
>   * @pos:	the type * to use as a loop cursor.
>   * @head:	the head for your list.
> -- 
> 2.1.0
> 

Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[Dan Streetman]

On Thu, May 28, 2015 at 4:39 PM,  <josh@joshtriplett.org> wrote:
> On Thu, May 28, 2015 at 04:35:27PM -0400, Dan Streetman wrote:
>> Add list_last_or_null_rcu(), to simplify getting the last entry from a
>> rcu-protected list.  The standard list_last_entry() can't be used as it
>> is not rcu-protected; the list may be modified concurrently.  And the
>> ->prev pointer can't be used, as only the ->next pointers are protected
>> by rcu.
>>
>> This simply iterates forward through the entire list, to get to the last
>> entry.  If the list is empty, it returns NULL.
>>
>> Signed-off-by: Dan Streetman <ddstreet@ieee.org>
>
> The list iteration functions are macros because they introduce a loop
> with attached loop block.  For this, is there any reason not to make it
> an inline function instead of a macro?

true, there's no reason i can see not to make it inline, let me send
an updated patch.

>
>>  include/linux/rculist.h | 21 +++++++++++++++++++++
>>  1 file changed, 21 insertions(+)
>>
>> diff --git a/include/linux/rculist.h b/include/linux/rculist.h
>> index a18b16f..954fde5 100644
>> --- a/include/linux/rculist.h
>> +++ b/include/linux/rculist.h
>> @@ -293,6 +293,27 @@ static inline void list_splice_init_rcu(struct list_head *list,
>>  })
>>
>>  /**
>> + * list_last_or_null_rcu - get the last element from a list
>> + * @ptr:        the list head to take the element from.
>> + * @type:       the type of the struct this is embedded in.
>> + * @member:     the name of the list_head within the struct.
>> + *
>> + * Note that if the list is empty, it returns NULL.
>> + *
>> + * This primitive may safely run concurrently with the _rcu list-mutation
>> + * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
>> + */
>> +#define list_last_or_null_rcu(ptr, type, member) \
>> +({ \
>> +     struct list_head *__ptr = (ptr); \
>> +     struct list_head *__last = __ptr; \
>> +     struct list_head *__entry = list_next_rcu(__ptr); \
>> +     for (; __entry != __ptr; __entry = list_next_rcu(__entry)) \
>> +             __last = __entry; \
>> +     likely(__ptr != __last) ? list_entry_rcu(__last, type, member) : NULL; \
>> +})
>> +
>> +/**
>>   * list_for_each_entry_rcu   -       iterate over rcu list of given type
>>   * @pos:     the type * to use as a loop cursor.
>>   * @head:    the head for your list.
>> --
>> 2.1.0
>>

Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[Dan Streetman]

On Thu, May 28, 2015 at 4:42 PM, Dan Streetman <ddstreet@ieee.org> wrote:
> On Thu, May 28, 2015 at 4:39 PM,  <josh@joshtriplett.org> wrote:
>> On Thu, May 28, 2015 at 04:35:27PM -0400, Dan Streetman wrote:
>>> Add list_last_or_null_rcu(), to simplify getting the last entry from a
>>> rcu-protected list.  The standard list_last_entry() can't be used as it
>>> is not rcu-protected; the list may be modified concurrently.  And the
>>> ->prev pointer can't be used, as only the ->next pointers are protected
>>> by rcu.
>>>
>>> This simply iterates forward through the entire list, to get to the last
>>> entry.  If the list is empty, it returns NULL.
>>>
>>> Signed-off-by: Dan Streetman <ddstreet@ieee.org>
>>
>> The list iteration functions are macros because they introduce a loop
>> with attached loop block.  For this, is there any reason not to make it
>> an inline function instead of a macro?
>
> true, there's no reason i can see not to make it inline, let me send
> an updated patch.

ha, as soon as i sent that email, i realized it can't be an inline
function, because the return value is (type *), not a predefined
value.  Of course it could return void*, but unless there's a benefit
of making it an inline function, it seems to me like it would be
better as a #define.

>
>>
>>>  include/linux/rculist.h | 21 +++++++++++++++++++++
>>>  1 file changed, 21 insertions(+)
>>>
>>> diff --git a/include/linux/rculist.h b/include/linux/rculist.h
>>> index a18b16f..954fde5 100644
>>> --- a/include/linux/rculist.h
>>> +++ b/include/linux/rculist.h
>>> @@ -293,6 +293,27 @@ static inline void list_splice_init_rcu(struct list_head *list,
>>>  })
>>>
>>>  /**
>>> + * list_last_or_null_rcu - get the last element from a list
>>> + * @ptr:        the list head to take the element from.
>>> + * @type:       the type of the struct this is embedded in.
>>> + * @member:     the name of the list_head within the struct.
>>> + *
>>> + * Note that if the list is empty, it returns NULL.
>>> + *
>>> + * This primitive may safely run concurrently with the _rcu list-mutation
>>> + * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
>>> + */
>>> +#define list_last_or_null_rcu(ptr, type, member) \
>>> +({ \
>>> +     struct list_head *__ptr = (ptr); \
>>> +     struct list_head *__last = __ptr; \
>>> +     struct list_head *__entry = list_next_rcu(__ptr); \
>>> +     for (; __entry != __ptr; __entry = list_next_rcu(__entry)) \
>>> +             __last = __entry; \
>>> +     likely(__ptr != __last) ? list_entry_rcu(__last, type, member) : NULL; \
>>> +})
>>> +
>>> +/**
>>>   * list_for_each_entry_rcu   -       iterate over rcu list of given type
>>>   * @pos:     the type * to use as a loop cursor.
>>>   * @head:    the head for your list.
>>> --
>>> 2.1.0
>>>

Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[Steven Rostedt]

On Thu, 28 May 2015 16:35:27 -0400
Dan Streetman <ddstreet@ieee.org> wrote:

> Add list_last_or_null_rcu(), to simplify getting the last entry from a
> rcu-protected list.  The standard list_last_entry() can't be used as it
> is not rcu-protected; the list may be modified concurrently.  And the
> ->prev pointer can't be used, as only the ->next pointers are protected
> by rcu.
> 
> This simply iterates forward through the entire list, to get to the last
> entry.  If the list is empty, it returns NULL.

May I asked what this would be used for? It seems awfully inefficient
in its implementation. What use cases would this be for? I hate to add
something like this as a generic function which would encourage people
to use it. Iterating over an entire list to find the last element is
just nasty.

-- Steve

Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[Paul E. McKenney]

On Thu, May 28, 2015 at 04:42:20PM -0400, Dan Streetman wrote:
> On Thu, May 28, 2015 at 4:39 PM,  <josh@joshtriplett.org> wrote:
> > On Thu, May 28, 2015 at 04:35:27PM -0400, Dan Streetman wrote:
> >> Add list_last_or_null_rcu(), to simplify getting the last entry from a
> >> rcu-protected list.  The standard list_last_entry() can't be used as it
> >> is not rcu-protected; the list may be modified concurrently.  And the
> >> ->prev pointer can't be used, as only the ->next pointers are protected
> >> by rcu.
> >>
> >> This simply iterates forward through the entire list, to get to the last
> >> entry.  If the list is empty, it returns NULL.
> >>
> >> Signed-off-by: Dan Streetman <ddstreet@ieee.org>
> >
> > The list iteration functions are macros because they introduce a loop
> > with attached loop block.  For this, is there any reason not to make it
> > an inline function instead of a macro?
> 
> true, there's no reason i can see not to make it inline, let me send
> an updated patch.

Hmmm...  If we can now do type-generic inline functions, it might make
sense to convert some of the others as well.

							Thanx, Paul

> >>  include/linux/rculist.h | 21 +++++++++++++++++++++
> >>  1 file changed, 21 insertions(+)
> >>
> >> diff --git a/include/linux/rculist.h b/include/linux/rculist.h
> >> index a18b16f..954fde5 100644
> >> --- a/include/linux/rculist.h
> >> +++ b/include/linux/rculist.h
> >> @@ -293,6 +293,27 @@ static inline void list_splice_init_rcu(struct list_head *list,
> >>  })
> >>
> >>  /**
> >> + * list_last_or_null_rcu - get the last element from a list
> >> + * @ptr:        the list head to take the element from.
> >> + * @type:       the type of the struct this is embedded in.
> >> + * @member:     the name of the list_head within the struct.
> >> + *
> >> + * Note that if the list is empty, it returns NULL.
> >> + *
> >> + * This primitive may safely run concurrently with the _rcu list-mutation
> >> + * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
> >> + */
> >> +#define list_last_or_null_rcu(ptr, type, member) \
> >> +({ \
> >> +     struct list_head *__ptr = (ptr); \
> >> +     struct list_head *__last = __ptr; \
> >> +     struct list_head *__entry = list_next_rcu(__ptr); \
> >> +     for (; __entry != __ptr; __entry = list_next_rcu(__entry)) \
> >> +             __last = __entry; \
> >> +     likely(__ptr != __last) ? list_entry_rcu(__last, type, member) : NULL; \
> >> +})
> >> +
> >> +/**
> >>   * list_for_each_entry_rcu   -       iterate over rcu list of given type
> >>   * @pos:     the type * to use as a loop cursor.
> >>   * @head:    the head for your list.
> >> --
> >> 2.1.0
> >>
> 

Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[Paul E. McKenney]

On Thu, May 28, 2015 at 04:44:59PM -0400, Dan Streetman wrote:
> On Thu, May 28, 2015 at 4:42 PM, Dan Streetman <ddstreet@ieee.org> wrote:
> > On Thu, May 28, 2015 at 4:39 PM,  <josh@joshtriplett.org> wrote:
> >> On Thu, May 28, 2015 at 04:35:27PM -0400, Dan Streetman wrote:
> >>> Add list_last_or_null_rcu(), to simplify getting the last entry from a
> >>> rcu-protected list.  The standard list_last_entry() can't be used as it
> >>> is not rcu-protected; the list may be modified concurrently.  And the
> >>> ->prev pointer can't be used, as only the ->next pointers are protected
> >>> by rcu.
> >>>
> >>> This simply iterates forward through the entire list, to get to the last
> >>> entry.  If the list is empty, it returns NULL.
> >>>
> >>> Signed-off-by: Dan Streetman <ddstreet@ieee.org>
> >>
> >> The list iteration functions are macros because they introduce a loop
> >> with attached loop block.  For this, is there any reason not to make it
> >> an inline function instead of a macro?
> >
> > true, there's no reason i can see not to make it inline, let me send
> > an updated patch.
> 
> ha, as soon as i sent that email, i realized it can't be an inline
> function, because the return value is (type *), not a predefined
> value.  Of course it could return void*, but unless there's a benefit
> of making it an inline function, it seems to me like it would be
> better as a #define.

Hey, I was hoping...  ;-)

							Thanx, Paul

Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[josh]

On Thu, May 28, 2015 at 04:44:59PM -0400, Dan Streetman wrote:
> On Thu, May 28, 2015 at 4:42 PM, Dan Streetman <ddstreet@ieee.org> wrote:
> > On Thu, May 28, 2015 at 4:39 PM,  <josh@joshtriplett.org> wrote:
> >> On Thu, May 28, 2015 at 04:35:27PM -0400, Dan Streetman wrote:
> >>> Add list_last_or_null_rcu(), to simplify getting the last entry from a
> >>> rcu-protected list.  The standard list_last_entry() can't be used as it
> >>> is not rcu-protected; the list may be modified concurrently.  And the
> >>> ->prev pointer can't be used, as only the ->next pointers are protected
> >>> by rcu.
> >>>
> >>> This simply iterates forward through the entire list, to get to the last
> >>> entry.  If the list is empty, it returns NULL.
> >>>
> >>> Signed-off-by: Dan Streetman <ddstreet@ieee.org>
> >>
> >> The list iteration functions are macros because they introduce a loop
> >> with attached loop block.  For this, is there any reason not to make it
> >> an inline function instead of a macro?
> >
> > true, there's no reason i can see not to make it inline, let me send
> > an updated patch.
> 
> ha, as soon as i sent that email, i realized it can't be an inline
> function, because the return value is (type *), not a predefined
> value.  Of course it could return void*, but unless there's a benefit
> of making it an inline function, it seems to me like it would be
> better as a #define.

Fair enough.  Sigh, C.

- Josh Triplett

Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[Dan Streetman]

On Thu, May 28, 2015 at 5:05 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
> On Thu, 28 May 2015 16:35:27 -0400
> Dan Streetman <ddstreet@ieee.org> wrote:
>
>> Add list_last_or_null_rcu(), to simplify getting the last entry from a
>> rcu-protected list.  The standard list_last_entry() can't be used as it
>> is not rcu-protected; the list may be modified concurrently.  And the
>> ->prev pointer can't be used, as only the ->next pointers are protected
>> by rcu.
>>
>> This simply iterates forward through the entire list, to get to the last
>> entry.  If the list is empty, it returns NULL.
>
> May I asked what this would be used for? It seems awfully inefficient
> in its implementation. What use cases would this be for? I hate to add
> something like this as a generic function which would encourage people
> to use it. Iterating over an entire list to find the last element is
> just nasty.

i have a patch series that will update zswap to be able to change its
parameters at runtime, instead of only at boot time.  To do that, it
creates new "pools" dynamically, and keeps them all in a list, with
only the 1st pool being actively used; any following pools still have
everything that was stored in them, but they aren't added to.  When
zswap has to "shrink" - by telling one of the pools to get rid of 1 or
more items - it picks the last on the list.  Once a pool is empty,
it's removed/freed.

So zswap *could* just manually iterate the list to the last element,
instead of using this new function.  But if rcu lists are ever
improved later on, e.g. if ->prev is somehow rcu-protected as well as
->next, then this function should be faster than manually iterating.

if there's a better rcu-way to get to the last list entry, then we
should definitely use it, although based on my understanding of the
rcu list implementation, you can only iterate forwards, safely
(without locking).

>
> -- Steve
>

Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[Dan Streetman]

On Thu, May 28, 2015 at 5:05 PM, Paul E. McKenney
<paulmck@linux.vnet.ibm.com> wrote:
> On Thu, May 28, 2015 at 04:42:20PM -0400, Dan Streetman wrote:
>> On Thu, May 28, 2015 at 4:39 PM,  <josh@joshtriplett.org> wrote:
>> > On Thu, May 28, 2015 at 04:35:27PM -0400, Dan Streetman wrote:
>> >> Add list_last_or_null_rcu(), to simplify getting the last entry from a
>> >> rcu-protected list.  The standard list_last_entry() can't be used as it
>> >> is not rcu-protected; the list may be modified concurrently.  And the
>> >> ->prev pointer can't be used, as only the ->next pointers are protected
>> >> by rcu.
>> >>
>> >> This simply iterates forward through the entire list, to get to the last
>> >> entry.  If the list is empty, it returns NULL.
>> >>
>> >> Signed-off-by: Dan Streetman <ddstreet@ieee.org>
>> >
>> > The list iteration functions are macros because they introduce a loop
>> > with attached loop block.  For this, is there any reason not to make it
>> > an inline function instead of a macro?
>>
>> true, there's no reason i can see not to make it inline, let me send
>> an updated patch.
>
> Hmmm...  If we can now do type-generic inline functions, it might make
> sense to convert some of the others as well.

oh, ok.  how do we do type-generic inline funcs?  return void*?

>
>                                                         Thanx, Paul
>
>> >>  include/linux/rculist.h | 21 +++++++++++++++++++++
>> >>  1 file changed, 21 insertions(+)
>> >>
>> >> diff --git a/include/linux/rculist.h b/include/linux/rculist.h
>> >> index a18b16f..954fde5 100644
>> >> --- a/include/linux/rculist.h
>> >> +++ b/include/linux/rculist.h
>> >> @@ -293,6 +293,27 @@ static inline void list_splice_init_rcu(struct list_head *list,
>> >>  })
>> >>
>> >>  /**
>> >> + * list_last_or_null_rcu - get the last element from a list
>> >> + * @ptr:        the list head to take the element from.
>> >> + * @type:       the type of the struct this is embedded in.
>> >> + * @member:     the name of the list_head within the struct.
>> >> + *
>> >> + * Note that if the list is empty, it returns NULL.
>> >> + *
>> >> + * This primitive may safely run concurrently with the _rcu list-mutation
>> >> + * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
>> >> + */
>> >> +#define list_last_or_null_rcu(ptr, type, member) \
>> >> +({ \
>> >> +     struct list_head *__ptr = (ptr); \
>> >> +     struct list_head *__last = __ptr; \
>> >> +     struct list_head *__entry = list_next_rcu(__ptr); \
>> >> +     for (; __entry != __ptr; __entry = list_next_rcu(__entry)) \
>> >> +             __last = __entry; \
>> >> +     likely(__ptr != __last) ? list_entry_rcu(__last, type, member) : NULL; \
>> >> +})
>> >> +
>> >> +/**
>> >>   * list_for_each_entry_rcu   -       iterate over rcu list of given type
>> >>   * @pos:     the type * to use as a loop cursor.
>> >>   * @head:    the head for your list.
>> >> --
>> >> 2.1.0
>> >>
>>
>

Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[Paul E. McKenney]

On Thu, May 28, 2015 at 05:12:00PM -0400, Dan Streetman wrote:
> On Thu, May 28, 2015 at 5:05 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
> > On Thu, 28 May 2015 16:35:27 -0400
> > Dan Streetman <ddstreet@ieee.org> wrote:
> >
> >> Add list_last_or_null_rcu(), to simplify getting the last entry from a
> >> rcu-protected list.  The standard list_last_entry() can't be used as it
> >> is not rcu-protected; the list may be modified concurrently.  And the
> >> ->prev pointer can't be used, as only the ->next pointers are protected
> >> by rcu.
> >>
> >> This simply iterates forward through the entire list, to get to the last
> >> entry.  If the list is empty, it returns NULL.
> >
> > May I asked what this would be used for? It seems awfully inefficient
> > in its implementation. What use cases would this be for? I hate to add
> > something like this as a generic function which would encourage people
> > to use it. Iterating over an entire list to find the last element is
> > just nasty.
> 
> i have a patch series that will update zswap to be able to change its
> parameters at runtime, instead of only at boot time.  To do that, it
> creates new "pools" dynamically, and keeps them all in a list, with
> only the 1st pool being actively used; any following pools still have
> everything that was stored in them, but they aren't added to.  When
> zswap has to "shrink" - by telling one of the pools to get rid of 1 or
> more items - it picks the last on the list.  Once a pool is empty,
> it's removed/freed.
> 
> So zswap *could* just manually iterate the list to the last element,
> instead of using this new function.  But if rcu lists are ever
> improved later on, e.g. if ->prev is somehow rcu-protected as well as
> ->next, then this function should be faster than manually iterating.
> 
> if there's a better rcu-way to get to the last list entry, then we
> should definitely use it, although based on my understanding of the
> rcu list implementation, you can only iterate forwards, safely
> (without locking).

The usual approach would be to maintain a tail pointer.  How big are
these lists likely to get?

							Thanx, Paul

Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[Paul E. McKenney]

On Thu, May 28, 2015 at 05:14:25PM -0400, Dan Streetman wrote:
> On Thu, May 28, 2015 at 5:05 PM, Paul E. McKenney
> <paulmck@linux.vnet.ibm.com> wrote:
> > On Thu, May 28, 2015 at 04:42:20PM -0400, Dan Streetman wrote:
> >> On Thu, May 28, 2015 at 4:39 PM,  <josh@joshtriplett.org> wrote:
> >> > On Thu, May 28, 2015 at 04:35:27PM -0400, Dan Streetman wrote:
> >> >> Add list_last_or_null_rcu(), to simplify getting the last entry from a
> >> >> rcu-protected list.  The standard list_last_entry() can't be used as it
> >> >> is not rcu-protected; the list may be modified concurrently.  And the
> >> >> ->prev pointer can't be used, as only the ->next pointers are protected
> >> >> by rcu.
> >> >>
> >> >> This simply iterates forward through the entire list, to get to the last
> >> >> entry.  If the list is empty, it returns NULL.
> >> >>
> >> >> Signed-off-by: Dan Streetman <ddstreet@ieee.org>
> >> >
> >> > The list iteration functions are macros because they introduce a loop
> >> > with attached loop block.  For this, is there any reason not to make it
> >> > an inline function instead of a macro?
> >>
> >> true, there's no reason i can see not to make it inline, let me send
> >> an updated patch.
> >
> > Hmmm...  If we can now do type-generic inline functions, it might make
> > sense to convert some of the others as well.
> 
> oh, ok.  how do we do type-generic inline funcs?  return void*?

I was hoping that you would tell me.  I use macros in that case.

							Thanx, Paul

Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[Dan Streetman]

On Thu, May 28, 2015 at 5:17 PM, Paul E. McKenney
<paulmck@linux.vnet.ibm.com> wrote:
> On Thu, May 28, 2015 at 05:14:25PM -0400, Dan Streetman wrote:
>> On Thu, May 28, 2015 at 5:05 PM, Paul E. McKenney
>> <paulmck@linux.vnet.ibm.com> wrote:
>> > On Thu, May 28, 2015 at 04:42:20PM -0400, Dan Streetman wrote:
>> >> On Thu, May 28, 2015 at 4:39 PM,  <josh@joshtriplett.org> wrote:
>> >> > On Thu, May 28, 2015 at 04:35:27PM -0400, Dan Streetman wrote:
>> >> >> Add list_last_or_null_rcu(), to simplify getting the last entry from a
>> >> >> rcu-protected list.  The standard list_last_entry() can't be used as it
>> >> >> is not rcu-protected; the list may be modified concurrently.  And the
>> >> >> ->prev pointer can't be used, as only the ->next pointers are protected
>> >> >> by rcu.
>> >> >>
>> >> >> This simply iterates forward through the entire list, to get to the last
>> >> >> entry.  If the list is empty, it returns NULL.
>> >> >>
>> >> >> Signed-off-by: Dan Streetman <ddstreet@ieee.org>
>> >> >
>> >> > The list iteration functions are macros because they introduce a loop
>> >> > with attached loop block.  For this, is there any reason not to make it
>> >> > an inline function instead of a macro?
>> >>
>> >> true, there's no reason i can see not to make it inline, let me send
>> >> an updated patch.
>> >
>> > Hmmm...  If we can now do type-generic inline functions, it might make
>> > sense to convert some of the others as well.
>>
>> oh, ok.  how do we do type-generic inline funcs?  return void*?
>
> I was hoping that you would tell me.  I use macros in that case.

ha, if I ever get to the point where i think i know more than you,
i'll let you know ;-)

>
>                                                         Thanx, Paul
>

Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[Dan Streetman]

On Thu, May 28, 2015 at 5:16 PM, Paul E. McKenney
<paulmck@linux.vnet.ibm.com> wrote:
> On Thu, May 28, 2015 at 05:12:00PM -0400, Dan Streetman wrote:
>> On Thu, May 28, 2015 at 5:05 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
>> > On Thu, 28 May 2015 16:35:27 -0400
>> > Dan Streetman <ddstreet@ieee.org> wrote:
>> >
>> >> Add list_last_or_null_rcu(), to simplify getting the last entry from a
>> >> rcu-protected list.  The standard list_last_entry() can't be used as it
>> >> is not rcu-protected; the list may be modified concurrently.  And the
>> >> ->prev pointer can't be used, as only the ->next pointers are protected
>> >> by rcu.
>> >>
>> >> This simply iterates forward through the entire list, to get to the last
>> >> entry.  If the list is empty, it returns NULL.
>> >
>> > May I asked what this would be used for? It seems awfully inefficient
>> > in its implementation. What use cases would this be for? I hate to add
>> > something like this as a generic function which would encourage people
>> > to use it. Iterating over an entire list to find the last element is
>> > just nasty.
>>
>> i have a patch series that will update zswap to be able to change its
>> parameters at runtime, instead of only at boot time.  To do that, it
>> creates new "pools" dynamically, and keeps them all in a list, with
>> only the 1st pool being actively used; any following pools still have
>> everything that was stored in them, but they aren't added to.  When
>> zswap has to "shrink" - by telling one of the pools to get rid of 1 or
>> more items - it picks the last on the list.  Once a pool is empty,
>> it's removed/freed.
>>
>> So zswap *could* just manually iterate the list to the last element,
>> instead of using this new function.  But if rcu lists are ever
>> improved later on, e.g. if ->prev is somehow rcu-protected as well as
>> ->next, then this function should be faster than manually iterating.
>>
>> if there's a better rcu-way to get to the last list entry, then we
>> should definitely use it, although based on my understanding of the
>> rcu list implementation, you can only iterate forwards, safely
>> (without locking).
>
> The usual approach would be to maintain a tail pointer.  How big are
> these lists likely to get?

in the vast majority of cases, it'll only be 1 entry; the list is only
added to when the user decides to change the pool type or compression
function, which during normal operation will probably happen very
rarely.  So in most situations, the function will just be a 1-step for
loop.  I'm only proposing this function since it may be useful to
optimize last-rcu-entry access later, and maybe for other users.

re: keeping a rcu-safe tail pointer, how is that done?  i assume since
head->prev isn't rcu protected (is it?), it would need to be separate
from the list, and thus would need to be spinlock-protected and
updated at each list update?

>
>                                                         Thanx, Paul
>

Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[Steven Rostedt]

On Thu, 28 May 2015 17:19:40 -0400
Dan Streetman <ddstreet@ieee.org> wrote:

> >> oh, ok.  how do we do type-generic inline funcs?  return void*?
> >
> > I was hoping that you would tell me.  I use macros in that case.
> 
> ha, if I ever get to the point where i think i know more than you,
> i'll let you know ;-)

static inline struct list_head *
list_last_or_null_rcu(struct list_head *ptr)
{
	struct list_head *entry;
	struct list_head *last;

	for (entry = list_next_rcu(ptr);
	     entry != ptr; entry = list_next_rcu(entry))
		last = __entry;
	if (last != ptr)
		return last;
	return NULL;
}

#define list_last_or_null_entry_rcu(ptr, type, member) \
({ \
	struct list_head *__ptr = list_last_or_null_rcu(ptr); \
	__ptr ? list_entry_rcu(__ptr, type, member) : NULL; \
})

-- Steve

Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[Dan Streetman]

On Thu, May 28, 2015 at 5:28 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
> On Thu, 28 May 2015 17:19:40 -0400
> Dan Streetman <ddstreet@ieee.org> wrote:
>
>> >> oh, ok.  how do we do type-generic inline funcs?  return void*?
>> >
>> > I was hoping that you would tell me.  I use macros in that case.
>>
>> ha, if I ever get to the point where i think i know more than you,
>> i'll let you know ;-)
>
> static inline struct list_head *
> list_last_or_null_rcu(struct list_head *ptr)
> {
>         struct list_head *entry;
>         struct list_head *last;
>
>         for (entry = list_next_rcu(ptr);
>              entry != ptr; entry = list_next_rcu(entry))
>                 last = __entry;
>         if (last != ptr)
>                 return last;
>         return NULL;
> }
>
> #define list_last_or_null_entry_rcu(ptr, type, member) \
> ({ \
>         struct list_head *__ptr = list_last_or_null_rcu(ptr); \
>         __ptr ? list_entry_rcu(__ptr, type, member) : NULL; \
> })

well sure :-)

however, the rcu list function currently doesn't include "entry" in
the function name, but returns the list entry (not the list_head).
that could be changed, but all callers would need to change, too.

>
> -- Steve

Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[Dan Streetman]

On Thu, May 28, 2015 at 5:30 PM, Dan Streetman <ddstreet@ieee.org> wrote:
> On Thu, May 28, 2015 at 5:28 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
>> On Thu, 28 May 2015 17:19:40 -0400
>> Dan Streetman <ddstreet@ieee.org> wrote:
>>
>>> >> oh, ok.  how do we do type-generic inline funcs?  return void*?
>>> >
>>> > I was hoping that you would tell me.  I use macros in that case.
>>>
>>> ha, if I ever get to the point where i think i know more than you,
>>> i'll let you know ;-)
>>
>> static inline struct list_head *
>> list_last_or_null_rcu(struct list_head *ptr)
>> {
>>         struct list_head *entry;
>>         struct list_head *last;
>>
>>         for (entry = list_next_rcu(ptr);
>>              entry != ptr; entry = list_next_rcu(entry))
>>                 last = __entry;
>>         if (last != ptr)
>>                 return last;
>>         return NULL;
>> }
>>
>> #define list_last_or_null_entry_rcu(ptr, type, member) \
>> ({ \
>>         struct list_head *__ptr = list_last_or_null_rcu(ptr); \
>>         __ptr ? list_entry_rcu(__ptr, type, member) : NULL; \
>> })
>
> well sure :-)
>
> however, the rcu list function currently doesn't include "entry" in
> the function name, but returns the list entry (not the list_head).
> that could be changed, but all callers would need to change, too.

to clarify, list_first_or_null_rcu() returns the list entry, not the
list_head; list_last_or_null_rcu() should likewise return the same
type.

git grep only shows 12 users of list_first_or_null_rcu(), so maybe
changing the name to list_first_entry_or_null_rcu() makes sense, which
would then use a new inline list_first_or_null_rcu() that returns
list_head instead of the entry type...

>
>>
>> -- Steve

Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[Paul E. McKenney]

On Thu, May 28, 2015 at 05:24:14PM -0400, Dan Streetman wrote:
> On Thu, May 28, 2015 at 5:16 PM, Paul E. McKenney
> <paulmck@linux.vnet.ibm.com> wrote:
> > On Thu, May 28, 2015 at 05:12:00PM -0400, Dan Streetman wrote:
> >> On Thu, May 28, 2015 at 5:05 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
> >> > On Thu, 28 May 2015 16:35:27 -0400
> >> > Dan Streetman <ddstreet@ieee.org> wrote:
> >> >
> >> >> Add list_last_or_null_rcu(), to simplify getting the last entry from a
> >> >> rcu-protected list.  The standard list_last_entry() can't be used as it
> >> >> is not rcu-protected; the list may be modified concurrently.  And the
> >> >> ->prev pointer can't be used, as only the ->next pointers are protected
> >> >> by rcu.
> >> >>
> >> >> This simply iterates forward through the entire list, to get to the last
> >> >> entry.  If the list is empty, it returns NULL.
> >> >
> >> > May I asked what this would be used for? It seems awfully inefficient
> >> > in its implementation. What use cases would this be for? I hate to add
> >> > something like this as a generic function which would encourage people
> >> > to use it. Iterating over an entire list to find the last element is
> >> > just nasty.
> >>
> >> i have a patch series that will update zswap to be able to change its
> >> parameters at runtime, instead of only at boot time.  To do that, it
> >> creates new "pools" dynamically, and keeps them all in a list, with
> >> only the 1st pool being actively used; any following pools still have
> >> everything that was stored in them, but they aren't added to.  When
> >> zswap has to "shrink" - by telling one of the pools to get rid of 1 or
> >> more items - it picks the last on the list.  Once a pool is empty,
> >> it's removed/freed.
> >>
> >> So zswap *could* just manually iterate the list to the last element,
> >> instead of using this new function.  But if rcu lists are ever
> >> improved later on, e.g. if ->prev is somehow rcu-protected as well as
> >> ->next, then this function should be faster than manually iterating.
> >>
> >> if there's a better rcu-way to get to the last list entry, then we
> >> should definitely use it, although based on my understanding of the
> >> rcu list implementation, you can only iterate forwards, safely
> >> (without locking).
> >
> > The usual approach would be to maintain a tail pointer.  How big are
> > these lists likely to get?
> 
> in the vast majority of cases, it'll only be 1 entry; the list is only
> added to when the user decides to change the pool type or compression
> function, which during normal operation will probably happen very
> rarely.  So in most situations, the function will just be a 1-step for
> loop.  I'm only proposing this function since it may be useful to
> optimize last-rcu-entry access later, and maybe for other users.

Fair enough.

> re: keeping a rcu-safe tail pointer, how is that done?  i assume since
> head->prev isn't rcu protected (is it?), it would need to be separate
> from the list, and thus would need to be spinlock-protected and
> updated at each list update?

Yep, each update that changed the tail would need to change the tail
pointer, and that would need to be protected from other updates.

But if the lists were long, one approach would be to provide a
list_del_rcu_bidir() or some such that didn't poison the ->prev pointer,
and then use rcu_dereference() to traverse the head element's ->prev
pointer, as you suggested above.  I have resisted doing that due to
debugging issues, but if there turns out to be a strong need, let's talk.

							Thanx, Paul

Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[Dan Streetman]

On Thu, May 28, 2015 at 6:29 PM, Paul E. McKenney
<paulmck@linux.vnet.ibm.com> wrote:
> On Thu, May 28, 2015 at 05:24:14PM -0400, Dan Streetman wrote:
>> On Thu, May 28, 2015 at 5:16 PM, Paul E. McKenney
>> <paulmck@linux.vnet.ibm.com> wrote:
>> > On Thu, May 28, 2015 at 05:12:00PM -0400, Dan Streetman wrote:
>> >> On Thu, May 28, 2015 at 5:05 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
>> >> > On Thu, 28 May 2015 16:35:27 -0400
>> >> > Dan Streetman <ddstreet@ieee.org> wrote:
>> >> >
>> >> >> Add list_last_or_null_rcu(), to simplify getting the last entry from a
>> >> >> rcu-protected list.  The standard list_last_entry() can't be used as it
>> >> >> is not rcu-protected; the list may be modified concurrently.  And the
>> >> >> ->prev pointer can't be used, as only the ->next pointers are protected
>> >> >> by rcu.
>> >> >>
>> >> >> This simply iterates forward through the entire list, to get to the last
>> >> >> entry.  If the list is empty, it returns NULL.
>> >> >
>> >> > May I asked what this would be used for? It seems awfully inefficient
>> >> > in its implementation. What use cases would this be for? I hate to add
>> >> > something like this as a generic function which would encourage people
>> >> > to use it. Iterating over an entire list to find the last element is
>> >> > just nasty.
>> >>
>> >> i have a patch series that will update zswap to be able to change its
>> >> parameters at runtime, instead of only at boot time.  To do that, it
>> >> creates new "pools" dynamically, and keeps them all in a list, with
>> >> only the 1st pool being actively used; any following pools still have
>> >> everything that was stored in them, but they aren't added to.  When
>> >> zswap has to "shrink" - by telling one of the pools to get rid of 1 or
>> >> more items - it picks the last on the list.  Once a pool is empty,
>> >> it's removed/freed.
>> >>
>> >> So zswap *could* just manually iterate the list to the last element,
>> >> instead of using this new function.  But if rcu lists are ever
>> >> improved later on, e.g. if ->prev is somehow rcu-protected as well as
>> >> ->next, then this function should be faster than manually iterating.
>> >>
>> >> if there's a better rcu-way to get to the last list entry, then we
>> >> should definitely use it, although based on my understanding of the
>> >> rcu list implementation, you can only iterate forwards, safely
>> >> (without locking).
>> >
>> > The usual approach would be to maintain a tail pointer.  How big are
>> > these lists likely to get?
>>
>> in the vast majority of cases, it'll only be 1 entry; the list is only
>> added to when the user decides to change the pool type or compression
>> function, which during normal operation will probably happen very
>> rarely.  So in most situations, the function will just be a 1-step for
>> loop.  I'm only proposing this function since it may be useful to
>> optimize last-rcu-entry access later, and maybe for other users.
>
> Fair enough.
>
>> re: keeping a rcu-safe tail pointer, how is that done?  i assume since
>> head->prev isn't rcu protected (is it?), it would need to be separate
>> from the list, and thus would need to be spinlock-protected and
>> updated at each list update?
>
> Yep, each update that changed the tail would need to change the tail
> pointer, and that would need to be protected from other updates.
>
> But if the lists were long, one approach would be to provide a
> list_del_rcu_bidir() or some such that didn't poison the ->prev pointer,
> and then use rcu_dereference() to traverse the head element's ->prev
> pointer, as you suggested above.  I have resisted doing that due to
> debugging issues, but if there turns out to be a strong need, let's talk.

In my case, there's certainly no strong need.  So this patch can be ignored.

Thnx!

>
>                                                         Thanx, Paul
>

Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[Dan Streetman]

On Thu, May 28, 2015 at 6:29 PM, Paul E. McKenney
<paulmck@linux.vnet.ibm.com> wrote:
> On Thu, May 28, 2015 at 05:24:14PM -0400, Dan Streetman wrote:
>> On Thu, May 28, 2015 at 5:16 PM, Paul E. McKenney
>> <paulmck@linux.vnet.ibm.com> wrote:
>> > On Thu, May 28, 2015 at 05:12:00PM -0400, Dan Streetman wrote:
>> >> On Thu, May 28, 2015 at 5:05 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
>> >> > On Thu, 28 May 2015 16:35:27 -0400
>> >> > Dan Streetman <ddstreet@ieee.org> wrote:
>> >> >
>> >> >> Add list_last_or_null_rcu(), to simplify getting the last entry from a
>> >> >> rcu-protected list.  The standard list_last_entry() can't be used as it
>> >> >> is not rcu-protected; the list may be modified concurrently.  And the
>> >> >> ->prev pointer can't be used, as only the ->next pointers are protected
>> >> >> by rcu.
>> >> >>
>> >> >> This simply iterates forward through the entire list, to get to the last
>> >> >> entry.  If the list is empty, it returns NULL.
>> >> >
>> >> > May I asked what this would be used for? It seems awfully inefficient
>> >> > in its implementation. What use cases would this be for? I hate to add
>> >> > something like this as a generic function which would encourage people
>> >> > to use it. Iterating over an entire list to find the last element is
>> >> > just nasty.
>> >>
>> >> i have a patch series that will update zswap to be able to change its
>> >> parameters at runtime, instead of only at boot time.  To do that, it
>> >> creates new "pools" dynamically, and keeps them all in a list, with
>> >> only the 1st pool being actively used; any following pools still have
>> >> everything that was stored in them, but they aren't added to.  When
>> >> zswap has to "shrink" - by telling one of the pools to get rid of 1 or
>> >> more items - it picks the last on the list.  Once a pool is empty,
>> >> it's removed/freed.
>> >>
>> >> So zswap *could* just manually iterate the list to the last element,
>> >> instead of using this new function.  But if rcu lists are ever
>> >> improved later on, e.g. if ->prev is somehow rcu-protected as well as
>> >> ->next, then this function should be faster than manually iterating.
>> >>
>> >> if there's a better rcu-way to get to the last list entry, then we
>> >> should definitely use it, although based on my understanding of the
>> >> rcu list implementation, you can only iterate forwards, safely
>> >> (without locking).
>> >
>> > The usual approach would be to maintain a tail pointer.  How big are
>> > these lists likely to get?
>>
>> in the vast majority of cases, it'll only be 1 entry; the list is only
>> added to when the user decides to change the pool type or compression
>> function, which during normal operation will probably happen very
>> rarely.  So in most situations, the function will just be a 1-step for
>> loop.  I'm only proposing this function since it may be useful to
>> optimize last-rcu-entry access later, and maybe for other users.
>
> Fair enough.
>
>> re: keeping a rcu-safe tail pointer, how is that done?  i assume since
>> head->prev isn't rcu protected (is it?), it would need to be separate
>> from the list, and thus would need to be spinlock-protected and
>> updated at each list update?
>
> Yep, each update that changed the tail would need to change the tail
> pointer, and that would need to be protected from other updates.
>
> But if the lists were long, one approach would be to provide a
> list_del_rcu_bidir() or some such that didn't poison the ->prev pointer,
> and then use rcu_dereference() to traverse the head element's ->prev
> pointer, as you suggested above.  I have resisted doing that due to
> debugging issues, but if there turns out to be a strong need, let's talk.

I was thinking; since the head element is never removed, its ->prev
pointer will never be poisoned; is something like this safe?

/* this can only be called on the head, not on any entry;
 * specifically this is not safe to call on any entry that
 * may be removed with list_del_rcu() or list_replace_rcu().
 */
#define list_last_or_null_rcu(head, type, member) \
({ \
        struct list_head *__last = (head)->prev; \
        __last != (head) ? list_entry_rcu(__last) : NULL; \
})

I was thinking that's unsafe because the head->prev pointer can be
updated directly, such as during list_del_rcu(last_entry) which will
directly reassign head->prev to the new last entry; but maybe that is
ok since list_del_rcu(first_entry) also directly reassigns head->next
to the new first entry?



>
>                                                         Thanx, Paul
>

Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[Paul E. McKenney]

On Fri, May 29, 2015 at 09:40:43AM -0400, Dan Streetman wrote:
> On Thu, May 28, 2015 at 6:29 PM, Paul E. McKenney
> <paulmck@linux.vnet.ibm.com> wrote:
> > On Thu, May 28, 2015 at 05:24:14PM -0400, Dan Streetman wrote:
> >> On Thu, May 28, 2015 at 5:16 PM, Paul E. McKenney
> >> <paulmck@linux.vnet.ibm.com> wrote:
> >> > On Thu, May 28, 2015 at 05:12:00PM -0400, Dan Streetman wrote:
> >> >> On Thu, May 28, 2015 at 5:05 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
> >> >> > On Thu, 28 May 2015 16:35:27 -0400
> >> >> > Dan Streetman <ddstreet@ieee.org> wrote:
> >> >> >
> >> >> >> Add list_last_or_null_rcu(), to simplify getting the last entry from a
> >> >> >> rcu-protected list.  The standard list_last_entry() can't be used as it
> >> >> >> is not rcu-protected; the list may be modified concurrently.  And the
> >> >> >> ->prev pointer can't be used, as only the ->next pointers are protected
> >> >> >> by rcu.
> >> >> >>
> >> >> >> This simply iterates forward through the entire list, to get to the last
> >> >> >> entry.  If the list is empty, it returns NULL.
> >> >> >
> >> >> > May I asked what this would be used for? It seems awfully inefficient
> >> >> > in its implementation. What use cases would this be for? I hate to add
> >> >> > something like this as a generic function which would encourage people
> >> >> > to use it. Iterating over an entire list to find the last element is
> >> >> > just nasty.
> >> >>
> >> >> i have a patch series that will update zswap to be able to change its
> >> >> parameters at runtime, instead of only at boot time.  To do that, it
> >> >> creates new "pools" dynamically, and keeps them all in a list, with
> >> >> only the 1st pool being actively used; any following pools still have
> >> >> everything that was stored in them, but they aren't added to.  When
> >> >> zswap has to "shrink" - by telling one of the pools to get rid of 1 or
> >> >> more items - it picks the last on the list.  Once a pool is empty,
> >> >> it's removed/freed.
> >> >>
> >> >> So zswap *could* just manually iterate the list to the last element,
> >> >> instead of using this new function.  But if rcu lists are ever
> >> >> improved later on, e.g. if ->prev is somehow rcu-protected as well as
> >> >> ->next, then this function should be faster than manually iterating.
> >> >>
> >> >> if there's a better rcu-way to get to the last list entry, then we
> >> >> should definitely use it, although based on my understanding of the
> >> >> rcu list implementation, you can only iterate forwards, safely
> >> >> (without locking).
> >> >
> >> > The usual approach would be to maintain a tail pointer.  How big are
> >> > these lists likely to get?
> >>
> >> in the vast majority of cases, it'll only be 1 entry; the list is only
> >> added to when the user decides to change the pool type or compression
> >> function, which during normal operation will probably happen very
> >> rarely.  So in most situations, the function will just be a 1-step for
> >> loop.  I'm only proposing this function since it may be useful to
> >> optimize last-rcu-entry access later, and maybe for other users.
> >
> > Fair enough.
> >
> >> re: keeping a rcu-safe tail pointer, how is that done?  i assume since
> >> head->prev isn't rcu protected (is it?), it would need to be separate
> >> from the list, and thus would need to be spinlock-protected and
> >> updated at each list update?
> >
> > Yep, each update that changed the tail would need to change the tail
> > pointer, and that would need to be protected from other updates.
> >
> > But if the lists were long, one approach would be to provide a
> > list_del_rcu_bidir() or some such that didn't poison the ->prev pointer,
> > and then use rcu_dereference() to traverse the head element's ->prev
> > pointer, as you suggested above.  I have resisted doing that due to
> > debugging issues, but if there turns out to be a strong need, let's talk.
> 
> I was thinking; since the head element is never removed, its ->prev
> pointer will never be poisoned; is something like this safe?
> 
> /* this can only be called on the head, not on any entry;
>  * specifically this is not safe to call on any entry that
>  * may be removed with list_del_rcu() or list_replace_rcu().
>  */
> #define list_last_or_null_rcu(head, type, member) \
> ({ \
>         struct list_head *__last = (head)->prev; \
>         __last != (head) ? list_entry_rcu(__last) : NULL; \
> })
> 
> I was thinking that's unsafe because the head->prev pointer can be
> updated directly, such as during list_del_rcu(last_entry) which will
> directly reassign head->prev to the new last entry; but maybe that is
> ok since list_del_rcu(first_entry) also directly reassigns head->next
> to the new first entry?

In your particular case, it would be safe, but people can and do call
list_del_rcu() on the header in order to remove the entire list, which
would poison the header's ->prev pointer.  So if you really want to do
this in your own code, fine, but please: (1) include a big fat comment
saying what you are doing and the resulting restrictions and (2) Name
it something specific to your code.

If multiple similar use cases show up, maybe we can add something to
the rculist_nulls.h file.

							Thanx, Paul

Re: [PATCH 1/2] rcu: introduce list_last_or_null_rcu

[Dan Streetman]

On Mon, Jun 1, 2015 at 2:17 PM, Paul E. McKenney
<paulmck@linux.vnet.ibm.com> wrote:
> On Fri, May 29, 2015 at 09:40:43AM -0400, Dan Streetman wrote:
>> On Thu, May 28, 2015 at 6:29 PM, Paul E. McKenney
>> <paulmck@linux.vnet.ibm.com> wrote:
>> > On Thu, May 28, 2015 at 05:24:14PM -0400, Dan Streetman wrote:
>> >> On Thu, May 28, 2015 at 5:16 PM, Paul E. McKenney
>> >> <paulmck@linux.vnet.ibm.com> wrote:
>> >> > On Thu, May 28, 2015 at 05:12:00PM -0400, Dan Streetman wrote:
>> >> >> On Thu, May 28, 2015 at 5:05 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
>> >> >> > On Thu, 28 May 2015 16:35:27 -0400
>> >> >> > Dan Streetman <ddstreet@ieee.org> wrote:
>> >> >> >
>> >> >> >> Add list_last_or_null_rcu(), to simplify getting the last entry from a
>> >> >> >> rcu-protected list.  The standard list_last_entry() can't be used as it
>> >> >> >> is not rcu-protected; the list may be modified concurrently.  And the
>> >> >> >> ->prev pointer can't be used, as only the ->next pointers are protected
>> >> >> >> by rcu.
>> >> >> >>
>> >> >> >> This simply iterates forward through the entire list, to get to the last
>> >> >> >> entry.  If the list is empty, it returns NULL.
>> >> >> >
>> >> >> > May I asked what this would be used for? It seems awfully inefficient
>> >> >> > in its implementation. What use cases would this be for? I hate to add
>> >> >> > something like this as a generic function which would encourage people
>> >> >> > to use it. Iterating over an entire list to find the last element is
>> >> >> > just nasty.
>> >> >>
>> >> >> i have a patch series that will update zswap to be able to change its
>> >> >> parameters at runtime, instead of only at boot time.  To do that, it
>> >> >> creates new "pools" dynamically, and keeps them all in a list, with
>> >> >> only the 1st pool being actively used; any following pools still have
>> >> >> everything that was stored in them, but they aren't added to.  When
>> >> >> zswap has to "shrink" - by telling one of the pools to get rid of 1 or
>> >> >> more items - it picks the last on the list.  Once a pool is empty,
>> >> >> it's removed/freed.
>> >> >>
>> >> >> So zswap *could* just manually iterate the list to the last element,
>> >> >> instead of using this new function.  But if rcu lists are ever
>> >> >> improved later on, e.g. if ->prev is somehow rcu-protected as well as
>> >> >> ->next, then this function should be faster than manually iterating.
>> >> >>
>> >> >> if there's a better rcu-way to get to the last list entry, then we
>> >> >> should definitely use it, although based on my understanding of the
>> >> >> rcu list implementation, you can only iterate forwards, safely
>> >> >> (without locking).
>> >> >
>> >> > The usual approach would be to maintain a tail pointer.  How big are
>> >> > these lists likely to get?
>> >>
>> >> in the vast majority of cases, it'll only be 1 entry; the list is only
>> >> added to when the user decides to change the pool type or compression
>> >> function, which during normal operation will probably happen very
>> >> rarely.  So in most situations, the function will just be a 1-step for
>> >> loop.  I'm only proposing this function since it may be useful to
>> >> optimize last-rcu-entry access later, and maybe for other users.
>> >
>> > Fair enough.
>> >
>> >> re: keeping a rcu-safe tail pointer, how is that done?  i assume since
>> >> head->prev isn't rcu protected (is it?), it would need to be separate
>> >> from the list, and thus would need to be spinlock-protected and
>> >> updated at each list update?
>> >
>> > Yep, each update that changed the tail would need to change the tail
>> > pointer, and that would need to be protected from other updates.
>> >
>> > But if the lists were long, one approach would be to provide a
>> > list_del_rcu_bidir() or some such that didn't poison the ->prev pointer,
>> > and then use rcu_dereference() to traverse the head element's ->prev
>> > pointer, as you suggested above.  I have resisted doing that due to
>> > debugging issues, but if there turns out to be a strong need, let's talk.
>>
>> I was thinking; since the head element is never removed, its ->prev
>> pointer will never be poisoned; is something like this safe?
>>
>> /* this can only be called on the head, not on any entry;
>>  * specifically this is not safe to call on any entry that
>>  * may be removed with list_del_rcu() or list_replace_rcu().
>>  */
>> #define list_last_or_null_rcu(head, type, member) \
>> ({ \
>>         struct list_head *__last = (head)->prev; \
>>         __last != (head) ? list_entry_rcu(__last) : NULL; \
>> })
>>
>> I was thinking that's unsafe because the head->prev pointer can be
>> updated directly, such as during list_del_rcu(last_entry) which will
>> directly reassign head->prev to the new last entry; but maybe that is
>> ok since list_del_rcu(first_entry) also directly reassigns head->next
>> to the new first entry?
>
> In your particular case, it would be safe, but people can and do call
> list_del_rcu() on the header in order to remove the entire list, which
> would poison the header's ->prev pointer.  So if you really want to do
> this in your own code, fine, but please: (1) include a big fat comment
> saying what you are doing and the resulting restrictions and (2) Name
> it something specific to your code.

Ok.  Since in my case there will only be 1 entry (or at worst just a
few) in the list in the majority of cases, I'll just stick to manually
iterating to the last entry.  It's easy and clear.

Thanks!

>
> If multiple similar use cases show up, maybe we can add something to
> the rculist_nulls.h file.
>
>                                                         Thanx, Paul
>