linux-kernel - Re: [PATCH] arch/tile: fix rwlock so would-be write lockers don't block new readers

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date:	Thu, 25 Nov 2010 00:37:48 +0800
From:	Cypher Wu <cypher.w@...il.com>
To:	Chris Metcalf <cmetcalf@...era.com>
Cc:	linux-kernel@...r.kernel.org,
	Américo Wang <xiyou.wangcong@...il.com>,
	Eric Dumazet <eric.dumazet@...il.com>,
	netdev <netdev@...r.kernel.org>
Subject: Re: [PATCH] arch/tile: fix rwlock so would-be write lockers don't
 block new readers

2010/11/24 Chris Metcalf <cmetcalf@...era.com>:
> On 11/23/2010 9:53 PM, Cypher Wu wrote:
>> 2010/11/24 Chris Metcalf <cmetcalf@...era.com>:
>>> On 11/22/2010 8:36 PM, Cypher Wu wrote:
>>>> Say, if core A try to write_lock() rwlock and current_ticket_ is 0 and
>>>> it write next_ticket_ to 1, when it processing the lock, core B try to
>>>> write_lock() again and write next_ticket_ to 2, then when A
>>>> write_unlock() it seen that (current_ticket_+1) is not equal to
>>>> next_ticket_, so it increment current_ticket_, and core B get the
>>>> lock. If core A try write_lock again before core B write_unlock, it
>>>> will increment next_ticket_ to 3. And so on.
>>>> This may rarely happened, I've tested it yesterday for several hours
>>>> it goes very well under pressure.
>>> This should be OK when it happens (other than starving out the readers, but
>>> that was the decision made by doing a ticket lock in the first place).
>>> Even if we wrap around 255 back to zero on the tickets, the ticket queue
>>> will work correctly.  The key is not to need more than 256 concurrent write
>>> lock waiters, which we don't.
>> If we count on that, should we make 'my_ticket_ = (val >>
>> WR_NEXT_SHIFT) & WR_MASK;'
>
> No, it's OK.  As the comment for the declaration of "my_ticket_" says, the
> trailing underscore reminds us that the high bits are garbage, and when we
> use the value, we do the mask: "((my_ticket_ - curr_) & WR_MASK)".  It
> turned out doing the mask here made the most sense from a code-generation
> point of view, partly just because of the possibility of the counter wrapping.
>
> --
> Chris Metcalf, Tilera Corp.
> http://www.tilera.com
>
>

If wrap does occurr direct subtraction may cause problem, but
write_lock() is usually only lock very little code, and since two
issue of that call will take us so many cycles that one the same core
the time eslapsed will be enough that wrap will never occurr.


-- 
Cyberman Wu
http://www.meganovo.com
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/