[RFC] vfs generic subtree support

[RFC] vfs generic subtree support

[Dmitry Monakhov]

Initially i've posted RFC patch-set which add subtree support for ext4.
http://marc.info/?l=linux-ext4&m=126563931215496&w=2
But in fact this is rather generic feature which may be implemented 
in vfs layer similar to namespace or security feature.

A subtree of a directory tree T is a tree consisting of a directory
(the subtree root) in T and all of its descendants in T.

Subtree assumptions:
* Each inode has subtree id (this id is stored inside inode).
* Subtree id is inherent from parent directory if corresponding flag is set
* Inode can not belongs to different subtrees

i've ommit subtree_type feature in order to simplify brief explanation.

Subtree with id == 0 has special meaning. It may contains roots of
other subtrees (this feature is used for cross subtree renames)
This feature has much in common with XFS project_id.

There are many usecases for such subtrees
1) Choroot environment or Containers on common file-system
   administrator creates a subtree,and setup quota
   #mkdir chroot-env
   #chattr -Q ${subtree_id} chroot-env
   #tar jxf /tmp/fedora-x86_64.tar.bz2 -C chroot-env
   #### as soon as subtree id inherented from parent untared content
   #### automatically belongs to ${subtree_id}
   #quotactl --type=subtree --id=${subtree_id} --bsoft=1000000 --bhard=1000000
   ###
   #chroot chroot-env /bin/bash
2) NFS quota on server side
   Administrator perform exactly the same stages, but instead of chroot
   hi just export result subtree to nfs server
One may imagine it's own usecase.


Usually we already have some content which we want to see as subtree
In this case we have to in-depth traverse it from the subtree root.
add_to_subtree(dir, subtree_id) /* in-depth  tree traversal */
{
	while(de = getdents(dir)) {
	     if (IS_DIR(de))
		    add_to_subtree(de, subtree_id)
             else
	            set_subtree_id(de, subtree);
       }
       set_subtree_id(de, subtree);
}
It is possible to manipulate subtree content

For example we have following hierarchy
/root/subtree-1/a/b/c/d/e/f/g
/root/subtree-2/dir/
want rename /root/subtree-1/a to /root/subtree-2/dir/AA
first we have to move "a" to default tree "root"
 #rename /root/subtree-1/a /root/a-1
Then we have assign to default subtree. Do it in width traverse order
Because otherwise this result in subtree assumptions violation.
 #walk_in_width(/root/AA, 0 /* default subtree */)
Then  assign target subtree_id
 #walk_in_depth(/root/AA, 2)
Ok now all content from /root/a-1 belongs to subtree_id == 2 so it is possible
rename it in to target place
 #rename /root/a-1 /root/subtree-2/dir/AA

Re: [RFC] vfs generic subtree support

[Al Viro]

On Tue, Feb 16, 2010 at 01:52:43PM +0300, Dmitry Monakhov wrote:
> Initially i've posted RFC patch-set which add subtree support for ext4.
> http://marc.info/?l=linux-ext4&m=126563931215496&w=2
> But in fact this is rather generic feature which may be implemented 
> in vfs layer similar to namespace or security feature.
> 
> A subtree of a directory tree T is a tree consisting of a directory
> (the subtree root) in T and all of its descendants in T.
> 
> Subtree assumptions:
> * Each inode has subtree id (this id is stored inside inode).
> * Subtree id is inherent from parent directory if corresponding flag is set
> * Inode can not belongs to different subtrees
> 
> i've ommit subtree_type feature in order to simplify brief explanation.
> 
> Subtree with id == 0 has special meaning. It may contains roots of
> other subtrees (this feature is used for cross subtree renames)
> This feature has much in common with XFS project_id.

Um.  Just how is it different from having normal subtrees mounted separately?
And what's the ID for?

We already can mount arbitrary subtrees of directory tree from given fs,
as many times as we want and in as many places as we like.  With each
mountpoint acting as barrier to link() and rename().

Re: [RFC] vfs generic subtree support

[Dmitry Monakhov]

Al Viro <viro@ZenIV.linux.org.uk> writes:

