2 * Copyright (c) 2006,2012 The DragonFly Project. All rights reserved.
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@backplane.com>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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
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.
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
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.
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.
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
54 #include <sys/types.h>
57 #include <sys/param.h>
59 #ifndef _SYS_SERIALIZE_H_
60 #include <sys/serialize.h>
62 #ifndef _SYS_SPINLOCK_H_
63 #include <sys/spinlock.h>
70 * CCMS uses a red-black tree to sort CSTs.
72 RB_HEAD(ccms_rb_tree, ccms_cst);
73 RB_PROTOTYPE3(ccms_rb_tree, ccms_cst, rbnode, ccms_cst_cmp, off_t);
79 * ccms_state_t - CCMS cache states
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.
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
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.
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
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.
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 */
119 * ccms_ltype_t - local access control lock state
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.
128 * lock type cache state
129 * --------- ---------
131 * EXCLUSIVE >= shared
132 * MODIFYING >= exclusive
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 */
141 * The CCMS ABI information structure. This structure contains ABI
142 * calls to resolve incompatible cache states.
145 int (*ccms_set_cache)(struct ccms_info *, struct ccms_lock *, ccms_state_t);
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.
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 */
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.
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:
179 * NOTE: Ranges may include negative offsets. These are typically used to
180 * represent meta-data.
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
189 struct ccms_dataspace *ds;
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.
208 * [--cst--][--cst--][--cst--]
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.
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
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
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.
237 RB_ENTRY(ccms_cst) rbnode; /* stored in a red-black tree */
238 struct ccms_cst *delayed_next; /* linked list to free */
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 */
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;
262 ccms_lock_init(ccms_lock_t lock, off_t beg_offset, off_t end_offset,
265 lock->beg_offset = beg_offset;
266 lock->end_offset = end_offset;
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);