From owner-freebsd-hackers@freebsd.org Thu Jun 16 16:44:19 2016 Return-Path: Delivered-To: freebsd-hackers@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 54F90A47B0C for ; Thu, 16 Jun 2016 16:44:19 +0000 (UTC) (envelope-from jhb@freebsd.org) 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 372811880 for ; Thu, 16 Jun 2016 16:44:19 +0000 (UTC) (envelope-from jhb@freebsd.org) Received: from ralph.baldwin.cx (c-73-231-226-104.hsd1.ca.comcast.net [73.231.226.104]) by bigwig.baldwin.cx (Postfix) with ESMTPSA id 40941B94E; Thu, 16 Jun 2016 12:44:18 -0400 (EDT) From: John Baldwin To: freebsd-hackers@freebsd.org, Bulat Bulat Subject: Re: Turnstile_purpose_ts_free Date: Thu, 16 Jun 2016 09:36:57 -0700 Message-ID: <4842510.LxNNL3jKi4@ralph.baldwin.cx> User-Agent: KMail/4.14.3 (FreeBSD/10.3-STABLE; KDE/4.14.3; amd64; ; ) In-Reply-To: <1465114041.917499339@f133.i.mail.ru> References: <1465114041.917499339@f133.i.mail.ru> MIME-Version: 1.0 Content-Transfer-Encoding: 7Bit Content-Type: text/plain; charset="us-ascii" X-Greylist: Sender succeeded SMTP AUTH, not delayed by milter-greylist-4.2.7 (bigwig.baldwin.cx); Thu, 16 Jun 2016 12:44:18 -0400 (EDT) X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.22 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 16 Jun 2016 16:44:19 -0000 On Sunday, June 05, 2016 11:07:21 AM Bulat Bulat via freebsd-hackers wrote: > Hi, guys. > > Have little question about implementation of turnstiles in the kernel. > That is, what is the purpose of ts_free list in turnstile structure? > Related file: kern/subr_turnstile.c > > I understand that turnstile is used for tracking non-sleepable locks, tracking > blocked threads on that lock, that > when thread blocks on lock it adds its own turnstile to lock's turnstile's ts_free > list and regrabs any available turnstile from that lock's turnstile's ts_free list when > it is waking up. > > Could you please explain, why algorithm does so, why goes through hassle of > putting turnstile into ts_free only to regrab it from ts_free later, as it stores pointer to own turnstile > and could keep it there, using only when it is the first thread to be blocked on a lock. > > There is definitely logic in using ts_free member, but it is a bit unclear for me. > Would be glad to see your explanation, thanks. The first thread to block on a lock donates its turnstile to that lock. However, that turnstile must remain in place and associated with that lock until all threads have been awakened. This means that the last thread to be awakened is the only thread that can take this turnstile. Thus, suppose you have two threads (T1 and T2) with turnstiles S1 and S2. Suppose T1 blocks on lock L first and T2 blocks second. At that point, S1 is used as the turnstile and S2 is in the ts_free list. If T1 is awakened first, it can't grab S1 as td_turnstile since T2 is still queued. Instead, it grabs S2 from ts_free. Later when T2 is awakened it grabs S1. The result in this case is that turnstiles are swapped between threads. -- John Baldwin