linux-kernel - Re: [RFC PATCH 3/4 v0.3] sched/umcg: RFC: add userspace sll helpers

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 for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <e84df89d-5c5b-c3fd-42f6-2240b8a110a1@uwaterloo.ca>
Date:   Fri, 16 Jul 2021 20:58:09 -0400
From:   Thierry Delisle <tdelisle@...terloo.ca>
To:     <posk@...k.io>
CC:     <avagin@...gle.com>, <bsegall@...gle.com>, <jannh@...gle.com>,
        <jnewsome@...project.org>, <joel@...lfernandes.org>,
        <linux-api@...r.kernel.org>, <linux-kernel@...r.kernel.org>,
        <mingo@...hat.com>, <peterz@...radead.org>, <pjt@...gle.com>,
        <posk@...gle.com>, <tglx@...utronix.de>,
        Peter Buhr <pabuhr@...terloo.ca>,
        Martin Karsten <mkarsten@...terloo.ca>
Subject: Re: [RFC PATCH 3/4 v0.3] sched/umcg: RFC: add userspace sll helpers

 > The helpers below can work with userspace single-linked lists 
concurrently
 > without indefinitely spinning in the kernel. Specifically:
 >
 > push (add to the head of the list):
 >
 >   step = 0
 >   while (++step < N)
 >      old = *head
 >      *next = old
 >      cmp_xchng(head, &old, next)
 >
 > pop (remove the first element from the list):
 >     mark the node as deleted by flipping its lowest bit without
 >     actually removing the node from the list:
 >
 >   curr = *head
 >   step = 0
 >
 >   while (curr && ++step < N)
 >
 >     next = *curr
 >     if (next & 1)
 >         curr = next & ~1
 >         continue
 >
 >     if (cmp_xchng(curr, next, next | 1))
 >         return curr
 >     else
 >         curr = next & ~1
 >
 > It is the userspace's responsibility to actually remove the
 > nodes marked as deleted from the list.

I believe the subsystem called Nemesis introduced a MCS-based queue that 
could
be useful here. The original paper is https://doi.org/10.1109/CCGRID.2006.31

You can also look at this repo for an implementation of the queue.
https://git.uwaterloo.ca/mkarsten/libfibre/-/blob/master/src/runtime/LockFreeQueues.h

While it uses 2 pointers, I believe it would fit well for idle_workers_ptr
since the push operation is wait-free, which avoids problems for the kernel.
The pop operation requires a lock in userspace *if* multiple servers can
consume from the same queue, but I don't believe it's a requirement in 
general.