linux-kernel - Re: [PATCH 0/3] 64-bit futexes: Intro

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]

Date:	Fri, 30 May 2008 21:04:33 -0700
From:	Ulrich Drepper <drepper@...hat.com>
To:	Linus Torvalds <torvalds@...ux-foundation.org>
CC:	linux-kernel@...r.kernel.org, akpm@...ux-foundation.org,
	mtk.manpages@...il.com
Subject: Re: [PATCH 0/3] 64-bit futexes: Intro

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Linus Torvalds wrote:
> The kernel calls reader-writer locks rwsemaphores.

Well, then you don't understand the complexity of the required interface
together with the performance implications.  Take your proposed allocation:

 - 29 bits of reader counts
 - 1 bit of uncontended writer
 - 1 bit of "contention" (ie a mark for requiring fairness)
 - 1 bit for a spinlock so that you can do all the fairness without
   doing any extra locked ops

Ask yourself this:

- - How do you know when there is no more writer waiting?  You cannot
  reset a "writer waiting" bit after you wake up one writer without
  waking every single thread waiting for the rwlock and letting them
  fight for it

- - How do you handle the difference between reader-preferred rwlocks
  and writer-preferred rwlocks?  In the latter, if a rwlock is locked
  for reading, future readers must be delayed until all writers are
  gone

- - How do you do the accounting for the *timedlock variants?  In the
  case of those a functions, if the threads wake due to a timeout,
  you have the decrement the waiter count.  But you have only one bit...

I don't say you cannot implement rwlocks this way.  Sure, it definitely
is possible.  But this implementation would in the contended case like
10x as slow as the current code because you constantly have to wake up
every single thread.

If you want, I'll give you a libpthread.so with the new code.  Then you
can test your code.  I bet you whatever you want that you cannot achieve
the performance with your puny 32-bit futex without limiting the number
of threads to a ridiculously low number.  The implementation I have
allows for 2^23 (possibly recursively locked) readers, 2^18 readers or
writers waiting.

When I was writing "you need more than 32 bits" I didn't even imagine
that somebody would suggest using such a primitive scheme which cannot
possibly work efficiently in a userlevel implementation.

- --
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEARECAAYFAkhAzlEACgkQ2ijCOnn/RHQ+bgCcDDmhSvbKdboyqa21smzlSt75
zHUAn2rr3NKns4Kb78Woas3NP5hbwkOU
=p6z6
-----END PGP SIGNATURE-----
--
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/