From owner-freebsd-hackers@FreeBSD.ORG  Tue Apr  8 06:34:36 2014
Return-Path: <owner-freebsd-hackers@FreeBSD.ORG>
Delivered-To: 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 DC314E60
 for <hackers@freebsd.org>; Tue,  8 Apr 2014 06:34:36 +0000 (UTC)
Received: from mail-ee0-x235.google.com (mail-ee0-x235.google.com
 [IPv6:2a00:1450:4013:c00::235])
 (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits))
 (Client CN "smtp.gmail.com",
 Issuer "Google Internet Authority G2" (verified OK))
 by mx1.freebsd.org (Postfix) with ESMTPS id 74BBB1958
 for <hackers@freebsd.org>; Tue,  8 Apr 2014 06:34:36 +0000 (UTC)
Received: by mail-ee0-f53.google.com with SMTP id b57so262602eek.12
 for <hackers@freebsd.org>; Mon, 07 Apr 2014 23:34:33 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
 h=sender:from:content-type:content-transfer-encoding:subject:date
 :message-id:to:mime-version;
 bh=iHc3Ume0afyLGJyJbVqNpQFocEeUfPBz8iPe2dIHmRs=;
 b=ZecZLviFN3KFSFMUr5++v34sFz3jhBO8G3YBIYaDGjHi08pScnyoMUGn1v5d04eOrZ
 DWmZCs4EFruk6nyva5XhIRgpq5FkS/jv6ga81MNtivcOKm5/wj7Jhgj/z5CF8oZ7LeZP
 zoHDWA/F78MKcFpVRR2AvroXFaPZHVHnqBy+7xyg1ahfF0NKZCqdI6IviLDYEa7aC2nl
 BVWYJtpbBQZoZ9p7v9Mx9rxFHVVH0NAXuFRLoyHS7fgp4nZypIdlFti0otlSlxtQ+Xfy
 NM8SSmy4iAnzIO9yjswe7MORgc6gdVYrEU7YkcFKNi7YGnu4Em28tyNmKW7tHOCpJ0JU
 56+A==
X-Received: by 10.14.99.68 with SMTP id w44mr205474eef.82.1396938873853;
 Mon, 07 Apr 2014 23:34:33 -0700 (PDT)
Received: from strashydlo.home (adbf56.neoplus.adsl.tpnet.pl. [79.184.5.56])
 by mx.google.com with ESMTPSA id u46sm2577414eel.1.2014.04.07.23.34.33
 for <hackers@freebsd.org>
 (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128);
 Mon, 07 Apr 2014 23:34:33 -0700 (PDT)
Sender: =?UTF-8?Q?Edward_Tomasz_Napiera=C5=82a?= <etnapierala@gmail.com>
From: =?iso-8859-2?Q?Edward_Tomasz_Napiera=B3a?= <trasz@FreeBSD.org>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Subject: Multiple locks and missing wakeup.
Date: Tue, 8 Apr 2014 08:34:30 +0200
Message-Id: <0D69A6A8-43D1-41FB-8C2D-00F5CAD9C86E@FreeBSD.org>
To: hackers@freebsd.org
Mime-Version: 1.0 (Apple Message framework v1283)
X-Mailer: Apple Mail (2.1283)
X-BeenThere: freebsd-hackers@freebsd.org
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Technical Discussions relating to FreeBSD
 <freebsd-hackers.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/options/freebsd-hackers>, 
 <mailto:freebsd-hackers-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-hackers/>
List-Post: <mailto:freebsd-hackers@freebsd.org>
List-Help: <mailto:freebsd-hackers-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>,
 <mailto:freebsd-hackers-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Tue, 08 Apr 2014 06:34:36 -0000

Let's say I have a kernel thread processing elements from a queue,
sleeping until there is work to do; something like this:

mtx_lock(&mtx1);
for (;;) {
	while (!LIST_EMPTY(&list1)) {
		elt = LIST_FIRST(&list1);
		do_stuff(elt);
		LIST_REMOVE(&list1, elt);
	}
	sleep(&list1, &mtx1);
}
mtx_unlock(&mtx1);

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:

mtx_lock(&mtx1);
for (;;) {
	while (!LIST_EMPTY(&list1)) {
		elt = LIST_FIRST(&list1);
		do_stuff(elt);
		LIST_REMOVE(&list1, elt);
	}

	mtx_lock(&mtx2);
	while (!LIST_EMPTY(&list2)) {
		elt = LIST_FIRST(&list2);
		do_other_stuff(elt);
		LIST_REMOVE(&list2, elt);
	}
	mtx_unlock(&mtx2);

	sleep(&list1, &mtx1);
}
mtx_unlock(&mtx1);