xref: /openbmc/linux/fs/nilfs2/bmap.c (revision 4800cd83)
1 /*
2  * bmap.c - NILFS block mapping.
3  *
4  * Copyright (C) 2006-2008 Nippon Telegraph and Telephone Corporation.
5  *
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.
10  *
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.
15  *
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
19  *
20  * Written by Koji Sato <koji@osrg.net>.
21  */
22 
23 #include <linux/fs.h>
24 #include <linux/string.h>
25 #include <linux/errno.h>
26 #include "nilfs.h"
27 #include "bmap.h"
28 #include "sb.h"
29 #include "btree.h"
30 #include "direct.h"
31 #include "btnode.h"
32 #include "mdt.h"
33 #include "dat.h"
34 #include "alloc.h"
35 
36 struct inode *nilfs_bmap_get_dat(const struct nilfs_bmap *bmap)
37 {
38 	return NILFS_I_NILFS(bmap->b_inode)->ns_dat;
39 }
40 
41 static int nilfs_bmap_convert_error(struct nilfs_bmap *bmap,
42 				     const char *fname, int err)
43 {
44 	struct inode *inode = bmap->b_inode;
45 
46 	if (err == -EINVAL) {
47 		nilfs_error(inode->i_sb, fname,
48 			    "broken bmap (inode number=%lu)\n", inode->i_ino);
49 		err = -EIO;
50 	}
51 	return err;
52 }
53 
54 /**
55  * nilfs_bmap_lookup_at_level - find a data block or node block
56  * @bmap: bmap
57  * @key: key
58  * @level: level
59  * @ptrp: place to store the value associated to @key
60  *
61  * Description: nilfs_bmap_lookup_at_level() finds a record whose key
62  * matches @key in the block at @level of the bmap.
63  *
64  * Return Value: On success, 0 is returned and the record associated with @key
65  * is stored in the place pointed by @ptrp. On error, one of the following
66  * negative error codes is returned.
67  *
68  * %-EIO - I/O error.
69  *
70  * %-ENOMEM - Insufficient amount of memory available.
71  *
72  * %-ENOENT - A record associated with @key does not exist.
73  */
74 int nilfs_bmap_lookup_at_level(struct nilfs_bmap *bmap, __u64 key, int level,
75 			       __u64 *ptrp)
76 {
77 	sector_t blocknr;
78 	int ret;
79 
80 	down_read(&bmap->b_sem);
81 	ret = bmap->b_ops->bop_lookup(bmap, key, level, ptrp);
82 	if (ret < 0) {
83 		ret = nilfs_bmap_convert_error(bmap, __func__, ret);
84 		goto out;
85 	}
86 	if (NILFS_BMAP_USE_VBN(bmap)) {
87 		ret = nilfs_dat_translate(nilfs_bmap_get_dat(bmap), *ptrp,
88 					  &blocknr);
89 		if (!ret)
90 			*ptrp = blocknr;
91 	}
92 
93  out:
94 	up_read(&bmap->b_sem);
95 	return ret;
96 }
97 
98 int nilfs_bmap_lookup_contig(struct nilfs_bmap *bmap, __u64 key, __u64 *ptrp,
99 			     unsigned maxblocks)
100 {
101 	int ret;
102 
103 	down_read(&bmap->b_sem);
104 	ret = bmap->b_ops->bop_lookup_contig(bmap, key, ptrp, maxblocks);
105 	up_read(&bmap->b_sem);
106 
107 	return nilfs_bmap_convert_error(bmap, __func__, ret);
108 }
109 
110 static int nilfs_bmap_do_insert(struct nilfs_bmap *bmap, __u64 key, __u64 ptr)
111 {
112 	__u64 keys[NILFS_BMAP_SMALL_HIGH + 1];
113 	__u64 ptrs[NILFS_BMAP_SMALL_HIGH + 1];
114 	int ret, n;
115 
116 	if (bmap->b_ops->bop_check_insert != NULL) {
117 		ret = bmap->b_ops->bop_check_insert(bmap, key);
118 		if (ret > 0) {
119 			n = bmap->b_ops->bop_gather_data(
120 				bmap, keys, ptrs, NILFS_BMAP_SMALL_HIGH + 1);
121 			if (n < 0)
122 				return n;
123 			ret = nilfs_btree_convert_and_insert(
124 				bmap, key, ptr, keys, ptrs, n);
125 			if (ret == 0)
126 				bmap->b_u.u_flags |= NILFS_BMAP_LARGE;
127 
128 			return ret;
129 		} else if (ret < 0)
130 			return ret;
131 	}
132 
133 	return bmap->b_ops->bop_insert(bmap, key, ptr);
134 }
135 
136 /**
137  * nilfs_bmap_insert - insert a new key-record pair into a bmap
138  * @bmap: bmap
139  * @key: key
140  * @rec: record
141  *
142  * Description: nilfs_bmap_insert() inserts the new key-record pair specified
143  * by @key and @rec into @bmap.
144  *
145  * Return Value: On success, 0 is returned. On error, one of the following
146  * negative error codes is returned.
147  *
148  * %-EIO - I/O error.
149  *
150  * %-ENOMEM - Insufficient amount of memory available.
151  *
152  * %-EEXIST - A record associated with @key already exist.
153  */
154 int nilfs_bmap_insert(struct nilfs_bmap *bmap,
155 		      unsigned long key,
156 		      unsigned long rec)
157 {
158 	int ret;
159 
160 	down_write(&bmap->b_sem);
161 	ret = nilfs_bmap_do_insert(bmap, key, rec);
162 	up_write(&bmap->b_sem);
163 
164 	return nilfs_bmap_convert_error(bmap, __func__, ret);
165 }
166 
167 static int nilfs_bmap_do_delete(struct nilfs_bmap *bmap, __u64 key)
168 {
169 	__u64 keys[NILFS_BMAP_LARGE_LOW + 1];
170 	__u64 ptrs[NILFS_BMAP_LARGE_LOW + 1];
171 	int ret, n;
172 
173 	if (bmap->b_ops->bop_check_delete != NULL) {
174 		ret = bmap->b_ops->bop_check_delete(bmap, key);
175 		if (ret > 0) {
176 			n = bmap->b_ops->bop_gather_data(
177 				bmap, keys, ptrs, NILFS_BMAP_LARGE_LOW + 1);
178 			if (n < 0)
179 				return n;
180 			ret = nilfs_direct_delete_and_convert(
181 				bmap, key, keys, ptrs, n);
182 			if (ret == 0)
183 				bmap->b_u.u_flags &= ~NILFS_BMAP_LARGE;
184 
185 			return ret;
186 		} else if (ret < 0)
187 			return ret;
188 	}
189 
190 	return bmap->b_ops->bop_delete(bmap, key);
191 }
192 
193 int nilfs_bmap_last_key(struct nilfs_bmap *bmap, unsigned long *key)
194 {
195 	__u64 lastkey;
196 	int ret;
197 
198 	down_read(&bmap->b_sem);
199 	ret = bmap->b_ops->bop_last_key(bmap, &lastkey);
200 	up_read(&bmap->b_sem);
201 
202 	if (ret < 0)
203 		ret = nilfs_bmap_convert_error(bmap, __func__, ret);
204 	else
205 		*key = lastkey;
206 	return ret;
207 }
208 
209 /**
210  * nilfs_bmap_delete - delete a key-record pair from a bmap
211  * @bmap: bmap
212  * @key: key
213  *
214  * Description: nilfs_bmap_delete() deletes the key-record pair specified by
215  * @key from @bmap.
216  *
217  * Return Value: On success, 0 is returned. On error, one of the following
218  * negative error codes is returned.
219  *
220  * %-EIO - I/O error.
221  *
222  * %-ENOMEM - Insufficient amount of memory available.
223  *
224  * %-ENOENT - A record associated with @key does not exist.
225  */
226 int nilfs_bmap_delete(struct nilfs_bmap *bmap, unsigned long key)
227 {
228 	int ret;
229 
230 	down_write(&bmap->b_sem);
231 	ret = nilfs_bmap_do_delete(bmap, key);
232 	up_write(&bmap->b_sem);
233 
234 	return nilfs_bmap_convert_error(bmap, __func__, ret);
235 }
236 
237 static int nilfs_bmap_do_truncate(struct nilfs_bmap *bmap, unsigned long key)
238 {
239 	__u64 lastkey;
240 	int ret;
241 
242 	ret = bmap->b_ops->bop_last_key(bmap, &lastkey);
243 	if (ret < 0) {
244 		if (ret == -ENOENT)
245 			ret = 0;
246 		return ret;
247 	}
248 
249 	while (key <= lastkey) {
250 		ret = nilfs_bmap_do_delete(bmap, lastkey);
251 		if (ret < 0)
252 			return ret;
253 		ret = bmap->b_ops->bop_last_key(bmap, &lastkey);
254 		if (ret < 0) {
255 			if (ret == -ENOENT)
256 				ret = 0;
257 			return ret;
258 		}
259 	}
260 	return 0;
261 }
262 
263 /**
264  * nilfs_bmap_truncate - truncate a bmap to a specified key
265  * @bmap: bmap
266  * @key: key
267  *
268  * Description: nilfs_bmap_truncate() removes key-record pairs whose keys are
269  * greater than or equal to @key from @bmap.
270  *
271  * Return Value: On success, 0 is returned. On error, one of the following
272  * negative error codes is returned.
273  *
274  * %-EIO - I/O error.
275  *
276  * %-ENOMEM - Insufficient amount of memory available.
277  */
278 int nilfs_bmap_truncate(struct nilfs_bmap *bmap, unsigned long key)
279 {
280 	int ret;
281 
282 	down_write(&bmap->b_sem);
283 	ret = nilfs_bmap_do_truncate(bmap, key);
284 	up_write(&bmap->b_sem);
285 
286 	return nilfs_bmap_convert_error(bmap, __func__, ret);
287 }
288 
289 /**
290  * nilfs_bmap_clear - free resources a bmap holds
291  * @bmap: bmap
292  *
293  * Description: nilfs_bmap_clear() frees resources associated with @bmap.
294  */
295 void nilfs_bmap_clear(struct nilfs_bmap *bmap)
296 {
297 	down_write(&bmap->b_sem);
298 	if (bmap->b_ops->bop_clear != NULL)
299 		bmap->b_ops->bop_clear(bmap);
300 	up_write(&bmap->b_sem);
301 }
302 
303 /**
304  * nilfs_bmap_propagate - propagate dirty state
305  * @bmap: bmap
306  * @bh: buffer head
307  *
308  * Description: nilfs_bmap_propagate() marks the buffers that directly or
309  * indirectly refer to the block specified by @bh dirty.
310  *
311  * Return Value: On success, 0 is returned. On error, one of the following
312  * negative error codes is returned.
313  *
314  * %-EIO - I/O error.
315  *
316  * %-ENOMEM - Insufficient amount of memory available.
317  */
318 int nilfs_bmap_propagate(struct nilfs_bmap *bmap, struct buffer_head *bh)
319 {
320 	int ret;
321 
322 	down_write(&bmap->b_sem);
323 	ret = bmap->b_ops->bop_propagate(bmap, bh);
324 	up_write(&bmap->b_sem);
325 
326 	return nilfs_bmap_convert_error(bmap, __func__, ret);
327 }
328 
329 /**
330  * nilfs_bmap_lookup_dirty_buffers -
331  * @bmap: bmap
332  * @listp: pointer to buffer head list
333  */
334 void nilfs_bmap_lookup_dirty_buffers(struct nilfs_bmap *bmap,
335 				     struct list_head *listp)
336 {
337 	if (bmap->b_ops->bop_lookup_dirty_buffers != NULL)
338 		bmap->b_ops->bop_lookup_dirty_buffers(bmap, listp);
339 }
340 
341 /**
342  * nilfs_bmap_assign - assign a new block number to a block
343  * @bmap: bmap
344  * @bhp: pointer to buffer head
345  * @blocknr: block number
346  * @binfo: block information
347  *
348  * Description: nilfs_bmap_assign() assigns the block number @blocknr to the
349  * buffer specified by @bh.
350  *
351  * Return Value: On success, 0 is returned and the buffer head of a newly
352  * create buffer and the block information associated with the buffer are
353  * stored in the place pointed by @bh and @binfo, respectively. On error, one
354  * of the following negative error codes is returned.
355  *
356  * %-EIO - I/O error.
357  *
358  * %-ENOMEM - Insufficient amount of memory available.
359  */
360 int nilfs_bmap_assign(struct nilfs_bmap *bmap,
361 		      struct buffer_head **bh,
362 		      unsigned long blocknr,
363 		      union nilfs_binfo *binfo)
364 {
365 	int ret;
366 
367 	down_write(&bmap->b_sem);
368 	ret = bmap->b_ops->bop_assign(bmap, bh, blocknr, binfo);
369 	up_write(&bmap->b_sem);
370 
371 	return nilfs_bmap_convert_error(bmap, __func__, ret);
372 }
373 
374 /**
375  * nilfs_bmap_mark - mark block dirty
376  * @bmap: bmap
377  * @key: key
378  * @level: level
379  *
380  * Description: nilfs_bmap_mark() marks the block specified by @key and @level
381  * as dirty.
382  *
383  * Return Value: On success, 0 is returned. On error, one of the following
384  * negative error codes is returned.
385  *
386  * %-EIO - I/O error.
387  *
388  * %-ENOMEM - Insufficient amount of memory available.
389  */
390 int nilfs_bmap_mark(struct nilfs_bmap *bmap, __u64 key, int level)
391 {
392 	int ret;
393 
394 	if (bmap->b_ops->bop_mark == NULL)
395 		return 0;
396 
397 	down_write(&bmap->b_sem);
398 	ret = bmap->b_ops->bop_mark(bmap, key, level);
399 	up_write(&bmap->b_sem);
400 
401 	return nilfs_bmap_convert_error(bmap, __func__, ret);
402 }
403 
404 /**
405  * nilfs_bmap_test_and_clear_dirty - test and clear a bmap dirty state
406  * @bmap: bmap
407  *
408  * Description: nilfs_test_and_clear() is the atomic operation to test and
409  * clear the dirty state of @bmap.
410  *
411  * Return Value: 1 is returned if @bmap is dirty, or 0 if clear.
412  */
413 int nilfs_bmap_test_and_clear_dirty(struct nilfs_bmap *bmap)
414 {
415 	int ret;
416 
417 	down_write(&bmap->b_sem);
418 	ret = nilfs_bmap_dirty(bmap);
419 	nilfs_bmap_clear_dirty(bmap);
420 	up_write(&bmap->b_sem);
421 	return ret;
422 }
423 
424 
425 /*
426  * Internal use only
427  */
428 
429 void nilfs_bmap_add_blocks(const struct nilfs_bmap *bmap, int n)
430 {
431 	inode_add_bytes(bmap->b_inode, (1 << bmap->b_inode->i_blkbits) * n);
432 }
433 
434 void nilfs_bmap_sub_blocks(const struct nilfs_bmap *bmap, int n)
435 {
436 	inode_sub_bytes(bmap->b_inode, (1 << bmap->b_inode->i_blkbits) * n);
437 }
438 
439 __u64 nilfs_bmap_data_get_key(const struct nilfs_bmap *bmap,
440 			      const struct buffer_head *bh)
441 {
442 	struct buffer_head *pbh;
443 	__u64 key;
444 
445 	key = page_index(bh->b_page) << (PAGE_CACHE_SHIFT -
446 					 bmap->b_inode->i_blkbits);
447 	for (pbh = page_buffers(bh->b_page); pbh != bh; pbh = pbh->b_this_page)
448 		key++;
449 
450 	return key;
451 }
452 
453 __u64 nilfs_bmap_find_target_seq(const struct nilfs_bmap *bmap, __u64 key)
454 {
455 	__s64 diff;
456 
457 	diff = key - bmap->b_last_allocated_key;
458 	if ((nilfs_bmap_keydiff_abs(diff) < NILFS_INODE_BMAP_SIZE) &&
459 	    (bmap->b_last_allocated_ptr != NILFS_BMAP_INVALID_PTR) &&
460 	    (bmap->b_last_allocated_ptr + diff > 0))
461 		return bmap->b_last_allocated_ptr + diff;
462 	else
463 		return NILFS_BMAP_INVALID_PTR;
464 }
465 
466 #define NILFS_BMAP_GROUP_DIV	8
467 __u64 nilfs_bmap_find_target_in_group(const struct nilfs_bmap *bmap)
468 {
469 	struct inode *dat = nilfs_bmap_get_dat(bmap);
470 	unsigned long entries_per_group = nilfs_palloc_entries_per_group(dat);
471 	unsigned long group = bmap->b_inode->i_ino / entries_per_group;
472 
473 	return group * entries_per_group +
474 		(bmap->b_inode->i_ino % NILFS_BMAP_GROUP_DIV) *
475 		(entries_per_group / NILFS_BMAP_GROUP_DIV);
476 }
477 
478 static struct lock_class_key nilfs_bmap_dat_lock_key;
479 static struct lock_class_key nilfs_bmap_mdt_lock_key;
480 
481 /**
482  * nilfs_bmap_read - read a bmap from an inode
483  * @bmap: bmap
484  * @raw_inode: on-disk inode
485  *
486  * Description: nilfs_bmap_read() initializes the bmap @bmap.
487  *
488  * Return Value: On success, 0 is returned. On error, the following negative
489  * error code is returned.
490  *
491  * %-ENOMEM - Insufficient amount of memory available.
492  */
493 int nilfs_bmap_read(struct nilfs_bmap *bmap, struct nilfs_inode *raw_inode)
494 {
495 	if (raw_inode == NULL)
496 		memset(bmap->b_u.u_data, 0, NILFS_BMAP_SIZE);
497 	else
498 		memcpy(bmap->b_u.u_data, raw_inode->i_bmap, NILFS_BMAP_SIZE);
499 
500 	init_rwsem(&bmap->b_sem);
501 	bmap->b_state = 0;
502 	bmap->b_inode = &NILFS_BMAP_I(bmap)->vfs_inode;
503 	switch (bmap->b_inode->i_ino) {
504 	case NILFS_DAT_INO:
505 		bmap->b_ptr_type = NILFS_BMAP_PTR_P;
506 		bmap->b_last_allocated_key = 0;
507 		bmap->b_last_allocated_ptr = NILFS_BMAP_NEW_PTR_INIT;
508 		lockdep_set_class(&bmap->b_sem, &nilfs_bmap_dat_lock_key);
509 		break;
510 	case NILFS_CPFILE_INO:
511 	case NILFS_SUFILE_INO:
512 		bmap->b_ptr_type = NILFS_BMAP_PTR_VS;
513 		bmap->b_last_allocated_key = 0;
514 		bmap->b_last_allocated_ptr = NILFS_BMAP_INVALID_PTR;
515 		lockdep_set_class(&bmap->b_sem, &nilfs_bmap_mdt_lock_key);
516 		break;
517 	case NILFS_IFILE_INO:
518 		lockdep_set_class(&bmap->b_sem, &nilfs_bmap_mdt_lock_key);
519 		/* Fall through */
520 	default:
521 		bmap->b_ptr_type = NILFS_BMAP_PTR_VM;
522 		bmap->b_last_allocated_key = 0;
523 		bmap->b_last_allocated_ptr = NILFS_BMAP_INVALID_PTR;
524 		break;
525 	}
526 
527 	return (bmap->b_u.u_flags & NILFS_BMAP_LARGE) ?
528 		nilfs_btree_init(bmap) : nilfs_direct_init(bmap);
529 }
530 
531 /**
532  * nilfs_bmap_write - write back a bmap to an inode
533  * @bmap: bmap
534  * @raw_inode: on-disk inode
535  *
536  * Description: nilfs_bmap_write() stores @bmap in @raw_inode.
537  */
538 void nilfs_bmap_write(struct nilfs_bmap *bmap, struct nilfs_inode *raw_inode)
539 {
540 	down_write(&bmap->b_sem);
541 	memcpy(raw_inode->i_bmap, bmap->b_u.u_data,
542 	       NILFS_INODE_BMAP_SIZE * sizeof(__le64));
543 	if (bmap->b_inode->i_ino == NILFS_DAT_INO)
544 		bmap->b_last_allocated_ptr = NILFS_BMAP_NEW_PTR_INIT;
545 
546 	up_write(&bmap->b_sem);
547 }
548 
549 void nilfs_bmap_init_gc(struct nilfs_bmap *bmap)
550 {
551 	memset(&bmap->b_u, 0, NILFS_BMAP_SIZE);
552 	init_rwsem(&bmap->b_sem);
553 	bmap->b_inode = &NILFS_BMAP_I(bmap)->vfs_inode;
554 	bmap->b_ptr_type = NILFS_BMAP_PTR_U;
555 	bmap->b_last_allocated_key = 0;
556 	bmap->b_last_allocated_ptr = NILFS_BMAP_INVALID_PTR;
557 	bmap->b_state = 0;
558 	nilfs_btree_init_gc(bmap);
559 }
560 
561 void nilfs_bmap_save(const struct nilfs_bmap *bmap,
562 		     struct nilfs_bmap_store *store)
563 {
564 	memcpy(store->data, bmap->b_u.u_data, sizeof(store->data));
565 	store->last_allocated_key = bmap->b_last_allocated_key;
566 	store->last_allocated_ptr = bmap->b_last_allocated_ptr;
567 	store->state = bmap->b_state;
568 }
569 
570 void nilfs_bmap_restore(struct nilfs_bmap *bmap,
571 			const struct nilfs_bmap_store *store)
572 {
573 	memcpy(bmap->b_u.u_data, store->data, sizeof(store->data));
574 	bmap->b_last_allocated_key = store->last_allocated_key;
575 	bmap->b_last_allocated_ptr = store->last_allocated_ptr;
576 	bmap->b_state = store->state;
577 }
578