Re: [RFC PATCH 1/3] llist: add list_add_iff_not_on_list()g

[Yosry Ahmed <yosry.ahmed@linux.dev>]

On Mon, Apr 28, 2025 at 11:12:07PM -0700, Shakeel Butt wrote:
> As the name implies, list_add_iff_not_on_list() adds the given node to
> the given only if the node is not on any list. Many CPUs can call this
> concurrently on the same node and only one of them will succeed.
> 
> This is also useful to be used by different contexts like task, irq and
> nmi. In the case of failure either the node as already present on some
> list or the caller can lost the race to add the given node to a list.
> That node will eventually be added to a list by the winner.
> 
> Signed-off-by: Shakeel Butt <shakeel.butt@linux.dev>
> ---
>  include/linux/llist.h |  3 +++
>  lib/llist.c           | 30 ++++++++++++++++++++++++++++++
>  2 files changed, 33 insertions(+)
> 
> diff --git a/include/linux/llist.h b/include/linux/llist.h
> index 2c982ff7475a..030cfec8778b 100644
> --- a/include/linux/llist.h
> +++ b/include/linux/llist.h
> @@ -236,6 +236,9 @@ static inline bool __llist_add_batch(struct llist_node *new_first,
>  	return new_last->next == NULL;
>  }
>  
> +extern bool llist_add_iff_not_on_list(struct llist_node *new,
> +				      struct llist_head *head);
> +
>  /**
>   * llist_add - add a new entry
>   * @new:	new entry to be added
> diff --git a/lib/llist.c b/lib/llist.c
> index f21d0cfbbaaa..9d743164720f 100644
> --- a/lib/llist.c
> +++ b/lib/llist.c
> @@ -36,6 +36,36 @@ bool llist_add_batch(struct llist_node *new_first, struct llist_node *new_last,
>  }
>  EXPORT_SYMBOL_GPL(llist_add_batch);
>  
> +/**
> + * llist_add_iff_not_on_list - add an entry if it is not on list
> + * @new:	entry to be added
> + * @head:	the head for your lock-less list
> + *
> + * Adds the given entry to the given list only if the entry is not on any list.
> + * This is useful for cases where multiple CPUs tries to add the same node to
> + * the list or multiple contexts (process, irq or nmi) may add the same node to
> + * the list.
> + *
> + * Return true only if the caller has successfully added the given node to the
> + * list. Returns false if entry is already on some list or if another inserter
> + * wins the race to eventually add the given node to the list.
> + */
> +bool llist_add_iff_not_on_list(struct llist_node *new, struct llist_head *head)

What about llist_try_add()?

> +{
> +	struct llist_node *first = READ_ONCE(head->first);
> +
> +	if (llist_on_list(new))
> +		return false;
> +
> +	if (cmpxchg(&new->next, new, first) != new)
> +		return false;

Here we will set new->next to the current head of the list, but this may
change from under us, and the next loop will then set it correctly
anyway. This is a bit confusing though.

Would it be better if we set new->next to NULL here, and then completely
rely on the loop below to set it properly?

> +
> +	while (!try_cmpxchg(&head->first, &first, new))
> +		new->next = first;

Not a big deal, but should we use llist_add_batch() here instead?

> +	return true;
> +}
> +EXPORT_SYMBOL_GPL(llist_add_iff_not_on_list);
> +
>  /**
>   * llist_del_first - delete the first entry of lock-less list
>   * @head:	the head for your lock-less list
> -- 
> 2.47.1
>