2 * This file is part of UBIFS.
4 * Copyright (C) 2006-2008 Nokia Corporation
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.
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
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
19 * Authors: Adrian Hunter
20 * Artem Bityutskiy (Битюцкий Артём)
24 * This file implements functions needed to recover from unclean un-mounts.
25 * When UBIFS is mounted, it checks a flag on the master node to determine if
26 * an un-mount was completed successfully. If not, the process of mounting
27 * incorporates additional checking and fixing of on-flash data structures.
28 * UBIFS always cleans away all remnants of an unclean un-mount, so that
29 * errors do not accumulate. However UBIFS defers recovery if it is mounted
30 * read-only, and the flash is not modified in that case.
32 * The general UBIFS approach to the recovery is that it recovers from
33 * corruptions which could be caused by power cuts, but it refuses to recover
34 * from corruption caused by other reasons. And UBIFS tries to distinguish
35 * between these 2 reasons of corruptions and silently recover in the former
36 * case and loudly complain in the latter case.
38 * UBIFS writes only to erased LEBs, so it writes only to the flash space
39 * containing only 0xFFs. UBIFS also always writes strictly from the beginning
40 * of the LEB to the end. And UBIFS assumes that the underlying flash media
41 * writes in @c->max_write_size bytes at a time.
43 * Hence, if UBIFS finds a corrupted node at offset X, it expects only the min.
44 * I/O unit corresponding to offset X to contain corrupted data, all the
45 * following min. I/O units have to contain empty space (all 0xFFs). If this is
46 * not true, the corruption cannot be the result of a power cut, and UBIFS
50 #include <linux/crc32.h>
51 #include <linux/slab.h>
55 * is_empty - determine whether a buffer is empty (contains all 0xff).
56 * @buf: buffer to clean
57 * @len: length of buffer
59 * This function returns %1 if the buffer is empty (contains all 0xff) otherwise
62 static int is_empty(void *buf
, int len
)
67 for (i
= 0; i
< len
; i
++)
74 * first_non_ff - find offset of the first non-0xff byte.
75 * @buf: buffer to search in
76 * @len: length of buffer
78 * This function returns offset of the first non-0xff byte in @buf or %-1 if
79 * the buffer contains only 0xff bytes.
81 static int first_non_ff(void *buf
, int len
)
86 for (i
= 0; i
< len
; i
++)
93 * get_master_node - get the last valid master node allowing for corruption.
94 * @c: UBIFS file-system description object
96 * @pbuf: buffer containing the LEB read, is returned here
97 * @mst: master node, if found, is returned here
98 * @cor: corruption, if found, is returned here
100 * This function allocates a buffer, reads the LEB into it, and finds and
101 * returns the last valid master node allowing for one area of corruption.
102 * The corrupt area, if there is one, must be consistent with the assumption
103 * that it is the result of an unclean unmount while the master node was being
104 * written. Under those circumstances, it is valid to use the previously written
107 * This function returns %0 on success and a negative error code on failure.
109 static int get_master_node(const struct ubifs_info
*c
, int lnum
, void **pbuf
,
110 struct ubifs_mst_node
**mst
, void **cor
)
112 const int sz
= c
->mst_node_alsz
;
116 sbuf
= vmalloc(c
->leb_size
);
120 err
= ubifs_leb_read(c
, lnum
, sbuf
, 0, c
->leb_size
, 0);
121 if (err
&& err
!= -EBADMSG
)
124 /* Find the first position that is definitely not a node */
128 while (offs
+ UBIFS_MST_NODE_SZ
<= c
->leb_size
) {
129 struct ubifs_ch
*ch
= buf
;
131 if (le32_to_cpu(ch
->magic
) != UBIFS_NODE_MAGIC
)
137 /* See if there was a valid master node before that */
144 ret
= ubifs_scan_a_node(c
, buf
, len
, lnum
, offs
, 1);
145 if (ret
!= SCANNED_A_NODE
&& offs
) {
146 /* Could have been corruption so check one place back */
150 ret
= ubifs_scan_a_node(c
, buf
, len
, lnum
, offs
, 1);
151 if (ret
!= SCANNED_A_NODE
)
153 * We accept only one area of corruption because
154 * we are assuming that it was caused while
155 * trying to write a master node.
159 if (ret
== SCANNED_A_NODE
) {
160 struct ubifs_ch
*ch
= buf
;
162 if (ch
->node_type
!= UBIFS_MST_NODE
)
164 dbg_rcvry("found a master node at %d:%d", lnum
, offs
);
171 /* Check for corruption */
172 if (offs
< c
->leb_size
) {
173 if (!is_empty(buf
, min_t(int, len
, sz
))) {
175 dbg_rcvry("found corruption at %d:%d", lnum
, offs
);
181 /* Check remaining empty space */
182 if (offs
< c
->leb_size
)
183 if (!is_empty(buf
, len
))
198 * write_rcvrd_mst_node - write recovered master node.
199 * @c: UBIFS file-system description object
202 * This function returns %0 on success and a negative error code on failure.
204 static int write_rcvrd_mst_node(struct ubifs_info
*c
,
205 struct ubifs_mst_node
*mst
)
207 int err
= 0, lnum
= UBIFS_MST_LNUM
, sz
= c
->mst_node_alsz
;
210 dbg_rcvry("recovery");
212 save_flags
= mst
->flags
;
213 mst
->flags
|= cpu_to_le32(UBIFS_MST_RCVRY
);
215 ubifs_prepare_node(c
, mst
, UBIFS_MST_NODE_SZ
, 1);
216 err
= ubifs_leb_change(c
, lnum
, mst
, sz
);
219 err
= ubifs_leb_change(c
, lnum
+ 1, mst
, sz
);
223 mst
->flags
= save_flags
;
228 * ubifs_recover_master_node - recover the master node.
229 * @c: UBIFS file-system description object
231 * This function recovers the master node from corruption that may occur due to
232 * an unclean unmount.
234 * This function returns %0 on success and a negative error code on failure.
236 int ubifs_recover_master_node(struct ubifs_info
*c
)
238 void *buf1
= NULL
, *buf2
= NULL
, *cor1
= NULL
, *cor2
= NULL
;
239 struct ubifs_mst_node
*mst1
= NULL
, *mst2
= NULL
, *mst
;
240 const int sz
= c
->mst_node_alsz
;
241 int err
, offs1
, offs2
;
243 dbg_rcvry("recovery");
245 err
= get_master_node(c
, UBIFS_MST_LNUM
, &buf1
, &mst1
, &cor1
);
249 err
= get_master_node(c
, UBIFS_MST_LNUM
+ 1, &buf2
, &mst2
, &cor2
);
254 offs1
= (void *)mst1
- buf1
;
255 if ((le32_to_cpu(mst1
->flags
) & UBIFS_MST_RCVRY
) &&
256 (offs1
== 0 && !cor1
)) {
258 * mst1 was written by recovery at offset 0 with no
261 dbg_rcvry("recovery recovery");
264 offs2
= (void *)mst2
- buf2
;
265 if (offs1
== offs2
) {
266 /* Same offset, so must be the same */
267 if (memcmp((void *)mst1
+ UBIFS_CH_SZ
,
268 (void *)mst2
+ UBIFS_CH_SZ
,
269 UBIFS_MST_NODE_SZ
- UBIFS_CH_SZ
))
272 } else if (offs2
+ sz
== offs1
) {
273 /* 1st LEB was written, 2nd was not */
277 } else if (offs1
== 0 &&
278 c
->leb_size
- offs2
- sz
< sz
) {
279 /* 1st LEB was unmapped and written, 2nd not */
287 * 2nd LEB was unmapped and about to be written, so
288 * there must be only one master node in the first LEB
291 if (offs1
!= 0 || cor1
)
299 * 1st LEB was unmapped and about to be written, so there must
300 * be no room left in 2nd LEB.
302 offs2
= (void *)mst2
- buf2
;
303 if (offs2
+ sz
+ sz
<= c
->leb_size
)
308 ubifs_msg("recovered master node from LEB %d",
309 (mst
== mst1
? UBIFS_MST_LNUM
: UBIFS_MST_LNUM
+ 1));
311 memcpy(c
->mst_node
, mst
, UBIFS_MST_NODE_SZ
);
314 /* Read-only mode. Keep a copy for switching to rw mode */
315 c
->rcvrd_mst_node
= kmalloc(sz
, GFP_KERNEL
);
316 if (!c
->rcvrd_mst_node
) {
320 memcpy(c
->rcvrd_mst_node
, c
->mst_node
, UBIFS_MST_NODE_SZ
);
323 * We had to recover the master node, which means there was an
324 * unclean reboot. However, it is possible that the master node
325 * is clean at this point, i.e., %UBIFS_MST_DIRTY is not set.
326 * E.g., consider the following chain of events:
328 * 1. UBIFS was cleanly unmounted, so the master node is clean
329 * 2. UBIFS is being mounted R/W and starts changing the master
330 * node in the first (%UBIFS_MST_LNUM). A power cut happens,
331 * so this LEB ends up with some amount of garbage at the
333 * 3. UBIFS is being mounted R/O. We reach this place and
334 * recover the master node from the second LEB
335 * (%UBIFS_MST_LNUM + 1). But we cannot update the media
336 * because we are being mounted R/O. We have to defer the
338 * 4. However, this master node (@c->mst_node) is marked as
339 * clean (since the step 1). And if we just return, the
340 * mount code will be confused and won't recover the master
341 * node when it is re-mounter R/W later.
343 * Thus, to force the recovery by marking the master node as
346 c
->mst_node
->flags
|= cpu_to_le32(UBIFS_MST_DIRTY
);
348 /* Write the recovered master node */
349 c
->max_sqnum
= le64_to_cpu(mst
->ch
.sqnum
) - 1;
350 err
= write_rcvrd_mst_node(c
, c
->mst_node
);
363 ubifs_err("failed to recover master node");
365 ubifs_err("dumping first master node");
366 ubifs_dump_node(c
, mst1
);
369 ubifs_err("dumping second master node");
370 ubifs_dump_node(c
, mst2
);
378 * ubifs_write_rcvrd_mst_node - write the recovered master node.
379 * @c: UBIFS file-system description object
381 * This function writes the master node that was recovered during mounting in
382 * read-only mode and must now be written because we are remounting rw.
384 * This function returns %0 on success and a negative error code on failure.
386 int ubifs_write_rcvrd_mst_node(struct ubifs_info
*c
)
390 if (!c
->rcvrd_mst_node
)
392 c
->rcvrd_mst_node
->flags
|= cpu_to_le32(UBIFS_MST_DIRTY
);
393 c
->mst_node
->flags
|= cpu_to_le32(UBIFS_MST_DIRTY
);
394 err
= write_rcvrd_mst_node(c
, c
->rcvrd_mst_node
);
397 kfree(c
->rcvrd_mst_node
);
398 c
->rcvrd_mst_node
= NULL
;
403 * is_last_write - determine if an offset was in the last write to a LEB.
404 * @c: UBIFS file-system description object
405 * @buf: buffer to check
406 * @offs: offset to check
408 * This function returns %1 if @offs was in the last write to the LEB whose data
409 * is in @buf, otherwise %0 is returned. The determination is made by checking
410 * for subsequent empty space starting from the next @c->max_write_size
413 static int is_last_write(const struct ubifs_info
*c
, void *buf
, int offs
)
415 int empty_offs
, check_len
;
419 * Round up to the next @c->max_write_size boundary i.e. @offs is in
420 * the last wbuf written. After that should be empty space.
422 empty_offs
= ALIGN(offs
+ 1, c
->max_write_size
);
423 check_len
= c
->leb_size
- empty_offs
;
424 p
= buf
+ empty_offs
- offs
;
425 return is_empty(p
, check_len
);
429 * clean_buf - clean the data from an LEB sitting in a buffer.
430 * @c: UBIFS file-system description object
431 * @buf: buffer to clean
432 * @lnum: LEB number to clean
433 * @offs: offset from which to clean
434 * @len: length of buffer
436 * This function pads up to the next min_io_size boundary (if there is one) and
437 * sets empty space to all 0xff. @buf, @offs and @len are updated to the next
438 * @c->min_io_size boundary.
440 static void clean_buf(const struct ubifs_info
*c
, void **buf
, int lnum
,
443 int empty_offs
, pad_len
;
446 dbg_rcvry("cleaning corruption at %d:%d", lnum
, *offs
);
448 ubifs_assert(!(*offs
& 7));
449 empty_offs
= ALIGN(*offs
, c
->min_io_size
);
450 pad_len
= empty_offs
- *offs
;
451 ubifs_pad(c
, *buf
, pad_len
);
455 memset(*buf
, 0xff, c
->leb_size
- empty_offs
);
459 * no_more_nodes - determine if there are no more nodes in a buffer.
460 * @c: UBIFS file-system description object
461 * @buf: buffer to check
462 * @len: length of buffer
463 * @lnum: LEB number of the LEB from which @buf was read
464 * @offs: offset from which @buf was read
466 * This function ensures that the corrupted node at @offs is the last thing
467 * written to a LEB. This function returns %1 if more data is not found and
468 * %0 if more data is found.
470 static int no_more_nodes(const struct ubifs_info
*c
, void *buf
, int len
,
473 struct ubifs_ch
*ch
= buf
;
474 int skip
, dlen
= le32_to_cpu(ch
->len
);
476 /* Check for empty space after the corrupt node's common header */
477 skip
= ALIGN(offs
+ UBIFS_CH_SZ
, c
->max_write_size
) - offs
;
478 if (is_empty(buf
+ skip
, len
- skip
))
481 * The area after the common header size is not empty, so the common
482 * header must be intact. Check it.
484 if (ubifs_check_node(c
, buf
, lnum
, offs
, 1, 0) != -EUCLEAN
) {
485 dbg_rcvry("unexpected bad common header at %d:%d", lnum
, offs
);
488 /* Now we know the corrupt node's length we can skip over it */
489 skip
= ALIGN(offs
+ dlen
, c
->max_write_size
) - offs
;
490 /* After which there should be empty space */
491 if (is_empty(buf
+ skip
, len
- skip
))
493 dbg_rcvry("unexpected data at %d:%d", lnum
, offs
+ skip
);
498 * fix_unclean_leb - fix an unclean LEB.
499 * @c: UBIFS file-system description object
500 * @sleb: scanned LEB information
501 * @start: offset where scan started
503 static int fix_unclean_leb(struct ubifs_info
*c
, struct ubifs_scan_leb
*sleb
,
506 int lnum
= sleb
->lnum
, endpt
= start
;
508 /* Get the end offset of the last node we are keeping */
509 if (!list_empty(&sleb
->nodes
)) {
510 struct ubifs_scan_node
*snod
;
512 snod
= list_entry(sleb
->nodes
.prev
,
513 struct ubifs_scan_node
, list
);
514 endpt
= snod
->offs
+ snod
->len
;
517 if (c
->ro_mount
&& !c
->remounting_rw
) {
518 /* Add to recovery list */
519 struct ubifs_unclean_leb
*ucleb
;
521 dbg_rcvry("need to fix LEB %d start %d endpt %d",
522 lnum
, start
, sleb
->endpt
);
523 ucleb
= kzalloc(sizeof(struct ubifs_unclean_leb
), GFP_NOFS
);
527 ucleb
->endpt
= endpt
;
528 list_add_tail(&ucleb
->list
, &c
->unclean_leb_list
);
530 /* Write the fixed LEB back to flash */
533 dbg_rcvry("fixing LEB %d start %d endpt %d",
534 lnum
, start
, sleb
->endpt
);
536 err
= ubifs_leb_unmap(c
, lnum
);
540 int len
= ALIGN(endpt
, c
->min_io_size
);
543 err
= ubifs_leb_read(c
, lnum
, sleb
->buf
, 0,
548 /* Pad to min_io_size */
550 int pad_len
= len
- ALIGN(endpt
, 8);
553 void *buf
= sleb
->buf
+ len
- pad_len
;
555 ubifs_pad(c
, buf
, pad_len
);
558 err
= ubifs_leb_change(c
, lnum
, sleb
->buf
, len
);
567 * drop_last_group - drop the last group of nodes.
568 * @sleb: scanned LEB information
569 * @offs: offset of dropped nodes is returned here
571 * This is a helper function for 'ubifs_recover_leb()' which drops the last
572 * group of nodes of the scanned LEB.
574 static void drop_last_group(struct ubifs_scan_leb
*sleb
, int *offs
)
576 while (!list_empty(&sleb
->nodes
)) {
577 struct ubifs_scan_node
*snod
;
580 snod
= list_entry(sleb
->nodes
.prev
, struct ubifs_scan_node
,
583 if (ch
->group_type
!= UBIFS_IN_NODE_GROUP
)
586 dbg_rcvry("dropping grouped node at %d:%d",
587 sleb
->lnum
, snod
->offs
);
589 list_del(&snod
->list
);
591 sleb
->nodes_cnt
-= 1;
596 * drop_last_node - drop the last node.
597 * @sleb: scanned LEB information
598 * @offs: offset of dropped nodes is returned here
599 * @grouped: non-zero if whole group of nodes have to be dropped
601 * This is a helper function for 'ubifs_recover_leb()' which drops the last
602 * node of the scanned LEB.
604 static void drop_last_node(struct ubifs_scan_leb
*sleb
, int *offs
)
606 struct ubifs_scan_node
*snod
;
608 if (!list_empty(&sleb
->nodes
)) {
609 snod
= list_entry(sleb
->nodes
.prev
, struct ubifs_scan_node
,
612 dbg_rcvry("dropping last node at %d:%d", sleb
->lnum
, snod
->offs
);
614 list_del(&snod
->list
);
616 sleb
->nodes_cnt
-= 1;
621 * ubifs_recover_leb - scan and recover a LEB.
622 * @c: UBIFS file-system description object
625 * @sbuf: LEB-sized buffer to use
626 * @jhead: journal head number this LEB belongs to (%-1 if the LEB does not
627 * belong to any journal head)
629 * This function does a scan of a LEB, but caters for errors that might have
630 * been caused by the unclean unmount from which we are attempting to recover.
631 * Returns %0 in case of success, %-EUCLEAN if an unrecoverable corruption is
632 * found, and a negative error code in case of failure.
634 struct ubifs_scan_leb
*ubifs_recover_leb(struct ubifs_info
*c
, int lnum
,
635 int offs
, void *sbuf
, int jhead
)
637 int ret
= 0, err
, len
= c
->leb_size
- offs
, start
= offs
, min_io_unit
;
638 int grouped
= jhead
== -1 ? 0 : c
->jheads
[jhead
].grouped
;
639 struct ubifs_scan_leb
*sleb
;
640 void *buf
= sbuf
+ offs
;
642 dbg_rcvry("%d:%d, jhead %d, grouped %d", lnum
, offs
, jhead
, grouped
);
644 sleb
= ubifs_start_scan(c
, lnum
, offs
, sbuf
);
648 ubifs_assert(len
>= 8);
650 dbg_scan("look at LEB %d:%d (%d bytes left)",
656 * Scan quietly until there is an error from which we cannot
659 ret
= ubifs_scan_a_node(c
, buf
, len
, lnum
, offs
, 1);
660 if (ret
== SCANNED_A_NODE
) {
661 /* A valid node, and not a padding node */
662 struct ubifs_ch
*ch
= buf
;
665 err
= ubifs_add_snod(c
, sleb
, buf
, offs
);
668 node_len
= ALIGN(le32_to_cpu(ch
->len
), 8);
672 } else if (ret
> 0) {
673 /* Padding bytes or a valid padding node */
677 } else if (ret
== SCANNED_EMPTY_SPACE
||
678 ret
== SCANNED_GARBAGE
||
679 ret
== SCANNED_A_BAD_PAD_NODE
||
680 ret
== SCANNED_A_CORRUPT_NODE
) {
681 dbg_rcvry("found corruption (%d) at %d:%d",
685 ubifs_err("unexpected return value %d", ret
);
691 if (ret
== SCANNED_GARBAGE
|| ret
== SCANNED_A_BAD_PAD_NODE
) {
692 if (!is_last_write(c
, buf
, offs
))
693 goto corrupted_rescan
;
694 } else if (ret
== SCANNED_A_CORRUPT_NODE
) {
695 if (!no_more_nodes(c
, buf
, len
, lnum
, offs
))
696 goto corrupted_rescan
;
697 } else if (!is_empty(buf
, len
)) {
698 if (!is_last_write(c
, buf
, offs
)) {
699 int corruption
= first_non_ff(buf
, len
);
702 * See header comment for this file for more
703 * explanations about the reasons we have this check.
705 ubifs_err("corrupt empty space LEB %d:%d, corruption "
706 "starts at %d", lnum
, offs
, corruption
);
707 /* Make sure we dump interesting non-0xFF data */
714 min_io_unit
= round_down(offs
, c
->min_io_size
);
717 * If nodes are grouped, always drop the incomplete group at
720 drop_last_group(sleb
, &offs
);
724 * If this LEB belongs to the GC head then while we are in the
725 * middle of the same min. I/O unit keep dropping nodes. So
726 * basically, what we want is to make sure that the last min.
727 * I/O unit where we saw the corruption is dropped completely
728 * with all the uncorrupted nodes which may possibly sit there.
730 * In other words, let's name the min. I/O unit where the
731 * corruption starts B, and the previous min. I/O unit A. The
732 * below code tries to deal with a situation when half of B
733 * contains valid nodes or the end of a valid node, and the
734 * second half of B contains corrupted data or garbage. This
735 * means that UBIFS had been writing to B just before the power
736 * cut happened. I do not know how realistic is this scenario
737 * that half of the min. I/O unit had been written successfully
738 * and the other half not, but this is possible in our 'failure
739 * mode emulation' infrastructure at least.
741 * So what is the problem, why we need to drop those nodes? Why
742 * can't we just clean-up the second half of B by putting a
743 * padding node there? We can, and this works fine with one
744 * exception which was reproduced with power cut emulation
745 * testing and happens extremely rarely.
747 * Imagine the file-system is full, we run GC which starts
748 * moving valid nodes from LEB X to LEB Y (obviously, LEB Y is
749 * the current GC head LEB). The @c->gc_lnum is -1, which means
750 * that GC will retain LEB X and will try to continue. Imagine
751 * that LEB X is currently the dirtiest LEB, and the amount of
752 * used space in LEB Y is exactly the same as amount of free
755 * And a power cut happens when nodes are moved from LEB X to
756 * LEB Y. We are here trying to recover LEB Y which is the GC
757 * head LEB. We find the min. I/O unit B as described above.
758 * Then we clean-up LEB Y by padding min. I/O unit. And later
759 * 'ubifs_rcvry_gc_commit()' function fails, because it cannot
760 * find a dirty LEB which could be GC'd into LEB Y! Even LEB X
761 * does not match because the amount of valid nodes there does
762 * not fit the free space in LEB Y any more! And this is
763 * because of the padding node which we added to LEB Y. The
764 * user-visible effect of this which I once observed and
765 * analysed is that we cannot mount the file-system with
768 * So obviously, to make sure that situation does not happen we
769 * should free min. I/O unit B in LEB Y completely and the last
770 * used min. I/O unit in LEB Y should be A. This is basically
771 * what the below code tries to do.
773 while (offs
> min_io_unit
)
774 drop_last_node(sleb
, &offs
);
778 len
= c
->leb_size
- offs
;
780 clean_buf(c
, &buf
, lnum
, &offs
, &len
);
781 ubifs_end_scan(c
, sleb
, lnum
, offs
);
783 err
= fix_unclean_leb(c
, sleb
, start
);
790 /* Re-scan the corrupted data with verbose messages */
791 ubifs_err("corruption %d", ret
);
792 ubifs_scan_a_node(c
, buf
, len
, lnum
, offs
, 1);
794 ubifs_scanned_corruption(c
, lnum
, offs
, buf
);
797 ubifs_err("LEB %d scanning failed", lnum
);
798 ubifs_scan_destroy(sleb
);
803 * get_cs_sqnum - get commit start sequence number.
804 * @c: UBIFS file-system description object
805 * @lnum: LEB number of commit start node
806 * @offs: offset of commit start node
807 * @cs_sqnum: commit start sequence number is returned here
809 * This function returns %0 on success and a negative error code on failure.
811 static int get_cs_sqnum(struct ubifs_info
*c
, int lnum
, int offs
,
812 unsigned long long *cs_sqnum
)
814 struct ubifs_cs_node
*cs_node
= NULL
;
817 dbg_rcvry("at %d:%d", lnum
, offs
);
818 cs_node
= kmalloc(UBIFS_CS_NODE_SZ
, GFP_KERNEL
);
821 if (c
->leb_size
- offs
< UBIFS_CS_NODE_SZ
)
823 err
= ubifs_leb_read(c
, lnum
, (void *)cs_node
, offs
,
824 UBIFS_CS_NODE_SZ
, 0);
825 if (err
&& err
!= -EBADMSG
)
827 ret
= ubifs_scan_a_node(c
, cs_node
, UBIFS_CS_NODE_SZ
, lnum
, offs
, 0);
828 if (ret
!= SCANNED_A_NODE
) {
829 ubifs_err("Not a valid node");
832 if (cs_node
->ch
.node_type
!= UBIFS_CS_NODE
) {
833 ubifs_err("Node a CS node, type is %d", cs_node
->ch
.node_type
);
836 if (le64_to_cpu(cs_node
->cmt_no
) != c
->cmt_no
) {
837 ubifs_err("CS node cmt_no %llu != current cmt_no %llu",
838 (unsigned long long)le64_to_cpu(cs_node
->cmt_no
),
842 *cs_sqnum
= le64_to_cpu(cs_node
->ch
.sqnum
);
843 dbg_rcvry("commit start sqnum %llu", *cs_sqnum
);
850 ubifs_err("failed to get CS sqnum");
856 * ubifs_recover_log_leb - scan and recover a log LEB.
857 * @c: UBIFS file-system description object
860 * @sbuf: LEB-sized buffer to use
862 * This function does a scan of a LEB, but caters for errors that might have
863 * been caused by unclean reboots from which we are attempting to recover
864 * (assume that only the last log LEB can be corrupted by an unclean reboot).
866 * This function returns %0 on success and a negative error code on failure.
868 struct ubifs_scan_leb
*ubifs_recover_log_leb(struct ubifs_info
*c
, int lnum
,
869 int offs
, void *sbuf
)
871 struct ubifs_scan_leb
*sleb
;
874 dbg_rcvry("LEB %d", lnum
);
875 next_lnum
= lnum
+ 1;
876 if (next_lnum
>= UBIFS_LOG_LNUM
+ c
->log_lebs
)
877 next_lnum
= UBIFS_LOG_LNUM
;
878 if (next_lnum
!= c
->ltail_lnum
) {
880 * We can only recover at the end of the log, so check that the
881 * next log LEB is empty or out of date.
883 sleb
= ubifs_scan(c
, next_lnum
, 0, sbuf
, 0);
886 if (sleb
->nodes_cnt
) {
887 struct ubifs_scan_node
*snod
;
888 unsigned long long cs_sqnum
= c
->cs_sqnum
;
890 snod
= list_entry(sleb
->nodes
.next
,
891 struct ubifs_scan_node
, list
);
895 err
= get_cs_sqnum(c
, lnum
, offs
, &cs_sqnum
);
897 ubifs_scan_destroy(sleb
);
901 if (snod
->sqnum
> cs_sqnum
) {
902 ubifs_err("unrecoverable log corruption "
904 ubifs_scan_destroy(sleb
);
905 return ERR_PTR(-EUCLEAN
);
908 ubifs_scan_destroy(sleb
);
910 return ubifs_recover_leb(c
, lnum
, offs
, sbuf
, -1);
914 * recover_head - recover a head.
915 * @c: UBIFS file-system description object
916 * @lnum: LEB number of head to recover
917 * @offs: offset of head to recover
918 * @sbuf: LEB-sized buffer to use
920 * This function ensures that there is no data on the flash at a head location.
922 * This function returns %0 on success and a negative error code on failure.
924 static int recover_head(struct ubifs_info
*c
, int lnum
, int offs
, void *sbuf
)
926 int len
= c
->max_write_size
, err
;
928 if (offs
+ len
> c
->leb_size
)
929 len
= c
->leb_size
- offs
;
934 /* Read at the head location and check it is empty flash */
935 err
= ubifs_leb_read(c
, lnum
, sbuf
, offs
, len
, 1);
936 if (err
|| !is_empty(sbuf
, len
)) {
937 dbg_rcvry("cleaning head at %d:%d", lnum
, offs
);
939 return ubifs_leb_unmap(c
, lnum
);
940 err
= ubifs_leb_read(c
, lnum
, sbuf
, 0, offs
, 1);
943 return ubifs_leb_change(c
, lnum
, sbuf
, offs
);
950 * ubifs_recover_inl_heads - recover index and LPT heads.
951 * @c: UBIFS file-system description object
952 * @sbuf: LEB-sized buffer to use
954 * This function ensures that there is no data on the flash at the index and
955 * LPT head locations.
957 * This deals with the recovery of a half-completed journal commit. UBIFS is
958 * careful never to overwrite the last version of the index or the LPT. Because
959 * the index and LPT are wandering trees, data from a half-completed commit will
960 * not be referenced anywhere in UBIFS. The data will be either in LEBs that are
961 * assumed to be empty and will be unmapped anyway before use, or in the index
964 * This function returns %0 on success and a negative error code on failure.
966 int ubifs_recover_inl_heads(struct ubifs_info
*c
, void *sbuf
)
970 ubifs_assert(!c
->ro_mount
|| c
->remounting_rw
);
972 dbg_rcvry("checking index head at %d:%d", c
->ihead_lnum
, c
->ihead_offs
);
973 err
= recover_head(c
, c
->ihead_lnum
, c
->ihead_offs
, sbuf
);
977 dbg_rcvry("checking LPT head at %d:%d", c
->nhead_lnum
, c
->nhead_offs
);
978 err
= recover_head(c
, c
->nhead_lnum
, c
->nhead_offs
, sbuf
);
986 * clean_an_unclean_leb - read and write a LEB to remove corruption.
987 * @c: UBIFS file-system description object
988 * @ucleb: unclean LEB information
989 * @sbuf: LEB-sized buffer to use
991 * This function reads a LEB up to a point pre-determined by the mount recovery,
992 * checks the nodes, and writes the result back to the flash, thereby cleaning
993 * off any following corruption, or non-fatal ECC errors.
995 * This function returns %0 on success and a negative error code on failure.
997 static int clean_an_unclean_leb(struct ubifs_info
*c
,
998 struct ubifs_unclean_leb
*ucleb
, void *sbuf
)
1000 int err
, lnum
= ucleb
->lnum
, offs
= 0, len
= ucleb
->endpt
, quiet
= 1;
1003 dbg_rcvry("LEB %d len %d", lnum
, len
);
1006 /* Nothing to read, just unmap it */
1007 err
= ubifs_leb_unmap(c
, lnum
);
1013 err
= ubifs_leb_read(c
, lnum
, buf
, offs
, len
, 0);
1014 if (err
&& err
!= -EBADMSG
)
1022 /* Scan quietly until there is an error */
1023 ret
= ubifs_scan_a_node(c
, buf
, len
, lnum
, offs
, quiet
);
1025 if (ret
== SCANNED_A_NODE
) {
1026 /* A valid node, and not a padding node */
1027 struct ubifs_ch
*ch
= buf
;
1030 node_len
= ALIGN(le32_to_cpu(ch
->len
), 8);
1038 /* Padding bytes or a valid padding node */
1045 if (ret
== SCANNED_EMPTY_SPACE
) {
1046 ubifs_err("unexpected empty space at %d:%d",
1052 /* Redo the last scan but noisily */
1057 ubifs_scanned_corruption(c
, lnum
, offs
, buf
);
1061 /* Pad to min_io_size */
1062 len
= ALIGN(ucleb
->endpt
, c
->min_io_size
);
1063 if (len
> ucleb
->endpt
) {
1064 int pad_len
= len
- ALIGN(ucleb
->endpt
, 8);
1067 buf
= c
->sbuf
+ len
- pad_len
;
1068 ubifs_pad(c
, buf
, pad_len
);
1072 /* Write back the LEB atomically */
1073 err
= ubifs_leb_change(c
, lnum
, sbuf
, len
);
1077 dbg_rcvry("cleaned LEB %d", lnum
);
1083 * ubifs_clean_lebs - clean LEBs recovered during read-only mount.
1084 * @c: UBIFS file-system description object
1085 * @sbuf: LEB-sized buffer to use
1087 * This function cleans a LEB identified during recovery that needs to be
1088 * written but was not because UBIFS was mounted read-only. This happens when
1089 * remounting to read-write mode.
1091 * This function returns %0 on success and a negative error code on failure.
1093 int ubifs_clean_lebs(struct ubifs_info
*c
, void *sbuf
)
1095 dbg_rcvry("recovery");
1096 while (!list_empty(&c
->unclean_leb_list
)) {
1097 struct ubifs_unclean_leb
*ucleb
;
1100 ucleb
= list_entry(c
->unclean_leb_list
.next
,
1101 struct ubifs_unclean_leb
, list
);
1102 err
= clean_an_unclean_leb(c
, ucleb
, sbuf
);
1105 list_del(&ucleb
->list
);
1112 * grab_empty_leb - grab an empty LEB to use as GC LEB and run commit.
1113 * @c: UBIFS file-system description object
1115 * This is a helper function for 'ubifs_rcvry_gc_commit()' which grabs an empty
1116 * LEB to be used as GC LEB (@c->gc_lnum), and then runs the commit. Returns
1117 * zero in case of success and a negative error code in case of failure.
1119 static int grab_empty_leb(struct ubifs_info
*c
)
1124 * Note, it is very important to first search for an empty LEB and then
1125 * run the commit, not vice-versa. The reason is that there might be
1126 * only one empty LEB at the moment, the one which has been the
1127 * @c->gc_lnum just before the power cut happened. During the regular
1128 * UBIFS operation (not now) @c->gc_lnum is marked as "taken", so no
1129 * one but GC can grab it. But at this moment this single empty LEB is
1130 * not marked as taken, so if we run commit - what happens? Right, the
1131 * commit will grab it and write the index there. Remember that the
1132 * index always expands as long as there is free space, and it only
1133 * starts consolidating when we run out of space.
1135 * IOW, if we run commit now, we might not be able to find a free LEB
1138 lnum
= ubifs_find_free_leb_for_idx(c
);
1140 ubifs_err("could not find an empty LEB");
1141 ubifs_dump_lprops(c
);
1142 ubifs_dump_budg(c
, &c
->bi
);
1146 /* Reset the index flag */
1147 err
= ubifs_change_one_lp(c
, lnum
, LPROPS_NC
, LPROPS_NC
, 0,
1153 dbg_rcvry("found empty LEB %d, run commit", lnum
);
1155 return ubifs_run_commit(c
);
1159 * ubifs_rcvry_gc_commit - recover the GC LEB number and run the commit.
1160 * @c: UBIFS file-system description object
1162 * Out-of-place garbage collection requires always one empty LEB with which to
1163 * start garbage collection. The LEB number is recorded in c->gc_lnum and is
1164 * written to the master node on unmounting. In the case of an unclean unmount
1165 * the value of gc_lnum recorded in the master node is out of date and cannot
1166 * be used. Instead, recovery must allocate an empty LEB for this purpose.
1167 * However, there may not be enough empty space, in which case it must be
1168 * possible to GC the dirtiest LEB into the GC head LEB.
1170 * This function also runs the commit which causes the TNC updates from
1171 * size-recovery and orphans to be written to the flash. That is important to
1172 * ensure correct replay order for subsequent mounts.
1174 * This function returns %0 on success and a negative error code on failure.
1176 int ubifs_rcvry_gc_commit(struct ubifs_info
*c
)
1178 struct ubifs_wbuf
*wbuf
= &c
->jheads
[GCHD
].wbuf
;
1179 struct ubifs_lprops lp
;
1182 dbg_rcvry("GC head LEB %d, offs %d", wbuf
->lnum
, wbuf
->offs
);
1185 if (wbuf
->lnum
== -1 || wbuf
->offs
== c
->leb_size
)
1186 return grab_empty_leb(c
);
1188 err
= ubifs_find_dirty_leb(c
, &lp
, wbuf
->offs
, 2);
1193 dbg_rcvry("could not find a dirty LEB");
1194 return grab_empty_leb(c
);
1197 ubifs_assert(!(lp
.flags
& LPROPS_INDEX
));
1198 ubifs_assert(lp
.free
+ lp
.dirty
>= wbuf
->offs
);
1201 * We run the commit before garbage collection otherwise subsequent
1202 * mounts will see the GC and orphan deletion in a different order.
1204 dbg_rcvry("committing");
1205 err
= ubifs_run_commit(c
);
1209 dbg_rcvry("GC'ing LEB %d", lp
.lnum
);
1210 mutex_lock_nested(&wbuf
->io_mutex
, wbuf
->jhead
);
1211 err
= ubifs_garbage_collect_leb(c
, &lp
);
1213 int err2
= ubifs_wbuf_sync_nolock(wbuf
);
1218 mutex_unlock(&wbuf
->io_mutex
);
1220 ubifs_err("GC failed, error %d", err
);
1226 ubifs_assert(err
== LEB_RETAINED
);
1227 if (err
!= LEB_RETAINED
)
1230 err
= ubifs_leb_unmap(c
, c
->gc_lnum
);
1234 dbg_rcvry("allocated LEB %d for GC", lp
.lnum
);
1239 * struct size_entry - inode size information for recovery.
1240 * @rb: link in the RB-tree of sizes
1241 * @inum: inode number
1242 * @i_size: size on inode
1243 * @d_size: maximum size based on data nodes
1244 * @exists: indicates whether the inode exists
1245 * @inode: inode if pinned in memory awaiting rw mode to fix it
1253 struct inode
*inode
;
1257 * add_ino - add an entry to the size tree.
1258 * @c: UBIFS file-system description object
1259 * @inum: inode number
1260 * @i_size: size on inode
1261 * @d_size: maximum size based on data nodes
1262 * @exists: indicates whether the inode exists
1264 static int add_ino(struct ubifs_info
*c
, ino_t inum
, loff_t i_size
,
1265 loff_t d_size
, int exists
)
1267 struct rb_node
**p
= &c
->size_tree
.rb_node
, *parent
= NULL
;
1268 struct size_entry
*e
;
1272 e
= rb_entry(parent
, struct size_entry
, rb
);
1276 p
= &(*p
)->rb_right
;
1279 e
= kzalloc(sizeof(struct size_entry
), GFP_KERNEL
);
1288 rb_link_node(&e
->rb
, parent
, p
);
1289 rb_insert_color(&e
->rb
, &c
->size_tree
);
1295 * find_ino - find an entry on the size tree.
1296 * @c: UBIFS file-system description object
1297 * @inum: inode number
1299 static struct size_entry
*find_ino(struct ubifs_info
*c
, ino_t inum
)
1301 struct rb_node
*p
= c
->size_tree
.rb_node
;
1302 struct size_entry
*e
;
1305 e
= rb_entry(p
, struct size_entry
, rb
);
1308 else if (inum
> e
->inum
)
1317 * remove_ino - remove an entry from the size tree.
1318 * @c: UBIFS file-system description object
1319 * @inum: inode number
1321 static void remove_ino(struct ubifs_info
*c
, ino_t inum
)
1323 struct size_entry
*e
= find_ino(c
, inum
);
1327 rb_erase(&e
->rb
, &c
->size_tree
);
1332 * ubifs_destroy_size_tree - free resources related to the size tree.
1333 * @c: UBIFS file-system description object
1335 void ubifs_destroy_size_tree(struct ubifs_info
*c
)
1337 struct rb_node
*this = c
->size_tree
.rb_node
;
1338 struct size_entry
*e
;
1341 if (this->rb_left
) {
1342 this = this->rb_left
;
1344 } else if (this->rb_right
) {
1345 this = this->rb_right
;
1348 e
= rb_entry(this, struct size_entry
, rb
);
1351 this = rb_parent(this);
1353 if (this->rb_left
== &e
->rb
)
1354 this->rb_left
= NULL
;
1356 this->rb_right
= NULL
;
1360 c
->size_tree
= RB_ROOT
;
1364 * ubifs_recover_size_accum - accumulate inode sizes for recovery.
1365 * @c: UBIFS file-system description object
1367 * @deletion: node is for a deletion
1368 * @new_size: inode size
1370 * This function has two purposes:
1371 * 1) to ensure there are no data nodes that fall outside the inode size
1372 * 2) to ensure there are no data nodes for inodes that do not exist
1373 * To accomplish those purposes, a rb-tree is constructed containing an entry
1374 * for each inode number in the journal that has not been deleted, and recording
1375 * the size from the inode node, the maximum size of any data node (also altered
1376 * by truncations) and a flag indicating a inode number for which no inode node
1377 * was present in the journal.
1379 * Note that there is still the possibility that there are data nodes that have
1380 * been committed that are beyond the inode size, however the only way to find
1381 * them would be to scan the entire index. Alternatively, some provision could
1382 * be made to record the size of inodes at the start of commit, which would seem
1383 * very cumbersome for a scenario that is quite unlikely and the only negative
1384 * consequence of which is wasted space.
1386 * This functions returns %0 on success and a negative error code on failure.
1388 int ubifs_recover_size_accum(struct ubifs_info
*c
, union ubifs_key
*key
,
1389 int deletion
, loff_t new_size
)
1391 ino_t inum
= key_inum(c
, key
);
1392 struct size_entry
*e
;
1395 switch (key_type(c
, key
)) {
1398 remove_ino(c
, inum
);
1400 e
= find_ino(c
, inum
);
1402 e
->i_size
= new_size
;
1405 err
= add_ino(c
, inum
, new_size
, 0, 1);
1411 case UBIFS_DATA_KEY
:
1412 e
= find_ino(c
, inum
);
1414 if (new_size
> e
->d_size
)
1415 e
->d_size
= new_size
;
1417 err
= add_ino(c
, inum
, 0, new_size
, 0);
1422 case UBIFS_TRUN_KEY
:
1423 e
= find_ino(c
, inum
);
1425 e
->d_size
= new_size
;
1432 * fix_size_in_place - fix inode size in place on flash.
1433 * @c: UBIFS file-system description object
1434 * @e: inode size information for recovery
1436 static int fix_size_in_place(struct ubifs_info
*c
, struct size_entry
*e
)
1438 struct ubifs_ino_node
*ino
= c
->sbuf
;
1440 union ubifs_key key
;
1441 int err
, lnum
, offs
, len
;
1445 /* Locate the inode node LEB number and offset */
1446 ino_key_init(c
, &key
, e
->inum
);
1447 err
= ubifs_tnc_locate(c
, &key
, ino
, &lnum
, &offs
);
1451 * If the size recorded on the inode node is greater than the size that
1452 * was calculated from nodes in the journal then don't change the inode.
1454 i_size
= le64_to_cpu(ino
->size
);
1455 if (i_size
>= e
->d_size
)
1458 err
= ubifs_leb_read(c
, lnum
, c
->sbuf
, 0, c
->leb_size
, 1);
1461 /* Change the size field and recalculate the CRC */
1462 ino
= c
->sbuf
+ offs
;
1463 ino
->size
= cpu_to_le64(e
->d_size
);
1464 len
= le32_to_cpu(ino
->ch
.len
);
1465 crc
= crc32(UBIFS_CRC32_INIT
, (void *)ino
+ 8, len
- 8);
1466 ino
->ch
.crc
= cpu_to_le32(crc
);
1467 /* Work out where data in the LEB ends and free space begins */
1469 len
= c
->leb_size
- 1;
1470 while (p
[len
] == 0xff)
1472 len
= ALIGN(len
+ 1, c
->min_io_size
);
1473 /* Atomically write the fixed LEB back again */
1474 err
= ubifs_leb_change(c
, lnum
, c
->sbuf
, len
);
1477 dbg_rcvry("inode %lu at %d:%d size %lld -> %lld",
1478 (unsigned long)e
->inum
, lnum
, offs
, i_size
, e
->d_size
);
1482 ubifs_warn("inode %lu failed to fix size %lld -> %lld error %d",
1483 (unsigned long)e
->inum
, e
->i_size
, e
->d_size
, err
);
1488 * ubifs_recover_size - recover inode size.
1489 * @c: UBIFS file-system description object
1491 * This function attempts to fix inode size discrepancies identified by the
1492 * 'ubifs_recover_size_accum()' function.
1494 * This functions returns %0 on success and a negative error code on failure.
1496 int ubifs_recover_size(struct ubifs_info
*c
)
1498 struct rb_node
*this = rb_first(&c
->size_tree
);
1501 struct size_entry
*e
;
1504 e
= rb_entry(this, struct size_entry
, rb
);
1506 union ubifs_key key
;
1508 ino_key_init(c
, &key
, e
->inum
);
1509 err
= ubifs_tnc_lookup(c
, &key
, c
->sbuf
);
1510 if (err
&& err
!= -ENOENT
)
1512 if (err
== -ENOENT
) {
1513 /* Remove data nodes that have no inode */
1514 dbg_rcvry("removing ino %lu",
1515 (unsigned long)e
->inum
);
1516 err
= ubifs_tnc_remove_ino(c
, e
->inum
);
1520 struct ubifs_ino_node
*ino
= c
->sbuf
;
1523 e
->i_size
= le64_to_cpu(ino
->size
);
1527 if (e
->exists
&& e
->i_size
< e
->d_size
) {
1529 /* Fix the inode size and pin it in memory */
1530 struct inode
*inode
;
1531 struct ubifs_inode
*ui
;
1533 ubifs_assert(!e
->inode
);
1535 inode
= ubifs_iget(c
->vfs_sb
, e
->inum
);
1537 return PTR_ERR(inode
);
1539 ui
= ubifs_inode(inode
);
1540 if (inode
->i_size
< e
->d_size
) {
1541 dbg_rcvry("ino %lu size %lld -> %lld",
1542 (unsigned long)e
->inum
,
1543 inode
->i_size
, e
->d_size
);
1544 inode
->i_size
= e
->d_size
;
1545 ui
->ui_size
= e
->d_size
;
1546 ui
->synced_i_size
= e
->d_size
;
1548 this = rb_next(this);
1553 /* Fix the size in place */
1554 err
= fix_size_in_place(c
, e
);
1562 this = rb_next(this);
1563 rb_erase(&e
->rb
, &c
->size_tree
);
This page took 0.061642 seconds and 5 git commands to generate.