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