> On Tue, Feb 16, 2010 at 01:52:43PM +0300, Dmitry Monakhov wrote:
>> Initially i've posted RFC patch-set which add subtree support for ext4.
>> http://marc.info/?l=linux-ext4&m=126563931215496&w=2
>> But in fact this is rather generic feature which may be implemented 
>> in vfs layer similar to namespace or security feature.
>> 
>> A subtree of a directory tree T is a tree consisting of a directory
>> (the subtree root) in T and all of its descendants in T.
>> 
>> Subtree assumptions:
>> * Each inode has subtree id (this id is stored inside inode).
>> * Subtree id is inherent from parent directory if corresponding flag is set
>> * Inode can not belongs to different subtrees
>> 
>> i've ommit subtree_type feature in order to simplify brief explanation.
>> 
>> Subtree with id == 0 has special meaning. It may contains roots of
>> other subtrees (this feature is used for cross subtree renames)
>> This feature has much in common with XFS project_id.
>
> Um.  Just how is it different from having normal subtrees mounted separately?
> And what's the ID for?
For example for quota needs. With subtree support we can account some
subtree in to corresponding quota_subtree id.
>
> We already can mount arbitrary subtrees of directory tree from given fs,
> as many times as we want and in as many places as we like.  With each
> mountpoint acting as barrier to link() and rename().

Re: [RFC] vfs generic subtree support

[Al Viro]

On Tue, Feb 16, 2010 at 03:37:58PM +0300, Dmitry Monakhov wrote:

> > Um.  Just how is it different from having normal subtrees mounted separately?
> > And what's the ID for?
> For example for quota needs. With subtree support we can account some
> subtree in to corresponding quota_subtree id.

What does that have to do with tree topology?  Having it inherited from
parent is fine, but the rest...  If you want to prevent renames/links
across an arbitrary subtree boundary, you can already have such policy
without any kernel changes; just mount them separately.  I'm afraid
I still don't get it...

I certainly see a point in having some kind of "quota group ID" assigned
to fs objects, but that seems to be completely independent from any
tree topology considerations.

Again, setting up a barrier is as simple as adding
	/foo/bar /foo/bar none bind,rw 0 0
in /etc/fstab or doing
	mount --bind /foo/bar /foo/bar
