2 * linux/fs/jbd2/revoke.c
4 * Written by Stephen C. Tweedie <sct@redhat.com>, 2000
6 * Copyright 2000 Red Hat corp --- All Rights Reserved
8 * This file is part of the Linux kernel and is made available under
9 * the terms of the GNU General Public License, version 2, or at your
10 * option, any later version, incorporated herein by reference.
12 * Journal revoke routines for the generic filesystem journaling code;
13 * part of the ext2fs journaling system.
15 * Revoke is the mechanism used to prevent old log records for deleted
16 * metadata from being replayed on top of newer data using the same
17 * blocks. The revoke mechanism is used in two separate places:
19 * + Commit: during commit we write the entire list of the current
20 * transaction's revoked blocks to the journal
22 * + Recovery: during recovery we record the transaction ID of all
23 * revoked blocks. If there are multiple revoke records in the log
24 * for a single block, only the last one counts, and if there is a log
25 * entry for a block beyond the last revoke, then that log entry still
28 * We can get interactions between revokes and new log data within a
31 * Block is revoked and then journaled:
32 * The desired end result is the journaling of the new block, so we
33 * cancel the revoke before the transaction commits.
35 * Block is journaled and then revoked:
36 * The revoke must take precedence over the write of the block, so we
37 * need either to cancel the journal entry or to write the revoke
38 * later in the log than the log block. In this case, we choose the
39 * latter: journaling a block cancels any revoke record for that block
40 * in the current transaction, so any revoke for that block in the
41 * transaction must have happened after the block was journaled and so
42 * the revoke must take precedence.
44 * Block is revoked and then written as data:
45 * The data write is allowed to succeed, but the revoke is _not_
46 * cancelled. We still need to prevent old log records from
47 * overwriting the new data. We don't even need to clear the revoke
50 * Revoke information on buffers is a tri-state value:
52 * RevokeValid clear: no cached revoke status, need to look it up
53 * RevokeValid set, Revoked clear:
54 * buffer has not been revoked, and cancel_revoke
56 * RevokeValid set, Revoked set:
57 * buffer has been revoked.
60 * We keep two hash tables of revoke records. One hashtable belongs to the
61 * running transaction (is pointed to by journal->j_revoke), the other one
62 * belongs to the committing transaction. Accesses to the second hash table
63 * happen only from the kjournald and no other thread touches this table. Also
64 * journal_switch_revoke_table() which switches which hashtable belongs to the
65 * running and which to the committing transaction is called only from
66 * kjournald. Therefore we need no locks when accessing the hashtable belonging
67 * to the committing transaction.
69 * All users operating on the hash table belonging to the running transaction
70 * have a handle to the transaction. Therefore they are safe from kjournald
71 * switching hash tables under them. For operations on the lists of entries in
72 * the hash table j_revoke_lock is used.
74 * Finally, also replay code uses the hash tables but at this moment noone else
75 * can touch them (filesystem isn't mounted yet) and hence no locking is
82 #include <linux/time.h>
84 #include <linux/jbd2.h>
85 #include <linux/errno.h>
86 #include <linux/slab.h>
87 #include <linux/list.h>
88 #include <linux/init.h>
90 #include <linux/log2.h>
92 static struct kmem_cache
*jbd2_revoke_record_cache
;
93 static struct kmem_cache
*jbd2_revoke_table_cache
;
95 /* Each revoke record represents one single revoked block. During
96 journal replay, this involves recording the transaction ID of the
97 last transaction to revoke this block. */
99 struct jbd2_revoke_record_s
101 struct list_head hash
;
102 tid_t sequence
; /* Used for recovery only */
103 unsigned long long blocknr
;
107 /* The revoke table is just a simple hash table of revoke records. */
108 struct jbd2_revoke_table_s
110 /* It is conceivable that we might want a larger hash table
111 * for recovery. Must be a power of two. */
114 struct list_head
*hash_table
;
119 static void write_one_revoke_record(journal_t
*, transaction_t
*,
120 struct journal_head
**, int *,
121 struct jbd2_revoke_record_s
*);
122 static void flush_descriptor(journal_t
*, struct journal_head
*, int);
125 /* Utility functions to maintain the revoke table */
127 /* Borrowed from buffer.c: this is a tried and tested block hash function */
128 static inline int hash(journal_t
*journal
, unsigned long long block
)
130 struct jbd2_revoke_table_s
*table
= journal
->j_revoke
;
131 int hash_shift
= table
->hash_shift
;
132 int hash
= (int)block
^ (int)((block
>> 31) >> 1);
134 return ((hash
<< (hash_shift
- 6)) ^
136 (hash
<< (hash_shift
- 12))) & (table
->hash_size
- 1);
139 static int insert_revoke_hash(journal_t
*journal
, unsigned long long blocknr
,
142 struct list_head
*hash_list
;
143 struct jbd2_revoke_record_s
*record
;
146 record
= kmem_cache_alloc(jbd2_revoke_record_cache
, GFP_NOFS
);
150 record
->sequence
= seq
;
151 record
->blocknr
= blocknr
;
152 hash_list
= &journal
->j_revoke
->hash_table
[hash(journal
, blocknr
)];
153 spin_lock(&journal
->j_revoke_lock
);
154 list_add(&record
->hash
, hash_list
);
155 spin_unlock(&journal
->j_revoke_lock
);
159 if (!journal_oom_retry
)
161 jbd_debug(1, "ENOMEM in %s, retrying\n", __func__
);
166 /* Find a revoke record in the journal's hash table. */
168 static struct jbd2_revoke_record_s
*find_revoke_record(journal_t
*journal
,
169 unsigned long long blocknr
)
171 struct list_head
*hash_list
;
172 struct jbd2_revoke_record_s
*record
;
174 hash_list
= &journal
->j_revoke
->hash_table
[hash(journal
, blocknr
)];
176 spin_lock(&journal
->j_revoke_lock
);
177 record
= (struct jbd2_revoke_record_s
*) hash_list
->next
;
178 while (&(record
->hash
) != hash_list
) {
179 if (record
->blocknr
== blocknr
) {
180 spin_unlock(&journal
->j_revoke_lock
);
183 record
= (struct jbd2_revoke_record_s
*) record
->hash
.next
;
185 spin_unlock(&journal
->j_revoke_lock
);
189 void jbd2_journal_destroy_revoke_caches(void)
191 if (jbd2_revoke_record_cache
) {
192 kmem_cache_destroy(jbd2_revoke_record_cache
);
193 jbd2_revoke_record_cache
= NULL
;
195 if (jbd2_revoke_table_cache
) {
196 kmem_cache_destroy(jbd2_revoke_table_cache
);
197 jbd2_revoke_table_cache
= NULL
;
201 int __init
jbd2_journal_init_revoke_caches(void)
203 J_ASSERT(!jbd2_revoke_record_cache
);
204 J_ASSERT(!jbd2_revoke_table_cache
);
206 jbd2_revoke_record_cache
= kmem_cache_create("jbd2_revoke_record",
207 sizeof(struct jbd2_revoke_record_s
),
209 SLAB_HWCACHE_ALIGN
|SLAB_TEMPORARY
,
211 if (!jbd2_revoke_record_cache
)
212 goto record_cache_failure
;
214 jbd2_revoke_table_cache
= kmem_cache_create("jbd2_revoke_table",
215 sizeof(struct jbd2_revoke_table_s
),
216 0, SLAB_TEMPORARY
, NULL
);
217 if (!jbd2_revoke_table_cache
)
218 goto table_cache_failure
;
221 jbd2_journal_destroy_revoke_caches();
222 record_cache_failure
:
226 static struct jbd2_revoke_table_s
*jbd2_journal_init_revoke_table(int hash_size
)
230 struct jbd2_revoke_table_s
*table
;
232 table
= kmem_cache_alloc(jbd2_revoke_table_cache
, GFP_KERNEL
);
236 while((tmp
>>= 1UL) != 0UL)
239 table
->hash_size
= hash_size
;
240 table
->hash_shift
= shift
;
242 kmalloc(hash_size
* sizeof(struct list_head
), GFP_KERNEL
);
243 if (!table
->hash_table
) {
244 kmem_cache_free(jbd2_revoke_table_cache
, table
);
249 for (tmp
= 0; tmp
< hash_size
; tmp
++)
250 INIT_LIST_HEAD(&table
->hash_table
[tmp
]);
256 static void jbd2_journal_destroy_revoke_table(struct jbd2_revoke_table_s
*table
)
259 struct list_head
*hash_list
;
261 for (i
= 0; i
< table
->hash_size
; i
++) {
262 hash_list
= &table
->hash_table
[i
];
263 J_ASSERT(list_empty(hash_list
));
266 kfree(table
->hash_table
);
267 kmem_cache_free(jbd2_revoke_table_cache
, table
);
270 /* Initialise the revoke table for a given journal to a given size. */
271 int jbd2_journal_init_revoke(journal_t
*journal
, int hash_size
)
273 J_ASSERT(journal
->j_revoke_table
[0] == NULL
);
274 J_ASSERT(is_power_of_2(hash_size
));
276 journal
->j_revoke_table
[0] = jbd2_journal_init_revoke_table(hash_size
);
277 if (!journal
->j_revoke_table
[0])
280 journal
->j_revoke_table
[1] = jbd2_journal_init_revoke_table(hash_size
);
281 if (!journal
->j_revoke_table
[1])
284 journal
->j_revoke
= journal
->j_revoke_table
[1];
286 spin_lock_init(&journal
->j_revoke_lock
);
291 jbd2_journal_destroy_revoke_table(journal
->j_revoke_table
[0]);
296 /* Destroy a journal's revoke table. The table must already be empty! */
297 void jbd2_journal_destroy_revoke(journal_t
*journal
)
299 journal
->j_revoke
= NULL
;
300 if (journal
->j_revoke_table
[0])
301 jbd2_journal_destroy_revoke_table(journal
->j_revoke_table
[0]);
302 if (journal
->j_revoke_table
[1])
303 jbd2_journal_destroy_revoke_table(journal
->j_revoke_table
[1]);
310 * jbd2_journal_revoke: revoke a given buffer_head from the journal. This
311 * prevents the block from being replayed during recovery if we take a
312 * crash after this current transaction commits. Any subsequent
313 * metadata writes of the buffer in this transaction cancel the
316 * Note that this call may block --- it is up to the caller to make
317 * sure that there are no further calls to journal_write_metadata
318 * before the revoke is complete. In ext3, this implies calling the
319 * revoke before clearing the block bitmap when we are deleting
322 * Revoke performs a jbd2_journal_forget on any buffer_head passed in as a
323 * parameter, but does _not_ forget the buffer_head if the bh was only
326 * bh_in may not be a journalled buffer - it may have come off
327 * the hash tables without an attached journal_head.
329 * If bh_in is non-zero, jbd2_journal_revoke() will decrement its b_count
333 int jbd2_journal_revoke(handle_t
*handle
, unsigned long long blocknr
,
334 struct buffer_head
*bh_in
)
336 struct buffer_head
*bh
= NULL
;
338 struct block_device
*bdev
;
343 BUFFER_TRACE(bh_in
, "enter");
345 journal
= handle
->h_transaction
->t_journal
;
346 if (!jbd2_journal_set_features(journal
, 0, 0, JBD2_FEATURE_INCOMPAT_REVOKE
)){
347 J_ASSERT (!"Cannot set revoke feature!");
351 bdev
= journal
->j_fs_dev
;
355 bh
= __find_get_block(bdev
, blocknr
, journal
->j_blocksize
);
357 BUFFER_TRACE(bh
, "found on hash");
359 #ifdef JBD2_EXPENSIVE_CHECKING
361 struct buffer_head
*bh2
;
363 /* If there is a different buffer_head lying around in
364 * memory anywhere... */
365 bh2
= __find_get_block(bdev
, blocknr
, journal
->j_blocksize
);
367 /* ... and it has RevokeValid status... */
368 if (bh2
!= bh
&& buffer_revokevalid(bh2
))
369 /* ...then it better be revoked too,
370 * since it's illegal to create a revoke
371 * record against a buffer_head which is
372 * not marked revoked --- that would
373 * risk missing a subsequent revoke
375 J_ASSERT_BH(bh2
, buffer_revoked(bh2
));
381 /* We really ought not ever to revoke twice in a row without
382 first having the revoke cancelled: it's illegal to free a
383 block twice without allocating it in between! */
385 if (!J_EXPECT_BH(bh
, !buffer_revoked(bh
),
386 "inconsistent data on disk")) {
391 set_buffer_revoked(bh
);
392 set_buffer_revokevalid(bh
);
394 BUFFER_TRACE(bh_in
, "call jbd2_journal_forget");
395 jbd2_journal_forget(handle
, bh_in
);
397 BUFFER_TRACE(bh
, "call brelse");
402 jbd_debug(2, "insert revoke for block %llu, bh_in=%p\n",blocknr
, bh_in
);
403 err
= insert_revoke_hash(journal
, blocknr
,
404 handle
->h_transaction
->t_tid
);
405 BUFFER_TRACE(bh_in
, "exit");
410 * Cancel an outstanding revoke. For use only internally by the
411 * journaling code (called from jbd2_journal_get_write_access).
413 * We trust buffer_revoked() on the buffer if the buffer is already
414 * being journaled: if there is no revoke pending on the buffer, then we
415 * don't do anything here.
417 * This would break if it were possible for a buffer to be revoked and
418 * discarded, and then reallocated within the same transaction. In such
419 * a case we would have lost the revoked bit, but when we arrived here
420 * the second time we would still have a pending revoke to cancel. So,
421 * do not trust the Revoked bit on buffers unless RevokeValid is also
424 int jbd2_journal_cancel_revoke(handle_t
*handle
, struct journal_head
*jh
)
426 struct jbd2_revoke_record_s
*record
;
427 journal_t
*journal
= handle
->h_transaction
->t_journal
;
429 int did_revoke
= 0; /* akpm: debug */
430 struct buffer_head
*bh
= jh2bh(jh
);
432 jbd_debug(4, "journal_head %p, cancelling revoke\n", jh
);
434 /* Is the existing Revoke bit valid? If so, we trust it, and
435 * only perform the full cancel if the revoke bit is set. If
436 * not, we can't trust the revoke bit, and we need to do the
437 * full search for a revoke record. */
438 if (test_set_buffer_revokevalid(bh
)) {
439 need_cancel
= test_clear_buffer_revoked(bh
);
442 clear_buffer_revoked(bh
);
446 record
= find_revoke_record(journal
, bh
->b_blocknr
);
448 jbd_debug(4, "cancelled existing revoke on "
449 "blocknr %llu\n", (unsigned long long)bh
->b_blocknr
);
450 spin_lock(&journal
->j_revoke_lock
);
451 list_del(&record
->hash
);
452 spin_unlock(&journal
->j_revoke_lock
);
453 kmem_cache_free(jbd2_revoke_record_cache
, record
);
458 #ifdef JBD2_EXPENSIVE_CHECKING
459 /* There better not be one left behind by now! */
460 record
= find_revoke_record(journal
, bh
->b_blocknr
);
461 J_ASSERT_JH(jh
, record
== NULL
);
464 /* Finally, have we just cleared revoke on an unhashed
465 * buffer_head? If so, we'd better make sure we clear the
466 * revoked status on any hashed alias too, otherwise the revoke
467 * state machine will get very upset later on. */
469 struct buffer_head
*bh2
;
470 bh2
= __find_get_block(bh
->b_bdev
, bh
->b_blocknr
, bh
->b_size
);
473 clear_buffer_revoked(bh2
);
480 /* journal_switch_revoke table select j_revoke for next transaction
481 * we do not want to suspend any processing until all revokes are
484 void jbd2_journal_switch_revoke_table(journal_t
*journal
)
488 if (journal
->j_revoke
== journal
->j_revoke_table
[0])
489 journal
->j_revoke
= journal
->j_revoke_table
[1];
491 journal
->j_revoke
= journal
->j_revoke_table
[0];
493 for (i
= 0; i
< journal
->j_revoke
->hash_size
; i
++)
494 INIT_LIST_HEAD(&journal
->j_revoke
->hash_table
[i
]);
498 * Write revoke records to the journal for all entries in the current
499 * revoke hash, deleting the entries as we go.
501 void jbd2_journal_write_revoke_records(journal_t
*journal
,
502 transaction_t
*transaction
)
504 struct journal_head
*descriptor
;
505 struct jbd2_revoke_record_s
*record
;
506 struct jbd2_revoke_table_s
*revoke
;
507 struct list_head
*hash_list
;
508 int i
, offset
, count
;
514 /* select revoke table for committing transaction */
515 revoke
= journal
->j_revoke
== journal
->j_revoke_table
[0] ?
516 journal
->j_revoke_table
[1] : journal
->j_revoke_table
[0];
518 for (i
= 0; i
< revoke
->hash_size
; i
++) {
519 hash_list
= &revoke
->hash_table
[i
];
521 while (!list_empty(hash_list
)) {
522 record
= (struct jbd2_revoke_record_s
*)
524 write_one_revoke_record(journal
, transaction
,
525 &descriptor
, &offset
,
528 list_del(&record
->hash
);
529 kmem_cache_free(jbd2_revoke_record_cache
, record
);
533 flush_descriptor(journal
, descriptor
, offset
);
534 jbd_debug(1, "Wrote %d revoke records\n", count
);
538 * Write out one revoke record. We need to create a new descriptor
539 * block if the old one is full or if we have not already created one.
542 static void write_one_revoke_record(journal_t
*journal
,
543 transaction_t
*transaction
,
544 struct journal_head
**descriptorp
,
546 struct jbd2_revoke_record_s
*record
)
548 struct journal_head
*descriptor
;
550 journal_header_t
*header
;
552 /* If we are already aborting, this all becomes a noop. We
553 still need to go round the loop in
554 jbd2_journal_write_revoke_records in order to free all of the
555 revoke records: only the IO to the journal is omitted. */
556 if (is_journal_aborted(journal
))
559 descriptor
= *descriptorp
;
562 /* Make sure we have a descriptor with space left for the record */
564 if (offset
== journal
->j_blocksize
) {
565 flush_descriptor(journal
, descriptor
, offset
);
571 descriptor
= jbd2_journal_get_descriptor_buffer(journal
);
574 header
= (journal_header_t
*) &jh2bh(descriptor
)->b_data
[0];
575 header
->h_magic
= cpu_to_be32(JBD2_MAGIC_NUMBER
);
576 header
->h_blocktype
= cpu_to_be32(JBD2_REVOKE_BLOCK
);
577 header
->h_sequence
= cpu_to_be32(transaction
->t_tid
);
579 /* Record it so that we can wait for IO completion later */
580 JBUFFER_TRACE(descriptor
, "file as BJ_LogCtl");
581 jbd2_journal_file_buffer(descriptor
, transaction
, BJ_LogCtl
);
583 offset
= sizeof(jbd2_journal_revoke_header_t
);
584 *descriptorp
= descriptor
;
587 if (JBD2_HAS_INCOMPAT_FEATURE(journal
, JBD2_FEATURE_INCOMPAT_64BIT
)) {
588 * ((__be64
*)(&jh2bh(descriptor
)->b_data
[offset
])) =
589 cpu_to_be64(record
->blocknr
);
593 * ((__be32
*)(&jh2bh(descriptor
)->b_data
[offset
])) =
594 cpu_to_be32(record
->blocknr
);
602 * Flush a revoke descriptor out to the journal. If we are aborting,
603 * this is a noop; otherwise we are generating a buffer which needs to
604 * be waited for during commit, so it has to go onto the appropriate
605 * journal buffer list.
608 static void flush_descriptor(journal_t
*journal
,
609 struct journal_head
*descriptor
,
612 jbd2_journal_revoke_header_t
*header
;
613 struct buffer_head
*bh
= jh2bh(descriptor
);
615 if (is_journal_aborted(journal
)) {
620 header
= (jbd2_journal_revoke_header_t
*) jh2bh(descriptor
)->b_data
;
621 header
->r_count
= cpu_to_be32(offset
);
622 set_buffer_jwrite(bh
);
623 BUFFER_TRACE(bh
, "write");
624 set_buffer_dirty(bh
);
625 ll_rw_block(SWRITE
, 1, &bh
);
630 * Revoke support for recovery.
632 * Recovery needs to be able to:
634 * record all revoke records, including the tid of the latest instance
635 * of each revoke in the journal
637 * check whether a given block in a given transaction should be replayed
638 * (ie. has not been revoked by a revoke record in that or a subsequent
641 * empty the revoke table after recovery.
645 * First, setting revoke records. We create a new revoke record for
646 * every block ever revoked in the log as we scan it for recovery, and
647 * we update the existing records if we find multiple revokes for a
651 int jbd2_journal_set_revoke(journal_t
*journal
,
652 unsigned long long blocknr
,
655 struct jbd2_revoke_record_s
*record
;
657 record
= find_revoke_record(journal
, blocknr
);
659 /* If we have multiple occurrences, only record the
660 * latest sequence number in the hashed record */
661 if (tid_gt(sequence
, record
->sequence
))
662 record
->sequence
= sequence
;
665 return insert_revoke_hash(journal
, blocknr
, sequence
);
669 * Test revoke records. For a given block referenced in the log, has
670 * that block been revoked? A revoke record with a given transaction
671 * sequence number revokes all blocks in that transaction and earlier
672 * ones, but later transactions still need replayed.
675 int jbd2_journal_test_revoke(journal_t
*journal
,
676 unsigned long long blocknr
,
679 struct jbd2_revoke_record_s
*record
;
681 record
= find_revoke_record(journal
, blocknr
);
684 if (tid_gt(sequence
, record
->sequence
))
690 * Finally, once recovery is over, we need to clear the revoke table so
691 * that it can be reused by the running filesystem.
694 void jbd2_journal_clear_revoke(journal_t
*journal
)
697 struct list_head
*hash_list
;
698 struct jbd2_revoke_record_s
*record
;
699 struct jbd2_revoke_table_s
*revoke
;
701 revoke
= journal
->j_revoke
;
703 for (i
= 0; i
< revoke
->hash_size
; i
++) {
704 hash_list
= &revoke
->hash_table
[i
];
705 while (!list_empty(hash_list
)) {
706 record
= (struct jbd2_revoke_record_s
*) hash_list
->next
;
707 list_del(&record
->hash
);
708 kmem_cache_free(jbd2_revoke_record_cache
, record
);