WineConf Agenda

[Andrew Tridgell]

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