| |||||||||||||
Widening ext4's readdir() cookieWidening ext4's readdir() cookiePosted Mar 28, 2013 9:32 UTC (Thu) by paulj (subscriber, #341)In reply to: Widening ext4's readdir() cookie by dark Parent article: Widening ext4's readdir() cookie
Yes, names would be too big. Cpurse, you don't need an index into the space of all possible names. You need an index into the entries (not necessarily names) that existed and have existed in this directory. I wonder is there not a way to get a stable order, with a reliable "next" operation, out of that?
(Log in to post comments)
Widening ext4's readdir() cookie Posted Mar 28, 2013 9:57 UTC (Thu) by dlang (✭ supporter ✭, #313) [Link]
remember, the OS has no idea when (or even if) the application is going to make it's next request. The spec allows the application to read one filename a week and still be guaranteed to see all files that existed when it started the read with no duplicates.
If there were no resource constraints, the system could use RCU type strategies to make a copy of the directory and just use the token as a numeric offset into this copy, but since the system has no way of ever knowing when it could release this copy, it would have to keep it forever.
remember that with NFS, a server is required to be consistent even across reboots.
Widening ext4's readdir() cookie Posted Mar 28, 2013 10:24 UTC (Thu) by paulj (subscriber, #341) [Link]
E.g. why not make the order a ring? Store last created ID with the directory. Use an index into that order that is easily capable of answering "What is the next value in the order?" - tree indices typically are capable of this.
To create an entry:
- locate the ID in your ordered index (B-tree, whatever)
Insertions have to be done atomically wrt directory and index and any readers. Removals do not need to modify the last-created ID in the directory though. But it does not matter a jot how the internal structure of the index changes.
No collisions, no hashes, no encoding the structure of indices into cookies. No nasty hacks. Just work with the grain by making the underlying order you're indexing have the properties you want.
You are limited to # of directory entries being the size of the ring, but it seems NFS compatibility would allow that ring to be (2^64)-1.
Why wouldn't that work?
Widening ext4's readdir() cookie Posted Mar 28, 2013 11:31 UTC (Thu) by paulj (subscriber, #341) [Link]
Actually the ring isn't necessary. Any way to pick a free ID will do.
|
|||||||||||||