Re: mtx_lock_recurse/mtx_unlock_recurse functions (proof-of-concept).

From: John-Mark Gurney (gurney_j_at_efn.org)
Date: 04/09/04

  • Next message: Teemu.Parkkinen_at_patria.fi: "Digital-tv card drivers and API discussion" 
    Date: Fri, 9 Apr 2004 11:01:06 -0700
To: Robert Watson <rwatson@freebsd.org>, Seigo Tanimura <tanimura@tanimura.dyndns.org>, Pawel Jakub Dawidek <pjd@freebsd.org>, freebsd-arch@freebsd.org

    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."
_______________________________________________
freebsd-arch@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-arch
To unsubscribe, send any mail to "freebsd-arch-unsubscribe@freebsd.org"
  • Next message: Teemu.Parkkinen_at_patria.fi: "Digital-tv card drivers and API discussion"

    Relevant Pages