From owner-freebsd-hackers@FreeBSD.ORG Tue Apr 8 14:01:48 2014 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id 83E15D44; Tue, 8 Apr 2014 14:01:48 +0000 (UTC) Received: from bigwig.baldwin.cx (bigwig.baldwin.cx [IPv6:2001:470:1f11:75::1]) (using TLSv1 with cipher DHE-RSA-CAMELLIA256-SHA (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 5CFC6152A; Tue, 8 Apr 2014 14:01:48 +0000 (UTC) Received: from jhbbsd.localnet (unknown [209.249.190.124]) by bigwig.baldwin.cx (Postfix) with ESMTPSA id 75090B926; Tue, 8 Apr 2014 10:01:47 -0400 (EDT) From: John Baldwin To: freebsd-hackers@freebsd.org Subject: Re: Multiple locks and missing wakeup. Date: Tue, 8 Apr 2014 10:01:31 -0400 User-Agent: KMail/1.13.5 (FreeBSD/8.4-CBSD-20130906; KDE/4.5.5; amd64; ; ) References: <0D69A6A8-43D1-41FB-8C2D-00F5CAD9C86E@FreeBSD.org> In-Reply-To: <0D69A6A8-43D1-41FB-8C2D-00F5CAD9C86E@FreeBSD.org> MIME-Version: 1.0 Content-Type: Text/Plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <201404081001.31219.jhb@freebsd.org> X-Greylist: Sender succeeded SMTP AUTH, not delayed by milter-greylist-4.2.7 (bigwig.baldwin.cx); Tue, 08 Apr 2014 10:01:47 -0400 (EDT) Cc: hackers@freebsd.org, Edward Tomasz =?utf-8?q?Napiera=C5=82a?= X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.17 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 08 Apr 2014 14:01:48 -0000 On Tuesday, April 08, 2014 2:34:30 am Edward Tomasz Napiera=C5=82a wrote: > Let's say I have a kernel thread processing elements from a queue, > sleeping until there is work to do; something like this: >=20 > mtx_lock(&mtx1); > for (;;) { > while (!LIST_EMPTY(&list1)) { > elt =3D LIST_FIRST(&list1); > do_stuff(elt); > LIST_REMOVE(&list1, elt); > } > sleep(&list1, &mtx1); > } > mtx_unlock(&mtx1); >=20 > Now, is there some way to make it work with two lists, protected > by different mutexes? The mutex part is crucial here; the whole > point of this is to reduce lock contention on one of the lists. The > following code would result in a missing wakeup: All our sleep primitives in the kernel only accept a single wait channel. It sounds like you want something more like select() or poll() where you can specify multiple wait channels. There isn't a good way to do that currently. You could write one, but it would be a bit hard to do correctly. In practice you'd end up implementing something that boiled down to having a single wait channel with a common lock that protected it so you could do something like: for (;;) { mtx_lock(&combo_lock); while (LIST_EMPTY(&list1) && LIST_EMPTY(&list2)) sleep(&shared_cv, &combo_lock); mtx_unlock(&combo_lock); /* Drain each list */ } The code to queue an item would then need to do something like: mtx_lock(&mtx1); mtx_lock(&combo_lock); LIST_INSERT(&list1, ...); wakeup(&shared_cv); mtx_unlock(&combo_lock); wakeup(&list1); /* If other waiters */ mtx_unlock(&mtx1); Another way to do this would be to be a bit more poll-like (e.g. if you wanted a generic mechanism for this) where you have some sort of 'poller' structure and you set a flag before starting a scan of all your backends. Any wakeup that occurs while scanning clears the flag, and you only sleep if the flag is still set at the end of the scan, etc. =2D-=20 John Baldwin