fs/nilfs2/bmap.c

   1 /*
   2  * bmap.c - NILFS block mapping.
   3  *
   4  * Copyright (C) 2006-2008 Nippon Telegraph and Telephone Corporation.
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * Written by Koji Sato.
  17  */
  18
  19 #include <linux/fs.h>
  20 #include <linux/string.h>
  21 #include <linux/errno.h>
  22 #include "nilfs.h"
  23 #include "bmap.h"
  24 #include "btree.h"
  25 #include "direct.h"
  26 #include "btnode.h"
  27 #include "mdt.h"
  28 #include "dat.h"
  29 #include "alloc.h"
  30
  31 struct inode *nilfs_bmap_get_dat(const struct nilfs_bmap *bmap)
  32 {
  33         struct the_nilfs *nilfs = bmap->b_inode->i_sb->s_fs_info;
  34
  35         return nilfs->ns_dat;
  36 }
  37
  38 static int nilfs_bmap_convert_error(struct nilfs_bmap *bmap,
  39                                      const char *fname, int err)
  40 {
  41         struct inode *inode = bmap->b_inode;
  42
  43         if (err == -EINVAL) {
  44                 __nilfs_error(inode->i_sb, fname,
  45                               "broken bmap (inode number=%lu)", inode->i_ino);
  46                 err = -EIO;
  47         }
  48         return err;
  49 }
  50
  51 /**
  52  * nilfs_bmap_lookup_at_level - find a data block or node block
  53  * @bmap: bmap
  54  * @key: key
  55  * @level: level
  56  * @ptrp: place to store the value associated to @key
  57  *
  58  * Description: nilfs_bmap_lookup_at_level() finds a record whose key
  59  * matches @key in the block at @level of the bmap.
  60  *
  61  * Return Value: On success, 0 is returned and the record associated with @key
  62  * is stored in the place pointed by @ptrp. On error, one of the following
  63  * negative error codes is returned.
  64  *
  65  * %-EIO - I/O error.
  66  *
  67  * %-ENOMEM - Insufficient amount of memory available.
  68  *
  69  * %-ENOENT - A record associated with @key does not exist.
  70  */
  71 int nilfs_bmap_lookup_at_level(struct nilfs_bmap *bmap, __u64 key, int level,
  72                                __u64 *ptrp)
  73 {
  74         sector_t blocknr;
  75         int ret;
  76
  77         down_read(&bmap->b_sem);
  78         ret = bmap->b_ops->bop_lookup(bmap, key, level, ptrp);
  79         if (ret < 0)
  80                 goto out;
  81
  82         if (NILFS_BMAP_USE_VBN(bmap)) {
  83                 ret = nilfs_dat_translate(nilfs_bmap_get_dat(bmap), *ptrp,
  84                                           &blocknr);
  85                 if (!ret)
  86                         *ptrp = blocknr;
  87                 else if (ret == -ENOENT) {
  88                         /*
  89                          * If there was no valid entry in DAT for the block
  90                          * address obtained by b_ops->bop_lookup, then pass
  91                          * internal code -EINVAL to nilfs_bmap_convert_error
  92                          * to treat it as metadata corruption.
  93                          */
  94                         ret = -EINVAL;
  95                 }
  96         }
  97
  98  out:
  99         up_read(&bmap->b_sem);
 100         return nilfs_bmap_convert_error(bmap, __func__, ret);
 101 }
 102
 103 int nilfs_bmap_lookup_contig(struct nilfs_bmap *bmap, __u64 key, __u64 *ptrp,
 104                              unsigned int maxblocks)
 105 {
 106         int ret;
 107
 108         down_read(&bmap->b_sem);
 109         ret = bmap->b_ops->bop_lookup_contig(bmap, key, ptrp, maxblocks);
 110         up_read(&bmap->b_sem);
 111
 112         return nilfs_bmap_convert_error(bmap, __func__, ret);
 113 }
 114
 115 static int nilfs_bmap_do_insert(struct nilfs_bmap *bmap, __u64 key, __u64 ptr)
 116 {
 117         __u64 keys[NILFS_BMAP_SMALL_HIGH + 1];
 118         __u64 ptrs[NILFS_BMAP_SMALL_HIGH + 1];
 119         int ret, n;
 120
 121         if (bmap->b_ops->bop_check_insert != NULL) {
 122                 ret = bmap->b_ops->bop_check_insert(bmap, key);
 123                 if (ret > 0) {
 124                         n = bmap->b_ops->bop_gather_data(
 125                                 bmap, keys, ptrs, NILFS_BMAP_SMALL_HIGH + 1);
 126                         if (n < 0)
 127                                 return n;
 128                         ret = nilfs_btree_convert_and_insert(
 129                                 bmap, key, ptr, keys, ptrs, n);
 130                         if (ret == 0)
 131                                 bmap->b_u.u_flags |= NILFS_BMAP_LARGE;
 132
 133                         return ret;
 134                 } else if (ret < 0)
 135                         return ret;
 136         }
 137
 138         return bmap->b_ops->bop_insert(bmap, key, ptr);
 139 }
 140
 141 /**
 142  * nilfs_bmap_insert - insert a new key-record pair into a bmap
 143  * @bmap: bmap
 144  * @key: key
 145  * @rec: record
 146  *
 147  * Description: nilfs_bmap_insert() inserts the new key-record pair specified
 148  * by @key and @rec into @bmap.
 149  *
 150  * Return Value: On success, 0 is returned. On error, one of the following
 151  * negative error codes is returned.
 152  *
 153  * %-EIO - I/O error.
 154  *
 155  * %-ENOMEM - Insufficient amount of memory available.
 156  *
 157  * %-EEXIST - A record associated with @key already exist.
 158  */
 159 int nilfs_bmap_insert(struct nilfs_bmap *bmap, __u64 key, unsigned long rec)
 160 {
 161         int ret;
 162
 163         down_write(&bmap->b_sem);
 164         ret = nilfs_bmap_do_insert(bmap, key, rec);
 165         up_write(&bmap->b_sem);
 166
 167         return nilfs_bmap_convert_error(bmap, __func__, ret);
 168 }
 169
 170 static int nilfs_bmap_do_delete(struct nilfs_bmap *bmap, __u64 key)
 171 {
 172         __u64 keys[NILFS_BMAP_LARGE_LOW + 1];
 173         __u64 ptrs[NILFS_BMAP_LARGE_LOW + 1];
 174         int ret, n;
 175
 176         if (bmap->b_ops->bop_check_delete != NULL) {
 177                 ret = bmap->b_ops->bop_check_delete(bmap, key);
 178                 if (ret > 0) {
 179                         n = bmap->b_ops->bop_gather_data(
 180                                 bmap, keys, ptrs, NILFS_BMAP_LARGE_LOW + 1);
 181                         if (n < 0)
 182                                 return n;
 183                         ret = nilfs_direct_delete_and_convert(
 184                                 bmap, key, keys, ptrs, n);
 185                         if (ret == 0)
 186                                 bmap->b_u.u_flags &= ~NILFS_BMAP_LARGE;
 187
 188                         return ret;
 189                 } else if (ret < 0)
 190                         return ret;
 191         }
 192
 193         return bmap->b_ops->bop_delete(bmap, key);
 194 }
 195
 196 /**
 197  * nilfs_bmap_seek_key - seek a valid entry and return its key
 198  * @bmap: bmap struct
 199  * @start: start key number
 200  * @keyp: place to store valid key
 201  *
 202  * Description: nilfs_bmap_seek_key() seeks a valid key on @bmap
 203  * starting from @start, and stores it to @keyp if found.
 204  *
 205  * Return Value: On success, 0 is returned. On error, one of the following
 206  * negative error codes is returned.
 207  *
 208  * %-EIO - I/O error.
 209  *
 210  * %-ENOMEM - Insufficient amount of memory available.
 211  *
 212  * %-ENOENT - No valid entry was found
 213  */
 214 int nilfs_bmap_seek_key(struct nilfs_bmap *bmap, __u64 start, __u64 *keyp)
 215 {
 216         int ret;
 217
 218         down_read(&bmap->b_sem);
 219         ret = bmap->b_ops->bop_seek_key(bmap, start, keyp);
 220         up_read(&bmap->b_sem);
 221
 222         if (ret < 0)
 223                 ret = nilfs_bmap_convert_error(bmap, __func__, ret);
 224         return ret;
 225 }
 226
 227 int nilfs_bmap_last_key(struct nilfs_bmap *bmap, __u64 *keyp)
 228 {
 229         int ret;
 230
 231         down_read(&bmap->b_sem);
 232         ret = bmap->b_ops->bop_last_key(bmap, keyp);
 233         up_read(&bmap->b_sem);
 234
 235         if (ret < 0)
 236                 ret = nilfs_bmap_convert_error(bmap, __func__, ret);
 237         return ret;
 238 }
 239
 240 /**
 241  * nilfs_bmap_delete - delete a key-record pair from a bmap
 242  * @bmap: bmap
 243  * @key: key
 244  *
 245  * Description: nilfs_bmap_delete() deletes the key-record pair specified by
 246  * @key from @bmap.
 247  *
 248  * Return Value: On success, 0 is returned. On error, one of the following
 249  * negative error codes is returned.
 250  *
 251  * %-EIO - I/O error.
 252  *
 253  * %-ENOMEM - Insufficient amount of memory available.
 254  *
 255  * %-ENOENT - A record associated with @key does not exist.
 256  */
 257 int nilfs_bmap_delete(struct nilfs_bmap *bmap, __u64 key)
 258 {
 259         int ret;
 260
 261         down_write(&bmap->b_sem);
 262         ret = nilfs_bmap_do_delete(bmap, key);
 263         up_write(&bmap->b_sem);
 264
 265         return nilfs_bmap_convert_error(bmap, __func__, ret);
 266 }
 267
 268 static int nilfs_bmap_do_truncate(struct nilfs_bmap *bmap, __u64 key)
 269 {
 270         __u64 lastkey;
 271         int ret;
 272
 273         ret = bmap->b_ops->bop_last_key(bmap, &lastkey);
 274         if (ret < 0) {
 275                 if (ret == -ENOENT)
 276                         ret = 0;
 277                 return ret;
 278         }
 279
 280         while (key <= lastkey) {
 281                 ret = nilfs_bmap_do_delete(bmap, lastkey);
 282                 if (ret < 0)
 283                         return ret;
 284                 ret = bmap->b_ops->bop_last_key(bmap, &lastkey);
 285                 if (ret < 0) {
 286                         if (ret == -ENOENT)
 287                                 ret = 0;
 288                         return ret;
 289                 }
 290         }
 291         return 0;
 292 }
 293
 294 /**
 295  * nilfs_bmap_truncate - truncate a bmap to a specified key
 296  * @bmap: bmap
 297  * @key: key
 298  *
 299  * Description: nilfs_bmap_truncate() removes key-record pairs whose keys are
 300  * greater than or equal to @key from @bmap.
 301  *
 302  * Return Value: On success, 0 is returned. On error, one of the following
 303  * negative error codes is returned.
 304  *
 305  * %-EIO - I/O error.
 306  *
 307  * %-ENOMEM - Insufficient amount of memory available.
 308  */
 309 int nilfs_bmap_truncate(struct nilfs_bmap *bmap, __u64 key)
 310 {
 311         int ret;
 312
 313         down_write(&bmap->b_sem);
 314         ret = nilfs_bmap_do_truncate(bmap, key);
 315         up_write(&bmap->b_sem);
 316
 317         return nilfs_bmap_convert_error(bmap, __func__, ret);
 318 }
 319
 320 /**
 321  * nilfs_bmap_clear - free resources a bmap holds
 322  * @bmap: bmap
 323  *
 324  * Description: nilfs_bmap_clear() frees resources associated with @bmap.
 325  */
 326 void nilfs_bmap_clear(struct nilfs_bmap *bmap)
 327 {
 328         down_write(&bmap->b_sem);
 329         if (bmap->b_ops->bop_clear != NULL)
 330                 bmap->b_ops->bop_clear(bmap);
 331         up_write(&bmap->b_sem);
 332 }
 333
 334 /**
 335  * nilfs_bmap_propagate - propagate dirty state
 336  * @bmap: bmap
 337  * @bh: buffer head
 338  *
 339  * Description: nilfs_bmap_propagate() marks the buffers that directly or
 340  * indirectly refer to the block specified by @bh dirty.
 341  *
 342  * Return Value: On success, 0 is returned. On error, one of the following
 343  * negative error codes is returned.
 344  *
 345  * %-EIO - I/O error.
 346  *
 347  * %-ENOMEM - Insufficient amount of memory available.
 348  */
 349 int nilfs_bmap_propagate(struct nilfs_bmap *bmap, struct buffer_head *bh)
 350 {
 351         int ret;
 352
 353         down_write(&bmap->b_sem);
 354         ret = bmap->b_ops->bop_propagate(bmap, bh);
 355         up_write(&bmap->b_sem);
 356
 357         return nilfs_bmap_convert_error(bmap, __func__, ret);
 358 }
 359
 360 /**
 361  * nilfs_bmap_lookup_dirty_buffers -
 362  * @bmap: bmap
 363  * @listp: pointer to buffer head list
 364  */
 365 void nilfs_bmap_lookup_dirty_buffers(struct nilfs_bmap *bmap,
 366                                      struct list_head *listp)
 367 {
 368         if (bmap->b_ops->bop_lookup_dirty_buffers != NULL)
 369                 bmap->b_ops->bop_lookup_dirty_buffers(bmap, listp);
 370 }
 371
 372 /**
 373  * nilfs_bmap_assign - assign a new block number to a block
 374  * @bmap: bmap
 375  * @bhp: pointer to buffer head
 376  * @blocknr: block number
 377  * @binfo: block information
 378  *
 379  * Description: nilfs_bmap_assign() assigns the block number @blocknr to the
 380  * buffer specified by @bh.
 381  *
 382  * Return Value: On success, 0 is returned and the buffer head of a newly
 383  * create buffer and the block information associated with the buffer are
 384  * stored in the place pointed by @bh and @binfo, respectively. On error, one
 385  * of the following negative error codes is returned.
 386  *
 387  * %-EIO - I/O error.
 388  *
 389  * %-ENOMEM - Insufficient amount of memory available.
 390  */
 391 int nilfs_bmap_assign(struct nilfs_bmap *bmap,
 392                       struct buffer_head **bh,
 393                       unsigned long blocknr,
 394                       union nilfs_binfo *binfo)
 395 {
 396         int ret;
 397
 398         down_write(&bmap->b_sem);
 399         ret = bmap->b_ops->bop_assign(bmap, bh, blocknr, binfo);
 400         up_write(&bmap->b_sem);
 401
 402         return nilfs_bmap_convert_error(bmap, __func__, ret);
 403 }
 404
 405 /**
 406  * nilfs_bmap_mark - mark block dirty
 407  * @bmap: bmap
 408  * @key: key
 409  * @level: level
 410  *
 411  * Description: nilfs_bmap_mark() marks the block specified by @key and @level
 412  * as dirty.
 413  *
 414  * Return Value: On success, 0 is returned. On error, one of the following
 415  * negative error codes is returned.
 416  *
 417  * %-EIO - I/O error.
 418  *
 419  * %-ENOMEM - Insufficient amount of memory available.
 420  */
 421 int nilfs_bmap_mark(struct nilfs_bmap *bmap, __u64 key, int level)
 422 {
 423         int ret;
 424
 425         if (bmap->b_ops->bop_mark == NULL)
 426                 return 0;
 427
 428         down_write(&bmap->b_sem);
 429         ret = bmap->b_ops->bop_mark(bmap, key, level);
 430         up_write(&bmap->b_sem);
 431
 432         return nilfs_bmap_convert_error(bmap, __func__, ret);
 433 }
 434
 435 /**
 436  * nilfs_bmap_test_and_clear_dirty - test and clear a bmap dirty state
 437  * @bmap: bmap
 438  *
 439  * Description: nilfs_test_and_clear() is the atomic operation to test and
 440  * clear the dirty state of @bmap.
 441  *
 442  * Return Value: 1 is returned if @bmap is dirty, or 0 if clear.
 443  */
 444 int nilfs_bmap_test_and_clear_dirty(struct nilfs_bmap *bmap)
 445 {
 446         int ret;
 447
 448         down_write(&bmap->b_sem);
 449         ret = nilfs_bmap_dirty(bmap);
 450         nilfs_bmap_clear_dirty(bmap);
 451         up_write(&bmap->b_sem);
 452         return ret;
 453 }
 454
 455
 456 /*
 457  * Internal use only
 458  */
 459 __u64 nilfs_bmap_data_get_key(const struct nilfs_bmap *bmap,
 460                               const struct buffer_head *bh)
 461 {
 462         struct buffer_head *pbh;
 463         __u64 key;
 464
 465         key = page_index(bh->b_page) << (PAGE_SHIFT -
 466                                          bmap->b_inode->i_blkbits);
 467         for (pbh = page_buffers(bh->b_page); pbh != bh; pbh = pbh->b_this_page)
 468                 key++;
 469
 470         return key;
 471 }
 472
 473 __u64 nilfs_bmap_find_target_seq(const struct nilfs_bmap *bmap, __u64 key)
 474 {
 475         __s64 diff;
 476
 477         diff = key - bmap->b_last_allocated_key;
 478         if ((nilfs_bmap_keydiff_abs(diff) < NILFS_INODE_BMAP_SIZE) &&
 479             (bmap->b_last_allocated_ptr != NILFS_BMAP_INVALID_PTR) &&
 480             (bmap->b_last_allocated_ptr + diff > 0))
 481                 return bmap->b_last_allocated_ptr + diff;
 482         else
 483                 return NILFS_BMAP_INVALID_PTR;
 484 }
 485
 486 #define NILFS_BMAP_GROUP_DIV    8
 487 __u64 nilfs_bmap_find_target_in_group(const struct nilfs_bmap *bmap)
 488 {
 489         struct inode *dat = nilfs_bmap_get_dat(bmap);
 490         unsigned long entries_per_group = nilfs_palloc_entries_per_group(dat);
 491         unsigned long group = bmap->b_inode->i_ino / entries_per_group;
 492
 493         return group * entries_per_group +
 494                 (bmap->b_inode->i_ino % NILFS_BMAP_GROUP_DIV) *
 495                 (entries_per_group / NILFS_BMAP_GROUP_DIV);
 496 }
 497
 498 static struct lock_class_key nilfs_bmap_dat_lock_key;
 499 static struct lock_class_key nilfs_bmap_mdt_lock_key;
 500
 501 /**
 502  * nilfs_bmap_read - read a bmap from an inode
 503  * @bmap: bmap
 504  * @raw_inode: on-disk inode
 505  *
 506  * Description: nilfs_bmap_read() initializes the bmap @bmap.
 507  *
 508  * Return Value: On success, 0 is returned. On error, the following negative
 509  * error code is returned.
 510  *
 511  * %-ENOMEM - Insufficient amount of memory available.
 512  */
 513 int nilfs_bmap_read(struct nilfs_bmap *bmap, struct nilfs_inode *raw_inode)
 514 {
 515         if (raw_inode == NULL)
 516                 memset(bmap->b_u.u_data, 0, NILFS_BMAP_SIZE);
 517         else
 518                 memcpy(bmap->b_u.u_data, raw_inode->i_bmap, NILFS_BMAP_SIZE);
 519
 520         init_rwsem(&bmap->b_sem);
 521         bmap->b_state = 0;
 522         bmap->b_inode = &NILFS_BMAP_I(bmap)->vfs_inode;
 523         switch (bmap->b_inode->i_ino) {
 524         case NILFS_DAT_INO:
 525                 bmap->b_ptr_type = NILFS_BMAP_PTR_P;
 526                 bmap->b_last_allocated_key = 0;
 527                 bmap->b_last_allocated_ptr = NILFS_BMAP_NEW_PTR_INIT;
 528                 lockdep_set_class(&bmap->b_sem, &nilfs_bmap_dat_lock_key);
 529                 break;
 530         case NILFS_CPFILE_INO:
 531         case NILFS_SUFILE_INO:
 532                 bmap->b_ptr_type = NILFS_BMAP_PTR_VS;
 533                 bmap->b_last_allocated_key = 0;
 534                 bmap->b_last_allocated_ptr = NILFS_BMAP_INVALID_PTR;
 535                 lockdep_set_class(&bmap->b_sem, &nilfs_bmap_mdt_lock_key);
 536                 break;
 537         case NILFS_IFILE_INO:
 538                 lockdep_set_class(&bmap->b_sem, &nilfs_bmap_mdt_lock_key);
 539                 /* Fall through */
 540         default:
 541                 bmap->b_ptr_type = NILFS_BMAP_PTR_VM;
 542                 bmap->b_last_allocated_key = 0;
 543                 bmap->b_last_allocated_ptr = NILFS_BMAP_INVALID_PTR;
 544                 break;
 545         }
 546
 547         return (bmap->b_u.u_flags & NILFS_BMAP_LARGE) ?
 548                 nilfs_btree_init(bmap) : nilfs_direct_init(bmap);
 549 }
 550
 551 /**
 552  * nilfs_bmap_write - write back a bmap to an inode
 553  * @bmap: bmap
 554  * @raw_inode: on-disk inode
 555  *
 556  * Description: nilfs_bmap_write() stores @bmap in @raw_inode.
 557  */
 558 void nilfs_bmap_write(struct nilfs_bmap *bmap, struct nilfs_inode *raw_inode)
 559 {
 560         down_write(&bmap->b_sem);
 561         memcpy(raw_inode->i_bmap, bmap->b_u.u_data,
 562                NILFS_INODE_BMAP_SIZE * sizeof(__le64));
 563         if (bmap->b_inode->i_ino == NILFS_DAT_INO)
 564                 bmap->b_last_allocated_ptr = NILFS_BMAP_NEW_PTR_INIT;
 565
 566         up_write(&bmap->b_sem);
 567 }
 568
 569 void nilfs_bmap_init_gc(struct nilfs_bmap *bmap)
 570 {
 571         memset(&bmap->b_u, 0, NILFS_BMAP_SIZE);
 572         init_rwsem(&bmap->b_sem);
 573         bmap->b_inode = &NILFS_BMAP_I(bmap)->vfs_inode;
 574         bmap->b_ptr_type = NILFS_BMAP_PTR_U;
 575         bmap->b_last_allocated_key = 0;
 576         bmap->b_last_allocated_ptr = NILFS_BMAP_INVALID_PTR;
 577         bmap->b_state = 0;
 578         nilfs_btree_init_gc(bmap);
 579 }
 580
 581 void nilfs_bmap_save(const struct nilfs_bmap *bmap,
 582                      struct nilfs_bmap_store *store)
 583 {
 584         memcpy(store->data, bmap->b_u.u_data, sizeof(store->data));
 585         store->last_allocated_key = bmap->b_last_allocated_key;
 586         store->last_allocated_ptr = bmap->b_last_allocated_ptr;
 587         store->state = bmap->b_state;
 588 }
 589
 590 void nilfs_bmap_restore(struct nilfs_bmap *bmap,
 591                         const struct nilfs_bmap_store *store)
 592 {
 593         memcpy(bmap->b_u.u_data, store->data, sizeof(store->data));
 594         bmap->b_last_allocated_key = store->last_allocated_key;
 595         bmap->b_last_allocated_ptr = store->last_allocated_ptr;
 596         bmap->b_state = store->state;
 597 }