Re: [RFC] shared subtrees

From: Mike Waychison (Michael.Waychison_at_Sun.COM)
Date: 02/02/05

  • Next message: Marcelo Tosatti: "Re: A scrub daemon (prezeroing)" 
    Date:	Wed, 02 Feb 2005 14:45:43 -0500
To: Ram <linuxram@us.ibm.com>

    -----BEGIN PGP SIGNED MESSAGE-----
    Hash: SHA1

    Ram wrote:
    > On Tue, 2005-02-01 at 15:21, J. Bruce Fields wrote:
    >
    >>On Tue, Jan 25, 2005 at 01:07:12PM -0800, Ram wrote:
    >>
    >>>If there exists a private subtree in a larger shared subtree, what
    >>>happens when the larger shared subtree is rbound to some other place?
    >>>Is a new private subtree created in the new larger shared subtree? or
    >>>will that be pruned out in the new larger subtree?
    >>
    >>"mount --rbind" will always do at least all the mounts that it did
    >>before the introduction of shared subtrees--so certainly it will copy
    >>private subtrees along with shared ones. (Since subtrees are private by
    >>default, anything else would make --rbind do nothing by default.) My
    >>understanding of Viro's RFC is that the new subtree will have no
    >>connection with the preexisting private subtree (we want private
    >>subtrees to stay private), but that the new copy will end up with
    >>whatever propagation the target of the "mount --rbind" had. (So the
    >>addition of the copy of the private subtree to the target vfsmount will
    >>be replicated on any vfsmount that the target vfsmount propogates to,
    >>and those copies will propagate among themselves in the same way that
    >>the copies of the target vfsmount propagate to each other.)
    >
    >
    > ok. that makes sense. As you said the private subtree shall get copied
    > to the new location, however propogations wont be set in either
    > directions. However I have a rather unusual requirement which forces
    > multiple rbind of a shared subtree within the same shared subtree.
    >
    > I did the calculation and found that the tree simply explodes with
    > vfsstructs. If I mark a subtree within the larger shared tree as
    > private, then the number of vfsstructs grows linearly O(n). However if
    > there was a way of marking a subtree within the larger shared tree as
    > unclonable than the increase in number of vfsstruct is constant.
    >
    > What I am essentially driving at is, can we add another feature which
    > allows me to mark a subtree as unclonable?
    >
    >
    > Read below to see how the tree explodes:
    >
    > to run you through an example:
    >
    > (In case the tree pictures below gets garbled, it can also be seen at
    > http://www.sudhaa.com/~ram/readahead/sharedsubtree/subtree )
    >
    > step 1:
    > lets say the root tree has just two directories with one vfsstruct.
    > root
    > / \
    > tmp usr
    > All I want is to be able to see the entire root tree
    > (but not anything under /root/tmp) to be viewable under /root/tmp/m*
    >
    > step2:
    > mount --make-shared /root
    >
    > mkdir -p /tmp/m1
    >
    > mount --rbind /root /tmp/m1
    >
    > the new tree now looks like this:
    >
    > root
    > / \
    > tmp usr
    > /
    > m1
    > / \
    > tmp usr
    > /
    > m1
    >
    > it has two vfsstructs
    >
    > step3:
    > mkdir -p /tmp/m2
    > mount --rbind /root /tmp/m2

    At this step, you probably shouldn't be using --rbind, but --bind
    instead to only bind a copy of the root vfsmount, so it now looks like:

    > root
    > / \
    > tmp usr
    > / \
    > m1 m2
    > / \ / \
    > tmp usr tmp usr
    > / \ / \
    > m1 m2 m1 m2

    - --
    Mike Waychison
    Sun Microsystems, Inc.
    1 (650) 352-5299 voice
    1 (416) 202-8336 voice

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    NOTICE: The opinions expressed in this email are held by me,
    and may not represent the views of Sun Microsystems, Inc.
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.2.5 (GNU/Linux)
    Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

    iD8DBQFCAS3ndQs4kOxk3/MRAm/qAJ0awCE49/g+HhMdX0MBZnFLSp2IjACgj5EQ
    El+YLq25hQeDAt9Y92nqoAU=
    =so+d
    -----END PGP SIGNATURE-----
    -
    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: Marcelo Tosatti: "Re: A scrub daemon (prezeroing)"

    Relevant Pages

    • Re: [RFC] shared subtrees
      ... >> If there exists a private subtree in a larger shared subtree, ... >> happens when the larger shared subtree is rbound to some other place? ... If I mark a subtree within the larger shared tree as ...
      (Linux-Kernel)
    • Re: [RFC] shared subtrees
      ... > If there exists a private subtree in a larger shared subtree, ... > happens when the larger shared subtree is rbound to some other place? ... addition of the copy of the private subtree to the target vfsmount will ...
      (Linux-Kernel)
    • Re: Copy-on-write tree data structure
      ... >>Let Node be a suitably defined data structure. ... this could be implemented by creating copies both of the tree ... >>strategy that makes copies of shared subtrees only when a shared subtree ... pointers to the unchanged sub-trees below it. ...
      (comp.lang.c)
    • Re: insert number in binary tree
      ... does anyone know how do we insert numbers in a binary tree? ... If this subtree is empty, ... promoting the right successor of the root will fix this: ...
      (comp.programming)
    • Re: How difficult is the firing squad synchronization problem?
      ... interconnections can reach to a global synchrony. ... Suppose that the tree contains only a root and two children (c1 ... The protocol goes as ... subtree manages its own synchrony. ...
      (comp.theory)