[Sheepdog] [PATCH v3] add object cache for sheep

[Liu Yuan]

NOTE:
  You also need to following QEMU patch to issue flush requests and not all kernel will
issue flush reqeust properly with upstream QEMU. For e.g, Debian squeeze will not issuse
flush reqeust via qemu to sheepdog[Linux kernel has different implementation of flush req 
and we works with new one]. 

Ubuntu server and RHEL 6 works as expected.

TODOs:
1 add an option to disable cache
2 cache object reclaim

v2 -> v3:
 - refactored the object cache code, cache_object_fd is removed
 - fix oc->dirty_rb race
 - donot propagate error to guests for flush operation
 - implement vdi delete operation

v1 -> v2:
 - free entry when add_to_dirty_rb_and_list() fails.
 - use mutex instead of spin lock.


    Object cache caches data and vdi objects on the local node. It is at
higher level than backend store. This extra cache layer translate gateway
requests into local requests, largely reducing the network traffic and highly
improving the IO performance.
    
    Dirty objects will be flushed to cluster storage by 'sync' request from
guest OS.

    The initial version concentrate on the simplicity. Its design is straightforward
just add one layer in front of the backend store. So the gateway requests (from Guest)

old path: IO req -> cluster backend store
   |
   v
new path: IO req -> object cache -> cluster backend store

    Later we might consider other features, for e.g., cache quota for different VDIs.

Thanks,
Yuan

Liu Yuan (8):
      sheep: drive object cache to work
      sheep: add red black tree library
      sheep: object cache proper
      sheep: teach sheep to use object cache
      sheep: add flush_vdi operation
      sheep: let object cache better interact with recovery logic
      collie: flush the vdi before searching the object
      object cache: implement vdi delete operation

 collie/vdi.c             |   19 ++
 include/rbtree.h         |   80 +++++++
 include/sheepdog_proto.h |    1 +
 lib/Makefile.am          |    2 +-
 lib/rbtree.c             |  451 ++++++++++++++++++++++++++++++++++++++++
 sheep/Makefile.am        |    2 +-
 sheep/group.c            |   13 +-
 sheep/object_cache.c     |  510 ++++++++++++++++++++++++++++++++++++++++++++++
 sheep/ops.c              |    7 +
 sheep/sheep_priv.h       |   40 ++++
 sheep/store.c            |   69 ++++++-
 11 files changed, 1185 insertions(+), 9 deletions(-)