~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/ubifs/recovery.c

Version: ~ [ linux-5.12-rc7 ] ~ [ linux-5.11.13 ] ~ [ linux-5.10.29 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.111 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.186 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.230 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.266 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.266 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.18.140 ] ~ [ linux-3.16.85 ] ~ [ linux-3.14.79 ] ~ [ linux-3.12.74 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 // SPDX-License-Identifier: GPL-2.0-only
  2 /*
  3  * This file is part of UBIFS.
  4  *
  5  * Copyright (C) 2006-2008 Nokia Corporation
  6  *
  7  * Authors: Adrian Hunter
  8  *          Artem Bityutskiy (Битюцкий Артём)
  9  */
 10 
 11 /*
 12  * This file implements functions needed to recover from unclean un-mounts.
 13  * When UBIFS is mounted, it checks a flag on the master node to determine if
 14  * an un-mount was completed successfully. If not, the process of mounting
 15  * incorporates additional checking and fixing of on-flash data structures.
 16  * UBIFS always cleans away all remnants of an unclean un-mount, so that
 17  * errors do not accumulate. However UBIFS defers recovery if it is mounted
 18  * read-only, and the flash is not modified in that case.
 19  *
 20  * The general UBIFS approach to the recovery is that it recovers from
 21  * corruptions which could be caused by power cuts, but it refuses to recover
 22  * from corruption caused by other reasons. And UBIFS tries to distinguish
 23  * between these 2 reasons of corruptions and silently recover in the former
 24  * case and loudly complain in the latter case.
 25  *
 26  * UBIFS writes only to erased LEBs, so it writes only to the flash space
 27  * containing only 0xFFs. UBIFS also always writes strictly from the beginning
 28  * of the LEB to the end. And UBIFS assumes that the underlying flash media
 29  * writes in @c->max_write_size bytes at a time.
 30  *
 31  * Hence, if UBIFS finds a corrupted node at offset X, it expects only the min.
 32  * I/O unit corresponding to offset X to contain corrupted data, all the
 33  * following min. I/O units have to contain empty space (all 0xFFs). If this is
 34  * not true, the corruption cannot be the result of a power cut, and UBIFS
 35  * refuses to mount.
 36  */
 37 
 38 #include <linux/crc32.h>
 39 #include <linux/slab.h>
 40 #include "ubifs.h"
 41 
 42 /**
 43  * is_empty - determine whether a buffer is empty (contains all 0xff).
 44  * @buf: buffer to clean
 45  * @len: length of buffer
 46  *
 47  * This function returns %1 if the buffer is empty (contains all 0xff) otherwise
 48  * %0 is returned.
 49  */
 50 static int is_empty(void *buf, int len)
 51 {
 52         uint8_t *p = buf;
 53         int i;
 54 
 55         for (i = 0; i < len; i++)
 56                 if (*p++ != 0xff)
 57                         return 0;
 58         return 1;
 59 }
 60 
 61 /**
 62  * first_non_ff - find offset of the first non-0xff byte.
 63  * @buf: buffer to search in
 64  * @len: length of buffer
 65  *
 66  * This function returns offset of the first non-0xff byte in @buf or %-1 if
 67  * the buffer contains only 0xff bytes.
 68  */
 69 static int first_non_ff(void *buf, int len)
 70 {
 71         uint8_t *p = buf;
 72         int i;
 73 
 74         for (i = 0; i < len; i++)
 75                 if (*p++ != 0xff)
 76                         return i;
 77         return -1;
 78 }
 79 
 80 /**
 81  * get_master_node - get the last valid master node allowing for corruption.
 82  * @c: UBIFS file-system description object
 83  * @lnum: LEB number
 84  * @pbuf: buffer containing the LEB read, is returned here
 85  * @mst: master node, if found, is returned here
 86  * @cor: corruption, if found, is returned here
 87  *
 88  * This function allocates a buffer, reads the LEB into it, and finds and
 89  * returns the last valid master node allowing for one area of corruption.
 90  * The corrupt area, if there is one, must be consistent with the assumption
 91  * that it is the result of an unclean unmount while the master node was being
 92  * written. Under those circumstances, it is valid to use the previously written
 93  * master node.
 94  *
 95  * This function returns %0 on success and a negative error code on failure.
 96  */
 97 static int get_master_node(const struct ubifs_info *c, int lnum, void **pbuf,
 98                            struct ubifs_mst_node **mst, void **cor)
 99 {
100         const int sz = c->mst_node_alsz;
101         int err, offs, len;
102         void *sbuf, *buf;
103 
104         sbuf = vmalloc(c->leb_size);
105         if (!sbuf)
106                 return -ENOMEM;
107 
108         err = ubifs_leb_read(c, lnum, sbuf, 0, c->leb_size, 0);
109         if (err && err != -EBADMSG)
110                 goto out_free;
111 
112         /* Find the first position that is definitely not a node */
113         offs = 0;
114         buf = sbuf;
115         len = c->leb_size;
116         while (offs + UBIFS_MST_NODE_SZ <= c->leb_size) {
117                 struct ubifs_ch *ch = buf;
118 
119                 if (le32_to_cpu(ch->magic) != UBIFS_NODE_MAGIC)
120                         break;
121                 offs += sz;
122                 buf  += sz;
123                 len  -= sz;
124         }
125         /* See if there was a valid master node before that */
126         if (offs) {
127                 int ret;
128 
129                 offs -= sz;
130                 buf  -= sz;
131                 len  += sz;
132                 ret = ubifs_scan_a_node(c, buf, len, lnum, offs, 1);
133                 if (ret != SCANNED_A_NODE && offs) {
134                         /* Could have been corruption so check one place back */
135                         offs -= sz;
136                         buf  -= sz;
137                         len  += sz;
138                         ret = ubifs_scan_a_node(c, buf, len, lnum, offs, 1);
139                         if (ret != SCANNED_A_NODE)
140                                 /*
141                                  * We accept only one area of corruption because
142                                  * we are assuming that it was caused while
143                                  * trying to write a master node.
144                                  */
145                                 goto out_err;
146                 }
147                 if (ret == SCANNED_A_NODE) {
148                         struct ubifs_ch *ch = buf;
149 
150                         if (ch->node_type != UBIFS_MST_NODE)
151                                 goto out_err;
152                         dbg_rcvry("found a master node at %d:%d", lnum, offs);
153                         *mst = buf;
154                         offs += sz;
155                         buf  += sz;
156                         len  -= sz;
157                 }
158         }
159         /* Check for corruption */
160         if (offs < c->leb_size) {
161                 if (!is_empty(buf, min_t(int, len, sz))) {
162                         *cor = buf;
163                         dbg_rcvry("found corruption at %d:%d", lnum, offs);
164                 }
165                 offs += sz;
166                 buf  += sz;
167                 len  -= sz;
168         }
169         /* Check remaining empty space */
170         if (offs < c->leb_size)
171                 if (!is_empty(buf, len))
172                         goto out_err;
173         *pbuf = sbuf;
174         return 0;
175 
176 out_err:
177         err = -EINVAL;
178 out_free:
179         vfree(sbuf);
180         *mst = NULL;
181         *cor = NULL;
182         return err;
183 }
184 
185 /**
186  * write_rcvrd_mst_node - write recovered master node.
187  * @c: UBIFS file-system description object
188  * @mst: master node
189  *
190  * This function returns %0 on success and a negative error code on failure.
191  */
192 static int write_rcvrd_mst_node(struct ubifs_info *c,
193                                 struct ubifs_mst_node *mst)
194 {
195         int err = 0, lnum = UBIFS_MST_LNUM, sz = c->mst_node_alsz;
196         __le32 save_flags;
197 
198         dbg_rcvry("recovery");
199 
200         save_flags = mst->flags;
201         mst->flags |= cpu_to_le32(UBIFS_MST_RCVRY);
202 
203         err = ubifs_prepare_node_hmac(c, mst, UBIFS_MST_NODE_SZ,
204                                       offsetof(struct ubifs_mst_node, hmac), 1);
205         if (err)
206                 goto out;
207         err = ubifs_leb_change(c, lnum, mst, sz);
208         if (err)
209                 goto out;
210         err = ubifs_leb_change(c, lnum + 1, mst, sz);
211         if (err)
212                 goto out;
213 out:
214         mst->flags = save_flags;
215         return err;
216 }
217 
218 /**
219  * ubifs_recover_master_node - recover the master node.
220  * @c: UBIFS file-system description object
221  *
222  * This function recovers the master node from corruption that may occur due to
223  * an unclean unmount.
224  *
225  * This function returns %0 on success and a negative error code on failure.
226  */
227 int ubifs_recover_master_node(struct ubifs_info *c)
228 {
229         void *buf1 = NULL, *buf2 = NULL, *cor1 = NULL, *cor2 = NULL;
230         struct ubifs_mst_node *mst1 = NULL, *mst2 = NULL, *mst;
231         const int sz = c->mst_node_alsz;
232         int err, offs1, offs2;
233 
234         dbg_rcvry("recovery");
235 
236         err = get_master_node(c, UBIFS_MST_LNUM, &buf1, &mst1, &cor1);
237         if (err)
238                 goto out_free;
239 
240         err = get_master_node(c, UBIFS_MST_LNUM + 1, &buf2, &mst2, &cor2);
241         if (err)
242                 goto out_free;
243 
244         if (mst1) {
245                 offs1 = (void *)mst1 - buf1;
246                 if ((le32_to_cpu(mst1->flags) & UBIFS_MST_RCVRY) &&
247                     (offs1 == 0 && !cor1)) {
248                         /*
249                          * mst1 was written by recovery at offset 0 with no
250                          * corruption.
251                          */
252                         dbg_rcvry("recovery recovery");
253                         mst = mst1;
254                 } else if (mst2) {
255                         offs2 = (void *)mst2 - buf2;
256                         if (offs1 == offs2) {
257                                 /* Same offset, so must be the same */
258                                 if (ubifs_compare_master_node(c, mst1, mst2))
259                                         goto out_err;
260                                 mst = mst1;
261                         } else if (offs2 + sz == offs1) {
262                                 /* 1st LEB was written, 2nd was not */
263                                 if (cor1)
264                                         goto out_err;
265                                 mst = mst1;
266                         } else if (offs1 == 0 &&
267                                    c->leb_size - offs2 - sz < sz) {
268                                 /* 1st LEB was unmapped and written, 2nd not */
269                                 if (cor1)
270                                         goto out_err;
271                                 mst = mst1;
272                         } else
273                                 goto out_err;
274                 } else {
275                         /*
276                          * 2nd LEB was unmapped and about to be written, so
277                          * there must be only one master node in the first LEB
278                          * and no corruption.
279                          */
280                         if (offs1 != 0 || cor1)
281                                 goto out_err;
282                         mst = mst1;
283                 }
284         } else {
285                 if (!mst2)
286                         goto out_err;
287                 /*
288                  * 1st LEB was unmapped and about to be written, so there must
289                  * be no room left in 2nd LEB.
290                  */
291                 offs2 = (void *)mst2 - buf2;
292                 if (offs2 + sz + sz <= c->leb_size)
293                         goto out_err;
294                 mst = mst2;
295         }
296 
297         ubifs_msg(c, "recovered master node from LEB %d",
298                   (mst == mst1 ? UBIFS_MST_LNUM : UBIFS_MST_LNUM + 1));
299 
300         memcpy(c->mst_node, mst, UBIFS_MST_NODE_SZ);
301 
302         if (c->ro_mount) {
303                 /* Read-only mode. Keep a copy for switching to rw mode */
304                 c->rcvrd_mst_node = kmalloc(sz, GFP_KERNEL);
305                 if (!c->rcvrd_mst_node) {
306                         err = -ENOMEM;
307                         goto out_free;
308                 }
309                 memcpy(c->rcvrd_mst_node, c->mst_node, UBIFS_MST_NODE_SZ);
310 
311                 /*
312                  * We had to recover the master node, which means there was an
313                  * unclean reboot. However, it is possible that the master node
314                  * is clean at this point, i.e., %UBIFS_MST_DIRTY is not set.
315                  * E.g., consider the following chain of events:
316                  *
317                  * 1. UBIFS was cleanly unmounted, so the master node is clean
318                  * 2. UBIFS is being mounted R/W and starts changing the master
319                  *    node in the first (%UBIFS_MST_LNUM). A power cut happens,
320                  *    so this LEB ends up with some amount of garbage at the
321                  *    end.
322                  * 3. UBIFS is being mounted R/O. We reach this place and
323                  *    recover the master node from the second LEB
324                  *    (%UBIFS_MST_LNUM + 1). But we cannot update the media
325                  *    because we are being mounted R/O. We have to defer the
326                  *    operation.
327                  * 4. However, this master node (@c->mst_node) is marked as
328                  *    clean (since the step 1). And if we just return, the
329                  *    mount code will be confused and won't recover the master
330                  *    node when it is re-mounter R/W later.
331                  *
332                  *    Thus, to force the recovery by marking the master node as
333                  *    dirty.
334                  */
335                 c->mst_node->flags |= cpu_to_le32(UBIFS_MST_DIRTY);
336         } else {
337                 /* Write the recovered master node */
338                 c->max_sqnum = le64_to_cpu(mst->ch.sqnum) - 1;
339                 err = write_rcvrd_mst_node(c, c->mst_node);
340                 if (err)
341                         goto out_free;
342         }
343 
344         vfree(buf2);
345         vfree(buf1);
346 
347         return 0;
348 
349 out_err:
350         err = -EINVAL;
351 out_free:
352         ubifs_err(c, "failed to recover master node");
353         if (mst1) {
354                 ubifs_err(c, "dumping first master node");
355                 ubifs_dump_node(c, mst1);
356         }
357         if (mst2) {
358                 ubifs_err(c, "dumping second master node");
359                 ubifs_dump_node(c, mst2);
360         }
361         vfree(buf2);
362         vfree(buf1);
363         return err;
364 }
365 
366 /**
367  * ubifs_write_rcvrd_mst_node - write the recovered master node.
368  * @c: UBIFS file-system description object
369  *
370  * This function writes the master node that was recovered during mounting in
371  * read-only mode and must now be written because we are remounting rw.
372  *
373  * This function returns %0 on success and a negative error code on failure.
374  */
375 int ubifs_write_rcvrd_mst_node(struct ubifs_info *c)
376 {
377         int err;
378 
379         if (!c->rcvrd_mst_node)
380                 return 0;
381         c->rcvrd_mst_node->flags |= cpu_to_le32(UBIFS_MST_DIRTY);
382         c->mst_node->flags |= cpu_to_le32(UBIFS_MST_DIRTY);
383         err = write_rcvrd_mst_node(c, c->rcvrd_mst_node);
384         if (err)
385                 return err;
386         kfree(c->rcvrd_mst_node);
387         c->rcvrd_mst_node = NULL;
388         return 0;
389 }
390 
391 /**
392  * is_last_write - determine if an offset was in the last write to a LEB.
393  * @c: UBIFS file-system description object
394  * @buf: buffer to check
395  * @offs: offset to check
396  *
397  * This function returns %1 if @offs was in the last write to the LEB whose data
398  * is in @buf, otherwise %0 is returned. The determination is made by checking
399  * for subsequent empty space starting from the next @c->max_write_size
400  * boundary.
401  */
402 static int is_last_write(const struct ubifs_info *c, void *buf, int offs)
403 {
404         int empty_offs, check_len;
405         uint8_t *p;
406 
407         /*
408          * Round up to the next @c->max_write_size boundary i.e. @offs is in
409          * the last wbuf written. After that should be empty space.
410          */
411         empty_offs = ALIGN(offs + 1, c->max_write_size);
412         check_len = c->leb_size - empty_offs;
413         p = buf + empty_offs - offs;
414         return is_empty(p, check_len);
415 }
416 
417 /**
418  * clean_buf - clean the data from an LEB sitting in a buffer.
419  * @c: UBIFS file-system description object
420  * @buf: buffer to clean
421  * @lnum: LEB number to clean
422  * @offs: offset from which to clean
423  * @len: length of buffer
424  *
425  * This function pads up to the next min_io_size boundary (if there is one) and
426  * sets empty space to all 0xff. @buf, @offs and @len are updated to the next
427  * @c->min_io_size boundary.
428  */
429 static void clean_buf(const struct ubifs_info *c, void **buf, int lnum,
430                       int *offs, int *len)
431 {
432         int empty_offs, pad_len;
433 
434         dbg_rcvry("cleaning corruption at %d:%d", lnum, *offs);
435 
436         ubifs_assert(c, !(*offs & 7));
437         empty_offs = ALIGN(*offs, c->min_io_size);
438         pad_len = empty_offs - *offs;
439         ubifs_pad(c, *buf, pad_len);
440         *offs += pad_len;
441         *buf += pad_len;
442         *len -= pad_len;
443         memset(*buf, 0xff, c->leb_size - empty_offs);
444 }
445 
446 /**
447  * no_more_nodes - determine if there are no more nodes in a buffer.
448  * @c: UBIFS file-system description object
449  * @buf: buffer to check
450  * @len: length of buffer
451  * @lnum: LEB number of the LEB from which @buf was read
452  * @offs: offset from which @buf was read
453  *
454  * This function ensures that the corrupted node at @offs is the last thing
455  * written to a LEB. This function returns %1 if more data is not found and
456  * %0 if more data is found.
457  */
458 static int no_more_nodes(const struct ubifs_info *c, void *buf, int len,
459                         int lnum, int offs)
460 {
461         struct ubifs_ch *ch = buf;
462         int skip, dlen = le32_to_cpu(ch->len);
463 
464         /* Check for empty space after the corrupt node's common header */
465         skip = ALIGN(offs + UBIFS_CH_SZ, c->max_write_size) - offs;
466         if (is_empty(buf + skip, len - skip))
467                 return 1;
468         /*
469          * The area after the common header size is not empty, so the common
470          * header must be intact. Check it.
471          */
472         if (ubifs_check_node(c, buf, lnum, offs, 1, 0) != -EUCLEAN) {
473                 dbg_rcvry("unexpected bad common header at %d:%d", lnum, offs);
474                 return 0;
475         }
476         /* Now we know the corrupt node's length we can skip over it */
477         skip = ALIGN(offs + dlen, c->max_write_size) - offs;
478         /* After which there should be empty space */
479         if (is_empty(buf + skip, len - skip))
480                 return 1;
481         dbg_rcvry("unexpected data at %d:%d", lnum, offs + skip);
482         return 0;
483 }
484 
485 /**
486  * fix_unclean_leb - fix an unclean LEB.
487  * @c: UBIFS file-system description object
488  * @sleb: scanned LEB information
489  * @start: offset where scan started
490  */
491 static int fix_unclean_leb(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
492                            int start)
493 {
494         int lnum = sleb->lnum, endpt = start;
495 
496         /* Get the end offset of the last node we are keeping */
497         if (!list_empty(&sleb->nodes)) {
498                 struct ubifs_scan_node *snod;
499 
500                 snod = list_entry(sleb->nodes.prev,
501                                   struct ubifs_scan_node, list);
502                 endpt = snod->offs + snod->len;
503         }
504 
505         if (c->ro_mount && !c->remounting_rw) {
506                 /* Add to recovery list */
507                 struct ubifs_unclean_leb *ucleb;
508 
509                 dbg_rcvry("need to fix LEB %d start %d endpt %d",
510                           lnum, start, sleb->endpt);
511                 ucleb = kzalloc(sizeof(struct ubifs_unclean_leb), GFP_NOFS);
512                 if (!ucleb)
513                         return -ENOMEM;
514                 ucleb->lnum = lnum;
515                 ucleb->endpt = endpt;
516                 list_add_tail(&ucleb->list, &c->unclean_leb_list);
517         } else {
518                 /* Write the fixed LEB back to flash */
519                 int err;
520 
521                 dbg_rcvry("fixing LEB %d start %d endpt %d",
522                           lnum, start, sleb->endpt);
523                 if (endpt == 0) {
524                         err = ubifs_leb_unmap(c, lnum);
525                         if (err)
526                                 return err;
527                 } else {
528                         int len = ALIGN(endpt, c->min_io_size);
529 
530                         if (start) {
531                                 err = ubifs_leb_read(c, lnum, sleb->buf, 0,
532                                                      start, 1);
533                                 if (err)
534                                         return err;
535                         }
536                         /* Pad to min_io_size */
537                         if (len > endpt) {
538                                 int pad_len = len - ALIGN(endpt, 8);
539 
540                                 if (pad_len > 0) {
541                                         void *buf = sleb->buf + len - pad_len;
542 
543                                         ubifs_pad(c, buf, pad_len);
544                                 }
545                         }
546                         err = ubifs_leb_change(c, lnum, sleb->buf, len);
547                         if (err)
548                                 return err;
549                 }
550         }
551         return 0;
552 }
553 
554 /**
555  * drop_last_group - drop the last group of nodes.
556  * @sleb: scanned LEB information
557  * @offs: offset of dropped nodes is returned here
558  *
559  * This is a helper function for 'ubifs_recover_leb()' which drops the last
560  * group of nodes of the scanned LEB.
561  */
562 static void drop_last_group(struct ubifs_scan_leb *sleb, int *offs)
563 {
564         while (!list_empty(&sleb->nodes)) {
565                 struct ubifs_scan_node *snod;
566                 struct ubifs_ch *ch;
567 
568                 snod = list_entry(sleb->nodes.prev, struct ubifs_scan_node,
569                                   list);
570                 ch = snod->node;
571                 if (ch->group_type != UBIFS_IN_NODE_GROUP)
572                         break;
573 
574                 dbg_rcvry("dropping grouped node at %d:%d",
575                           sleb->lnum, snod->offs);
576                 *offs = snod->offs;
577                 list_del(&snod->list);
578                 kfree(snod);
579                 sleb->nodes_cnt -= 1;
580         }
581 }
582 
583 /**
584  * drop_last_node - drop the last node.
585  * @sleb: scanned LEB information
586  * @offs: offset of dropped nodes is returned here
587  *
588  * This is a helper function for 'ubifs_recover_leb()' which drops the last
589  * node of the scanned LEB.
590  */
591 static void drop_last_node(struct ubifs_scan_leb *sleb, int *offs)
592 {
593         struct ubifs_scan_node *snod;
594 
595         if (!list_empty(&sleb->nodes)) {
596                 snod = list_entry(sleb->nodes.prev, struct ubifs_scan_node,
597                                   list);
598 
599                 dbg_rcvry("dropping last node at %d:%d",
600                           sleb->lnum, snod->offs);
601                 *offs = snod->offs;
602                 list_del(&snod->list);
603                 kfree(snod);
604                 sleb->nodes_cnt -= 1;
605         }
606 }
607 
608 /**
609  * ubifs_recover_leb - scan and recover a LEB.
610  * @c: UBIFS file-system description object
611  * @lnum: LEB number
612  * @offs: offset
613  * @sbuf: LEB-sized buffer to use
614  * @jhead: journal head number this LEB belongs to (%-1 if the LEB does not
615  *         belong to any journal head)
616  *
617  * This function does a scan of a LEB, but caters for errors that might have
618  * been caused by the unclean unmount from which we are attempting to recover.
619  * Returns the scanned information on success and a negative error code on
620  * failure.
621  */
622 struct ubifs_scan_leb *ubifs_recover_leb(struct ubifs_info *c, int lnum,
623                                          int offs, void *sbuf, int jhead)
624 {
625         int ret = 0, err, len = c->leb_size - offs, start = offs, min_io_unit;
626         int grouped = jhead == -1 ? 0 : c->jheads[jhead].grouped;
627         struct ubifs_scan_leb *sleb;
628         void *buf = sbuf + offs;
629 
630         dbg_rcvry("%d:%d, jhead %d, grouped %d", lnum, offs, jhead, grouped);
631 
632         sleb = ubifs_start_scan(c, lnum, offs, sbuf);
633         if (IS_ERR(sleb))
634                 return sleb;
635 
636         ubifs_assert(c, len >= 8);
637         while (len >= 8) {
638                 dbg_scan("look at LEB %d:%d (%d bytes left)",
639                          lnum, offs, len);
640 
641                 cond_resched();
642 
643                 /*
644                  * Scan quietly until there is an error from which we cannot
645                  * recover
646                  */
647                 ret = ubifs_scan_a_node(c, buf, len, lnum, offs, 1);
648                 if (ret == SCANNED_A_NODE) {
649                         /* A valid node, and not a padding node */
650                         struct ubifs_ch *ch = buf;
651                         int node_len;
652 
653                         err = ubifs_add_snod(c, sleb, buf, offs);
654                         if (err)
655                                 goto error;
656                         node_len = ALIGN(le32_to_cpu(ch->len), 8);
657                         offs += node_len;
658                         buf += node_len;
659                         len -= node_len;
660                 } else if (ret > 0) {
661                         /* Padding bytes or a valid padding node */
662                         offs += ret;
663                         buf += ret;
664                         len -= ret;
665                 } else if (ret == SCANNED_EMPTY_SPACE ||
666                            ret == SCANNED_GARBAGE     ||
667                            ret == SCANNED_A_BAD_PAD_NODE ||
668                            ret == SCANNED_A_CORRUPT_NODE) {
669                         dbg_rcvry("found corruption (%d) at %d:%d",
670                                   ret, lnum, offs);
671                         break;
672                 } else {
673                         ubifs_err(c, "unexpected return value %d", ret);
674                         err = -EINVAL;
675                         goto error;
676                 }
677         }
678 
679         if (ret == SCANNED_GARBAGE || ret == SCANNED_A_BAD_PAD_NODE) {
680                 if (!is_last_write(c, buf, offs))
681                         goto corrupted_rescan;
682         } else if (ret == SCANNED_A_CORRUPT_NODE) {
683                 if (!no_more_nodes(c, buf, len, lnum, offs))
684                         goto corrupted_rescan;
685         } else if (!is_empty(buf, len)) {
686                 if (!is_last_write(c, buf, offs)) {
687                         int corruption = first_non_ff(buf, len);
688 
689                         /*
690                          * See header comment for this file for more
691                          * explanations about the reasons we have this check.
692                          */
693                         ubifs_err(c, "corrupt empty space LEB %d:%d, corruption starts at %d",
694                                   lnum, offs, corruption);
695                         /* Make sure we dump interesting non-0xFF data */
696                         offs += corruption;
697                         buf += corruption;
698                         goto corrupted;
699                 }
700         }
701 
702         min_io_unit = round_down(offs, c->min_io_size);
703         if (grouped)
704                 /*
705                  * If nodes are grouped, always drop the incomplete group at
706                  * the end.
707                  */
708                 drop_last_group(sleb, &offs);
709 
710         if (jhead == GCHD) {
711                 /*
712                  * If this LEB belongs to the GC head then while we are in the
713                  * middle of the same min. I/O unit keep dropping nodes. So
714                  * basically, what we want is to make sure that the last min.
715                  * I/O unit where we saw the corruption is dropped completely
716                  * with all the uncorrupted nodes which may possibly sit there.
717                  *
718                  * In other words, let's name the min. I/O unit where the
719                  * corruption starts B, and the previous min. I/O unit A. The
720                  * below code tries to deal with a situation when half of B
721                  * contains valid nodes or the end of a valid node, and the
722                  * second half of B contains corrupted data or garbage. This
723                  * means that UBIFS had been writing to B just before the power
724                  * cut happened. I do not know how realistic is this scenario
725                  * that half of the min. I/O unit had been written successfully
726                  * and the other half not, but this is possible in our 'failure
727                  * mode emulation' infrastructure at least.
728                  *
729                  * So what is the problem, why we need to drop those nodes? Why
730                  * can't we just clean-up the second half of B by putting a
731                  * padding node there? We can, and this works fine with one
732                  * exception which was reproduced with power cut emulation
733                  * testing and happens extremely rarely.
734                  *
735                  * Imagine the file-system is full, we run GC which starts
736                  * moving valid nodes from LEB X to LEB Y (obviously, LEB Y is
737                  * the current GC head LEB). The @c->gc_lnum is -1, which means
738                  * that GC will retain LEB X and will try to continue. Imagine
739                  * that LEB X is currently the dirtiest LEB, and the amount of
740                  * used space in LEB Y is exactly the same as amount of free
741                  * space in LEB X.
742                  *
743                  * And a power cut happens when nodes are moved from LEB X to
744                  * LEB Y. We are here trying to recover LEB Y which is the GC
745                  * head LEB. We find the min. I/O unit B as described above.
746                  * Then we clean-up LEB Y by padding min. I/O unit. And later
747                  * 'ubifs_rcvry_gc_commit()' function fails, because it cannot
748                  * find a dirty LEB which could be GC'd into LEB Y! Even LEB X
749                  * does not match because the amount of valid nodes there does
750                  * not fit the free space in LEB Y any more! And this is
751                  * because of the padding node which we added to LEB Y. The
752                  * user-visible effect of this which I once observed and
753                  * analysed is that we cannot mount the file-system with
754                  * -ENOSPC error.
755                  *
756                  * So obviously, to make sure that situation does not happen we
757                  * should free min. I/O unit B in LEB Y completely and the last
758                  * used min. I/O unit in LEB Y should be A. This is basically
759                  * what the below code tries to do.
760                  */
761                 while (offs > min_io_unit)
762                         drop_last_node(sleb, &offs);
763         }
764 
765         buf = sbuf + offs;
766         len = c->leb_size - offs;
767 
768         clean_buf(c, &buf, lnum, &offs, &len);
769         ubifs_end_scan(c, sleb, lnum, offs);
770 
771         err = fix_unclean_leb(c, sleb, start);
772         if (err)
773                 goto error;
774 
775         return sleb;
776 
777 corrupted_rescan:
778         /* Re-scan the corrupted data with verbose messages */
779         ubifs_err(c, "corruption %d", ret);
780         ubifs_scan_a_node(c, buf, len, lnum, offs, 0);
781 corrupted:
782         ubifs_scanned_corruption(c, lnum, offs, buf);
783         err = -EUCLEAN;
784 error:
785         ubifs_err(c, "LEB %d scanning failed", lnum);
786         ubifs_scan_destroy(sleb);
787         return ERR_PTR(err);
788 }
789 
790 /**
791  * get_cs_sqnum - get commit start sequence number.
792  * @c: UBIFS file-system description object
793  * @lnum: LEB number of commit start node
794  * @offs: offset of commit start node
795  * @cs_sqnum: commit start sequence number is returned here
796  *
797  * This function returns %0 on success and a negative error code on failure.
798  */
799 static int get_cs_sqnum(struct ubifs_info *c, int lnum, int offs,
800                         unsigned long long *cs_sqnum)
801 {
802         struct ubifs_cs_node *cs_node = NULL;
803         int err, ret;
804 
805         dbg_rcvry("at %d:%d", lnum, offs);
806         cs_node = kmalloc(UBIFS_CS_NODE_SZ, GFP_KERNEL);
807         if (!cs_node)
808                 return -ENOMEM;
809         if (c->leb_size - offs < UBIFS_CS_NODE_SZ)
810                 goto out_err;
811         err = ubifs_leb_read(c, lnum, (void *)cs_node, offs,
812                              UBIFS_CS_NODE_SZ, 0);
813         if (err && err != -EBADMSG)
814                 goto out_free;
815         ret = ubifs_scan_a_node(c, cs_node, UBIFS_CS_NODE_SZ, lnum, offs, 0);
816         if (ret != SCANNED_A_NODE) {
817                 ubifs_err(c, "Not a valid node");
818                 goto out_err;
819         }
820         if (cs_node->ch.node_type != UBIFS_CS_NODE) {
821                 ubifs_err(c, "Not a CS node, type is %d", cs_node->ch.node_type);
822                 goto out_err;
823         }
824         if (le64_to_cpu(cs_node->cmt_no) != c->cmt_no) {
825                 ubifs_err(c, "CS node cmt_no %llu != current cmt_no %llu",
826                           (unsigned long long)le64_to_cpu(cs_node->cmt_no),
827                           c->cmt_no);
828                 goto out_err;
829         }
830         *cs_sqnum = le64_to_cpu(cs_node->ch.sqnum);
831         dbg_rcvry("commit start sqnum %llu", *cs_sqnum);
832         kfree(cs_node);
833         return 0;
834 
835 out_err:
836         err = -EINVAL;
837 out_free:
838         ubifs_err(c, "failed to get CS sqnum");
839         kfree(cs_node);
840         return err;
841 }
842 
843 /**
844  * ubifs_recover_log_leb - scan and recover a log LEB.
845  * @c: UBIFS file-system description object
846  * @lnum: LEB number
847  * @offs: offset
848  * @sbuf: LEB-sized buffer to use
849  *
850  * This function does a scan of a LEB, but caters for errors that might have
851  * been caused by unclean reboots from which we are attempting to recover
852  * (assume that only the last log LEB can be corrupted by an unclean reboot).
853  *
854  * This function returns %0 on success and a negative error code on failure.
855  */
856 struct ubifs_scan_leb *ubifs_recover_log_leb(struct ubifs_info *c, int lnum,
857                                              int offs, void *sbuf)
858 {
859         struct ubifs_scan_leb *sleb;
860         int next_lnum;
861 
862         dbg_rcvry("LEB %d", lnum);
863         next_lnum = lnum + 1;
864         if (next_lnum >= UBIFS_LOG_LNUM + c->log_lebs)
865                 next_lnum = UBIFS_LOG_LNUM;
866         if (next_lnum != c->ltail_lnum) {
867                 /*
868                  * We can only recover at the end of the log, so check that the
869                  * next log LEB is empty or out of date.
870                  */
871                 sleb = ubifs_scan(c, next_lnum, 0, sbuf, 0);
872                 if (IS_ERR(sleb))
873                         return sleb;
874                 if (sleb->nodes_cnt) {
875                         struct ubifs_scan_node *snod;
876                         unsigned long long cs_sqnum = c->cs_sqnum;
877 
878                         snod = list_entry(sleb->nodes.next,
879                                           struct ubifs_scan_node, list);
880                         if (cs_sqnum == 0) {
881                                 int err;
882 
883                                 err = get_cs_sqnum(c, lnum, offs, &cs_sqnum);
884                                 if (err) {
885                                         ubifs_scan_destroy(sleb);
886                                         return ERR_PTR(err);
887                                 }
888                         }
889                         if (snod->sqnum > cs_sqnum) {
890                                 ubifs_err(c, "unrecoverable log corruption in LEB %d",
891                                           lnum);
892                                 ubifs_scan_destroy(sleb);
893                                 return ERR_PTR(-EUCLEAN);
894                         }
895                 }
896                 ubifs_scan_destroy(sleb);
897         }
898         return ubifs_recover_leb(c, lnum, offs, sbuf, -1);
899 }
900 
901 /**
902  * recover_head - recover a head.
903  * @c: UBIFS file-system description object
904  * @lnum: LEB number of head to recover
905  * @offs: offset of head to recover
906  * @sbuf: LEB-sized buffer to use
907  *
908  * This function ensures that there is no data on the flash at a head location.
909  *
910  * This function returns %0 on success and a negative error code on failure.
911  */
912 static int recover_head(struct ubifs_info *c, int lnum, int offs, void *sbuf)
913 {
914         int len = c->max_write_size, err;
915 
916         if (offs + len > c->leb_size)
917                 len = c->leb_size - offs;
918 
919         if (!len)
920                 return 0;
921 
922         /* Read at the head location and check it is empty flash */
923         err = ubifs_leb_read(c, lnum, sbuf, offs, len, 1);
924         if (err || !is_empty(sbuf, len)) {
925                 dbg_rcvry("cleaning head at %d:%d", lnum, offs);
926                 if (offs == 0)
927                         return ubifs_leb_unmap(c, lnum);
928                 err = ubifs_leb_read(c, lnum, sbuf, 0, offs, 1);
929                 if (err)
930                         return err;
931                 return ubifs_leb_change(c, lnum, sbuf, offs);
932         }
933 
934         return 0;
935 }
936 
937 /**
938  * ubifs_recover_inl_heads - recover index and LPT heads.
939  * @c: UBIFS file-system description object
940  * @sbuf: LEB-sized buffer to use
941  *
942  * This function ensures that there is no data on the flash at the index and
943  * LPT head locations.
944  *
945  * This deals with the recovery of a half-completed journal commit. UBIFS is
946  * careful never to overwrite the last version of the index or the LPT. Because
947  * the index and LPT are wandering trees, data from a half-completed commit will
948  * not be referenced anywhere in UBIFS. The data will be either in LEBs that are
949  * assumed to be empty and will be unmapped anyway before use, or in the index
950  * and LPT heads.
951  *
952  * This function returns %0 on success and a negative error code on failure.
953  */
954 int ubifs_recover_inl_heads(struct ubifs_info *c, void *sbuf)
955 {
956         int err;
957 
958         ubifs_assert(c, !c->ro_mount || c->remounting_rw);
959 
960         dbg_rcvry("checking index head at %d:%d", c->ihead_lnum, c->ihead_offs);
961         err = recover_head(c, c->ihead_lnum, c->ihead_offs, sbuf);
962         if (err)
963                 return err;
964 
965         dbg_rcvry("checking LPT head at %d:%d", c->nhead_lnum, c->nhead_offs);
966 
967         return recover_head(c, c->nhead_lnum, c->nhead_offs, sbuf);
968 }
969 
970 /**
971  * clean_an_unclean_leb - read and write a LEB to remove corruption.
972  * @c: UBIFS file-system description object
973  * @ucleb: unclean LEB information
974  * @sbuf: LEB-sized buffer to use
975  *
976  * This function reads a LEB up to a point pre-determined by the mount recovery,
977  * checks the nodes, and writes the result back to the flash, thereby cleaning
978  * off any following corruption, or non-fatal ECC errors.
979  *
980  * This function returns %0 on success and a negative error code on failure.
981  */
982 static int clean_an_unclean_leb(struct ubifs_info *c,
983                                 struct ubifs_unclean_leb *ucleb, void *sbuf)
984 {
985         int err, lnum = ucleb->lnum, offs = 0, len = ucleb->endpt, quiet = 1;
986         void *buf = sbuf;
987 
988         dbg_rcvry("LEB %d len %d", lnum, len);
989 
990         if (len == 0) {
991                 /* Nothing to read, just unmap it */
992                 return ubifs_leb_unmap(c, lnum);
993         }
994 
995         err = ubifs_leb_read(c, lnum, buf, offs, len, 0);
996         if (err && err != -EBADMSG)
997                 return err;
998 
999         while (len >= 8) {
1000                 int ret;
1001 
1002                 cond_resched();
1003 
1004                 /* Scan quietly until there is an error */
1005                 ret = ubifs_scan_a_node(c, buf, len, lnum, offs, quiet);
1006 
1007                 if (ret == SCANNED_A_NODE) {
1008                         /* A valid node, and not a padding node */
1009                         struct ubifs_ch *ch = buf;
1010                         int node_len;
1011 
1012                         node_len = ALIGN(le32_to_cpu(ch->len), 8);
1013                         offs += node_len;
1014                         buf += node_len;
1015                         len -= node_len;
1016                         continue;
1017                 }
1018 
1019                 if (ret > 0) {
1020                         /* Padding bytes or a valid padding node */
1021                         offs += ret;
1022                         buf += ret;
1023                         len -= ret;
1024                         continue;
1025                 }
1026 
1027                 if (ret == SCANNED_EMPTY_SPACE) {
1028                         ubifs_err(c, "unexpected empty space at %d:%d",
1029                                   lnum, offs);
1030                         return -EUCLEAN;
1031                 }
1032 
1033                 if (quiet) {
1034                         /* Redo the last scan but noisily */
1035                         quiet = 0;
1036                         continue;
1037                 }
1038 
1039                 ubifs_scanned_corruption(c, lnum, offs, buf);
1040                 return -EUCLEAN;
1041         }
1042 
1043         /* Pad to min_io_size */
1044         len = ALIGN(ucleb->endpt, c->min_io_size);
1045         if (len > ucleb->endpt) {
1046                 int pad_len = len - ALIGN(ucleb->endpt, 8);
1047 
1048                 if (pad_len > 0) {
1049                         buf = c->sbuf + len - pad_len;
1050                         ubifs_pad(c, buf, pad_len);
1051                 }
1052         }
1053 
1054         /* Write back the LEB atomically */
1055         err = ubifs_leb_change(c, lnum, sbuf, len);
1056         if (err)
1057                 return err;
1058 
1059         dbg_rcvry("cleaned LEB %d", lnum);
1060 
1061         return 0;
1062 }
1063 
1064 /**
1065  * ubifs_clean_lebs - clean LEBs recovered during read-only mount.
1066  * @c: UBIFS file-system description object
1067  * @sbuf: LEB-sized buffer to use
1068  *
1069  * This function cleans a LEB identified during recovery that needs to be
1070  * written but was not because UBIFS was mounted read-only. This happens when
1071  * remounting to read-write mode.
1072  *
1073  * This function returns %0 on success and a negative error code on failure.
1074  */
1075 int ubifs_clean_lebs(struct ubifs_info *c, void *sbuf)
1076 {
1077         dbg_rcvry("recovery");
1078         while (!list_empty(&c->unclean_leb_list)) {
1079                 struct ubifs_unclean_leb *ucleb;
1080                 int err;
1081 
1082                 ucleb = list_entry(c->unclean_leb_list.next,
1083                                    struct ubifs_unclean_leb, list);
1084                 err = clean_an_unclean_leb(c, ucleb, sbuf);
1085                 if (err)
1086                         return err;
1087                 list_del(&ucleb->list);
1088                 kfree(ucleb);
1089         }
1090         return 0;
1091 }
1092 
1093 /**
1094  * grab_empty_leb - grab an empty LEB to use as GC LEB and run commit.
1095  * @c: UBIFS file-system description object
1096  *
1097  * This is a helper function for 'ubifs_rcvry_gc_commit()' which grabs an empty
1098  * LEB to be used as GC LEB (@c->gc_lnum), and then runs the commit. Returns
1099  * zero in case of success and a negative error code in case of failure.
1100  */
1101 static int grab_empty_leb(struct ubifs_info *c)
1102 {
1103         int lnum, err;
1104 
1105         /*
1106          * Note, it is very important to first search for an empty LEB and then
1107          * run the commit, not vice-versa. The reason is that there might be
1108          * only one empty LEB at the moment, the one which has been the
1109          * @c->gc_lnum just before the power cut happened. During the regular
1110          * UBIFS operation (not now) @c->gc_lnum is marked as "taken", so no
1111          * one but GC can grab it. But at this moment this single empty LEB is
1112          * not marked as taken, so if we run commit - what happens? Right, the
1113          * commit will grab it and write the index there. Remember that the
1114          * index always expands as long as there is free space, and it only
1115          * starts consolidating when we run out of space.
1116          *
1117          * IOW, if we run commit now, we might not be able to find a free LEB
1118          * after this.
1119          */
1120         lnum = ubifs_find_free_leb_for_idx(c);
1121         if (lnum < 0) {
1122                 ubifs_err(c, "could not find an empty LEB");
1123                 ubifs_dump_lprops(c);
1124                 ubifs_dump_budg(c, &c->bi);
1125                 return lnum;
1126         }
1127 
1128         /* Reset the index flag */
1129         err = ubifs_change_one_lp(c, lnum, LPROPS_NC, LPROPS_NC, 0,
1130                                   LPROPS_INDEX, 0);
1131         if (err)
1132                 return err;
1133 
1134         c->gc_lnum = lnum;
1135         dbg_rcvry("found empty LEB %d, run commit", lnum);
1136 
1137         return ubifs_run_commit(c);
1138 }
1139 
1140 /**
1141  * ubifs_rcvry_gc_commit - recover the GC LEB number and run the commit.
1142  * @c: UBIFS file-system description object
1143  *
1144  * Out-of-place garbage collection requires always one empty LEB with which to
1145  * start garbage collection. The LEB number is recorded in c->gc_lnum and is
1146  * written to the master node on unmounting. In the case of an unclean unmount
1147  * the value of gc_lnum recorded in the master node is out of date and cannot
1148  * be used. Instead, recovery must allocate an empty LEB for this purpose.
1149  * However, there may not be enough empty space, in which case it must be
1150  * possible to GC the dirtiest LEB into the GC head LEB.
1151  *
1152  * This function also runs the commit which causes the TNC updates from
1153  * size-recovery and orphans to be written to the flash. That is important to
1154  * ensure correct replay order for subsequent mounts.
1155  *
1156  * This function returns %0 on success and a negative error code on failure.
1157  */
1158 int ubifs_rcvry_gc_commit(struct ubifs_info *c)
1159 {
1160         struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
1161         struct ubifs_lprops lp;
1162         int err;
1163 
1164         dbg_rcvry("GC head LEB %d, offs %d", wbuf->lnum, wbuf->offs);
1165 
1166         c->gc_lnum = -1;
1167         if (wbuf->lnum == -1 || wbuf->offs == c->leb_size)
1168                 return grab_empty_leb(c);
1169 
1170         err = ubifs_find_dirty_leb(c, &lp, wbuf->offs, 2);
1171         if (err) {
1172                 if (err != -ENOSPC)
1173                         return err;
1174 
1175                 dbg_rcvry("could not find a dirty LEB");
1176                 return grab_empty_leb(c);
1177         }
1178 
1179         ubifs_assert(c, !(lp.flags & LPROPS_INDEX));
1180         ubifs_assert(c, lp.free + lp.dirty >= wbuf->offs);
1181 
1182         /*
1183          * We run the commit before garbage collection otherwise subsequent
1184          * mounts will see the GC and orphan deletion in a different order.
1185          */
1186         dbg_rcvry("committing");
1187         err = ubifs_run_commit(c);
1188         if (err)
1189                 return err;
1190 
1191         dbg_rcvry("GC'ing LEB %d", lp.lnum);
1192         mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead);
1193         err = ubifs_garbage_collect_leb(c, &lp);
1194         if (err >= 0) {
1195                 int err2 = ubifs_wbuf_sync_nolock(wbuf);
1196 
1197                 if (err2)
1198                         err = err2;
1199         }
1200         mutex_unlock(&wbuf->io_mutex);
1201         if (err < 0) {
1202                 ubifs_err(c, "GC failed, error %d", err);
1203                 if (err == -EAGAIN)
1204                         err = -EINVAL;
1205                 return err;
1206         }
1207 
1208         ubifs_assert(c, err == LEB_RETAINED);
1209         if (err != LEB_RETAINED)
1210                 return -EINVAL;
1211 
1212         err = ubifs_leb_unmap(c, c->gc_lnum);
1213         if (err)
1214                 return err;
1215 
1216         dbg_rcvry("allocated LEB %d for GC", lp.lnum);
1217         return 0;
1218 }
1219 
1220 /**
1221  * struct size_entry - inode size information for recovery.
1222  * @rb: link in the RB-tree of sizes
1223  * @inum: inode number
1224  * @i_size: size on inode
1225  * @d_size: maximum size based on data nodes
1226  * @exists: indicates whether the inode exists
1227  * @inode: inode if pinned in memory awaiting rw mode to fix it
1228  */
1229 struct size_entry {
1230         struct rb_node rb;
1231         ino_t inum;
1232         loff_t i_size;
1233         loff_t d_size;
1234         int exists;
1235         struct inode *inode;
1236 };
1237 
1238 /**
1239  * add_ino - add an entry to the size tree.
1240  * @c: UBIFS file-system description object
1241  * @inum: inode number
1242  * @i_size: size on inode
1243  * @d_size: maximum size based on data nodes
1244  * @exists: indicates whether the inode exists
1245  */
1246 static int add_ino(struct ubifs_info *c, ino_t inum, loff_t i_size,
1247                    loff_t d_size, int exists)
1248 {
1249         struct rb_node **p = &c->size_tree.rb_node, *parent = NULL;
1250         struct size_entry *e;
1251 
1252         while (*p) {
1253                 parent = *p;
1254                 e = rb_entry(parent, struct size_entry, rb);
1255                 if (inum < e->inum)
1256                         p = &(*p)->rb_left;
1257                 else
1258                         p = &(*p)->rb_right;
1259         }
1260 
1261         e = kzalloc(sizeof(struct size_entry), GFP_KERNEL);
1262         if (!e)
1263                 return -ENOMEM;
1264 
1265         e->inum = inum;
1266         e->i_size = i_size;
1267         e->d_size = d_size;
1268         e->exists = exists;
1269 
1270         rb_link_node(&e->rb, parent, p);
1271         rb_insert_color(&e->rb, &c->size_tree);
1272 
1273         return 0;
1274 }
1275 
1276 /**
1277  * find_ino - find an entry on the size tree.
1278  * @c: UBIFS file-system description object
1279  * @inum: inode number
1280  */
1281 static struct size_entry *find_ino(struct ubifs_info *c, ino_t inum)
1282 {
1283         struct rb_node *p = c->size_tree.rb_node;
1284         struct size_entry *e;
1285 
1286         while (p) {
1287                 e = rb_entry(p, struct size_entry, rb);
1288                 if (inum < e->inum)
1289                         p = p->rb_left;
1290                 else if (inum > e->inum)
1291                         p = p->rb_right;
1292                 else
1293                         return e;
1294         }
1295         return NULL;
1296 }
1297 
1298 /**
1299  * remove_ino - remove an entry from the size tree.
1300  * @c: UBIFS file-system description object
1301  * @inum: inode number
1302  */
1303 static void remove_ino(struct ubifs_info *c, ino_t inum)
1304 {
1305         struct size_entry *e = find_ino(c, inum);
1306 
1307         if (!e)
1308                 return;
1309         rb_erase(&e->rb, &c->size_tree);
1310         kfree(e);
1311 }
1312 
1313 /**
1314  * ubifs_destroy_size_tree - free resources related to the size tree.
1315  * @c: UBIFS file-system description object
1316  */
1317 void ubifs_destroy_size_tree(struct ubifs_info *c)
1318 {
1319         struct size_entry *e, *n;
1320 
1321         rbtree_postorder_for_each_entry_safe(e, n, &c->size_tree, rb) {
1322                 iput(e->inode);
1323                 kfree(e);
1324         }
1325 
1326         c->size_tree = RB_ROOT;
1327 }
1328 
1329 /**
1330  * ubifs_recover_size_accum - accumulate inode sizes for recovery.
1331  * @c: UBIFS file-system description object
1332  * @key: node key
1333  * @deletion: node is for a deletion
1334  * @new_size: inode size
1335  *
1336  * This function has two purposes:
1337  *     1) to ensure there are no data nodes that fall outside the inode size
1338  *     2) to ensure there are no data nodes for inodes that do not exist
1339  * To accomplish those purposes, a rb-tree is constructed containing an entry
1340  * for each inode number in the journal that has not been deleted, and recording
1341  * the size from the inode node, the maximum size of any data node (also altered
1342  * by truncations) and a flag indicating a inode number for which no inode node
1343  * was present in the journal.
1344  *
1345  * Note that there is still the possibility that there are data nodes that have
1346  * been committed that are beyond the inode size, however the only way to find
1347  * them would be to scan the entire index. Alternatively, some provision could
1348  * be made to record the size of inodes at the start of commit, which would seem
1349  * very cumbersome for a scenario that is quite unlikely and the only negative
1350  * consequence of which is wasted space.
1351  *
1352  * This functions returns %0 on success and a negative error code on failure.
1353  */
1354 int ubifs_recover_size_accum(struct ubifs_info *c, union ubifs_key *key,
1355                              int deletion, loff_t new_size)
1356 {
1357         ino_t inum = key_inum(c, key);
1358         struct size_entry *e;
1359         int err;
1360 
1361         switch (key_type(c, key)) {
1362         case UBIFS_INO_KEY:
1363                 if (deletion)
1364                         remove_ino(c, inum);
1365                 else {
1366                         e = find_ino(c, inum);
1367                         if (e) {
1368                                 e->i_size = new_size;
1369                                 e->exists = 1;
1370                         } else {
1371                                 err = add_ino(c, inum, new_size, 0, 1);
1372                                 if (err)
1373                                         return err;
1374                         }
1375                 }
1376                 break;
1377         case UBIFS_DATA_KEY:
1378                 e = find_ino(c, inum);
1379                 if (e) {
1380                         if (new_size > e->d_size)
1381                                 e->d_size = new_size;
1382                 } else {
1383                         err = add_ino(c, inum, 0, new_size, 0);
1384                         if (err)
1385                                 return err;
1386                 }
1387                 break;
1388         case UBIFS_TRUN_KEY:
1389                 e = find_ino(c, inum);
1390                 if (e)
1391                         e->d_size = new_size;
1392                 break;
1393         }
1394         return 0;
1395 }
1396 
1397 /**
1398  * fix_size_in_place - fix inode size in place on flash.
1399  * @c: UBIFS file-system description object
1400  * @e: inode size information for recovery
1401  */
1402 static int fix_size_in_place(struct ubifs_info *c, struct size_entry *e)
1403 {
1404         struct ubifs_ino_node *ino = c->sbuf;
1405         unsigned char *p;
1406         union ubifs_key key;
1407         int err, lnum, offs, len;
1408         loff_t i_size;
1409         uint32_t crc;
1410 
1411         /* Locate the inode node LEB number and offset */
1412         ino_key_init(c, &key, e->inum);
1413         err = ubifs_tnc_locate(c, &key, ino, &lnum, &offs);
1414         if (err)
1415                 goto out;
1416         /*
1417          * If the size recorded on the inode node is greater than the size that
1418          * was calculated from nodes in the journal then don't change the inode.
1419          */
1420         i_size = le64_to_cpu(ino->size);
1421         if (i_size >= e->d_size)
1422                 return 0;
1423         /* Read the LEB */
1424         err = ubifs_leb_read(c, lnum, c->sbuf, 0, c->leb_size, 1);
1425         if (err)
1426                 goto out;
1427         /* Change the size field and recalculate the CRC */
1428         ino = c->sbuf + offs;
1429         ino->size = cpu_to_le64(e->d_size);
1430         len = le32_to_cpu(ino->ch.len);
1431         crc = crc32(UBIFS_CRC32_INIT, (void *)ino + 8, len - 8);
1432         ino->ch.crc = cpu_to_le32(crc);
1433         /* Work out where data in the LEB ends and free space begins */
1434         p = c->sbuf;
1435         len = c->leb_size - 1;
1436         while (p[len] == 0xff)
1437                 len -= 1;
1438         len = ALIGN(len + 1, c->min_io_size);
1439         /* Atomically write the fixed LEB back again */
1440         err = ubifs_leb_change(c, lnum, c->sbuf, len);
1441         if (err)
1442                 goto out;
1443         dbg_rcvry("inode %lu at %d:%d size %lld -> %lld",
1444                   (unsigned long)e->inum, lnum, offs, i_size, e->d_size);
1445         return 0;
1446 
1447 out:
1448         ubifs_warn(c, "inode %lu failed to fix size %lld -> %lld error %d",
1449                    (unsigned long)e->inum, e->i_size, e->d_size, err);
1450         return err;
1451 }
1452 
1453 /**
1454  * inode_fix_size - fix inode size
1455  * @c: UBIFS file-system description object
1456  * @e: inode size information for recovery
1457  */
1458 static int inode_fix_size(struct ubifs_info *c, struct size_entry *e)
1459 {
1460         struct inode *inode;
1461         struct ubifs_inode *ui;
1462         int err;
1463 
1464         if (c->ro_mount)
1465                 ubifs_assert(c, !e->inode);
1466 
1467         if (e->inode) {
1468                 /* Remounting rw, pick up inode we stored earlier */
1469                 inode = e->inode;
1470         } else {
1471                 inode = ubifs_iget(c->vfs_sb, e->inum);
1472                 if (IS_ERR(inode))
1473                         return PTR_ERR(inode);
1474 
1475                 if (inode->i_size >= e->d_size) {
1476                         /*
1477                          * The original inode in the index already has a size
1478                          * big enough, nothing to do
1479                          */
1480                         iput(inode);
1481                         return 0;
1482                 }
1483 
1484                 dbg_rcvry("ino %lu size %lld -> %lld",
1485                           (unsigned long)e->inum,
1486                           inode->i_size, e->d_size);
1487 
1488                 ui = ubifs_inode(inode);
1489 
1490                 inode->i_size = e->d_size;
1491                 ui->ui_size = e->d_size;
1492                 ui->synced_i_size = e->d_size;
1493 
1494                 e->inode = inode;
1495         }
1496 
1497         /*
1498          * In readonly mode just keep the inode pinned in memory until we go
1499          * readwrite. In readwrite mode write the inode to the journal with the
1500          * fixed size.
1501          */
1502         if (c->ro_mount)
1503                 return 0;
1504 
1505         err = ubifs_jnl_write_inode(c, inode);
1506 
1507         iput(inode);
1508 
1509         if (err)
1510                 return err;
1511 
1512         rb_erase(&e->rb, &c->size_tree);
1513         kfree(e);
1514 
1515         return 0;
1516 }
1517 
1518 /**
1519  * ubifs_recover_size - recover inode size.
1520  * @c: UBIFS file-system description object
1521  * @in_place: If true, do a in-place size fixup
1522  *
1523  * This function attempts to fix inode size discrepancies identified by the
1524  * 'ubifs_recover_size_accum()' function.
1525  *
1526  * This functions returns %0 on success and a negative error code on failure.
1527  */
1528 int ubifs_recover_size(struct ubifs_info *c, bool in_place)
1529 {
1530         struct rb_node *this = rb_first(&c->size_tree);
1531 
1532         while (this) {
1533                 struct size_entry *e;
1534                 int err;
1535 
1536                 e = rb_entry(this, struct size_entry, rb);
1537 
1538                 this = rb_next(this);
1539 
1540                 if (!e->exists) {
1541                         union ubifs_key key;
1542 
1543                         ino_key_init(c, &key, e->inum);
1544                         err = ubifs_tnc_lookup(c, &key, c->sbuf);
1545                         if (err && err != -ENOENT)
1546                                 return err;
1547                         if (err == -ENOENT) {
1548                                 /* Remove data nodes that have no inode */
1549                                 dbg_rcvry("removing ino %lu",
1550                                           (unsigned long)e->inum);
1551                                 err = ubifs_tnc_remove_ino(c, e->inum);
1552                                 if (err)
1553                                         return err;
1554                         } else {
1555                                 struct ubifs_ino_node *ino = c->sbuf;
1556 
1557                                 e->exists = 1;
1558                                 e->i_size = le64_to_cpu(ino->size);
1559                         }
1560                 }
1561 
1562                 if (e->exists && e->i_size < e->d_size) {
1563                         ubifs_assert(c, !(c->ro_mount && in_place));
1564 
1565                         /*
1566                          * We found data that is outside the found inode size,
1567                          * fixup the inode size
1568                          */
1569 
1570                         if (in_place) {
1571                                 err = fix_size_in_place(c, e);
1572                                 if (err)
1573                                         return err;
1574                                 iput(e->inode);
1575                         } else {
1576                                 err = inode_fix_size(c, e);
1577                                 if (err)
1578                                         return err;
1579                                 continue;
1580                         }
1581                 }
1582 
1583                 rb_erase(&e->rb, &c->size_tree);
1584                 kfree(e);
1585         }
1586 
1587         return 0;
1588 }
1589 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp