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