Hello.
So I've finished new kernel quota code and utilities. I know its maybe late
for 2.3/2.4, Linus, so if you aren't going to accept this stuff for 2.3 tell
me it please so I can at least port my fixes from 2.2 to 2.3 which are IMO
must for 2.4.
The new quota code (and new file format) does:
* allow large (32-bit) uids/gids
* root is no longer special user -- in old format user with uid 0 couldn't
have quota soft limit; CAP_SYS_RESOURCE is honoured instead of uid 0
* architecture independent quota file format (everything is stored
little-endian and time_t was replaced by u64)
* cleanup of quota code (some parts were really ancient and didn't have
sense in current kernels)
Things I wasn't sure about:
* In quotactl() is for operations like SETQUOTA etc. tested CAP_SYS_RESOUCE.
Isn't CAP_SYS_ADMIN better?
* Is it right to store time on disk just as time_t typed to u64? Is it
guaranteed that measure of CURRENT_TIME won't change from seconds to some
other measure?
Known problem (also present in kernel 2.2):
* Announcing about block soft limit overcomitting doesn't work due to ext2
preallocation - we don't announce exceeding when we preallocate blocks
which is right because a user doesn't really use the space. But we have
to update quota information (and eventually set time when soft limit
becomes hard one) as we don't know when block from preallocated becomes
allocated.
Solutions:
1) Threat preallocation as any other allocation and live with the result
that limit will be announced earlier...
2) Let it be. Nobody cares about announcing ;-).
3) Add call which announces using preallocated block.
And now how new format looks:
Quota files changed their names from quota.(user|group) to aquota.(user|
group). With this we'll prevent problems with old kernels touching our files
and hopefully also some problems between a monitor and a chair...
Each quota file from now on must begin with header
struct disk_dqheader {
__u32 dqh_magic; /* Magic number identifying file */
__u32 dqh_version; /* File version */
};
Any following data might be type (determined by magic) and version specific.
In current files (both user and group) follows
struct disk_dqinfo {
__u64 dqi_bgrace; /* Time before block soft limit becomes hard limit */
__u64 dqi_igrace; /* Time before inode soft limit becomes hard limit */
__u32 dqi_hashsize; /* Size of hash table in file */
__u32 dqi_flags; /* Flags for quotafile -- ie. root-squash */
__u32 dqi_blocks; /* Number of blocks in file */
__u32 dqi_empty; /* Almost empty block - with less than DQMERGELIM
entries */
};
and then from offset 1024 hashtable with dqi_hashsize entries. After hashtable
are blocks of entries with quota data. Each block is 1kb long. In the beginning
has
struct disk_dqhbheader {
__u32 dqhh_nextblk; /* Number of next block for this hash entry */
__u32 dqhh_prevblk; /* Number of previous block for this hash entry */
__u16 dqhh_entries; /* Number of valid entries in block */
__u16 dqhh_pad1;
};
then follow at most 23 entries of
struct disk_dqblk {
__u32 dqb_id; /* id this quota applies to */
__u32 dqb_bhardlimit; /* absolute limit on disk blks alloc */
__u32 dqb_bsoftlimit; /* preferred limit on disk blks */
__u32 dqb_curblocks; /* current block count */
__u32 dqb_ihardlimit; /* absolute limit on allocated inodes */
__u32 dqb_isoftlimit; /* preferred inode limit */
__u32 dqb_curinodes; /* current # allocated inodes */
__u64 dqb_btime; /* time limit for excessive disk use */
__u64 dqb_itime; /* time limit for excessive inode use */
};
And now how it all works:
In the hashtable there is for each hashvalue number of block which we should
search in for entries. More hashvalues can point to the same block (actually
when there are no entries, all hashvalues points to the same block). Blocks can
be linked in a list - when there are many entries with the same hashvalue (see
splitting block for explanation). The second and next blocks are bit special -
inevitably they aren't pointed from hashtable and we also threat them bit
differently when deleting entries (see below).
When we want to read entry from disk:
1) compute hashvalue
2) look at corresponding place in hashtable for block number
3) read the block
4) search the block for our entry
5) if not found read next block in chain (if actual block is last, entry
doesn't exist)
When we want to commit some entry to disk:
1) If entry contains only zeros delete it otherwise write it
When we want to write entry:
1) If entry was read before (not new), it has its offset saved in dquot
structure so we simply write it and return.
2) Entry is new so we have to find some place for it.
3) If block entry should go in by its hashvalue isn't full we simply add
it.
4) If it has successor (all entries have same hashvalue - see below) we
find last block in the list and put the entry to this block (or create
new block and link it to the end of the list).
5) As we want to avoid from hashchains we try to split the full block - we
choose some hashvalues and move corresponding entries to new empty
block. Then we of course rewrite references from hashtable.
If we were successful we can now add the entry to the block.
6) If we weren't successful (all entries had same hashvalue), we put entry
to new empty block and link it after the first block.
When we want to delete entry:
1) If entry hasn't set offset in dquot structure (it is new) we junk it as
it was never on the disk.
2) Delete the entry - move last entry from last block in the list over
deleted entry (if it wasn't last...)
3) If block is empty and it is not first in the list, delete it (move last
block in the file over it)
4) If block has less than 5 entries and is first (*) in the linked list
try to merge block with some other block.
* - we don't want to merge non-first blocks as if we had to create chain
this hashvalue is overloaded and we had better not to add any other
entries...
Merging blocks:
1) If there isn't any other almost empty block (its number would be in
info in dqi_empty) set dqi_empty
2) Othewise add entries from first block to the second one and delete the
first block (move last block in file over it).
3) Update hashtable properly
The nice thing about this structure is that we have read_dquot on 2 reads
(hashtable + block) in most cases and write_dquot on 1 write. The deletes and
inserts are in quota rare and so they aren't performace critical...
The bad thing is that it's a lot of code :(
There are a few questionable things:
1) Is all the merging stuff (~100 lines of code) reasonable? Deletes in
quotas are rare and so it might be feasible to just delete entry and
don't merge blocks. But the problem is that the structure might slowly
degrade to a very low number of entries in block => big file.
I dislike the idea of some userspace optimalizer as that would mean
turning quotas off => efectively shutdown a computer for a while if you
don't want to have inconsistent structures...
2) Is deleting of blocks (~80 lines of code) reasonable? Currently I move
last block over deleted block which requires update of hashtable,
update of eventual list pointers and so on - a lot of tiny annoying
things to do... The advantage is obvious - I can later truncate the
file and so reduce the size. If I just did linked list of empty blocks,
file would never shrink but it will probably reach some size and then
stop growing.
Suggestions, comments?
Everything can be donwloaded from ftp://atrey.karlin.mff.cuni.cz/pub/local/jack/
Kernel patch is quota-patch-2.3.13.diff.gz, utilities are quota-2.00.tar.gz.
A few words to the utils:
Utilities didn't differ much from the old ones. I tried to preserve interface
of the old utilites. The exceptions are edquota+setquota and quotacheck.
I extended the functionality of setquota so it can do now everything the
edquota could do and I removed edquota as I think that user interface of
edquota should be done some other way...
The change of quotacheck was must due to more complicated file format. Now it
accepts only one mountpoint (as fsck) and a few new options:
-f - force check even if quota enabled in kernel
-i - interactive mode
-n - automatically discard duplicated structures (in interactive mode)
-s user-hashsize,group-hashsize - hashsizes to be used when header corrupted
I removed quotaoff (it was symlink to quotaon..) as I don't like the idea of
programs changing their behaviour when ran with different name. Instead quotaon
has now option -f. If anybody wants old functionality he can do a shell alias or
a script...
I added utility convertquota with obvious functionality. It also allows creating
of new quota files (option -n).
Note that RPC things and EXT2_DIRECT things are untested cause I currenly don't
have necessary libraries at home.
Please test... Thanks
Honza.
