2 * bmap.c - NILFS block mapping.
4 * Copyright (C) 2006-2008 Nippon Telegraph and Telephone Corporation.
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.
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.
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
20 * Written by Koji Sato <koji@osrg.net>.
24 #include <linux/string.h>
25 #include <linux/errno.h>
36 struct inode *nilfs_bmap_get_dat(const struct nilfs_bmap *bmap)
38 return nilfs_dat_inode(NILFS_I_NILFS(bmap->b_inode));
42 * nilfs_bmap_lookup_at_level - find a data block or node block
46 * @ptrp: place to store the value associated to @key
48 * Description: nilfs_bmap_lookup_at_level() finds a record whose key
49 * matches @key in the block at @level of the bmap.
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.
57 * %-ENOMEM - Insufficient amount of memory available.
59 * %-ENOENT - A record associated with @key does not exist.
61 int nilfs_bmap_lookup_at_level(struct nilfs_bmap *bmap, __u64 key, int level,
67 down_read(&bmap->b_sem);
68 ret = bmap->b_ops->bop_lookup(bmap, key, level, ptrp);
71 if (NILFS_BMAP_USE_VBN(bmap)) {
72 ret = nilfs_dat_translate(nilfs_bmap_get_dat(bmap), *ptrp,
79 up_read(&bmap->b_sem);
83 int nilfs_bmap_lookup_contig(struct nilfs_bmap *bmap, __u64 key, __u64 *ptrp,
88 down_read(&bmap->b_sem);
89 ret = bmap->b_ops->bop_lookup_contig(bmap, key, ptrp, maxblocks);
90 up_read(&bmap->b_sem);
94 static int nilfs_bmap_do_insert(struct nilfs_bmap *bmap, __u64 key, __u64 ptr)
96 __u64 keys[NILFS_BMAP_SMALL_HIGH + 1];
97 __u64 ptrs[NILFS_BMAP_SMALL_HIGH + 1];
100 if (bmap->b_ops->bop_check_insert != NULL) {
101 ret = bmap->b_ops->bop_check_insert(bmap, key);
103 n = bmap->b_ops->bop_gather_data(
104 bmap, keys, ptrs, NILFS_BMAP_SMALL_HIGH + 1);
107 ret = nilfs_btree_convert_and_insert(
108 bmap, key, ptr, keys, ptrs, n);
110 bmap->b_u.u_flags |= NILFS_BMAP_LARGE;
117 return bmap->b_ops->bop_insert(bmap, key, ptr);
121 * nilfs_bmap_insert - insert a new key-record pair into a bmap
126 * Description: nilfs_bmap_insert() inserts the new key-record pair specified
127 * by @key and @rec into @bmap.
129 * Return Value: On success, 0 is returned. On error, one of the following
130 * negative error codes is returned.
134 * %-ENOMEM - Insufficient amount of memory available.
136 * %-EEXIST - A record associated with @key already exist.
138 int nilfs_bmap_insert(struct nilfs_bmap *bmap,
144 down_write(&bmap->b_sem);
145 ret = nilfs_bmap_do_insert(bmap, key, rec);
146 up_write(&bmap->b_sem);
150 static int nilfs_bmap_do_delete(struct nilfs_bmap *bmap, __u64 key)
152 __u64 keys[NILFS_BMAP_LARGE_LOW + 1];
153 __u64 ptrs[NILFS_BMAP_LARGE_LOW + 1];
156 if (bmap->b_ops->bop_check_delete != NULL) {
157 ret = bmap->b_ops->bop_check_delete(bmap, key);
159 n = bmap->b_ops->bop_gather_data(
160 bmap, keys, ptrs, NILFS_BMAP_LARGE_LOW + 1);
163 ret = nilfs_direct_delete_and_convert(
164 bmap, key, keys, ptrs, n);
166 bmap->b_u.u_flags &= ~NILFS_BMAP_LARGE;
173 return bmap->b_ops->bop_delete(bmap, key);
176 int nilfs_bmap_last_key(struct nilfs_bmap *bmap, unsigned long *key)
181 down_read(&bmap->b_sem);
182 ret = bmap->b_ops->bop_last_key(bmap, &lastkey);
185 up_read(&bmap->b_sem);
190 * nilfs_bmap_delete - delete a key-record pair from a bmap
194 * Description: nilfs_bmap_delete() deletes the key-record pair specified by
197 * Return Value: On success, 0 is returned. On error, one of the following
198 * negative error codes is returned.
202 * %-ENOMEM - Insufficient amount of memory available.
204 * %-ENOENT - A record associated with @key does not exist.
206 int nilfs_bmap_delete(struct nilfs_bmap *bmap, unsigned long key)
210 down_write(&bmap->b_sem);
211 ret = nilfs_bmap_do_delete(bmap, key);
212 up_write(&bmap->b_sem);
216 static int nilfs_bmap_do_truncate(struct nilfs_bmap *bmap, unsigned long key)
221 ret = bmap->b_ops->bop_last_key(bmap, &lastkey);
228 while (key <= lastkey) {
229 ret = nilfs_bmap_do_delete(bmap, lastkey);
232 ret = bmap->b_ops->bop_last_key(bmap, &lastkey);
243 * nilfs_bmap_truncate - truncate a bmap to a specified key
247 * Description: nilfs_bmap_truncate() removes key-record pairs whose keys are
248 * greater than or equal to @key from @bmap.
250 * Return Value: On success, 0 is returned. On error, one of the following
251 * negative error codes is returned.
255 * %-ENOMEM - Insufficient amount of memory available.
257 int nilfs_bmap_truncate(struct nilfs_bmap *bmap, unsigned long key)
261 down_write(&bmap->b_sem);
262 ret = nilfs_bmap_do_truncate(bmap, key);
263 up_write(&bmap->b_sem);
268 * nilfs_bmap_clear - free resources a bmap holds
271 * Description: nilfs_bmap_clear() frees resources associated with @bmap.
273 void nilfs_bmap_clear(struct nilfs_bmap *bmap)
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);
282 * nilfs_bmap_propagate - propagate dirty state
286 * Description: nilfs_bmap_propagate() marks the buffers that directly or
287 * indirectly refer to the block specified by @bh dirty.
289 * Return Value: On success, 0 is returned. On error, one of the following
290 * negative error codes is returned.
294 * %-ENOMEM - Insufficient amount of memory available.
296 int nilfs_bmap_propagate(struct nilfs_bmap *bmap, struct buffer_head *bh)
300 down_write(&bmap->b_sem);
301 ret = bmap->b_ops->bop_propagate(bmap, bh);
302 up_write(&bmap->b_sem);
307 * nilfs_bmap_lookup_dirty_buffers -
309 * @listp: pointer to buffer head list
311 void nilfs_bmap_lookup_dirty_buffers(struct nilfs_bmap *bmap,
312 struct list_head *listp)
314 if (bmap->b_ops->bop_lookup_dirty_buffers != NULL)
315 bmap->b_ops->bop_lookup_dirty_buffers(bmap, listp);
319 * nilfs_bmap_assign - assign a new block number to a block
321 * @bhp: pointer to buffer head
322 * @blocknr: block number
323 * @binfo: block information
325 * Description: nilfs_bmap_assign() assigns the block number @blocknr to the
326 * buffer specified by @bh.
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.
335 * %-ENOMEM - Insufficient amount of memory available.
337 int nilfs_bmap_assign(struct nilfs_bmap *bmap,
338 struct buffer_head **bh,
339 unsigned long blocknr,
340 union nilfs_binfo *binfo)
344 down_write(&bmap->b_sem);
345 ret = bmap->b_ops->bop_assign(bmap, bh, blocknr, binfo);
346 up_write(&bmap->b_sem);
351 * nilfs_bmap_mark - mark block dirty
356 * Description: nilfs_bmap_mark() marks the block specified by @key and @level
359 * Return Value: On success, 0 is returned. On error, one of the following
360 * negative error codes is returned.
364 * %-ENOMEM - Insufficient amount of memory available.
366 int nilfs_bmap_mark(struct nilfs_bmap *bmap, __u64 key, int level)
370 if (bmap->b_ops->bop_mark == NULL)
373 down_write(&bmap->b_sem);
374 ret = bmap->b_ops->bop_mark(bmap, key, level);
375 up_write(&bmap->b_sem);
380 * nilfs_bmap_test_and_clear_dirty - test and clear a bmap dirty state
383 * Description: nilfs_test_and_clear() is the atomic operation to test and
384 * clear the dirty state of @bmap.
386 * Return Value: 1 is returned if @bmap is dirty, or 0 if clear.
388 int nilfs_bmap_test_and_clear_dirty(struct nilfs_bmap *bmap)
392 down_write(&bmap->b_sem);
393 ret = nilfs_bmap_dirty(bmap);
394 nilfs_bmap_clear_dirty(bmap);
395 up_write(&bmap->b_sem);
404 void nilfs_bmap_add_blocks(const struct nilfs_bmap *bmap, int n)
406 inode_add_bytes(bmap->b_inode, (1 << bmap->b_inode->i_blkbits) * n);
409 void nilfs_bmap_sub_blocks(const struct nilfs_bmap *bmap, int n)
411 inode_sub_bytes(bmap->b_inode, (1 << bmap->b_inode->i_blkbits) * n);
414 __u64 nilfs_bmap_data_get_key(const struct nilfs_bmap *bmap,
415 const struct buffer_head *bh)
417 struct buffer_head *pbh;
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)
428 __u64 nilfs_bmap_find_target_seq(const struct nilfs_bmap *bmap, __u64 key)
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;
438 return NILFS_BMAP_INVALID_PTR;
441 #define NILFS_BMAP_GROUP_DIV 8
442 __u64 nilfs_bmap_find_target_in_group(const struct nilfs_bmap *bmap)
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;
448 return group * entries_per_group +
449 (bmap->b_inode->i_ino % NILFS_BMAP_GROUP_DIV) *
450 (entries_per_group / NILFS_BMAP_GROUP_DIV);
453 static struct lock_class_key nilfs_bmap_dat_lock_key;
454 static struct lock_class_key nilfs_bmap_mdt_lock_key;
457 * nilfs_bmap_read - read a bmap from an inode
459 * @raw_inode: on-disk inode
461 * Description: nilfs_bmap_read() initializes the bmap @bmap.
463 * Return Value: On success, 0 is returned. On error, the following negative
464 * error code is returned.
466 * %-ENOMEM - Insufficient amount of memory available.
468 int nilfs_bmap_read(struct nilfs_bmap *bmap, struct nilfs_inode *raw_inode)
470 if (raw_inode == NULL)
471 memset(bmap->b_u.u_data, 0, NILFS_BMAP_SIZE);
473 memcpy(bmap->b_u.u_data, raw_inode->i_bmap, NILFS_BMAP_SIZE);
475 init_rwsem(&bmap->b_sem);
477 bmap->b_inode = &NILFS_BMAP_I(bmap)->vfs_inode;
478 switch (bmap->b_inode->i_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);
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);
492 case NILFS_IFILE_INO:
493 lockdep_set_class(&bmap->b_sem, &nilfs_bmap_mdt_lock_key);
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;
502 return (bmap->b_u.u_flags & NILFS_BMAP_LARGE) ?
503 nilfs_btree_init(bmap) : nilfs_direct_init(bmap);
507 * nilfs_bmap_write - write back a bmap to an inode
509 * @raw_inode: on-disk inode
511 * Description: nilfs_bmap_write() stores @bmap in @raw_inode.
513 void nilfs_bmap_write(struct nilfs_bmap *bmap, struct nilfs_inode *raw_inode)
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;
521 up_write(&bmap->b_sem);
524 void nilfs_bmap_init_gc(struct nilfs_bmap *bmap)
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;
533 nilfs_btree_init_gc(bmap);
536 void nilfs_bmap_save(const struct nilfs_bmap *bmap,
537 struct nilfs_bmap_store *store)
539 memcpy(store->data, bmap->b_u.u_data, sizeof(store->data));
540 store->last_allocated_key = bmap->b_last_allocated_key;
541 store->last_allocated_ptr = bmap->b_last_allocated_ptr;
542 store->state = bmap->b_state;
545 void nilfs_bmap_restore(struct nilfs_bmap *bmap,
546 const struct nilfs_bmap_store *store)
548 memcpy(bmap->b_u.u_data, store->data, sizeof(store->data));
549 bmap->b_last_allocated_key = store->last_allocated_key;
550 bmap->b_last_allocated_ptr = store->last_allocated_ptr;
551 bmap->b_state = store->state;