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,
105 NILFS_BMAP_LARGE_LOW, NILFS_BMAP_LARGE_HIGH);
107 bmap->b_u.u_flags |= NILFS_BMAP_LARGE;
114 return bmap->b_ops->bop_insert(bmap, key, ptr);
118 * nilfs_bmap_insert - insert a new key-record pair into a bmap
123 * Description: nilfs_bmap_insert() inserts the new key-record pair specified
124 * by @key and @rec into @bmap.
126 * Return Value: On success, 0 is returned. On error, one of the following
127 * negative error codes is returned.
131 * %-ENOMEM - Insufficient amount of memory available.
133 * %-EEXIST - A record associated with @key already exist.
135 int nilfs_bmap_insert(struct nilfs_bmap *bmap,
141 down_write(&bmap->b_sem);
142 ret = nilfs_bmap_do_insert(bmap, key, rec);
143 up_write(&bmap->b_sem);
147 static int nilfs_bmap_do_delete(struct nilfs_bmap *bmap, __u64 key)
149 __u64 keys[NILFS_BMAP_LARGE_LOW + 1];
150 __u64 ptrs[NILFS_BMAP_LARGE_LOW + 1];
153 if (bmap->b_ops->bop_check_delete != NULL) {
154 ret = bmap->b_ops->bop_check_delete(bmap, key);
156 n = bmap->b_ops->bop_gather_data(
157 bmap, keys, ptrs, NILFS_BMAP_LARGE_LOW + 1);
160 ret = nilfs_direct_delete_and_convert(
161 bmap, key, keys, ptrs, n,
162 NILFS_BMAP_SMALL_LOW, NILFS_BMAP_SMALL_HIGH);
164 bmap->b_u.u_flags &= ~NILFS_BMAP_LARGE;
171 return bmap->b_ops->bop_delete(bmap, key);
174 int nilfs_bmap_last_key(struct nilfs_bmap *bmap, unsigned long *key)
179 down_read(&bmap->b_sem);
180 ret = bmap->b_ops->bop_last_key(bmap, &lastkey);
183 up_read(&bmap->b_sem);
188 * nilfs_bmap_delete - delete a key-record pair from a bmap
192 * Description: nilfs_bmap_delete() deletes the key-record pair specified by
195 * Return Value: On success, 0 is returned. On error, one of the following
196 * negative error codes is returned.
200 * %-ENOMEM - Insufficient amount of memory available.
202 * %-ENOENT - A record associated with @key does not exist.
204 int nilfs_bmap_delete(struct nilfs_bmap *bmap, unsigned long key)
208 down_write(&bmap->b_sem);
209 ret = nilfs_bmap_do_delete(bmap, key);
210 up_write(&bmap->b_sem);
214 static int nilfs_bmap_do_truncate(struct nilfs_bmap *bmap, unsigned long key)
219 ret = bmap->b_ops->bop_last_key(bmap, &lastkey);
226 while (key <= lastkey) {
227 ret = nilfs_bmap_do_delete(bmap, lastkey);
230 ret = bmap->b_ops->bop_last_key(bmap, &lastkey);
241 * nilfs_bmap_truncate - truncate a bmap to a specified key
245 * Description: nilfs_bmap_truncate() removes key-record pairs whose keys are
246 * greater than or equal to @key from @bmap.
248 * Return Value: On success, 0 is returned. On error, one of the following
249 * negative error codes is returned.
253 * %-ENOMEM - Insufficient amount of memory available.
255 int nilfs_bmap_truncate(struct nilfs_bmap *bmap, unsigned long key)
259 down_write(&bmap->b_sem);
260 ret = nilfs_bmap_do_truncate(bmap, key);
261 up_write(&bmap->b_sem);
266 * nilfs_bmap_clear - free resources a bmap holds
269 * Description: nilfs_bmap_clear() frees resources associated with @bmap.
271 void nilfs_bmap_clear(struct nilfs_bmap *bmap)
273 down_write(&bmap->b_sem);
274 if (bmap->b_ops->bop_clear != NULL)
275 bmap->b_ops->bop_clear(bmap);
276 up_write(&bmap->b_sem);
280 * nilfs_bmap_propagate - propagate dirty state
284 * Description: nilfs_bmap_propagate() marks the buffers that directly or
285 * indirectly refer to the block specified by @bh dirty.
287 * Return Value: On success, 0 is returned. On error, one of the following
288 * negative error codes is returned.
292 * %-ENOMEM - Insufficient amount of memory available.
294 int nilfs_bmap_propagate(struct nilfs_bmap *bmap, struct buffer_head *bh)
298 down_write(&bmap->b_sem);
299 ret = bmap->b_ops->bop_propagate(bmap, bh);
300 up_write(&bmap->b_sem);
305 * nilfs_bmap_lookup_dirty_buffers -
307 * @listp: pointer to buffer head list
309 void nilfs_bmap_lookup_dirty_buffers(struct nilfs_bmap *bmap,
310 struct list_head *listp)
312 if (bmap->b_ops->bop_lookup_dirty_buffers != NULL)
313 bmap->b_ops->bop_lookup_dirty_buffers(bmap, listp);
317 * nilfs_bmap_assign - assign a new block number to a block
319 * @bhp: pointer to buffer head
320 * @blocknr: block number
321 * @binfo: block information
323 * Description: nilfs_bmap_assign() assigns the block number @blocknr to the
324 * buffer specified by @bh.
326 * Return Value: On success, 0 is returned and the buffer head of a newly
327 * create buffer and the block information associated with the buffer are
328 * stored in the place pointed by @bh and @binfo, respectively. On error, one
329 * of the following negative error codes is returned.
333 * %-ENOMEM - Insufficient amount of memory available.
335 int nilfs_bmap_assign(struct nilfs_bmap *bmap,
336 struct buffer_head **bh,
337 unsigned long blocknr,
338 union nilfs_binfo *binfo)
342 down_write(&bmap->b_sem);
343 ret = bmap->b_ops->bop_assign(bmap, bh, blocknr, binfo);
344 up_write(&bmap->b_sem);
349 * nilfs_bmap_mark - mark block dirty
354 * Description: nilfs_bmap_mark() marks the block specified by @key and @level
357 * Return Value: On success, 0 is returned. On error, one of the following
358 * negative error codes is returned.
362 * %-ENOMEM - Insufficient amount of memory available.
364 int nilfs_bmap_mark(struct nilfs_bmap *bmap, __u64 key, int level)
368 if (bmap->b_ops->bop_mark == NULL)
371 down_write(&bmap->b_sem);
372 ret = bmap->b_ops->bop_mark(bmap, key, level);
373 up_write(&bmap->b_sem);
378 * nilfs_bmap_test_and_clear_dirty - test and clear a bmap dirty state
381 * Description: nilfs_test_and_clear() is the atomic operation to test and
382 * clear the dirty state of @bmap.
384 * Return Value: 1 is returned if @bmap is dirty, or 0 if clear.
386 int nilfs_bmap_test_and_clear_dirty(struct nilfs_bmap *bmap)
390 down_write(&bmap->b_sem);
391 ret = nilfs_bmap_dirty(bmap);
392 nilfs_bmap_clear_dirty(bmap);
393 up_write(&bmap->b_sem);
402 void nilfs_bmap_add_blocks(const struct nilfs_bmap *bmap, int n)
404 inode_add_bytes(bmap->b_inode, (1 << bmap->b_inode->i_blkbits) * n);
405 if (NILFS_MDT(bmap->b_inode))
406 nilfs_mdt_mark_dirty(bmap->b_inode);
408 mark_inode_dirty(bmap->b_inode);
411 void nilfs_bmap_sub_blocks(const struct nilfs_bmap *bmap, int n)
413 inode_sub_bytes(bmap->b_inode, (1 << bmap->b_inode->i_blkbits) * n);
414 if (NILFS_MDT(bmap->b_inode))
415 nilfs_mdt_mark_dirty(bmap->b_inode);
417 mark_inode_dirty(bmap->b_inode);
420 __u64 nilfs_bmap_data_get_key(const struct nilfs_bmap *bmap,
421 const struct buffer_head *bh)
423 struct buffer_head *pbh;
426 key = page_index(bh->b_page) << (PAGE_CACHE_SHIFT -
427 bmap->b_inode->i_blkbits);
428 for (pbh = page_buffers(bh->b_page); pbh != bh;
429 pbh = pbh->b_this_page, key++);
434 __u64 nilfs_bmap_find_target_seq(const struct nilfs_bmap *bmap, __u64 key)
438 diff = key - bmap->b_last_allocated_key;
439 if ((nilfs_bmap_keydiff_abs(diff) < NILFS_INODE_BMAP_SIZE) &&
440 (bmap->b_last_allocated_ptr != NILFS_BMAP_INVALID_PTR) &&
441 (bmap->b_last_allocated_ptr + diff > 0))
442 return bmap->b_last_allocated_ptr + diff;
444 return NILFS_BMAP_INVALID_PTR;
447 static struct inode *nilfs_bmap_get_dat(const struct nilfs_bmap *bmap)
449 return nilfs_dat_inode(NILFS_I_NILFS(bmap->b_inode));
452 #define NILFS_BMAP_GROUP_DIV 8
453 __u64 nilfs_bmap_find_target_in_group(const struct nilfs_bmap *bmap)
455 struct inode *dat = nilfs_bmap_get_dat(bmap);
456 unsigned long entries_per_group = nilfs_palloc_entries_per_group(dat);
457 unsigned long group = bmap->b_inode->i_ino / entries_per_group;
459 return group * entries_per_group +
460 (bmap->b_inode->i_ino % NILFS_BMAP_GROUP_DIV) *
461 (entries_per_group / NILFS_BMAP_GROUP_DIV);
464 static int nilfs_bmap_prepare_alloc_v(struct nilfs_bmap *bmap,
465 union nilfs_bmap_ptr_req *req)
467 return nilfs_dat_prepare_alloc(nilfs_bmap_get_dat(bmap), &req->bpr_req);
470 static void nilfs_bmap_commit_alloc_v(struct nilfs_bmap *bmap,
471 union nilfs_bmap_ptr_req *req)
473 nilfs_dat_commit_alloc(nilfs_bmap_get_dat(bmap), &req->bpr_req);
476 static void nilfs_bmap_abort_alloc_v(struct nilfs_bmap *bmap,
477 union nilfs_bmap_ptr_req *req)
479 nilfs_dat_abort_alloc(nilfs_bmap_get_dat(bmap), &req->bpr_req);
482 int nilfs_bmap_start_v(struct nilfs_bmap *bmap, union nilfs_bmap_ptr_req *req,
485 struct inode *dat = nilfs_bmap_get_dat(bmap);
488 ret = nilfs_dat_prepare_start(dat, &req->bpr_req);
490 nilfs_dat_commit_start(dat, &req->bpr_req, blocknr);
494 static int nilfs_bmap_prepare_end_v(struct nilfs_bmap *bmap,
495 union nilfs_bmap_ptr_req *req)
497 return nilfs_dat_prepare_end(nilfs_bmap_get_dat(bmap), &req->bpr_req);
500 static void nilfs_bmap_commit_end_v(struct nilfs_bmap *bmap,
501 union nilfs_bmap_ptr_req *req)
503 nilfs_dat_commit_end(nilfs_bmap_get_dat(bmap), &req->bpr_req, 0);
506 static void nilfs_bmap_commit_end_vmdt(struct nilfs_bmap *bmap,
507 union nilfs_bmap_ptr_req *req)
509 nilfs_dat_commit_end(nilfs_bmap_get_dat(bmap), &req->bpr_req, 1);
512 static void nilfs_bmap_abort_end_v(struct nilfs_bmap *bmap,
513 union nilfs_bmap_ptr_req *req)
515 nilfs_dat_abort_end(nilfs_bmap_get_dat(bmap), &req->bpr_req);
518 int nilfs_bmap_move_v(const struct nilfs_bmap *bmap, __u64 vblocknr,
521 return nilfs_dat_move(nilfs_bmap_get_dat(bmap), vblocknr, blocknr);
524 int nilfs_bmap_mark_dirty(const struct nilfs_bmap *bmap, __u64 vblocknr)
526 return nilfs_dat_mark_dirty(nilfs_bmap_get_dat(bmap), vblocknr);
529 int nilfs_bmap_prepare_update(struct nilfs_bmap *bmap,
530 union nilfs_bmap_ptr_req *oldreq,
531 union nilfs_bmap_ptr_req *newreq)
535 ret = bmap->b_pops->bpop_prepare_end_ptr(bmap, oldreq);
538 ret = bmap->b_pops->bpop_prepare_alloc_ptr(bmap, newreq);
540 bmap->b_pops->bpop_abort_end_ptr(bmap, oldreq);
545 void nilfs_bmap_commit_update(struct nilfs_bmap *bmap,
546 union nilfs_bmap_ptr_req *oldreq,
547 union nilfs_bmap_ptr_req *newreq)
549 bmap->b_pops->bpop_commit_end_ptr(bmap, oldreq);
550 bmap->b_pops->bpop_commit_alloc_ptr(bmap, newreq);
553 void nilfs_bmap_abort_update(struct nilfs_bmap *bmap,
554 union nilfs_bmap_ptr_req *oldreq,
555 union nilfs_bmap_ptr_req *newreq)
557 bmap->b_pops->bpop_abort_end_ptr(bmap, oldreq);
558 bmap->b_pops->bpop_abort_alloc_ptr(bmap, newreq);
561 static int nilfs_bmap_translate_v(const struct nilfs_bmap *bmap, __u64 ptr,
567 ret = nilfs_dat_translate(nilfs_bmap_get_dat(bmap), ptr, &blocknr);
575 static int nilfs_bmap_prepare_alloc_p(struct nilfs_bmap *bmap,
576 union nilfs_bmap_ptr_req *req)
578 /* ignore target ptr */
579 req->bpr_ptr = bmap->b_last_allocated_ptr++;
583 static void nilfs_bmap_commit_alloc_p(struct nilfs_bmap *bmap,
584 union nilfs_bmap_ptr_req *req)
589 static void nilfs_bmap_abort_alloc_p(struct nilfs_bmap *bmap,
590 union nilfs_bmap_ptr_req *req)
592 bmap->b_last_allocated_ptr--;
595 static const struct nilfs_bmap_ptr_operations nilfs_bmap_ptr_ops_v = {
596 .bpop_prepare_alloc_ptr = nilfs_bmap_prepare_alloc_v,
597 .bpop_commit_alloc_ptr = nilfs_bmap_commit_alloc_v,
598 .bpop_abort_alloc_ptr = nilfs_bmap_abort_alloc_v,
599 .bpop_prepare_end_ptr = nilfs_bmap_prepare_end_v,
600 .bpop_commit_end_ptr = nilfs_bmap_commit_end_v,
601 .bpop_abort_end_ptr = nilfs_bmap_abort_end_v,
603 .bpop_translate = nilfs_bmap_translate_v,
606 static const struct nilfs_bmap_ptr_operations nilfs_bmap_ptr_ops_vmdt = {
607 .bpop_prepare_alloc_ptr = nilfs_bmap_prepare_alloc_v,
608 .bpop_commit_alloc_ptr = nilfs_bmap_commit_alloc_v,
609 .bpop_abort_alloc_ptr = nilfs_bmap_abort_alloc_v,
610 .bpop_prepare_end_ptr = nilfs_bmap_prepare_end_v,
611 .bpop_commit_end_ptr = nilfs_bmap_commit_end_vmdt,
612 .bpop_abort_end_ptr = nilfs_bmap_abort_end_v,
614 .bpop_translate = nilfs_bmap_translate_v,
617 static const struct nilfs_bmap_ptr_operations nilfs_bmap_ptr_ops_p = {
618 .bpop_prepare_alloc_ptr = nilfs_bmap_prepare_alloc_p,
619 .bpop_commit_alloc_ptr = nilfs_bmap_commit_alloc_p,
620 .bpop_abort_alloc_ptr = nilfs_bmap_abort_alloc_p,
621 .bpop_prepare_end_ptr = NULL,
622 .bpop_commit_end_ptr = NULL,
623 .bpop_abort_end_ptr = NULL,
625 .bpop_translate = NULL,
628 static const struct nilfs_bmap_ptr_operations nilfs_bmap_ptr_ops_gc = {
629 .bpop_prepare_alloc_ptr = NULL,
630 .bpop_commit_alloc_ptr = NULL,
631 .bpop_abort_alloc_ptr = NULL,
632 .bpop_prepare_end_ptr = NULL,
633 .bpop_commit_end_ptr = NULL,
634 .bpop_abort_end_ptr = NULL,
636 .bpop_translate = NULL,
639 static struct lock_class_key nilfs_bmap_dat_lock_key;
642 * nilfs_bmap_read - read a bmap from an inode
644 * @raw_inode: on-disk inode
646 * Description: nilfs_bmap_read() initializes the bmap @bmap.
648 * Return Value: On success, 0 is returned. On error, the following negative
649 * error code is returned.
651 * %-ENOMEM - Insufficient amount of memory available.
653 int nilfs_bmap_read(struct nilfs_bmap *bmap, struct nilfs_inode *raw_inode)
655 if (raw_inode == NULL)
656 memset(bmap->b_u.u_data, 0, NILFS_BMAP_SIZE);
658 memcpy(bmap->b_u.u_data, raw_inode->i_bmap, NILFS_BMAP_SIZE);
660 init_rwsem(&bmap->b_sem);
662 bmap->b_inode = &NILFS_BMAP_I(bmap)->vfs_inode;
663 switch (bmap->b_inode->i_ino) {
665 bmap->b_pops = &nilfs_bmap_ptr_ops_p;
666 bmap->b_last_allocated_key = 0; /* XXX: use macro */
667 bmap->b_last_allocated_ptr = NILFS_BMAP_NEW_PTR_INIT;
668 lockdep_set_class(&bmap->b_sem, &nilfs_bmap_dat_lock_key);
670 case NILFS_CPFILE_INO:
671 case NILFS_SUFILE_INO:
672 bmap->b_pops = &nilfs_bmap_ptr_ops_vmdt;
673 bmap->b_last_allocated_key = 0; /* XXX: use macro */
674 bmap->b_last_allocated_ptr = NILFS_BMAP_INVALID_PTR;
677 bmap->b_pops = &nilfs_bmap_ptr_ops_v;
678 bmap->b_last_allocated_key = 0; /* XXX: use macro */
679 bmap->b_last_allocated_ptr = NILFS_BMAP_INVALID_PTR;
683 return (bmap->b_u.u_flags & NILFS_BMAP_LARGE) ?
684 nilfs_btree_init(bmap,
685 NILFS_BMAP_LARGE_LOW,
686 NILFS_BMAP_LARGE_HIGH) :
687 nilfs_direct_init(bmap,
688 NILFS_BMAP_SMALL_LOW,
689 NILFS_BMAP_SMALL_HIGH);
693 * nilfs_bmap_write - write back a bmap to an inode
695 * @raw_inode: on-disk inode
697 * Description: nilfs_bmap_write() stores @bmap in @raw_inode.
699 void nilfs_bmap_write(struct nilfs_bmap *bmap, struct nilfs_inode *raw_inode)
701 down_write(&bmap->b_sem);
702 memcpy(raw_inode->i_bmap, bmap->b_u.u_data,
703 NILFS_INODE_BMAP_SIZE * sizeof(__le64));
704 if (bmap->b_inode->i_ino == NILFS_DAT_INO)
705 bmap->b_last_allocated_ptr = NILFS_BMAP_NEW_PTR_INIT;
707 up_write(&bmap->b_sem);
710 void nilfs_bmap_init_gc(struct nilfs_bmap *bmap)
712 memset(&bmap->b_u, 0, NILFS_BMAP_SIZE);
713 init_rwsem(&bmap->b_sem);
714 bmap->b_inode = &NILFS_BMAP_I(bmap)->vfs_inode;
715 bmap->b_pops = &nilfs_bmap_ptr_ops_gc;
716 bmap->b_last_allocated_key = 0;
717 bmap->b_last_allocated_ptr = NILFS_BMAP_INVALID_PTR;
719 nilfs_btree_init_gc(bmap);
722 void nilfs_bmap_init_gcdat(struct nilfs_bmap *gcbmap, struct nilfs_bmap *bmap)
724 memcpy(gcbmap, bmap, sizeof(union nilfs_bmap_union));
725 init_rwsem(&gcbmap->b_sem);
726 lockdep_set_class(&bmap->b_sem, &nilfs_bmap_dat_lock_key);
727 gcbmap->b_inode = &NILFS_BMAP_I(gcbmap)->vfs_inode;
730 void nilfs_bmap_commit_gcdat(struct nilfs_bmap *gcbmap, struct nilfs_bmap *bmap)
732 memcpy(bmap, gcbmap, sizeof(union nilfs_bmap_union));
733 init_rwsem(&bmap->b_sem);
734 lockdep_set_class(&bmap->b_sem, &nilfs_bmap_dat_lock_key);
735 bmap->b_inode = &NILFS_BMAP_I(bmap)->vfs_inode;