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