From owner-freebsd-hackers@freebsd.org Sun Apr 9 15:56:36 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 D99EBD365C9 for ; Sun, 9 Apr 2017 15:56:36 +0000 (UTC) (envelope-from ablacktshirt@gmail.com) Received: from mail-pg0-x241.google.com (mail-pg0-x241.google.com [IPv6:2607:f8b0:400e:c05::241]) (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 A7AF27A1 for ; Sun, 9 Apr 2017 15:56:36 +0000 (UTC) (envelope-from ablacktshirt@gmail.com) Received: by mail-pg0-x241.google.com with SMTP id 81so22803373pgh.3 for ; Sun, 09 Apr 2017 08:56:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=subject:to:references:cc:from:message-id:date:user-agent :mime-version:in-reply-to:content-transfer-encoding; bh=8yKtTJGqBRM5lN7JcFOLcgahMmg9BBFrov2P3XgjQiM=; b=TtrSR+cnwoyzQyyR0+WPMMc/0Szy+JWVz0nm3nrV9xEvswRQ5ugJtK/zKNLFwhQRSz 3XHJPJB5JL8L15JmNYl7Q109N1wWSygtY0ZPom5/jW1iujSpQPUCsyLp+sqOCv2rjO7G 6ZTOdzCaok6j32t0JCVWVkUD7A/8XBsAcLg/XbXm3hmeEmOvHZwiPZ6icmkrvLjuwQDq 2CI96FOfmmR08G7L0VZm08GF3zCrHoH3QXXxHC9u3O8l+oARco7je0GgsRwOJ7Gh5Hcf t0/jOhACsKghzMYWcszXx/lwkF132cj2ffWXST+w0CKJeqlQEFsfUfzmIJzWjqKevByn aXgA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:references:cc:from:message-id:date :user-agent:mime-version:in-reply-to:content-transfer-encoding; bh=8yKtTJGqBRM5lN7JcFOLcgahMmg9BBFrov2P3XgjQiM=; b=VFbpv93sHljt7zpwBZQuHeauKFKKbQBBeRYa2iYNU6nGPLNEXlRlc9lIwyVZRX9K4v XbRymTceWVo82lBv9Id/pvEfnM2G6QYxI1xxIJDFYN0aERO5BH44+fN56h5wbeLqxNqR vJoisICvGGGFq2QhQfbbq/bYJHdTJ5D2HvYzgsNefOBbUEhZWkH2jWk96fbG9F2jw/X4 70u6oTEuGKf+O9dCzcBg0ax70YP/uMQDsbs7q0YX1qw1K4vNjkirYw8IznkcZOYnx3Ke I5Ye9m0ldZhG9wOfy90AMoYPJIbegPZVShP66oDQQilcu/T1vjOc+fjcHPIhcQIgQ05h giUw== X-Gm-Message-State: AFeK/H3nwWI5SDsFFlKoObg+DhST2Sfnl5Qim3NAiK0O3eIwMEEm1IQdYDNpirJVf7PiVg== X-Received: by 10.84.231.193 with SMTP id g1mr48577104pln.84.1491753396150; Sun, 09 Apr 2017 08:56:36 -0700 (PDT) Received: from [192.168.0.100] ([110.64.91.54]) by smtp.gmail.com with ESMTPSA id f1sm19719389pfc.105.2017.04.09.08.56.32 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 09 Apr 2017 08:56:34 -0700 (PDT) Subject: Re: Understanding the FreeBSD locking mechanism To: vasanth sabavat References: Cc: Ed Schouten , freebsd-hackers@freebsd.org From: Yubin Ruan Message-ID: Date: Sun, 9 Apr 2017 23:56:29 +0800 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.7.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit 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 15:56:36 -0000 On 2017/4/9 21:28, vasanth sabavat wrote: > > 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. Can't the scheduler preempt thread B and put thread A to run? After all, we did not disable interrupt. regards, Yubin Ruan > > 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