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 static struct inode *nilfs_bmap_get_dat(const struct nilfs_bmap *bmap)
36 return nilfs_dat_inode(NILFS_I_NILFS(bmap->b_inode));
39 int nilfs_bmap_lookup_at_level(struct nilfs_bmap *bmap, __u64 key, int level,
45 down_read(&bmap->b_sem);
46 ret = bmap->b_ops->bop_lookup(bmap, key, level, ptrp);
49 if (NILFS_BMAP_USE_VBN(bmap)) {
50 ret = nilfs_dat_translate(nilfs_bmap_get_dat(bmap), *ptrp,
57 up_read(&bmap->b_sem);
63 * nilfs_bmap_lookup - find a record
66 * @recp: pointer to record
68 * Description: nilfs_bmap_lookup() finds a record whose key matches @key in
71 * Return Value: On success, 0 is returned and the record associated with @key
72 * is stored in the place pointed by @recp. On error, one of the following
73 * negative error codes is returned.
77 * %-ENOMEM - Insufficient amount of memory available.
79 * %-ENOENT - A record associated with @key does not exist.
81 int nilfs_bmap_lookup(struct nilfs_bmap *bmap,
88 /* XXX: use macro for level 1 */
89 ret = nilfs_bmap_lookup_at_level(bmap, key, 1, &ptr);
95 static int nilfs_bmap_do_insert(struct nilfs_bmap *bmap, __u64 key, __u64 ptr)
97 __u64 keys[NILFS_BMAP_SMALL_HIGH + 1];
98 __u64 ptrs[NILFS_BMAP_SMALL_HIGH + 1];
101 if (bmap->b_ops->bop_check_insert != NULL) {
102 ret = bmap->b_ops->bop_check_insert(bmap, key);
104 n = bmap->b_ops->bop_gather_data(
105 bmap, keys, ptrs, NILFS_BMAP_SMALL_HIGH + 1);
108 ret = nilfs_btree_convert_and_insert(
109 bmap, key, ptr, keys, ptrs, n);
111 bmap->b_u.u_flags |= NILFS_BMAP_LARGE;
118 return bmap->b_ops->bop_insert(bmap, key, ptr);
122 * nilfs_bmap_insert - insert a new key-record pair into a bmap
127 * Description: nilfs_bmap_insert() inserts the new key-record pair specified
128 * by @key and @rec into @bmap.
130 * Return Value: On success, 0 is returned. On error, one of the following
131 * negative error codes is returned.
135 * %-ENOMEM - Insufficient amount of memory available.
137 * %-EEXIST - A record associated with @key already exist.
139 int nilfs_bmap_insert(struct nilfs_bmap *bmap,
145 down_write(&bmap->b_sem);
146 ret = nilfs_bmap_do_insert(bmap, key, rec);
147 up_write(&bmap->b_sem);
151 static int nilfs_bmap_do_delete(struct nilfs_bmap *bmap, __u64 key)
153 __u64 keys[NILFS_BMAP_LARGE_LOW + 1];
154 __u64 ptrs[NILFS_BMAP_LARGE_LOW + 1];
157 if (bmap->b_ops->bop_check_delete != NULL) {
158 ret = bmap->b_ops->bop_check_delete(bmap, key);
160 n = bmap->b_ops->bop_gather_data(
161 bmap, keys, ptrs, NILFS_BMAP_LARGE_LOW + 1);
164 ret = nilfs_direct_delete_and_convert(
165 bmap, key, keys, ptrs, n);
167 bmap->b_u.u_flags &= ~NILFS_BMAP_LARGE;
174 return bmap->b_ops->bop_delete(bmap, key);
177 int nilfs_bmap_last_key(struct nilfs_bmap *bmap, unsigned long *key)
182 down_read(&bmap->b_sem);
183 ret = bmap->b_ops->bop_last_key(bmap, &lastkey);
186 up_read(&bmap->b_sem);
191 * nilfs_bmap_delete - delete a key-record pair from a bmap
195 * Description: nilfs_bmap_delete() deletes the key-record pair specified by
198 * Return Value: On success, 0 is returned. On error, one of the following
199 * negative error codes is returned.
203 * %-ENOMEM - Insufficient amount of memory available.
205 * %-ENOENT - A record associated with @key does not exist.
207 int nilfs_bmap_delete(struct nilfs_bmap *bmap, unsigned long key)
211 down_write(&bmap->b_sem);
212 ret = nilfs_bmap_do_delete(bmap, key);
213 up_write(&bmap->b_sem);
217 static int nilfs_bmap_do_truncate(struct nilfs_bmap *bmap, unsigned long key)
222 ret = bmap->b_ops->bop_last_key(bmap, &lastkey);
229 while (key <= lastkey) {
230 ret = nilfs_bmap_do_delete(bmap, lastkey);
233 ret = bmap->b_ops->bop_last_key(bmap, &lastkey);
244 * nilfs_bmap_truncate - truncate a bmap to a specified key
248 * Description: nilfs_bmap_truncate() removes key-record pairs whose keys are
249 * greater than or equal to @key from @bmap.
251 * Return Value: On success, 0 is returned. On error, one of the following
252 * negative error codes is returned.
256 * %-ENOMEM - Insufficient amount of memory available.
258 int nilfs_bmap_truncate(struct nilfs_bmap *bmap, unsigned long key)
262 down_write(&bmap->b_sem);
263 ret = nilfs_bmap_do_truncate(bmap, key);
264 up_write(&bmap->b_sem);
269 * nilfs_bmap_clear - free resources a bmap holds
272 * Description: nilfs_bmap_clear() frees resources associated with @bmap.
274 void nilfs_bmap_clear(struct nilfs_bmap *bmap)
276 down_write(&bmap->b_sem);
277 if (bmap->b_ops->bop_clear != NULL)
278 bmap->b_ops->bop_clear(bmap);
279 up_write(&bmap->b_sem);
283 * nilfs_bmap_propagate - propagate dirty state
287 * Description: nilfs_bmap_propagate() marks the buffers that directly or
288 * indirectly refer to the block specified by @bh dirty.
290 * Return Value: On success, 0 is returned. On error, one of the following
291 * negative error codes is returned.
295 * %-ENOMEM - Insufficient amount of memory available.
297 int nilfs_bmap_propagate(struct nilfs_bmap *bmap, struct buffer_head *bh)
301 down_write(&bmap->b_sem);
302 ret = bmap->b_ops->bop_propagate(bmap, bh);
303 up_write(&bmap->b_sem);
308 * nilfs_bmap_lookup_dirty_buffers -
310 * @listp: pointer to buffer head list
312 void nilfs_bmap_lookup_dirty_buffers(struct nilfs_bmap *bmap,
313 struct list_head *listp)
315 if (bmap->b_ops->bop_lookup_dirty_buffers != NULL)
316 bmap->b_ops->bop_lookup_dirty_buffers(bmap, listp);
320 * nilfs_bmap_assign - assign a new block number to a block
322 * @bhp: pointer to buffer head
323 * @blocknr: block number
324 * @binfo: block information
326 * Description: nilfs_bmap_assign() assigns the block number @blocknr to the
327 * buffer specified by @bh.
329 * Return Value: On success, 0 is returned and the buffer head of a newly
330 * create buffer and the block information associated with the buffer are
331 * stored in the place pointed by @bh and @binfo, respectively. On error, one
332 * of the following negative error codes is returned.
336 * %-ENOMEM - Insufficient amount of memory available.
338 int nilfs_bmap_assign(struct nilfs_bmap *bmap,
339 struct buffer_head **bh,
340 unsigned long blocknr,
341 union nilfs_binfo *binfo)
345 down_write(&bmap->b_sem);
346 ret = bmap->b_ops->bop_assign(bmap, bh, blocknr, binfo);
347 up_write(&bmap->b_sem);
352 * nilfs_bmap_mark - mark block dirty
357 * Description: nilfs_bmap_mark() marks the block specified by @key and @level
360 * Return Value: On success, 0 is returned. On error, one of the following
361 * negative error codes is returned.
365 * %-ENOMEM - Insufficient amount of memory available.
367 int nilfs_bmap_mark(struct nilfs_bmap *bmap, __u64 key, int level)
371 if (bmap->b_ops->bop_mark == NULL)
374 down_write(&bmap->b_sem);
375 ret = bmap->b_ops->bop_mark(bmap, key, level);
376 up_write(&bmap->b_sem);
381 * nilfs_bmap_test_and_clear_dirty - test and clear a bmap dirty state
384 * Description: nilfs_test_and_clear() is the atomic operation to test and
385 * clear the dirty state of @bmap.
387 * Return Value: 1 is returned if @bmap is dirty, or 0 if clear.
389 int nilfs_bmap_test_and_clear_dirty(struct nilfs_bmap *bmap)
393 down_write(&bmap->b_sem);
394 ret = nilfs_bmap_dirty(bmap);
395 nilfs_bmap_clear_dirty(bmap);
396 up_write(&bmap->b_sem);
405 void nilfs_bmap_add_blocks(const struct nilfs_bmap *bmap, int n)
407 inode_add_bytes(bmap->b_inode, (1 << bmap->b_inode->i_blkbits) * n);
408 if (NILFS_MDT(bmap->b_inode))
409 nilfs_mdt_mark_dirty(bmap->b_inode);
411 mark_inode_dirty(bmap->b_inode);
414 void nilfs_bmap_sub_blocks(const struct nilfs_bmap *bmap, int n)
416 inode_sub_bytes(bmap->b_inode, (1 << bmap->b_inode->i_blkbits) * n);
417 if (NILFS_MDT(bmap->b_inode))
418 nilfs_mdt_mark_dirty(bmap->b_inode);
420 mark_inode_dirty(bmap->b_inode);
423 __u64 nilfs_bmap_data_get_key(const struct nilfs_bmap *bmap,
424 const struct buffer_head *bh)
426 struct buffer_head *pbh;
429 key = page_index(bh->b_page) << (PAGE_CACHE_SHIFT -
430 bmap->b_inode->i_blkbits);
431 for (pbh = page_buffers(bh->b_page); pbh != bh;
432 pbh = pbh->b_this_page, key++);
437 __u64 nilfs_bmap_find_target_seq(const struct nilfs_bmap *bmap, __u64 key)
441 diff = key - bmap->b_last_allocated_key;
442 if ((nilfs_bmap_keydiff_abs(diff) < NILFS_INODE_BMAP_SIZE) &&
443 (bmap->b_last_allocated_ptr != NILFS_BMAP_INVALID_PTR) &&
444 (bmap->b_last_allocated_ptr + diff > 0))
445 return bmap->b_last_allocated_ptr + diff;
447 return NILFS_BMAP_INVALID_PTR;
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 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 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 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 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 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,
502 bmap->b_ptr_type == NILFS_BMAP_PTR_VS);
505 void nilfs_bmap_abort_end_v(struct nilfs_bmap *bmap,
506 union nilfs_bmap_ptr_req *req)
508 nilfs_dat_abort_end(nilfs_bmap_get_dat(bmap), &req->bpr_req);
511 int nilfs_bmap_move_v(const struct nilfs_bmap *bmap, __u64 vblocknr,
514 return nilfs_dat_move(nilfs_bmap_get_dat(bmap), vblocknr, blocknr);
517 int nilfs_bmap_mark_dirty(const struct nilfs_bmap *bmap, __u64 vblocknr)
519 return nilfs_dat_mark_dirty(nilfs_bmap_get_dat(bmap), vblocknr);
522 int nilfs_bmap_prepare_update_v(struct nilfs_bmap *bmap,
523 union nilfs_bmap_ptr_req *oldreq,
524 union nilfs_bmap_ptr_req *newreq)
526 struct inode *dat = nilfs_bmap_get_dat(bmap);
529 ret = nilfs_dat_prepare_end(dat, &oldreq->bpr_req);
532 ret = nilfs_dat_prepare_alloc(dat, &newreq->bpr_req);
534 nilfs_dat_abort_end(dat, &oldreq->bpr_req);
539 void nilfs_bmap_commit_update_v(struct nilfs_bmap *bmap,
540 union nilfs_bmap_ptr_req *oldreq,
541 union nilfs_bmap_ptr_req *newreq)
543 struct inode *dat = nilfs_bmap_get_dat(bmap);
545 nilfs_dat_commit_end(dat, &oldreq->bpr_req,
546 bmap->b_ptr_type == NILFS_BMAP_PTR_VS);
547 nilfs_dat_commit_alloc(dat, &newreq->bpr_req);
550 void nilfs_bmap_abort_update_v(struct nilfs_bmap *bmap,
551 union nilfs_bmap_ptr_req *oldreq,
552 union nilfs_bmap_ptr_req *newreq)
554 struct inode *dat = nilfs_bmap_get_dat(bmap);
556 nilfs_dat_abort_end(dat, &oldreq->bpr_req);
557 nilfs_dat_abort_alloc(dat, &newreq->bpr_req);
560 static struct lock_class_key nilfs_bmap_dat_lock_key;
563 * nilfs_bmap_read - read a bmap from an inode
565 * @raw_inode: on-disk inode
567 * Description: nilfs_bmap_read() initializes the bmap @bmap.
569 * Return Value: On success, 0 is returned. On error, the following negative
570 * error code is returned.
572 * %-ENOMEM - Insufficient amount of memory available.
574 int nilfs_bmap_read(struct nilfs_bmap *bmap, struct nilfs_inode *raw_inode)
576 if (raw_inode == NULL)
577 memset(bmap->b_u.u_data, 0, NILFS_BMAP_SIZE);
579 memcpy(bmap->b_u.u_data, raw_inode->i_bmap, NILFS_BMAP_SIZE);
581 init_rwsem(&bmap->b_sem);
583 bmap->b_inode = &NILFS_BMAP_I(bmap)->vfs_inode;
584 switch (bmap->b_inode->i_ino) {
586 bmap->b_ptr_type = NILFS_BMAP_PTR_P;
587 bmap->b_last_allocated_key = 0;
588 bmap->b_last_allocated_ptr = NILFS_BMAP_NEW_PTR_INIT;
589 lockdep_set_class(&bmap->b_sem, &nilfs_bmap_dat_lock_key);
591 case NILFS_CPFILE_INO:
592 case NILFS_SUFILE_INO:
593 bmap->b_ptr_type = NILFS_BMAP_PTR_VS;
594 bmap->b_last_allocated_key = 0;
595 bmap->b_last_allocated_ptr = NILFS_BMAP_INVALID_PTR;
598 bmap->b_ptr_type = NILFS_BMAP_PTR_VM;
599 bmap->b_last_allocated_key = 0;
600 bmap->b_last_allocated_ptr = NILFS_BMAP_INVALID_PTR;
604 return (bmap->b_u.u_flags & NILFS_BMAP_LARGE) ?
605 nilfs_btree_init(bmap) : nilfs_direct_init(bmap);
609 * nilfs_bmap_write - write back a bmap to an inode
611 * @raw_inode: on-disk inode
613 * Description: nilfs_bmap_write() stores @bmap in @raw_inode.
615 void nilfs_bmap_write(struct nilfs_bmap *bmap, struct nilfs_inode *raw_inode)
617 down_write(&bmap->b_sem);
618 memcpy(raw_inode->i_bmap, bmap->b_u.u_data,
619 NILFS_INODE_BMAP_SIZE * sizeof(__le64));
620 if (bmap->b_inode->i_ino == NILFS_DAT_INO)
621 bmap->b_last_allocated_ptr = NILFS_BMAP_NEW_PTR_INIT;
623 up_write(&bmap->b_sem);
626 void nilfs_bmap_init_gc(struct nilfs_bmap *bmap)
628 memset(&bmap->b_u, 0, NILFS_BMAP_SIZE);
629 init_rwsem(&bmap->b_sem);
630 bmap->b_inode = &NILFS_BMAP_I(bmap)->vfs_inode;
631 bmap->b_ptr_type = NILFS_BMAP_PTR_U;
632 bmap->b_last_allocated_key = 0;
633 bmap->b_last_allocated_ptr = NILFS_BMAP_INVALID_PTR;
635 nilfs_btree_init_gc(bmap);
638 void nilfs_bmap_init_gcdat(struct nilfs_bmap *gcbmap, struct nilfs_bmap *bmap)
640 memcpy(gcbmap, bmap, sizeof(union nilfs_bmap_union));
641 init_rwsem(&gcbmap->b_sem);
642 lockdep_set_class(&bmap->b_sem, &nilfs_bmap_dat_lock_key);
643 gcbmap->b_inode = &NILFS_BMAP_I(gcbmap)->vfs_inode;
646 void nilfs_bmap_commit_gcdat(struct nilfs_bmap *gcbmap, struct nilfs_bmap *bmap)
648 memcpy(bmap, gcbmap, sizeof(union nilfs_bmap_union));
649 init_rwsem(&bmap->b_sem);
650 lockdep_set_class(&bmap->b_sem, &nilfs_bmap_dat_lock_key);
651 bmap->b_inode = &NILFS_BMAP_I(bmap)->vfs_inode;