Date: Fri, 9 Apr 2004 11:01:06 -0700 From: John-Mark Gurney <gurney_j@efn.org> To: Robert Watson <rwatson@freebsd.org>, Seigo Tanimura <tanimura@tanimura.dyndns.org>, Pawel Jakub Dawidek <pjd@freebsd.org>, freebsd-arch@freebsd.org Subject: Re: mtx_lock_recurse/mtx_unlock_recurse functions (proof-of-concept). Message-ID: <20040409180106.GM567@funkthat.com> In-Reply-To: <20040409165757.GL567@funkthat.com> References: <200404090853.i398rwAq029617@urban> <Pine.NEB.3.96L.1040409103002.62857B-100000@fledge.watson.org> <20040409165757.GL567@funkthat.com>
next in thread | previous in thread | raw e-mail | index | archive | help
John-Mark Gurney wrote this message on Fri, Apr 09, 2004 at 09:57 -0700:
> I have devised a locking method that I believe will work with the
> current architecture of kqueue. And it doesn't involve adding a lock
> to any KNOTEs... It's handled solely by object and kqueue lock. If you
> want a copy, I can send it to you.. Or should I repost it here?
By request, I am reposting the brief document that I wrote describing
my idea to put kqueues under locks:
Just to let others know about the work on this. I think I have a
solution for the locking of kqueues, but it is compilicated by the
fact that there are linked lists that belong to both the kqueue and
the object that kqueue is watching, and each need to be protected by
a seperate locks, yet both need to be obtained in different orders...
so, I came up with an algorithm that is able to treat both locks as
leaf locks, yet avoid deadlock... There might be a better implementation
of this, so input would be helpful...
Basicly, we have two different call paths for kqueue:
a) adding an event from userland:
create knote
add knote to kqueue
add knote to watch object
b) marking an event as ready/available via object:
add knote to kqueue's active list
Now the problem is that there needs to be locks for both the kqueue
and the object, and they need to be seperate locks, yet, they both
need to be obtained in different orders... So, the solution I came
up with is something similar to a read/write lock...
Assumptions:
1) holding the kqueue lock means that any knotes on the kqueue
are valid, and the objects referenced by the knotes are also
valid..
2) holding the object lock means that all knotes associated with
the object are valid and that the kqueue of all knote's are also
valid..
Now, the nice thing about 2 is that you can reference a kqueue w/o
holding it's lock, but of course you can't maniuplate it.. and of
course thats the same with 1, is that you can reference the object
of all the knotes associated with the kqueue...
The solution is to introduce a flag, locked by the kqueue lock, that
needs to be obtained before you can manipulate the kqueue.. Nothing
special needs to be done for the object... What now happens is that
nothing special happens in case a above, the flag is obtained as if
it's a normal lock (we man want to switch this for performance
reasons, but this way makes it more generic)...
but in case b, once we have obtained the object lock, we can now walk
the list of KNOTEs that we need to activate.. We then attempt to grab
the flag associated with the kqueue that we are trying to put the KNOTE
on.. If we can't, before we release the lock that protects the flag,
we unlock our object lock, and then msleep on the kqueue lock and using
P_DROP (since the lock isn't guranteed to be valid to reaquire since
we don't have our object lock anymore).. We then do a wakeup on the
kqueue lock when ever we release the flag, and this will then give
all the objects waiting for the kqueue to become available to restart
processing of their KNOTE queue...
There are possible optimizations, like walking the rest of the list
of KNOTEs associated with the object in a failure case, and retry
again, etc. But I want to make sure that the locking works and won't
cause a problem...
How does this sound to people? I have some code starting to implement
this, but I haven't gotten very far with it yet...
--
John-Mark Gurney Voice: +1 415 225 5579
"All that I will do, has been done, All that I have, has not."
--
John-Mark Gurney Voice: +1 415 225 5579
"All that I will do, has been done, All that I have, has not."
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20040409180106.GM567>