tech-kern archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

Re: radix tree implementation for quota ?

On Nov 28, 2010, at 9:27 AM, Manuel Bouyer wrote:

> On Sun, Nov 28, 2010 at 05:21:52PM +0000, Sad Clouds wrote:
>> On Sun, 28 Nov 2010 17:53:59 +0100
>> Manuel Bouyer <> wrote:
>>> One open question is how to store quota informations on disk.
>>> At this time we use one big array indexed by uid or gid. This can
>>> be very space-consuming if you have a very sparse uid/gid allocation,
>>> this is why I don't think this simple format is suitable any more
>>> (especially with 32bits uid/gid, and 64bit storage for various values).
>>> Linux uses a radix tree for this, and I coudln't come up with a better idea 
>>> :)
>> Wouldn't a hash table work?
> I think it's too dependant on uid distribution, or even how much uid you
> have. a tree scales and adapts better.

If you just read and write on mount/unmount/fsck, a linear text file 
would work that you convert into a rb-tree or p-tree on mount and then
read the tree and emit a text file on close.

This does assume you are going to cache the entire quota file while
the file system is mounted.

Home | Main Index | Thread Index | Old Index