2 * This file is part of UBIFS.
4 * Copyright (C) 2006-2008 Nokia Corporation
6 * This program is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License version 2 as published by
8 * the Free Software Foundation.
10 * This program is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
15 * You should have received a copy of the GNU General Public License along with
16 * this program; if not, write to the Free Software Foundation, Inc., 51
17 * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 * Authors: Adrian Hunter
20 * Artem Bityutskiy (Битюцкий Артём)
24 * This file implements functions needed to recover from unclean un-mounts.
25 * When UBIFS is mounted, it checks a flag on the master node to determine if
26 * an un-mount was completed successfully. If not, the process of mounting
27 * incorporates additional checking and fixing of on-flash data structures.
28 * UBIFS always cleans away all remnants of an unclean un-mount, so that
29 * errors do not accumulate. However UBIFS defers recovery if it is mounted
30 * read-only, and the flash is not modified in that case.
32 * The general UBIFS approach to the recovery is that it recovers from
33 * corruptions which could be caused by power cuts, but it refuses to recover
34 * from corruption caused by other reasons. And UBIFS tries to distinguish
35 * between these 2 reasons of corruptions and silently recover in the former
36 * case and loudly complain in the latter case.
38 * UBIFS writes only to erased LEBs, so it writes only to the flash space
39 * containing only 0xFFs. UBIFS also always writes strictly from the beginning
40 * of the LEB to the end. And UBIFS assumes that the underlying flash media
41 * writes in @c->max_write_size bytes at a time.
43 * Hence, if UBIFS finds a corrupted node at offset X, it expects only the min.
44 * I/O unit corresponding to offset X to contain corrupted data, all the
45 * following min. I/O units have to contain empty space (all 0xFFs). If this is
46 * not true, the corruption cannot be the result of a power cut, and UBIFS
50 #include <linux/crc32.h>
51 #include <linux/slab.h>
55 * is_empty - determine whether a buffer is empty (contains all 0xff).
56 * @buf: buffer to clean
57 * @len: length of buffer
59 * This function returns %1 if the buffer is empty (contains all 0xff) otherwise
62 static int is_empty(void *buf, int len)
67 for (i = 0; i < len; i++)
74 * first_non_ff - find offset of the first non-0xff byte.
75 * @buf: buffer to search in
76 * @len: length of buffer
78 * This function returns offset of the first non-0xff byte in @buf or %-1 if
79 * the buffer contains only 0xff bytes.
81 static int first_non_ff(void *buf, int len)
86 for (i = 0; i < len; i++)
93 * get_master_node - get the last valid master node allowing for corruption.
94 * @c: UBIFS file-system description object
96 * @pbuf: buffer containing the LEB read, is returned here
97 * @mst: master node, if found, is returned here
98 * @cor: corruption, if found, is returned here
100 * This function allocates a buffer, reads the LEB into it, and finds and
101 * returns the last valid master node allowing for one area of corruption.
102 * The corrupt area, if there is one, must be consistent with the assumption
103 * that it is the result of an unclean unmount while the master node was being
104 * written. Under those circumstances, it is valid to use the previously written
107 * This function returns %0 on success and a negative error code on failure.
109 static int get_master_node(const struct ubifs_info *c, int lnum, void **pbuf,
110 struct ubifs_mst_node **mst, void **cor)
112 const int sz = c->mst_node_alsz;
116 sbuf = vmalloc(c->leb_size);
120 err = ubifs_leb_read(c, lnum, sbuf, 0, c->leb_size, 0);
121 if (err && err != -EBADMSG)
124 /* Find the first position that is definitely not a node */
128 while (offs + UBIFS_MST_NODE_SZ <= c->leb_size) {
129 struct ubifs_ch *ch = buf;
131 if (le32_to_cpu(ch->magic) != UBIFS_NODE_MAGIC)
137 /* See if there was a valid master node before that */
144 ret = ubifs_scan_a_node(c, buf, len, lnum, offs, 1);
145 if (ret != SCANNED_A_NODE && offs) {
146 /* Could have been corruption so check one place back */
150 ret = ubifs_scan_a_node(c, buf, len, lnum, offs, 1);
151 if (ret != SCANNED_A_NODE)
153 * We accept only one area of corruption because
154 * we are assuming that it was caused while
155 * trying to write a master node.
159 if (ret == SCANNED_A_NODE) {
160 struct ubifs_ch *ch = buf;
162 if (ch->node_type != UBIFS_MST_NODE)
164 dbg_rcvry("found a master node at %d:%d", lnum, offs);
171 /* Check for corruption */
172 if (offs < c->leb_size) {
173 if (!is_empty(buf, min_t(int, len, sz))) {
175 dbg_rcvry("found corruption at %d:%d", lnum, offs);
181 /* Check remaining empty space */
182 if (offs < c->leb_size)
183 if (!is_empty(buf, len)) {
184 int corruption = first_non_ff(buf, len);
185 ubifs_err("corrupt empty space LEB %d:%d, corruption starts at %d",
186 lnum, offs, corruption);
187 ubifs_scanned_corruption(c, lnum, offs + corruption, buf + corruption);
203 * write_rcvrd_mst_node - write recovered master node.
204 * @c: UBIFS file-system description object
207 * This function returns %0 on success and a negative error code on failure.
209 static int write_rcvrd_mst_node(struct ubifs_info *c,
210 struct ubifs_mst_node *mst)
212 int err = 0, lnum = UBIFS_MST_LNUM, sz = c->mst_node_alsz;
215 dbg_rcvry("recovery");
217 save_flags = mst->flags;
218 mst->flags |= cpu_to_le32(UBIFS_MST_RCVRY);
220 ubifs_prepare_node(c, mst, UBIFS_MST_NODE_SZ, 1);
221 err = ubifs_leb_change(c, lnum, mst, sz);
224 err = ubifs_leb_change(c, lnum + 1, mst, sz);
228 mst->flags = save_flags;
233 * ubifs_recover_master_node - recover the master node.
234 * @c: UBIFS file-system description object
236 * This function recovers the master node from corruption that may occur due to
237 * an unclean unmount.
239 * This function returns %0 on success and a negative error code on failure.
241 int ubifs_recover_master_node(struct ubifs_info *c)
243 void *buf1 = NULL, *buf2 = NULL, *cor1 = NULL, *cor2 = NULL;
244 struct ubifs_mst_node *mst1 = NULL, *mst2 = NULL, *mst;
245 const int sz = c->mst_node_alsz;
246 int err, offs1, offs2;
248 dbg_rcvry("recovery");
250 err = get_master_node(c, UBIFS_MST_LNUM, &buf1, &mst1, &cor1);
252 dbg_rcvry("get 1st master node failed %d", err);
254 err = get_master_node(c, UBIFS_MST_LNUM + 1, &buf2, &mst2, &cor2);
256 dbg_rcvry("get 2nd master node failed %d", err);
259 offs1 = (void *)mst1 - buf1;
260 if ((le32_to_cpu(mst1->flags) & UBIFS_MST_RCVRY) &&
261 (offs1 == 0 && !cor1)) {
263 * mst1 was written by recovery at offset 0 with no
266 dbg_rcvry("recovery recovery");
269 offs2 = (void *)mst2 - buf2;
270 if (offs1 == offs2) {
271 /* Same offset, so must be the same */
272 if (memcmp((void *)mst1 + UBIFS_CH_SZ,
273 (void *)mst2 + UBIFS_CH_SZ,
274 UBIFS_MST_NODE_SZ - UBIFS_CH_SZ))
277 } else if (offs2 + sz == offs1) {
278 /* 1st LEB was written, 2nd was not */
282 } else if (offs1 == 0 &&
283 c->leb_size - offs2 - sz < sz) {
284 /* 1st LEB was unmapped and written, 2nd not */
292 * 2nd LEB was unmapped and about to be written, so
293 * there must be only one master node in the first LEB
296 if (offs1 != 0 || cor1)
304 * 1st LEB was unmapped and about to be written, so there must
305 * be no room left in 2nd LEB.
307 offs2 = (void *)mst2 - buf2;
308 if (offs2 + sz + sz <= c->leb_size)
313 ubifs_msg("recovered master node from LEB %d",
314 (mst == mst1 ? UBIFS_MST_LNUM : UBIFS_MST_LNUM + 1));
316 memcpy(c->mst_node, mst, UBIFS_MST_NODE_SZ);
319 /* Read-only mode. Keep a copy for switching to rw mode */
320 c->rcvrd_mst_node = kmalloc(sz, GFP_KERNEL);
321 if (!c->rcvrd_mst_node) {
325 memcpy(c->rcvrd_mst_node, c->mst_node, UBIFS_MST_NODE_SZ);
328 * We had to recover the master node, which means there was an
329 * unclean reboot. However, it is possible that the master node
330 * is clean at this point, i.e., %UBIFS_MST_DIRTY is not set.
331 * E.g., consider the following chain of events:
333 * 1. UBIFS was cleanly unmounted, so the master node is clean
334 * 2. UBIFS is being mounted R/W and starts changing the master
335 * node in the first (%UBIFS_MST_LNUM). A power cut happens,
336 * so this LEB ends up with some amount of garbage at the
338 * 3. UBIFS is being mounted R/O. We reach this place and
339 * recover the master node from the second LEB
340 * (%UBIFS_MST_LNUM + 1). But we cannot update the media
341 * because we are being mounted R/O. We have to defer the
343 * 4. However, this master node (@c->mst_node) is marked as
344 * clean (since the step 1). And if we just return, the
345 * mount code will be confused and won't recover the master
346 * node when it is re-mounter R/W later.
348 * Thus, to force the recovery by marking the master node as
351 c->mst_node->flags |= cpu_to_le32(UBIFS_MST_DIRTY);
353 /* Write the recovered master node */
354 c->max_sqnum = le64_to_cpu(mst->ch.sqnum) - 1;
355 err = write_rcvrd_mst_node(c, c->mst_node);
368 ubifs_err("failed to recover master node");
370 ubifs_err("dumping first master node");
371 ubifs_dump_node(c, mst1);
374 ubifs_err("dumping second master node");
375 ubifs_dump_node(c, mst2);
383 * ubifs_write_rcvrd_mst_node - write the recovered master node.
384 * @c: UBIFS file-system description object
386 * This function writes the master node that was recovered during mounting in
387 * read-only mode and must now be written because we are remounting rw.
389 * This function returns %0 on success and a negative error code on failure.
391 int ubifs_write_rcvrd_mst_node(struct ubifs_info *c)
395 if (!c->rcvrd_mst_node)
397 c->rcvrd_mst_node->flags |= cpu_to_le32(UBIFS_MST_DIRTY);
398 c->mst_node->flags |= cpu_to_le32(UBIFS_MST_DIRTY);
399 err = write_rcvrd_mst_node(c, c->rcvrd_mst_node);
402 kfree(c->rcvrd_mst_node);
403 c->rcvrd_mst_node = NULL;
408 * is_last_write - determine if an offset was in the last write to a LEB.
409 * @c: UBIFS file-system description object
410 * @buf: buffer to check
411 * @offs: offset to check
413 * This function returns %1 if @offs was in the last write to the LEB whose data
414 * is in @buf, otherwise %0 is returned. The determination is made by checking
415 * for subsequent empty space starting from the next @c->max_write_size
418 static int is_last_write(const struct ubifs_info *c, void *buf, int offs)
421 * The empty corruption may harmless, but this
422 * is a bad habit for sw development, fix me.
426 int empty_offs, check_len;
430 * Round up to the next @c->max_write_size boundary i.e. @offs is in
431 * the last wbuf written. After that should be empty space.
433 empty_offs = ALIGN(offs + 1, c->max_write_size);
434 check_len = c->leb_size - empty_offs;
435 p = buf + empty_offs - offs;
436 return is_empty(p, check_len);
441 * clean_buf - clean the data from an LEB sitting in a buffer.
442 * @c: UBIFS file-system description object
443 * @buf: buffer to clean
444 * @lnum: LEB number to clean
445 * @offs: offset from which to clean
446 * @len: length of buffer
448 * This function pads up to the next min_io_size boundary (if there is one) and
449 * sets empty space to all 0xff. @buf, @offs and @len are updated to the next
450 * @c->min_io_size boundary.
452 static void clean_buf(const struct ubifs_info *c, void **buf, int lnum,
455 int empty_offs, pad_len;
458 dbg_rcvry("cleaning corruption at %d:%d", lnum, *offs);
460 ubifs_assert(!(*offs & 7));
461 empty_offs = ALIGN(*offs, c->min_io_size);
462 pad_len = empty_offs - *offs;
463 ubifs_pad(c, *buf, pad_len);
467 memset(*buf, 0xff, c->leb_size - empty_offs);
471 * no_more_nodes - determine if there are no more nodes in a buffer.
472 * @c: UBIFS file-system description object
473 * @buf: buffer to check
474 * @len: length of buffer
475 * @lnum: LEB number of the LEB from which @buf was read
476 * @offs: offset from which @buf was read
478 * This function ensures that the corrupted node at @offs is the last thing
479 * written to a LEB. This function returns %1 if more data is not found and
480 * %0 if more data is found.
482 static int no_more_nodes(const struct ubifs_info *c, void *buf, int len,
485 struct ubifs_ch *ch = buf;
486 int skip, dlen = le32_to_cpu(ch->len);
488 /* Check for empty space after the corrupt node's common header */
489 skip = ALIGN(offs + UBIFS_CH_SZ, c->max_write_size) - offs;
490 if (is_empty(buf + skip, len - skip))
493 * The area after the common header size is not empty, so the common
494 * header must be intact. Check it.
496 if (ubifs_check_node(c, buf, lnum, offs, 1, 0) != -EUCLEAN) {
497 dbg_rcvry("unexpected bad common header at %d:%d", lnum, offs);
500 /* Now we know the corrupt node's length we can skip over it */
501 skip = ALIGN(offs + dlen, c->max_write_size) - offs;
502 /* After which there should be empty space */
503 if (!is_empty(buf + skip, len - skip)) {
504 int corruption = first_non_ff(buf + skip, len - skip);
505 ubifs_err("unexpected data at LEB %d:%d, corruption starts at %d",
506 lnum, offs + skip, corruption);
507 ubifs_scanned_corruption(c, lnum, offs + skip + corruption, buf + skip + corruption);
514 * ubifs_fix_unclean_leb - fix an unclean LEB.
515 * @c: UBIFS file-system description object
516 * @sleb: scanned LEB information
517 * @start: offset where scan started
519 int ubifs_fix_unclean_leb(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
522 int lnum = sleb->lnum, endpt = start;
524 /* Get the end offset of the last node we are keeping */
525 if (!list_empty(&sleb->nodes)) {
526 struct ubifs_scan_node *snod;
528 snod = list_entry(sleb->nodes.prev,
529 struct ubifs_scan_node, list);
530 endpt = snod->offs + snod->len;
533 if (c->ro_mount && !c->remounting_rw) {
534 /* Add to recovery list */
535 struct ubifs_unclean_leb *ucleb;
537 dbg_rcvry("need to fix LEB %d start %d endpt %d",
538 lnum, start, sleb->endpt);
539 ucleb = kzalloc(sizeof(struct ubifs_unclean_leb), GFP_NOFS);
543 ucleb->endpt = endpt;
544 list_add_tail(&ucleb->list, &c->unclean_leb_list);
546 /* Write the fixed LEB back to flash */
549 dbg_rcvry("fixing LEB %d start %d endpt %d",
550 lnum, start, sleb->endpt);
552 err = ubifs_leb_unmap(c, lnum);
556 int len = ALIGN(endpt, c->min_io_size);
559 err = ubifs_leb_read(c, lnum, sleb->buf, 0,
564 /* Pad to min_io_size */
566 int pad_len = len - ALIGN(endpt, 8);
569 void *buf = sleb->buf + len - pad_len;
571 ubifs_pad(c, buf, pad_len);
574 err = ubifs_leb_change(c, lnum, sleb->buf, len);
583 * drop_last_group - drop the last group of nodes.
584 * @sleb: scanned LEB information
585 * @offs: offset of dropped nodes is returned here
587 * This is a helper function for 'ubifs_recover_leb()' which drops the last
588 * group of nodes of the scanned LEB.
590 static void drop_last_group(struct ubifs_scan_leb *sleb, int *offs)
592 while (!list_empty(&sleb->nodes)) {
593 struct ubifs_scan_node *snod;
596 snod = list_entry(sleb->nodes.prev, struct ubifs_scan_node,
599 if (ch->group_type != UBIFS_IN_NODE_GROUP)
602 dbg_rcvry("dropping grouped node at %d:%d",
603 sleb->lnum, snod->offs);
605 list_del(&snod->list);
607 sleb->nodes_cnt -= 1;
612 * drop_last_node - drop the last node.
613 * @sleb: scanned LEB information
614 * @offs: offset of dropped nodes is returned here
615 * @grouped: non-zero if whole group of nodes have to be dropped
617 * This is a helper function for 'ubifs_recover_leb()' which drops the last
618 * node of the scanned LEB.
620 static void drop_last_node(struct ubifs_scan_leb *sleb, int *offs)
622 struct ubifs_scan_node *snod;
624 if (!list_empty(&sleb->nodes)) {
625 snod = list_entry(sleb->nodes.prev, struct ubifs_scan_node,
628 dbg_rcvry("dropping last node at %d:%d",
629 sleb->lnum, snod->offs);
631 list_del(&snod->list);
633 sleb->nodes_cnt -= 1;
638 * ubifs_recover_leb - scan and recover a LEB.
639 * @c: UBIFS file-system description object
642 * @sbuf: LEB-sized buffer to use
643 * @jhead: journal head number this LEB belongs to (%-1 if the LEB does not
644 * belong to any journal head)
646 * This function does a scan of a LEB, but caters for errors that might have
647 * been caused by the unclean unmount from which we are attempting to recover.
648 * Returns %0 in case of success, %-EUCLEAN if an unrecoverable corruption is
649 * found, and a negative error code in case of failure.
651 struct ubifs_scan_leb *ubifs_recover_leb(struct ubifs_info *c, int lnum,
652 int offs, void *sbuf, int jhead)
654 int ret = 0, err, len = c->leb_size - offs, start = offs, min_io_unit;
655 int grouped = jhead == -1 ? 0 : c->jheads[jhead].grouped;
656 struct ubifs_scan_leb *sleb;
657 void *buf = sbuf + offs;
659 dbg_rcvry("%d:%d, jhead %d, grouped %d", lnum, offs, jhead, grouped);
661 sleb = ubifs_start_scan(c, lnum, offs, sbuf);
665 ubifs_assert(len >= 8);
667 dbg_scan("look at LEB %d:%d (%d bytes left)",
673 * Scan quietly until there is an error from which we cannot
676 ret = ubifs_scan_a_node(c, buf, len, lnum, offs, 1);
677 if (ret == SCANNED_A_NODE) {
678 /* A valid node, and not a padding node */
679 struct ubifs_ch *ch = buf;
682 err = ubifs_add_snod(c, sleb, buf, offs);
685 node_len = ALIGN(le32_to_cpu(ch->len), 8);
689 } else if (ret > 0) {
690 /* Padding bytes or a valid padding node */
694 } else if (ret == SCANNED_EMPTY_SPACE ||
695 ret == SCANNED_GARBAGE ||
696 ret == SCANNED_A_BAD_PAD_NODE ||
697 ret == SCANNED_A_CORRUPT_NODE) {
698 dbg_rcvry("found corruption (%d) at %d:%d",
702 ubifs_err("unexpected return value %d", ret);
708 if (ret == SCANNED_GARBAGE || ret == SCANNED_A_BAD_PAD_NODE) {
709 if (!is_last_write(c, buf, offs))
710 goto corrupted_rescan;
711 } else if (ret == SCANNED_A_CORRUPT_NODE) {
712 if (!no_more_nodes(c, buf, len, lnum, offs))
713 goto corrupted_rescan;
714 } else if (!is_empty(buf, len)) {
715 if (!is_last_write(c, buf, offs)) {
716 int corruption = first_non_ff(buf, len);
719 * See header comment for this file for more
720 * explanations about the reasons we have this check.
722 ubifs_err("corrupt empty space LEB %d:%d, corruption starts at %d",
723 lnum, offs, corruption);
724 /* Make sure we dump interesting non-0xFF data */
731 min_io_unit = round_down(offs, c->min_io_size);
734 * If nodes are grouped, always drop the incomplete group at
737 drop_last_group(sleb, &offs);
741 * If this LEB belongs to the GC head then while we are in the
742 * middle of the same min. I/O unit keep dropping nodes. So
743 * basically, what we want is to make sure that the last min.
744 * I/O unit where we saw the corruption is dropped completely
745 * with all the uncorrupted nodes which may possibly sit there.
747 * In other words, let's name the min. I/O unit where the
748 * corruption starts B, and the previous min. I/O unit A. The
749 * below code tries to deal with a situation when half of B
750 * contains valid nodes or the end of a valid node, and the
751 * second half of B contains corrupted data or garbage. This
752 * means that UBIFS had been writing to B just before the power
753 * cut happened. I do not know how realistic is this scenario
754 * that half of the min. I/O unit had been written successfully
755 * and the other half not, but this is possible in our 'failure
756 * mode emulation' infrastructure at least.
758 * So what is the problem, why we need to drop those nodes? Why
759 * can't we just clean-up the second half of B by putting a
760 * padding node there? We can, and this works fine with one
761 * exception which was reproduced with power cut emulation
762 * testing and happens extremely rarely.
764 * Imagine the file-system is full, we run GC which starts
765 * moving valid nodes from LEB X to LEB Y (obviously, LEB Y is
766 * the current GC head LEB). The @c->gc_lnum is -1, which means
767 * that GC will retain LEB X and will try to continue. Imagine
768 * that LEB X is currently the dirtiest LEB, and the amount of
769 * used space in LEB Y is exactly the same as amount of free
772 * And a power cut happens when nodes are moved from LEB X to
773 * LEB Y. We are here trying to recover LEB Y which is the GC
774 * head LEB. We find the min. I/O unit B as described above.
775 * Then we clean-up LEB Y by padding min. I/O unit. And later
776 * 'ubifs_rcvry_gc_commit()' function fails, because it cannot
777 * find a dirty LEB which could be GC'd into LEB Y! Even LEB X
778 * does not match because the amount of valid nodes there does
779 * not fit the free space in LEB Y any more! And this is
780 * because of the padding node which we added to LEB Y. The
781 * user-visible effect of this which I once observed and
782 * analysed is that we cannot mount the file-system with
785 * So obviously, to make sure that situation does not happen we
786 * should free min. I/O unit B in LEB Y completely and the last
787 * used min. I/O unit in LEB Y should be A. This is basically
788 * what the below code tries to do.
790 while (offs > min_io_unit)
791 drop_last_node(sleb, &offs);
795 len = c->leb_size - offs;
797 clean_buf(c, &buf, lnum, &offs, &len);
798 ubifs_end_scan(c, sleb, lnum, offs);
800 err = ubifs_fix_unclean_leb(c, sleb, start);
807 /* Re-scan the corrupted data with verbose messages */
808 ubifs_err("corruption %d", ret);
809 ubifs_scan_a_node(c, buf, len, lnum, offs, 1);
811 ubifs_scanned_corruption(c, lnum, offs, buf);
814 ubifs_err("LEB %d scanning failed", lnum);
815 ubifs_scan_destroy(sleb);
820 * get_cs_sqnum - get commit start sequence number.
821 * @c: UBIFS file-system description object
822 * @lnum: LEB number of commit start node
823 * @offs: offset of commit start node
824 * @cs_sqnum: commit start sequence number is returned here
826 * This function returns %0 on success and a negative error code on failure.
828 static int get_cs_sqnum(struct ubifs_info *c, int lnum, int offs,
829 unsigned long long *cs_sqnum)
831 struct ubifs_cs_node *cs_node = NULL;
834 dbg_rcvry("at %d:%d", lnum, offs);
835 cs_node = kmalloc(UBIFS_CS_NODE_SZ, GFP_KERNEL);
838 if (c->leb_size - offs < UBIFS_CS_NODE_SZ)
840 err = ubifs_leb_read(c, lnum, (void *)cs_node, offs,
841 UBIFS_CS_NODE_SZ, 0);
842 if (err && err != -EBADMSG)
844 ret = ubifs_scan_a_node(c, cs_node, UBIFS_CS_NODE_SZ, lnum, offs, 0);
845 if (ret != SCANNED_A_NODE) {
846 ubifs_err("Not a valid node");
849 if (cs_node->ch.node_type != UBIFS_CS_NODE) {
850 ubifs_err("Node a CS node, type is %d", cs_node->ch.node_type);
853 if (le64_to_cpu(cs_node->cmt_no) != c->cmt_no) {
854 ubifs_err("CS node cmt_no %llu != current cmt_no %llu",
855 (unsigned long long)le64_to_cpu(cs_node->cmt_no),
859 *cs_sqnum = le64_to_cpu(cs_node->ch.sqnum);
860 dbg_rcvry("commit start sqnum %llu", *cs_sqnum);
867 ubifs_err("failed to get CS sqnum");
873 * ubifs_recover_log_leb - scan and recover a log LEB.
874 * @c: UBIFS file-system description object
877 * @sbuf: LEB-sized buffer to use
879 * This function does a scan of a LEB, but caters for errors that might have
880 * been caused by unclean reboots from which we are attempting to recover
881 * (assume that only the last log LEB can be corrupted by an unclean reboot).
883 * This function returns %0 on success and a negative error code on failure.
885 struct ubifs_scan_leb *ubifs_recover_log_leb(struct ubifs_info *c, int lnum,
886 int offs, void *sbuf)
888 struct ubifs_scan_leb *sleb;
891 dbg_rcvry("LEB %d", lnum);
892 next_lnum = lnum + 1;
893 if (next_lnum >= UBIFS_LOG_LNUM + c->log_lebs)
894 next_lnum = UBIFS_LOG_LNUM;
895 if (next_lnum != c->ltail_lnum) {
897 * We can only recover at the end of the log, so check that the
898 * next log LEB is empty or out of date.
900 sleb = ubifs_scan(c, next_lnum, 0, sbuf, 0);
903 if (sleb->nodes_cnt) {
904 struct ubifs_scan_node *snod;
905 unsigned long long cs_sqnum = c->cs_sqnum;
907 snod = list_entry(sleb->nodes.next,
908 struct ubifs_scan_node, list);
912 err = get_cs_sqnum(c, lnum, offs, &cs_sqnum);
914 ubifs_scan_destroy(sleb);
918 if (snod->sqnum > cs_sqnum) {
919 ubifs_err("unrecoverable log corruption in LEB %d",
921 ubifs_scan_destroy(sleb);
922 return ERR_PTR(-EUCLEAN);
925 ubifs_scan_destroy(sleb);
927 return ubifs_recover_leb(c, lnum, offs, sbuf, -1);
931 * recover_head - recover a head.
932 * @c: UBIFS file-system description object
933 * @lnum: LEB number of head to recover
934 * @offs: offset of head to recover
935 * @sbuf: LEB-sized buffer to use
937 * This function ensures that there is no data on the flash at a head location.
939 * This function returns %0 on success and a negative error code on failure.
941 static int recover_head(struct ubifs_info *c, int lnum, int offs, void *sbuf)
943 int len = c->max_write_size, err;
945 if (offs + len > c->leb_size)
946 len = c->leb_size - offs;
951 /* Read at the head location and check it is empty flash */
952 err = ubifs_leb_read(c, lnum, sbuf, offs, len, 1);
953 if (err || !is_empty(sbuf, len)) {
954 dbg_rcvry("cleaning head at %d:%d", lnum, offs);
956 return ubifs_leb_unmap(c, lnum);
957 err = ubifs_leb_read(c, lnum, sbuf, 0, offs, 1);
960 return ubifs_leb_change(c, lnum, sbuf, offs);
967 * ubifs_recover_inl_heads - recover index and LPT heads.
968 * @c: UBIFS file-system description object
969 * @sbuf: LEB-sized buffer to use
971 * This function ensures that there is no data on the flash at the index and
972 * LPT head locations.
974 * This deals with the recovery of a half-completed journal commit. UBIFS is
975 * careful never to overwrite the last version of the index or the LPT. Because
976 * the index and LPT are wandering trees, data from a half-completed commit will
977 * not be referenced anywhere in UBIFS. The data will be either in LEBs that are
978 * assumed to be empty and will be unmapped anyway before use, or in the index
981 * This function returns %0 on success and a negative error code on failure.
983 int ubifs_recover_inl_heads(struct ubifs_info *c, void *sbuf)
987 ubifs_assert(!c->ro_mount || c->remounting_rw);
989 dbg_rcvry("checking index head at %d:%d", c->ihead_lnum, c->ihead_offs);
990 err = recover_head(c, c->ihead_lnum, c->ihead_offs, sbuf);
994 dbg_rcvry("checking LPT head at %d:%d", c->nhead_lnum, c->nhead_offs);
995 err = recover_head(c, c->nhead_lnum, c->nhead_offs, sbuf);
1003 * clean_an_unclean_leb - read and write a LEB to remove corruption.
1004 * @c: UBIFS file-system description object
1005 * @ucleb: unclean LEB information
1006 * @sbuf: LEB-sized buffer to use
1008 * This function reads a LEB up to a point pre-determined by the mount recovery,
1009 * checks the nodes, and writes the result back to the flash, thereby cleaning
1010 * off any following corruption, or non-fatal ECC errors.
1012 * This function returns %0 on success and a negative error code on failure.
1014 static int clean_an_unclean_leb(struct ubifs_info *c,
1015 struct ubifs_unclean_leb *ucleb, void *sbuf)
1017 int err, lnum = ucleb->lnum, offs = 0, len = ucleb->endpt, quiet = 1;
1020 dbg_rcvry("LEB %d len %d", lnum, len);
1023 /* Nothing to read, just unmap it */
1024 err = ubifs_leb_unmap(c, lnum);
1030 err = ubifs_leb_read(c, lnum, buf, offs, len, 0);
1031 if (err && err != -EBADMSG)
1039 /* Scan quietly until there is an error */
1040 ret = ubifs_scan_a_node(c, buf, len, lnum, offs, quiet);
1042 if (ret == SCANNED_A_NODE) {
1043 /* A valid node, and not a padding node */
1044 struct ubifs_ch *ch = buf;
1047 node_len = ALIGN(le32_to_cpu(ch->len), 8);
1055 /* Padding bytes or a valid padding node */
1062 if (ret == SCANNED_EMPTY_SPACE) {
1063 ubifs_err("unexpected empty space at %d:%d",
1069 /* Redo the last scan but noisily */
1074 ubifs_scanned_corruption(c, lnum, offs, buf);
1078 /* Pad to min_io_size */
1079 len = ALIGN(ucleb->endpt, c->min_io_size);
1080 if (len > ucleb->endpt) {
1081 int pad_len = len - ALIGN(ucleb->endpt, 8);
1084 buf = c->sbuf + len - pad_len;
1085 ubifs_pad(c, buf, pad_len);
1089 /* Write back the LEB atomically */
1090 err = ubifs_leb_change(c, lnum, sbuf, len);
1094 dbg_rcvry("cleaned LEB %d", lnum);
1100 * ubifs_clean_lebs - clean LEBs recovered during read-only mount.
1101 * @c: UBIFS file-system description object
1102 * @sbuf: LEB-sized buffer to use
1104 * This function cleans a LEB identified during recovery that needs to be
1105 * written but was not because UBIFS was mounted read-only. This happens when
1106 * remounting to read-write mode.
1108 * This function returns %0 on success and a negative error code on failure.
1110 int ubifs_clean_lebs(struct ubifs_info *c, void *sbuf)
1112 dbg_rcvry("recovery");
1113 while (!list_empty(&c->unclean_leb_list)) {
1114 struct ubifs_unclean_leb *ucleb;
1117 ucleb = list_entry(c->unclean_leb_list.next,
1118 struct ubifs_unclean_leb, list);
1119 err = clean_an_unclean_leb(c, ucleb, sbuf);
1122 list_del(&ucleb->list);
1129 * grab_empty_leb - grab an empty LEB to use as GC LEB and run commit.
1130 * @c: UBIFS file-system description object
1132 * This is a helper function for 'ubifs_rcvry_gc_commit()' which grabs an empty
1133 * LEB to be used as GC LEB (@c->gc_lnum), and then runs the commit. Returns
1134 * zero in case of success and a negative error code in case of failure.
1136 static int grab_empty_leb(struct ubifs_info *c)
1141 * Note, it is very important to first search for an empty LEB and then
1142 * run the commit, not vice-versa. The reason is that there might be
1143 * only one empty LEB at the moment, the one which has been the
1144 * @c->gc_lnum just before the power cut happened. During the regular
1145 * UBIFS operation (not now) @c->gc_lnum is marked as "taken", so no
1146 * one but GC can grab it. But at this moment this single empty LEB is
1147 * not marked as taken, so if we run commit - what happens? Right, the
1148 * commit will grab it and write the index there. Remember that the
1149 * index always expands as long as there is free space, and it only
1150 * starts consolidating when we run out of space.
1152 * IOW, if we run commit now, we might not be able to find a free LEB
1155 lnum = ubifs_find_free_leb_for_idx(c);
1157 ubifs_err("could not find an empty LEB");
1158 ubifs_dump_lprops(c);
1159 ubifs_dump_budg(c, &c->bi);
1163 /* Reset the index flag */
1164 err = ubifs_change_one_lp(c, lnum, LPROPS_NC, LPROPS_NC, 0,
1170 dbg_rcvry("found empty LEB %d, run commit", lnum);
1172 return ubifs_run_commit(c);
1176 * ubifs_rcvry_gc_commit - recover the GC LEB number and run the commit.
1177 * @c: UBIFS file-system description object
1179 * Out-of-place garbage collection requires always one empty LEB with which to
1180 * start garbage collection. The LEB number is recorded in c->gc_lnum and is
1181 * written to the master node on unmounting. In the case of an unclean unmount
1182 * the value of gc_lnum recorded in the master node is out of date and cannot
1183 * be used. Instead, recovery must allocate an empty LEB for this purpose.
1184 * However, there may not be enough empty space, in which case it must be
1185 * possible to GC the dirtiest LEB into the GC head LEB.
1187 * This function also runs the commit which causes the TNC updates from
1188 * size-recovery and orphans to be written to the flash. That is important to
1189 * ensure correct replay order for subsequent mounts.
1191 * This function returns %0 on success and a negative error code on failure.
1193 int ubifs_rcvry_gc_commit(struct ubifs_info *c)
1195 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
1196 struct ubifs_lprops lp;
1199 dbg_rcvry("GC head LEB %d, offs %d", wbuf->lnum, wbuf->offs);
1202 if (wbuf->lnum == -1 || wbuf->offs == c->leb_size)
1203 return grab_empty_leb(c);
1205 err = ubifs_find_dirty_leb(c, &lp, wbuf->offs, 2);
1210 dbg_rcvry("could not find a dirty LEB");
1211 return grab_empty_leb(c);
1214 ubifs_assert(!(lp.flags & LPROPS_INDEX));
1215 ubifs_assert(lp.free + lp.dirty >= wbuf->offs);
1218 * We run the commit before garbage collection otherwise subsequent
1219 * mounts will see the GC and orphan deletion in a different order.
1221 dbg_rcvry("committing");
1222 err = ubifs_run_commit(c);
1226 dbg_rcvry("GC'ing LEB %d", lp.lnum);
1227 mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead);
1228 err = ubifs_garbage_collect_leb(c, &lp);
1230 int err2 = ubifs_wbuf_sync_nolock(wbuf);
1235 mutex_unlock(&wbuf->io_mutex);
1237 ubifs_err("GC failed, error %d", err);
1243 ubifs_assert(err == LEB_RETAINED);
1244 if (err != LEB_RETAINED)
1247 err = ubifs_leb_unmap(c, c->gc_lnum);
1251 dbg_rcvry("allocated LEB %d for GC", lp.lnum);
1256 * struct size_entry - inode size information for recovery.
1257 * @rb: link in the RB-tree of sizes
1258 * @inum: inode number
1259 * @i_size: size on inode
1260 * @d_size: maximum size based on data nodes
1261 * @exists: indicates whether the inode exists
1262 * @inode: inode if pinned in memory awaiting rw mode to fix it
1270 struct inode *inode;
1274 * add_ino - add an entry to the size tree.
1275 * @c: UBIFS file-system description object
1276 * @inum: inode number
1277 * @i_size: size on inode
1278 * @d_size: maximum size based on data nodes
1279 * @exists: indicates whether the inode exists
1281 static int add_ino(struct ubifs_info *c, ino_t inum, loff_t i_size,
1282 loff_t d_size, int exists)
1284 struct rb_node **p = &c->size_tree.rb_node, *parent = NULL;
1285 struct size_entry *e;
1289 e = rb_entry(parent, struct size_entry, rb);
1293 p = &(*p)->rb_right;
1296 e = kzalloc(sizeof(struct size_entry), GFP_KERNEL);
1305 rb_link_node(&e->rb, parent, p);
1306 rb_insert_color(&e->rb, &c->size_tree);
1312 * find_ino - find an entry on the size tree.
1313 * @c: UBIFS file-system description object
1314 * @inum: inode number
1316 static struct size_entry *find_ino(struct ubifs_info *c, ino_t inum)
1318 struct rb_node *p = c->size_tree.rb_node;
1319 struct size_entry *e;
1322 e = rb_entry(p, struct size_entry, rb);
1325 else if (inum > e->inum)
1334 * remove_ino - remove an entry from the size tree.
1335 * @c: UBIFS file-system description object
1336 * @inum: inode number
1338 static void remove_ino(struct ubifs_info *c, ino_t inum)
1340 struct size_entry *e = find_ino(c, inum);
1344 rb_erase(&e->rb, &c->size_tree);
1349 * ubifs_destroy_size_tree - free resources related to the size tree.
1350 * @c: UBIFS file-system description object
1352 void ubifs_destroy_size_tree(struct ubifs_info *c)
1354 struct rb_node *this = c->size_tree.rb_node;
1355 struct size_entry *e;
1358 if (this->rb_left) {
1359 this = this->rb_left;
1361 } else if (this->rb_right) {
1362 this = this->rb_right;
1365 e = rb_entry(this, struct size_entry, rb);
1368 this = rb_parent(this);
1370 if (this->rb_left == &e->rb)
1371 this->rb_left = NULL;
1373 this->rb_right = NULL;
1377 c->size_tree = RB_ROOT;
1381 * ubifs_recover_size_accum - accumulate inode sizes for recovery.
1382 * @c: UBIFS file-system description object
1384 * @deletion: node is for a deletion
1385 * @new_size: inode size
1387 * This function has two purposes:
1388 * 1) to ensure there are no data nodes that fall outside the inode size
1389 * 2) to ensure there are no data nodes for inodes that do not exist
1390 * To accomplish those purposes, a rb-tree is constructed containing an entry
1391 * for each inode number in the journal that has not been deleted, and recording
1392 * the size from the inode node, the maximum size of any data node (also altered
1393 * by truncations) and a flag indicating a inode number for which no inode node
1394 * was present in the journal.
1396 * Note that there is still the possibility that there are data nodes that have
1397 * been committed that are beyond the inode size, however the only way to find
1398 * them would be to scan the entire index. Alternatively, some provision could
1399 * be made to record the size of inodes at the start of commit, which would seem
1400 * very cumbersome for a scenario that is quite unlikely and the only negative
1401 * consequence of which is wasted space.
1403 * This functions returns %0 on success and a negative error code on failure.
1405 int ubifs_recover_size_accum(struct ubifs_info *c, union ubifs_key *key,
1406 int deletion, loff_t new_size)
1408 ino_t inum = key_inum(c, key);
1409 struct size_entry *e;
1412 switch (key_type(c, key)) {
1415 remove_ino(c, inum);
1417 e = find_ino(c, inum);
1419 e->i_size = new_size;
1422 err = add_ino(c, inum, new_size, 0, 1);
1428 case UBIFS_DATA_KEY:
1429 e = find_ino(c, inum);
1431 if (new_size > e->d_size)
1432 e->d_size = new_size;
1434 err = add_ino(c, inum, 0, new_size, 0);
1439 case UBIFS_TRUN_KEY:
1440 e = find_ino(c, inum);
1442 e->d_size = new_size;
1449 * fix_size_in_place - fix inode size in place on flash.
1450 * @c: UBIFS file-system description object
1451 * @e: inode size information for recovery
1453 static int fix_size_in_place(struct ubifs_info *c, struct size_entry *e)
1455 struct ubifs_ino_node *ino = c->sbuf;
1457 union ubifs_key key;
1458 int err, lnum, offs, len;
1462 /* Locate the inode node LEB number and offset */
1463 ino_key_init(c, &key, e->inum);
1464 err = ubifs_tnc_locate(c, &key, ino, &lnum, &offs);
1468 * If the size recorded on the inode node is greater than the size that
1469 * was calculated from nodes in the journal then don't change the inode.
1471 i_size = le64_to_cpu(ino->size);
1472 if (i_size >= e->d_size)
1475 err = ubifs_leb_read(c, lnum, c->sbuf, 0, c->leb_size, 1);
1478 /* Change the size field and recalculate the CRC */
1479 ino = c->sbuf + offs;
1480 ino->size = cpu_to_le64(e->d_size);
1481 len = le32_to_cpu(ino->ch.len);
1482 crc = crc32(UBIFS_CRC32_INIT, (void *)ino + 8, len - 8);
1483 ino->ch.crc = cpu_to_le32(crc);
1484 /* Work out where data in the LEB ends and free space begins */
1486 len = c->leb_size - 1;
1487 while (p[len] == 0xff)
1489 len = ALIGN(len + 1, c->min_io_size);
1490 /* Atomically write the fixed LEB back again */
1491 err = ubifs_leb_change(c, lnum, c->sbuf, len);
1494 dbg_rcvry("inode %lu at %d:%d size %lld -> %lld",
1495 (unsigned long)e->inum, lnum, offs, i_size, e->d_size);
1499 ubifs_warn("inode %lu failed to fix size %lld -> %lld error %d",
1500 (unsigned long)e->inum, e->i_size, e->d_size, err);
1505 * ubifs_recover_size - recover inode size.
1506 * @c: UBIFS file-system description object
1508 * This function attempts to fix inode size discrepancies identified by the
1509 * 'ubifs_recover_size_accum()' function.
1511 * This functions returns %0 on success and a negative error code on failure.
1513 int ubifs_recover_size(struct ubifs_info *c)
1515 struct rb_node *this = rb_first(&c->size_tree);
1518 struct size_entry *e;
1521 e = rb_entry(this, struct size_entry, rb);
1523 union ubifs_key key;
1525 ino_key_init(c, &key, e->inum);
1526 err = ubifs_tnc_lookup(c, &key, c->sbuf);
1527 if (err && err != -ENOENT)
1529 if (err == -ENOENT) {
1530 /* Remove data nodes that have no inode */
1531 dbg_rcvry("removing ino %lu",
1532 (unsigned long)e->inum);
1533 err = ubifs_tnc_remove_ino(c, e->inum);
1537 struct ubifs_ino_node *ino = c->sbuf;
1540 e->i_size = le64_to_cpu(ino->size);
1544 if (e->exists && e->i_size < e->d_size) {
1546 /* Fix the inode size and pin it in memory */
1547 struct inode *inode;
1548 struct ubifs_inode *ui;
1550 ubifs_assert(!e->inode);
1552 inode = ubifs_iget(c->vfs_sb, e->inum);
1554 return PTR_ERR(inode);
1556 ui = ubifs_inode(inode);
1557 if (inode->i_size < e->d_size) {
1558 dbg_rcvry("ino %lu size %lld -> %lld",
1559 (unsigned long)e->inum,
1560 inode->i_size, e->d_size);
1561 inode->i_size = e->d_size;
1562 ui->ui_size = e->d_size;
1563 ui->synced_i_size = e->d_size;
1565 this = rb_next(this);
1570 /* Fix the size in place */
1571 err = fix_size_in_place(c, e);
1579 this = rb_next(this);
1580 rb_erase(&e->rb, &c->size_tree);