CCMS - Make the cache coherency locks MPSAFE.
[dragonfly.git] / sys / sys / ccms.h
1 /*
2  * Copyright (c) 2006 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  * $DragonFly: src/sys/sys/ccms.h,v 1.1 2006/08/23 06:45:40 dillon Exp $
35  */
36 /*
37  * CCMS - Cache Coherency Management System.  These structures are used
38  * to manage cache coherency and locking for an object.  Cache Coherency is
39  * managed at byte granularity with 64 bit offset ranges.
40  *
41  * Management is broken into two distinct pieces: (1) Local shared/exclusive
42  * locks which essentially replace traditional vnode locks and (2) local
43  * cache state which interacts with other hosts and follows a MESI-like model.
44  *
45  * The core to the entire module is the 'CST' (Cache State Tree) structure
46  * which stores both pieces of information in a red-black tree styled data
47  * structure.  CSTs are non-overlapping offset-ranged entities.  Other
48  * higher level structures govern how CSTs in the red-black tree or cut up
49  * or merged.
50  */
51
52 #ifndef _SYS_CCMS_H_
53 #define _SYS_CCMS_H_
54
55 #ifndef _SYS_TYPES_H_
56 #include <sys/types.h>
57 #endif
58 #ifndef _SYS_PARAM_H_
59 #include <sys/param.h>
60 #endif
61 #ifndef _SYS_SERIALIZE_H_
62 #include <sys/serialize.h>
63 #endif
64 #ifndef _SYS_SPINLOCK_H_
65 #include <sys/spinlock.h>
66 #endif
67 #ifndef _SYS_TREE_H_
68 #include <sys/tree.h>
69 #endif
70
71 #ifndef _SYS_SPINLOCK2_H_
72 #include <sys/spinlock2.h>
73 #endif
74
75 /*
76  * CCMS uses a red-black tree to sort CSTs.
77  */
78 RB_HEAD(ccms_rb_tree, ccms_cst);
79 RB_PROTOTYPE3(ccms_rb_tree, ccms_cst, rbnode, ccms_cst_cmp, off_t);
80
81 struct ccms_lock;
82 struct ccms_cst;
83
84 /*
85  * ccms_state_t - CCMS cache states
86  *
87  * CCMS uses an extended MESI caching model.  There are two extension
88  * states, MASTER and SLAVE, which represents dirty data which has not been 
89  * synchronized to backing store but which nevertheless is being shared
90  * between distinct caches.   These states are designed to allow data
91  * to be shared between nodes in a cluster without having to wait for it
92  * to be synchronized with its backing store.
93  *
94  * SLAVE     -  A shared state where the master copy of the data is being 
95  *              held by a foreign cache rather then by backing store.
96  *              This state implies that the backing store may contain stale
97  *              data.
98  *
99  * MASTER    -  A shared state where the master copy of the data is being
100  *              held locally.  Zero or more foreign caches may be holding
101  *              a copy of our data, so we cannot modify it without 
102  *              invalidating those caches.  This state implies that the
103  *              backing store may contain stale data.
104  *
105  *              MASTER differs from MODIFIED in that the data is read-only
106  *              due to the existance of foreign copies.  However, even though
107  *              the data is read-only, it is ALSO DIRTY because the backing
108  *              store has not been synchronized
109  *
110  * NOTE!  The cache state represents the worst case cache state for caching
111  * elements such as the buffer cache or VM page cache or the vnode attribute 
112  * cache (or other things) within the specified range.  It does NOT mean
113  * that the local machine actually has all of the requested data in-hand.
114  */
115 typedef enum ccms_state { 
116     CCMS_STATE_INVALID = 0,
117     CCMS_STATE_SHARED,          /* clean, read-only, from backing store */
118     CCMS_STATE_SLAVE,           /* clean, read-only, from master */
119     CCMS_STATE_MASTER,          /* dirty, read-only, shared master copy */
120     CCMS_STATE_EXCLUSIVE,       /* clean, read-only, exclusive */
121     CCMS_STATE_MODIFIED         /* clean or dirty, read-write, exclusive */
122 } ccms_state_t;
123
124 /*
125  * ccms_ltype_t - local access control lock state
126  *
127  * Note: A MODIFYING lock is an exclusive lock where the caller intends to
128  * make a modification, such as issuing a WRITE.  The difference between the
129  * two is in how the cache state is effected by the lock.   The distinction
130  * exists because there are many situations where the governing structure
131  * on the local machine needs to be locked exclusively, but the underlying
132  * data cache does not.
133  *
134  *      lock type       cache state
135  *      ---------       ---------
136  *      SHARED          >= shared
137  *      EXCLUSIVE       >= shared
138  *      MODIFYING       >= exclusive
139  */
140 typedef enum ccms_ltype {
141     CCMS_LTYPE_SHARED = 0,      /* shared lock on the range */
142     CCMS_LTYPE_EXCLUSIVE,       /* exclusive lock on the range */
143     CCMS_LTYPE_MODIFYING        /* modifying lock on the range */
144 } ccms_ltype_t;
145
146 /*
147  * The CCMS ABI information structure.  This structure contains ABI
148  * calls to resolve incompatible cache states.
149  */
150 struct ccms_info {
151     int (*ccms_set_cache)(struct ccms_info *, struct ccms_lock *, ccms_state_t);
152     void *data;
153     /* XXX */
154 };
155
156 /*
157  * A CCMS dataspace, typically stored in a vnode or VM object.   The primary
158  * reference is to the ccms_dataspace representing the local machine.  The
159  * chain field is used to link ccms_dataspace's representing other machines.
160  * These foreign representations typically only contain summary 'worst-case'
161  * CSTs.  The chain only needs to be followed if a CST has a cache state
162  * that is incompatible with the request.
163  */
164 struct ccms_dataspace {
165     struct ccms_rb_tree tree;
166     struct ccms_info    *info;
167     struct ccms_dataspace *chain;
168     ccms_state_t        defstate;
169     struct spinlock     spin;
170     struct ccms_cst     *delayed_free;  /* delayed frees */
171 };
172
173 /*
174  * The CCMS locking element - represents a high level locking request,
175  * such as used by read, write, and truncate operations.  These requests
176  * are not organized into any tree but instead are shadowed by items in
177  * the actual cache state tree (ccms_cst).  There are no direct links
178  * between a ccms_lock and the underlying CST items, only reference count
179  * fields in the CST item.
180  *
181  * When a CCMS lock is established the cache state of the underlying elements
182  * is adjusted to meet the requirements of the lock.  The cache state
183  * requirements are infered by the lock type:
184  *
185  * NOTE: Ranges may include negative offsets.  These are typically used to
186  * represent meta-data.
187  *
188  *                local lock            cache state
189  *                -----------------     --------------------
190  * SHARED       - SHARED                must not be invalid
191  * EXCLUSIVE    - EXCLUSIVE             must not be invalid
192  * MODIFYING    - EXCLUSIVE             must be EXCLUSIVE or MODIFIED
193  */
194 struct ccms_lock {
195         struct ccms_dataspace *ds;
196         off_t   beg_offset;
197         off_t   end_offset;
198         ccms_ltype_t ltype;
199 };
200
201 /*
202  * CCMS cache state tree element (CST) - represents the actual cache
203  * management state for a data space.  The cache state tree is a
204  * non-overlaping red-black tree containing ranged ccms_cst structures
205  * which reflect the resolved state for all current high level locking
206  * requests.  For example, two overlapping ccms_lock requests for shared
207  * access would typically be represented by three non-overlapping ccms_cst
208  * items in the CST.  The CST item representing the overlapped portion of
209  * the ccms_lock requests would have ref count of 2 while the other CST
210  * items would have a ref count of 1.
211  *
212  *      [lock request #01]
213  *               [lock request #02]
214  *      [--cst--][--cst--][--cst--]
215  *
216  * CSTs are partitioned so their edges line up to all current and pending
217  * ccms_lock requests.  CSTs are re-merged whenever possible.  A freshly
218  * initialized database typically has a single CST representing the default
219  * cache state for the host.
220  *
221  * A CST represents *TWO* different things.  First, it represents local
222  * locks held on data ranges.  Second, it represents the best-case cache
223  * state for data cached on the local machine for local<->remote host
224  * interactions.
225  *
226  * Any arbitrary data range within a dataspace can be locked shared or
227  * exclusive.  Obtaining a lock has the side effect of potentially modifying
228  * the cache state.  A positive sharecount in a CST indicates that a
229  * shared access lock is being held.  A negative sharecount indicates an
230  * exclusive access lock is being held on the range.  A MODIFYING lock
231  * type is just an exclusive lock but one which effects the cache state
232  * differently.
233  *
234  * The end offset is byte-inclusive, allowing the entire 64 bit data space
235  * to be represented without overflowing the edge case.  For example, a
236  * 64 byte area might be represented as (0,63).  The offsets are SIGNED
237  * entities.  Negative offsets are often used to represent meta-data
238  * such as ownership and permissions.  The file size is typically cached as a
239  * side effect of file operations occuring at the file EOF rather then
240  * combined with ownership and permissions.
241  */
242 struct ccms_cst {
243         RB_ENTRY(ccms_cst) rbnode;      /* stored in a red-black tree */
244         struct  ccms_cst *delayed_next; /* linked list to free */
245         off_t   beg_offset;
246         off_t   end_offset;
247         ccms_state_t state;             /* local cache state */
248         int     sharecount;             /* shared or exclusive lock count */
249         int     modifycount;            /* number of modifying exclusive lks */
250         int     blocked;                /* indicates a blocked lock request */
251         int     xrefs;                  /* lock overlap references */
252         int     lrefs;                  /* left edge refs */
253         int     rrefs;                  /* right edge refs */
254 };
255
256 typedef struct ccms_info *ccms_info_t;
257 typedef struct ccms_dataspace *ccms_dataspace_t;
258 typedef struct ccms_lock *ccms_lock_t;
259 typedef struct ccms_cst *ccms_cst_t;
260
261 /*
262  * Kernel API
263  */
264 #ifdef _KERNEL
265
266 static __inline
267 void
268 ccms_lock_init(ccms_lock_t lock, off_t beg_offset, off_t end_offset,
269                ccms_ltype_t ltype)
270 {
271     lock->beg_offset = beg_offset;
272     lock->end_offset = end_offset;
273     lock->ltype = ltype;
274 }
275
276 void ccms_dataspace_init(ccms_dataspace_t);
277 void ccms_dataspace_destroy(ccms_dataspace_t);
278 int ccms_lock_get(ccms_dataspace_t, ccms_lock_t);
279 int ccms_lock_get_uio(ccms_dataspace_t, ccms_lock_t, struct uio *);
280 int ccms_lock_put(ccms_dataspace_t, ccms_lock_t);
281
282 #endif
283
284 #endif
285