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
= ubi_read(c
->ubi
, lnum
, sbuf
, 0, c
->leb_size
);
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
= ubi_leb_change(c
->ubi
, lnum
, mst
, sz
, UBI_SHORTTERM
);
219 err
= ubi_leb_change(c
->ubi
, lnum
+ 1, mst
, sz
, UBI_SHORTTERM
);
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 && offs2
+ sz
>= c
->leb_size
) {
278 /* 1st LEB was unmapped and written, 2nd not */
286 * 2nd LEB was unmapped and about to be written, so
287 * there must be only one master node in the first LEB
290 if (offs1
!= 0 || cor1
)
298 * 1st LEB was unmapped and about to be written, so there must
299 * be no room left in 2nd LEB.
301 offs2
= (void *)mst2
- buf2
;
302 if (offs2
+ sz
+ sz
<= c
->leb_size
)
307 ubifs_msg("recovered master node from LEB %d",
308 (mst
== mst1
? UBIFS_MST_LNUM
: UBIFS_MST_LNUM
+ 1));
310 memcpy(c
->mst_node
, mst
, UBIFS_MST_NODE_SZ
);
313 /* Read-only mode. Keep a copy for switching to rw mode */
314 c
->rcvrd_mst_node
= kmalloc(sz
, GFP_KERNEL
);
315 if (!c
->rcvrd_mst_node
) {
319 memcpy(c
->rcvrd_mst_node
, c
->mst_node
, UBIFS_MST_NODE_SZ
);
322 * We had to recover the master node, which means there was an
323 * unclean reboot. However, it is possible that the master node
324 * is clean at this point, i.e., %UBIFS_MST_DIRTY is not set.
325 * E.g., consider the following chain of events:
327 * 1. UBIFS was cleanly unmounted, so the master node is clean
328 * 2. UBIFS is being mounted R/W and starts changing the master
329 * node in the first (%UBIFS_MST_LNUM). A power cut happens,
330 * so this LEB ends up with some amount of garbage at the
332 * 3. UBIFS is being mounted R/O. We reach this place and
333 * recover the master node from the second LEB
334 * (%UBIFS_MST_LNUM + 1). But we cannot update the media
335 * because we are being mounted R/O. We have to defer the
337 * 4. However, this master node (@c->mst_node) is marked as
338 * clean (since the step 1). And if we just return, the
339 * mount code will be confused and won't recover the master
340 * node when it is re-mounter R/W later.
342 * Thus, to force the recovery by marking the master node as
345 c
->mst_node
->flags
|= cpu_to_le32(UBIFS_MST_DIRTY
);
347 /* Write the recovered master node */
348 c
->max_sqnum
= le64_to_cpu(mst
->ch
.sqnum
) - 1;
349 err
= write_rcvrd_mst_node(c
, c
->mst_node
);
362 ubifs_err("failed to recover master node");
364 dbg_err("dumping first master node");
365 dbg_dump_node(c
, mst1
);
368 dbg_err("dumping second master node");
369 dbg_dump_node(c
, mst2
);
377 * ubifs_write_rcvrd_mst_node - write the recovered master node.
378 * @c: UBIFS file-system description object
380 * This function writes the master node that was recovered during mounting in
381 * read-only mode and must now be written because we are remounting rw.
383 * This function returns %0 on success and a negative error code on failure.
385 int ubifs_write_rcvrd_mst_node(struct ubifs_info
*c
)
389 if (!c
->rcvrd_mst_node
)
391 c
->rcvrd_mst_node
->flags
|= cpu_to_le32(UBIFS_MST_DIRTY
);
392 c
->mst_node
->flags
|= cpu_to_le32(UBIFS_MST_DIRTY
);
393 err
= write_rcvrd_mst_node(c
, c
->rcvrd_mst_node
);
396 kfree(c
->rcvrd_mst_node
);
397 c
->rcvrd_mst_node
= NULL
;
402 * is_last_write - determine if an offset was in the last write to a LEB.
403 * @c: UBIFS file-system description object
404 * @buf: buffer to check
405 * @offs: offset to check
407 * This function returns %1 if @offs was in the last write to the LEB whose data
408 * is in @buf, otherwise %0 is returned. The determination is made by checking
409 * for subsequent empty space starting from the next @c->max_write_size
412 static int is_last_write(const struct ubifs_info
*c
, void *buf
, int offs
)
414 int empty_offs
, check_len
;
418 * Round up to the next @c->max_write_size boundary i.e. @offs is in
419 * the last wbuf written. After that should be empty space.
421 empty_offs
= ALIGN(offs
+ 1, c
->max_write_size
);
422 check_len
= c
->leb_size
- empty_offs
;
423 p
= buf
+ empty_offs
- offs
;
424 return is_empty(p
, check_len
);
428 * clean_buf - clean the data from an LEB sitting in a buffer.
429 * @c: UBIFS file-system description object
430 * @buf: buffer to clean
431 * @lnum: LEB number to clean
432 * @offs: offset from which to clean
433 * @len: length of buffer
435 * This function pads up to the next min_io_size boundary (if there is one) and
436 * sets empty space to all 0xff. @buf, @offs and @len are updated to the next
437 * @c->min_io_size boundary.
439 static void clean_buf(const struct ubifs_info
*c
, void **buf
, int lnum
,
442 int empty_offs
, pad_len
;
445 dbg_rcvry("cleaning corruption at %d:%d", lnum
, *offs
);
447 ubifs_assert(!(*offs
& 7));
448 empty_offs
= ALIGN(*offs
, c
->min_io_size
);
449 pad_len
= empty_offs
- *offs
;
450 ubifs_pad(c
, *buf
, pad_len
);
454 memset(*buf
, 0xff, c
->leb_size
- empty_offs
);
458 * no_more_nodes - determine if there are no more nodes in a buffer.
459 * @c: UBIFS file-system description object
460 * @buf: buffer to check
461 * @len: length of buffer
462 * @lnum: LEB number of the LEB from which @buf was read
463 * @offs: offset from which @buf was read
465 * This function ensures that the corrupted node at @offs is the last thing
466 * written to a LEB. This function returns %1 if more data is not found and
467 * %0 if more data is found.
469 static int no_more_nodes(const struct ubifs_info
*c
, void *buf
, int len
,
472 struct ubifs_ch
*ch
= buf
;
473 int skip
, dlen
= le32_to_cpu(ch
->len
);
475 /* Check for empty space after the corrupt node's common header */
476 skip
= ALIGN(offs
+ UBIFS_CH_SZ
, c
->max_write_size
) - offs
;
477 if (is_empty(buf
+ skip
, len
- skip
))
480 * The area after the common header size is not empty, so the common
481 * header must be intact. Check it.
483 if (ubifs_check_node(c
, buf
, lnum
, offs
, 1, 0) != -EUCLEAN
) {
484 dbg_rcvry("unexpected bad common header at %d:%d", lnum
, offs
);
487 /* Now we know the corrupt node's length we can skip over it */
488 skip
= ALIGN(offs
+ dlen
, c
->max_write_size
) - offs
;
489 /* After which there should be empty space */
490 if (is_empty(buf
+ skip
, len
- skip
))
492 dbg_rcvry("unexpected data at %d:%d", lnum
, offs
+ skip
);
497 * fix_unclean_leb - fix an unclean LEB.
498 * @c: UBIFS file-system description object
499 * @sleb: scanned LEB information
500 * @start: offset where scan started
502 static int fix_unclean_leb(struct ubifs_info
*c
, struct ubifs_scan_leb
*sleb
,
505 int lnum
= sleb
->lnum
, endpt
= start
;
507 /* Get the end offset of the last node we are keeping */
508 if (!list_empty(&sleb
->nodes
)) {
509 struct ubifs_scan_node
*snod
;
511 snod
= list_entry(sleb
->nodes
.prev
,
512 struct ubifs_scan_node
, list
);
513 endpt
= snod
->offs
+ snod
->len
;
516 if (c
->ro_mount
&& !c
->remounting_rw
) {
517 /* Add to recovery list */
518 struct ubifs_unclean_leb
*ucleb
;
520 dbg_rcvry("need to fix LEB %d start %d endpt %d",
521 lnum
, start
, sleb
->endpt
);
522 ucleb
= kzalloc(sizeof(struct ubifs_unclean_leb
), GFP_NOFS
);
526 ucleb
->endpt
= endpt
;
527 list_add_tail(&ucleb
->list
, &c
->unclean_leb_list
);
529 /* Write the fixed LEB back to flash */
532 dbg_rcvry("fixing LEB %d start %d endpt %d",
533 lnum
, start
, sleb
->endpt
);
535 err
= ubifs_leb_unmap(c
, lnum
);
539 int len
= ALIGN(endpt
, c
->min_io_size
);
542 err
= ubi_read(c
->ubi
, lnum
, sleb
->buf
, 0,
547 /* Pad to min_io_size */
549 int pad_len
= len
- ALIGN(endpt
, 8);
552 void *buf
= sleb
->buf
+ len
- pad_len
;
554 ubifs_pad(c
, buf
, pad_len
);
557 err
= ubi_leb_change(c
->ubi
, lnum
, sleb
->buf
, len
,
567 * drop_incomplete_group - drop nodes from an incomplete group.
568 * @sleb: scanned LEB information
569 * @offs: offset of dropped nodes is returned here
571 * This function returns %1 if nodes are dropped and %0 otherwise.
573 static int drop_incomplete_group(struct ubifs_scan_leb
*sleb
, int *offs
)
577 while (!list_empty(&sleb
->nodes
)) {
578 struct ubifs_scan_node
*snod
;
581 snod
= list_entry(sleb
->nodes
.prev
, struct ubifs_scan_node
,
584 if (ch
->group_type
!= UBIFS_IN_NODE_GROUP
)
586 dbg_rcvry("dropping node at %d:%d", sleb
->lnum
, snod
->offs
);
588 list_del(&snod
->list
);
590 sleb
->nodes_cnt
-= 1;
597 * ubifs_recover_leb - scan and recover a LEB.
598 * @c: UBIFS file-system description object
601 * @sbuf: LEB-sized buffer to use
602 * @grouped: nodes may be grouped for recovery
604 * This function does a scan of a LEB, but caters for errors that might have
605 * been caused by the unclean unmount from which we are attempting to recover.
606 * Returns %0 in case of success, %-EUCLEAN if an unrecoverable corruption is
607 * found, and a negative error code in case of failure.
609 struct ubifs_scan_leb
*ubifs_recover_leb(struct ubifs_info
*c
, int lnum
,
610 int offs
, void *sbuf
, int grouped
)
612 int ret
= 0, err
, len
= c
->leb_size
- offs
, need_clean
= 0;
614 struct ubifs_scan_leb
*sleb
;
615 void *buf
= sbuf
+ offs
;
617 dbg_rcvry("%d:%d", lnum
, offs
);
619 sleb
= ubifs_start_scan(c
, lnum
, offs
, sbuf
);
627 dbg_scan("look at LEB %d:%d (%d bytes left)",
633 * Scan quietly until there is an error from which we cannot
636 ret
= ubifs_scan_a_node(c
, buf
, len
, lnum
, offs
, 0);
637 if (ret
== SCANNED_A_NODE
) {
638 /* A valid node, and not a padding node */
639 struct ubifs_ch
*ch
= buf
;
642 err
= ubifs_add_snod(c
, sleb
, buf
, offs
);
645 node_len
= ALIGN(le32_to_cpu(ch
->len
), 8);
649 } else if (ret
> 0) {
650 /* Padding bytes or a valid padding node */
654 } else if (ret
== SCANNED_EMPTY_SPACE
||
655 ret
== SCANNED_GARBAGE
||
656 ret
== SCANNED_A_BAD_PAD_NODE
||
657 ret
== SCANNED_A_CORRUPT_NODE
) {
658 dbg_rcvry("found corruption - %d", ret
);
661 dbg_err("unexpected return value %d", ret
);
667 if (ret
== SCANNED_GARBAGE
|| ret
== SCANNED_A_BAD_PAD_NODE
) {
668 if (is_last_write(c
, buf
, offs
)) {
669 clean_buf(c
, &buf
, lnum
, &offs
, &len
);
672 goto corrupted_rescan
;
673 } else if (ret
== SCANNED_A_CORRUPT_NODE
) {
674 if (no_more_nodes(c
, buf
, len
, lnum
, offs
)) {
675 clean_buf(c
, &buf
, lnum
, &offs
, &len
);
678 goto corrupted_rescan
;
679 } else if (!is_empty(buf
, len
)) {
680 if (is_last_write(c
, buf
, offs
)) {
681 clean_buf(c
, &buf
, lnum
, &offs
, &len
);
684 int corruption
= first_non_ff(buf
, len
);
687 * See header comment for this file for more
688 * explanations about the reasons we have this check.
690 ubifs_err("corrupt empty space LEB %d:%d, corruption "
691 "starts at %d", lnum
, offs
, corruption
);
692 /* Make sure we dump interesting non-0xFF data */
699 /* Drop nodes from incomplete group */
700 if (grouped
&& drop_incomplete_group(sleb
, &offs
)) {
702 len
= c
->leb_size
- offs
;
703 clean_buf(c
, &buf
, lnum
, &offs
, &len
);
707 if (offs
% c
->min_io_size
) {
708 clean_buf(c
, &buf
, lnum
, &offs
, &len
);
712 ubifs_end_scan(c
, sleb
, lnum
, offs
);
715 err
= fix_unclean_leb(c
, sleb
, start
);
723 /* Re-scan the corrupted data with verbose messages */
724 dbg_err("corruptio %d", ret
);
725 ubifs_scan_a_node(c
, buf
, len
, lnum
, offs
, 1);
727 ubifs_scanned_corruption(c
, lnum
, offs
, buf
);
730 ubifs_err("LEB %d scanning failed", lnum
);
731 ubifs_scan_destroy(sleb
);
736 * get_cs_sqnum - get commit start sequence number.
737 * @c: UBIFS file-system description object
738 * @lnum: LEB number of commit start node
739 * @offs: offset of commit start node
740 * @cs_sqnum: commit start sequence number is returned here
742 * This function returns %0 on success and a negative error code on failure.
744 static int get_cs_sqnum(struct ubifs_info
*c
, int lnum
, int offs
,
745 unsigned long long *cs_sqnum
)
747 struct ubifs_cs_node
*cs_node
= NULL
;
750 dbg_rcvry("at %d:%d", lnum
, offs
);
751 cs_node
= kmalloc(UBIFS_CS_NODE_SZ
, GFP_KERNEL
);
754 if (c
->leb_size
- offs
< UBIFS_CS_NODE_SZ
)
756 err
= ubi_read(c
->ubi
, lnum
, (void *)cs_node
, offs
, UBIFS_CS_NODE_SZ
);
757 if (err
&& err
!= -EBADMSG
)
759 ret
= ubifs_scan_a_node(c
, cs_node
, UBIFS_CS_NODE_SZ
, lnum
, offs
, 0);
760 if (ret
!= SCANNED_A_NODE
) {
761 dbg_err("Not a valid node");
764 if (cs_node
->ch
.node_type
!= UBIFS_CS_NODE
) {
765 dbg_err("Node a CS node, type is %d", cs_node
->ch
.node_type
);
768 if (le64_to_cpu(cs_node
->cmt_no
) != c
->cmt_no
) {
769 dbg_err("CS node cmt_no %llu != current cmt_no %llu",
770 (unsigned long long)le64_to_cpu(cs_node
->cmt_no
),
774 *cs_sqnum
= le64_to_cpu(cs_node
->ch
.sqnum
);
775 dbg_rcvry("commit start sqnum %llu", *cs_sqnum
);
782 ubifs_err("failed to get CS sqnum");
788 * ubifs_recover_log_leb - scan and recover a log LEB.
789 * @c: UBIFS file-system description object
792 * @sbuf: LEB-sized buffer to use
794 * This function does a scan of a LEB, but caters for errors that might have
795 * been caused by unclean reboots from which we are attempting to recover
796 * (assume that only the last log LEB can be corrupted by an unclean reboot).
798 * This function returns %0 on success and a negative error code on failure.
800 struct ubifs_scan_leb
*ubifs_recover_log_leb(struct ubifs_info
*c
, int lnum
,
801 int offs
, void *sbuf
)
803 struct ubifs_scan_leb
*sleb
;
806 dbg_rcvry("LEB %d", lnum
);
807 next_lnum
= lnum
+ 1;
808 if (next_lnum
>= UBIFS_LOG_LNUM
+ c
->log_lebs
)
809 next_lnum
= UBIFS_LOG_LNUM
;
810 if (next_lnum
!= c
->ltail_lnum
) {
812 * We can only recover at the end of the log, so check that the
813 * next log LEB is empty or out of date.
815 sleb
= ubifs_scan(c
, next_lnum
, 0, sbuf
, 0);
818 if (sleb
->nodes_cnt
) {
819 struct ubifs_scan_node
*snod
;
820 unsigned long long cs_sqnum
= c
->cs_sqnum
;
822 snod
= list_entry(sleb
->nodes
.next
,
823 struct ubifs_scan_node
, list
);
827 err
= get_cs_sqnum(c
, lnum
, offs
, &cs_sqnum
);
829 ubifs_scan_destroy(sleb
);
833 if (snod
->sqnum
> cs_sqnum
) {
834 ubifs_err("unrecoverable log corruption "
836 ubifs_scan_destroy(sleb
);
837 return ERR_PTR(-EUCLEAN
);
840 ubifs_scan_destroy(sleb
);
842 return ubifs_recover_leb(c
, lnum
, offs
, sbuf
, 0);
846 * recover_head - recover a head.
847 * @c: UBIFS file-system description object
848 * @lnum: LEB number of head to recover
849 * @offs: offset of head to recover
850 * @sbuf: LEB-sized buffer to use
852 * This function ensures that there is no data on the flash at a head location.
854 * This function returns %0 on success and a negative error code on failure.
856 static int recover_head(const struct ubifs_info
*c
, int lnum
, int offs
,
859 int len
= c
->max_write_size
, err
;
861 if (offs
+ len
> c
->leb_size
)
862 len
= c
->leb_size
- offs
;
867 /* Read at the head location and check it is empty flash */
868 err
= ubi_read(c
->ubi
, lnum
, sbuf
, offs
, len
);
869 if (err
|| !is_empty(sbuf
, len
)) {
870 dbg_rcvry("cleaning head at %d:%d", lnum
, offs
);
872 return ubifs_leb_unmap(c
, lnum
);
873 err
= ubi_read(c
->ubi
, lnum
, sbuf
, 0, offs
);
876 return ubi_leb_change(c
->ubi
, lnum
, sbuf
, offs
, UBI_UNKNOWN
);
883 * ubifs_recover_inl_heads - recover index and LPT heads.
884 * @c: UBIFS file-system description object
885 * @sbuf: LEB-sized buffer to use
887 * This function ensures that there is no data on the flash at the index and
888 * LPT head locations.
890 * This deals with the recovery of a half-completed journal commit. UBIFS is
891 * careful never to overwrite the last version of the index or the LPT. Because
892 * the index and LPT are wandering trees, data from a half-completed commit will
893 * not be referenced anywhere in UBIFS. The data will be either in LEBs that are
894 * assumed to be empty and will be unmapped anyway before use, or in the index
897 * This function returns %0 on success and a negative error code on failure.
899 int ubifs_recover_inl_heads(const struct ubifs_info
*c
, void *sbuf
)
903 ubifs_assert(!c
->ro_mount
|| c
->remounting_rw
);
905 dbg_rcvry("checking index head at %d:%d", c
->ihead_lnum
, c
->ihead_offs
);
906 err
= recover_head(c
, c
->ihead_lnum
, c
->ihead_offs
, sbuf
);
910 dbg_rcvry("checking LPT head at %d:%d", c
->nhead_lnum
, c
->nhead_offs
);
911 err
= recover_head(c
, c
->nhead_lnum
, c
->nhead_offs
, sbuf
);
919 * clean_an_unclean_leb - read and write a LEB to remove corruption.
920 * @c: UBIFS file-system description object
921 * @ucleb: unclean LEB information
922 * @sbuf: LEB-sized buffer to use
924 * This function reads a LEB up to a point pre-determined by the mount recovery,
925 * checks the nodes, and writes the result back to the flash, thereby cleaning
926 * off any following corruption, or non-fatal ECC errors.
928 * This function returns %0 on success and a negative error code on failure.
930 static int clean_an_unclean_leb(const struct ubifs_info
*c
,
931 struct ubifs_unclean_leb
*ucleb
, void *sbuf
)
933 int err
, lnum
= ucleb
->lnum
, offs
= 0, len
= ucleb
->endpt
, quiet
= 1;
936 dbg_rcvry("LEB %d len %d", lnum
, len
);
939 /* Nothing to read, just unmap it */
940 err
= ubifs_leb_unmap(c
, lnum
);
946 err
= ubi_read(c
->ubi
, lnum
, buf
, offs
, len
);
947 if (err
&& err
!= -EBADMSG
)
955 /* Scan quietly until there is an error */
956 ret
= ubifs_scan_a_node(c
, buf
, len
, lnum
, offs
, quiet
);
958 if (ret
== SCANNED_A_NODE
) {
959 /* A valid node, and not a padding node */
960 struct ubifs_ch
*ch
= buf
;
963 node_len
= ALIGN(le32_to_cpu(ch
->len
), 8);
971 /* Padding bytes or a valid padding node */
978 if (ret
== SCANNED_EMPTY_SPACE
) {
979 ubifs_err("unexpected empty space at %d:%d",
985 /* Redo the last scan but noisily */
990 ubifs_scanned_corruption(c
, lnum
, offs
, buf
);
994 /* Pad to min_io_size */
995 len
= ALIGN(ucleb
->endpt
, c
->min_io_size
);
996 if (len
> ucleb
->endpt
) {
997 int pad_len
= len
- ALIGN(ucleb
->endpt
, 8);
1000 buf
= c
->sbuf
+ len
- pad_len
;
1001 ubifs_pad(c
, buf
, pad_len
);
1005 /* Write back the LEB atomically */
1006 err
= ubi_leb_change(c
->ubi
, lnum
, sbuf
, len
, UBI_UNKNOWN
);
1010 dbg_rcvry("cleaned LEB %d", lnum
);
1016 * ubifs_clean_lebs - clean LEBs recovered during read-only mount.
1017 * @c: UBIFS file-system description object
1018 * @sbuf: LEB-sized buffer to use
1020 * This function cleans a LEB identified during recovery that needs to be
1021 * written but was not because UBIFS was mounted read-only. This happens when
1022 * remounting to read-write mode.
1024 * This function returns %0 on success and a negative error code on failure.
1026 int ubifs_clean_lebs(const struct ubifs_info
*c
, void *sbuf
)
1028 dbg_rcvry("recovery");
1029 while (!list_empty(&c
->unclean_leb_list
)) {
1030 struct ubifs_unclean_leb
*ucleb
;
1033 ucleb
= list_entry(c
->unclean_leb_list
.next
,
1034 struct ubifs_unclean_leb
, list
);
1035 err
= clean_an_unclean_leb(c
, ucleb
, sbuf
);
1038 list_del(&ucleb
->list
);
1045 * grab_empty_leb - grab an empty LEB to use as GC LEB and run commit.
1046 * @c: UBIFS file-system description object
1048 * This is a helper function for 'ubifs_rcvry_gc_commit()' which grabs an empty
1049 * LEB to be used as GC LEB (@c->gc_lnum), and then runs the commit. Returns
1050 * zero in case of success and a negative error code in case of failure.
1052 static int grab_empty_leb(struct ubifs_info
*c
)
1057 * Note, it is very important to first search for an empty LEB and then
1058 * run the commit, not vice-versa. The reason is that there might be
1059 * only one empty LEB at the moment, the one which has been the
1060 * @c->gc_lnum just before the power cut happened. During the regular
1061 * UBIFS operation (not now) @c->gc_lnum is marked as "taken", so no
1062 * one but GC can grab it. But at this moment this single empty LEB is
1063 * not marked as taken, so if we run commit - what happens? Right, the
1064 * commit will grab it and write the index there. Remember that the
1065 * index always expands as long as there is free space, and it only
1066 * starts consolidating when we run out of space.
1068 * IOW, if we run commit now, we might not be able to find a free LEB
1071 lnum
= ubifs_find_free_leb_for_idx(c
);
1073 dbg_err("could not find an empty LEB");
1075 dbg_dump_budg(c
, &c
->bi
);
1079 /* Reset the index flag */
1080 err
= ubifs_change_one_lp(c
, lnum
, LPROPS_NC
, LPROPS_NC
, 0,
1086 dbg_rcvry("found empty LEB %d, run commit", lnum
);
1088 return ubifs_run_commit(c
);
1092 * ubifs_rcvry_gc_commit - recover the GC LEB number and run the commit.
1093 * @c: UBIFS file-system description object
1095 * Out-of-place garbage collection requires always one empty LEB with which to
1096 * start garbage collection. The LEB number is recorded in c->gc_lnum and is
1097 * written to the master node on unmounting. In the case of an unclean unmount
1098 * the value of gc_lnum recorded in the master node is out of date and cannot
1099 * be used. Instead, recovery must allocate an empty LEB for this purpose.
1100 * However, there may not be enough empty space, in which case it must be
1101 * possible to GC the dirtiest LEB into the GC head LEB.
1103 * This function also runs the commit which causes the TNC updates from
1104 * size-recovery and orphans to be written to the flash. That is important to
1105 * ensure correct replay order for subsequent mounts.
1107 * This function returns %0 on success and a negative error code on failure.
1109 int ubifs_rcvry_gc_commit(struct ubifs_info
*c
)
1111 struct ubifs_wbuf
*wbuf
= &c
->jheads
[GCHD
].wbuf
;
1112 struct ubifs_lprops lp
;
1115 dbg_rcvry("GC head LEB %d, offs %d", wbuf
->lnum
, wbuf
->offs
);
1118 if (wbuf
->lnum
== -1 || wbuf
->offs
== c
->leb_size
)
1119 return grab_empty_leb(c
);
1121 err
= ubifs_find_dirty_leb(c
, &lp
, wbuf
->offs
, 2);
1126 dbg_rcvry("could not find a dirty LEB");
1127 return grab_empty_leb(c
);
1130 ubifs_assert(!(lp
.flags
& LPROPS_INDEX
));
1131 ubifs_assert(lp
.free
+ lp
.dirty
>= wbuf
->offs
);
1134 * We run the commit before garbage collection otherwise subsequent
1135 * mounts will see the GC and orphan deletion in a different order.
1137 dbg_rcvry("committing");
1138 err
= ubifs_run_commit(c
);
1142 dbg_rcvry("GC'ing LEB %d", lp
.lnum
);
1143 mutex_lock_nested(&wbuf
->io_mutex
, wbuf
->jhead
);
1144 err
= ubifs_garbage_collect_leb(c
, &lp
);
1146 int err2
= ubifs_wbuf_sync_nolock(wbuf
);
1151 mutex_unlock(&wbuf
->io_mutex
);
1153 dbg_err("GC failed, error %d", err
);
1159 ubifs_assert(err
== LEB_RETAINED
);
1160 if (err
!= LEB_RETAINED
)
1163 err
= ubifs_leb_unmap(c
, c
->gc_lnum
);
1167 dbg_rcvry("allocated LEB %d for GC", lp
.lnum
);
1172 * struct size_entry - inode size information for recovery.
1173 * @rb: link in the RB-tree of sizes
1174 * @inum: inode number
1175 * @i_size: size on inode
1176 * @d_size: maximum size based on data nodes
1177 * @exists: indicates whether the inode exists
1178 * @inode: inode if pinned in memory awaiting rw mode to fix it
1186 struct inode
*inode
;
1190 * add_ino - add an entry to the size tree.
1191 * @c: UBIFS file-system description object
1192 * @inum: inode number
1193 * @i_size: size on inode
1194 * @d_size: maximum size based on data nodes
1195 * @exists: indicates whether the inode exists
1197 static int add_ino(struct ubifs_info
*c
, ino_t inum
, loff_t i_size
,
1198 loff_t d_size
, int exists
)
1200 struct rb_node
**p
= &c
->size_tree
.rb_node
, *parent
= NULL
;
1201 struct size_entry
*e
;
1205 e
= rb_entry(parent
, struct size_entry
, rb
);
1209 p
= &(*p
)->rb_right
;
1212 e
= kzalloc(sizeof(struct size_entry
), GFP_KERNEL
);
1221 rb_link_node(&e
->rb
, parent
, p
);
1222 rb_insert_color(&e
->rb
, &c
->size_tree
);
1228 * find_ino - find an entry on the size tree.
1229 * @c: UBIFS file-system description object
1230 * @inum: inode number
1232 static struct size_entry
*find_ino(struct ubifs_info
*c
, ino_t inum
)
1234 struct rb_node
*p
= c
->size_tree
.rb_node
;
1235 struct size_entry
*e
;
1238 e
= rb_entry(p
, struct size_entry
, rb
);
1241 else if (inum
> e
->inum
)
1250 * remove_ino - remove an entry from the size tree.
1251 * @c: UBIFS file-system description object
1252 * @inum: inode number
1254 static void remove_ino(struct ubifs_info
*c
, ino_t inum
)
1256 struct size_entry
*e
= find_ino(c
, inum
);
1260 rb_erase(&e
->rb
, &c
->size_tree
);
1265 * ubifs_destroy_size_tree - free resources related to the size tree.
1266 * @c: UBIFS file-system description object
1268 void ubifs_destroy_size_tree(struct ubifs_info
*c
)
1270 struct rb_node
*this = c
->size_tree
.rb_node
;
1271 struct size_entry
*e
;
1274 if (this->rb_left
) {
1275 this = this->rb_left
;
1277 } else if (this->rb_right
) {
1278 this = this->rb_right
;
1281 e
= rb_entry(this, struct size_entry
, rb
);
1284 this = rb_parent(this);
1286 if (this->rb_left
== &e
->rb
)
1287 this->rb_left
= NULL
;
1289 this->rb_right
= NULL
;
1293 c
->size_tree
= RB_ROOT
;
1297 * ubifs_recover_size_accum - accumulate inode sizes for recovery.
1298 * @c: UBIFS file-system description object
1300 * @deletion: node is for a deletion
1301 * @new_size: inode size
1303 * This function has two purposes:
1304 * 1) to ensure there are no data nodes that fall outside the inode size
1305 * 2) to ensure there are no data nodes for inodes that do not exist
1306 * To accomplish those purposes, a rb-tree is constructed containing an entry
1307 * for each inode number in the journal that has not been deleted, and recording
1308 * the size from the inode node, the maximum size of any data node (also altered
1309 * by truncations) and a flag indicating a inode number for which no inode node
1310 * was present in the journal.
1312 * Note that there is still the possibility that there are data nodes that have
1313 * been committed that are beyond the inode size, however the only way to find
1314 * them would be to scan the entire index. Alternatively, some provision could
1315 * be made to record the size of inodes at the start of commit, which would seem
1316 * very cumbersome for a scenario that is quite unlikely and the only negative
1317 * consequence of which is wasted space.
1319 * This functions returns %0 on success and a negative error code on failure.
1321 int ubifs_recover_size_accum(struct ubifs_info
*c
, union ubifs_key
*key
,
1322 int deletion
, loff_t new_size
)
1324 ino_t inum
= key_inum(c
, key
);
1325 struct size_entry
*e
;
1328 switch (key_type(c
, key
)) {
1331 remove_ino(c
, inum
);
1333 e
= find_ino(c
, inum
);
1335 e
->i_size
= new_size
;
1338 err
= add_ino(c
, inum
, new_size
, 0, 1);
1344 case UBIFS_DATA_KEY
:
1345 e
= find_ino(c
, inum
);
1347 if (new_size
> e
->d_size
)
1348 e
->d_size
= new_size
;
1350 err
= add_ino(c
, inum
, 0, new_size
, 0);
1355 case UBIFS_TRUN_KEY
:
1356 e
= find_ino(c
, inum
);
1358 e
->d_size
= new_size
;
1365 * fix_size_in_place - fix inode size in place on flash.
1366 * @c: UBIFS file-system description object
1367 * @e: inode size information for recovery
1369 static int fix_size_in_place(struct ubifs_info
*c
, struct size_entry
*e
)
1371 struct ubifs_ino_node
*ino
= c
->sbuf
;
1373 union ubifs_key key
;
1374 int err
, lnum
, offs
, len
;
1378 /* Locate the inode node LEB number and offset */
1379 ino_key_init(c
, &key
, e
->inum
);
1380 err
= ubifs_tnc_locate(c
, &key
, ino
, &lnum
, &offs
);
1384 * If the size recorded on the inode node is greater than the size that
1385 * was calculated from nodes in the journal then don't change the inode.
1387 i_size
= le64_to_cpu(ino
->size
);
1388 if (i_size
>= e
->d_size
)
1391 err
= ubi_read(c
->ubi
, lnum
, c
->sbuf
, 0, c
->leb_size
);
1394 /* Change the size field and recalculate the CRC */
1395 ino
= c
->sbuf
+ offs
;
1396 ino
->size
= cpu_to_le64(e
->d_size
);
1397 len
= le32_to_cpu(ino
->ch
.len
);
1398 crc
= crc32(UBIFS_CRC32_INIT
, (void *)ino
+ 8, len
- 8);
1399 ino
->ch
.crc
= cpu_to_le32(crc
);
1400 /* Work out where data in the LEB ends and free space begins */
1402 len
= c
->leb_size
- 1;
1403 while (p
[len
] == 0xff)
1405 len
= ALIGN(len
+ 1, c
->min_io_size
);
1406 /* Atomically write the fixed LEB back again */
1407 err
= ubi_leb_change(c
->ubi
, lnum
, c
->sbuf
, len
, UBI_UNKNOWN
);
1410 dbg_rcvry("inode %lu at %d:%d size %lld -> %lld",
1411 (unsigned long)e
->inum
, lnum
, offs
, i_size
, e
->d_size
);
1415 ubifs_warn("inode %lu failed to fix size %lld -> %lld error %d",
1416 (unsigned long)e
->inum
, e
->i_size
, e
->d_size
, err
);
1421 * ubifs_recover_size - recover inode size.
1422 * @c: UBIFS file-system description object
1424 * This function attempts to fix inode size discrepancies identified by the
1425 * 'ubifs_recover_size_accum()' function.
1427 * This functions returns %0 on success and a negative error code on failure.
1429 int ubifs_recover_size(struct ubifs_info
*c
)
1431 struct rb_node
*this = rb_first(&c
->size_tree
);
1434 struct size_entry
*e
;
1437 e
= rb_entry(this, struct size_entry
, rb
);
1439 union ubifs_key key
;
1441 ino_key_init(c
, &key
, e
->inum
);
1442 err
= ubifs_tnc_lookup(c
, &key
, c
->sbuf
);
1443 if (err
&& err
!= -ENOENT
)
1445 if (err
== -ENOENT
) {
1446 /* Remove data nodes that have no inode */
1447 dbg_rcvry("removing ino %lu",
1448 (unsigned long)e
->inum
);
1449 err
= ubifs_tnc_remove_ino(c
, e
->inum
);
1453 struct ubifs_ino_node
*ino
= c
->sbuf
;
1456 e
->i_size
= le64_to_cpu(ino
->size
);
1460 if (e
->exists
&& e
->i_size
< e
->d_size
) {
1462 /* Fix the inode size and pin it in memory */
1463 struct inode
*inode
;
1464 struct ubifs_inode
*ui
;
1466 ubifs_assert(!e
->inode
);
1468 inode
= ubifs_iget(c
->vfs_sb
, e
->inum
);
1470 return PTR_ERR(inode
);
1472 ui
= ubifs_inode(inode
);
1473 if (inode
->i_size
< e
->d_size
) {
1474 dbg_rcvry("ino %lu size %lld -> %lld",
1475 (unsigned long)e
->inum
,
1476 inode
->i_size
, e
->d_size
);
1477 inode
->i_size
= e
->d_size
;
1478 ui
->ui_size
= e
->d_size
;
1479 ui
->synced_i_size
= e
->d_size
;
1481 this = rb_next(this);
1486 /* Fix the size in place */
1487 err
= fix_size_in_place(c
, e
);
1495 this = rb_next(this);
1496 rb_erase(&e
->rb
, &c
->size_tree
);