windows-bplus-tree-20070823
authorJeffrey Altman <jaltman@secure-endpoints.com>
Fri, 24 Aug 2007 04:19:18 +0000 (04:19 +0000)
committerJeffrey Altman <jaltman@secure-endpoints.com>
Fri, 24 Aug 2007 04:19:18 +0000 (04:19 +0000)
commitc8bf408ced50cf9fba1595ec94368e4060223d89
tree987955d91170fee467e32b663003d4072a62e4cb
parente5ec3ad4fc7009fec4a0760738a6b23c250d5d83
windows-bplus-tree-20070823

Windows uses case-insensitive file name pattern matching
but AFS is a case sensitive file system.  The AFS3 directory
format is block based, uses network byte order and
includes a hash table for fast case sensitive lookups.
This causes several problems for the Windows AFS client.
(1) Traversing the directory blocks is cpu expensive
(2) A hash table miss does not indicate that the desired
    entry does not exist.
(3) Determining whether a non-ambiguous inexact match or
    the entry does not exist requires a linear traversal
    of the entire directory.
These issues often result in 100% CPU utilization.

These issues are addressed by building a modified B+ tree for
each directory and then using the B+ tree for searches.

Further improvements can be made by using the B+ tree leaf
nodes for directory enumeration.
14 files changed:
src/WINNT/afsd/NTMakefile
src/WINNT/afsd/afsd.h
src/WINNT/afsd/afsd_init.c
src/WINNT/afsd/afsd_service.c
src/WINNT/afsd/cm.h
src/WINNT/afsd/cm_btree.c
src/WINNT/afsd/cm_btree.h
src/WINNT/afsd/cm_dir.c
src/WINNT/afsd/cm_dir.h
src/WINNT/afsd/cm_scache.c
src/WINNT/afsd/cm_scache.h
src/WINNT/afsd/cm_utils.c
src/WINNT/afsd/cm_vnodeops.c
src/WINNT/afsd/lock.txt