From owner-freebsd-hackers@freebsd.org Sun Apr 9 13:28:53 2017 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 BBEE7D3507E for ; Sun, 9 Apr 2017 13:28:53 +0000 (UTC) (envelope-from vasanth.raonaik@gmail.com) Received: from mail-oi0-x232.google.com (mail-oi0-x232.google.com [IPv6:2607:f8b0:4003:c06::232]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 8053EE6B for ; Sun, 9 Apr 2017 13:28:53 +0000 (UTC) (envelope-from vasanth.raonaik@gmail.com) Received: by mail-oi0-x232.google.com with SMTP id g204so51509505oib.1 for ; Sun, 09 Apr 2017 06:28:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=MvooiGLvDttcl//L/B/qEVo9aBPnzYDm2YR5CZZI1xA=; b=JME6LdWKTYMqwGo62ty6Yi9tziia5GvNv5D470u29z38p9QBKmNm8YgH2DhJs2TE9q FnTilbvcqipZ6bhQ8KAnsRPrrSunmlEN9o1uLeyp3VIVEE3wcsKD2tHJQLfioWVKD7C5 dIVLDaXmb2epdrjtB2kTUHCHCGa7WUDbWsP/Tyyr9O1kSOaQ/zW2x7ccBK6yw5l4gUTx 5YtAG0TfhEi3xFmFIoGSrLm2Vy5yiChxCvFJyCH7Nw9aIp5Ge9xx+oyBWrI6tY0+rIjm cSa1X9QCYVlvq4nnSoonzms+V+wCVCHMJSUPsY+in4SjrwuFoLA1/DhzB2dUz0twcKdR RvuQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=MvooiGLvDttcl//L/B/qEVo9aBPnzYDm2YR5CZZI1xA=; b=AEv6nYpTfaV9FqmnjfEGy5l1nix0bpNwG5X9fnld13knaGiUcM3G6Jj0ql+CC43Q/i xXeaHGxDt2ga8Nurt1FvoYQYyFo71t0jeDwQPYOBjCuE/aZtfywb25DBJDReIUS2A2Cw c5LGXlPxe35l+5lRCCarsbKmw16QuiaDHJE9ClD3rYmWtPkwR1DKvjl+kkScw8xCxEL3 Pj7nT7uU7KnDem3rM2RQ7WtCaB2sDTcigZSTdq73h+8qgVkjzc4e0bHyBhhSfS49MfQ3 jRhdNZseW5cKwI6buoTFu/iYRssyYSMd+EUTT4ruI0F7d8jqZ4049ipo4twBJ/E2r6pz Pvfw== X-Gm-Message-State: AN3rC/4k9xG6DtH7W9WHi/IBz066/NHndLhRDVfOBgQg/lWalSc5lSOPwri0wRloGFI1Hot3UjnPAk1alv47EQ== X-Received: by 10.202.245.137 with SMTP id t131mr798786oih.149.1491744532658; Sun, 09 Apr 2017 06:28:52 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: vasanth sabavat Date: Sun, 09 Apr 2017 13:28:41 +0000 Message-ID: Subject: Re: Understanding the FreeBSD locking mechanism To: Ed Schouten , Yubin Ruan Cc: freebsd-hackers@freebsd.org Content-Type: text/plain; charset=UTF-8 X-Content-Filtered-By: Mailman/MimeDel 2.1.23 X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 09 Apr 2017 13:28:53 -0000 On Sun, Apr 9, 2017 at 3:14 AM Yubin Ruan wrote: > On 2017/4/6 17:31, Ed Schouten wrote: > > Hi Yubin, > > > > 2017-04-06 11:16 GMT+02:00 Yubin Ruan : > >> Does this function provides the ordinary "spinlock" functionality? There > >> is no special "test-and-set" instruction, and neither any extra locking > >> to protect internal data structure manipulation. Isn't this subjected to > >> race condition? > > > > Locking a spinlock is done through macro mtx_lock_spin(), which > > expands to __mtx_lock_spin() in sys/sys/mutex.h. That macro first > > calls into the function you looked at, spinlock_enter(), to disable > > interrupts. It then calls into the _mtx_obtain_lock_fetch() to do the > > test-and-set operation you were looking for. > > Thanks for replying. I have read some of those codes. > > Just a few more questions, if you don't mind: > > (1) why are spinlocks forced to disable interrupt in FreeBSD? > > From the book "The design and implementation of the FreeBSD Operating > System", the authors say "spinning can result in deadlock if a thread > interrupted the thread that held a mutex and then tried to acquire the > mutex"...(section 4.3, Mutex Synchronization, paragraph 4) > > I don't get the point why a spinlock(or *spin mutex* in the FreeBSD > world) has to disable interrupt. Being interrupted does not necessarily > mean a deadlock. Assume that thread A holding a lock T gets interrupted > by another thread B(context switch here) and thread B try to acquire > the lock T. After finding out that lock T has already been acquired, > thread B will just spin until it gets preempted, after which thread A > gets waken up and run and release the lock T. Assume single CPU, If thread B spins where will thread A get to run and finish up its critical section and release the lock? The one CPU you have is held by thread b for spinning. For spin locks on single core, it does not make sense to spin. We just disable interrupts as we are currently the only ones running we just need to make sure no others will get to preempt us. That's why spin locks should be held for short duration. When you have multiple cores, ThreadA can spin on cpu1, while thread B holding the lock on cpu2 can finish up and release it. We disable interrupts only on cpu1 so we don't want to preempt threadA. The cost of preemption is very high compared to short spin. Note: short spin. Look at adaptive spin locks. So, you see there is not > necessarily any deadlock even if thread A get interrupted. > > I can only remember two conditions where using spinlock without > disabling interrupts will cause deadlock: > > #######1, spinlock used in an interrupt handler > If a thread A holding a spinlock T get interrupted and the interrupt > handler responsible for this interrupt try to acquire T, then we have > deadlock, because A would never have a chance to run before the > interrupt handler return, and the interrupt handler, unfortunately, > will continue to spin ... so in this situation, one has to disable > interrupt before spinning. > > As far as I know, in Linux, they provide two kinds of spinlocks: > > spin_lock(..); /* spinlock that does not disable interrupts */ > spin_lock_irqsave(...); /* spinlock that disable local interrupt */ > > > #######2, priority inversion problem > If thread B with a higher priority get in and try to acquire the lock > that thread A currently holds, then thread B would spin, while at the > same time thread A has no chance to run because it has lower priority, > thus not being able to release the lock. > (I haven't investigate enough into the source code, so I don't know > how FreeBSD and Linux handle this priority inversion problem. Maybe > they use priority inheritance or random boosting?) > > thanks, > Yubin Ruan > _______________________________________________ > freebsd-hackers@freebsd.org mailing list > https://lists.freebsd.org/mailman/listinfo/freebsd-hackers > To unsubscribe, send any mail to "freebsd-hackers-unsubscribe@freebsd.org" > -- Thanks, Vasanth