580 lines · c
1// SPDX-License-Identifier: GPL-2.0+2/*3 * NILFS block mapping.4 *5 * Copyright (C) 2006-2008 Nippon Telegraph and Telephone Corporation.6 *7 * Written by Koji Sato.8 */9 10#include <linux/fs.h>11#include <linux/string.h>12#include <linux/errno.h>13#include "nilfs.h"14#include "bmap.h"15#include "btree.h"16#include "direct.h"17#include "btnode.h"18#include "mdt.h"19#include "dat.h"20#include "alloc.h"21 22struct inode *nilfs_bmap_get_dat(const struct nilfs_bmap *bmap)23{24 struct the_nilfs *nilfs = bmap->b_inode->i_sb->s_fs_info;25 26 return nilfs->ns_dat;27}28 29static int nilfs_bmap_convert_error(struct nilfs_bmap *bmap,30 const char *fname, int err)31{32 struct inode *inode = bmap->b_inode;33 34 if (err == -EINVAL) {35 __nilfs_error(inode->i_sb, fname,36 "broken bmap (inode number=%lu)", inode->i_ino);37 err = -EIO;38 }39 return err;40}41 42/**43 * nilfs_bmap_lookup_at_level - find a data block or node block44 * @bmap: bmap45 * @key: key46 * @level: level47 * @ptrp: place to store the value associated to @key48 *49 * Description: nilfs_bmap_lookup_at_level() finds a record whose key50 * matches @key in the block at @level of the bmap.51 *52 * Return Value: On success, 0 is returned and the record associated with @key53 * is stored in the place pointed by @ptrp. On error, one of the following54 * negative error codes is returned.55 *56 * %-EIO - I/O error.57 *58 * %-ENOMEM - Insufficient amount of memory available.59 *60 * %-ENOENT - A record associated with @key does not exist.61 */62int nilfs_bmap_lookup_at_level(struct nilfs_bmap *bmap, __u64 key, int level,63 __u64 *ptrp)64{65 sector_t blocknr;66 int ret;67 68 down_read(&bmap->b_sem);69 ret = bmap->b_ops->bop_lookup(bmap, key, level, ptrp);70 if (ret < 0)71 goto out;72 73 if (NILFS_BMAP_USE_VBN(bmap)) {74 ret = nilfs_dat_translate(nilfs_bmap_get_dat(bmap), *ptrp,75 &blocknr);76 if (!ret)77 *ptrp = blocknr;78 else if (ret == -ENOENT) {79 /*80 * If there was no valid entry in DAT for the block81 * address obtained by b_ops->bop_lookup, then pass82 * internal code -EINVAL to nilfs_bmap_convert_error83 * to treat it as metadata corruption.84 */85 ret = -EINVAL;86 }87 }88 89 out:90 up_read(&bmap->b_sem);91 return nilfs_bmap_convert_error(bmap, __func__, ret);92}93 94int nilfs_bmap_lookup_contig(struct nilfs_bmap *bmap, __u64 key, __u64 *ptrp,95 unsigned int maxblocks)96{97 int ret;98 99 down_read(&bmap->b_sem);100 ret = bmap->b_ops->bop_lookup_contig(bmap, key, ptrp, maxblocks);101 up_read(&bmap->b_sem);102 103 return nilfs_bmap_convert_error(bmap, __func__, ret);104}105 106static int nilfs_bmap_do_insert(struct nilfs_bmap *bmap, __u64 key, __u64 ptr)107{108 __u64 keys[NILFS_BMAP_SMALL_HIGH + 1];109 __u64 ptrs[NILFS_BMAP_SMALL_HIGH + 1];110 int ret, n;111 112 if (bmap->b_ops->bop_check_insert != NULL) {113 ret = bmap->b_ops->bop_check_insert(bmap, key);114 if (ret > 0) {115 n = bmap->b_ops->bop_gather_data(116 bmap, keys, ptrs, NILFS_BMAP_SMALL_HIGH + 1);117 if (n < 0)118 return n;119 ret = nilfs_btree_convert_and_insert(120 bmap, key, ptr, keys, ptrs, n);121 if (ret == 0)122 bmap->b_u.u_flags |= NILFS_BMAP_LARGE;123 124 return ret;125 } else if (ret < 0)126 return ret;127 }128 129 return bmap->b_ops->bop_insert(bmap, key, ptr);130}131 132/**133 * nilfs_bmap_insert - insert a new key-record pair into a bmap134 * @bmap: bmap135 * @key: key136 * @rec: record137 *138 * Description: nilfs_bmap_insert() inserts the new key-record pair specified139 * by @key and @rec into @bmap.140 *141 * Return Value: On success, 0 is returned. On error, one of the following142 * negative error codes is returned.143 *144 * %-EIO - I/O error.145 *146 * %-ENOMEM - Insufficient amount of memory available.147 *148 * %-EEXIST - A record associated with @key already exist.149 */150int nilfs_bmap_insert(struct nilfs_bmap *bmap, __u64 key, unsigned long rec)151{152 int ret;153 154 down_write(&bmap->b_sem);155 ret = nilfs_bmap_do_insert(bmap, key, rec);156 up_write(&bmap->b_sem);157 158 return nilfs_bmap_convert_error(bmap, __func__, ret);159}160 161static int nilfs_bmap_do_delete(struct nilfs_bmap *bmap, __u64 key)162{163 __u64 keys[NILFS_BMAP_LARGE_LOW + 1];164 __u64 ptrs[NILFS_BMAP_LARGE_LOW + 1];165 int ret, n;166 167 if (bmap->b_ops->bop_check_delete != NULL) {168 ret = bmap->b_ops->bop_check_delete(bmap, key);169 if (ret > 0) {170 n = bmap->b_ops->bop_gather_data(171 bmap, keys, ptrs, NILFS_BMAP_LARGE_LOW + 1);172 if (n < 0)173 return n;174 ret = nilfs_direct_delete_and_convert(175 bmap, key, keys, ptrs, n);176 if (ret == 0)177 bmap->b_u.u_flags &= ~NILFS_BMAP_LARGE;178 179 return ret;180 } else if (ret < 0)181 return ret;182 }183 184 return bmap->b_ops->bop_delete(bmap, key);185}186 187/**188 * nilfs_bmap_seek_key - seek a valid entry and return its key189 * @bmap: bmap struct190 * @start: start key number191 * @keyp: place to store valid key192 *193 * Description: nilfs_bmap_seek_key() seeks a valid key on @bmap194 * starting from @start, and stores it to @keyp if found.195 *196 * Return Value: On success, 0 is returned. On error, one of the following197 * negative error codes is returned.198 *199 * %-EIO - I/O error.200 *201 * %-ENOMEM - Insufficient amount of memory available.202 *203 * %-ENOENT - No valid entry was found204 */205int nilfs_bmap_seek_key(struct nilfs_bmap *bmap, __u64 start, __u64 *keyp)206{207 int ret;208 209 down_read(&bmap->b_sem);210 ret = bmap->b_ops->bop_seek_key(bmap, start, keyp);211 up_read(&bmap->b_sem);212 213 if (ret < 0)214 ret = nilfs_bmap_convert_error(bmap, __func__, ret);215 return ret;216}217 218int nilfs_bmap_last_key(struct nilfs_bmap *bmap, __u64 *keyp)219{220 int ret;221 222 down_read(&bmap->b_sem);223 ret = bmap->b_ops->bop_last_key(bmap, keyp);224 up_read(&bmap->b_sem);225 226 if (ret < 0)227 ret = nilfs_bmap_convert_error(bmap, __func__, ret);228 return ret;229}230 231/**232 * nilfs_bmap_delete - delete a key-record pair from a bmap233 * @bmap: bmap234 * @key: key235 *236 * Description: nilfs_bmap_delete() deletes the key-record pair specified by237 * @key from @bmap.238 *239 * Return Value: On success, 0 is returned. On error, one of the following240 * negative error codes is returned.241 *242 * %-EIO - I/O error.243 *244 * %-ENOMEM - Insufficient amount of memory available.245 *246 * %-ENOENT - A record associated with @key does not exist.247 */248int nilfs_bmap_delete(struct nilfs_bmap *bmap, __u64 key)249{250 int ret;251 252 down_write(&bmap->b_sem);253 ret = nilfs_bmap_do_delete(bmap, key);254 up_write(&bmap->b_sem);255 256 return nilfs_bmap_convert_error(bmap, __func__, ret);257}258 259static int nilfs_bmap_do_truncate(struct nilfs_bmap *bmap, __u64 key)260{261 __u64 lastkey;262 int ret;263 264 ret = bmap->b_ops->bop_last_key(bmap, &lastkey);265 if (ret < 0) {266 if (ret == -ENOENT)267 ret = 0;268 return ret;269 }270 271 while (key <= lastkey) {272 ret = nilfs_bmap_do_delete(bmap, lastkey);273 if (ret < 0)274 return ret;275 ret = bmap->b_ops->bop_last_key(bmap, &lastkey);276 if (ret < 0) {277 if (ret == -ENOENT)278 ret = 0;279 return ret;280 }281 }282 return 0;283}284 285/**286 * nilfs_bmap_truncate - truncate a bmap to a specified key287 * @bmap: bmap288 * @key: key289 *290 * Description: nilfs_bmap_truncate() removes key-record pairs whose keys are291 * greater than or equal to @key from @bmap.292 *293 * Return Value: On success, 0 is returned. On error, one of the following294 * negative error codes is returned.295 *296 * %-EIO - I/O error.297 *298 * %-ENOMEM - Insufficient amount of memory available.299 */300int nilfs_bmap_truncate(struct nilfs_bmap *bmap, __u64 key)301{302 int ret;303 304 down_write(&bmap->b_sem);305 ret = nilfs_bmap_do_truncate(bmap, key);306 up_write(&bmap->b_sem);307 308 return nilfs_bmap_convert_error(bmap, __func__, ret);309}310 311/**312 * nilfs_bmap_clear - free resources a bmap holds313 * @bmap: bmap314 *315 * Description: nilfs_bmap_clear() frees resources associated with @bmap.316 */317void nilfs_bmap_clear(struct nilfs_bmap *bmap)318{319 down_write(&bmap->b_sem);320 if (bmap->b_ops->bop_clear != NULL)321 bmap->b_ops->bop_clear(bmap);322 up_write(&bmap->b_sem);323}324 325/**326 * nilfs_bmap_propagate - propagate dirty state327 * @bmap: bmap328 * @bh: buffer head329 *330 * Description: nilfs_bmap_propagate() marks the buffers that directly or331 * indirectly refer to the block specified by @bh dirty.332 *333 * Return Value: On success, 0 is returned. On error, one of the following334 * negative error codes is returned.335 *336 * %-EIO - I/O error.337 *338 * %-ENOMEM - Insufficient amount of memory available.339 */340int nilfs_bmap_propagate(struct nilfs_bmap *bmap, struct buffer_head *bh)341{342 int ret;343 344 down_write(&bmap->b_sem);345 ret = bmap->b_ops->bop_propagate(bmap, bh);346 up_write(&bmap->b_sem);347 348 return nilfs_bmap_convert_error(bmap, __func__, ret);349}350 351/**352 * nilfs_bmap_lookup_dirty_buffers - collect dirty block buffers353 * @bmap: bmap354 * @listp: pointer to buffer head list355 */356void nilfs_bmap_lookup_dirty_buffers(struct nilfs_bmap *bmap,357 struct list_head *listp)358{359 if (bmap->b_ops->bop_lookup_dirty_buffers != NULL)360 bmap->b_ops->bop_lookup_dirty_buffers(bmap, listp);361}362 363/**364 * nilfs_bmap_assign - assign a new block number to a block365 * @bmap: bmap366 * @bh: pointer to buffer head367 * @blocknr: block number368 * @binfo: block information369 *370 * Description: nilfs_bmap_assign() assigns the block number @blocknr to the371 * buffer specified by @bh.372 *373 * Return Value: On success, 0 is returned and the buffer head of a newly374 * create buffer and the block information associated with the buffer are375 * stored in the place pointed by @bh and @binfo, respectively. On error, one376 * of the following negative error codes is returned.377 *378 * %-EIO - I/O error.379 *380 * %-ENOMEM - Insufficient amount of memory available.381 */382int nilfs_bmap_assign(struct nilfs_bmap *bmap,383 struct buffer_head **bh,384 unsigned long blocknr,385 union nilfs_binfo *binfo)386{387 int ret;388 389 down_write(&bmap->b_sem);390 ret = bmap->b_ops->bop_assign(bmap, bh, blocknr, binfo);391 up_write(&bmap->b_sem);392 393 return nilfs_bmap_convert_error(bmap, __func__, ret);394}395 396/**397 * nilfs_bmap_mark - mark block dirty398 * @bmap: bmap399 * @key: key400 * @level: level401 *402 * Description: nilfs_bmap_mark() marks the block specified by @key and @level403 * as dirty.404 *405 * Return Value: On success, 0 is returned. On error, one of the following406 * negative error codes is returned.407 *408 * %-EIO - I/O error.409 *410 * %-ENOMEM - Insufficient amount of memory available.411 */412int nilfs_bmap_mark(struct nilfs_bmap *bmap, __u64 key, int level)413{414 int ret;415 416 if (bmap->b_ops->bop_mark == NULL)417 return 0;418 419 down_write(&bmap->b_sem);420 ret = bmap->b_ops->bop_mark(bmap, key, level);421 up_write(&bmap->b_sem);422 423 return nilfs_bmap_convert_error(bmap, __func__, ret);424}425 426/**427 * nilfs_bmap_test_and_clear_dirty - test and clear a bmap dirty state428 * @bmap: bmap429 *430 * Description: nilfs_test_and_clear() is the atomic operation to test and431 * clear the dirty state of @bmap.432 *433 * Return Value: 1 is returned if @bmap is dirty, or 0 if clear.434 */435int nilfs_bmap_test_and_clear_dirty(struct nilfs_bmap *bmap)436{437 int ret;438 439 down_write(&bmap->b_sem);440 ret = nilfs_bmap_dirty(bmap);441 nilfs_bmap_clear_dirty(bmap);442 up_write(&bmap->b_sem);443 return ret;444}445 446 447/*448 * Internal use only449 */450__u64 nilfs_bmap_data_get_key(const struct nilfs_bmap *bmap,451 const struct buffer_head *bh)452{453 loff_t pos = folio_pos(bh->b_folio) + bh_offset(bh);454 455 return pos >> bmap->b_inode->i_blkbits;456}457 458__u64 nilfs_bmap_find_target_seq(const struct nilfs_bmap *bmap, __u64 key)459{460 __s64 diff;461 462 diff = key - bmap->b_last_allocated_key;463 if ((nilfs_bmap_keydiff_abs(diff) < NILFS_INODE_BMAP_SIZE) &&464 (bmap->b_last_allocated_ptr != NILFS_BMAP_INVALID_PTR) &&465 (bmap->b_last_allocated_ptr + diff > 0))466 return bmap->b_last_allocated_ptr + diff;467 else468 return NILFS_BMAP_INVALID_PTR;469}470 471#define NILFS_BMAP_GROUP_DIV 8472__u64 nilfs_bmap_find_target_in_group(const struct nilfs_bmap *bmap)473{474 struct inode *dat = nilfs_bmap_get_dat(bmap);475 unsigned long entries_per_group = nilfs_palloc_entries_per_group(dat);476 unsigned long group = bmap->b_inode->i_ino / entries_per_group;477 478 return group * entries_per_group +479 (bmap->b_inode->i_ino % NILFS_BMAP_GROUP_DIV) *480 (entries_per_group / NILFS_BMAP_GROUP_DIV);481}482 483static struct lock_class_key nilfs_bmap_dat_lock_key;484static struct lock_class_key nilfs_bmap_mdt_lock_key;485 486/**487 * nilfs_bmap_read - read a bmap from an inode488 * @bmap: bmap489 * @raw_inode: on-disk inode490 *491 * Description: nilfs_bmap_read() initializes the bmap @bmap.492 *493 * Return Value: On success, 0 is returned. On error, the following negative494 * error code is returned.495 *496 * %-ENOMEM - Insufficient amount of memory available.497 */498int nilfs_bmap_read(struct nilfs_bmap *bmap, struct nilfs_inode *raw_inode)499{500 if (raw_inode == NULL)501 memset(bmap->b_u.u_data, 0, NILFS_BMAP_SIZE);502 else503 memcpy(bmap->b_u.u_data, raw_inode->i_bmap, NILFS_BMAP_SIZE);504 505 init_rwsem(&bmap->b_sem);506 bmap->b_state = 0;507 bmap->b_inode = &NILFS_BMAP_I(bmap)->vfs_inode;508 switch (bmap->b_inode->i_ino) {509 case NILFS_DAT_INO:510 bmap->b_ptr_type = NILFS_BMAP_PTR_P;511 bmap->b_last_allocated_key = 0;512 bmap->b_last_allocated_ptr = NILFS_BMAP_NEW_PTR_INIT;513 lockdep_set_class(&bmap->b_sem, &nilfs_bmap_dat_lock_key);514 break;515 case NILFS_CPFILE_INO:516 case NILFS_SUFILE_INO:517 bmap->b_ptr_type = NILFS_BMAP_PTR_VS;518 bmap->b_last_allocated_key = 0;519 bmap->b_last_allocated_ptr = NILFS_BMAP_INVALID_PTR;520 lockdep_set_class(&bmap->b_sem, &nilfs_bmap_mdt_lock_key);521 break;522 case NILFS_IFILE_INO:523 lockdep_set_class(&bmap->b_sem, &nilfs_bmap_mdt_lock_key);524 fallthrough;525 default:526 bmap->b_ptr_type = NILFS_BMAP_PTR_VM;527 bmap->b_last_allocated_key = 0;528 bmap->b_last_allocated_ptr = NILFS_BMAP_INVALID_PTR;529 break;530 }531 532 return (bmap->b_u.u_flags & NILFS_BMAP_LARGE) ?533 nilfs_btree_init(bmap) : nilfs_direct_init(bmap);534}535 536/**537 * nilfs_bmap_write - write back a bmap to an inode538 * @bmap: bmap539 * @raw_inode: on-disk inode540 *541 * Description: nilfs_bmap_write() stores @bmap in @raw_inode.542 */543void nilfs_bmap_write(struct nilfs_bmap *bmap, struct nilfs_inode *raw_inode)544{545 memcpy(raw_inode->i_bmap, bmap->b_u.u_data,546 NILFS_INODE_BMAP_SIZE * sizeof(__le64));547 if (bmap->b_inode->i_ino == NILFS_DAT_INO)548 bmap->b_last_allocated_ptr = NILFS_BMAP_NEW_PTR_INIT;549}550 551void nilfs_bmap_init_gc(struct nilfs_bmap *bmap)552{553 memset(&bmap->b_u, 0, NILFS_BMAP_SIZE);554 init_rwsem(&bmap->b_sem);555 bmap->b_inode = &NILFS_BMAP_I(bmap)->vfs_inode;556 bmap->b_ptr_type = NILFS_BMAP_PTR_U;557 bmap->b_last_allocated_key = 0;558 bmap->b_last_allocated_ptr = NILFS_BMAP_INVALID_PTR;559 bmap->b_state = 0;560 nilfs_btree_init_gc(bmap);561}562 563void nilfs_bmap_save(const struct nilfs_bmap *bmap,564 struct nilfs_bmap_store *store)565{566 memcpy(store->data, bmap->b_u.u_data, sizeof(store->data));567 store->last_allocated_key = bmap->b_last_allocated_key;568 store->last_allocated_ptr = bmap->b_last_allocated_ptr;569 store->state = bmap->b_state;570}571 572void nilfs_bmap_restore(struct nilfs_bmap *bmap,573 const struct nilfs_bmap_store *store)574{575 memcpy(bmap->b_u.u_data, store->data, sizeof(store->data));576 bmap->b_last_allocated_key = store->last_allocated_key;577 bmap->b_last_allocated_ptr = store->last_allocated_ptr;578 bmap->b_state = store->state;579}580