Dimitrie,
Speaking of which, both Samba and Wine suffer from the lack of support of cases-insensitivness in the kernel. Now, I'm not suggesting that we should push for that (I'm aware of the past discussions on LKML, and I must agree with Linus), but we should push for *something* that's acceptable and helps us solve the negative lookups a bit faster than a full directory listing every time.
I have a proposed solution for that which needs no kernel modifications. I have been meaning to write this up properly, so if you like I can do that for WineConf.
Here is the (probably inadequate) rough description:
The key is to look at the relative probability of different case combinations of names created using posix interfaces. Names created using Win32 style interfaces (via Wine or Samba) cover all different case combinations, but names created by unix users tend (to a very large degree) to use a much more restricted set of case combinations.
So, proposed solution is:
1) store the full case preserved name in a xattr
2) programs like Samba and Wine will lookup this xattr element and return that case preserved name in directory listings
3) keep a shared memory cache bitmap indexed by directory inode. It would consume memory of 4 bits per directory plus one microsecond timestamp per directory when full (note, it does not consume memory per-filename, only per directory). This keeps the memory usage low.
4) the 4 bits would indicate the "state" of that directory. Default state of a directory is 0, meaning unknown (that state is implied if an entry for that directory is not present in the shared cache)
5) other states would mean things like:
i) some filename in this directory may have a uppercase character in the leading position only. ii) some filename in this directory might have a uppercase character in any position iii) some filename in this directory may have a leading set of uppercase characters iv) all names in this directory are lowercase
6) when storing a name in the posix filesystem, we store the lowercase name, plus store the case preserved name in the xattr
7) when needing to look for a name in a directory, we check the shared bitmap. If it says "unknown" then we have to scan the directory as usual
8) when scanning the directory, we update the global bitmap if needed with anything we find. For example, if we only come across names that in the posix world are all lowercase then we set that state.
9) when we look for a name and the global cache indicates that (for example) there may be a file with 1 uppercase char in the leading position then we need to call stat() at most twice. As most filesystems these days use hash based directories, this stat() call costs us O(log N), which is a heck of a lot better than O(N) for a full scan.
10) cache coherence is done by the microsecond timestamp on the directory. This isn't perfect, but is the best we can do without kernel help. We might possibly be able to convince the kernel guys to give us a better coherence method (such as a in-memory revision count per directory).
The end result of this plan is this:
- for directories that are accessed only by Wine/Samba, and not by posix programs, we will operate very fast (ie. O(log N)) and completely accurately. We will be case insensitive and case preserving.
- for directories that are accessed only by posix systems, there is no overhead
- for mixed directories, Win32 names will appear lowercase to posix programs, but will be case preserving to Wine/Samba. Wine/Samba will be fast as long as posix programs don't create names like "MyFileNameIsReallyCool". It doesn't matter if Wine/Samba create names like that, only if posix does. Worst case is what we have now (full scan if we have silly posix users).
This all relies on the fact that posix programs tend to quite rarely create filenames with lots of upper/lowercase. You get some like "Mail", and "Desktop", but we can cope with those easily using bits as above. We just need to judge at what stage doing several stat() calls pays off versus just doing a scan. That will require some tuning (it might be useful to keep an estimate of the directory size in the cache to guide this heuristic).
Obviously there are many details I am glossing over (locking and permissions on the global cache for example). I am confident these can be solved quite easily.
Cheers, Tridge