]>
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
40 #include <linux/crc32.h>
41 #include <linux/slab.h>
43 #include <linux/err.h>
48 * is_empty - determine whether a buffer is empty (contains all 0xff).
49 * @buf: buffer to clean
50 * @len: length of buffer
52 * This function returns %1 if the buffer is empty (contains all 0xff) otherwise
55 static int is_empty(void *buf
, int len
)
60 for (i
= 0; i
< len
; i
++)
67 * first_non_ff - find offset of the first non-0xff byte.
68 * @buf: buffer to search in
69 * @len: length of buffer
71 * This function returns offset of the first non-0xff byte in @buf or %-1 if
72 * the buffer contains only 0xff bytes.
74 static int first_non_ff(void *buf
, int len
)
79 for (i
= 0; i
< len
; i
++)
86 * get_master_node - get the last valid master node allowing for corruption.
87 * @c: UBIFS file-system description object
89 * @pbuf: buffer containing the LEB read, is returned here
90 * @mst: master node, if found, is returned here
91 * @cor: corruption, if found, is returned here
93 * This function allocates a buffer, reads the LEB into it, and finds and
94 * returns the last valid master node allowing for one area of corruption.
95 * The corrupt area, if there is one, must be consistent with the assumption
96 * that it is the result of an unclean unmount while the master node was being
97 * written. Under those circumstances, it is valid to use the previously written
100 * This function returns %0 on success and a negative error code on failure.
102 static int get_master_node(const struct ubifs_info
*c
, int lnum
, void **pbuf
,
103 struct ubifs_mst_node
**mst
, void **cor
)
105 const int sz
= c
->mst_node_alsz
;
109 sbuf
= vmalloc(c
->leb_size
);
113 err
= ubifs_leb_read(c
, lnum
, sbuf
, 0, c
->leb_size
, 0);
114 if (err
&& err
!= -EBADMSG
)
117 /* Find the first position that is definitely not a node */
121 while (offs
+ UBIFS_MST_NODE_SZ
<= c
->leb_size
) {
122 struct ubifs_ch
*ch
= buf
;
124 if (le32_to_cpu(ch
->magic
) != UBIFS_NODE_MAGIC
)
130 /* See if there was a valid master node before that */
137 ret
= ubifs_scan_a_node(c
, buf
, len
, lnum
, offs
, 1);
138 if (ret
!= SCANNED_A_NODE
&& offs
) {
139 /* Could have been corruption so check one place back */
143 ret
= ubifs_scan_a_node(c
, buf
, len
, lnum
, offs
, 1);
144 if (ret
!= SCANNED_A_NODE
)
146 * We accept only one area of corruption because
147 * we are assuming that it was caused while
148 * trying to write a master node.
152 if (ret
== SCANNED_A_NODE
) {
153 struct ubifs_ch
*ch
= buf
;
155 if (ch
->node_type
!= UBIFS_MST_NODE
)
157 dbg_rcvry("found a master node at %d:%d", lnum
, offs
);
164 /* Check for corruption */
165 if (offs
< c
->leb_size
) {
166 if (!is_empty(buf
, min_t(int, len
, sz
))) {
168 dbg_rcvry("found corruption at %d:%d", lnum
, offs
);
174 /* Check remaining empty space */
175 if (offs
< c
->leb_size
)
176 if (!is_empty(buf
, len
))
191 * write_rcvrd_mst_node - write recovered master node.
192 * @c: UBIFS file-system description object
195 * This function returns %0 on success and a negative error code on failure.
197 static int write_rcvrd_mst_node(struct ubifs_info
*c
,
198 struct ubifs_mst_node
*mst
)
200 int err
= 0, lnum
= UBIFS_MST_LNUM
, sz
= c
->mst_node_alsz
;
203 dbg_rcvry("recovery");
205 save_flags
= mst
->flags
;
206 mst
->flags
|= cpu_to_le32(UBIFS_MST_RCVRY
);
208 ubifs_prepare_node(c
, mst
, UBIFS_MST_NODE_SZ
, 1);
209 err
= ubifs_leb_change(c
, lnum
, mst
, sz
);
212 err
= ubifs_leb_change(c
, lnum
+ 1, mst
, sz
);
216 mst
->flags
= save_flags
;
221 * ubifs_recover_master_node - recover the master node.
222 * @c: UBIFS file-system description object
224 * This function recovers the master node from corruption that may occur due to
225 * an unclean unmount.
227 * This function returns %0 on success and a negative error code on failure.
229 int ubifs_recover_master_node(struct ubifs_info
*c
)
231 void *buf1
= NULL
, *buf2
= NULL
, *cor1
= NULL
, *cor2
= NULL
;
232 struct ubifs_mst_node
*mst1
= NULL
, *mst2
= NULL
, *mst
;
233 const int sz
= c
->mst_node_alsz
;
234 int err
, offs1
, offs2
;
236 dbg_rcvry("recovery");
238 err
= get_master_node(c
, UBIFS_MST_LNUM
, &buf1
, &mst1
, &cor1
);
242 err
= get_master_node(c
, UBIFS_MST_LNUM
+ 1, &buf2
, &mst2
, &cor2
);
247 offs1
= (void *)mst1
- buf1
;
248 if ((le32_to_cpu(mst1
->flags
) & UBIFS_MST_RCVRY
) &&
249 (offs1
== 0 && !cor1
)) {
251 * mst1 was written by recovery at offset 0 with no
254 dbg_rcvry("recovery recovery");
257 offs2
= (void *)mst2
- buf2
;
258 if (offs1
== offs2
) {
259 /* Same offset, so must be the same */
260 if (memcmp((void *)mst1
+ UBIFS_CH_SZ
,
261 (void *)mst2
+ UBIFS_CH_SZ
,
262 UBIFS_MST_NODE_SZ
- UBIFS_CH_SZ
))
265 } else if (offs2
+ sz
== offs1
) {
266 /* 1st LEB was written, 2nd was not */
270 } else if (offs1
== 0 &&
271 c
->leb_size
- offs2
- sz
< sz
) {
272 /* 1st LEB was unmapped and written, 2nd not */
280 * 2nd LEB was unmapped and about to be written, so
281 * there must be only one master node in the first LEB
284 if (offs1
!= 0 || cor1
)
292 * 1st LEB was unmapped and about to be written, so there must
293 * be no room left in 2nd LEB.
295 offs2
= (void *)mst2
- buf2
;
296 if (offs2
+ sz
+ sz
<= c
->leb_size
)
301 ubifs_msg(c
, "recovered master node from LEB %d",
302 (mst
== mst1
? UBIFS_MST_LNUM
: UBIFS_MST_LNUM
+ 1));
304 memcpy(c
->mst_node
, mst
, UBIFS_MST_NODE_SZ
);
307 /* Read-only mode. Keep a copy for switching to rw mode */
308 c
->rcvrd_mst_node
= kmalloc(sz
, GFP_KERNEL
);
309 if (!c
->rcvrd_mst_node
) {
313 memcpy(c
->rcvrd_mst_node
, c
->mst_node
, UBIFS_MST_NODE_SZ
);
316 * We had to recover the master node, which means there was an
317 * unclean reboot. However, it is possible that the master node
318 * is clean at this point, i.e., %UBIFS_MST_DIRTY is not set.
319 * E.g., consider the following chain of events:
321 * 1. UBIFS was cleanly unmounted, so the master node is clean
322 * 2. UBIFS is being mounted R/W and starts changing the master
323 * node in the first (%UBIFS_MST_LNUM). A power cut happens,
324 * so this LEB ends up with some amount of garbage at the
326 * 3. UBIFS is being mounted R/O. We reach this place and
327 * recover the master node from the second LEB
328 * (%UBIFS_MST_LNUM + 1). But we cannot update the media
329 * because we are being mounted R/O. We have to defer the
331 * 4. However, this master node (@c->mst_node) is marked as
332 * clean (since the step 1). And if we just return, the
333 * mount code will be confused and won't recover the master
334 * node when it is re-mounter R/W later.
336 * Thus, to force the recovery by marking the master node as
339 c
->mst_node
->flags
|= cpu_to_le32(UBIFS_MST_DIRTY
);
342 /* Write the recovered master node */
343 c
->max_sqnum
= le64_to_cpu(mst
->ch
.sqnum
) - 1;
344 err
= write_rcvrd_mst_node(c
, c
->mst_node
);
358 ubifs_err(c
, "failed to recover master node");
360 ubifs_err(c
, "dumping first master node");
361 ubifs_dump_node(c
, mst1
);
364 ubifs_err(c
, "dumping second master node");
365 ubifs_dump_node(c
, mst2
);
373 * ubifs_write_rcvrd_mst_node - write the recovered master node.
374 * @c: UBIFS file-system description object
376 * This function writes the master node that was recovered during mounting in
377 * read-only mode and must now be written because we are remounting rw.
379 * This function returns %0 on success and a negative error code on failure.
381 int ubifs_write_rcvrd_mst_node(struct ubifs_info
*c
)
385 if (!c
->rcvrd_mst_node
)
387 c
->rcvrd_mst_node
->flags
|= cpu_to_le32(UBIFS_MST_DIRTY
);
388 c
->mst_node
->flags
|= cpu_to_le32(UBIFS_MST_DIRTY
);
389 err
= write_rcvrd_mst_node(c
, c
->rcvrd_mst_node
);
392 kfree(c
->rcvrd_mst_node
);
393 c
->rcvrd_mst_node
= NULL
;
398 * is_last_write - determine if an offset was in the last write to a LEB.
399 * @c: UBIFS file-system description object
400 * @buf: buffer to check
401 * @offs: offset to check
403 * This function returns %1 if @offs was in the last write to the LEB whose data
404 * is in @buf, otherwise %0 is returned. The determination is made by checking
405 * for subsequent empty space starting from the next @c->max_write_size
408 static int is_last_write(const struct ubifs_info
*c
, void *buf
, int offs
)
410 int empty_offs
, check_len
;
414 * Round up to the next @c->max_write_size boundary i.e. @offs is in
415 * the last wbuf written. After that should be empty space.
417 empty_offs
= ALIGN(offs
+ 1, c
->max_write_size
);
418 check_len
= c
->leb_size
- empty_offs
;
419 p
= buf
+ empty_offs
- offs
;
420 return is_empty(p
, check_len
);
424 * clean_buf - clean the data from an LEB sitting in a buffer.
425 * @c: UBIFS file-system description object
426 * @buf: buffer to clean
427 * @lnum: LEB number to clean
428 * @offs: offset from which to clean
429 * @len: length of buffer
431 * This function pads up to the next min_io_size boundary (if there is one) and
432 * sets empty space to all 0xff. @buf, @offs and @len are updated to the next
433 * @c->min_io_size boundary.
435 static void clean_buf(const struct ubifs_info
*c
, void **buf
, int lnum
,
438 int empty_offs
, pad_len
;
441 dbg_rcvry("cleaning corruption at %d:%d", lnum
, *offs
);
443 ubifs_assert(!(*offs
& 7));
444 empty_offs
= ALIGN(*offs
, c
->min_io_size
);
445 pad_len
= empty_offs
- *offs
;
446 ubifs_pad(c
, *buf
, pad_len
);
450 memset(*buf
, 0xff, c
->leb_size
- empty_offs
);
454 * no_more_nodes - determine if there are no more nodes in a buffer.
455 * @c: UBIFS file-system description object
456 * @buf: buffer to check
457 * @len: length of buffer
458 * @lnum: LEB number of the LEB from which @buf was read
459 * @offs: offset from which @buf was read
461 * This function ensures that the corrupted node at @offs is the last thing
462 * written to a LEB. This function returns %1 if more data is not found and
463 * %0 if more data is found.
465 static int no_more_nodes(const struct ubifs_info
*c
, void *buf
, int len
,
468 struct ubifs_ch
*ch
= buf
;
469 int skip
, dlen
= le32_to_cpu(ch
->len
);
471 /* Check for empty space after the corrupt node's common header */
472 skip
= ALIGN(offs
+ UBIFS_CH_SZ
, c
->max_write_size
) - offs
;
473 if (is_empty(buf
+ skip
, len
- skip
))
476 * The area after the common header size is not empty, so the common
477 * header must be intact. Check it.
479 if (ubifs_check_node(c
, buf
, lnum
, offs
, 1, 0) != -EUCLEAN
) {
480 dbg_rcvry("unexpected bad common header at %d:%d", lnum
, offs
);
483 /* Now we know the corrupt node's length we can skip over it */
484 skip
= ALIGN(offs
+ dlen
, c
->max_write_size
) - offs
;
485 /* After which there should be empty space */
486 if (is_empty(buf
+ skip
, len
- skip
))
488 dbg_rcvry("unexpected data at %d:%d", lnum
, offs
+ skip
);
493 * fix_unclean_leb - fix an unclean LEB.
494 * @c: UBIFS file-system description object
495 * @sleb: scanned LEB information
496 * @start: offset where scan started
498 static int fix_unclean_leb(struct ubifs_info
*c
, struct ubifs_scan_leb
*sleb
,
501 int lnum
= sleb
->lnum
, endpt
= start
;
503 /* Get the end offset of the last node we are keeping */
504 if (!list_empty(&sleb
->nodes
)) {
505 struct ubifs_scan_node
*snod
;
507 snod
= list_entry(sleb
->nodes
.prev
,
508 struct ubifs_scan_node
, list
);
509 endpt
= snod
->offs
+ snod
->len
;
512 if (c
->ro_mount
&& !c
->remounting_rw
) {
513 /* Add to recovery list */
514 struct ubifs_unclean_leb
*ucleb
;
516 dbg_rcvry("need to fix LEB %d start %d endpt %d",
517 lnum
, start
, sleb
->endpt
);
518 ucleb
= kzalloc(sizeof(struct ubifs_unclean_leb
), GFP_NOFS
);
522 ucleb
->endpt
= endpt
;
523 list_add_tail(&ucleb
->list
, &c
->unclean_leb_list
);
526 /* Write the fixed LEB back to flash */
529 dbg_rcvry("fixing LEB %d start %d endpt %d",
530 lnum
, start
, sleb
->endpt
);
532 err
= ubifs_leb_unmap(c
, lnum
);
536 int len
= ALIGN(endpt
, c
->min_io_size
);
539 err
= ubifs_leb_read(c
, lnum
, sleb
->buf
, 0,
544 /* Pad to min_io_size */
546 int pad_len
= len
- ALIGN(endpt
, 8);
549 void *buf
= sleb
->buf
+ len
- pad_len
;
551 ubifs_pad(c
, buf
, pad_len
);
554 err
= ubifs_leb_change(c
, lnum
, sleb
->buf
, len
);
564 * drop_last_group - drop the last group of nodes.
565 * @sleb: scanned LEB information
566 * @offs: offset of dropped nodes is returned here
568 * This is a helper function for 'ubifs_recover_leb()' which drops the last
569 * group of nodes of the scanned LEB.
571 static void drop_last_group(struct ubifs_scan_leb
*sleb
, int *offs
)
573 while (!list_empty(&sleb
->nodes
)) {
574 struct ubifs_scan_node
*snod
;
577 snod
= list_entry(sleb
->nodes
.prev
, struct ubifs_scan_node
,
580 if (ch
->group_type
!= UBIFS_IN_NODE_GROUP
)
583 dbg_rcvry("dropping grouped node at %d:%d",
584 sleb
->lnum
, snod
->offs
);
586 list_del(&snod
->list
);
588 sleb
->nodes_cnt
-= 1;
593 * drop_last_node - drop the last node.
594 * @sleb: scanned LEB information
595 * @offs: offset of dropped nodes is returned here
597 * This is a helper function for 'ubifs_recover_leb()' which drops the last
598 * node of the scanned LEB.
600 static void drop_last_node(struct ubifs_scan_leb
*sleb
, int *offs
)
602 struct ubifs_scan_node
*snod
;
604 if (!list_empty(&sleb
->nodes
)) {
605 snod
= list_entry(sleb
->nodes
.prev
, struct ubifs_scan_node
,
608 dbg_rcvry("dropping last node at %d:%d",
609 sleb
->lnum
, snod
->offs
);
611 list_del(&snod
->list
);
613 sleb
->nodes_cnt
-= 1;
618 * ubifs_recover_leb - scan and recover a LEB.
619 * @c: UBIFS file-system description object
622 * @sbuf: LEB-sized buffer to use
623 * @jhead: journal head number this LEB belongs to (%-1 if the LEB does not
624 * belong to any journal head)
626 * This function does a scan of a LEB, but caters for errors that might have
627 * been caused by the unclean unmount from which we are attempting to recover.
628 * Returns the scanned information on success and a negative error code on
631 struct ubifs_scan_leb
*ubifs_recover_leb(struct ubifs_info
*c
, int lnum
,
632 int offs
, void *sbuf
, int jhead
)
634 int ret
= 0, err
, len
= c
->leb_size
- offs
, start
= offs
, min_io_unit
;
635 int grouped
= jhead
== -1 ? 0 : c
->jheads
[jhead
].grouped
;
636 struct ubifs_scan_leb
*sleb
;
637 void *buf
= sbuf
+ offs
;
639 dbg_rcvry("%d:%d, jhead %d, grouped %d", lnum
, offs
, jhead
, grouped
);
641 sleb
= ubifs_start_scan(c
, lnum
, offs
, sbuf
);
645 ubifs_assert(len
>= 8);
647 dbg_scan("look at LEB %d:%d (%d bytes left)",
653 * Scan quietly until there is an error from which we cannot
656 ret
= ubifs_scan_a_node(c
, buf
, len
, lnum
, offs
, 1);
657 if (ret
== SCANNED_A_NODE
) {
658 /* A valid node, and not a padding node */
659 struct ubifs_ch
*ch
= buf
;
662 err
= ubifs_add_snod(c
, sleb
, buf
, offs
);
665 node_len
= ALIGN(le32_to_cpu(ch
->len
), 8);
669 } else if (ret
> 0) {
670 /* Padding bytes or a valid padding node */
674 } else if (ret
== SCANNED_EMPTY_SPACE
||
675 ret
== SCANNED_GARBAGE
||
676 ret
== SCANNED_A_BAD_PAD_NODE
||
677 ret
== SCANNED_A_CORRUPT_NODE
) {
678 dbg_rcvry("found corruption (%d) at %d:%d",
682 ubifs_err(c
, "unexpected return value %d", ret
);
688 if (ret
== SCANNED_GARBAGE
|| ret
== SCANNED_A_BAD_PAD_NODE
) {
689 if (!is_last_write(c
, buf
, offs
))
690 goto corrupted_rescan
;
691 } else if (ret
== SCANNED_A_CORRUPT_NODE
) {
692 if (!no_more_nodes(c
, buf
, len
, lnum
, offs
))
693 goto corrupted_rescan
;
694 } else if (!is_empty(buf
, len
)) {
695 if (!is_last_write(c
, buf
, offs
)) {
696 int corruption
= first_non_ff(buf
, len
);
699 * See header comment for this file for more
700 * explanations about the reasons we have this check.
702 ubifs_err(c
, "corrupt empty space LEB %d:%d, corruption starts at %d",
703 lnum
, offs
, corruption
);
704 /* Make sure we dump interesting non-0xFF data */
711 min_io_unit
= round_down(offs
, c
->min_io_size
);
714 * If nodes are grouped, always drop the incomplete group at
717 drop_last_group(sleb
, &offs
);
721 * If this LEB belongs to the GC head then while we are in the
722 * middle of the same min. I/O unit keep dropping nodes. So
723 * basically, what we want is to make sure that the last min.
724 * I/O unit where we saw the corruption is dropped completely
725 * with all the uncorrupted nodes which may possibly sit there.
727 * In other words, let's name the min. I/O unit where the
728 * corruption starts B, and the previous min. I/O unit A. The
729 * below code tries to deal with a situation when half of B
730 * contains valid nodes or the end of a valid node, and the
731 * second half of B contains corrupted data or garbage. This
732 * means that UBIFS had been writing to B just before the power
733 * cut happened. I do not know how realistic is this scenario
734 * that half of the min. I/O unit had been written successfully
735 * and the other half not, but this is possible in our 'failure
736 * mode emulation' infrastructure at least.
738 * So what is the problem, why we need to drop those nodes? Why
739 * can't we just clean-up the second half of B by putting a
740 * padding node there? We can, and this works fine with one
741 * exception which was reproduced with power cut emulation
742 * testing and happens extremely rarely.
744 * Imagine the file-system is full, we run GC which starts
745 * moving valid nodes from LEB X to LEB Y (obviously, LEB Y is
746 * the current GC head LEB). The @c->gc_lnum is -1, which means
747 * that GC will retain LEB X and will try to continue. Imagine
748 * that LEB X is currently the dirtiest LEB, and the amount of
749 * used space in LEB Y is exactly the same as amount of free
752 * And a power cut happens when nodes are moved from LEB X to
753 * LEB Y. We are here trying to recover LEB Y which is the GC
754 * head LEB. We find the min. I/O unit B as described above.
755 * Then we clean-up LEB Y by padding min. I/O unit. And later
756 * 'ubifs_rcvry_gc_commit()' function fails, because it cannot
757 * find a dirty LEB which could be GC'd into LEB Y! Even LEB X
758 * does not match because the amount of valid nodes there does
759 * not fit the free space in LEB Y any more! And this is
760 * because of the padding node which we added to LEB Y. The
761 * user-visible effect of this which I once observed and
762 * analysed is that we cannot mount the file-system with
765 * So obviously, to make sure that situation does not happen we
766 * should free min. I/O unit B in LEB Y completely and the last
767 * used min. I/O unit in LEB Y should be A. This is basically
768 * what the below code tries to do.
770 while (offs
> min_io_unit
)
771 drop_last_node(sleb
, &offs
);
775 len
= c
->leb_size
- offs
;
777 clean_buf(c
, &buf
, lnum
, &offs
, &len
);
778 ubifs_end_scan(c
, sleb
, lnum
, offs
);
780 err
= fix_unclean_leb(c
, sleb
, start
);
787 /* Re-scan the corrupted data with verbose messages */
788 ubifs_err(c
, "corruption %d", ret
);
789 ubifs_scan_a_node(c
, buf
, len
, lnum
, offs
, 1);
791 ubifs_scanned_corruption(c
, lnum
, offs
, buf
);
794 ubifs_err(c
, "LEB %d scanning failed", lnum
);
795 ubifs_scan_destroy(sleb
);
800 * get_cs_sqnum - get commit start sequence number.
801 * @c: UBIFS file-system description object
802 * @lnum: LEB number of commit start node
803 * @offs: offset of commit start node
804 * @cs_sqnum: commit start sequence number is returned here
806 * This function returns %0 on success and a negative error code on failure.
808 static int get_cs_sqnum(struct ubifs_info
*c
, int lnum
, int offs
,
809 unsigned long long *cs_sqnum
)
811 struct ubifs_cs_node
*cs_node
= NULL
;
814 dbg_rcvry("at %d:%d", lnum
, offs
);
815 cs_node
= kmalloc(UBIFS_CS_NODE_SZ
, GFP_KERNEL
);
818 if (c
->leb_size
- offs
< UBIFS_CS_NODE_SZ
)
820 err
= ubifs_leb_read(c
, lnum
, (void *)cs_node
, offs
,
821 UBIFS_CS_NODE_SZ
, 0);
822 if (err
&& err
!= -EBADMSG
)
824 ret
= ubifs_scan_a_node(c
, cs_node
, UBIFS_CS_NODE_SZ
, lnum
, offs
, 0);
825 if (ret
!= SCANNED_A_NODE
) {
826 ubifs_err(c
, "Not a valid node");
829 if (cs_node
->ch
.node_type
!= UBIFS_CS_NODE
) {
830 ubifs_err(c
, "Node a CS node, type is %d", cs_node
->ch
.node_type
);
833 if (le64_to_cpu(cs_node
->cmt_no
) != c
->cmt_no
) {
834 ubifs_err(c
, "CS node cmt_no %llu != current cmt_no %llu",
835 (unsigned long long)le64_to_cpu(cs_node
->cmt_no
),
839 *cs_sqnum
= le64_to_cpu(cs_node
->ch
.sqnum
);
840 dbg_rcvry("commit start sqnum %llu", *cs_sqnum
);
847 ubifs_err(c
, "failed to get CS sqnum");
853 * ubifs_recover_log_leb - scan and recover a log LEB.
854 * @c: UBIFS file-system description object
857 * @sbuf: LEB-sized buffer to use
859 * This function does a scan of a LEB, but caters for errors that might have
860 * been caused by unclean reboots from which we are attempting to recover
861 * (assume that only the last log LEB can be corrupted by an unclean reboot).
863 * This function returns %0 on success and a negative error code on failure.
865 struct ubifs_scan_leb
*ubifs_recover_log_leb(struct ubifs_info
*c
, int lnum
,
866 int offs
, void *sbuf
)
868 struct ubifs_scan_leb
*sleb
;
871 dbg_rcvry("LEB %d", lnum
);
872 next_lnum
= lnum
+ 1;
873 if (next_lnum
>= UBIFS_LOG_LNUM
+ c
->log_lebs
)
874 next_lnum
= UBIFS_LOG_LNUM
;
875 if (next_lnum
!= c
->ltail_lnum
) {
877 * We can only recover at the end of the log, so check that the
878 * next log LEB is empty or out of date.
880 sleb
= ubifs_scan(c
, next_lnum
, 0, sbuf
, 0);
883 if (sleb
->nodes_cnt
) {
884 struct ubifs_scan_node
*snod
;
885 unsigned long long cs_sqnum
= c
->cs_sqnum
;
887 snod
= list_entry(sleb
->nodes
.next
,
888 struct ubifs_scan_node
, list
);
892 err
= get_cs_sqnum(c
, lnum
, offs
, &cs_sqnum
);
894 ubifs_scan_destroy(sleb
);
898 if (snod
->sqnum
> cs_sqnum
) {
899 ubifs_err(c
, "unrecoverable log corruption in LEB %d",
901 ubifs_scan_destroy(sleb
);
902 return ERR_PTR(-EUCLEAN
);
905 ubifs_scan_destroy(sleb
);
907 return ubifs_recover_leb(c
, lnum
, offs
, sbuf
, -1);
911 * recover_head - recover a head.
912 * @c: UBIFS file-system description object
913 * @lnum: LEB number of head to recover
914 * @offs: offset of head to recover
915 * @sbuf: LEB-sized buffer to use
917 * This function ensures that there is no data on the flash at a head location.
919 * This function returns %0 on success and a negative error code on failure.
921 static int recover_head(struct ubifs_info
*c
, int lnum
, int offs
, void *sbuf
)
923 int len
= c
->max_write_size
, err
;
925 if (offs
+ len
> c
->leb_size
)
926 len
= c
->leb_size
- offs
;
931 /* Read at the head location and check it is empty flash */
932 err
= ubifs_leb_read(c
, lnum
, sbuf
, offs
, len
, 1);
933 if (err
|| !is_empty(sbuf
, len
)) {
934 dbg_rcvry("cleaning head at %d:%d", lnum
, offs
);
936 return ubifs_leb_unmap(c
, lnum
);
937 err
= ubifs_leb_read(c
, lnum
, sbuf
, 0, offs
, 1);
940 return ubifs_leb_change(c
, lnum
, sbuf
, offs
);
947 * ubifs_recover_inl_heads - recover index and LPT heads.
948 * @c: UBIFS file-system description object
949 * @sbuf: LEB-sized buffer to use
951 * This function ensures that there is no data on the flash at the index and
952 * LPT head locations.
954 * This deals with the recovery of a half-completed journal commit. UBIFS is
955 * careful never to overwrite the last version of the index or the LPT. Because
956 * the index and LPT are wandering trees, data from a half-completed commit will
957 * not be referenced anywhere in UBIFS. The data will be either in LEBs that are
958 * assumed to be empty and will be unmapped anyway before use, or in the index
961 * This function returns %0 on success and a negative error code on failure.
963 int ubifs_recover_inl_heads(struct ubifs_info
*c
, void *sbuf
)
967 ubifs_assert(!c
->ro_mount
|| c
->remounting_rw
);
969 dbg_rcvry("checking index head at %d:%d", c
->ihead_lnum
, c
->ihead_offs
);
970 err
= recover_head(c
, c
->ihead_lnum
, c
->ihead_offs
, sbuf
);
974 dbg_rcvry("checking LPT head at %d:%d", c
->nhead_lnum
, c
->nhead_offs
);
976 return recover_head(c
, c
->nhead_lnum
, c
->nhead_offs
, sbuf
);
980 * clean_an_unclean_leb - read and write a LEB to remove corruption.
981 * @c: UBIFS file-system description object
982 * @ucleb: unclean LEB information
983 * @sbuf: LEB-sized buffer to use
985 * This function reads a LEB up to a point pre-determined by the mount recovery,
986 * checks the nodes, and writes the result back to the flash, thereby cleaning
987 * off any following corruption, or non-fatal ECC errors.
989 * This function returns %0 on success and a negative error code on failure.
991 static int clean_an_unclean_leb(struct ubifs_info
*c
,
992 struct ubifs_unclean_leb
*ucleb
, void *sbuf
)
994 int err
, lnum
= ucleb
->lnum
, offs
= 0, len
= ucleb
->endpt
, quiet
= 1;
997 dbg_rcvry("LEB %d len %d", lnum
, len
);
1000 /* Nothing to read, just unmap it */
1001 return ubifs_leb_unmap(c
, lnum
);
1004 err
= ubifs_leb_read(c
, lnum
, buf
, offs
, len
, 0);
1005 if (err
&& err
!= -EBADMSG
)
1013 /* Scan quietly until there is an error */
1014 ret
= ubifs_scan_a_node(c
, buf
, len
, lnum
, offs
, quiet
);
1016 if (ret
== SCANNED_A_NODE
) {
1017 /* A valid node, and not a padding node */
1018 struct ubifs_ch
*ch
= buf
;
1021 node_len
= ALIGN(le32_to_cpu(ch
->len
), 8);
1029 /* Padding bytes or a valid padding node */
1036 if (ret
== SCANNED_EMPTY_SPACE
) {
1037 ubifs_err(c
, "unexpected empty space at %d:%d",
1043 /* Redo the last scan but noisily */
1048 ubifs_scanned_corruption(c
, lnum
, offs
, buf
);
1052 /* Pad to min_io_size */
1053 len
= ALIGN(ucleb
->endpt
, c
->min_io_size
);
1054 if (len
> ucleb
->endpt
) {
1055 int pad_len
= len
- ALIGN(ucleb
->endpt
, 8);
1058 buf
= c
->sbuf
+ len
- pad_len
;
1059 ubifs_pad(c
, buf
, pad_len
);
1063 /* Write back the LEB atomically */
1064 err
= ubifs_leb_change(c
, lnum
, sbuf
, len
);
1068 dbg_rcvry("cleaned LEB %d", lnum
);
1074 * ubifs_clean_lebs - clean LEBs recovered during read-only mount.
1075 * @c: UBIFS file-system description object
1076 * @sbuf: LEB-sized buffer to use
1078 * This function cleans a LEB identified during recovery that needs to be
1079 * written but was not because UBIFS was mounted read-only. This happens when
1080 * remounting to read-write mode.
1082 * This function returns %0 on success and a negative error code on failure.
1084 int ubifs_clean_lebs(struct ubifs_info
*c
, void *sbuf
)
1086 dbg_rcvry("recovery");
1087 while (!list_empty(&c
->unclean_leb_list
)) {
1088 struct ubifs_unclean_leb
*ucleb
;
1091 ucleb
= list_entry(c
->unclean_leb_list
.next
,
1092 struct ubifs_unclean_leb
, list
);
1093 err
= clean_an_unclean_leb(c
, ucleb
, sbuf
);
1096 list_del(&ucleb
->list
);
1104 * grab_empty_leb - grab an empty LEB to use as GC LEB and run commit.
1105 * @c: UBIFS file-system description object
1107 * This is a helper function for 'ubifs_rcvry_gc_commit()' which grabs an empty
1108 * LEB to be used as GC LEB (@c->gc_lnum), and then runs the commit. Returns
1109 * zero in case of success and a negative error code in case of failure.
1111 static int grab_empty_leb(struct ubifs_info
*c
)
1116 * Note, it is very important to first search for an empty LEB and then
1117 * run the commit, not vice-versa. The reason is that there might be
1118 * only one empty LEB at the moment, the one which has been the
1119 * @c->gc_lnum just before the power cut happened. During the regular
1120 * UBIFS operation (not now) @c->gc_lnum is marked as "taken", so no
1121 * one but GC can grab it. But at this moment this single empty LEB is
1122 * not marked as taken, so if we run commit - what happens? Right, the
1123 * commit will grab it and write the index there. Remember that the
1124 * index always expands as long as there is free space, and it only
1125 * starts consolidating when we run out of space.
1127 * IOW, if we run commit now, we might not be able to find a free LEB
1130 lnum
= ubifs_find_free_leb_for_idx(c
);
1132 ubifs_err(c
, "could not find an empty LEB");
1133 ubifs_dump_lprops(c
);
1134 ubifs_dump_budg(c
, &c
->bi
);
1138 /* Reset the index flag */
1139 err
= ubifs_change_one_lp(c
, lnum
, LPROPS_NC
, LPROPS_NC
, 0,
1145 dbg_rcvry("found empty LEB %d, run commit", lnum
);
1147 return ubifs_run_commit(c
);
1151 * ubifs_rcvry_gc_commit - recover the GC LEB number and run the commit.
1152 * @c: UBIFS file-system description object
1154 * Out-of-place garbage collection requires always one empty LEB with which to
1155 * start garbage collection. The LEB number is recorded in c->gc_lnum and is
1156 * written to the master node on unmounting. In the case of an unclean unmount
1157 * the value of gc_lnum recorded in the master node is out of date and cannot
1158 * be used. Instead, recovery must allocate an empty LEB for this purpose.
1159 * However, there may not be enough empty space, in which case it must be
1160 * possible to GC the dirtiest LEB into the GC head LEB.
1162 * This function also runs the commit which causes the TNC updates from
1163 * size-recovery and orphans to be written to the flash. That is important to
1164 * ensure correct replay order for subsequent mounts.
1166 * This function returns %0 on success and a negative error code on failure.
1168 int ubifs_rcvry_gc_commit(struct ubifs_info
*c
)
1170 struct ubifs_wbuf
*wbuf
= &c
->jheads
[GCHD
].wbuf
;
1171 struct ubifs_lprops lp
;
1174 dbg_rcvry("GC head LEB %d, offs %d", wbuf
->lnum
, wbuf
->offs
);
1177 if (wbuf
->lnum
== -1 || wbuf
->offs
== c
->leb_size
)
1178 return grab_empty_leb(c
);
1180 err
= ubifs_find_dirty_leb(c
, &lp
, wbuf
->offs
, 2);
1185 dbg_rcvry("could not find a dirty LEB");
1186 return grab_empty_leb(c
);
1189 ubifs_assert(!(lp
.flags
& LPROPS_INDEX
));
1190 ubifs_assert(lp
.free
+ lp
.dirty
>= wbuf
->offs
);
1193 * We run the commit before garbage collection otherwise subsequent
1194 * mounts will see the GC and orphan deletion in a different order.
1196 dbg_rcvry("committing");
1197 err
= ubifs_run_commit(c
);
1201 dbg_rcvry("GC'ing LEB %d", lp
.lnum
);
1202 mutex_lock_nested(&wbuf
->io_mutex
, wbuf
->jhead
);
1203 err
= ubifs_garbage_collect_leb(c
, &lp
);
1205 int err2
= ubifs_wbuf_sync_nolock(wbuf
);
1210 mutex_unlock(&wbuf
->io_mutex
);
1212 ubifs_err(c
, "GC failed, error %d", err
);
1218 ubifs_assert(err
== LEB_RETAINED
);
1219 if (err
!= LEB_RETAINED
)
1222 err
= ubifs_leb_unmap(c
, c
->gc_lnum
);
1226 dbg_rcvry("allocated LEB %d for GC", lp
.lnum
);
1230 int ubifs_rcvry_gc_commit(struct ubifs_info
*c
)
1237 * struct size_entry - inode size information for recovery.
1238 * @rb: link in the RB-tree of sizes
1239 * @inum: inode number
1240 * @i_size: size on inode
1241 * @d_size: maximum size based on data nodes
1242 * @exists: indicates whether the inode exists
1243 * @inode: inode if pinned in memory awaiting rw mode to fix it
1251 struct inode
*inode
;
1255 * add_ino - add an entry to the size tree.
1256 * @c: UBIFS file-system description object
1257 * @inum: inode number
1258 * @i_size: size on inode
1259 * @d_size: maximum size based on data nodes
1260 * @exists: indicates whether the inode exists
1262 static int add_ino(struct ubifs_info
*c
, ino_t inum
, loff_t i_size
,
1263 loff_t d_size
, int exists
)
1265 struct rb_node
**p
= &c
->size_tree
.rb_node
, *parent
= NULL
;
1266 struct size_entry
*e
;
1270 e
= rb_entry(parent
, struct size_entry
, rb
);
1274 p
= &(*p
)->rb_right
;
1277 e
= kzalloc(sizeof(struct size_entry
), GFP_KERNEL
);
1286 rb_link_node(&e
->rb
, parent
, p
);
1287 rb_insert_color(&e
->rb
, &c
->size_tree
);
1293 * find_ino - find an entry on the size tree.
1294 * @c: UBIFS file-system description object
1295 * @inum: inode number
1297 static struct size_entry
*find_ino(struct ubifs_info
*c
, ino_t inum
)
1299 struct rb_node
*p
= c
->size_tree
.rb_node
;
1300 struct size_entry
*e
;
1303 e
= rb_entry(p
, struct size_entry
, rb
);
1306 else if (inum
> e
->inum
)
1315 * remove_ino - remove an entry from the size tree.
1316 * @c: UBIFS file-system description object
1317 * @inum: inode number
1319 static void remove_ino(struct ubifs_info
*c
, ino_t inum
)
1321 struct size_entry
*e
= find_ino(c
, inum
);
1325 rb_erase(&e
->rb
, &c
->size_tree
);
1330 * ubifs_destroy_size_tree - free resources related to the size tree.
1331 * @c: UBIFS file-system description object
1333 void ubifs_destroy_size_tree(struct ubifs_info
*c
)
1335 struct size_entry
*e
, *n
;
1337 rbtree_postorder_for_each_entry_safe(e
, n
, &c
->size_tree
, rb
) {
1343 c
->size_tree
= RB_ROOT
;
1347 * ubifs_recover_size_accum - accumulate inode sizes for recovery.
1348 * @c: UBIFS file-system description object
1350 * @deletion: node is for a deletion
1351 * @new_size: inode size
1353 * This function has two purposes:
1354 * 1) to ensure there are no data nodes that fall outside the inode size
1355 * 2) to ensure there are no data nodes for inodes that do not exist
1356 * To accomplish those purposes, a rb-tree is constructed containing an entry
1357 * for each inode number in the journal that has not been deleted, and recording
1358 * the size from the inode node, the maximum size of any data node (also altered
1359 * by truncations) and a flag indicating a inode number for which no inode node
1360 * was present in the journal.
1362 * Note that there is still the possibility that there are data nodes that have
1363 * been committed that are beyond the inode size, however the only way to find
1364 * them would be to scan the entire index. Alternatively, some provision could
1365 * be made to record the size of inodes at the start of commit, which would seem
1366 * very cumbersome for a scenario that is quite unlikely and the only negative
1367 * consequence of which is wasted space.
1369 * This functions returns %0 on success and a negative error code on failure.
1371 int ubifs_recover_size_accum(struct ubifs_info
*c
, union ubifs_key
*key
,
1372 int deletion
, loff_t new_size
)
1374 ino_t inum
= key_inum(c
, key
);
1375 struct size_entry
*e
;
1378 switch (key_type(c
, key
)) {
1381 remove_ino(c
, inum
);
1383 e
= find_ino(c
, inum
);
1385 e
->i_size
= new_size
;
1388 err
= add_ino(c
, inum
, new_size
, 0, 1);
1394 case UBIFS_DATA_KEY
:
1395 e
= find_ino(c
, inum
);
1397 if (new_size
> e
->d_size
)
1398 e
->d_size
= new_size
;
1400 err
= add_ino(c
, inum
, 0, new_size
, 0);
1405 case UBIFS_TRUN_KEY
:
1406 e
= find_ino(c
, inum
);
1408 e
->d_size
= new_size
;
1416 * fix_size_in_place - fix inode size in place on flash.
1417 * @c: UBIFS file-system description object
1418 * @e: inode size information for recovery
1420 static int fix_size_in_place(struct ubifs_info
*c
, struct size_entry
*e
)
1422 struct ubifs_ino_node
*ino
= c
->sbuf
;
1424 union ubifs_key key
;
1425 int err
, lnum
, offs
, len
;
1429 /* Locate the inode node LEB number and offset */
1430 ino_key_init(c
, &key
, e
->inum
);
1431 err
= ubifs_tnc_locate(c
, &key
, ino
, &lnum
, &offs
);
1435 * If the size recorded on the inode node is greater than the size that
1436 * was calculated from nodes in the journal then don't change the inode.
1438 i_size
= le64_to_cpu(ino
->size
);
1439 if (i_size
>= e
->d_size
)
1442 err
= ubifs_leb_read(c
, lnum
, c
->sbuf
, 0, c
->leb_size
, 1);
1445 /* Change the size field and recalculate the CRC */
1446 ino
= c
->sbuf
+ offs
;
1447 ino
->size
= cpu_to_le64(e
->d_size
);
1448 len
= le32_to_cpu(ino
->ch
.len
);
1449 crc
= crc32(UBIFS_CRC32_INIT
, (void *)ino
+ 8, len
- 8);
1450 ino
->ch
.crc
= cpu_to_le32(crc
);
1451 /* Work out where data in the LEB ends and free space begins */
1453 len
= c
->leb_size
- 1;
1454 while (p
[len
] == 0xff)
1456 len
= ALIGN(len
+ 1, c
->min_io_size
);
1457 /* Atomically write the fixed LEB back again */
1458 err
= ubifs_leb_change(c
, lnum
, c
->sbuf
, len
);
1461 dbg_rcvry("inode %lu at %d:%d size %lld -> %lld",
1462 (unsigned long)e
->inum
, lnum
, offs
, i_size
, e
->d_size
);
1466 ubifs_warn(c
, "inode %lu failed to fix size %lld -> %lld error %d",
1467 (unsigned long)e
->inum
, e
->i_size
, e
->d_size
, err
);
1473 * ubifs_recover_size - recover inode size.
1474 * @c: UBIFS file-system description object
1476 * This function attempts to fix inode size discrepancies identified by the
1477 * 'ubifs_recover_size_accum()' function.
1479 * This functions returns %0 on success and a negative error code on failure.
1481 int ubifs_recover_size(struct ubifs_info
*c
)
1483 struct rb_node
*this = rb_first(&c
->size_tree
);
1486 struct size_entry
*e
;
1489 e
= rb_entry(this, struct size_entry
, rb
);
1491 union ubifs_key key
;
1493 ino_key_init(c
, &key
, e
->inum
);
1494 err
= ubifs_tnc_lookup(c
, &key
, c
->sbuf
);
1495 if (err
&& err
!= -ENOENT
)
1497 if (err
== -ENOENT
) {
1498 /* Remove data nodes that have no inode */
1499 dbg_rcvry("removing ino %lu",
1500 (unsigned long)e
->inum
);
1501 err
= ubifs_tnc_remove_ino(c
, e
->inum
);
1505 struct ubifs_ino_node
*ino
= c
->sbuf
;
1508 e
->i_size
= le64_to_cpu(ino
->size
);
1512 if (e
->exists
&& e
->i_size
< e
->d_size
) {
1514 /* Fix the inode size and pin it in memory */
1515 struct inode
*inode
;
1516 struct ubifs_inode
*ui
;
1518 ubifs_assert(!e
->inode
);
1520 inode
= ubifs_iget(c
->vfs_sb
, e
->inum
);
1522 return PTR_ERR(inode
);
1524 ui
= ubifs_inode(inode
);
1525 if (inode
->i_size
< e
->d_size
) {
1526 dbg_rcvry("ino %lu size %lld -> %lld",
1527 (unsigned long)e
->inum
,
1528 inode
->i_size
, e
->d_size
);
1529 inode
->i_size
= e
->d_size
;
1530 ui
->ui_size
= e
->d_size
;
1531 ui
->synced_i_size
= e
->d_size
;
1533 this = rb_next(this);
1539 /* Fix the size in place */
1540 err
= fix_size_in_place(c
, e
);
1549 this = rb_next(this);
1550 rb_erase(&e
->rb
, &c
->size_tree
);