From owner-freebsd-hackers@FreeBSD.ORG Tue Apr 8 16:45:55 2014 Return-Path: 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 0497FC97; Tue, 8 Apr 2014 16:45:55 +0000 (UTC) Received: from mail-ee0-x22a.google.com (mail-ee0-x22a.google.com [IPv6:2a00:1450:4013:c00::22a]) (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 4151D16B5; Tue, 8 Apr 2014 16:45:54 +0000 (UTC) Received: by mail-ee0-f42.google.com with SMTP id d17so909886eek.29 for ; Tue, 08 Apr 2014 09:45:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=sender:subject:mime-version:content-type:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=OnH9PEizjo9Nktyvn9ssgc+3mv0Ju4yAEMT0egn0VV4=; b=fJ4xRe3tku97KNH4T2uwBAzs4VlLwEHTqr/Hg+ZZ0TOnhDaioIcQizOPbHvtdoO0sw 6F+PswoCcetR8hNYfROuhyIPeOo3syauHg16Jg6448vU8j+39Lui3KctAE40DUBMGqLL s2RCs2n7ZzJCP2EBUz9KXffNw01Qi+6f8ds3PD/3wPVn6NKQpMUaCYBtyBzVITjjHhqc fi8lha/UZMOh8GSb2J4M//eKCUuLz/xdlZ5kYIt6+iaXPLhpMPTO5Of3kaPuHXn4hfaE vnAGyiYt7q1+LwBS8vopFLMBw3LxsInArRchzs3jETJYm/NvHfYkD06PCY4vGR7vN+8J Pl8A== X-Received: by 10.14.109.201 with SMTP id s49mr3348162eeg.88.1396975552521; Tue, 08 Apr 2014 09:45:52 -0700 (PDT) Received: from strashydlo.home (adbf56.neoplus.adsl.tpnet.pl. [79.184.5.56]) by mx.google.com with ESMTPSA id l42sm5645764eew.19.2014.04.08.09.45.51 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Tue, 08 Apr 2014 09:45:51 -0700 (PDT) Sender: =?UTF-8?Q?Edward_Tomasz_Napiera=C5=82a?= Subject: Re: Multiple locks and missing wakeup. Mime-Version: 1.0 (Apple Message framework v1283) Content-Type: text/plain; charset=iso-8859-2 From: =?iso-8859-2?Q?Edward_Tomasz_Napiera=B3a?= In-Reply-To: <201404081001.31219.jhb@freebsd.org> Date: Tue, 8 Apr 2014 18:45:49 +0200 Content-Transfer-Encoding: quoted-printable Message-Id: References: <0D69A6A8-43D1-41FB-8C2D-00F5CAD9C86E@FreeBSD.org> <201404081001.31219.jhb@freebsd.org> To: John Baldwin X-Mailer: Apple Mail (2.1283) Cc: freebsd-hackers@freebsd.org, hackers@freebsd.org 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 16:45:55 -0000 Wiadomo=B6=E6 napisana przez John Baldwin w dniu 8 kwi 2014, o godz. = 16:01: > On Tuesday, April 08, 2014 2:34:30 am Edward Tomasz Napiera=B3a 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: >=20 > 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. Perhaps I should have been more clear: I'm ok with a single wait channel. The problem is that there is no way to pass more than one mutex to the sleep() function, so we can miss wakeup for the list protected by the second lock, if something gets enqueued between releasing mtx2 and calling sleep(). > 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: The whole purpose of this is to avoid locking mtx1 in the the enqueue routine for the second list, for contention reasons. [..] > 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. But the flag would have to be protected by the mutex we pass to sleep(), and would require grabbing that mutex in both enqueue routines, right?