linux-kernel - Re: [RFC PATCH 1/3] llist: add list_add_iff_not_on

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <aBIbRhLjmO-fKKGr@Asmaa.>
Date: Wed, 30 Apr 2025 05:44:54 -0700
From: Yosry Ahmed <yosry.ahmed@...ux.dev>
To: Shakeel Butt <shakeel.butt@...ux.dev>
Cc: Tejun Heo <tj@...nel.org>, Andrew Morton <akpm@...ux-foundation.org>,
	Alexei Starovoitov <ast@...nel.org>,
	Johannes Weiner <hannes@...xchg.org>,
	Michal Hocko <mhocko@...nel.org>,
	Roman Gushchin <roman.gushchin@...ux.dev>,
	Muchun Song <muchun.song@...ux.dev>,
	Michal Koutný <mkoutny@...e.com>,
	Vlastimil Babka <vbabka@...e.cz>,
	Sebastian Andrzej Siewior <bigeasy@...utronix.de>,
	JP Kobryn <inwardvessel@...il.com>, bpf@...r.kernel.org,
	linux-mm@...ck.org, cgroups@...r.kernel.org,
	linux-kernel@...r.kernel.org,
	Meta kernel team <kernel-team@...a.com>
Subject: Re: [RFC PATCH 1/3] llist: add list_add_iff_not_on_list()g

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@...ux.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
>