UBIFS seekdir()/telldir() issue
The problem
~~~~~~~~~~~
telldir() returns an opaque 32-bit value which should be enough to seek to the position later and continue readdir()-ing.
UBIFS stores direntries in a B-tree with 64-bit keys like:
| Parent Ino (32-bit) | key type (3 bits) | name hash (29 bits) |
The name hash may have collisions. Obviously, this does not quite fit to the telldir()/seekdir() model.
Note, this is very similar to reiserfs and reiser4 approach.
Current UBIFS implementation
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
At the moment UBIFS stores the hash value in file->f_pos, so telldir() basically returns direntry name hash values. And this does not quite work in case of hash collisions - seekdir() may not always seek correctly, which is rare though.
However, consecutive readdir() calls work fine because we store full name in file->private_data which helps to deal with collisions.
Naturally, readdir() returns direntries in hash order.
It seems there are not much applications which depend on telldir() and seekdir(), so this does not look too bad, at least in embedded world. But this means NFS will not really work because it needs "absolute" seekdir() implementation.
Possible approach
~~~~~~~~~~~~~~~~~
Short investigation showed that other file-systems have separate trees which are needed just for the sake of seekdir(). Well, it is sad that FSes have to do this just because of not very good interface, but such is live.
In UBIFS we are very reluctant to maintain any additional on-flash tree which would emulate traditional Unix "directory is an array of direntries" view. It is just too much overhead for embedded systems. And it would add more complexity to an already complex file-system.
Instead, we would like to do the following.
1. Assign a 32-bit unique id for each direntry. Each directory inode has its own space of the ids.
2. readdir() stores the id of the next direntry to return in file->f_pos, which means telldir() will return the unique ids, not hashes as it is currently done.
3. However, readdir() still walks direntries in hash, and it stores the key and full name of the next entry in file->private_data. This makes consecutive readdir() calls work correctly and efficiently.
4. When seeking, UBIFS havs to scan the main B-tree and look up direntry with the required ID. This is not efficient.
This approach gives full seekdir() support, except of one case described below.
Problems with this approach would be:
1. Slow seeks. But we think that actually rare applications do seekdir(), at least in embedded world. Comments?
2. If the direntry we are trying to seek to was _deleted_, we'll be unable to gracefully start from the closest next one. This is simply because readdir() returns entries in hash order, not in id order. The best UBIFS would be able to do in this case is to seek to the beginning of the directory.
IOW, sequence like this would be problematic:
dir = opendir();
pos = telldir(dir);
dent = readdri(dir);unlink(dent->d_name);
closedir(dir);
dir = opendir();
seekdir(pos); // Here we do not know where to seek
But we think this is also quite rare use-case and it should not hurt to seek to the beginning in these cases. Comments?
Thanks
Signature · 2 lines
Best Regards, Artem Bityutskiy (Артём Битюцкий)
Hi,
Quoted 14 lines
The problem
~~~~~~~~~~~
telldir()returns an opaque 32-bit value which should be enough to seek to the position later and continue readdir()-ing.UBIFS stores direntries in a B-tree with 64-bit keys like:
| Parent Ino (32-bit) | key type (3 bits) | name hash (29 bits) |The name hash may have collisions. Obviously, this does not quite fit to the telldir()/seekdir() model.
Note, this is very similar to reiserfs and reiser4 approach.
Quoted 7 lines
Current UBIFS implementation
~~~~~~~~~~~~~~~~~~~~~~~~~~~~At the moment UBIFS stores the hash value in
file->f_pos, sotelldir()basically returns direntry name hash values. And this does not quite work in case of hash collisions -seekdir()may not always seek correctly, which is rare though.
Yes, this is a classical problem of seekdir implementations :).
Quoted 62 lines
However, consecutive
readdir()calls work fine because we store full name infile->private_datawhich helps to deal with collisions.Naturally,
readdir()returns direntries in hash order.It seems there are not much applications which depend on
telldir()andseekdir(), so this does not look too bad, at least in embedded world. But this means NFS will not really work because it needs "absolute"seekdir()implementation.Possible approach
~~~~~~~~~~~~~~~~~Short investigation showed that other file-systems have separate trees which are needed just for the sake of
seekdir(). Well, it is sad that FSes have to do this just because of not very good interface, but such is live.In UBIFS we are very reluctant to maintain any additional on-flash tree which would emulate traditional Unix "directory is an array of direntries" view. It is just too much overhead for embedded systems. And it would add more complexity to an already complex file-system.
Instead, we would like to do the following.
1. Assign a 32-bit unique id for each direntry. Each directory inode has its own space of the ids.
2.readdir()stores the id of the next direntry to return infile->f_pos, which meanstelldir()will return the unique ids, not hashes as it is currently done.
3. However,readdir()still walks direntries in hash, and it stores the key and full name of the next entry infile->private_data. This makes consecutivereaddir()calls work correctly and efficiently.
4. When seeking, UBIFS havs to scan the main B-tree and look up direntry with the required ID. This is not efficient.This approach gives full
seekdir()support, except of one case described below.Problems with this approach would be:
1. Slow seeks. But we think that actually rare applications doseekdir(), at least in embedded world. Comments?2. If the direntry we are trying to seek to was _deleted_, we'll be unable to gracefully start from the closest next one. This is simply because
readdir()returns entries in hash order, not in id order. The best UBIFS would be able to do in this case is to seek to the beginning of the directory.IOW, sequence like this would be problematic:
dir =
opendir();
pos = telldir(dir);
dent = readdri(dir);unlink(dent->d_name);
closedir(dir);
dir =opendir();
seekdir(pos); // Here we do not know where to seek
Quoted 2 lines
But we think this is also quite rare use-case and it should not hurt to seek to the beginning in these cases. Comments?
The sequence you write above is actually incorrect I think. Noone
guarantees that the cookie returned by telldir() is valid after closedir(). What is a bigger (and quite common) problem is, if somebody uses readdir/telldir/seekdir while someone else creates/deletes files in the directory. The standard implies in this case that subsequent readdir should return all the files which were not touched (or all files after position set by seekdir if used...).
Honza
Signature · 2 lines
Jan Kara <[email protected]> SuSE CR Labs
Quoted 7 lines · Jan Kara
The sequence you write above is actually incorrect I think. Noone
guarantees that the cookie returned bytelldir()is valid afterclosedir(). What is a bigger (and quite common) problem is, if somebody uses readdir/telldir/seekdir while someone else creates/deletes files in the directory. The standard implies in this case that subsequent readdir should return all the files which were not touched (or all files after position set by seekdir if used...).
Not according to this:
http://www.opengroup.org/onlinepubs/009695399/functions/readdir.html
"If a file is removed from or added to the directory after the most recent call to opendir() or rewinddir(), whether a subsequent call to readdir() returns an entry for that file is unspecified."
Quoted 9 lines · Adrian Hunter
Quoted 7 lines · Jan Kara
The sequence you write above is actually incorrect I think. Noone
guarantees that the cookie returned bytelldir()is valid afterclosedir(). What is a bigger (and quite common) problem is, if somebody uses readdir/telldir/seekdir while someone else creates/deletes files in the directory. The standard implies in this case that subsequent readdir should return all the files which were not touched (or all files after position set by seekdir if used...).
Quoted 8 lines
Not according to this:
http://www.opengroup.org/onlinepubs/009695399/functions/readdir.html
"If a file is removed from or added to the directory after the most recent call to
opendir()orrewinddir(), whether a subsequent call toreaddir()returns an entry for that file is unspecified."
This is exactly what I meant. Maybe phrased it wrongly in my email :)
Honza
Signature · 2 lines
Jan Kara <[email protected]> SUSE Labs, CR