From owner-freebsd-current@FreeBSD.ORG Sun May 26 00:53:02 2013 Return-Path: Delivered-To: freebsd-current@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by hub.freebsd.org (Postfix) with ESMTP id BA3EDF31 for ; Sun, 26 May 2013 00:53:02 +0000 (UTC) (envelope-from asmrookie@gmail.com) Received: from mail-ie0-x22c.google.com (mail-ie0-x22c.google.com [IPv6:2607:f8b0:4001:c03::22c]) by mx1.freebsd.org (Postfix) with ESMTP id 9002815C for ; Sun, 26 May 2013 00:53:02 +0000 (UTC) Received: by mail-ie0-f172.google.com with SMTP id 16so15782028iea.31 for ; Sat, 25 May 2013 17:53:02 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:reply-to:sender:in-reply-to:references:date :x-google-sender-auth:message-id:subject:from:to:cc:content-type; bh=aYSpbisi8sMh9vXu3ep4YoCloW76BLQ391KbWjm86h8=; b=U/OwzGPVuV1I0G2BNkUi1hVa96+SyEKs2YPK0jKCIDnoL6vU+LjYfnY74dWROFaX8X uXbNN+6rVlvvLHxHqDlArERdKm33KwR11QYhVVrnY396eMmXtqUTFEod8PUZIZyfByDn lPlo6jIfa9QNH7LsNmTaLl0mSepORKTp42LkOdxwkq9x7/RdtfhFkfqlb7b6K5/B0vqk HZ1eDbb9O908r/3ES/AuZddiy2IYXI6lsSFrcwl+JANDsL7cGbLHjF2THBya/MhSa/QS BIGsVDZUEyUT0jTmXB4hsNdlFb521D16KjHMRydfiHPDHF/NS9yevpg7UC0Eb6Ms0nRL cY6g== MIME-Version: 1.0 X-Received: by 10.42.168.198 with SMTP id x6mr15258252icy.45.1369529581998; Sat, 25 May 2013 17:53:01 -0700 (PDT) Sender: asmrookie@gmail.com Received: by 10.42.253.129 with HTTP; Sat, 25 May 2013 17:53:01 -0700 (PDT) In-Reply-To: References: Date: Sun, 26 May 2013 02:53:01 +0200 X-Google-Sender-Auth: _x-tPpz0aj41jSOVoRfEuTWc1Kk Message-ID: Subject: Re: Incorrect comparison of ticks in deadlkres From: Attilio Rao To: Ryan Stone Content-Type: text/plain; charset=UTF-8 Cc: FreeBSD Current , arao@freebsd.og X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.14 Precedence: list Reply-To: attilio@FreeBSD.org List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 26 May 2013 00:53:02 -0000 On Sat, May 25, 2013 at 11:55 PM, Ryan Stone wrote: > Currently deadlkres performs the following comparison when trying to check > for threads that have been blocked on a mutex or sleeping on an sx lock: > > if (TD_ON_LOCK(td) && ticks < td->td_blktick) { > /* check for deadlock...*/ Yes the check looks indeed inverted. > > > The test against ticks is incorrect. It results in deadlkres only > signaling a deadlock after ticks has rolled over; at 1000 hz this will take > up to 49 days. From looking at the history of the code this test appears > to be a attempt to deal with ticks rollover. However this is necessary; > later on the code calculates the amount of time that has passed with: > tticks = ticks - td->td_blktick; > > ticks was designed to exploit integer underflow in the case of rollover to > guarantee that subtraction produces correct results in all cases (other > than a double rollover, of course). I am going to remove the two incorrect > tests unless somebody can point out a overflow/underflow case that I > haven't considered. I'm not sure I follow what are you saying. Assume that when thread td goes to sleep, ticks is very close to the 32 bits limit. Then thread td goes to sleep and td->td_blktick is set to a value very close to 32 bits limits. After a while deadlkres thread kicks in and in the while "ticks" counter overflowed, rolling back to a very low value. How are you supposed to compute a valid value from this situation? I think that you need to still guard about overflow of ticks for such cases. Additively, if you really want to improve deadlkres, you should bring into the logic a fix for the adaptive spinning. Think about the schematic LOR case. Because of the adaptive spinning what will happen is that 2 threads getting a deadlock on 2 different locks will just end up spinning. I think you should import some sort of checks just like spinmutexes do, but with much higher time threshhold. Attilio -- Peace can only be achieved by understanding - A. Einstein