[Tux3] More xattr design details

[Daniel Phillips]

On Wednesday 10 September 2008 15:52, Daniel Phillips wrote:
> Choose a solution:
> 
>   1) Ignore the problem and hope it never bites (typical)
> 
>   2) Refcount all atoms and delete any that fall to zero
> 
>   3) Garbage collect unused atoms from time to time

On Wednesday 10 September 2008 18:23, Benjamin K. Stuhl wrote:
> I have an argument for going with solution 1 or 3, maybe depending on
> filesystem size: we basically have to keep a copy of the atom table in
> memory at all times, otherwise we have to fetch a bunch of blocks
> everytime someone calls setxattr().

It is not as bad as that, it is just a probe or two into the buffer
cache, where each probe is just a lookup in a very small radix tree,
normally a single level.  We could put a small hash in front of that
if it matters, which would save not only the radix tree probe but the
iteration through the dentry block, and replace it with iterating down
a hash chain.  Not a hugely obvious difference I expect, but also
pretty easy to write, so if/when it gets to be the most annoying thing
about Tux3 then it will go in.

> I see two general cases for 
> filesystems:
>   1. filesystem size >> RAM: this is the common case for everything except
> USB thumb drives, and if the atom table is large enough to matter in terms
> of disk usage, it's already getting cramped by main memory
>   2. filesystem size <= RAM: for all modern media, this is small enough
> that garbage collection should feasible in a reasonable amount of time
> 
> So if we accept that caching constraints for the atom table reasonably
> bound it by main memory size, it seems to me that there is no reason to
> bother with reference counting. (Plus, that means that the atom table
> takes up one less word per atom.)

But you can't place any bound on the size of the atom table unless
there is some means of knowing when an atom can be deleted.

> All that said, this may simply be an argument against having a global atom
> table at all: the atom table constitutes an unprivileged DoS. Especially
> since I can't think of a sane way to charge quota for shared xattr names.

Without reference counting the atom table is a DoS, that is why
reference counting or something equivalent is not an option.  And it is
indeed an argument against atoms, not because of efficiency but because
of complexity.  So long as the complexity does not blow up then I think
atoms are a win.  Maybe a big win if you think about the compression
possibilities I mentioned earlier.

> Maybe the solution is to have the xattr atom table be per-directory or
> per-user? (A per-user atom table could then be integrated with the
> per-user quota information and also makes it crystal clear who gets
> charged for the atom table blocks. But then it might make sense to
> refcount or GC atoms again, so that users can reclaim their quota blocks.
> Hmm. Or maybe 1-bit refcounting: any name used more than once never goes
> away, unless we have some sort of GC?)

That is a good idea that had not occured to me.  I will regard it as a
fallback if reference counting does not work out.  But I think reference
counting will work out just fine, and it is the cleanest solution imho.

Regards,

Daniel

_______________________________________________
Tux3 mailing list
Tux3 at tux3.org
http://tux3.org/cgi-bin/mailman/listinfo/tux3