linux-kernel - Re: [PATCH] netfilter: use per-CPU recursive lock {XV}

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: <1240854297.7620.65.camel@twins>
Date:	Mon, 27 Apr 2009 19:44:57 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Stephen Hemminger <shemminger@...tta.com>
Cc:	Mathieu Desnoyers <mathieu.desnoyers@...ymtl.ca>,
	Eric Dumazet <dada1@...mosbay.com>,
	David Miller <davem@...emloft.net>,
	Jarek Poplawski <jarkao2@...il.com>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Ingo Molnar <mingo@...e.hu>, Paul Mackerras <paulus@...ba.org>,
	paulmck@...ux.vnet.ibm.com, Evgeniy Polyakov <zbr@...emap.net>,
	kaber@...sh.net, jeff.chua.linux@...il.com, laijs@...fujitsu.com,
	jengelh@...ozas.de, r000n@...0n.net, linux-kernel@...r.kernel.org,
	netfilter-devel@...r.kernel.org, netdev@...r.kernel.org,
	benh@...nel.crashing.org
Subject: Re: [PATCH] netfilter: use per-CPU recursive lock {XV}

On Sun, 2009-04-26 at 14:57 -0700, Stephen Hemminger wrote:
> On Sun, 26 Apr 2009 14:56:46 -0400
> Mathieu Desnoyers <mathieu.desnoyers@...ymtl.ca> wrote:
> 
> > * Eric Dumazet (dada1@...mosbay.com) wrote:
> > > From: Stephen Hemminger <shemminger@...tta.com>
> > > 
> > > > Epilogue due to master Jarek. Lockdep carest not about the locking
> > > > doth bestowed. Therefore no keys are needed.
> > > > 
> > > > Signed-off-by: Stephen Hemminger <shemminger@...tta.com>
> > > 
> > > So far, so good, should be ready for inclusion now, nobody complained :)
> > > 
> > > I include the final patch, merge of your last two patches.
> > > 
> > > David, could you please review it once again and apply it if it's OK ?
> > 
> > > Thanks to all for your help and patience
> > > 
> > > [PATCH] netfilter: use per-CPU recursive lock {XV}
> > 
> > Hi Eric, 
> > 
> > Suitable name would probably be :
> > 
> 
> But Linus is trying to delude himself.
> 
> This usage is recursive even if he doesn't like the terminology.
> The same CPU has to be able to reacquire the read lock without deadlocking.
> If reader/writer locks were implemented in a pure writer gets priority
> method, then this code would break!  So yes read locks can be used recursively
> now in Linux, but if the were implemented differently then this code
> would break.  For example, the -rt kernel turns all read/write locks into
> mutexs, so the -rt kernel developers will have to address this.

A recursive lock has the property:

lock()
{
  if (lock->owner == current) {
    lock->depth++;
    return;
  }

  /* regular lock stuff */
}

unlock()
{
  if (!--lock->depth)
    /* regular unlock */
}

non of the linux kernel locking primitives have this -- with the
possible exception of the cpu-hotplug lock.

What rwlock_t has, is reader bias to the point where you can utterly
starve writers, with the side effect that you can obtain multiple read
ownerships without causing a deadlock.

This is not what is called a recursive lock. A recursive lock would have
each owner only once, this rwlock_t thing is simply so unfair that it
can have unlimited owners, including multiple copies of the same one.

rwsem has fifo fairness, and therefore can deadlock in this scenario,
suppose thread A does a read, thread B tries a write and blocks, then
thread A recurses and tries to obtain another read ownership --
deadlock, as the FIFO fairness will demand the second read ownership
will wait on the pending writer, which will wait on the outstanding read
owner.

Now if rwsem were a fifo-fair recursive lock, the above would not
deadlock, since it would detect that the task already had (read)
ownership and simply increment the depth, instead of trying to acquire a
second ownership.

This is all common and well understood terminology, not something Linus
invented just to harras you with.

Generally speaking we do not condone recursive locking strategies -- and
afaik reiserfs (as per the BKL) and the network code (as per abusing
rwlock_t unfairness) are the only offenders.

Like Linus stated, recursive locking is generally poor taste and
indicates you basically gave up on trying to find a proper locking
scheme. We should very much work towards getting rid of these
abberations instead of adding new ones.

Linus is very much right on what he said, and you calling him delusional
only high-lights your ignorance on the issue.

[ PS. -rt implements rwlock_t as a proper recursive lock (either a mutex
  or a full multi-owner reader-writer lock with PI fairness) so if
  anybody abuses rwlock_t unfairness in a way that is not strict owner
  recursive we have a problem. ]
--
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/