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>
34 int nilfs_bmap_lookup_at_level(struct nilfs_bmap *bmap, __u64 key, int level,
40 down_read(&bmap->b_sem);
41 ret = bmap->b_ops->bop_lookup(bmap, key, level, ptrp);
44 if (bmap->b_pops->bpop_translate != NULL) {
45 ret = bmap->b_pops->bpop_translate(bmap, *ptrp, &ptr);
52 up_read(&bmap->b_sem);
58 * nilfs_bmap_lookup - find a record
61 * @recp: pointer to record
63 * Description: nilfs_bmap_lookup() finds a record whose key matches @key in
66 * Return Value: On success, 0 is returned and the record associated with @key
67 * is stored in the place pointed by @recp. On error, one of the following
68 * negative error codes is returned.
72 * %-ENOMEM - Insufficient amount of memory available.
74 * %-ENOENT - A record associated with @key does not exist.
76 int nilfs_bmap_lookup(struct nilfs_bmap *bmap,
83 /* XXX: use macro for level 1 */
84 ret = nilfs_bmap_lookup_at_level(bmap, key, 1, &ptr);
90 static int nilfs_bmap_do_insert(struct nilfs_bmap *bmap, __u64 key, __u64 ptr)
92 __u64 keys[NILFS_BMAP_SMALL_HIGH + 1];
93 __u64 ptrs[NILFS_BMAP_SMALL_HIGH + 1];
96 if (bmap->b_ops->bop_check_insert != NULL) {
97 ret = bmap->b_ops->bop_check_insert(bmap, key);
99 n = bmap->b_ops->bop_gather_data(
100 bmap, keys, ptrs, NILFS_BMAP_SMALL_HIGH + 1);
103 ret = nilfs_btree_convert_and_insert(
104 bmap, key, ptr, keys, ptrs, n);
106 bmap->b_u.u_flags |= NILFS_BMAP_LARGE;
113 return bmap->b_ops->bop_insert(bmap, key, ptr);
117 * nilfs_bmap_insert - insert a new key-record pair into a bmap
122 * Description: nilfs_bmap_insert() inserts the new key-record pair specified
123 * by @key and @rec into @bmap.
125 * Return Value: On success, 0 is returned. On error, one of the following
126 * negative error codes is returned.
130 * %-ENOMEM - Insufficient amount of memory available.
132 * %-EEXIST - A record associated with @key already exist.
134 int nilfs_bmap_insert(struct nilfs_bmap *bmap,
140 down_write(&bmap->b_sem);
141 ret = nilfs_bmap_do_insert(bmap, key, rec);
142 up_write(&bmap->b_sem);
146 static int nilfs_bmap_do_delete(struct nilfs_bmap *bmap, __u64 key)
148 __u64 keys[NILFS_BMAP_LARGE_LOW + 1];
149 __u64 ptrs[NILFS_BMAP_LARGE_LOW + 1];
152 if (bmap->b_ops->bop_check_delete != NULL) {
153 ret = bmap->b_ops->bop_check_delete(bmap, key);
155 n = bmap->b_ops->bop_gather_data(
156 bmap, keys, ptrs, NILFS_BMAP_LARGE_LOW + 1);
159 ret = nilfs_direct_delete_and_convert(
160 bmap, key, keys, ptrs, n);
162 bmap->b_u.u_flags &= ~NILFS_BMAP_LARGE;
169 return bmap->b_ops->bop_delete(bmap, key);
172 int nilfs_bmap_last_key(struct nilfs_bmap *bmap, unsigned long *key)
177 down_read(&bmap->b_sem);
178 ret = bmap->b_ops->bop_last_key(bmap, &lastkey);
181 up_read(&bmap->b_sem);
186 * nilfs_bmap_delete - delete a key-record pair from a bmap
190 * Description: nilfs_bmap_delete() deletes the key-record pair specified by
193 * Return Value: On success, 0 is returned. On error, one of the following
194 * negative error codes is returned.
198 * %-ENOMEM - Insufficient amount of memory available.
200 * %-ENOENT - A record associated with @key does not exist.
202 int nilfs_bmap_delete(struct nilfs_bmap *bmap, unsigned long key)
206 down_write(&bmap->b_sem);
207 ret = nilfs_bmap_do_delete(bmap, key);
208 up_write(&bmap->b_sem);
212 static int nilfs_bmap_do_truncate(struct nilfs_bmap *bmap, unsigned long key)
217 ret = bmap->b_ops->bop_last_key(bmap, &lastkey);
224 while (key <= lastkey) {
225 ret = nilfs_bmap_do_delete(bmap, lastkey);
228 ret = bmap->b_ops->bop_last_key(bmap, &lastkey);
239 * nilfs_bmap_truncate - truncate a bmap to a specified key
243 * Description: nilfs_bmap_truncate() removes key-record pairs whose keys are
244 * greater than or equal to @key from @bmap.
246 * Return Value: On success, 0 is returned. On error, one of the following
247 * negative error codes is returned.
251 * %-ENOMEM - Insufficient amount of memory available.
253 int nilfs_bmap_truncate(struct nilfs_bmap *bmap, unsigned long key)
257 down_write(&bmap->b_sem);
258 ret = nilfs_bmap_do_truncate(bmap, key);
259 up_write(&bmap->b_sem);
264 * nilfs_bmap_clear - free resources a bmap holds
267 * Description: nilfs_bmap_clear() frees resources associated with @bmap.
269 void nilfs_bmap_clear(struct nilfs_bmap *bmap)
271 down_write(&bmap->b_sem);
272 if (bmap->b_ops->bop_clear != NULL)
273 bmap->b_ops->bop_clear(bmap);
274 up_write(&bmap->b_sem);
278 * nilfs_bmap_propagate - propagate dirty state
282 * Description: nilfs_bmap_propagate() marks the buffers that directly or
283 * indirectly refer to the block specified by @bh dirty.
285 * Return Value: On success, 0 is returned. On error, one of the following
286 * negative error codes is returned.
290 * %-ENOMEM - Insufficient amount of memory available.
292 int nilfs_bmap_propagate(struct nilfs_bmap *bmap, struct buffer_head *bh)
296 down_write(&bmap->b_sem);
297 ret = bmap->b_ops->bop_propagate(bmap, bh);
298 up_write(&bmap->b_sem);
303 * nilfs_bmap_lookup_dirty_buffers -
305 * @listp: pointer to buffer head list
307 void nilfs_bmap_lookup_dirty_buffers(struct nilfs_bmap *bmap,
308 struct list_head *listp)
310 if (bmap->b_ops->bop_lookup_dirty_buffers != NULL)
311 bmap->b_ops->bop_lookup_dirty_buffers(bmap, listp);
315 * nilfs_bmap_assign - assign a new block number to a block
317 * @bhp: pointer to buffer head
318 * @blocknr: block number
319 * @binfo: block information
321 * Description: nilfs_bmap_assign() assigns the block number @blocknr to the
322 * buffer specified by @bh.
324 * Return Value: On success, 0 is returned and the buffer head of a newly
325 * create buffer and the block information associated with the buffer are
326 * stored in the place pointed by @bh and @binfo, respectively. On error, one
327 * of the following negative error codes is returned.
331 * %-ENOMEM - Insufficient amount of memory available.
333 int nilfs_bmap_assign(struct nilfs_bmap *bmap,
334 struct buffer_head **bh,
335 unsigned long blocknr,
336 union nilfs_binfo *binfo)
340 down_write(&bmap->b_sem);
341 ret = bmap->b_ops->bop_assign(bmap, bh, blocknr, binfo);
342 up_write(&bmap->b_sem);
347 * nilfs_bmap_mark - mark block dirty
352 * Description: nilfs_bmap_mark() marks the block specified by @key and @level
355 * Return Value: On success, 0 is returned. On error, one of the following
356 * negative error codes is returned.
360 * %-ENOMEM - Insufficient amount of memory available.
362 int nilfs_bmap_mark(struct nilfs_bmap *bmap, __u64 key, int level)
366 if (bmap->b_ops->bop_mark == NULL)
369 down_write(&bmap->b_sem);
370 ret = bmap->b_ops->bop_mark(bmap, key, level);
371 up_write(&bmap->b_sem);
376 * nilfs_bmap_test_and_clear_dirty - test and clear a bmap dirty state
379 * Description: nilfs_test_and_clear() is the atomic operation to test and
380 * clear the dirty state of @bmap.
382 * Return Value: 1 is returned if @bmap is dirty, or 0 if clear.
384 int nilfs_bmap_test_and_clear_dirty(struct nilfs_bmap *bmap)
388 down_write(&bmap->b_sem);
389 ret = nilfs_bmap_dirty(bmap);
390 nilfs_bmap_clear_dirty(bmap);
391 up_write(&bmap->b_sem);
400 void nilfs_bmap_add_blocks(const struct nilfs_bmap *bmap, int n)
402 inode_add_bytes(bmap->b_inode, (1 << bmap->b_inode->i_blkbits) * n);
403 if (NILFS_MDT(bmap->b_inode))
404 nilfs_mdt_mark_dirty(bmap->b_inode);
406 mark_inode_dirty(bmap->b_inode);
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);
412 if (NILFS_MDT(bmap->b_inode))
413 nilfs_mdt_mark_dirty(bmap->b_inode);
415 mark_inode_dirty(bmap->b_inode);
418 __u64 nilfs_bmap_data_get_key(const struct nilfs_bmap *bmap,
419 const struct buffer_head *bh)
421 struct buffer_head *pbh;
424 key = page_index(bh->b_page) << (PAGE_CACHE_SHIFT -
425 bmap->b_inode->i_blkbits);
426 for (pbh = page_buffers(bh->b_page); pbh != bh;
427 pbh = pbh->b_this_page, key++);
432 __u64 nilfs_bmap_find_target_seq(const struct nilfs_bmap *bmap, __u64 key)
436 diff = key - bmap->b_last_allocated_key;
437 if ((nilfs_bmap_keydiff_abs(diff) < NILFS_INODE_BMAP_SIZE) &&
438 (bmap->b_last_allocated_ptr != NILFS_BMAP_INVALID_PTR) &&
439 (bmap->b_last_allocated_ptr + diff > 0))
440 return bmap->b_last_allocated_ptr + diff;
442 return NILFS_BMAP_INVALID_PTR;
445 static struct inode *nilfs_bmap_get_dat(const struct nilfs_bmap *bmap)
447 return nilfs_dat_inode(NILFS_I_NILFS(bmap->b_inode));
450 #define NILFS_BMAP_GROUP_DIV 8
451 __u64 nilfs_bmap_find_target_in_group(const struct nilfs_bmap *bmap)
453 struct inode *dat = nilfs_bmap_get_dat(bmap);
454 unsigned long entries_per_group = nilfs_palloc_entries_per_group(dat);
455 unsigned long group = bmap->b_inode->i_ino / entries_per_group;
457 return group * entries_per_group +
458 (bmap->b_inode->i_ino % NILFS_BMAP_GROUP_DIV) *
459 (entries_per_group / NILFS_BMAP_GROUP_DIV);
462 static int nilfs_bmap_prepare_alloc_v(struct nilfs_bmap *bmap,
463 union nilfs_bmap_ptr_req *req)
465 return nilfs_dat_prepare_alloc(nilfs_bmap_get_dat(bmap), &req->bpr_req);
468 static void nilfs_bmap_commit_alloc_v(struct nilfs_bmap *bmap,
469 union nilfs_bmap_ptr_req *req)
471 nilfs_dat_commit_alloc(nilfs_bmap_get_dat(bmap), &req->bpr_req);
474 static void nilfs_bmap_abort_alloc_v(struct nilfs_bmap *bmap,
475 union nilfs_bmap_ptr_req *req)
477 nilfs_dat_abort_alloc(nilfs_bmap_get_dat(bmap), &req->bpr_req);
480 int nilfs_bmap_start_v(struct nilfs_bmap *bmap, union nilfs_bmap_ptr_req *req,
483 struct inode *dat = nilfs_bmap_get_dat(bmap);
486 ret = nilfs_dat_prepare_start(dat, &req->bpr_req);
488 nilfs_dat_commit_start(dat, &req->bpr_req, blocknr);
492 static int nilfs_bmap_prepare_end_v(struct nilfs_bmap *bmap,
493 union nilfs_bmap_ptr_req *req)
495 return nilfs_dat_prepare_end(nilfs_bmap_get_dat(bmap), &req->bpr_req);
498 static void nilfs_bmap_commit_end_v(struct nilfs_bmap *bmap,
499 union nilfs_bmap_ptr_req *req)
501 nilfs_dat_commit_end(nilfs_bmap_get_dat(bmap), &req->bpr_req, 0);
504 static void nilfs_bmap_commit_end_vmdt(struct nilfs_bmap *bmap,
505 union nilfs_bmap_ptr_req *req)
507 nilfs_dat_commit_end(nilfs_bmap_get_dat(bmap), &req->bpr_req, 1);
510 static void nilfs_bmap_abort_end_v(struct nilfs_bmap *bmap,
511 union nilfs_bmap_ptr_req *req)
513 nilfs_dat_abort_end(nilfs_bmap_get_dat(bmap), &req->bpr_req);
516 int nilfs_bmap_move_v(const struct nilfs_bmap *bmap, __u64 vblocknr,
519 return nilfs_dat_move(nilfs_bmap_get_dat(bmap), vblocknr, blocknr);
522 int nilfs_bmap_mark_dirty(const struct nilfs_bmap *bmap, __u64 vblocknr)
524 return nilfs_dat_mark_dirty(nilfs_bmap_get_dat(bmap), vblocknr);
527 int nilfs_bmap_prepare_update(struct nilfs_bmap *bmap,
528 union nilfs_bmap_ptr_req *oldreq,
529 union nilfs_bmap_ptr_req *newreq)
533 ret = bmap->b_pops->bpop_prepare_end_ptr(bmap, oldreq);
536 ret = bmap->b_pops->bpop_prepare_alloc_ptr(bmap, newreq);
538 bmap->b_pops->bpop_abort_end_ptr(bmap, oldreq);
543 void nilfs_bmap_commit_update(struct nilfs_bmap *bmap,
544 union nilfs_bmap_ptr_req *oldreq,
545 union nilfs_bmap_ptr_req *newreq)
547 bmap->b_pops->bpop_commit_end_ptr(bmap, oldreq);
548 bmap->b_pops->bpop_commit_alloc_ptr(bmap, newreq);
551 void nilfs_bmap_abort_update(struct nilfs_bmap *bmap,
552 union nilfs_bmap_ptr_req *oldreq,
553 union nilfs_bmap_ptr_req *newreq)
555 bmap->b_pops->bpop_abort_end_ptr(bmap, oldreq);
556 bmap->b_pops->bpop_abort_alloc_ptr(bmap, newreq);
559 static int nilfs_bmap_translate_v(const struct nilfs_bmap *bmap, __u64 ptr,
565 ret = nilfs_dat_translate(nilfs_bmap_get_dat(bmap), ptr, &blocknr);
573 static int nilfs_bmap_prepare_alloc_p(struct nilfs_bmap *bmap,
574 union nilfs_bmap_ptr_req *req)
576 /* ignore target ptr */
577 req->bpr_ptr = bmap->b_last_allocated_ptr++;
581 static void nilfs_bmap_commit_alloc_p(struct nilfs_bmap *bmap,
582 union nilfs_bmap_ptr_req *req)
587 static void nilfs_bmap_abort_alloc_p(struct nilfs_bmap *bmap,
588 union nilfs_bmap_ptr_req *req)
590 bmap->b_last_allocated_ptr--;
593 static const struct nilfs_bmap_ptr_operations nilfs_bmap_ptr_ops_v = {
594 .bpop_prepare_alloc_ptr = nilfs_bmap_prepare_alloc_v,
595 .bpop_commit_alloc_ptr = nilfs_bmap_commit_alloc_v,
596 .bpop_abort_alloc_ptr = nilfs_bmap_abort_alloc_v,
597 .bpop_prepare_end_ptr = nilfs_bmap_prepare_end_v,
598 .bpop_commit_end_ptr = nilfs_bmap_commit_end_v,
599 .bpop_abort_end_ptr = nilfs_bmap_abort_end_v,
601 .bpop_translate = nilfs_bmap_translate_v,
604 static const struct nilfs_bmap_ptr_operations nilfs_bmap_ptr_ops_vmdt = {
605 .bpop_prepare_alloc_ptr = nilfs_bmap_prepare_alloc_v,
606 .bpop_commit_alloc_ptr = nilfs_bmap_commit_alloc_v,
607 .bpop_abort_alloc_ptr = nilfs_bmap_abort_alloc_v,
608 .bpop_prepare_end_ptr = nilfs_bmap_prepare_end_v,
609 .bpop_commit_end_ptr = nilfs_bmap_commit_end_vmdt,
610 .bpop_abort_end_ptr = nilfs_bmap_abort_end_v,
612 .bpop_translate = nilfs_bmap_translate_v,
615 static const struct nilfs_bmap_ptr_operations nilfs_bmap_ptr_ops_p = {
616 .bpop_prepare_alloc_ptr = nilfs_bmap_prepare_alloc_p,
617 .bpop_commit_alloc_ptr = nilfs_bmap_commit_alloc_p,
618 .bpop_abort_alloc_ptr = nilfs_bmap_abort_alloc_p,
619 .bpop_prepare_end_ptr = NULL,
620 .bpop_commit_end_ptr = NULL,
621 .bpop_abort_end_ptr = NULL,
623 .bpop_translate = NULL,
626 static const struct nilfs_bmap_ptr_operations nilfs_bmap_ptr_ops_gc = {
627 .bpop_prepare_alloc_ptr = NULL,
628 .bpop_commit_alloc_ptr = NULL,
629 .bpop_abort_alloc_ptr = NULL,
630 .bpop_prepare_end_ptr = NULL,
631 .bpop_commit_end_ptr = NULL,
632 .bpop_abort_end_ptr = NULL,
634 .bpop_translate = NULL,
637 static struct lock_class_key nilfs_bmap_dat_lock_key;
640 * nilfs_bmap_read - read a bmap from an inode
642 * @raw_inode: on-disk inode
644 * Description: nilfs_bmap_read() initializes the bmap @bmap.
646 * Return Value: On success, 0 is returned. On error, the following negative
647 * error code is returned.
649 * %-ENOMEM - Insufficient amount of memory available.
651 int nilfs_bmap_read(struct nilfs_bmap *bmap, struct nilfs_inode *raw_inode)
653 if (raw_inode == NULL)
654 memset(bmap->b_u.u_data, 0, NILFS_BMAP_SIZE);
656 memcpy(bmap->b_u.u_data, raw_inode->i_bmap, NILFS_BMAP_SIZE);
658 init_rwsem(&bmap->b_sem);
660 bmap->b_inode = &NILFS_BMAP_I(bmap)->vfs_inode;
661 switch (bmap->b_inode->i_ino) {
663 bmap->b_pops = &nilfs_bmap_ptr_ops_p;
664 bmap->b_last_allocated_key = 0; /* XXX: use macro */
665 bmap->b_last_allocated_ptr = NILFS_BMAP_NEW_PTR_INIT;
666 lockdep_set_class(&bmap->b_sem, &nilfs_bmap_dat_lock_key);
668 case NILFS_CPFILE_INO:
669 case NILFS_SUFILE_INO:
670 bmap->b_pops = &nilfs_bmap_ptr_ops_vmdt;
671 bmap->b_last_allocated_key = 0; /* XXX: use macro */
672 bmap->b_last_allocated_ptr = NILFS_BMAP_INVALID_PTR;
675 bmap->b_pops = &nilfs_bmap_ptr_ops_v;
676 bmap->b_last_allocated_key = 0; /* XXX: use macro */
677 bmap->b_last_allocated_ptr = NILFS_BMAP_INVALID_PTR;
681 return (bmap->b_u.u_flags & NILFS_BMAP_LARGE) ?
682 nilfs_btree_init(bmap) : nilfs_direct_init(bmap);
686 * nilfs_bmap_write - write back a bmap to an inode
688 * @raw_inode: on-disk inode
690 * Description: nilfs_bmap_write() stores @bmap in @raw_inode.
692 void nilfs_bmap_write(struct nilfs_bmap *bmap, struct nilfs_inode *raw_inode)
694 down_write(&bmap->b_sem);
695 memcpy(raw_inode->i_bmap, bmap->b_u.u_data,
696 NILFS_INODE_BMAP_SIZE * sizeof(__le64));
697 if (bmap->b_inode->i_ino == NILFS_DAT_INO)
698 bmap->b_last_allocated_ptr = NILFS_BMAP_NEW_PTR_INIT;
700 up_write(&bmap->b_sem);
703 void nilfs_bmap_init_gc(struct nilfs_bmap *bmap)
705 memset(&bmap->b_u, 0, NILFS_BMAP_SIZE);
706 init_rwsem(&bmap->b_sem);
707 bmap->b_inode = &NILFS_BMAP_I(bmap)->vfs_inode;
708 bmap->b_pops = &nilfs_bmap_ptr_ops_gc;
709 bmap->b_last_allocated_key = 0;
710 bmap->b_last_allocated_ptr = NILFS_BMAP_INVALID_PTR;
712 nilfs_btree_init_gc(bmap);
715 void nilfs_bmap_init_gcdat(struct nilfs_bmap *gcbmap, struct nilfs_bmap *bmap)
717 memcpy(gcbmap, bmap, sizeof(union nilfs_bmap_union));
718 init_rwsem(&gcbmap->b_sem);
719 lockdep_set_class(&bmap->b_sem, &nilfs_bmap_dat_lock_key);
720 gcbmap->b_inode = &NILFS_BMAP_I(gcbmap)->vfs_inode;
723 void nilfs_bmap_commit_gcdat(struct nilfs_bmap *gcbmap, struct nilfs_bmap *bmap)
725 memcpy(bmap, gcbmap, sizeof(union nilfs_bmap_union));
726 init_rwsem(&bmap->b_sem);
727 lockdep_set_class(&bmap->b_sem, &nilfs_bmap_dat_lock_key);
728 bmap->b_inode = &NILFS_BMAP_I(bmap)->vfs_inode;