linux-kernel - Re: [PATCH -v4 2/2] lib, Add lock-less NULL terminated single list

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: <AANLkTincM=Jsu48yJ_wEinj4Vfdu3Xt8QgC50Uqav7q3@mail.gmail.com>
Date:	Tue, 16 Nov 2010 08:33:26 -0800
From:	Linus Torvalds <torvalds@...ux-foundation.org>
To:	Peter Zijlstra <peterz@...radead.org>
Cc:	Huang Ying <ying.huang@...el.com>, Len Brown <lenb@...nel.org>,
	linux-kernel@...r.kernel.org, Andi Kleen <andi@...stfloor.org>,
	linux-acpi@...r.kernel.org,
	Andrew Morton <akpm@...ux-foundation.org>,
	Thomas Gleixner <tglx@...utronix.de>,
	Ingo Molnar <mingo@...e.hu>,
	Mauro Carvalho Chehab <mchehab@...hat.com>
Subject: Re: [PATCH -v4 2/2] lib, Add lock-less NULL terminated single list

On Tue, Nov 16, 2010 at 3:50 AM, Peter Zijlstra <peterz@...radead.org> wrote:
> On Tue, 2010-11-16 at 08:53 +0800, Huang Ying wrote:
>> +/**
>> + * llist_del_all - delete all entries from lock-less list
>> + * @head:      the head of lock-less list to delete all entries
>> + *
>> + * If list is empty, return NULL, otherwise, delete all entries and
>> + * return the pointer to the first entry.
>> + */
>> +struct llist_node *llist_del_all(struct llist_head *head)
>> +{
>> +       return xchg(&head->first, NULL);
>> +}
>> +EXPORT_SYMBOL_GPL(llist_del_all);
>
> Its not del_all, since it returns the actual list. move or splice might
> be better names.

I don't think it's a "move", since the result isn't actually a
list_head (it's by definition a "we remove all entries from the list,
and then we can look at the list entries in private afterwards").

So the "delete" part _is_ important - before the op, we had an atomic
list. After the op, we just have a bunch of entries (they may be a
list, but they aren't a _lock-less_ list any more: they are literally
just private entries now).

So both "move" and "splice" imply at least to me that the target is
equivalent to the source. And it really isn't. The target is something
totally different. In fact, my original objection to this code was
that there wasn't a good separation between "entries" and "lock-less
head of list", and it used the same type for both - the way the
regular list functions do. In the regular list implementation, each
list entry really is a list head too, and you can have lists that
don't even _have_ separate heads, but everything is a list entry
(common in things like the dentry "siblings" list, where each dentry
can be used as the "head" to that sibling list - all siblings are
equal).

Now, I don't know if "del_all" is necessarily the proper name, but I
do think that it's important to make it clear that as far as the
lock-lessness of the list is concerned, the operation really is about
removing all entries, and it's not some kind of symmetric operation
wrt src/dest like with normal lists.

                                  Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/