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