e2fsck/revoke.c

   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
  37  *   we 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  *   former: the commit code must skip any block that has the Revoke bit
  40  *   set.
  41  *
  42  * Block is revoked and then written as data:
  43  *   The data write is allowed to succeed, but the revoke is _not_
  44  *   cancelled.  We still need to prevent old log records from
  45  *   overwriting the new data.  We don't even need to clear the revoke
  46  *   bit here.
  47  *
  48  * Revoke information on buffers is a tri-state value:
  49  *
  50  * RevokeValid clear:   no cached revoke status, need to look it up
  51  * RevokeValid set, Revoke clear:
  52  *                      buffer has not been revoked, and cancel_revoke
  53  *                      need do nothing.
  54  * RevokeValid set, Revoke set:
  55  *                      buffer has been revoked.
  56  */
  57
  58 #ifndef __KERNEL__
  59 #include "jfs_user.h"
  60 #else
  61 #include <linux/sched.h>
  62 #include <linux/fs.h>
  63 #include <linux/jfs.h>
  64 #include <linux/errno.h>
  65 #include <linux/slab.h>
  66 #include <linux/locks.h>
  67 #include <linux/buffer.h>
  68 #include <linux/list.h>
  69 #endif
  70
  71 static kmem_cache_t *revoke_record_cache;
  72 static kmem_cache_t *revoke_table_cache;
  73
  74 /* Each revoke record represents one single revoked block.  During
  75    journal replay, this involves recording the transaction ID of the
  76    last transaction to revoke this block. */
  77
  78 struct jfs_revoke_record_s
  79 {
  80         struct list_head  hash;
  81         tid_t             sequence;     /* Used for recovery only */
  82         unsigned long     blocknr;
  83 };
  84
  85
  86 /* The revoke table is just a simple hash table of revoke records. */
  87 struct jfs_revoke_table_s
  88 {
  89         /* It is conceivable that we might want a larger hash table
  90          * for recovery.  Must be a power of two. */
  91         int               hash_size;
  92         int               hash_shift;
  93         struct list_head *hash_table;
  94 };
  95
  96
  97 #ifdef __KERNEL__
  98 static void write_one_revoke_record(journal_t *, transaction_t *,
  99                                     struct buffer_head **, int *,
 100                                     struct jfs_revoke_record_s *);
 101 static void flush_descriptor(journal_t *, struct buffer_head *, int);
 102 #endif
 103
 104 /* Utility functions to maintain the revoke table */
 105
 106 /* Borrowed from buffer.c: this is a tried and tested block hash function */
 107 static inline int hash(journal_t *journal, unsigned long block)
 108 {
 109         struct jfs_revoke_table_s *table = journal->j_revoke;
 110         int hash_shift = table->hash_shift;
 111
 112         return ((block << (hash_shift - 6)) ^
 113                 (block >> 13) ^
 114                 (block << (hash_shift - 12))) & (table->hash_size - 1);
 115 }
 116
 117 int insert_revoke_hash(journal_t *journal, unsigned long blocknr, tid_t seq)
 118 {
 119         struct list_head *hash_list;
 120         struct jfs_revoke_record_s *record;
 121
 122         record = kmem_cache_alloc(revoke_record_cache, GFP_KERNEL);
 123         if (!record)
 124                 return -ENOMEM;
 125
 126         record->sequence = seq;
 127         record->blocknr = blocknr;
 128         hash_list = &journal->j_revoke->hash_table[hash(journal, blocknr)];
 129         list_add(&record->hash, hash_list);
 130         return 0;
 131 }
 132
 133 /* Find a revoke record in the journal's hash table. */
 134
 135 static struct jfs_revoke_record_s *find_revoke_record(journal_t *journal,
 136                                                       unsigned long blocknr)
 137 {
 138         struct list_head *hash_list;
 139         struct jfs_revoke_record_s *record;
 140
 141         hash_list = &journal->j_revoke->hash_table[hash(journal, blocknr)];
 142
 143         record = (struct jfs_revoke_record_s *) hash_list->next;
 144         while (&(record->hash) != hash_list) {
 145                 if (record->blocknr == blocknr)
 146                         return record;
 147                 record = (struct jfs_revoke_record_s *) record->hash.next;
 148         }
 149         return NULL;
 150 }
 151
 152
 153
 154 /* Initialise the revoke table for a given journal to a given size. */
 155
 156 int journal_init_revoke(journal_t *journal, int hash_size)
 157 {
 158         int shift, tmp;
 159
 160         J_ASSERT (journal->j_revoke == NULL);
 161
 162         if (!revoke_record_cache)
 163                 revoke_record_cache =
 164                         kmem_cache_create ("revoke_record",
 165                                            sizeof(struct jfs_revoke_record_s),
 166                                            0, SLAB_HWCACHE_ALIGN, NULL, NULL);
 167
 168         if (!revoke_table_cache)
 169                 revoke_table_cache =
 170                         kmem_cache_create ("revoke_table",
 171                                            sizeof(struct jfs_revoke_table_s),
 172                                            0, 0, NULL, NULL);
 173
 174         if (!revoke_record_cache || !revoke_table_cache)
 175                 return -ENOMEM;
 176
 177         journal->j_revoke = kmem_cache_alloc(revoke_table_cache, GFP_KERNEL);
 178         if (!journal->j_revoke)
 179                 return -ENOMEM;
 180
 181         /* Check that the hash_size is a power of two */
 182         J_ASSERT ((hash_size & (hash_size-1)) == 0);
 183
 184         journal->j_revoke->hash_size = hash_size;
 185
 186         shift = 0;
 187         tmp = hash_size;
 188         while((tmp >>= 1UL) != 0UL)
 189                 shift++;
 190         journal->j_revoke->hash_shift = shift;
 191
 192         journal->j_revoke->hash_table =
 193                 kmalloc(hash_size * sizeof(struct list_head), GFP_KERNEL);
 194         if (!journal->j_revoke->hash_table) {
 195                 kmem_cache_free(revoke_table_cache, journal->j_revoke);
 196                 journal->j_revoke = NULL;
 197                 return -ENOMEM;
 198         }
 199
 200         for (tmp = 0; tmp < hash_size; tmp++)
 201                 INIT_LIST_HEAD(&journal->j_revoke->hash_table[tmp]);
 202
 203         return 0;
 204 }
 205
 206 /* Destoy a journal's revoke table.  The table must already be empty! */
 207
 208 void journal_destroy_revoke(journal_t *journal)
 209 {
 210         struct jfs_revoke_table_s *table;
 211         struct list_head *hash_list;
 212         int i;
 213
 214         table = journal->j_revoke;
 215         if (!table)
 216                 return;
 217
 218         for (i=0; i<table->hash_size; i++) {
 219                 hash_list = &table->hash_table[i];
 220                 J_ASSERT (list_empty(hash_list));
 221         }
 222
 223         kfree(table->hash_table);
 224         kmem_cache_free(revoke_table_cache, table);
 225         journal->j_revoke = NULL;
 226 }
 227
 228
 229 #ifdef __KERNEL__
 230
 231 /*
 232  * journal_revoke: revoke a given buffer_head from the journal.  This
 233  * prevents the block from being replayed during recovery if we take a
 234  * crash after this current transaction commits.  Any subsequent
 235  * metadata writes of the buffer in this transaction cancel the
 236  * revoke.
 237  *
 238  * Note that this call may block --- it is up to the caller to make
 239  * sure that there are no further calls to journal_write_metadata
 240  * before the revoke is complete.  In ext3, this implies calling the
 241  * revoke before clearing the block bitmap when we are deleting
 242  * metadata.
 243  *
 244  * Revoke performs a journal_forget on any buffer_head passed in as a
 245  * parameter, but does _not_ forget the buffer_head if the bh was only
 246  * found implicitly.
 247  *
 248  * Revoke must observe the same synchronisation rules as bforget: it
 249  * must not discard the buffer once it has blocked.
 250  */
 251
 252 int journal_revoke(handle_t *handle, unsigned long blocknr,
 253                    struct buffer_head *bh_in)
 254 {
 255         struct buffer_head *bh;
 256         journal_t *journal;
 257         kdev_t dev;
 258         int err;
 259
 260         journal = handle->h_transaction->t_journal;
 261         if (!journal_set_features(journal, 0, 0, JFS_FEATURE_INCOMPAT_REVOKE))
 262                 return -EINVAL;
 263
 264         dev = journal->j_dev;
 265         bh = bh_in;
 266
 267         if (!bh)
 268                 bh = get_hash_table(dev, blocknr, journal->j_blocksize);
 269
 270         /* We really ought not ever to revoke twice in a row without
 271            first having the revoke cancelled: it's illegal to free a
 272            block twice without allocating it in between! */
 273         if (bh) {
 274                 J_ASSERT (!test_and_set_bit(BH_Revoked, &bh->b_state));
 275                 set_bit(BH_RevokeValid, &bh->b_state);
 276                 if (bh_in)
 277                         journal_forget(handle, bh_in);
 278                 else
 279                         brelse(bh);
 280         }
 281
 282         lock_journal(journal);
 283         err = insert_revoke_hash(journal, blocknr,
 284                                  handle->h_transaction->t_tid);
 285         unlock_journal(journal);
 286
 287         return err;
 288 }
 289
 290
 291 /*
 292  * Cancel an outstanding revoke.  For use only internally by the
 293  * journaling code (called from journal_get_write_access).
 294  *
 295  * We trust the BH_Revoked bit on the buffer if the buffer is already
 296  * being journaled: if there is no revoke pending on the buffer, then we
 297  * don't do anything here.
 298  *
 299  * This would break if it were possible for a buffer to be revoked and
 300  * discarded, and then reallocated within the same transaction.  In such
 301  * a case we would have lost the revoked bit, but when we arrived here
 302  * the second time we would still have a pending revoke to cancel.  So,
 303  * do not trust the Revoked bit on buffers unless RevokeValid is also
 304  * set.
 305  *
 306  * The caller must have the journal locked.
 307  * */
 308
 309 void journal_cancel_revoke(handle_t *handle, struct buffer_head *bh)
 310 {
 311         struct jfs_revoke_record_s *record;
 312         journal_t *journal = handle->h_transaction->t_journal;
 313         int need_cancel;
 314
 315         J_ASSERT (journal->j_locked);
 316
 317         /* Is the existing Revoke bit valid?  If so, we trust it, and
 318          * only perform the full cancel if the revoke bit is set.  If
 319          * not, we can't trust the revoke bit, and we need to do the
 320          * full search for a revoke record. */
 321         if (test_and_set_bit(BH_RevokeValid, &bh->b_state))
 322                 need_cancel = (test_and_clear_bit(BH_Revoked, &bh->b_state));
 323         else {
 324                 need_cancel = 1;
 325                 clear_bit(BH_Revoked, &bh->b_state);
 326         }
 327
 328         if (need_cancel) {
 329                 record = find_revoke_record(journal, bh->b_blocknr);
 330                 if (record) {
 331                         list_del(&record->hash);
 332                         kmem_cache_free(revoke_record_cache, record);
 333                 }
 334         }
 335 }
 336
 337
 338 /*
 339  * Write revoke records to the journal for all entries in the current
 340  * revoke hash, deleting the entries as we go.
 341  *
 342  * Called with the journal lock held.
 343  */
 344
 345 void journal_write_revoke_records(journal_t *journal,
 346                                   transaction_t *transaction)
 347 {
 348         struct buffer_head *descriptor;
 349         struct jfs_revoke_record_s *record;
 350         struct jfs_revoke_table_s *revoke;
 351         struct list_head *hash_list;
 352         int i, offset;
 353
 354         descriptor = NULL;
 355         offset = 0;
 356         revoke = journal->j_revoke;
 357
 358         for (i = 0; i < revoke->hash_size; i++) {
 359                 hash_list = &revoke->hash_table[i];
 360
 361                 while (!list_empty(hash_list)) {
 362                         record = (struct jfs_revoke_record_s *)
 363                                 hash_list->next;
 364                         write_one_revoke_record(journal, transaction,
 365                                                 &descriptor, &offset,
 366                                                 record);
 367                         list_del(&record->hash);
 368                         kmem_cache_free(revoke_record_cache, record);
 369                 }
 370         }
 371         if (descriptor)
 372                 flush_descriptor(journal, descriptor, offset);
 373 }
 374
 375 /*
 376  * Write out one revoke record.  We need to create a new descriptor
 377  * block if the old one is full or if we have not already created one.
 378  */
 379
 380 static void write_one_revoke_record(journal_t *journal,
 381                                     transaction_t *transaction,
 382                                     struct buffer_head **descriptorp,
 383                                     int *offsetp,
 384                                     struct jfs_revoke_record_s *record)
 385 {
 386         struct buffer_head *descriptor;
 387         int offset;
 388         journal_header_t *header;
 389
 390         /* If we are already aborting, this all becomes a noop.  We
 391            still need to go round the loop in
 392            journal_write_revoke_records in order to free all of the
 393            revoke records: only the IO to the journal is omitted. */
 394         if (is_journal_abort(journal))
 395                 return;
 396
 397         descriptor = *descriptorp;
 398         offset = *offsetp;
 399
 400         /* Make sure we have a descriptor with space left for the record */
 401         if (descriptor) {
 402                 if (offset == journal->j_blocksize) {
 403                         flush_descriptor(journal, descriptor, offset);
 404                         descriptor = NULL;
 405                 }
 406         }
 407
 408         if (!descriptor) {
 409                 descriptor = journal_get_descriptor_buffer(journal);
 410                 header = (journal_header_t *) &descriptor->b_data[0];
 411                 header->h_magic     = htonl(JFS_MAGIC_NUMBER);
 412                 header->h_blocktype = htonl(JFS_REVOKE_BLOCK);
 413                 header->h_sequence  = htonl(transaction->t_tid);
 414
 415                 /* Record it so that we can wait for IO completion later */
 416                 journal_file_buffer(descriptor, transaction, BJ_LogCtl);
 417
 418                 offset = sizeof(journal_revoke_header_t);
 419                 *descriptorp = descriptor;
 420         }
 421
 422         * ((unsigned int *)(&descriptor->b_data[offset])) =
 423                 htonl(record->blocknr);
 424         offset += 4;
 425         *offsetp = offset;
 426 }
 427
 428 /*
 429  * Flush a revoke descriptor out to the journal.  If we are aborting,
 430  * this is a noop; otherwise we are generating a buffer which needs to
 431  * be waited for during commit, so it has to go onto the appropriate
 432  * journal buffer list.
 433  */
 434
 435 static void flush_descriptor(journal_t *journal,
 436                              struct buffer_head *descriptor,
 437                              int offset)
 438 {
 439         journal_revoke_header_t *header;
 440
 441         if (is_journal_abort(journal)) {
 442                 brelse(descriptor);
 443                 return;
 444         }
 445
 446         header = (journal_revoke_header_t *) descriptor->b_data;
 447         header->r_count = htonl(offset);
 448         set_bit(BH_JWrite, &descriptor->b_state);
 449         ll_rw_block (WRITE, 1, &descriptor);
 450 }
 451
 452 #endif
 453
 454 /*
 455  * Revoke support for recovery.
 456  *
 457  * Recovery needs to be able to:
 458  *
 459  *  record all revoke records, including the tid of the latest instance
 460  *  of each revoke in the journal
 461  *
 462  *  check whether a given block in a given transaction should be replayed
 463  *  (ie. has not been revoked by a revoke record in that or a subsequent
 464  *  transaction)
 465  *
 466  *  empty the revoke table after recovery.
 467  */
 468
 469 /*
 470  * First, setting revoke records.  We create a new revoke record for
 471  * every block ever revoked in the log as we scan it for recovery, and
 472  * we update the existing records if we find multiple revokes for a
 473  * single block.
 474  */
 475
 476 int journal_set_revoke(journal_t *journal,
 477                        unsigned long blocknr,
 478                        tid_t sequence)
 479 {
 480         struct jfs_revoke_record_s *record;
 481
 482         record = find_revoke_record(journal, blocknr);
 483         if (record) {
 484                 /* If we have multiple occurences, only record the
 485                  * latest sequence number in the hashed record */
 486                 if (tid_ge(sequence, record->sequence))
 487                         record->sequence = sequence;
 488                 return 0;
 489         }
 490         return insert_revoke_hash(journal, blocknr, sequence);
 491 }
 492
 493 /*
 494  * Test revoke records.  For a given block referenced in the log, has
 495  * that block been revoked?  A revoke record with a given transaction
 496  * sequence number revokes all blocks in that transaction and earlier
 497  * ones, but later transactions still need replayed.
 498  */
 499
 500 int journal_test_revoke(journal_t *journal,
 501                         unsigned long blocknr,
 502                         tid_t sequence)
 503 {
 504         struct jfs_revoke_record_s *record;
 505
 506         record = find_revoke_record(journal, blocknr);
 507         if (!record)
 508                 return 0;
 509         if (tid_ge(sequence, record->sequence))
 510                 return 0;
 511         return 1;
 512 }
 513
 514 /*
 515  * Finally, once recovery is over, we need to clear the revoke table so
 516  * that it can be reused by the running filesystem.
 517  */
 518
 519 void journal_clear_revoke(journal_t *journal)
 520 {
 521         int i;
 522         struct list_head *hash_list;
 523         struct jfs_revoke_record_s *record;
 524         struct jfs_revoke_table_s *revoke;
 525
 526         revoke = journal->j_revoke;
 527
 528         for (i = 0; i < revoke->hash_size; i++) {
 529                 hash_list = &revoke->hash_table[i];
 530                 while (!list_empty(hash_list)) {
 531                         record = (struct jfs_revoke_record_s*) hash_list->next;
 532                         list_del(&record->hash);
 533                         kmem_cache_free(revoke_record_cache, record);
 534                 }
 535         }
 536 }
 537