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