[ACL-Devel] FS meta information (properties/attributes/...)

[Curtis Anderson]

Andreas Gruenbacher wrote: 
> A chained list of blocks (usually just one block) containing something like the
> following struct for each attribute:
> 
> struct attr_entry {
>   __u16    attr_type;     // user or system attribute?
>   __u16    name_offs;
>   __u32    value_block;   // disk block attribute is stored on
>   __u32    value_size;    // size of attribute value
>   __u16    value_offs;    // offset in disk block
> };
> 
> And then somewhere the attribute names:
>   "acl\0dacl\0cap\0\0"   // system attribute names
>   "thumbnail\0\0"        // user attribute names
> 
> Then depending on size, block either points to a direct block, or an indirection
> block. With 1K blocks this gives us 256K per attribute. With 4K blocks we could
> get 4M. Not bad  :-)
> 
> I guess storing the attribute entries consecutively (with the names padded to
> word boundaries) should do.
> 
> Compared to the current approach, we would have one more level of indirection in
> a simple implementation. Maybe that can be improved upon by storing everything
> on the first block if there's enough room (which I expect to be the common
> case).

There are several issues that have to be nailed down in an attribute scheme:
0) how do I find the list of attr structures given the on-disk inode?
1) how do I search the list of attribute names, is there any indexing?
2) how do I point to the value and how do I know how big it is?
3) how do I efficiently pack small names/values into filesystem blocks?
4) how do I insert/delete attribute names, are there index updates?
5) how do I insert/delete/update-in-place attribute values?
6) how do I reclaim space from attribute names that have been deleted?
7) how do I reclaim space from attribute values that have changed size or been deleted?
8) how do I do all that in a transactional way so that the metadata is always good?
9) how do I modify fsck to find and fix problems with attribute structures?

You've got good answers for point 2) and part of 3) so far.  I'd suggest extending
your structure like so to better address point 3):

struct attr_entry {
    __u16    attr_type;     // user or system attribute?
    __u32    name_block;    // disk block name is stored in
    __u16    name_offs;     // offset of name within block
    __u32    value_block;   // disk block value is stored in
    __u32    value_size;    // size of attribute value
    __u16    value_offs;    // offset of value in within block
};

In XFS, I vampired off of the infrastructure built up for directories.  The
attribute name took the place of the filename and I added a new structure field
to point to the attribute value block(s).  I'd suggest looking closely at
something similar here.  There has been a lot of thought put into efficiently
representing/accessing/updating directory contents that you can simply make use
of.  Note that I'm talking about reusing code here, not about making files look
like mini-directories.  I believe you can copy the directory code, update it for
use with attributes, and you've got most of your solution.

In XFS, attribute names are hashed into 32bit numbers and those numbers are used
as the index into a B+ tree.  The leaf nodes in the tree contain a sorted index of
hash values contained in that block plus a miniature heap management system that
tracks free space and structures that contain the actual attribute name strings.
The attribute values are either stored just after the attribute name, if they are
small enough, or in separate blocks.  The entire construct desribed above lives
inside a virtual address space just like the bytes in a regular file and all
"block pointers" are really block offsets relative to the 0 block in the attribute
fork.  If the attribute fork is small enough, it shifts structure to a highly
compact form and lives inside the inode.  If it is a bit larger, it shifts form
and lives inside a single leaf block hanging from the inode.  If it is even larger,
it becomes the full B+ tree described above.

The only difference between attributes in an attribute fork and filenames in a
directory is the addition of the attribute value stored inside the leaf block
or in another block.

The point of the above description is just to show that there can be a whole lot
of detail that you might not want to re-invent if you can vampire off something
that is close enough.  On the other hand, did I mention "overkill", a simplistic
implementation can get most of the value at quite a bit less cost than doing the
full magilla.  YMMV. :-)

Thanks,

	Curtis

-- 
Curtis Anderson - Storage Group Leader		canderson@turbolinux.com
-------------------------------------------------------------------------
Linux ACL Developers List ---  http://acl.bestbits.at/acl-devel/

To unsubscribe, send a message with `unsubscribe acl-devel'
in the message body to majordomo@bestbits.at.
-------------------------------------------------------------------------