when (or after) you've mounted your fs.  Or
	for i in /foo/*; do mount --bind $i $i; done
if you want all top-level subdirectories in /foo to be barriers, etc.
Either will prevent objects from one subtree to be renamable/linkable
from another.  Can be arbitrary nested as well...

IOW, that looks like a trivially implemented policy that might or might not
be desirable for specific setup, but I don't see the reason to tie this quota
groups stuff to it or to its reimplementation...

Re: [RFC] vfs generic subtree support

[Dmitry Monakhov]

Al Viro <viro@ZenIV.linux.org.uk> writes:

> On Tue, Feb 16, 2010 at 03:37:58PM +0300, Dmitry Monakhov wrote:
>
>> > Um.  Just how is it different from having normal subtrees mounted separately?
>> > And what's the ID for?
>> For example for quota needs. With subtree support we can account some
>> subtree in to corresponding quota_subtree id.
>
> What does that have to do with tree topology?  Having it inherited from
> parent is fine, but the rest...  If you want to prevent renames/links
> across an arbitrary subtree boundary, you can already have such policy
> without any kernel changes; just mount them separately.  I'm afraid
> I still don't get it...
>
> I certainly see a point in having some kind of "quota group ID" assigned
> to fs objects, but that seems to be completely independent from any
> tree topology considerations.
Agree "subtree" is not really good word this. Because it may be useful
not only for subtrees. Also "quota group id" IMHO not really good (at
leas it is ambiguous).

Let's call it "metagroup" id. If you know better (more descriptive) word
for this purpose i please make your suggestion.

- Such metagroup may be assigned to inode. And this id is stored on
  inode.
- It may be inherent from parent, if corresponding flag is set 
  on parent dir.
- metagroup id may be used by generic quota.
- metagroup id has no in common with link/rename behavior,
  bind mount is responsible for such behavior.
Are you agree with following conception?
>
> Again, setting up a barrier is as simple as adding
> 	/foo/bar /foo/bar none bind,rw 0 0
> in /etc/fstab or doing
> 	mount --bind /foo/bar /foo/bar
> when (or after) you've mounted your fs.  Or
> 	for i in /foo/*; do mount --bind $i $i; done
> if you want all top-level subdirectories in /foo to be barriers, etc.
> Either will prevent objects from one subtree to be renamable/linkable
> from another.  Can be arbitrary nested as well...
>
> IOW, that looks like a trivially implemented policy that might or might not
> be desirable for specific setup, but I don't see the reason to tie this quota
> groups stuff to it or to its reimplementation...

Re: [RFC] vfs generic subtree support

[Al Viro]

On Tue, Feb 16, 2010 at 05:01:36PM +0300, Dmitry Monakhov wrote:

> Let's call it "metagroup" id. If you know better (more descriptive) word
> for this purpose i please make your suggestion.
> 
> - Such metagroup may be assigned to inode. And this id is stored on
>   inode.
> - It may be inherent from parent, if corresponding flag is set 
>   on parent dir.
> - metagroup id may be used by generic quota.

I would probably like to see example with fewer "may" and more details ;-)
Seriously, what kind of rules and uses for it do you have in mind?  More
specific example would be nice...

Re: [RFC] vfs generic subtree support

[Dmitry Monakhov]

Al Viro <viro@ZenIV.linux.org.uk> writes:

> On Tue, Feb 16, 2010 at 05:01:36PM +0300, Dmitry Monakhov wrote:
>
>> Let's call it "metagroup" id. If you know better (more descriptive) word
>> for this purpose i please make your suggestion.
>> 
>> - Such metagroup may be assigned to inode. And this id is stored on
>>   inode.
>> - It may be inherent from parent, if corresponding flag is set 
>>   on parent dir.
- if inherent flag is not set, then inherent metagroup id
  from mnt_root 
>> - metagroup id may be used by generic quota.
>
> I would probably like to see example with fewer "may" and more details ;-)
> Seriously, what kind of rules and uses for it do you have in mind?  More
> specific example would be nice...
Use-cases:
*Assing maximum disc space consumption for some hierarchy *

  1) Create chroot environment
    # tar  xf chroot_env.tar /var/xxx/chroot
  2) Assign some metagroup id to the chroot content (via not yet
     existent ./metagroup cmd-tool)
    # find /var/xxx/chroot  | xargs ./metagroup --set 1000

  3) Setup quota limits
    # quota-set --type metagroup --blk_soft=1024M blk_hard=1024M /var

  4) Export this tree (it may be more complex)
    # mount /var/xxx/chroot /mnt/chroot -obound

  5)Now we may use this /mnt/chroot as:
    5A) A regular chroot envirement, user is unable to exceed metagroup
        quota, regardless to real available space on /var/
    5B) As a container's (namespace) root. 
    5C) export this /mnt/chroot to nfs server and nfs client can not
        overcome given metagroup quota limit. 

Re: [RFC] vfs generic subtree support

[Matthew Wilcox]

On Tue, Feb 16, 2010 at 06:00:32PM +0300, Dmitry Monakhov wrote:
> Use-cases:
> *Assing maximum disc space consumption for some hierarchy *
> 
>   1) Create chroot environment
>     # tar  xf chroot_env.tar /var/xxx/chroot
>   2) Assign some metagroup id to the chroot content (via not yet
>      existent ./metagroup cmd-tool)
>     # find /var/xxx/chroot  | xargs ./metagroup --set 1000
> 
>   3) Setup quota limits
>     # quota-set --type metagroup --blk_soft=1024M blk_hard=1024M /var
> 
>   4) Export this tree (it may be more complex)
>     # mount /var/xxx/chroot /mnt/chroot -obound
> 
>   5)Now we may use this /mnt/chroot as:
>     5A) A regular chroot envirement, user is unable to exceed metagroup
>         quota, regardless to real available space on /var/
>     5B) As a container's (namespace) root. 
>     5C) export this /mnt/chroot to nfs server and nfs client can not
>         overcome given metagroup quota limit. 

This all seems quota-related ... do you envisage uses that aren't
quota-related?

-- 
Matthew Wilcox				Intel Open Source Technology Centre
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Re: [RFC] vfs generic subtree support

[Dmitry Monakhov]

Matthew Wilcox <matthew@wil.cx> writes:

> On Tue, Feb 16, 2010 at 06:00:32PM +0300, Dmitry Monakhov wrote:
>> Use-cases:
>> *Assing maximum disc space consumption for some hierarchy *
>> 
>>   1) Create chroot environment
>>     # tar  xf chroot_env.tar /var/xxx/chroot
>>   2) Assign some metagroup id to the chroot content (via not yet
>>      existent ./metagroup cmd-tool)
>>     # find /var/xxx/chroot  | xargs ./metagroup --set 1000
>> 
>>   3) Setup quota limits
>>     # quota-set --type metagroup --blk_soft=1024M blk_hard=1024M /var
>> 
>>   4) Export this tree (it may be more complex)
>>     # mount /var/xxx/chroot /mnt/chroot -obound
>> 
>>   5)Now we may use this /mnt/chroot as:
>>     5A) A regular chroot envirement, user is unable to exceed metagroup
>>         quota, regardless to real available space on /var/
>>     5B) As a container's (namespace) root. 
>>     5C) export this /mnt/chroot to nfs server and nfs client can not
>>         overcome given metagroup quota limit. 
>
> This all seems quota-related ... do you envisage uses that aren't
> quota-related?
Yes. Since link/rename behavior is no longer depends on metagroup
I'm consider it as quota related only.  

Re: [RFC] vfs generic subtree support

[J. Bruce Fields]

On Tue, Feb 16, 2010 at 06:32:47PM +0300, Dmitry Monakhov wrote:
> Matthew Wilcox <matthew@wil.cx> writes:
> 
> > On Tue, Feb 16, 2010 at 06:00:32PM +0300, Dmitry Monakhov wrote:
> >> Use-cases:
> >> *Assing maximum disc space consumption for some hierarchy *
> >> 
> >>   1) Create chroot environment
> >>     # tar  xf chroot_env.tar /var/xxx/chroot
> >>   2) Assign some metagroup id to the chroot content (via not yet
> >>      existent ./metagroup cmd-tool)
> >>     # find /var/xxx/chroot  | xargs ./metagroup --set 1000
> >> 
> >>   3) Setup quota limits
> >>     # quota-set --type metagroup --blk_soft=1024M blk_hard=1024M /var
> >> 
> >>   4) Export this tree (it may be more complex)
> >>     # mount /var/xxx/chroot /mnt/chroot -obound
> >> 
> >>   5)Now we may use this /mnt/chroot as:
> >>     5A) A regular chroot envirement, user is unable to exceed metagroup
> >>         quota, regardless to real available space on /var/
> >>     5B) As a container's (namespace) root. 
> >>     5C) export this /mnt/chroot to nfs server and nfs client can not
> >>         overcome given metagroup quota limit. 
> >
> > This all seems quota-related ... do you envisage uses that aren't
> > quota-related?
> Yes. Since link/rename behavior is no longer depends on metagroup
> I'm consider it as quota related only.  

It'd allow nfsd to implement export subtrees safely.

(The current problem: there's not an easy way to determine whether an
inode (looked up from a filehandle) is reachable from a given directory.
So if you export a directory that isn't the root of a filesystem, you
have an unfortunate choice:

	- turn on the "subtree_check" export option: add information
	  sufficient to lookup the parent directory to each filehandle.
	  But then filehandles change (and clients get ESTALE) on
	  cross-directory rename.

	- Accept the possibility that someone could fake up a filehandle
	  that grants access to files outside the exported subtree.  OK
	  if you're exporting the subtree just for convenience, but bad
	  if you're exporting /usr/local and think /etc/some-secret is
	  safe without /usr/local being on a separate partition.

With subtrees presumably we could stick the subtree-id in the
filehandle, and the subtree would provide a security boundary that's
easy to check on filehandle lookup (by comparing the subtree-id in the
filehandle to the one in the inode you find).  And subtrees would be
simpler to manage than separate partitions.)

--b.

Re: [RFC] vfs generic subtree support

[Christoph Hellwig]

On Tue, Feb 16, 2010 at 02:25:40PM -0500, J. Bruce Fields wrote:
> It'd allow nfsd to implement export subtrees safely.
> 
> (The current problem: there's not an easy way to determine whether an
> inode (looked up from a filehandle) is reachable from a given directory.
> So if you export a directory that isn't the root of a filesystem, you
> have an unfortunate choice:
> 
> 	- turn on the "subtree_check" export option: add information
> 	  sufficient to lookup the parent directory to each filehandle.
> 	  But then filehandles change (and clients get ESTALE) on
> 	  cross-directory rename.
> 
> 	- Accept the possibility that someone could fake up a filehandle
> 	  that grants access to files outside the exported subtree.  OK
> 	  if you're exporting the subtree just for convenience, but bad
> 	  if you're exporting /usr/local and think /etc/some-secret is
> 	  safe without /usr/local being on a separate partition.
> 
> With subtrees presumably we could stick the subtree-id in the
> filehandle, and the subtree would provide a security boundary that's
> easy to check on filehandle lookup (by comparing the subtree-id in the
> filehandle to the one in the inode you find).  And subtrees would be
> simpler to manage than separate partitions.)

NFS exporting is in fact the reason why the XFS hierachial project
quotas were added, but only for space usage accounting and enforcement
reason.  Adding the project ID to the file handles does indeed sound
like a good idea, I'll see if it's easily implementable.

Note that in the end the best idea would be to simply allow mounting
multiple of these roots inside a single superblock.  David Howell's
infrastructure for sharing a nfs superblock for multiple blocks
allows this, and I even implemented prototypes of this for ext2 and
xfs, and a rather mutilated version of my patches is still in btrfs.

> 
> --b.
> --
> To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
---end quoted text---

Re: [RFC] vfs generic subtree support

[J. Bruce Fields]

On Tue, Feb 16, 2010 at 02:32:05PM -0500, Christoph Hellwig wrote:
> On Tue, Feb 16, 2010 at 02:25:40PM -0500, J. Bruce Fields wrote:
> > It'd allow nfsd to implement export subtrees safely.
> > 
> > (The current problem: there's not an easy way to determine whether an
> > inode (looked up from a filehandle) is reachable from a given directory.
> > So if you export a directory that isn't the root of a filesystem, you
> > have an unfortunate choice:
> > 
> > 	- turn on the "subtree_check" export option: add information
> > 	  sufficient to lookup the parent directory to each filehandle.
> > 	  But then filehandles change (and clients get ESTALE) on
> > 	  cross-directory rename.
> > 
> > 	- Accept the possibility that someone could fake up a filehandle
> > 	  that grants access to files outside the exported subtree.  OK
> > 	  if you're exporting the subtree just for convenience, but bad
> > 	  if you're exporting /usr/local and think /etc/some-secret is
> > 	  safe without /usr/local being on a separate partition.
> > 
> > With subtrees presumably we could stick the subtree-id in the
> > filehandle, and the subtree would provide a security boundary that's
> > easy to check on filehandle lookup (by comparing the subtree-id in the
> > filehandle to the one in the inode you find).  And subtrees would be
> > simpler to manage than separate partitions.)
> 
> NFS exporting is in fact the reason why the XFS hierachial project
> quotas were added, but only for space usage accounting and enforcement
> reason.  Adding the project ID to the file handles does indeed sound
> like a good idea, I'll see if it's easily implementable.
> 
> Note that in the end the best idea would be to simply allow mounting
> multiple of these roots inside a single superblock.

I lost you there.

--b.

> David Howell's
> infrastructure for sharing a nfs superblock for multiple blocks
> allows this, and I even implemented prototypes of this for ext2 and
> xfs, and a rather mutilated version of my patches is still in btrfs.