sys/vfs/hammer2/hammer2_ccms.h

   1 /*
   2  * Copyright (c) 2006,2012 The DragonFly Project.  All rights reserved.
   3  *
   4  * This code is derived from software contributed to The DragonFly Project
   5  * by Matthew Dillon <dillon@backplane.com>
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  * 3. Neither the name of The DragonFly Project nor the names of its
  18  *    contributors may be used to endorse or promote products derived
  19  *    from this software without specific, prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34 /*
  35  * CCMS - Cache Coherency Management System.  These structures are used
  36  * to manage cache coherency and locking for an object.  Cache Coherency is
  37  * managed at byte granularity with 64 bit offset ranges.
  38  *
  39  * Management is broken into two distinct pieces: (1) Local shared/exclusive
  40  * locks which essentially replace traditional vnode locks and (2) local
  41  * cache state which interacts with other hosts and follows a MESI-like model.
  42  *
  43  * The core to the entire module is the 'CST' (Cache State Tree) structure
  44  * which stores both pieces of information in a red-black tree styled data
  45  * structure.  CSTs are non-overlapping offset-ranged entities.  Other
  46  * higher level structures govern how CSTs in the red-black tree or cut up
  47  * or merged.
  48  */
  49
  50 #ifndef _SYS_CCMS_H_
  51 #define _SYS_CCMS_H_
  52
  53 #ifndef _SYS_TYPES_H_
  54 #include <sys/types.h>
  55 #endif
  56 #ifndef _SYS_PARAM_H_
  57 #include <sys/param.h>
  58 #endif
  59 #ifndef _SYS_SERIALIZE_H_
  60 #include <sys/serialize.h>
  61 #endif
  62 #ifndef _SYS_SPINLOCK_H_
  63 #include <sys/spinlock.h>
  64 #endif
  65 #ifndef _SYS_TREE_H_
  66 #include <sys/tree.h>
  67 #endif
  68
  69 /*
  70  * CCMS uses a red-black tree to sort CSTs.
  71  */
  72 RB_HEAD(ccms_rb_tree, ccms_cst);
  73 RB_PROTOTYPE3(ccms_rb_tree, ccms_cst, rbnode, ccms_cst_cmp, off_t);
  74
  75 struct ccms_lock;
  76 struct ccms_cst;
  77
  78 /*
  79  * ccms_state_t - CCMS cache states
  80  *
  81  * CCMS uses an extended MESI caching model.  There are two extension
  82  * states, MASTER and SLAVE, which represents dirty data which has not been
  83  * synchronized to backing store but which nevertheless is being shared
  84  * between distinct caches.   These states are designed to allow data
  85  * to be shared between nodes in a cluster without having to wait for it
  86  * to be synchronized with its backing store.
  87  *
  88  * SLAVE     -  A shared state where the master copy of the data is being
  89  *              held by a foreign cache rather then by backing store.
  90  *              This state implies that the backing store may contain stale
  91  *              data.
  92  *
  93  * MASTER    -  A shared state where the master copy of the data is being
  94  *              held locally.  Zero or more foreign caches may be holding
  95  *              a copy of our data, so we cannot modify it without
  96  *              invalidating those caches.  This state implies that the
  97  *              backing store may contain stale data.
  98  *
  99  *              MASTER differs from MODIFIED in that the data is read-only
 100  *              due to the existance of foreign copies.  However, even though
 101  *              the data is read-only, it is ALSO DIRTY because the backing
 102  *              store has not been synchronized
 103  *
 104  * NOTE!  The cache state represents the worst case cache state for caching
 105  * elements such as the buffer cache or VM page cache or the vnode attribute
 106  * cache (or other things) within the specified range.  It does NOT mean
 107  * that the local machine actually has all of the requested data in-hand.
 108  */
 109 typedef enum ccms_state {
 110     CCMS_STATE_INVALID = 0,
 111     CCMS_STATE_SHARED,          /* clean, read-only, from backing store */
 112     CCMS_STATE_SLAVE,           /* clean, read-only, from master */
 113     CCMS_STATE_MASTER,          /* dirty, read-only, shared master copy */
 114     CCMS_STATE_EXCLUSIVE,       /* clean, read-only, exclusive */
 115     CCMS_STATE_MODIFIED         /* clean or dirty, read-write, exclusive */
 116 } ccms_state_t;
 117
 118 /*
 119  * ccms_ltype_t - local access control lock state
 120  *
 121  * Note: A MODIFYING lock is an exclusive lock where the caller intends to
 122  * make a modification, such as issuing a WRITE.  The difference between the
 123  * two is in how the cache state is effected by the lock.   The distinction
 124  * exists because there are many situations where the governing structure
 125  * on the local machine needs to be locked exclusively, but the underlying
 126  * data cache does not.
 127  *
 128  *      lock type       cache state
 129  *      ---------       ---------
 130  *      SHARED          >= shared
 131  *      EXCLUSIVE       >= shared
 132  *      MODIFYING       >= exclusive
 133  */
 134 typedef enum ccms_ltype {
 135     CCMS_LTYPE_SHARED = 0,      /* shared lock on the range */
 136     CCMS_LTYPE_EXCLUSIVE,       /* exclusive lock on the range */
 137     CCMS_LTYPE_MODIFYING        /* modifying lock on the range */
 138 } ccms_ltype_t;
 139
 140 /*
 141  * The CCMS ABI information structure.  This structure contains ABI
 142  * calls to resolve incompatible cache states.
 143  */
 144 struct ccms_info {
 145     int (*ccms_set_cache)(struct ccms_info *, struct ccms_lock *, ccms_state_t);
 146     void *data;
 147     /* XXX */
 148 };
 149
 150 /*
 151  * A CCMS dataspace, typically stored in a vnode or VM object.   The primary
 152  * reference is to the ccms_dataspace representing the local machine.  The
 153  * chain field is used to link ccms_dataspace's representing other machines.
 154  * These foreign representations typically only contain summary 'worst-case'
 155  * CSTs.  The chain only needs to be followed if a CST has a cache state
 156  * that is incompatible with the request.
 157  */
 158 struct ccms_dataspace {
 159     struct ccms_rb_tree tree;
 160     struct ccms_info    *info;
 161     struct ccms_dataspace *chain;
 162     ccms_state_t        defstate;
 163     struct spinlock     spin;
 164     struct ccms_cst     *delayed_free;  /* delayed frees */
 165 };
 166
 167 /*
 168  * The CCMS locking element - represents a high level locking request,
 169  * such as used by read, write, and truncate operations.  These requests
 170  * are not organized into any tree but instead are shadowed by items in
 171  * the actual cache state tree (ccms_cst).  There are no direct links
 172  * between a ccms_lock and the underlying CST items, only reference count
 173  * fields in the CST item.
 174  *
 175  * When a CCMS lock is established the cache state of the underlying elements
 176  * is adjusted to meet the requirements of the lock.  The cache state
 177  * requirements are infered by the lock type:
 178  *
 179  * NOTE: Ranges may include negative offsets.  These are typically used to
 180  * represent meta-data.
 181  *
 182  *                local lock            cache state
 183  *                -----------------     --------------------
 184  * SHARED       - SHARED                must not be invalid
 185  * EXCLUSIVE    - EXCLUSIVE             must not be invalid
 186  * MODIFYING    - EXCLUSIVE             must be EXCLUSIVE or MODIFIED
 187  */
 188 struct ccms_lock {
 189         struct ccms_dataspace *ds;
 190         off_t   beg_offset;
 191         off_t   end_offset;
 192         ccms_ltype_t ltype;
 193 };
 194
 195 /*
 196  * CCMS cache state tree element (CST) - represents the actual cache
 197  * management state for a data space.  The cache state tree is a
 198  * non-overlaping red-black tree containing ranged ccms_cst structures
 199  * which reflect the resolved state for all current high level locking
 200  * requests.  For example, two overlapping ccms_lock requests for shared
 201  * access would typically be represented by three non-overlapping ccms_cst
 202  * items in the CST.  The CST item representing the overlapped portion of
 203  * the ccms_lock requests would have ref count of 2 while the other CST
 204  * items would have a ref count of 1.
 205  *
 206  *      [lock request #01]
 207  *               [lock request #02]
 208  *      [--cst--][--cst--][--cst--]
 209  *
 210  * CSTs are partitioned so their edges line up to all current and pending
 211  * ccms_lock requests.  CSTs are re-merged whenever possible.  A freshly
 212  * initialized database typically has a single CST representing the default
 213  * cache state for the host.
 214  *
 215  * A CST represents *TWO* different things.  First, it represents local
 216  * locks held on data ranges.  Second, it represents the best-case cache
 217  * state for data cached on the local machine for local<->remote host
 218  * interactions.
 219  *
 220  * Any arbitrary data range within a dataspace can be locked shared or
 221  * exclusive.  Obtaining a lock has the side effect of potentially modifying
 222  * the cache state.  A positive sharecount in a CST indicates that a
 223  * shared access lock is being held.  A negative sharecount indicates an
 224  * exclusive access lock is being held on the range.  A MODIFYING lock
 225  * type is just an exclusive lock but one which effects the cache state
 226  * differently.
 227  *
 228  * The end offset is byte-inclusive, allowing the entire 64 bit data space
 229  * to be represented without overflowing the edge case.  For example, a
 230  * 64 byte area might be represented as (0,63).  The offsets are SIGNED
 231  * entities.  Negative offsets are often used to represent meta-data
 232  * such as ownership and permissions.  The file size is typically cached as a
 233  * side effect of file operations occuring at the file EOF rather then
 234  * combined with ownership and permissions.
 235  */
 236 struct ccms_cst {
 237         RB_ENTRY(ccms_cst) rbnode;      /* stored in a red-black tree */
 238         struct  ccms_cst *delayed_next; /* linked list to free */
 239         off_t   beg_offset;
 240         off_t   end_offset;
 241         ccms_state_t state;             /* local cache state */
 242         int     sharecount;             /* shared or exclusive lock count */
 243         int     modifycount;            /* number of modifying exclusive lks */
 244         int     blocked;                /* indicates a blocked lock request */
 245         int     xrefs;                  /* lock overlap references */
 246         int     lrefs;                  /* left edge refs */
 247         int     rrefs;                  /* right edge refs */
 248 };
 249
 250 typedef struct ccms_info *ccms_info_t;
 251 typedef struct ccms_dataspace *ccms_dataspace_t;
 252 typedef struct ccms_lock *ccms_lock_t;
 253 typedef struct ccms_cst *ccms_cst_t;
 254
 255 /*
 256  * Kernel API
 257  */
 258 #ifdef _KERNEL
 259
 260 static __inline
 261 void
 262 ccms_lock_init(ccms_lock_t lock, off_t beg_offset, off_t end_offset,
 263                ccms_ltype_t ltype)
 264 {
 265     lock->beg_offset = beg_offset;
 266     lock->end_offset = end_offset;
 267     lock->ltype = ltype;
 268 }
 269
 270 void ccms_dataspace_init(ccms_dataspace_t);
 271 void ccms_dataspace_destroy(ccms_dataspace_t);
 272 int ccms_lock_get(ccms_dataspace_t, ccms_lock_t);
 273 int ccms_lock_get_uio(ccms_dataspace_t, ccms_lock_t, struct uio *);
 274 int ccms_lock_put(ccms_dataspace_t, ccms_lock_t);
 275
 276 #endif
 277
 278 #endif