Re: radix tree implementation for quota ?

[Manuel Bouyer <bouyer%antioche.eu.org@localhost>]

On Mon, Nov 29, 2010 at 01:29:47AM +0700, Robert Elz wrote:
> [...]
> 
> If you're going to force the quota info to be in the filesystem itself,
> then you should probably consider splitting the two types of info that
> are stored there - there's the current usage info (etc) that can certainly
> be associated (very closely) with the filesystem, and there are the
> administrator set limits, which really shouldn't be.

one issue (which isn't really one) is that you'd then need to have
2 distinct block allocation for new uid. in things I didn't list in my
original mail was also the ability to set a default value for quotas, and
a way do define different behavior for uids without limit (to mean
either "no limits" or "a 0 limit" - the current behavior is annoying
in my context).

> 
> The problem is that we want to be able to have limits set for transient
> filesystems (tmpfs, or mfs, etc), they shouldn't just be lost when the
> filesystem evaporates.

sure.

> 
> When it was originally done, that was enough for me to allow the quota
> data to be anywhere (ie: not require it to live in the filesystem being
> monitored) - splitting it was just too much trouble.
> 
> bouyer%antioche.eu.org@localhost said:
>   | For a flat text file, lookup time is probably prohibitive (remeber we
>   | need to get acces to the quota information for every file create or 
> delete,
> 
> not really, it is all supposed to be cached,

there is a limit on the cache size, isn't it ?

> the file is touched only
> when a new user's file is first touched (ie, opened) or when the last
> ref to some user's file is made

how does it work with a NFS server ?

> (or a sync operation, but they're not
> frequent - most likely they never happen in practice, except as part
> of unmount.)

If this is integrated in the journal (which I want to do), they will
become much more frequent. 

> You want the accesses to be quite quick, but they don't
> have to be zero cost.
> 
> mellon%fugue.com@localhost said:
>   | No, wouldn't the kernel just deliver UIDs and usages?   Why would you want
>   | more than that in the kernel?
> 
> Well, first, and obviously, the kernel has to actually enforce the limits,
> so at the very least it needs to know the limits.   Having the file ops be
> in user space was the way the Sydney version of this stuff worked, and that
> had enough problems that it was what I deliberately set out to be different
> from, communicating between kernel and some user space daemon whenever a
> file for a new user is touched is just plain hard to get right.   The Sydney
> stuff didn't even try, they told the kernel the limits when a user logged in
> (as part of login, and I think, su) which meant that I/O to files belonging
> to users who were not logged in was totally untracked (and it is pretty easy
> to see how to use that to totally defeat the system ...)
> 
> bouyer%antioche.eu.org@localhost said:
>   | You're suggesting I should include Berkeley DB in the kernel, right ? 
> 
> When I saw your first message, I planned on suggesting just that.
> Well, not quite that, as the full blown db stuff isn't needed, just
> the hash access method, or a simplified version of it.   That's pretty
> much what we do now actually, with a trivial hash function (blockno =
> id * quote_block_size / disk block size) and then direct access to the
> quote info in the block - a more intelligent hash function, with a scan
> when the block is read to find the appropriate entry and dbm style block
> splitting on overflow ought to work reasonably well, and not be either
> large or costly.

I'll have to see how dbm works. I'm not sure it's better than a radix
tree though.

-- 
Manuel Bouyer <bouyer%antioche.eu.org@localhost>
     NetBSD: 26 ans d'experience feront toujours la difference
--