Re: 2.6.11-rc2-mm1

From: Evgeniy Polyakov (johnpol_at_2ka.mipt.ru)
Date: 01/25/05

  • Next message: Valdis.Kletnieks_at_vt.edu: "Re: thoughts on kernel security issues" 
    Date:	Wed, 26 Jan 2005 00:17:34 +0300
To: J_rn Engel <joern@wohnheim.fh-wedel.de>

    On Tue, 25 Jan 2005 19:21:10 +0100
    J_rn Engel <joern@wohnheim.fh-wedel.de> wrote:

    > On Tue, 25 January 2005 19:04:47 +0300, Evgeniy Polyakov wrote:
    > > On Tue, 2005-01-25 at 16:34 +0100, Bartlomiej Zolnierkiewicz wrote:
    > >
    > > > Ugh, now think about that:
    > > >
    > > > CPU0 CPU1
    > > > place1: place2:
    > > > lock a lock b
    > > > < guess what happens here :-) >
    > > > lock b lock a
    > > > ... ...
    > >
    > > :) he-he, such place are in add and remove routings, and they can not be
    > > run simultaneously
    > > in different CPUs.
    >
    > Makes my toenails curl. Something fun I might write someday is a
    > statical (dead-)lock checker. The design is very simple:
    >
    > o Annotate code with the lock that could be taken.
    > o Whenever getting a lock B, write down something like "A->B" for
    > every lock A we already have.
    > o Create a graph from the locking hierarchy obtained above.
    > o Look for cycles.
    >
    > A cycle-free graph means that the code is deadlock-free. In the
    > above, the graph surely has cycles. You could argue that the checker
    > should be smarter, but then again - why should it? Is there a
    > compelling reason why locking schemes as outlined above actually make
    > the code better?

    That will catch only simple cases - for the whole picture you need
    to run graph generator from all allowed code pathes, but that
    will require knowledge of the tested system, so it will not and
    actually can not be absolutely generic.
     
    > J_rn
    >
    > --
    > It does not matter how slowly you go, so long as you do not stop.
    > -- Confucius

            Evgeniy Polyakov

    Only failure makes us experts. -- Theo de Raadt
    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  • Next message: Valdis.Kletnieks_at_vt.edu: "Re: thoughts on kernel security issues"

    Relevant Pages

    • Patch: 2.6.7/fs/dnotify.c - make dn_lock a regular spinlock
      ... declared as rw_lock_t, but the lock is only taken exclusively. ... cycles by changing it to spinlock_t. ... modifying many of the places that call into dnotify. ... send the line "unsubscribe linux-kernel" in ...
      (Linux-Kernel)
    • Re: 2.6.11-rc2-mm1
      ... >> lock a lock b ... Create a graph from the locking hierarchy obtained above. ... the graph surely has cycles. ... send the line "unsubscribe linux-kernel" in ...
      (Linux-Kernel)
    • Re: [RFC, PATCH] locks: remove posix deadlock detection
      ... whether we're adding a cycle to an arbitrary directed acyclic graph. ... And this calculation has to be performed while holding a lock (currently ... EDEADLK behaviour is required by SuSv3 ...
      (Linux-Kernel)
    • Re: How come Ada isnt more popular?
      ... The difference is between a) graph treated as a mesh of nodes which "own" each other and b) graph treated as a collection of nodes. ... The former might have ownership cycles between nodes, but not the latter, where ownership is an acyclic relation between graph and nodes. ... there is a strong argument is that for some class of algorithms it might be beneficial to be able to "drop on the floor" a bigger part of the graph altogether. ...
      (comp.lang.ada)
    • Elecsol batteries (again)
      ... Look at the graph at the bottom. ... D.O.D. means Depth of Discharge. ... cycles for various D.O.D.s between 50% and 100%. ... sense in that the deeper the discharge, the less life cycles each ...
      (uk.rec.waterways)