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