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