linux-kernel - Confused about hlist_unhashed

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-next>] [day] [month] [year] [list]

Date:   Fri, 31 Jan 2020 16:43:09 +0000
From:   Will Deacon <will@...nel.org>
To:     edumazet@...gle.com, tglx@...utronix.de, paulmck@...nel.org
Cc:     x86@...nel.org, linux-kernel@...r.kernel.org, peterz@...radead.org
Subject: Confused about hlist_unhashed_lockless()

Hi folks,

I just ran into c54a2744497d ("list: Add hlist_unhashed_lockless()")
but I'm a bit confused about what it's trying to achieve. It also seems
to have been merged without any callers (even in -next) -- was that
intentional?

My main source of confusion is the lack of memory barriers. For example,
if you look at the following pair of functions:

static inline int hlist_unhashed_lockless(const struct hlist_node *h)
{
	return !READ_ONCE(h->pprev);
}

static inline void hlist_add_before(struct hlist_node *n,
				    struct hlist_node *next)
{
	WRITE_ONCE(n->pprev, next->pprev);
	WRITE_ONCE(n->next, next);
	WRITE_ONCE(next->pprev, &n->next);
	WRITE_ONCE(*(n->pprev), n);
}

Then running these two concurrently on the same node means that
hlist_unhashed_lockless() doesn't really tell you anything about whether
or not the node is reachable in the list (i.e. there is another node
with a next pointer pointing to it). In other words, I think all of
these outcomes are permitted:

	hlist_unhashed_lockless(n)	n reachable in list
	0				0 (No reordering)
	0				1 (No reordering)
	1				0 (No reordering)
	1				1 (Reorder first and last WRITE_ONCEs)

So I must be missing some details about the use-case here. Please could
you enlighten me? The RCU implementation permits only the first three
outcomes afaict, why not use that and leave non-RCU hlist as it was?

Cheers,

Will