diff options
author | Kent Overstreet <koverstreet@google.com> | 2013-03-23 19:11:31 -0400 |
---|---|---|
committer | Kent Overstreet <koverstreet@google.com> | 2013-03-23 19:11:31 -0400 |
commit | cafe563591446cf80bfbc2fe3bc72a2e36cf1060 (patch) | |
tree | c8ae27b13dcdb0219634376ca5e667df32b1173a /drivers/md/bcache/journal.h | |
parent | ea6749c705d9e629ed03c7336cc929fc6014b834 (diff) |
bcache: A block layer cache
Does writethrough and writeback caching, handles unclean shutdown, and
has a bunch of other nifty features motivated by real world usage.
See the wiki at http://bcache.evilpiepirate.org for more.
Signed-off-by: Kent Overstreet <koverstreet@google.com>
Diffstat (limited to 'drivers/md/bcache/journal.h')
-rw-r--r-- | drivers/md/bcache/journal.h | 215 |
1 files changed, 215 insertions, 0 deletions
diff --git a/drivers/md/bcache/journal.h b/drivers/md/bcache/journal.h new file mode 100644 index 000000000000..3d7851274b04 --- /dev/null +++ b/drivers/md/bcache/journal.h | |||
@@ -0,0 +1,215 @@ | |||
1 | #ifndef _BCACHE_JOURNAL_H | ||
2 | #define _BCACHE_JOURNAL_H | ||
3 | |||
4 | /* | ||
5 | * THE JOURNAL: | ||
6 | * | ||
7 | * The journal is treated as a circular buffer of buckets - a journal entry | ||
8 | * never spans two buckets. This means (not implemented yet) we can resize the | ||
9 | * journal at runtime, and will be needed for bcache on raw flash support. | ||
10 | * | ||
11 | * Journal entries contain a list of keys, ordered by the time they were | ||
12 | * inserted; thus journal replay just has to reinsert the keys. | ||
13 | * | ||
14 | * We also keep some things in the journal header that are logically part of the | ||
15 | * superblock - all the things that are frequently updated. This is for future | ||
16 | * bcache on raw flash support; the superblock (which will become another | ||
17 | * journal) can't be moved or wear leveled, so it contains just enough | ||
18 | * information to find the main journal, and the superblock only has to be | ||
19 | * rewritten when we want to move/wear level the main journal. | ||
20 | * | ||
21 | * Currently, we don't journal BTREE_REPLACE operations - this will hopefully be | ||
22 | * fixed eventually. This isn't a bug - BTREE_REPLACE is used for insertions | ||
23 | * from cache misses, which don't have to be journaled, and for writeback and | ||
24 | * moving gc we work around it by flushing the btree to disk before updating the | ||
25 | * gc information. But it is a potential issue with incremental garbage | ||
26 | * collection, and it's fragile. | ||
27 | * | ||
28 | * OPEN JOURNAL ENTRIES: | ||
29 | * | ||
30 | * Each journal entry contains, in the header, the sequence number of the last | ||
31 | * journal entry still open - i.e. that has keys that haven't been flushed to | ||
32 | * disk in the btree. | ||
33 | * | ||
34 | * We track this by maintaining a refcount for every open journal entry, in a | ||
35 | * fifo; each entry in the fifo corresponds to a particular journal | ||
36 | * entry/sequence number. When the refcount at the tail of the fifo goes to | ||
37 | * zero, we pop it off - thus, the size of the fifo tells us the number of open | ||
38 | * journal entries | ||
39 | * | ||
40 | * We take a refcount on a journal entry when we add some keys to a journal | ||
41 | * entry that we're going to insert (held by struct btree_op), and then when we | ||
42 | * insert those keys into the btree the btree write we're setting up takes a | ||
43 | * copy of that refcount (held by struct btree_write). That refcount is dropped | ||
44 | * when the btree write completes. | ||
45 | * | ||
46 | * A struct btree_write can only hold a refcount on a single journal entry, but | ||
47 | * might contain keys for many journal entries - we handle this by making sure | ||
48 | * it always has a refcount on the _oldest_ journal entry of all the journal | ||
49 | * entries it has keys for. | ||
50 | * | ||
51 | * JOURNAL RECLAIM: | ||
52 | * | ||
53 | * As mentioned previously, our fifo of refcounts tells us the number of open | ||
54 | * journal entries; from that and the current journal sequence number we compute | ||
55 | * last_seq - the oldest journal entry we still need. We write last_seq in each | ||
56 | * journal entry, and we also have to keep track of where it exists on disk so | ||
57 | * we don't overwrite it when we loop around the journal. | ||
58 | * | ||
59 | * To do that we track, for each journal bucket, the sequence number of the | ||
60 | * newest journal entry it contains - if we don't need that journal entry we | ||
61 | * don't need anything in that bucket anymore. From that we track the last | ||
62 | * journal bucket we still need; all this is tracked in struct journal_device | ||
63 | * and updated by journal_reclaim(). | ||
64 | * | ||
65 | * JOURNAL FILLING UP: | ||
66 | * | ||
67 | * There are two ways the journal could fill up; either we could run out of | ||
68 | * space to write to, or we could have too many open journal entries and run out | ||
69 | * of room in the fifo of refcounts. Since those refcounts are decremented | ||
70 | * without any locking we can't safely resize that fifo, so we handle it the | ||
71 | * same way. | ||
72 | * | ||
73 | * If the journal fills up, we start flushing dirty btree nodes until we can | ||
74 | * allocate space for a journal write again - preferentially flushing btree | ||
75 | * nodes that are pinning the oldest journal entries first. | ||
76 | */ | ||
77 | |||
78 | #define BCACHE_JSET_VERSION_UUIDv1 1 | ||
79 | /* Always latest UUID format */ | ||
80 | #define BCACHE_JSET_VERSION_UUID 1 | ||
81 | #define BCACHE_JSET_VERSION 1 | ||
82 | |||
83 | /* | ||
84 | * On disk format for a journal entry: | ||
85 | * seq is monotonically increasing; every journal entry has its own unique | ||
86 | * sequence number. | ||
87 | * | ||
88 | * last_seq is the oldest journal entry that still has keys the btree hasn't | ||
89 | * flushed to disk yet. | ||
90 | * | ||
91 | * version is for on disk format changes. | ||
92 | */ | ||
93 | struct jset { | ||
94 | uint64_t csum; | ||
95 | uint64_t magic; | ||
96 | uint64_t seq; | ||
97 | uint32_t version; | ||
98 | uint32_t keys; | ||
99 | |||
100 | uint64_t last_seq; | ||
101 | |||
102 | BKEY_PADDED(uuid_bucket); | ||
103 | BKEY_PADDED(btree_root); | ||
104 | uint16_t btree_level; | ||
105 | uint16_t pad[3]; | ||
106 | |||
107 | uint64_t prio_bucket[MAX_CACHES_PER_SET]; | ||
108 | |||
109 | union { | ||
110 | struct bkey start[0]; | ||
111 | uint64_t d[0]; | ||
112 | }; | ||
113 | }; | ||
114 | |||
115 | /* | ||
116 | * Only used for holding the journal entries we read in btree_journal_read() | ||
117 | * during cache_registration | ||
118 | */ | ||
119 | struct journal_replay { | ||
120 | struct list_head list; | ||
121 | atomic_t *pin; | ||
122 | struct jset j; | ||
123 | }; | ||
124 | |||
125 | /* | ||
126 | * We put two of these in struct journal; we used them for writes to the | ||
127 | * journal that are being staged or in flight. | ||
128 | */ | ||
129 | struct journal_write { | ||
130 | struct jset *data; | ||
131 | #define JSET_BITS 3 | ||
132 | |||
133 | struct cache_set *c; | ||
134 | struct closure_waitlist wait; | ||
135 | bool need_write; | ||
136 | }; | ||
137 | |||
138 | /* Embedded in struct cache_set */ | ||
139 | struct journal { | ||
140 | spinlock_t lock; | ||
141 | /* used when waiting because the journal was full */ | ||
142 | struct closure_waitlist wait; | ||
143 | struct closure_with_timer io; | ||
144 | |||
145 | /* Number of blocks free in the bucket(s) we're currently writing to */ | ||
146 | unsigned blocks_free; | ||
147 | uint64_t seq; | ||
148 | DECLARE_FIFO(atomic_t, pin); | ||
149 | |||
150 | BKEY_PADDED(key); | ||
151 | |||
152 | struct journal_write w[2], *cur; | ||
153 | }; | ||
154 | |||
155 | /* | ||
156 | * Embedded in struct cache. First three fields refer to the array of journal | ||
157 | * buckets, in cache_sb. | ||
158 | */ | ||
159 | struct journal_device { | ||
160 | /* | ||
161 | * For each journal bucket, contains the max sequence number of the | ||
162 | * journal writes it contains - so we know when a bucket can be reused. | ||
163 | */ | ||
164 | uint64_t seq[SB_JOURNAL_BUCKETS]; | ||
165 | |||
166 | /* Journal bucket we're currently writing to */ | ||
167 | unsigned cur_idx; | ||
168 | |||
169 | /* Last journal bucket that still contains an open journal entry */ | ||
170 | unsigned last_idx; | ||
171 | |||
172 | /* Next journal bucket to be discarded */ | ||
173 | unsigned discard_idx; | ||
174 | |||
175 | #define DISCARD_READY 0 | ||
176 | #define DISCARD_IN_FLIGHT 1 | ||
177 | #define DISCARD_DONE 2 | ||
178 | /* 1 - discard in flight, -1 - discard completed */ | ||
179 | atomic_t discard_in_flight; | ||
180 | |||
181 | struct work_struct discard_work; | ||
182 | struct bio discard_bio; | ||
183 | struct bio_vec discard_bv; | ||
184 | |||
185 | /* Bio for journal reads/writes to this device */ | ||
186 | struct bio bio; | ||
187 | struct bio_vec bv[8]; | ||
188 | }; | ||
189 | |||
190 | #define journal_pin_cmp(c, l, r) \ | ||
191 | (fifo_idx(&(c)->journal.pin, (l)->journal) > \ | ||
192 | fifo_idx(&(c)->journal.pin, (r)->journal)) | ||
193 | |||
194 | #define JOURNAL_PIN 20000 | ||
195 | |||
196 | #define journal_full(j) \ | ||
197 | (!(j)->blocks_free || fifo_free(&(j)->pin) <= 1) | ||
198 | |||
199 | struct closure; | ||
200 | struct cache_set; | ||
201 | struct btree_op; | ||
202 | |||
203 | void bch_journal(struct closure *); | ||
204 | void bch_journal_next(struct journal *); | ||
205 | void bch_journal_mark(struct cache_set *, struct list_head *); | ||
206 | void bch_journal_meta(struct cache_set *, struct closure *); | ||
207 | int bch_journal_read(struct cache_set *, struct list_head *, | ||
208 | struct btree_op *); | ||
209 | int bch_journal_replay(struct cache_set *, struct list_head *, | ||
210 | struct btree_op *); | ||
211 | |||
212 | void bch_journal_free(struct cache_set *); | ||
213 | int bch_journal_alloc(struct cache_set *); | ||
214 | |||
215 | #endif /* _BCACHE_JOURNAL_H */ | ||