Root/
1 | /* |
2 | * This file is part of UBIFS. |
3 | * |
4 | * Copyright (C) 2006-2008 Nokia Corporation. |
5 | * |
6 | * This program is free software; you can redistribute it and/or modify it |
7 | * under the terms of the GNU General Public License version 2 as published by |
8 | * the Free Software Foundation. |
9 | * |
10 | * This program is distributed in the hope that it will be useful, but WITHOUT |
11 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
12 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for |
13 | * more details. |
14 | * |
15 | * You should have received a copy of the GNU General Public License along with |
16 | * this program; if not, write to the Free Software Foundation, Inc., 51 |
17 | * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA |
18 | * |
19 | * Author: Adrian Hunter |
20 | */ |
21 | |
22 | #include "ubifs.h" |
23 | |
24 | /* |
25 | * An orphan is an inode number whose inode node has been committed to the index |
26 | * with a link count of zero. That happens when an open file is deleted |
27 | * (unlinked) and then a commit is run. In the normal course of events the inode |
28 | * would be deleted when the file is closed. However in the case of an unclean |
29 | * unmount, orphans need to be accounted for. After an unclean unmount, the |
30 | * orphans' inodes must be deleted which means either scanning the entire index |
31 | * looking for them, or keeping a list on flash somewhere. This unit implements |
32 | * the latter approach. |
33 | * |
34 | * The orphan area is a fixed number of LEBs situated between the LPT area and |
35 | * the main area. The number of orphan area LEBs is specified when the file |
36 | * system is created. The minimum number is 1. The size of the orphan area |
37 | * should be so that it can hold the maximum number of orphans that are expected |
38 | * to ever exist at one time. |
39 | * |
40 | * The number of orphans that can fit in a LEB is: |
41 | * |
42 | * (c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64) |
43 | * |
44 | * For example: a 15872 byte LEB can fit 1980 orphans so 1 LEB may be enough. |
45 | * |
46 | * Orphans are accumulated in a rb-tree. When an inode's link count drops to |
47 | * zero, the inode number is added to the rb-tree. It is removed from the tree |
48 | * when the inode is deleted. Any new orphans that are in the orphan tree when |
49 | * the commit is run, are written to the orphan area in 1 or more orphan nodes. |
50 | * If the orphan area is full, it is consolidated to make space. There is |
51 | * always enough space because validation prevents the user from creating more |
52 | * than the maximum number of orphans allowed. |
53 | */ |
54 | |
55 | #ifdef CONFIG_UBIFS_FS_DEBUG |
56 | static int dbg_check_orphans(struct ubifs_info *c); |
57 | #else |
58 | #define dbg_check_orphans(c) 0 |
59 | #endif |
60 | |
61 | /** |
62 | * ubifs_add_orphan - add an orphan. |
63 | * @c: UBIFS file-system description object |
64 | * @inum: orphan inode number |
65 | * |
66 | * Add an orphan. This function is called when an inodes link count drops to |
67 | * zero. |
68 | */ |
69 | int ubifs_add_orphan(struct ubifs_info *c, ino_t inum) |
70 | { |
71 | struct ubifs_orphan *orphan, *o; |
72 | struct rb_node **p, *parent = NULL; |
73 | |
74 | orphan = kzalloc(sizeof(struct ubifs_orphan), GFP_NOFS); |
75 | if (!orphan) |
76 | return -ENOMEM; |
77 | orphan->inum = inum; |
78 | orphan->new = 1; |
79 | |
80 | spin_lock(&c->orphan_lock); |
81 | if (c->tot_orphans >= c->max_orphans) { |
82 | spin_unlock(&c->orphan_lock); |
83 | kfree(orphan); |
84 | return -ENFILE; |
85 | } |
86 | p = &c->orph_tree.rb_node; |
87 | while (*p) { |
88 | parent = *p; |
89 | o = rb_entry(parent, struct ubifs_orphan, rb); |
90 | if (inum < o->inum) |
91 | p = &(*p)->rb_left; |
92 | else if (inum > o->inum) |
93 | p = &(*p)->rb_right; |
94 | else { |
95 | dbg_err("orphaned twice"); |
96 | spin_unlock(&c->orphan_lock); |
97 | kfree(orphan); |
98 | return 0; |
99 | } |
100 | } |
101 | c->tot_orphans += 1; |
102 | c->new_orphans += 1; |
103 | rb_link_node(&orphan->rb, parent, p); |
104 | rb_insert_color(&orphan->rb, &c->orph_tree); |
105 | list_add_tail(&orphan->list, &c->orph_list); |
106 | list_add_tail(&orphan->new_list, &c->orph_new); |
107 | spin_unlock(&c->orphan_lock); |
108 | dbg_gen("ino %lu", (unsigned long)inum); |
109 | return 0; |
110 | } |
111 | |
112 | /** |
113 | * ubifs_delete_orphan - delete an orphan. |
114 | * @c: UBIFS file-system description object |
115 | * @inum: orphan inode number |
116 | * |
117 | * Delete an orphan. This function is called when an inode is deleted. |
118 | */ |
119 | void ubifs_delete_orphan(struct ubifs_info *c, ino_t inum) |
120 | { |
121 | struct ubifs_orphan *o; |
122 | struct rb_node *p; |
123 | |
124 | spin_lock(&c->orphan_lock); |
125 | p = c->orph_tree.rb_node; |
126 | while (p) { |
127 | o = rb_entry(p, struct ubifs_orphan, rb); |
128 | if (inum < o->inum) |
129 | p = p->rb_left; |
130 | else if (inum > o->inum) |
131 | p = p->rb_right; |
132 | else { |
133 | if (o->dnext) { |
134 | spin_unlock(&c->orphan_lock); |
135 | dbg_gen("deleted twice ino %lu", |
136 | (unsigned long)inum); |
137 | return; |
138 | } |
139 | if (o->cnext) { |
140 | o->dnext = c->orph_dnext; |
141 | c->orph_dnext = o; |
142 | spin_unlock(&c->orphan_lock); |
143 | dbg_gen("delete later ino %lu", |
144 | (unsigned long)inum); |
145 | return; |
146 | } |
147 | rb_erase(p, &c->orph_tree); |
148 | list_del(&o->list); |
149 | c->tot_orphans -= 1; |
150 | if (o->new) { |
151 | list_del(&o->new_list); |
152 | c->new_orphans -= 1; |
153 | } |
154 | spin_unlock(&c->orphan_lock); |
155 | kfree(o); |
156 | dbg_gen("inum %lu", (unsigned long)inum); |
157 | return; |
158 | } |
159 | } |
160 | spin_unlock(&c->orphan_lock); |
161 | dbg_err("missing orphan ino %lu", (unsigned long)inum); |
162 | dbg_dump_stack(); |
163 | } |
164 | |
165 | /** |
166 | * ubifs_orphan_start_commit - start commit of orphans. |
167 | * @c: UBIFS file-system description object |
168 | * |
169 | * Start commit of orphans. |
170 | */ |
171 | int ubifs_orphan_start_commit(struct ubifs_info *c) |
172 | { |
173 | struct ubifs_orphan *orphan, **last; |
174 | |
175 | spin_lock(&c->orphan_lock); |
176 | last = &c->orph_cnext; |
177 | list_for_each_entry(orphan, &c->orph_new, new_list) { |
178 | ubifs_assert(orphan->new); |
179 | orphan->new = 0; |
180 | *last = orphan; |
181 | last = &orphan->cnext; |
182 | } |
183 | *last = orphan->cnext; |
184 | c->cmt_orphans = c->new_orphans; |
185 | c->new_orphans = 0; |
186 | dbg_cmt("%d orphans to commit", c->cmt_orphans); |
187 | INIT_LIST_HEAD(&c->orph_new); |
188 | if (c->tot_orphans == 0) |
189 | c->no_orphs = 1; |
190 | else |
191 | c->no_orphs = 0; |
192 | spin_unlock(&c->orphan_lock); |
193 | return 0; |
194 | } |
195 | |
196 | /** |
197 | * avail_orphs - calculate available space. |
198 | * @c: UBIFS file-system description object |
199 | * |
200 | * This function returns the number of orphans that can be written in the |
201 | * available space. |
202 | */ |
203 | static int avail_orphs(struct ubifs_info *c) |
204 | { |
205 | int avail_lebs, avail, gap; |
206 | |
207 | avail_lebs = c->orph_lebs - (c->ohead_lnum - c->orph_first) - 1; |
208 | avail = avail_lebs * |
209 | ((c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64)); |
210 | gap = c->leb_size - c->ohead_offs; |
211 | if (gap >= UBIFS_ORPH_NODE_SZ + sizeof(__le64)) |
212 | avail += (gap - UBIFS_ORPH_NODE_SZ) / sizeof(__le64); |
213 | return avail; |
214 | } |
215 | |
216 | /** |
217 | * tot_avail_orphs - calculate total space. |
218 | * @c: UBIFS file-system description object |
219 | * |
220 | * This function returns the number of orphans that can be written in half |
221 | * the total space. That leaves half the space for adding new orphans. |
222 | */ |
223 | static int tot_avail_orphs(struct ubifs_info *c) |
224 | { |
225 | int avail_lebs, avail; |
226 | |
227 | avail_lebs = c->orph_lebs; |
228 | avail = avail_lebs * |
229 | ((c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64)); |
230 | return avail / 2; |
231 | } |
232 | |
233 | /** |
234 | * do_write_orph_node - write a node to the orphan head. |
235 | * @c: UBIFS file-system description object |
236 | * @len: length of node |
237 | * @atomic: write atomically |
238 | * |
239 | * This function writes a node to the orphan head from the orphan buffer. If |
240 | * %atomic is not zero, then the write is done atomically. On success, %0 is |
241 | * returned, otherwise a negative error code is returned. |
242 | */ |
243 | static int do_write_orph_node(struct ubifs_info *c, int len, int atomic) |
244 | { |
245 | int err = 0; |
246 | |
247 | if (atomic) { |
248 | ubifs_assert(c->ohead_offs == 0); |
249 | ubifs_prepare_node(c, c->orph_buf, len, 1); |
250 | len = ALIGN(len, c->min_io_size); |
251 | err = ubifs_leb_change(c, c->ohead_lnum, c->orph_buf, len, |
252 | UBI_SHORTTERM); |
253 | } else { |
254 | if (c->ohead_offs == 0) { |
255 | /* Ensure LEB has been unmapped */ |
256 | err = ubifs_leb_unmap(c, c->ohead_lnum); |
257 | if (err) |
258 | return err; |
259 | } |
260 | err = ubifs_write_node(c, c->orph_buf, len, c->ohead_lnum, |
261 | c->ohead_offs, UBI_SHORTTERM); |
262 | } |
263 | return err; |
264 | } |
265 | |
266 | /** |
267 | * write_orph_node - write an orphan node. |
268 | * @c: UBIFS file-system description object |
269 | * @atomic: write atomically |
270 | * |
271 | * This function builds an orphan node from the cnext list and writes it to the |
272 | * orphan head. On success, %0 is returned, otherwise a negative error code |
273 | * is returned. |
274 | */ |
275 | static int write_orph_node(struct ubifs_info *c, int atomic) |
276 | { |
277 | struct ubifs_orphan *orphan, *cnext; |
278 | struct ubifs_orph_node *orph; |
279 | int gap, err, len, cnt, i; |
280 | |
281 | ubifs_assert(c->cmt_orphans > 0); |
282 | gap = c->leb_size - c->ohead_offs; |
283 | if (gap < UBIFS_ORPH_NODE_SZ + sizeof(__le64)) { |
284 | c->ohead_lnum += 1; |
285 | c->ohead_offs = 0; |
286 | gap = c->leb_size; |
287 | if (c->ohead_lnum > c->orph_last) { |
288 | /* |
289 | * We limit the number of orphans so that this should |
290 | * never happen. |
291 | */ |
292 | ubifs_err("out of space in orphan area"); |
293 | return -EINVAL; |
294 | } |
295 | } |
296 | cnt = (gap - UBIFS_ORPH_NODE_SZ) / sizeof(__le64); |
297 | if (cnt > c->cmt_orphans) |
298 | cnt = c->cmt_orphans; |
299 | len = UBIFS_ORPH_NODE_SZ + cnt * sizeof(__le64); |
300 | ubifs_assert(c->orph_buf); |
301 | orph = c->orph_buf; |
302 | orph->ch.node_type = UBIFS_ORPH_NODE; |
303 | spin_lock(&c->orphan_lock); |
304 | cnext = c->orph_cnext; |
305 | for (i = 0; i < cnt; i++) { |
306 | orphan = cnext; |
307 | orph->inos[i] = cpu_to_le64(orphan->inum); |
308 | cnext = orphan->cnext; |
309 | orphan->cnext = NULL; |
310 | } |
311 | c->orph_cnext = cnext; |
312 | c->cmt_orphans -= cnt; |
313 | spin_unlock(&c->orphan_lock); |
314 | if (c->cmt_orphans) |
315 | orph->cmt_no = cpu_to_le64(c->cmt_no); |
316 | else |
317 | /* Mark the last node of the commit */ |
318 | orph->cmt_no = cpu_to_le64((c->cmt_no) | (1ULL << 63)); |
319 | ubifs_assert(c->ohead_offs + len <= c->leb_size); |
320 | ubifs_assert(c->ohead_lnum >= c->orph_first); |
321 | ubifs_assert(c->ohead_lnum <= c->orph_last); |
322 | err = do_write_orph_node(c, len, atomic); |
323 | c->ohead_offs += ALIGN(len, c->min_io_size); |
324 | c->ohead_offs = ALIGN(c->ohead_offs, 8); |
325 | return err; |
326 | } |
327 | |
328 | /** |
329 | * write_orph_nodes - write orphan nodes until there are no more to commit. |
330 | * @c: UBIFS file-system description object |
331 | * @atomic: write atomically |
332 | * |
333 | * This function writes orphan nodes for all the orphans to commit. On success, |
334 | * %0 is returned, otherwise a negative error code is returned. |
335 | */ |
336 | static int write_orph_nodes(struct ubifs_info *c, int atomic) |
337 | { |
338 | int err; |
339 | |
340 | while (c->cmt_orphans > 0) { |
341 | err = write_orph_node(c, atomic); |
342 | if (err) |
343 | return err; |
344 | } |
345 | if (atomic) { |
346 | int lnum; |
347 | |
348 | /* Unmap any unused LEBs after consolidation */ |
349 | lnum = c->ohead_lnum + 1; |
350 | for (lnum = c->ohead_lnum + 1; lnum <= c->orph_last; lnum++) { |
351 | err = ubifs_leb_unmap(c, lnum); |
352 | if (err) |
353 | return err; |
354 | } |
355 | } |
356 | return 0; |
357 | } |
358 | |
359 | /** |
360 | * consolidate - consolidate the orphan area. |
361 | * @c: UBIFS file-system description object |
362 | * |
363 | * This function enables consolidation by putting all the orphans into the list |
364 | * to commit. The list is in the order that the orphans were added, and the |
365 | * LEBs are written atomically in order, so at no time can orphans be lost by |
366 | * an unclean unmount. |
367 | * |
368 | * This function returns %0 on success and a negative error code on failure. |
369 | */ |
370 | static int consolidate(struct ubifs_info *c) |
371 | { |
372 | int tot_avail = tot_avail_orphs(c), err = 0; |
373 | |
374 | spin_lock(&c->orphan_lock); |
375 | dbg_cmt("there is space for %d orphans and there are %d", |
376 | tot_avail, c->tot_orphans); |
377 | if (c->tot_orphans - c->new_orphans <= tot_avail) { |
378 | struct ubifs_orphan *orphan, **last; |
379 | int cnt = 0; |
380 | |
381 | /* Change the cnext list to include all non-new orphans */ |
382 | last = &c->orph_cnext; |
383 | list_for_each_entry(orphan, &c->orph_list, list) { |
384 | if (orphan->new) |
385 | continue; |
386 | *last = orphan; |
387 | last = &orphan->cnext; |
388 | cnt += 1; |
389 | } |
390 | *last = orphan->cnext; |
391 | ubifs_assert(cnt == c->tot_orphans - c->new_orphans); |
392 | c->cmt_orphans = cnt; |
393 | c->ohead_lnum = c->orph_first; |
394 | c->ohead_offs = 0; |
395 | } else { |
396 | /* |
397 | * We limit the number of orphans so that this should |
398 | * never happen. |
399 | */ |
400 | ubifs_err("out of space in orphan area"); |
401 | err = -EINVAL; |
402 | } |
403 | spin_unlock(&c->orphan_lock); |
404 | return err; |
405 | } |
406 | |
407 | /** |
408 | * commit_orphans - commit orphans. |
409 | * @c: UBIFS file-system description object |
410 | * |
411 | * This function commits orphans to flash. On success, %0 is returned, |
412 | * otherwise a negative error code is returned. |
413 | */ |
414 | static int commit_orphans(struct ubifs_info *c) |
415 | { |
416 | int avail, atomic = 0, err; |
417 | |
418 | ubifs_assert(c->cmt_orphans > 0); |
419 | avail = avail_orphs(c); |
420 | if (avail < c->cmt_orphans) { |
421 | /* Not enough space to write new orphans, so consolidate */ |
422 | err = consolidate(c); |
423 | if (err) |
424 | return err; |
425 | atomic = 1; |
426 | } |
427 | err = write_orph_nodes(c, atomic); |
428 | return err; |
429 | } |
430 | |
431 | /** |
432 | * erase_deleted - erase the orphans marked for deletion. |
433 | * @c: UBIFS file-system description object |
434 | * |
435 | * During commit, the orphans being committed cannot be deleted, so they are |
436 | * marked for deletion and deleted by this function. Also, the recovery |
437 | * adds killed orphans to the deletion list, and therefore they are deleted |
438 | * here too. |
439 | */ |
440 | static void erase_deleted(struct ubifs_info *c) |
441 | { |
442 | struct ubifs_orphan *orphan, *dnext; |
443 | |
444 | spin_lock(&c->orphan_lock); |
445 | dnext = c->orph_dnext; |
446 | while (dnext) { |
447 | orphan = dnext; |
448 | dnext = orphan->dnext; |
449 | ubifs_assert(!orphan->new); |
450 | rb_erase(&orphan->rb, &c->orph_tree); |
451 | list_del(&orphan->list); |
452 | c->tot_orphans -= 1; |
453 | dbg_gen("deleting orphan ino %lu", (unsigned long)orphan->inum); |
454 | kfree(orphan); |
455 | } |
456 | c->orph_dnext = NULL; |
457 | spin_unlock(&c->orphan_lock); |
458 | } |
459 | |
460 | /** |
461 | * ubifs_orphan_end_commit - end commit of orphans. |
462 | * @c: UBIFS file-system description object |
463 | * |
464 | * End commit of orphans. |
465 | */ |
466 | int ubifs_orphan_end_commit(struct ubifs_info *c) |
467 | { |
468 | int err; |
469 | |
470 | if (c->cmt_orphans != 0) { |
471 | err = commit_orphans(c); |
472 | if (err) |
473 | return err; |
474 | } |
475 | erase_deleted(c); |
476 | err = dbg_check_orphans(c); |
477 | return err; |
478 | } |
479 | |
480 | /** |
481 | * ubifs_clear_orphans - erase all LEBs used for orphans. |
482 | * @c: UBIFS file-system description object |
483 | * |
484 | * If recovery is not required, then the orphans from the previous session |
485 | * are not needed. This function locates the LEBs used to record |
486 | * orphans, and un-maps them. |
487 | */ |
488 | int ubifs_clear_orphans(struct ubifs_info *c) |
489 | { |
490 | int lnum, err; |
491 | |
492 | for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) { |
493 | err = ubifs_leb_unmap(c, lnum); |
494 | if (err) |
495 | return err; |
496 | } |
497 | c->ohead_lnum = c->orph_first; |
498 | c->ohead_offs = 0; |
499 | return 0; |
500 | } |
501 | |
502 | /** |
503 | * insert_dead_orphan - insert an orphan. |
504 | * @c: UBIFS file-system description object |
505 | * @inum: orphan inode number |
506 | * |
507 | * This function is a helper to the 'do_kill_orphans()' function. The orphan |
508 | * must be kept until the next commit, so it is added to the rb-tree and the |
509 | * deletion list. |
510 | */ |
511 | static int insert_dead_orphan(struct ubifs_info *c, ino_t inum) |
512 | { |
513 | struct ubifs_orphan *orphan, *o; |
514 | struct rb_node **p, *parent = NULL; |
515 | |
516 | orphan = kzalloc(sizeof(struct ubifs_orphan), GFP_KERNEL); |
517 | if (!orphan) |
518 | return -ENOMEM; |
519 | orphan->inum = inum; |
520 | |
521 | p = &c->orph_tree.rb_node; |
522 | while (*p) { |
523 | parent = *p; |
524 | o = rb_entry(parent, struct ubifs_orphan, rb); |
525 | if (inum < o->inum) |
526 | p = &(*p)->rb_left; |
527 | else if (inum > o->inum) |
528 | p = &(*p)->rb_right; |
529 | else { |
530 | /* Already added - no problem */ |
531 | kfree(orphan); |
532 | return 0; |
533 | } |
534 | } |
535 | c->tot_orphans += 1; |
536 | rb_link_node(&orphan->rb, parent, p); |
537 | rb_insert_color(&orphan->rb, &c->orph_tree); |
538 | list_add_tail(&orphan->list, &c->orph_list); |
539 | orphan->dnext = c->orph_dnext; |
540 | c->orph_dnext = orphan; |
541 | dbg_mnt("ino %lu, new %d, tot %d", (unsigned long)inum, |
542 | c->new_orphans, c->tot_orphans); |
543 | return 0; |
544 | } |
545 | |
546 | /** |
547 | * do_kill_orphans - remove orphan inodes from the index. |
548 | * @c: UBIFS file-system description object |
549 | * @sleb: scanned LEB |
550 | * @last_cmt_no: cmt_no of last orphan node read is passed and returned here |
551 | * @outofdate: whether the LEB is out of date is returned here |
552 | * @last_flagged: whether the end orphan node is encountered |
553 | * |
554 | * This function is a helper to the 'kill_orphans()' function. It goes through |
555 | * every orphan node in a LEB and for every inode number recorded, removes |
556 | * all keys for that inode from the TNC. |
557 | */ |
558 | static int do_kill_orphans(struct ubifs_info *c, struct ubifs_scan_leb *sleb, |
559 | unsigned long long *last_cmt_no, int *outofdate, |
560 | int *last_flagged) |
561 | { |
562 | struct ubifs_scan_node *snod; |
563 | struct ubifs_orph_node *orph; |
564 | unsigned long long cmt_no; |
565 | ino_t inum; |
566 | int i, n, err, first = 1; |
567 | |
568 | list_for_each_entry(snod, &sleb->nodes, list) { |
569 | if (snod->type != UBIFS_ORPH_NODE) { |
570 | ubifs_err("invalid node type %d in orphan area at " |
571 | "%d:%d", snod->type, sleb->lnum, snod->offs); |
572 | dbg_dump_node(c, snod->node); |
573 | return -EINVAL; |
574 | } |
575 | |
576 | orph = snod->node; |
577 | |
578 | /* Check commit number */ |
579 | cmt_no = le64_to_cpu(orph->cmt_no) & LLONG_MAX; |
580 | /* |
581 | * The commit number on the master node may be less, because |
582 | * of a failed commit. If there are several failed commits in a |
583 | * row, the commit number written on orphan nodes will continue |
584 | * to increase (because the commit number is adjusted here) even |
585 | * though the commit number on the master node stays the same |
586 | * because the master node has not been re-written. |
587 | */ |
588 | if (cmt_no > c->cmt_no) |
589 | c->cmt_no = cmt_no; |
590 | if (cmt_no < *last_cmt_no && *last_flagged) { |
591 | /* |
592 | * The last orphan node had a higher commit number and |
593 | * was flagged as the last written for that commit |
594 | * number. That makes this orphan node, out of date. |
595 | */ |
596 | if (!first) { |
597 | ubifs_err("out of order commit number %llu in " |
598 | "orphan node at %d:%d", |
599 | cmt_no, sleb->lnum, snod->offs); |
600 | dbg_dump_node(c, snod->node); |
601 | return -EINVAL; |
602 | } |
603 | dbg_rcvry("out of date LEB %d", sleb->lnum); |
604 | *outofdate = 1; |
605 | return 0; |
606 | } |
607 | |
608 | if (first) |
609 | first = 0; |
610 | |
611 | n = (le32_to_cpu(orph->ch.len) - UBIFS_ORPH_NODE_SZ) >> 3; |
612 | for (i = 0; i < n; i++) { |
613 | inum = le64_to_cpu(orph->inos[i]); |
614 | dbg_rcvry("deleting orphaned inode %lu", |
615 | (unsigned long)inum); |
616 | err = ubifs_tnc_remove_ino(c, inum); |
617 | if (err) |
618 | return err; |
619 | err = insert_dead_orphan(c, inum); |
620 | if (err) |
621 | return err; |
622 | } |
623 | |
624 | *last_cmt_no = cmt_no; |
625 | if (le64_to_cpu(orph->cmt_no) & (1ULL << 63)) { |
626 | dbg_rcvry("last orph node for commit %llu at %d:%d", |
627 | cmt_no, sleb->lnum, snod->offs); |
628 | *last_flagged = 1; |
629 | } else |
630 | *last_flagged = 0; |
631 | } |
632 | |
633 | return 0; |
634 | } |
635 | |
636 | /** |
637 | * kill_orphans - remove all orphan inodes from the index. |
638 | * @c: UBIFS file-system description object |
639 | * |
640 | * If recovery is required, then orphan inodes recorded during the previous |
641 | * session (which ended with an unclean unmount) must be deleted from the index. |
642 | * This is done by updating the TNC, but since the index is not updated until |
643 | * the next commit, the LEBs where the orphan information is recorded are not |
644 | * erased until the next commit. |
645 | */ |
646 | static int kill_orphans(struct ubifs_info *c) |
647 | { |
648 | unsigned long long last_cmt_no = 0; |
649 | int lnum, err = 0, outofdate = 0, last_flagged = 0; |
650 | |
651 | c->ohead_lnum = c->orph_first; |
652 | c->ohead_offs = 0; |
653 | /* Check no-orphans flag and skip this if no orphans */ |
654 | if (c->no_orphs) { |
655 | dbg_rcvry("no orphans"); |
656 | return 0; |
657 | } |
658 | /* |
659 | * Orph nodes always start at c->orph_first and are written to each |
660 | * successive LEB in turn. Generally unused LEBs will have been unmapped |
661 | * but may contain out of date orphan nodes if the unmap didn't go |
662 | * through. In addition, the last orphan node written for each commit is |
663 | * marked (top bit of orph->cmt_no is set to 1). It is possible that |
664 | * there are orphan nodes from the next commit (i.e. the commit did not |
665 | * complete successfully). In that case, no orphans will have been lost |
666 | * due to the way that orphans are written, and any orphans added will |
667 | * be valid orphans anyway and so can be deleted. |
668 | */ |
669 | for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) { |
670 | struct ubifs_scan_leb *sleb; |
671 | |
672 | dbg_rcvry("LEB %d", lnum); |
673 | sleb = ubifs_scan(c, lnum, 0, c->sbuf); |
674 | if (IS_ERR(sleb)) { |
675 | sleb = ubifs_recover_leb(c, lnum, 0, c->sbuf, 0); |
676 | if (IS_ERR(sleb)) { |
677 | err = PTR_ERR(sleb); |
678 | break; |
679 | } |
680 | } |
681 | err = do_kill_orphans(c, sleb, &last_cmt_no, &outofdate, |
682 | &last_flagged); |
683 | if (err || outofdate) { |
684 | ubifs_scan_destroy(sleb); |
685 | break; |
686 | } |
687 | if (sleb->endpt) { |
688 | c->ohead_lnum = lnum; |
689 | c->ohead_offs = sleb->endpt; |
690 | } |
691 | ubifs_scan_destroy(sleb); |
692 | } |
693 | return err; |
694 | } |
695 | |
696 | /** |
697 | * ubifs_mount_orphans - delete orphan inodes and erase LEBs that recorded them. |
698 | * @c: UBIFS file-system description object |
699 | * @unclean: indicates recovery from unclean unmount |
700 | * @read_only: indicates read only mount |
701 | * |
702 | * This function is called when mounting to erase orphans from the previous |
703 | * session. If UBIFS was not unmounted cleanly, then the inodes recorded as |
704 | * orphans are deleted. |
705 | */ |
706 | int ubifs_mount_orphans(struct ubifs_info *c, int unclean, int read_only) |
707 | { |
708 | int err = 0; |
709 | |
710 | c->max_orphans = tot_avail_orphs(c); |
711 | |
712 | if (!read_only) { |
713 | c->orph_buf = vmalloc(c->leb_size); |
714 | if (!c->orph_buf) |
715 | return -ENOMEM; |
716 | } |
717 | |
718 | if (unclean) |
719 | err = kill_orphans(c); |
720 | else if (!read_only) |
721 | err = ubifs_clear_orphans(c); |
722 | |
723 | return err; |
724 | } |
725 | |
726 | #ifdef CONFIG_UBIFS_FS_DEBUG |
727 | |
728 | struct check_orphan { |
729 | struct rb_node rb; |
730 | ino_t inum; |
731 | }; |
732 | |
733 | struct check_info { |
734 | unsigned long last_ino; |
735 | unsigned long tot_inos; |
736 | unsigned long missing; |
737 | unsigned long long leaf_cnt; |
738 | struct ubifs_ino_node *node; |
739 | struct rb_root root; |
740 | }; |
741 | |
742 | static int dbg_find_orphan(struct ubifs_info *c, ino_t inum) |
743 | { |
744 | struct ubifs_orphan *o; |
745 | struct rb_node *p; |
746 | |
747 | spin_lock(&c->orphan_lock); |
748 | p = c->orph_tree.rb_node; |
749 | while (p) { |
750 | o = rb_entry(p, struct ubifs_orphan, rb); |
751 | if (inum < o->inum) |
752 | p = p->rb_left; |
753 | else if (inum > o->inum) |
754 | p = p->rb_right; |
755 | else { |
756 | spin_unlock(&c->orphan_lock); |
757 | return 1; |
758 | } |
759 | } |
760 | spin_unlock(&c->orphan_lock); |
761 | return 0; |
762 | } |
763 | |
764 | static int dbg_ins_check_orphan(struct rb_root *root, ino_t inum) |
765 | { |
766 | struct check_orphan *orphan, *o; |
767 | struct rb_node **p, *parent = NULL; |
768 | |
769 | orphan = kzalloc(sizeof(struct check_orphan), GFP_NOFS); |
770 | if (!orphan) |
771 | return -ENOMEM; |
772 | orphan->inum = inum; |
773 | |
774 | p = &root->rb_node; |
775 | while (*p) { |
776 | parent = *p; |
777 | o = rb_entry(parent, struct check_orphan, rb); |
778 | if (inum < o->inum) |
779 | p = &(*p)->rb_left; |
780 | else if (inum > o->inum) |
781 | p = &(*p)->rb_right; |
782 | else { |
783 | kfree(orphan); |
784 | return 0; |
785 | } |
786 | } |
787 | rb_link_node(&orphan->rb, parent, p); |
788 | rb_insert_color(&orphan->rb, root); |
789 | return 0; |
790 | } |
791 | |
792 | static int dbg_find_check_orphan(struct rb_root *root, ino_t inum) |
793 | { |
794 | struct check_orphan *o; |
795 | struct rb_node *p; |
796 | |
797 | p = root->rb_node; |
798 | while (p) { |
799 | o = rb_entry(p, struct check_orphan, rb); |
800 | if (inum < o->inum) |
801 | p = p->rb_left; |
802 | else if (inum > o->inum) |
803 | p = p->rb_right; |
804 | else |
805 | return 1; |
806 | } |
807 | return 0; |
808 | } |
809 | |
810 | static void dbg_free_check_tree(struct rb_root *root) |
811 | { |
812 | struct rb_node *this = root->rb_node; |
813 | struct check_orphan *o; |
814 | |
815 | while (this) { |
816 | if (this->rb_left) { |
817 | this = this->rb_left; |
818 | continue; |
819 | } else if (this->rb_right) { |
820 | this = this->rb_right; |
821 | continue; |
822 | } |
823 | o = rb_entry(this, struct check_orphan, rb); |
824 | this = rb_parent(this); |
825 | if (this) { |
826 | if (this->rb_left == &o->rb) |
827 | this->rb_left = NULL; |
828 | else |
829 | this->rb_right = NULL; |
830 | } |
831 | kfree(o); |
832 | } |
833 | } |
834 | |
835 | static int dbg_orphan_check(struct ubifs_info *c, struct ubifs_zbranch *zbr, |
836 | void *priv) |
837 | { |
838 | struct check_info *ci = priv; |
839 | ino_t inum; |
840 | int err; |
841 | |
842 | inum = key_inum(c, &zbr->key); |
843 | if (inum != ci->last_ino) { |
844 | /* Lowest node type is the inode node, so it comes first */ |
845 | if (key_type(c, &zbr->key) != UBIFS_INO_KEY) |
846 | ubifs_err("found orphan node ino %lu, type %d", |
847 | (unsigned long)inum, key_type(c, &zbr->key)); |
848 | ci->last_ino = inum; |
849 | ci->tot_inos += 1; |
850 | err = ubifs_tnc_read_node(c, zbr, ci->node); |
851 | if (err) { |
852 | ubifs_err("node read failed, error %d", err); |
853 | return err; |
854 | } |
855 | if (ci->node->nlink == 0) |
856 | /* Must be recorded as an orphan */ |
857 | if (!dbg_find_check_orphan(&ci->root, inum) && |
858 | !dbg_find_orphan(c, inum)) { |
859 | ubifs_err("missing orphan, ino %lu", |
860 | (unsigned long)inum); |
861 | ci->missing += 1; |
862 | } |
863 | } |
864 | ci->leaf_cnt += 1; |
865 | return 0; |
866 | } |
867 | |
868 | static int dbg_read_orphans(struct check_info *ci, struct ubifs_scan_leb *sleb) |
869 | { |
870 | struct ubifs_scan_node *snod; |
871 | struct ubifs_orph_node *orph; |
872 | ino_t inum; |
873 | int i, n, err; |
874 | |
875 | list_for_each_entry(snod, &sleb->nodes, list) { |
876 | cond_resched(); |
877 | if (snod->type != UBIFS_ORPH_NODE) |
878 | continue; |
879 | orph = snod->node; |
880 | n = (le32_to_cpu(orph->ch.len) - UBIFS_ORPH_NODE_SZ) >> 3; |
881 | for (i = 0; i < n; i++) { |
882 | inum = le64_to_cpu(orph->inos[i]); |
883 | err = dbg_ins_check_orphan(&ci->root, inum); |
884 | if (err) |
885 | return err; |
886 | } |
887 | } |
888 | return 0; |
889 | } |
890 | |
891 | static int dbg_scan_orphans(struct ubifs_info *c, struct check_info *ci) |
892 | { |
893 | int lnum, err = 0; |
894 | |
895 | /* Check no-orphans flag and skip this if no orphans */ |
896 | if (c->no_orphs) |
897 | return 0; |
898 | |
899 | for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) { |
900 | struct ubifs_scan_leb *sleb; |
901 | |
902 | sleb = ubifs_scan(c, lnum, 0, c->dbg->buf); |
903 | if (IS_ERR(sleb)) { |
904 | err = PTR_ERR(sleb); |
905 | break; |
906 | } |
907 | |
908 | err = dbg_read_orphans(ci, sleb); |
909 | ubifs_scan_destroy(sleb); |
910 | if (err) |
911 | break; |
912 | } |
913 | |
914 | return err; |
915 | } |
916 | |
917 | static int dbg_check_orphans(struct ubifs_info *c) |
918 | { |
919 | struct check_info ci; |
920 | int err; |
921 | |
922 | if (!(ubifs_chk_flags & UBIFS_CHK_ORPH)) |
923 | return 0; |
924 | |
925 | ci.last_ino = 0; |
926 | ci.tot_inos = 0; |
927 | ci.missing = 0; |
928 | ci.leaf_cnt = 0; |
929 | ci.root = RB_ROOT; |
930 | ci.node = kmalloc(UBIFS_MAX_INO_NODE_SZ, GFP_NOFS); |
931 | if (!ci.node) { |
932 | ubifs_err("out of memory"); |
933 | return -ENOMEM; |
934 | } |
935 | |
936 | err = dbg_scan_orphans(c, &ci); |
937 | if (err) |
938 | goto out; |
939 | |
940 | err = dbg_walk_index(c, &dbg_orphan_check, NULL, &ci); |
941 | if (err) { |
942 | ubifs_err("cannot scan TNC, error %d", err); |
943 | goto out; |
944 | } |
945 | |
946 | if (ci.missing) { |
947 | ubifs_err("%lu missing orphan(s)", ci.missing); |
948 | err = -EINVAL; |
949 | goto out; |
950 | } |
951 | |
952 | dbg_cmt("last inode number is %lu", ci.last_ino); |
953 | dbg_cmt("total number of inodes is %lu", ci.tot_inos); |
954 | dbg_cmt("total number of leaf nodes is %llu", ci.leaf_cnt); |
955 | |
956 | out: |
957 | dbg_free_check_tree(&ci.root); |
958 | kfree(ci.node); |
959 | return err; |
960 | } |
961 | |
962 | #endif /* CONFIG_UBIFS_FS_DEBUG */ |
963 |
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