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