From nobody Mon Jun 28 11:20:25 2021 X-Original-To: freebsd-hackers@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4F15511CA30B for ; Mon, 28 Jun 2021 11:20:41 +0000 (UTC) (envelope-from kostikbel@gmail.com) Received: from kib.kiev.ua (kib.kiev.ua [IPv6:2001:470:d5e7:1::1]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 4GD4sj03rmz4nS4; Mon, 28 Jun 2021 11:20:40 +0000 (UTC) (envelope-from kostikbel@gmail.com) Received: from tom.home (kib@localhost [127.0.0.1]) by kib.kiev.ua (8.16.1/8.16.1) with ESMTPS id 15SBKQUK001356 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NO); Mon, 28 Jun 2021 14:20:29 +0300 (EEST) (envelope-from kostikbel@gmail.com) DKIM-Filter: OpenDKIM Filter v2.10.3 kib.kiev.ua 15SBKQUK001356 Received: (from kostik@localhost) by tom.home (8.16.1/8.16.1/Submit) id 15SBKPxx001339; Mon, 28 Jun 2021 14:20:25 +0300 (EEST) (envelope-from kostikbel@gmail.com) X-Authentication-Warning: tom.home: kostik set sender to kostikbel@gmail.com using -f Date: Mon, 28 Jun 2021 14:20:25 +0300 From: Konstantin Belousov To: Dmitry Chagin Cc: freebsd-hackers@freebsd.org Subject: Re: pondering pi futexes Message-ID: References: List-Id: Technical discussions relating to FreeBSD List-Archive: https://lists.freebsd.org/archives/freebsd-hackers List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-freebsd-hackers@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: X-Spam-Status: No, score=-1.0 required=5.0 tests=ALL_TRUSTED,BAYES_00, DKIM_ADSP_CUSTOM_MED,FORGED_GMAIL_RCVD,FREEMAIL_FROM, NML_ADSP_CUSTOM_MED autolearn=no autolearn_force=no version=3.4.5 X-Spam-Checker-Version: SpamAssassin 3.4.5 (2021-03-20) on tom.home X-Rspamd-Queue-Id: 4GD4sj03rmz4nS4 X-Spamd-Bar: ---- Authentication-Results: mx1.freebsd.org; none X-Spamd-Result: default: False [-4.00 / 15.00]; REPLY(-4.00)[] X-ThisMailContainsUnwantedMimeParts: N On Sun, Jun 27, 2021 at 10:39:35PM +0300, Dmitry Chagin wrote: > > Hi, > some time ago I have changed Linuxulator futexes from sx lock to mtx. > sx was used as it allows copyin/copyout with sx lock held. > to use mtx I have changed the code like: > 1. lock mtx; > 2. disable_pagefaults; > 3. copyin() > 4. enable_pagefaults; > 5. if error > - unlock mtx; > copyin(); > if error == 0 goto 1. > > it works (needto replace copyin() by fueword32()), but pondering pi futexes > imlementation, I see that it is not possible to drop the futex lock on a return > from msleep() path. > > below a simplified FUTEX_LOCK_PI operation, where on enter to the kernel current thread: > > 0. acquire futex lock (which is mtx) > 1. cmpset(0 -> current thread TID), return (0) on success; > 2. fetch() from futex *uaddr (for TID of owner): > - check EDEADLK case (the futex word at *uaddr is already locked by the caller); > - check that is no waiters on *uaddr exists which is waiting via FUTEX_WAIT or > FUTEX_WAIT_BITSET, return (EINVAL) if so; > - cmpset(TID -> (FUTEX_WAITERS|TID)); > - on error, the futex owner changed in user-space, repeat from 1. > 3. Here we have: the owner, one waiter (current thread) and 0 or more waiters > sleeping on a waiting_proc. FUTEX_WAITERS bit is set, so any new waiters go to > the kernel and owner should unlock futex via the FUTEX_UNLOCK_PI op; > 4. Try to find the thread which is associated with the owner’s TID: > - on error, something bad happened, owner died? Clean owner state link? > return (ESRCH). Or if no other waiters? Check this... > - on success: > - save owner state link to the struct futex (save priority); > - check the owner's priority, bump it if needed; > - put the current thread to the waiters list in descending priority order; > - change priority of all waiters if needed; > - msleep on a futex waiting_proc; come back with futex lock held; > - restore own priority? If last waiter?; [ponders..] > - on timeout return (ETIMEDOUT); > - the current thread is the new owner: > bah!! - store() the owner TID to *uaddr; [check what should I do on error..] > - release futex lock; > - return (0). > > is it possible to hold *uaddr page to prevent page faults? I did not followed exact algorithm you trying to describe. Still, I can make two points which could be useful for formulation of the working solution. 1. Umtx AKA FreeBSD native implementation of something very similar to futex, has a concept of the umtx queue chain. The chain owns the mutex lock used for 'fast' ops, but for situations like accesses to userspace, we 'busy' the umtxq chain. De-facto busy state is the hand-rolled sleepable lock, with usual interlocking against chain mutex, and msleep/wakeup inter-thread notifications. 2. If you insist on accessing userspace pages while owning non-sleepable locks, or even sleepable locks which do not compose cleanly with whole VM+VFS+network (the later due to NFS) locking protocols, we do have a technique that can be used. Althought it is complicated and sometimes slow. You already noted half of it above, namely disable of the page faults and copyin_nofault-like operations. Second half is prefaulting, which is done by vm_fault_quick_hold_pages(). There are two ways you can use it. Either you hold the target userspace page, then remap it into KVA and access userspace object through the kernel mapping. This assumes that the object fits into page, also it does not interact with parallel forks and CoW, which you either have to accept to recheck after. The usual races, e.g. userspace remapping the held (actually wired) page under us, is there, of course, but it is a race anyway. Or, you hold the page but still access it using copyin_nofault. Then any reported error from copyin becomes fatal instead of an indicator to retry. Error can happen for the same reason, because userspace could unmap or remap this address under us. Umtx implementation only uses busy on chains, might be because _nofault+ vm_fault_quick_hold() appeared later.