revoke.c revision 8cf93332d180e6929d73cd8c855c3a83d6a6648c
1/* 2 * linux/fs/revoke.c 3 * 4 * Written by Stephen C. Tweedie <sct@redhat.com>, 2000 5 * 6 * Copyright 2000 Red Hat corp --- All Rights Reserved 7 * 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. 11 * 12 * Journal revoke routines for the generic filesystem journaling code; 13 * part of the ext2fs journaling system. 14 * 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: 18 * 19 * + Commit: during commit we write the entire list of the current 20 * transaction's revoked blocks to the journal 21 * 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 26 * gets replayed. 27 * 28 * We can get interactions between revokes and new log data within a 29 * single transaction: 30 * 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. 34 * 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. 43 * 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 48 * bit here. 49 * 50 * Revoke information on buffers is a tri-state value: 51 * 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 55 * need do nothing. 56 * RevokeValid set, Revoked set: 57 * buffer has been revoked. 58 */ 59 60#ifndef __KERNEL__ 61#include "jfs_user.h" 62#else 63#include <linux/sched.h> 64#include <linux/fs.h> 65#include <linux/jbd.h> 66#include <linux/errno.h> 67#include <linux/slab.h> 68#include <linux/locks.h> 69#include <linux/list.h> 70#include <linux/smp_lock.h> 71#include <linux/init.h> 72#endif 73 74static kmem_cache_t *revoke_record_cache; 75static kmem_cache_t *revoke_table_cache; 76 77/* Each revoke record represents one single revoked block. During 78 journal replay, this involves recording the transaction ID of the 79 last transaction to revoke this block. */ 80 81struct jbd_revoke_record_s 82{ 83 struct list_head hash; 84 tid_t sequence; /* Used for recovery only */ 85 unsigned long blocknr; 86}; 87 88 89/* The revoke table is just a simple hash table of revoke records. */ 90struct jbd_revoke_table_s 91{ 92 /* It is conceivable that we might want a larger hash table 93 * for recovery. Must be a power of two. */ 94 int hash_size; 95 int hash_shift; 96 struct list_head *hash_table; 97}; 98 99 100#ifdef __KERNEL__ 101static void write_one_revoke_record(journal_t *, transaction_t *, 102 struct journal_head **, int *, 103 struct jbd_revoke_record_s *); 104static void flush_descriptor(journal_t *, struct journal_head *, int); 105#endif 106 107/* Utility functions to maintain the revoke table */ 108 109/* Borrowed from buffer.c: this is a tried and tested block hash function */ 110static inline int hash(journal_t *journal, unsigned long block) 111{ 112 struct jbd_revoke_table_s *table = journal->j_revoke; 113 int hash_shift = table->hash_shift; 114 115 return ((block << (hash_shift - 6)) ^ 116 (block >> 13) ^ 117 (block << (hash_shift - 12))) & (table->hash_size - 1); 118} 119 120int insert_revoke_hash(journal_t *journal, unsigned long blocknr, tid_t seq) 121{ 122 struct list_head *hash_list; 123 struct jbd_revoke_record_s *record; 124 125repeat: 126 record = kmem_cache_alloc(revoke_record_cache, GFP_NOFS); 127 if (!record) 128 goto oom; 129 130 record->sequence = seq; 131 record->blocknr = blocknr; 132 hash_list = &journal->j_revoke->hash_table[hash(journal, blocknr)]; 133 list_add(&record->hash, hash_list); 134 return 0; 135 136oom: 137#ifdef __KERNEL__ 138 if (!journal_oom_retry) 139 return -ENOMEM; 140 jbd_debug(1, "ENOMEM in " __FUNCTION__ ", retrying.\n"); 141 current->policy |= SCHED_YIELD; 142 schedule(); 143 goto repeat; 144#else 145 return -ENOMEM; 146#endif 147} 148 149/* Find a revoke record in the journal's hash table. */ 150 151static struct jbd_revoke_record_s *find_revoke_record(journal_t *journal, 152 unsigned long blocknr) 153{ 154 struct list_head *hash_list; 155 struct jbd_revoke_record_s *record; 156 157 hash_list = &journal->j_revoke->hash_table[hash(journal, blocknr)]; 158 159 record = (struct jbd_revoke_record_s *) hash_list->next; 160 while (&(record->hash) != hash_list) { 161 if (record->blocknr == blocknr) 162 return record; 163 record = (struct jbd_revoke_record_s *) record->hash.next; 164 } 165 return NULL; 166} 167 168int __init journal_init_revoke_caches(void) 169{ 170 revoke_record_cache = kmem_cache_create("revoke_record", 171 sizeof(struct jbd_revoke_record_s), 172 0, SLAB_HWCACHE_ALIGN, NULL, NULL); 173 if (revoke_record_cache == 0) 174 return -ENOMEM; 175 176 revoke_table_cache = kmem_cache_create("revoke_table", 177 sizeof(struct jbd_revoke_table_s), 178 0, 0, NULL, NULL); 179 if (revoke_table_cache == 0) { 180 kmem_cache_destroy(revoke_record_cache); 181 revoke_record_cache = NULL; 182 return -ENOMEM; 183 } 184 return 0; 185} 186 187void journal_destroy_revoke_caches(void) 188{ 189 kmem_cache_destroy(revoke_record_cache); 190 revoke_record_cache = 0; 191 kmem_cache_destroy(revoke_table_cache); 192 revoke_table_cache = 0; 193} 194 195/* Initialise the revoke table for a given journal to a given size. */ 196 197int journal_init_revoke(journal_t *journal, int hash_size) 198{ 199 int shift, tmp; 200 201 J_ASSERT (journal->j_revoke == NULL); 202 203 journal->j_revoke = kmem_cache_alloc(revoke_table_cache, GFP_KERNEL); 204 if (!journal->j_revoke) 205 return -ENOMEM; 206 207 /* Check that the hash_size is a power of two */ 208 J_ASSERT ((hash_size & (hash_size-1)) == 0); 209 210 journal->j_revoke->hash_size = hash_size; 211 212 shift = 0; 213 tmp = hash_size; 214 while((tmp >>= 1UL) != 0UL) 215 shift++; 216 journal->j_revoke->hash_shift = shift; 217 218 journal->j_revoke->hash_table = 219 kmalloc(hash_size * sizeof(struct list_head), GFP_KERNEL); 220 if (!journal->j_revoke->hash_table) { 221 kmem_cache_free(revoke_table_cache, journal->j_revoke); 222 journal->j_revoke = NULL; 223 return -ENOMEM; 224 } 225 226 for (tmp = 0; tmp < hash_size; tmp++) 227 INIT_LIST_HEAD(&journal->j_revoke->hash_table[tmp]); 228 229 return 0; 230} 231 232/* Destoy a journal's revoke table. The table must already be empty! */ 233 234void journal_destroy_revoke(journal_t *journal) 235{ 236 struct jbd_revoke_table_s *table; 237 struct list_head *hash_list; 238 int i; 239 240 table = journal->j_revoke; 241 if (!table) 242 return; 243 244 for (i=0; i<table->hash_size; i++) { 245 hash_list = &table->hash_table[i]; 246 J_ASSERT (list_empty(hash_list)); 247 } 248 249 kfree(table->hash_table); 250 kmem_cache_free(revoke_table_cache, table); 251 journal->j_revoke = NULL; 252} 253 254 255#ifdef __KERNEL__ 256 257/* 258 * journal_revoke: revoke a given buffer_head from the journal. This 259 * prevents the block from being replayed during recovery if we take a 260 * crash after this current transaction commits. Any subsequent 261 * metadata writes of the buffer in this transaction cancel the 262 * revoke. 263 * 264 * Note that this call may block --- it is up to the caller to make 265 * sure that there are no further calls to journal_write_metadata 266 * before the revoke is complete. In ext3, this implies calling the 267 * revoke before clearing the block bitmap when we are deleting 268 * metadata. 269 * 270 * Revoke performs a journal_forget on any buffer_head passed in as a 271 * parameter, but does _not_ forget the buffer_head if the bh was only 272 * found implicitly. 273 * 274 * bh_in may not be a journalled buffer - it may have come off 275 * the hash tables without an attached journal_head. 276 * 277 * If bh_in is non-zero, journal_revoke() will decrement its b_count 278 * by one. 279 */ 280 281int journal_revoke(handle_t *handle, unsigned long blocknr, 282 struct buffer_head *bh_in) 283{ 284 struct buffer_head *bh = NULL; 285 journal_t *journal; 286 kdev_t dev; 287 int err; 288 289 if (bh_in) 290 BUFFER_TRACE(bh_in, "enter"); 291 292 journal = handle->h_transaction->t_journal; 293 if (!journal_set_features(journal, 0, 0, JFS_FEATURE_INCOMPAT_REVOKE)){ 294 J_ASSERT (!"Cannot set revoke feature!"); 295 return -EINVAL; 296 } 297 298 dev = journal->j_fs_dev; 299 bh = bh_in; 300 301 if (!bh) { 302 bh = get_hash_table(dev, blocknr, journal->j_blocksize); 303 if (bh) 304 BUFFER_TRACE(bh, "found on hash"); 305 } 306#ifdef JBD_EXPENSIVE_CHECKING 307 else { 308 struct buffer_head *bh2; 309 310 /* If there is a different buffer_head lying around in 311 * memory anywhere... */ 312 bh2 = get_hash_table(dev, blocknr, journal->j_blocksize); 313 if (bh2) { 314 /* ... and it has RevokeValid status... */ 315 if ((bh2 != bh) && 316 test_bit(BH_RevokeValid, &bh2->b_state)) 317 /* ...then it better be revoked too, 318 * since it's illegal to create a revoke 319 * record against a buffer_head which is 320 * not marked revoked --- that would 321 * risk missing a subsequent revoke 322 * cancel. */ 323 J_ASSERT_BH(bh2, test_bit(BH_Revoked, & 324 bh2->b_state)); 325 __brelse(bh2); 326 } 327 } 328#endif 329 330 /* We really ought not ever to revoke twice in a row without 331 first having the revoke cancelled: it's illegal to free a 332 block twice without allocating it in between! */ 333 if (bh) { 334 J_ASSERT_BH(bh, !test_bit(BH_Revoked, &bh->b_state)); 335 set_bit(BH_Revoked, &bh->b_state); 336 set_bit(BH_RevokeValid, &bh->b_state); 337 if (bh_in) { 338 BUFFER_TRACE(bh_in, "call journal_forget"); 339 journal_forget(handle, bh_in); 340 } else { 341 BUFFER_TRACE(bh, "call brelse"); 342 __brelse(bh); 343 } 344 } 345 346 lock_journal(journal); 347 jbd_debug(2, "insert revoke for block %lu, bh_in=%p\n", blocknr, bh_in); 348 err = insert_revoke_hash(journal, blocknr, 349 handle->h_transaction->t_tid); 350 unlock_journal(journal); 351 BUFFER_TRACE(bh_in, "exit"); 352 return err; 353} 354 355/* 356 * Cancel an outstanding revoke. For use only internally by the 357 * journaling code (called from journal_get_write_access). 358 * 359 * We trust the BH_Revoked bit on the buffer if the buffer is already 360 * being journaled: if there is no revoke pending on the buffer, then we 361 * don't do anything here. 362 * 363 * This would break if it were possible for a buffer to be revoked and 364 * discarded, and then reallocated within the same transaction. In such 365 * a case we would have lost the revoked bit, but when we arrived here 366 * the second time we would still have a pending revoke to cancel. So, 367 * do not trust the Revoked bit on buffers unless RevokeValid is also 368 * set. 369 * 370 * The caller must have the journal locked. 371 */ 372int journal_cancel_revoke(handle_t *handle, struct journal_head *jh) 373{ 374 struct jbd_revoke_record_s *record; 375 journal_t *journal = handle->h_transaction->t_journal; 376 int need_cancel; 377 int did_revoke = 0; /* akpm: debug */ 378 struct buffer_head *bh = jh2bh(jh); 379 380 jbd_debug(4, "journal_head %p, cancelling revoke\n", jh); 381 382 /* Is the existing Revoke bit valid? If so, we trust it, and 383 * only perform the full cancel if the revoke bit is set. If 384 * not, we can't trust the revoke bit, and we need to do the 385 * full search for a revoke record. */ 386 if (test_and_set_bit(BH_RevokeValid, &bh->b_state)) 387 need_cancel = (test_and_clear_bit(BH_Revoked, &bh->b_state)); 388 else { 389 need_cancel = 1; 390 clear_bit(BH_Revoked, &bh->b_state); 391 } 392 393 if (need_cancel) { 394 record = find_revoke_record(journal, bh->b_blocknr); 395 if (record) { 396 jbd_debug(4, "cancelled existing revoke on " 397 "blocknr %lu\n", bh->b_blocknr); 398 list_del(&record->hash); 399 kmem_cache_free(revoke_record_cache, record); 400 did_revoke = 1; 401 } 402 } 403 404#ifdef JBD_EXPENSIVE_CHECKING 405 /* There better not be one left behind by now! */ 406 record = find_revoke_record(journal, bh->b_blocknr); 407 J_ASSERT_JH(jh, record == NULL); 408#endif 409 410 /* Finally, have we just cleared revoke on an unhashed 411 * buffer_head? If so, we'd better make sure we clear the 412 * revoked status on any hashed alias too, otherwise the revoke 413 * state machine will get very upset later on. */ 414 if (need_cancel && !bh->b_pprev) { 415 struct buffer_head *bh2; 416 bh2 = get_hash_table(bh->b_dev, bh->b_blocknr, bh->b_size); 417 if (bh2) { 418 clear_bit(BH_Revoked, &bh2->b_state); 419 __brelse(bh2); 420 } 421 } 422 423 return did_revoke; 424} 425 426 427/* 428 * Write revoke records to the journal for all entries in the current 429 * revoke hash, deleting the entries as we go. 430 * 431 * Called with the journal lock held. 432 */ 433 434void journal_write_revoke_records(journal_t *journal, 435 transaction_t *transaction) 436{ 437 struct journal_head *descriptor; 438 struct jbd_revoke_record_s *record; 439 struct jbd_revoke_table_s *revoke; 440 struct list_head *hash_list; 441 int i, offset, count; 442 443 descriptor = NULL; 444 offset = 0; 445 count = 0; 446 revoke = journal->j_revoke; 447 448 for (i = 0; i < revoke->hash_size; i++) { 449 hash_list = &revoke->hash_table[i]; 450 451 while (!list_empty(hash_list)) { 452 record = (struct jbd_revoke_record_s *) 453 hash_list->next; 454 write_one_revoke_record(journal, transaction, 455 &descriptor, &offset, 456 record); 457 count++; 458 list_del(&record->hash); 459 kmem_cache_free(revoke_record_cache, record); 460 } 461 } 462 if (descriptor) 463 flush_descriptor(journal, descriptor, offset); 464 jbd_debug(1, "Wrote %d revoke records\n", count); 465} 466 467/* 468 * Write out one revoke record. We need to create a new descriptor 469 * block if the old one is full or if we have not already created one. 470 */ 471 472static void write_one_revoke_record(journal_t *journal, 473 transaction_t *transaction, 474 struct journal_head **descriptorp, 475 int *offsetp, 476 struct jbd_revoke_record_s *record) 477{ 478 struct journal_head *descriptor; 479 int offset; 480 journal_header_t *header; 481 482 /* If we are already aborting, this all becomes a noop. We 483 still need to go round the loop in 484 journal_write_revoke_records in order to free all of the 485 revoke records: only the IO to the journal is omitted. */ 486 if (is_journal_aborted(journal)) 487 return; 488 489 descriptor = *descriptorp; 490 offset = *offsetp; 491 492 /* Make sure we have a descriptor with space left for the record */ 493 if (descriptor) { 494 if (offset == journal->j_blocksize) { 495 flush_descriptor(journal, descriptor, offset); 496 descriptor = NULL; 497 } 498 } 499 500 if (!descriptor) { 501 descriptor = journal_get_descriptor_buffer(journal); 502 if (!descriptor) 503 return; 504 header = (journal_header_t *) &jh2bh(descriptor)->b_data[0]; 505 header->h_magic = htonl(JFS_MAGIC_NUMBER); 506 header->h_blocktype = htonl(JFS_REVOKE_BLOCK); 507 header->h_sequence = htonl(transaction->t_tid); 508 509 /* Record it so that we can wait for IO completion later */ 510 JBUFFER_TRACE(descriptor, "file as BJ_LogCtl"); 511 journal_file_buffer(descriptor, transaction, BJ_LogCtl); 512 513 offset = sizeof(journal_revoke_header_t); 514 *descriptorp = descriptor; 515 } 516 517 * ((unsigned int *)(&jh2bh(descriptor)->b_data[offset])) = 518 htonl(record->blocknr); 519 offset += 4; 520 *offsetp = offset; 521} 522 523/* 524 * Flush a revoke descriptor out to the journal. If we are aborting, 525 * this is a noop; otherwise we are generating a buffer which needs to 526 * be waited for during commit, so it has to go onto the appropriate 527 * journal buffer list. 528 */ 529 530static void flush_descriptor(journal_t *journal, 531 struct journal_head *descriptor, 532 int offset) 533{ 534 journal_revoke_header_t *header; 535 536 if (is_journal_aborted(journal)) { 537 JBUFFER_TRACE(descriptor, "brelse"); 538 __brelse(jh2bh(descriptor)); 539 return; 540 } 541 542 header = (journal_revoke_header_t *) jh2bh(descriptor)->b_data; 543 header->r_count = htonl(offset); 544 set_bit(BH_JWrite, &jh2bh(descriptor)->b_state); 545 { 546 struct buffer_head *bh = jh2bh(descriptor); 547 BUFFER_TRACE(bh, "write"); 548 ll_rw_block (WRITE, 1, &bh); 549 } 550} 551 552#endif 553 554/* 555 * Revoke support for recovery. 556 * 557 * Recovery needs to be able to: 558 * 559 * record all revoke records, including the tid of the latest instance 560 * of each revoke in the journal 561 * 562 * check whether a given block in a given transaction should be replayed 563 * (ie. has not been revoked by a revoke record in that or a subsequent 564 * transaction) 565 * 566 * empty the revoke table after recovery. 567 */ 568 569/* 570 * First, setting revoke records. We create a new revoke record for 571 * every block ever revoked in the log as we scan it for recovery, and 572 * we update the existing records if we find multiple revokes for a 573 * single block. 574 */ 575 576int journal_set_revoke(journal_t *journal, 577 unsigned long blocknr, 578 tid_t sequence) 579{ 580 struct jbd_revoke_record_s *record; 581 582 record = find_revoke_record(journal, blocknr); 583 if (record) { 584 /* If we have multiple occurences, only record the 585 * latest sequence number in the hashed record */ 586 if (tid_gt(sequence, record->sequence)) 587 record->sequence = sequence; 588 return 0; 589 } 590 return insert_revoke_hash(journal, blocknr, sequence); 591} 592 593/* 594 * Test revoke records. For a given block referenced in the log, has 595 * that block been revoked? A revoke record with a given transaction 596 * sequence number revokes all blocks in that transaction and earlier 597 * ones, but later transactions still need replayed. 598 */ 599 600int journal_test_revoke(journal_t *journal, 601 unsigned long blocknr, 602 tid_t sequence) 603{ 604 struct jbd_revoke_record_s *record; 605 606 record = find_revoke_record(journal, blocknr); 607 if (!record) 608 return 0; 609 if (tid_gt(sequence, record->sequence)) 610 return 0; 611 return 1; 612} 613 614/* 615 * Finally, once recovery is over, we need to clear the revoke table so 616 * that it can be reused by the running filesystem. 617 */ 618 619void journal_clear_revoke(journal_t *journal) 620{ 621 int i; 622 struct list_head *hash_list; 623 struct jbd_revoke_record_s *record; 624 struct jbd_revoke_table_s *revoke; 625 626 revoke = journal->j_revoke; 627 628 for (i = 0; i < revoke->hash_size; i++) { 629 hash_list = &revoke->hash_table[i]; 630 while (!list_empty(hash_list)) { 631 record = (struct jbd_revoke_record_s*) hash_list->next; 632 list_del(&record->hash); 633 kmem_cache_free(revoke_record_cache, record); 634 } 635 } 636} 637 638