From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 00AEBC369DC for ; Tue, 29 Apr 2025 06:12:40 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 0C1136B0005; Tue, 29 Apr 2025 02:12:40 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 0443C6B000C; Tue, 29 Apr 2025 02:12:39 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E2A5B6B000D; Tue, 29 Apr 2025 02:12:39 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id BE46B6B0005 for ; Tue, 29 Apr 2025 02:12:39 -0400 (EDT) Received: from smtpin05.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id A09F780F05 for ; Tue, 29 Apr 2025 06:12:39 +0000 (UTC) X-FDA: 83386062438.05.69888CB Received: from out-178.mta0.migadu.com (out-178.mta0.migadu.com [91.218.175.178]) by imf15.hostedemail.com (Postfix) with ESMTP id DF621A000F for ; Tue, 29 Apr 2025 06:12:37 +0000 (UTC) Authentication-Results: imf15.hostedemail.com; dkim=pass header.d=linux.dev header.s=key1 header.b=G8K50aPa; dmarc=pass (policy=none) header.from=linux.dev; spf=pass (imf15.hostedemail.com: domain of shakeel.butt@linux.dev designates 91.218.175.178 as permitted sender) smtp.mailfrom=shakeel.butt@linux.dev ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1745907158; a=rsa-sha256; cv=none; b=TzyYxdAHGwYNWj818yLTSw/Tf3NMSyG3h0b8opYxkoIRln2wj0gRlYqI4hztW5faib/SqW wlC1UbkWTQQUcm3yzQ4hMttDXvVlFyaE66OenstEvWk0Fndo/ndEzrt2TxzgPhL0GUgmUc 0XyDeoUXwZXa0anabrpKBSk8D2bykP0= ARC-Authentication-Results: i=1; imf15.hostedemail.com; dkim=pass header.d=linux.dev header.s=key1 header.b=G8K50aPa; dmarc=pass (policy=none) header.from=linux.dev; spf=pass (imf15.hostedemail.com: domain of shakeel.butt@linux.dev designates 91.218.175.178 as permitted sender) smtp.mailfrom=shakeel.butt@linux.dev ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1745907158; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=Y0GCrjGtquPsOI35plGdgUQW448xZcx6HHNt3mxji6M=; b=AS+cMELRoikYtHNIHJ6L69V5R5OFab1drOxJg850Jb6ibzRX8nhFPl7u0eWc0qBO84UrUB iTzKx4/wkEs4cX6JqfE7pnicthnCJZW7onlvscmKTahZc5k1JUAl0KEMpJZpLp2PpOUWaT XzWgOi+SW8klwdh3myRNfh4M8JX2BPM= X-Report-Abuse: Please report any abuse attempt to abuse@migadu.com and include these headers. DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linux.dev; s=key1; t=1745907155; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=Y0GCrjGtquPsOI35plGdgUQW448xZcx6HHNt3mxji6M=; b=G8K50aPalxCurXCs8MzqUCxqQtHVl+V5W1N6WLfUGShF4gMmsaZp5t2m85tfP429t0pyBD vdHZ6EKbajUKl9WNEtwoLC8OHw67tekWbbtELBZOeKkCRAUdBwDEC2lRDp8XwDcykT/Nfg 2vP6HBmWrLpf01hxCtxfiMZrS+itV34= From: Shakeel Butt To: Tejun Heo , Andrew Morton , Alexei Starovoitov Cc: Johannes Weiner , Michal Hocko , Roman Gushchin , Muchun Song , Yosry Ahmed , =?UTF-8?q?Michal=20Koutn=C3=BD?= , Vlastimil Babka , Sebastian Andrzej Siewior , JP Kobryn , bpf@vger.kernel.org, linux-mm@kvack.org, cgroups@vger.kernel.org, linux-kernel@vger.kernel.org, Meta kernel team Subject: [RFC PATCH 1/3] llist: add list_add_iff_not_on_list() Date: Mon, 28 Apr 2025 23:12:07 -0700 Message-ID: <20250429061211.1295443-2-shakeel.butt@linux.dev> In-Reply-To: <20250429061211.1295443-1-shakeel.butt@linux.dev> References: <20250429061211.1295443-1-shakeel.butt@linux.dev> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Migadu-Flow: FLOW_OUT X-Rspamd-Server: rspam03 X-Rspamd-Queue-Id: DF621A000F X-Stat-Signature: xbi6i8p4sz4u7ifyikygkns19oq8o7tt X-Rspam-User: X-HE-Tag: 1745907157-930409 X-HE-Meta: U2FsdGVkX1+nYrLOgeIyEFJLkxOOa4M8nMIEE8FE8TO4L1UJABKwhIWp8kxlLVHOuN4l9W2T2/j2d2+K6bEMHgWNb16+/VJc0N7GLlrcyOtH2aDcfnuR/+iFAAikKtuPSXYOsXVVROQe8mRrrkpjFSQKjXBh7X8EnoGu3ikgNqc3NTnnpY2pot9EK9ucxwqJXNZGih1Vxp/BdKF8XUh+PAz3BgyzXpvjhWe/ipUOB6xx6Cf9I0MYhRTHYXAzdhQJ9HVKS99OC5XwjqSbons7X32PlOkR3K/Iak6bOfMbUVnuvvbwXiJUnxPsBEXCLonJ1AtFi8SrNCLsN2z5LwcRoXgOe6snRpUKvgIdqmvJkZII577YbP2M4tz/edpddTcYvyqCA2tYy+sso1/ZMV5TUcOLxa549+EWFlk4bEWvuJqoW0OR2XTKixUSHGDiA2JVefsPw2Db08pmYYYetIu5rUwCvWUzGQYNRmfPd8beOztMJ8MBo/G/h++be55AXGVKLad1Cy2LTK5CTT5w6hf0YutB9Qd8mKYmGc7yAifNFXMp4Vq/UOc3hvlAfSxtHqvTDVbhqPMP0yGbEf1hxxRJGx8Ux2qDHyUimSaxu5pXP3nBszUxMRO+w7TnnVSkbpNGcx5r7cpeOY0O2bjlcndXMpS7vfxnowiYH7TSWJ1t70ls/yy3Gvx6uUukTaGZw4E0OqlVGHhTuPdxxvjAX1AXxPpGK0YIYETarejBN57ZM6HWFbNQ7GdmMbkvAkFoVfpXJCXlp7ASYQfTkkN5mWIusNPSLSDzcgx79ZGnCVfBKrsJQQ6EFwm/ekJumBLVtQqxLmpzg1NwqzCCcWDIsqhY5Bfgedcm5MKTBluogT+EY3WrIS3rghBWyx/k6VMFtV93hIsK02KUxB7AKakL5QKSUDE/6h0phQWKYJU7CBMwB0AJTRN9LLsolEBvXcP3VqBt/M3iO1yr8c6M4fTrGY/ +c2xepBM xEV8gPqMzTfTo7XeJt4Z2bgPZj9XKVXITu20TnhDEvWV+gncbMWp8OrPCpzyrpgB9L10qYwy7jffGTUvqr3zSH6j7jStMdb9a6ldP1ZkwYwGgCXhYL4emorHM5GW3hfD9RXSnzg9nqIBGh3O/v19suFGs9UZ0jOcT3zD6zCfdeKFeEwtO8gbwDWPCs+H77tBfxRB/l02FCrBKXNzV8wppCmZaOZ7qAbMC3Zxo X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: 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 --- 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) +{ + struct llist_node *first = READ_ONCE(head->first); + + if (llist_on_list(new)) + return false; + + if (cmpxchg(&new->next, new, first) != new) + return false; + + while (!try_cmpxchg(&head->first, &first, new)) + new->next = first; + 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