]>
git.ipfire.org Git - people/ms/u-boot.git/blob - fs/ubifs/recovery.c
2 * This file is part of UBIFS.
4 * Copyright (C) 2006-2008 Nokia Corporation
6 * SPDX-License-Identifier: GPL-2.0+
8 * Authors: Adrian Hunter
9 * Artem Bityutskiy (Битюцкий Артём)
13 * This file implements functions needed to recover from unclean un-mounts.
14 * When UBIFS is mounted, it checks a flag on the master node to determine if
15 * an un-mount was completed successfully. If not, the process of mounting
16 * incorporates additional checking and fixing of on-flash data structures.
17 * UBIFS always cleans away all remnants of an unclean un-mount, so that
18 * errors do not accumulate. However UBIFS defers recovery if it is mounted
19 * read-only, and the flash is not modified in that case.
21 * The general UBIFS approach to the recovery is that it recovers from
22 * corruptions which could be caused by power cuts, but it refuses to recover
23 * from corruption caused by other reasons. And UBIFS tries to distinguish
24 * between these 2 reasons of corruptions and silently recover in the former
25 * case and loudly complain in the latter case.
27 * UBIFS writes only to erased LEBs, so it writes only to the flash space
28 * containing only 0xFFs. UBIFS also always writes strictly from the beginning
29 * of the LEB to the end. And UBIFS assumes that the underlying flash media
30 * writes in @c->max_write_size bytes at a time.
32 * Hence, if UBIFS finds a corrupted node at offset X, it expects only the min.
33 * I/O unit corresponding to offset X to contain corrupted data, all the
34 * following min. I/O units have to contain empty space (all 0xFFs). If this is
35 * not true, the corruption cannot be the result of a power cut, and UBIFS
41 #include <linux/crc32.h>
42 #include <linux/slab.h>
44 #include <linux/err.h>
49 * is_empty - determine whether a buffer is empty (contains all 0xff).
50 * @buf: buffer to clean
51 * @len: length of buffer
53 * This function returns %1 if the buffer is empty (contains all 0xff) otherwise
56 static int is_empty(void *buf
, int len
)
61 for (i
= 0; i
< len
; i
++)
68 * first_non_ff - find offset of the first non-0xff byte.
69 * @buf: buffer to search in
70 * @len: length of buffer
72 * This function returns offset of the first non-0xff byte in @buf or %-1 if
73 * the buffer contains only 0xff bytes.
75 static int first_non_ff(void *buf
, int len
)
80 for (i
= 0; i
< len
; i
++)
87 * get_master_node - get the last valid master node allowing for corruption.
88 * @c: UBIFS file-system description object
90 * @pbuf: buffer containing the LEB read, is returned here
91 * @mst: master node, if found, is returned here
92 * @cor: corruption, if found, is returned here
94 * This function allocates a buffer, reads the LEB into it, and finds and
95 * returns the last valid master node allowing for one area of corruption.
96 * The corrupt area, if there is one, must be consistent with the assumption
97 * that it is the result of an unclean unmount while the master node was being
98 * written. Under those circumstances, it is valid to use the previously written
101 * This function returns %0 on success and a negative error code on failure.
103 static int get_master_node(const struct ubifs_info
*c
, int lnum
, void **pbuf
,
104 struct ubifs_mst_node
**mst
, void **cor
)
106 const int sz
= c
->mst_node_alsz
;
110 sbuf
= vmalloc(c
->leb_size
);
114 err
= ubifs_leb_read(c
, lnum
, sbuf
, 0, c
->leb_size
, 0);
115 if (err
&& err
!= -EBADMSG
)
118 /* Find the first position that is definitely not a node */
122 while (offs
+ UBIFS_MST_NODE_SZ
<= c
->leb_size
) {
123 struct ubifs_ch
*ch
= buf
;
125 if (le32_to_cpu(ch
->magic
) != UBIFS_NODE_MAGIC
)
131 /* See if there was a valid master node before that */
138 ret
= ubifs_scan_a_node(c
, buf
, len
, lnum
, offs
, 1);
139 if (ret
!= SCANNED_A_NODE
&& offs
) {
140 /* Could have been corruption so check one place back */
144 ret
= ubifs_scan_a_node(c
, buf
, len
, lnum
, offs
, 1);
145 if (ret
!= SCANNED_A_NODE
)
147 * We accept only one area of corruption because
148 * we are assuming that it was caused while
149 * trying to write a master node.
153 if (ret
== SCANNED_A_NODE
) {
154 struct ubifs_ch
*ch
= buf
;
156 if (ch
->node_type
!= UBIFS_MST_NODE
)
158 dbg_rcvry("found a master node at %d:%d", lnum
, offs
);
165 /* Check for corruption */
166 if (offs
< c
->leb_size
) {
167 if (!is_empty(buf
, min_t(int, len
, sz
))) {
169 dbg_rcvry("found corruption at %d:%d", lnum
, offs
);
175 /* Check remaining empty space */
176 if (offs
< c
->leb_size
)
177 if (!is_empty(buf
, len
))
192 * write_rcvrd_mst_node - write recovered master node.
193 * @c: UBIFS file-system description object
196 * This function returns %0 on success and a negative error code on failure.
198 static int write_rcvrd_mst_node(struct ubifs_info
*c
,
199 struct ubifs_mst_node
*mst
)
201 int err
= 0, lnum
= UBIFS_MST_LNUM
, sz
= c
->mst_node_alsz
;
204 dbg_rcvry("recovery");
206 save_flags
= mst
->flags
;
207 mst
->flags
|= cpu_to_le32(UBIFS_MST_RCVRY
);
209 ubifs_prepare_node(c
, mst
, UBIFS_MST_NODE_SZ
, 1);
210 err
= ubifs_leb_change(c
, lnum
, mst
, sz
);
213 err
= ubifs_leb_change(c
, lnum
+ 1, mst
, sz
);
217 mst
->flags
= save_flags
;
222 * ubifs_recover_master_node - recover the master node.
223 * @c: UBIFS file-system description object
225 * This function recovers the master node from corruption that may occur due to
226 * an unclean unmount.
228 * This function returns %0 on success and a negative error code on failure.
230 int ubifs_recover_master_node(struct ubifs_info
*c
)
232 void *buf1
= NULL
, *buf2
= NULL
, *cor1
= NULL
, *cor2
= NULL
;
233 struct ubifs_mst_node
*mst1
= NULL
, *mst2
= NULL
, *mst
;
234 const int sz
= c
->mst_node_alsz
;
235 int err
, offs1
, offs2
;
237 dbg_rcvry("recovery");
239 err
= get_master_node(c
, UBIFS_MST_LNUM
, &buf1
, &mst1
, &cor1
);
243 err
= get_master_node(c
, UBIFS_MST_LNUM
+ 1, &buf2
, &mst2
, &cor2
);
248 offs1
= (void *)mst1
- buf1
;
249 if ((le32_to_cpu(mst1
->flags
) & UBIFS_MST_RCVRY
) &&
250 (offs1
== 0 && !cor1
)) {
252 * mst1 was written by recovery at offset 0 with no
255 dbg_rcvry("recovery recovery");
258 offs2
= (void *)mst2
- buf2
;
259 if (offs1
== offs2
) {
260 /* Same offset, so must be the same */
261 if (memcmp((void *)mst1
+ UBIFS_CH_SZ
,
262 (void *)mst2
+ UBIFS_CH_SZ
,
263 UBIFS_MST_NODE_SZ
- UBIFS_CH_SZ
))
266 } else if (offs2
+ sz
== offs1
) {
267 /* 1st LEB was written, 2nd was not */
271 } else if (offs1
== 0 &&
272 c
->leb_size
- offs2
- sz
< sz
) {
273 /* 1st LEB was unmapped and written, 2nd not */
281 * 2nd LEB was unmapped and about to be written, so
282 * there must be only one master node in the first LEB
285 if (offs1
!= 0 || cor1
)
293 * 1st LEB was unmapped and about to be written, so there must
294 * be no room left in 2nd LEB.
296 offs2
= (void *)mst2
- buf2
;
297 if (offs2
+ sz
+ sz
<= c
->leb_size
)
302 ubifs_msg("recovered master node from LEB %d",
303 (mst
== mst1
? UBIFS_MST_LNUM
: UBIFS_MST_LNUM
+ 1));
305 memcpy(c
->mst_node
, mst
, UBIFS_MST_NODE_SZ
);
308 /* Read-only mode. Keep a copy for switching to rw mode */
309 c
->rcvrd_mst_node
= kmalloc(sz
, GFP_KERNEL
);
310 if (!c
->rcvrd_mst_node
) {
314 memcpy(c
->rcvrd_mst_node
, c
->mst_node
, UBIFS_MST_NODE_SZ
);
317 * We had to recover the master node, which means there was an
318 * unclean reboot. However, it is possible that the master node
319 * is clean at this point, i.e., %UBIFS_MST_DIRTY is not set.
320 * E.g., consider the following chain of events:
322 * 1. UBIFS was cleanly unmounted, so the master node is clean
323 * 2. UBIFS is being mounted R/W and starts changing the master
324 * node in the first (%UBIFS_MST_LNUM). A power cut happens,
325 * so this LEB ends up with some amount of garbage at the
327 * 3. UBIFS is being mounted R/O. We reach this place and
328 * recover the master node from the second LEB
329 * (%UBIFS_MST_LNUM + 1). But we cannot update the media
330 * because we are being mounted R/O. We have to defer the
332 * 4. However, this master node (@c->mst_node) is marked as
333 * clean (since the step 1). And if we just return, the
334 * mount code will be confused and won't recover the master
335 * node when it is re-mounter R/W later.
337 * Thus, to force the recovery by marking the master node as
340 c
->mst_node
->flags
|= cpu_to_le32(UBIFS_MST_DIRTY
);
343 /* Write the recovered master node */
344 c
->max_sqnum
= le64_to_cpu(mst
->ch
.sqnum
) - 1;
345 err
= write_rcvrd_mst_node(c
, c
->mst_node
);
359 ubifs_err("failed to recover master node");
361 ubifs_err("dumping first master node");
362 ubifs_dump_node(c
, mst1
);
365 ubifs_err("dumping second master node");
366 ubifs_dump_node(c
, mst2
);
374 * ubifs_write_rcvrd_mst_node - write the recovered master node.
375 * @c: UBIFS file-system description object
377 * This function writes the master node that was recovered during mounting in
378 * read-only mode and must now be written because we are remounting rw.
380 * This function returns %0 on success and a negative error code on failure.
382 int ubifs_write_rcvrd_mst_node(struct ubifs_info
*c
)
386 if (!c
->rcvrd_mst_node
)
388 c
->rcvrd_mst_node
->flags
|= cpu_to_le32(UBIFS_MST_DIRTY
);
389 c
->mst_node
->flags
|= cpu_to_le32(UBIFS_MST_DIRTY
);
390 err
= write_rcvrd_mst_node(c
, c
->rcvrd_mst_node
);
393 kfree(c
->rcvrd_mst_node
);
394 c
->rcvrd_mst_node
= NULL
;
399 * is_last_write - determine if an offset was in the last write to a LEB.
400 * @c: UBIFS file-system description object
401 * @buf: buffer to check
402 * @offs: offset to check
404 * This function returns %1 if @offs was in the last write to the LEB whose data
405 * is in @buf, otherwise %0 is returned. The determination is made by checking
406 * for subsequent empty space starting from the next @c->max_write_size
409 static int is_last_write(const struct ubifs_info
*c
, void *buf
, int offs
)
411 int empty_offs
, check_len
;
415 * Round up to the next @c->max_write_size boundary i.e. @offs is in
416 * the last wbuf written. After that should be empty space.
418 empty_offs
= ALIGN(offs
+ 1, c
->max_write_size
);
419 check_len
= c
->leb_size
- empty_offs
;
420 p
= buf
+ empty_offs
- offs
;
421 return is_empty(p
, check_len
);
425 * clean_buf - clean the data from an LEB sitting in a buffer.
426 * @c: UBIFS file-system description object
427 * @buf: buffer to clean
428 * @lnum: LEB number to clean
429 * @offs: offset from which to clean
430 * @len: length of buffer
432 * This function pads up to the next min_io_size boundary (if there is one) and
433 * sets empty space to all 0xff. @buf, @offs and @len are updated to the next
434 * @c->min_io_size boundary.
436 static void clean_buf(const struct ubifs_info
*c
, void **buf
, int lnum
,
439 int empty_offs
, pad_len
;
442 dbg_rcvry("cleaning corruption at %d:%d", lnum
, *offs
);
444 ubifs_assert(!(*offs
& 7));
445 empty_offs
= ALIGN(*offs
, c
->min_io_size
);
446 pad_len
= empty_offs
- *offs
;
447 ubifs_pad(c
, *buf
, pad_len
);
451 memset(*buf
, 0xff, c
->leb_size
- empty_offs
);
455 * no_more_nodes - determine if there are no more nodes in a buffer.
456 * @c: UBIFS file-system description object
457 * @buf: buffer to check
458 * @len: length of buffer
459 * @lnum: LEB number of the LEB from which @buf was read
460 * @offs: offset from which @buf was read
462 * This function ensures that the corrupted node at @offs is the last thing
463 * written to a LEB. This function returns %1 if more data is not found and
464 * %0 if more data is found.
466 static int no_more_nodes(const struct ubifs_info
*c
, void *buf
, int len
,
469 struct ubifs_ch
*ch
= buf
;
470 int skip
, dlen
= le32_to_cpu(ch
->len
);
472 /* Check for empty space after the corrupt node's common header */
473 skip
= ALIGN(offs
+ UBIFS_CH_SZ
, c
->max_write_size
) - offs
;
474 if (is_empty(buf
+ skip
, len
- skip
))
477 * The area after the common header size is not empty, so the common
478 * header must be intact. Check it.
480 if (ubifs_check_node(c
, buf
, lnum
, offs
, 1, 0) != -EUCLEAN
) {
481 dbg_rcvry("unexpected bad common header at %d:%d", lnum
, offs
);
484 /* Now we know the corrupt node's length we can skip over it */
485 skip
= ALIGN(offs
+ dlen
, c
->max_write_size
) - offs
;
486 /* After which there should be empty space */
487 if (is_empty(buf
+ skip
, len
- skip
))
489 dbg_rcvry("unexpected data at %d:%d", lnum
, offs
+ skip
);
494 * fix_unclean_leb - fix an unclean LEB.
495 * @c: UBIFS file-system description object
496 * @sleb: scanned LEB information
497 * @start: offset where scan started
499 static int fix_unclean_leb(struct ubifs_info
*c
, struct ubifs_scan_leb
*sleb
,
502 int lnum
= sleb
->lnum
, endpt
= start
;
504 /* Get the end offset of the last node we are keeping */
505 if (!list_empty(&sleb
->nodes
)) {
506 struct ubifs_scan_node
*snod
;
508 snod
= list_entry(sleb
->nodes
.prev
,
509 struct ubifs_scan_node
, list
);
510 endpt
= snod
->offs
+ snod
->len
;
513 if (c
->ro_mount
&& !c
->remounting_rw
) {
514 /* Add to recovery list */
515 struct ubifs_unclean_leb
*ucleb
;
517 dbg_rcvry("need to fix LEB %d start %d endpt %d",
518 lnum
, start
, sleb
->endpt
);
519 ucleb
= kzalloc(sizeof(struct ubifs_unclean_leb
), GFP_NOFS
);
523 ucleb
->endpt
= endpt
;
524 list_add_tail(&ucleb
->list
, &c
->unclean_leb_list
);
527 /* Write the fixed LEB back to flash */
530 dbg_rcvry("fixing LEB %d start %d endpt %d",
531 lnum
, start
, sleb
->endpt
);
533 err
= ubifs_leb_unmap(c
, lnum
);
537 int len
= ALIGN(endpt
, c
->min_io_size
);
540 err
= ubifs_leb_read(c
, lnum
, sleb
->buf
, 0,
545 /* Pad to min_io_size */
547 int pad_len
= len
- ALIGN(endpt
, 8);
550 void *buf
= sleb
->buf
+ len
- pad_len
;
552 ubifs_pad(c
, buf
, pad_len
);
555 err
= ubifs_leb_change(c
, lnum
, sleb
->buf
, len
);
565 * drop_last_group - drop the last group of nodes.
566 * @sleb: scanned LEB information
567 * @offs: offset of dropped nodes is returned here
569 * This is a helper function for 'ubifs_recover_leb()' which drops the last
570 * group of nodes of the scanned LEB.
572 static void drop_last_group(struct ubifs_scan_leb
*sleb
, int *offs
)
574 while (!list_empty(&sleb
->nodes
)) {
575 struct ubifs_scan_node
*snod
;
578 snod
= list_entry(sleb
->nodes
.prev
, struct ubifs_scan_node
,
581 if (ch
->group_type
!= UBIFS_IN_NODE_GROUP
)
584 dbg_rcvry("dropping grouped node at %d:%d",
585 sleb
->lnum
, snod
->offs
);
587 list_del(&snod
->list
);
589 sleb
->nodes_cnt
-= 1;
594 * drop_last_node - drop the last node.
595 * @sleb: scanned LEB information
596 * @offs: offset of dropped nodes is returned here
597 * @grouped: non-zero if whole group of nodes have to be dropped
599 * This is a helper function for 'ubifs_recover_leb()' which drops the last
600 * node of the scanned LEB.
602 static void drop_last_node(struct ubifs_scan_leb
*sleb
, int *offs
)
604 struct ubifs_scan_node
*snod
;
606 if (!list_empty(&sleb
->nodes
)) {
607 snod
= list_entry(sleb
->nodes
.prev
, struct ubifs_scan_node
,
610 dbg_rcvry("dropping last node at %d:%d",
611 sleb
->lnum
, snod
->offs
);
613 list_del(&snod
->list
);
615 sleb
->nodes_cnt
-= 1;
620 * ubifs_recover_leb - scan and recover a LEB.
621 * @c: UBIFS file-system description object
624 * @sbuf: LEB-sized buffer to use
625 * @jhead: journal head number this LEB belongs to (%-1 if the LEB does not
626 * belong to any journal head)
628 * This function does a scan of a LEB, but caters for errors that might have
629 * been caused by the unclean unmount from which we are attempting to recover.
630 * Returns %0 in case of success, %-EUCLEAN if an unrecoverable corruption is
631 * found, and a negative error code in case of failure.
633 struct ubifs_scan_leb
*ubifs_recover_leb(struct ubifs_info
*c
, int lnum
,
634 int offs
, void *sbuf
, int jhead
)
636 int ret
= 0, err
, len
= c
->leb_size
- offs
, start
= offs
, min_io_unit
;
637 int grouped
= jhead
== -1 ? 0 : c
->jheads
[jhead
].grouped
;
638 struct ubifs_scan_leb
*sleb
;
639 void *buf
= sbuf
+ offs
;
641 dbg_rcvry("%d:%d, jhead %d, grouped %d", lnum
, offs
, jhead
, grouped
);
643 sleb
= ubifs_start_scan(c
, lnum
, offs
, sbuf
);
647 ubifs_assert(len
>= 8);
649 dbg_scan("look at LEB %d:%d (%d bytes left)",
655 * Scan quietly until there is an error from which we cannot
658 ret
= ubifs_scan_a_node(c
, buf
, len
, lnum
, offs
, 1);
659 if (ret
== SCANNED_A_NODE
) {
660 /* A valid node, and not a padding node */
661 struct ubifs_ch
*ch
= buf
;
664 err
= ubifs_add_snod(c
, sleb
, buf
, offs
);
667 node_len
= ALIGN(le32_to_cpu(ch
->len
), 8);
671 } else if (ret
> 0) {
672 /* Padding bytes or a valid padding node */
676 } else if (ret
== SCANNED_EMPTY_SPACE
||
677 ret
== SCANNED_GARBAGE
||
678 ret
== SCANNED_A_BAD_PAD_NODE
||
679 ret
== SCANNED_A_CORRUPT_NODE
) {
680 dbg_rcvry("found corruption (%d) at %d:%d",
684 ubifs_err("unexpected return value %d", ret
);
690 if (ret
== SCANNED_GARBAGE
|| ret
== SCANNED_A_BAD_PAD_NODE
) {
691 if (!is_last_write(c
, buf
, offs
))
692 goto corrupted_rescan
;
693 } else if (ret
== SCANNED_A_CORRUPT_NODE
) {
694 if (!no_more_nodes(c
, buf
, len
, lnum
, offs
))
695 goto corrupted_rescan
;
696 } else if (!is_empty(buf
, len
)) {
697 if (!is_last_write(c
, buf
, offs
)) {
698 int corruption
= first_non_ff(buf
, len
);
701 * See header comment for this file for more
702 * explanations about the reasons we have this check.
704 ubifs_err("corrupt empty space LEB %d:%d, corruption starts at %d",
705 lnum
, offs
, corruption
);
706 /* Make sure we dump interesting non-0xFF data */
713 min_io_unit
= round_down(offs
, c
->min_io_size
);
716 * If nodes are grouped, always drop the incomplete group at
719 drop_last_group(sleb
, &offs
);
723 * If this LEB belongs to the GC head then while we are in the
724 * middle of the same min. I/O unit keep dropping nodes. So
725 * basically, what we want is to make sure that the last min.
726 * I/O unit where we saw the corruption is dropped completely
727 * with all the uncorrupted nodes which may possibly sit there.
729 * In other words, let's name the min. I/O unit where the
730 * corruption starts B, and the previous min. I/O unit A. The
731 * below code tries to deal with a situation when half of B
732 * contains valid nodes or the end of a valid node, and the
733 * second half of B contains corrupted data or garbage. This
734 * means that UBIFS had been writing to B just before the power
735 * cut happened. I do not know how realistic is this scenario
736 * that half of the min. I/O unit had been written successfully
737 * and the other half not, but this is possible in our 'failure
738 * mode emulation' infrastructure at least.
740 * So what is the problem, why we need to drop those nodes? Why
741 * can't we just clean-up the second half of B by putting a
742 * padding node there? We can, and this works fine with one
743 * exception which was reproduced with power cut emulation
744 * testing and happens extremely rarely.
746 * Imagine the file-system is full, we run GC which starts
747 * moving valid nodes from LEB X to LEB Y (obviously, LEB Y is
748 * the current GC head LEB). The @c->gc_lnum is -1, which means
749 * that GC will retain LEB X and will try to continue. Imagine
750 * that LEB X is currently the dirtiest LEB, and the amount of
751 * used space in LEB Y is exactly the same as amount of free
754 * And a power cut happens when nodes are moved from LEB X to
755 * LEB Y. We are here trying to recover LEB Y which is the GC
756 * head LEB. We find the min. I/O unit B as described above.
757 * Then we clean-up LEB Y by padding min. I/O unit. And later
758 * 'ubifs_rcvry_gc_commit()' function fails, because it cannot
759 * find a dirty LEB which could be GC'd into LEB Y! Even LEB X
760 * does not match because the amount of valid nodes there does
761 * not fit the free space in LEB Y any more! And this is
762 * because of the padding node which we added to LEB Y. The
763 * user-visible effect of this which I once observed and
764 * analysed is that we cannot mount the file-system with
767 * So obviously, to make sure that situation does not happen we
768 * should free min. I/O unit B in LEB Y completely and the last
769 * used min. I/O unit in LEB Y should be A. This is basically
770 * what the below code tries to do.
772 while (offs
> min_io_unit
)
773 drop_last_node(sleb
, &offs
);
777 len
= c
->leb_size
- offs
;
779 clean_buf(c
, &buf
, lnum
, &offs
, &len
);
780 ubifs_end_scan(c
, sleb
, lnum
, offs
);
782 err
= fix_unclean_leb(c
, sleb
, start
);
789 /* Re-scan the corrupted data with verbose messages */
790 ubifs_err("corruption %d", ret
);
791 ubifs_scan_a_node(c
, buf
, len
, lnum
, offs
, 1);
793 ubifs_scanned_corruption(c
, lnum
, offs
, buf
);
796 ubifs_err("LEB %d scanning failed", lnum
);
797 ubifs_scan_destroy(sleb
);
802 * get_cs_sqnum - get commit start sequence number.
803 * @c: UBIFS file-system description object
804 * @lnum: LEB number of commit start node
805 * @offs: offset of commit start node
806 * @cs_sqnum: commit start sequence number is returned here
808 * This function returns %0 on success and a negative error code on failure.
810 static int get_cs_sqnum(struct ubifs_info
*c
, int lnum
, int offs
,
811 unsigned long long *cs_sqnum
)
813 struct ubifs_cs_node
*cs_node
= NULL
;
816 dbg_rcvry("at %d:%d", lnum
, offs
);
817 cs_node
= kmalloc(UBIFS_CS_NODE_SZ
, GFP_KERNEL
);
820 if (c
->leb_size
- offs
< UBIFS_CS_NODE_SZ
)
822 err
= ubifs_leb_read(c
, lnum
, (void *)cs_node
, offs
,
823 UBIFS_CS_NODE_SZ
, 0);
824 if (err
&& err
!= -EBADMSG
)
826 ret
= ubifs_scan_a_node(c
, cs_node
, UBIFS_CS_NODE_SZ
, lnum
, offs
, 0);
827 if (ret
!= SCANNED_A_NODE
) {
828 ubifs_err("Not a valid node");
831 if (cs_node
->ch
.node_type
!= UBIFS_CS_NODE
) {
832 ubifs_err("Node a CS node, type is %d", cs_node
->ch
.node_type
);
835 if (le64_to_cpu(cs_node
->cmt_no
) != c
->cmt_no
) {
836 ubifs_err("CS node cmt_no %llu != current cmt_no %llu",
837 (unsigned long long)le64_to_cpu(cs_node
->cmt_no
),
841 *cs_sqnum
= le64_to_cpu(cs_node
->ch
.sqnum
);
842 dbg_rcvry("commit start sqnum %llu", *cs_sqnum
);
849 ubifs_err("failed to get CS sqnum");
855 * ubifs_recover_log_leb - scan and recover a log LEB.
856 * @c: UBIFS file-system description object
859 * @sbuf: LEB-sized buffer to use
861 * This function does a scan of a LEB, but caters for errors that might have
862 * been caused by unclean reboots from which we are attempting to recover
863 * (assume that only the last log LEB can be corrupted by an unclean reboot).
865 * This function returns %0 on success and a negative error code on failure.
867 struct ubifs_scan_leb
*ubifs_recover_log_leb(struct ubifs_info
*c
, int lnum
,
868 int offs
, void *sbuf
)
870 struct ubifs_scan_leb
*sleb
;
873 dbg_rcvry("LEB %d", lnum
);
874 next_lnum
= lnum
+ 1;
875 if (next_lnum
>= UBIFS_LOG_LNUM
+ c
->log_lebs
)
876 next_lnum
= UBIFS_LOG_LNUM
;
877 if (next_lnum
!= c
->ltail_lnum
) {
879 * We can only recover at the end of the log, so check that the
880 * next log LEB is empty or out of date.
882 sleb
= ubifs_scan(c
, next_lnum
, 0, sbuf
, 0);
885 if (sleb
->nodes_cnt
) {
886 struct ubifs_scan_node
*snod
;
887 unsigned long long cs_sqnum
= c
->cs_sqnum
;
889 snod
= list_entry(sleb
->nodes
.next
,
890 struct ubifs_scan_node
, list
);
894 err
= get_cs_sqnum(c
, lnum
, offs
, &cs_sqnum
);
896 ubifs_scan_destroy(sleb
);
900 if (snod
->sqnum
> cs_sqnum
) {
901 ubifs_err("unrecoverable log corruption in LEB %d",
903 ubifs_scan_destroy(sleb
);
904 return ERR_PTR(-EUCLEAN
);
907 ubifs_scan_destroy(sleb
);
909 return ubifs_recover_leb(c
, lnum
, offs
, sbuf
, -1);
913 * recover_head - recover a head.
914 * @c: UBIFS file-system description object
915 * @lnum: LEB number of head to recover
916 * @offs: offset of head to recover
917 * @sbuf: LEB-sized buffer to use
919 * This function ensures that there is no data on the flash at a head location.
921 * This function returns %0 on success and a negative error code on failure.
923 static int recover_head(struct ubifs_info
*c
, int lnum
, int offs
, void *sbuf
)
925 int len
= c
->max_write_size
, err
;
927 if (offs
+ len
> c
->leb_size
)
928 len
= c
->leb_size
- offs
;
933 /* Read at the head location and check it is empty flash */
934 err
= ubifs_leb_read(c
, lnum
, sbuf
, offs
, len
, 1);
935 if (err
|| !is_empty(sbuf
, len
)) {
936 dbg_rcvry("cleaning head at %d:%d", lnum
, offs
);
938 return ubifs_leb_unmap(c
, lnum
);
939 err
= ubifs_leb_read(c
, lnum
, sbuf
, 0, offs
, 1);
942 return ubifs_leb_change(c
, lnum
, sbuf
, offs
);
949 * ubifs_recover_inl_heads - recover index and LPT heads.
950 * @c: UBIFS file-system description object
951 * @sbuf: LEB-sized buffer to use
953 * This function ensures that there is no data on the flash at the index and
954 * LPT head locations.
956 * This deals with the recovery of a half-completed journal commit. UBIFS is
957 * careful never to overwrite the last version of the index or the LPT. Because
958 * the index and LPT are wandering trees, data from a half-completed commit will
959 * not be referenced anywhere in UBIFS. The data will be either in LEBs that are
960 * assumed to be empty and will be unmapped anyway before use, or in the index
963 * This function returns %0 on success and a negative error code on failure.
965 int ubifs_recover_inl_heads(struct ubifs_info
*c
, void *sbuf
)
969 ubifs_assert(!c
->ro_mount
|| c
->remounting_rw
);
971 dbg_rcvry("checking index head at %d:%d", c
->ihead_lnum
, c
->ihead_offs
);
972 err
= recover_head(c
, c
->ihead_lnum
, c
->ihead_offs
, sbuf
);
976 dbg_rcvry("checking LPT head at %d:%d", c
->nhead_lnum
, c
->nhead_offs
);
977 err
= recover_head(c
, c
->nhead_lnum
, c
->nhead_offs
, sbuf
);
985 * clean_an_unclean_leb - read and write a LEB to remove corruption.
986 * @c: UBIFS file-system description object
987 * @ucleb: unclean LEB information
988 * @sbuf: LEB-sized buffer to use
990 * This function reads a LEB up to a point pre-determined by the mount recovery,
991 * checks the nodes, and writes the result back to the flash, thereby cleaning
992 * off any following corruption, or non-fatal ECC errors.
994 * This function returns %0 on success and a negative error code on failure.
996 static int clean_an_unclean_leb(struct ubifs_info
*c
,
997 struct ubifs_unclean_leb
*ucleb
, void *sbuf
)
999 int err
, lnum
= ucleb
->lnum
, offs
= 0, len
= ucleb
->endpt
, quiet
= 1;
1002 dbg_rcvry("LEB %d len %d", lnum
, len
);
1005 /* Nothing to read, just unmap it */
1006 err
= ubifs_leb_unmap(c
, lnum
);
1012 err
= ubifs_leb_read(c
, lnum
, buf
, offs
, len
, 0);
1013 if (err
&& err
!= -EBADMSG
)
1021 /* Scan quietly until there is an error */
1022 ret
= ubifs_scan_a_node(c
, buf
, len
, lnum
, offs
, quiet
);
1024 if (ret
== SCANNED_A_NODE
) {
1025 /* A valid node, and not a padding node */
1026 struct ubifs_ch
*ch
= buf
;
1029 node_len
= ALIGN(le32_to_cpu(ch
->len
), 8);
1037 /* Padding bytes or a valid padding node */
1044 if (ret
== SCANNED_EMPTY_SPACE
) {
1045 ubifs_err("unexpected empty space at %d:%d",
1051 /* Redo the last scan but noisily */
1056 ubifs_scanned_corruption(c
, lnum
, offs
, buf
);
1060 /* Pad to min_io_size */
1061 len
= ALIGN(ucleb
->endpt
, c
->min_io_size
);
1062 if (len
> ucleb
->endpt
) {
1063 int pad_len
= len
- ALIGN(ucleb
->endpt
, 8);
1066 buf
= c
->sbuf
+ len
- pad_len
;
1067 ubifs_pad(c
, buf
, pad_len
);
1071 /* Write back the LEB atomically */
1072 err
= ubifs_leb_change(c
, lnum
, sbuf
, len
);
1076 dbg_rcvry("cleaned LEB %d", lnum
);
1082 * ubifs_clean_lebs - clean LEBs recovered during read-only mount.
1083 * @c: UBIFS file-system description object
1084 * @sbuf: LEB-sized buffer to use
1086 * This function cleans a LEB identified during recovery that needs to be
1087 * written but was not because UBIFS was mounted read-only. This happens when
1088 * remounting to read-write mode.
1090 * This function returns %0 on success and a negative error code on failure.
1092 int ubifs_clean_lebs(struct ubifs_info
*c
, void *sbuf
)
1094 dbg_rcvry("recovery");
1095 while (!list_empty(&c
->unclean_leb_list
)) {
1096 struct ubifs_unclean_leb
*ucleb
;
1099 ucleb
= list_entry(c
->unclean_leb_list
.next
,
1100 struct ubifs_unclean_leb
, list
);
1101 err
= clean_an_unclean_leb(c
, ucleb
, sbuf
);
1104 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
);
1238 int ubifs_rcvry_gc_commit(struct ubifs_info
*c
)
1245 * struct size_entry - inode size information for recovery.
1246 * @rb: link in the RB-tree of sizes
1247 * @inum: inode number
1248 * @i_size: size on inode
1249 * @d_size: maximum size based on data nodes
1250 * @exists: indicates whether the inode exists
1251 * @inode: inode if pinned in memory awaiting rw mode to fix it
1259 struct inode
*inode
;
1263 * add_ino - add an entry to the size tree.
1264 * @c: UBIFS file-system description object
1265 * @inum: inode number
1266 * @i_size: size on inode
1267 * @d_size: maximum size based on data nodes
1268 * @exists: indicates whether the inode exists
1270 static int add_ino(struct ubifs_info
*c
, ino_t inum
, loff_t i_size
,
1271 loff_t d_size
, int exists
)
1273 struct rb_node
**p
= &c
->size_tree
.rb_node
, *parent
= NULL
;
1274 struct size_entry
*e
;
1278 e
= rb_entry(parent
, struct size_entry
, rb
);
1282 p
= &(*p
)->rb_right
;
1285 e
= kzalloc(sizeof(struct size_entry
), GFP_KERNEL
);
1294 rb_link_node(&e
->rb
, parent
, p
);
1295 rb_insert_color(&e
->rb
, &c
->size_tree
);
1301 * find_ino - find an entry on the size tree.
1302 * @c: UBIFS file-system description object
1303 * @inum: inode number
1305 static struct size_entry
*find_ino(struct ubifs_info
*c
, ino_t inum
)
1307 struct rb_node
*p
= c
->size_tree
.rb_node
;
1308 struct size_entry
*e
;
1311 e
= rb_entry(p
, struct size_entry
, rb
);
1314 else if (inum
> e
->inum
)
1323 * remove_ino - remove an entry from the size tree.
1324 * @c: UBIFS file-system description object
1325 * @inum: inode number
1327 static void remove_ino(struct ubifs_info
*c
, ino_t inum
)
1329 struct size_entry
*e
= find_ino(c
, inum
);
1333 rb_erase(&e
->rb
, &c
->size_tree
);
1338 * ubifs_destroy_size_tree - free resources related to the size tree.
1339 * @c: UBIFS file-system description object
1341 void ubifs_destroy_size_tree(struct ubifs_info
*c
)
1343 struct size_entry
*e
, *n
;
1345 rbtree_postorder_for_each_entry_safe(e
, n
, &c
->size_tree
, rb
) {
1351 c
->size_tree
= RB_ROOT
;
1355 * ubifs_recover_size_accum - accumulate inode sizes for recovery.
1356 * @c: UBIFS file-system description object
1358 * @deletion: node is for a deletion
1359 * @new_size: inode size
1361 * This function has two purposes:
1362 * 1) to ensure there are no data nodes that fall outside the inode size
1363 * 2) to ensure there are no data nodes for inodes that do not exist
1364 * To accomplish those purposes, a rb-tree is constructed containing an entry
1365 * for each inode number in the journal that has not been deleted, and recording
1366 * the size from the inode node, the maximum size of any data node (also altered
1367 * by truncations) and a flag indicating a inode number for which no inode node
1368 * was present in the journal.
1370 * Note that there is still the possibility that there are data nodes that have
1371 * been committed that are beyond the inode size, however the only way to find
1372 * them would be to scan the entire index. Alternatively, some provision could
1373 * be made to record the size of inodes at the start of commit, which would seem
1374 * very cumbersome for a scenario that is quite unlikely and the only negative
1375 * consequence of which is wasted space.
1377 * This functions returns %0 on success and a negative error code on failure.
1379 int ubifs_recover_size_accum(struct ubifs_info
*c
, union ubifs_key
*key
,
1380 int deletion
, loff_t new_size
)
1382 ino_t inum
= key_inum(c
, key
);
1383 struct size_entry
*e
;
1386 switch (key_type(c
, key
)) {
1389 remove_ino(c
, inum
);
1391 e
= find_ino(c
, inum
);
1393 e
->i_size
= new_size
;
1396 err
= add_ino(c
, inum
, new_size
, 0, 1);
1402 case UBIFS_DATA_KEY
:
1403 e
= find_ino(c
, inum
);
1405 if (new_size
> e
->d_size
)
1406 e
->d_size
= new_size
;
1408 err
= add_ino(c
, inum
, 0, new_size
, 0);
1413 case UBIFS_TRUN_KEY
:
1414 e
= find_ino(c
, inum
);
1416 e
->d_size
= new_size
;
1424 * fix_size_in_place - fix inode size in place on flash.
1425 * @c: UBIFS file-system description object
1426 * @e: inode size information for recovery
1428 static int fix_size_in_place(struct ubifs_info
*c
, struct size_entry
*e
)
1430 struct ubifs_ino_node
*ino
= c
->sbuf
;
1432 union ubifs_key key
;
1433 int err
, lnum
, offs
, len
;
1437 /* Locate the inode node LEB number and offset */
1438 ino_key_init(c
, &key
, e
->inum
);
1439 err
= ubifs_tnc_locate(c
, &key
, ino
, &lnum
, &offs
);
1443 * If the size recorded on the inode node is greater than the size that
1444 * was calculated from nodes in the journal then don't change the inode.
1446 i_size
= le64_to_cpu(ino
->size
);
1447 if (i_size
>= e
->d_size
)
1450 err
= ubifs_leb_read(c
, lnum
, c
->sbuf
, 0, c
->leb_size
, 1);
1453 /* Change the size field and recalculate the CRC */
1454 ino
= c
->sbuf
+ offs
;
1455 ino
->size
= cpu_to_le64(e
->d_size
);
1456 len
= le32_to_cpu(ino
->ch
.len
);
1457 crc
= crc32(UBIFS_CRC32_INIT
, (void *)ino
+ 8, len
- 8);
1458 ino
->ch
.crc
= cpu_to_le32(crc
);
1459 /* Work out where data in the LEB ends and free space begins */
1461 len
= c
->leb_size
- 1;
1462 while (p
[len
] == 0xff)
1464 len
= ALIGN(len
+ 1, c
->min_io_size
);
1465 /* Atomically write the fixed LEB back again */
1466 err
= ubifs_leb_change(c
, lnum
, c
->sbuf
, len
);
1469 dbg_rcvry("inode %lu at %d:%d size %lld -> %lld",
1470 (unsigned long)e
->inum
, lnum
, offs
, i_size
, e
->d_size
);
1474 ubifs_warn("inode %lu failed to fix size %lld -> %lld error %d",
1475 (unsigned long)e
->inum
, e
->i_size
, e
->d_size
, err
);
1481 * ubifs_recover_size - recover inode size.
1482 * @c: UBIFS file-system description object
1484 * This function attempts to fix inode size discrepancies identified by the
1485 * 'ubifs_recover_size_accum()' function.
1487 * This functions returns %0 on success and a negative error code on failure.
1489 int ubifs_recover_size(struct ubifs_info
*c
)
1491 struct rb_node
*this = rb_first(&c
->size_tree
);
1494 struct size_entry
*e
;
1497 e
= rb_entry(this, struct size_entry
, rb
);
1499 union ubifs_key key
;
1501 ino_key_init(c
, &key
, e
->inum
);
1502 err
= ubifs_tnc_lookup(c
, &key
, c
->sbuf
);
1503 if (err
&& err
!= -ENOENT
)
1505 if (err
== -ENOENT
) {
1506 /* Remove data nodes that have no inode */
1507 dbg_rcvry("removing ino %lu",
1508 (unsigned long)e
->inum
);
1509 err
= ubifs_tnc_remove_ino(c
, e
->inum
);
1513 struct ubifs_ino_node
*ino
= c
->sbuf
;
1516 e
->i_size
= le64_to_cpu(ino
->size
);
1520 if (e
->exists
&& e
->i_size
< e
->d_size
) {
1522 /* Fix the inode size and pin it in memory */
1523 struct inode
*inode
;
1524 struct ubifs_inode
*ui
;
1526 ubifs_assert(!e
->inode
);
1528 inode
= ubifs_iget(c
->vfs_sb
, e
->inum
);
1530 return PTR_ERR(inode
);
1532 ui
= ubifs_inode(inode
);
1533 if (inode
->i_size
< e
->d_size
) {
1534 dbg_rcvry("ino %lu size %lld -> %lld",
1535 (unsigned long)e
->inum
,
1536 inode
->i_size
, e
->d_size
);
1537 inode
->i_size
= e
->d_size
;
1538 ui
->ui_size
= e
->d_size
;
1539 ui
->synced_i_size
= e
->d_size
;
1541 this = rb_next(this);
1547 /* Fix the size in place */
1548 err
= fix_size_in_place(c
, e
);
1557 this = rb_next(this);
1558 rb_erase(&e
->rb
, &c
->size_tree
);