]> git.sur5r.net Git - u-boot/blob - fs/ubifs/replay.c
rockchip: add boot-mode support for rk3288, rk3036
[u-boot] / fs / ubifs / replay.c
1 /*
2  * This file is part of UBIFS.
3  *
4  * Copyright (C) 2006-2008 Nokia Corporation.
5  *
6  * SPDX-License-Identifier:     GPL-2.0+
7  *
8  * Authors: Adrian Hunter
9  *          Artem Bityutskiy (Битюцкий Артём)
10  */
11
12 /*
13  * This file contains journal replay code. It runs when the file-system is being
14  * mounted and requires no locking.
15  *
16  * The larger is the journal, the longer it takes to scan it, so the longer it
17  * takes to mount UBIFS. This is why the journal has limited size which may be
18  * changed depending on the system requirements. But a larger journal gives
19  * faster I/O speed because it writes the index less frequently. So this is a
20  * trade-off. Also, the journal is indexed by the in-memory index (TNC), so the
21  * larger is the journal, the more memory its index may consume.
22  */
23
24 #ifdef __UBOOT__
25 #include <linux/compat.h>
26 #include <linux/err.h>
27 #endif
28 #include "ubifs.h"
29 #include <linux/bug.h>
30 #include <linux/list_sort.h>
31
32 /**
33  * struct replay_entry - replay list entry.
34  * @lnum: logical eraseblock number of the node
35  * @offs: node offset
36  * @len: node length
37  * @deletion: non-zero if this entry corresponds to a node deletion
38  * @sqnum: node sequence number
39  * @list: links the replay list
40  * @key: node key
41  * @nm: directory entry name
42  * @old_size: truncation old size
43  * @new_size: truncation new size
44  *
45  * The replay process first scans all buds and builds the replay list, then
46  * sorts the replay list in nodes sequence number order, and then inserts all
47  * the replay entries to the TNC.
48  */
49 struct replay_entry {
50         int lnum;
51         int offs;
52         int len;
53         unsigned int deletion:1;
54         unsigned long long sqnum;
55         struct list_head list;
56         union ubifs_key key;
57         union {
58                 struct qstr nm;
59                 struct {
60                         loff_t old_size;
61                         loff_t new_size;
62                 };
63         };
64 };
65
66 /**
67  * struct bud_entry - entry in the list of buds to replay.
68  * @list: next bud in the list
69  * @bud: bud description object
70  * @sqnum: reference node sequence number
71  * @free: free bytes in the bud
72  * @dirty: dirty bytes in the bud
73  */
74 struct bud_entry {
75         struct list_head list;
76         struct ubifs_bud *bud;
77         unsigned long long sqnum;
78         int free;
79         int dirty;
80 };
81
82 /**
83  * set_bud_lprops - set free and dirty space used by a bud.
84  * @c: UBIFS file-system description object
85  * @b: bud entry which describes the bud
86  *
87  * This function makes sure the LEB properties of bud @b are set correctly
88  * after the replay. Returns zero in case of success and a negative error code
89  * in case of failure.
90  */
91 static int set_bud_lprops(struct ubifs_info *c, struct bud_entry *b)
92 {
93         const struct ubifs_lprops *lp;
94         int err = 0, dirty;
95
96         ubifs_get_lprops(c);
97
98         lp = ubifs_lpt_lookup_dirty(c, b->bud->lnum);
99         if (IS_ERR(lp)) {
100                 err = PTR_ERR(lp);
101                 goto out;
102         }
103
104         dirty = lp->dirty;
105         if (b->bud->start == 0 && (lp->free != c->leb_size || lp->dirty != 0)) {
106                 /*
107                  * The LEB was added to the journal with a starting offset of
108                  * zero which means the LEB must have been empty. The LEB
109                  * property values should be @lp->free == @c->leb_size and
110                  * @lp->dirty == 0, but that is not the case. The reason is that
111                  * the LEB had been garbage collected before it became the bud,
112                  * and there was not commit inbetween. The garbage collector
113                  * resets the free and dirty space without recording it
114                  * anywhere except lprops, so if there was no commit then
115                  * lprops does not have that information.
116                  *
117                  * We do not need to adjust free space because the scan has told
118                  * us the exact value which is recorded in the replay entry as
119                  * @b->free.
120                  *
121                  * However we do need to subtract from the dirty space the
122                  * amount of space that the garbage collector reclaimed, which
123                  * is the whole LEB minus the amount of space that was free.
124                  */
125                 dbg_mnt("bud LEB %d was GC'd (%d free, %d dirty)", b->bud->lnum,
126                         lp->free, lp->dirty);
127                 dbg_gc("bud LEB %d was GC'd (%d free, %d dirty)", b->bud->lnum,
128                         lp->free, lp->dirty);
129                 dirty -= c->leb_size - lp->free;
130                 /*
131                  * If the replay order was perfect the dirty space would now be
132                  * zero. The order is not perfect because the journal heads
133                  * race with each other. This is not a problem but is does mean
134                  * that the dirty space may temporarily exceed c->leb_size
135                  * during the replay.
136                  */
137                 if (dirty != 0)
138                         dbg_mnt("LEB %d lp: %d free %d dirty replay: %d free %d dirty",
139                                 b->bud->lnum, lp->free, lp->dirty, b->free,
140                                 b->dirty);
141         }
142         lp = ubifs_change_lp(c, lp, b->free, dirty + b->dirty,
143                              lp->flags | LPROPS_TAKEN, 0);
144         if (IS_ERR(lp)) {
145                 err = PTR_ERR(lp);
146                 goto out;
147         }
148
149         /* Make sure the journal head points to the latest bud */
150         err = ubifs_wbuf_seek_nolock(&c->jheads[b->bud->jhead].wbuf,
151                                      b->bud->lnum, c->leb_size - b->free);
152
153 out:
154         ubifs_release_lprops(c);
155         return err;
156 }
157
158 /**
159  * set_buds_lprops - set free and dirty space for all replayed buds.
160  * @c: UBIFS file-system description object
161  *
162  * This function sets LEB properties for all replayed buds. Returns zero in
163  * case of success and a negative error code in case of failure.
164  */
165 static int set_buds_lprops(struct ubifs_info *c)
166 {
167         struct bud_entry *b;
168         int err;
169
170         list_for_each_entry(b, &c->replay_buds, list) {
171                 err = set_bud_lprops(c, b);
172                 if (err)
173                         return err;
174         }
175
176         return 0;
177 }
178
179 /**
180  * trun_remove_range - apply a replay entry for a truncation to the TNC.
181  * @c: UBIFS file-system description object
182  * @r: replay entry of truncation
183  */
184 static int trun_remove_range(struct ubifs_info *c, struct replay_entry *r)
185 {
186         unsigned min_blk, max_blk;
187         union ubifs_key min_key, max_key;
188         ino_t ino;
189
190         min_blk = r->new_size / UBIFS_BLOCK_SIZE;
191         if (r->new_size & (UBIFS_BLOCK_SIZE - 1))
192                 min_blk += 1;
193
194         max_blk = r->old_size / UBIFS_BLOCK_SIZE;
195         if ((r->old_size & (UBIFS_BLOCK_SIZE - 1)) == 0)
196                 max_blk -= 1;
197
198         ino = key_inum(c, &r->key);
199
200         data_key_init(c, &min_key, ino, min_blk);
201         data_key_init(c, &max_key, ino, max_blk);
202
203         return ubifs_tnc_remove_range(c, &min_key, &max_key);
204 }
205
206 /**
207  * apply_replay_entry - apply a replay entry to the TNC.
208  * @c: UBIFS file-system description object
209  * @r: replay entry to apply
210  *
211  * Apply a replay entry to the TNC.
212  */
213 static int apply_replay_entry(struct ubifs_info *c, struct replay_entry *r)
214 {
215         int err;
216
217         dbg_mntk(&r->key, "LEB %d:%d len %d deletion %d sqnum %llu key ",
218                  r->lnum, r->offs, r->len, r->deletion, r->sqnum);
219
220         /* Set c->replay_sqnum to help deal with dangling branches. */
221         c->replay_sqnum = r->sqnum;
222
223         if (is_hash_key(c, &r->key)) {
224                 if (r->deletion)
225                         err = ubifs_tnc_remove_nm(c, &r->key, &r->nm);
226                 else
227                         err = ubifs_tnc_add_nm(c, &r->key, r->lnum, r->offs,
228                                                r->len, &r->nm);
229         } else {
230                 if (r->deletion)
231                         switch (key_type(c, &r->key)) {
232                         case UBIFS_INO_KEY:
233                         {
234                                 ino_t inum = key_inum(c, &r->key);
235
236                                 err = ubifs_tnc_remove_ino(c, inum);
237                                 break;
238                         }
239                         case UBIFS_TRUN_KEY:
240                                 err = trun_remove_range(c, r);
241                                 break;
242                         default:
243                                 err = ubifs_tnc_remove(c, &r->key);
244                                 break;
245                         }
246                 else
247                         err = ubifs_tnc_add(c, &r->key, r->lnum, r->offs,
248                                             r->len);
249                 if (err)
250                         return err;
251
252                 if (c->need_recovery)
253                         err = ubifs_recover_size_accum(c, &r->key, r->deletion,
254                                                        r->new_size);
255         }
256
257         return err;
258 }
259
260 /**
261  * replay_entries_cmp - compare 2 replay entries.
262  * @priv: UBIFS file-system description object
263  * @a: first replay entry
264  * @a: second replay entry
265  *
266  * This is a comparios function for 'list_sort()' which compares 2 replay
267  * entries @a and @b by comparing their sequence numer.  Returns %1 if @a has
268  * greater sequence number and %-1 otherwise.
269  */
270 static int replay_entries_cmp(void *priv, struct list_head *a,
271                               struct list_head *b)
272 {
273         struct replay_entry *ra, *rb;
274
275         cond_resched();
276         if (a == b)
277                 return 0;
278
279         ra = list_entry(a, struct replay_entry, list);
280         rb = list_entry(b, struct replay_entry, list);
281         ubifs_assert(ra->sqnum != rb->sqnum);
282         if (ra->sqnum > rb->sqnum)
283                 return 1;
284         return -1;
285 }
286
287 /**
288  * apply_replay_list - apply the replay list to the TNC.
289  * @c: UBIFS file-system description object
290  *
291  * Apply all entries in the replay list to the TNC. Returns zero in case of
292  * success and a negative error code in case of failure.
293  */
294 static int apply_replay_list(struct ubifs_info *c)
295 {
296         struct replay_entry *r;
297         int err;
298
299         list_sort(c, &c->replay_list, &replay_entries_cmp);
300
301         list_for_each_entry(r, &c->replay_list, list) {
302                 cond_resched();
303
304                 err = apply_replay_entry(c, r);
305                 if (err)
306                         return err;
307         }
308
309         return 0;
310 }
311
312 /**
313  * destroy_replay_list - destroy the replay.
314  * @c: UBIFS file-system description object
315  *
316  * Destroy the replay list.
317  */
318 static void destroy_replay_list(struct ubifs_info *c)
319 {
320         struct replay_entry *r, *tmp;
321
322         list_for_each_entry_safe(r, tmp, &c->replay_list, list) {
323                 if (is_hash_key(c, &r->key))
324                         kfree(r->nm.name);
325                 list_del(&r->list);
326                 kfree(r);
327         }
328 }
329
330 /**
331  * insert_node - insert a node to the replay list
332  * @c: UBIFS file-system description object
333  * @lnum: node logical eraseblock number
334  * @offs: node offset
335  * @len: node length
336  * @key: node key
337  * @sqnum: sequence number
338  * @deletion: non-zero if this is a deletion
339  * @used: number of bytes in use in a LEB
340  * @old_size: truncation old size
341  * @new_size: truncation new size
342  *
343  * This function inserts a scanned non-direntry node to the replay list. The
344  * replay list contains @struct replay_entry elements, and we sort this list in
345  * sequence number order before applying it. The replay list is applied at the
346  * very end of the replay process. Since the list is sorted in sequence number
347  * order, the older modifications are applied first. This function returns zero
348  * in case of success and a negative error code in case of failure.
349  */
350 static int insert_node(struct ubifs_info *c, int lnum, int offs, int len,
351                        union ubifs_key *key, unsigned long long sqnum,
352                        int deletion, int *used, loff_t old_size,
353                        loff_t new_size)
354 {
355         struct replay_entry *r;
356
357         dbg_mntk(key, "add LEB %d:%d, key ", lnum, offs);
358
359         if (key_inum(c, key) >= c->highest_inum)
360                 c->highest_inum = key_inum(c, key);
361
362         r = kzalloc(sizeof(struct replay_entry), GFP_KERNEL);
363         if (!r)
364                 return -ENOMEM;
365
366         if (!deletion)
367                 *used += ALIGN(len, 8);
368         r->lnum = lnum;
369         r->offs = offs;
370         r->len = len;
371         r->deletion = !!deletion;
372         r->sqnum = sqnum;
373         key_copy(c, key, &r->key);
374         r->old_size = old_size;
375         r->new_size = new_size;
376
377         list_add_tail(&r->list, &c->replay_list);
378         return 0;
379 }
380
381 /**
382  * insert_dent - insert a directory entry node into the replay list.
383  * @c: UBIFS file-system description object
384  * @lnum: node logical eraseblock number
385  * @offs: node offset
386  * @len: node length
387  * @key: node key
388  * @name: directory entry name
389  * @nlen: directory entry name length
390  * @sqnum: sequence number
391  * @deletion: non-zero if this is a deletion
392  * @used: number of bytes in use in a LEB
393  *
394  * This function inserts a scanned directory entry node or an extended
395  * attribute entry to the replay list. Returns zero in case of success and a
396  * negative error code in case of failure.
397  */
398 static int insert_dent(struct ubifs_info *c, int lnum, int offs, int len,
399                        union ubifs_key *key, const char *name, int nlen,
400                        unsigned long long sqnum, int deletion, int *used)
401 {
402         struct replay_entry *r;
403         char *nbuf;
404
405         dbg_mntk(key, "add LEB %d:%d, key ", lnum, offs);
406         if (key_inum(c, key) >= c->highest_inum)
407                 c->highest_inum = key_inum(c, key);
408
409         r = kzalloc(sizeof(struct replay_entry), GFP_KERNEL);
410         if (!r)
411                 return -ENOMEM;
412
413         nbuf = kmalloc(nlen + 1, GFP_KERNEL);
414         if (!nbuf) {
415                 kfree(r);
416                 return -ENOMEM;
417         }
418
419         if (!deletion)
420                 *used += ALIGN(len, 8);
421         r->lnum = lnum;
422         r->offs = offs;
423         r->len = len;
424         r->deletion = !!deletion;
425         r->sqnum = sqnum;
426         key_copy(c, key, &r->key);
427         r->nm.len = nlen;
428         memcpy(nbuf, name, nlen);
429         nbuf[nlen] = '\0';
430         r->nm.name = nbuf;
431
432         list_add_tail(&r->list, &c->replay_list);
433         return 0;
434 }
435
436 /**
437  * ubifs_validate_entry - validate directory or extended attribute entry node.
438  * @c: UBIFS file-system description object
439  * @dent: the node to validate
440  *
441  * This function validates directory or extended attribute entry node @dent.
442  * Returns zero if the node is all right and a %-EINVAL if not.
443  */
444 int ubifs_validate_entry(struct ubifs_info *c,
445                          const struct ubifs_dent_node *dent)
446 {
447         int key_type = key_type_flash(c, dent->key);
448         int nlen = le16_to_cpu(dent->nlen);
449
450         if (le32_to_cpu(dent->ch.len) != nlen + UBIFS_DENT_NODE_SZ + 1 ||
451             dent->type >= UBIFS_ITYPES_CNT ||
452             nlen > UBIFS_MAX_NLEN || dent->name[nlen] != 0 ||
453             strnlen(dent->name, nlen) != nlen ||
454             le64_to_cpu(dent->inum) > MAX_INUM) {
455                 ubifs_err(c, "bad %s node", key_type == UBIFS_DENT_KEY ?
456                           "directory entry" : "extended attribute entry");
457                 return -EINVAL;
458         }
459
460         if (key_type != UBIFS_DENT_KEY && key_type != UBIFS_XENT_KEY) {
461                 ubifs_err(c, "bad key type %d", key_type);
462                 return -EINVAL;
463         }
464
465         return 0;
466 }
467
468 /**
469  * is_last_bud - check if the bud is the last in the journal head.
470  * @c: UBIFS file-system description object
471  * @bud: bud description object
472  *
473  * This function checks if bud @bud is the last bud in its journal head. This
474  * information is then used by 'replay_bud()' to decide whether the bud can
475  * have corruptions or not. Indeed, only last buds can be corrupted by power
476  * cuts. Returns %1 if this is the last bud, and %0 if not.
477  */
478 static int is_last_bud(struct ubifs_info *c, struct ubifs_bud *bud)
479 {
480         struct ubifs_jhead *jh = &c->jheads[bud->jhead];
481         struct ubifs_bud *next;
482         uint32_t data;
483         int err;
484
485         if (list_is_last(&bud->list, &jh->buds_list))
486                 return 1;
487
488         /*
489          * The following is a quirk to make sure we work correctly with UBIFS
490          * images used with older UBIFS.
491          *
492          * Normally, the last bud will be the last in the journal head's list
493          * of bud. However, there is one exception if the UBIFS image belongs
494          * to older UBIFS. This is fairly unlikely: one would need to use old
495          * UBIFS, then have a power cut exactly at the right point, and then
496          * try to mount this image with new UBIFS.
497          *
498          * The exception is: it is possible to have 2 buds A and B, A goes
499          * before B, and B is the last, bud B is contains no data, and bud A is
500          * corrupted at the end. The reason is that in older versions when the
501          * journal code switched the next bud (from A to B), it first added a
502          * log reference node for the new bud (B), and only after this it
503          * synchronized the write-buffer of current bud (A). But later this was
504          * changed and UBIFS started to always synchronize the write-buffer of
505          * the bud (A) before writing the log reference for the new bud (B).
506          *
507          * But because older UBIFS always synchronized A's write-buffer before
508          * writing to B, we can recognize this exceptional situation but
509          * checking the contents of bud B - if it is empty, then A can be
510          * treated as the last and we can recover it.
511          *
512          * TODO: remove this piece of code in a couple of years (today it is
513          * 16.05.2011).
514          */
515         next = list_entry(bud->list.next, struct ubifs_bud, list);
516         if (!list_is_last(&next->list, &jh->buds_list))
517                 return 0;
518
519         err = ubifs_leb_read(c, next->lnum, (char *)&data, next->start, 4, 1);
520         if (err)
521                 return 0;
522
523         return data == 0xFFFFFFFF;
524 }
525
526 /**
527  * replay_bud - replay a bud logical eraseblock.
528  * @c: UBIFS file-system description object
529  * @b: bud entry which describes the bud
530  *
531  * This function replays bud @bud, recovers it if needed, and adds all nodes
532  * from this bud to the replay list. Returns zero in case of success and a
533  * negative error code in case of failure.
534  */
535 static int replay_bud(struct ubifs_info *c, struct bud_entry *b)
536 {
537         int is_last = is_last_bud(c, b->bud);
538         int err = 0, used = 0, lnum = b->bud->lnum, offs = b->bud->start;
539         struct ubifs_scan_leb *sleb;
540         struct ubifs_scan_node *snod;
541
542         dbg_mnt("replay bud LEB %d, head %d, offs %d, is_last %d",
543                 lnum, b->bud->jhead, offs, is_last);
544
545         if (c->need_recovery && is_last)
546                 /*
547                  * Recover only last LEBs in the journal heads, because power
548                  * cuts may cause corruptions only in these LEBs, because only
549                  * these LEBs could possibly be written to at the power cut
550                  * time.
551                  */
552                 sleb = ubifs_recover_leb(c, lnum, offs, c->sbuf, b->bud->jhead);
553         else
554                 sleb = ubifs_scan(c, lnum, offs, c->sbuf, 0);
555         if (IS_ERR(sleb))
556                 return PTR_ERR(sleb);
557
558         /*
559          * The bud does not have to start from offset zero - the beginning of
560          * the 'lnum' LEB may contain previously committed data. One of the
561          * things we have to do in replay is to correctly update lprops with
562          * newer information about this LEB.
563          *
564          * At this point lprops thinks that this LEB has 'c->leb_size - offs'
565          * bytes of free space because it only contain information about
566          * committed data.
567          *
568          * But we know that real amount of free space is 'c->leb_size -
569          * sleb->endpt', and the space in the 'lnum' LEB between 'offs' and
570          * 'sleb->endpt' is used by bud data. We have to correctly calculate
571          * how much of these data are dirty and update lprops with this
572          * information.
573          *
574          * The dirt in that LEB region is comprised of padding nodes, deletion
575          * nodes, truncation nodes and nodes which are obsoleted by subsequent
576          * nodes in this LEB. So instead of calculating clean space, we
577          * calculate used space ('used' variable).
578          */
579
580         list_for_each_entry(snod, &sleb->nodes, list) {
581                 int deletion = 0;
582
583                 cond_resched();
584
585                 if (snod->sqnum >= SQNUM_WATERMARK) {
586                         ubifs_err(c, "file system's life ended");
587                         goto out_dump;
588                 }
589
590                 if (snod->sqnum > c->max_sqnum)
591                         c->max_sqnum = snod->sqnum;
592
593                 switch (snod->type) {
594                 case UBIFS_INO_NODE:
595                 {
596                         struct ubifs_ino_node *ino = snod->node;
597                         loff_t new_size = le64_to_cpu(ino->size);
598
599                         if (le32_to_cpu(ino->nlink) == 0)
600                                 deletion = 1;
601                         err = insert_node(c, lnum, snod->offs, snod->len,
602                                           &snod->key, snod->sqnum, deletion,
603                                           &used, 0, new_size);
604                         break;
605                 }
606                 case UBIFS_DATA_NODE:
607                 {
608                         struct ubifs_data_node *dn = snod->node;
609                         loff_t new_size = le32_to_cpu(dn->size) +
610                                           key_block(c, &snod->key) *
611                                           UBIFS_BLOCK_SIZE;
612
613                         err = insert_node(c, lnum, snod->offs, snod->len,
614                                           &snod->key, snod->sqnum, deletion,
615                                           &used, 0, new_size);
616                         break;
617                 }
618                 case UBIFS_DENT_NODE:
619                 case UBIFS_XENT_NODE:
620                 {
621                         struct ubifs_dent_node *dent = snod->node;
622
623                         err = ubifs_validate_entry(c, dent);
624                         if (err)
625                                 goto out_dump;
626
627                         err = insert_dent(c, lnum, snod->offs, snod->len,
628                                           &snod->key, dent->name,
629                                           le16_to_cpu(dent->nlen), snod->sqnum,
630                                           !le64_to_cpu(dent->inum), &used);
631                         break;
632                 }
633                 case UBIFS_TRUN_NODE:
634                 {
635                         struct ubifs_trun_node *trun = snod->node;
636                         loff_t old_size = le64_to_cpu(trun->old_size);
637                         loff_t new_size = le64_to_cpu(trun->new_size);
638                         union ubifs_key key;
639
640                         /* Validate truncation node */
641                         if (old_size < 0 || old_size > c->max_inode_sz ||
642                             new_size < 0 || new_size > c->max_inode_sz ||
643                             old_size <= new_size) {
644                                 ubifs_err(c, "bad truncation node");
645                                 goto out_dump;
646                         }
647
648                         /*
649                          * Create a fake truncation key just to use the same
650                          * functions which expect nodes to have keys.
651                          */
652                         trun_key_init(c, &key, le32_to_cpu(trun->inum));
653                         err = insert_node(c, lnum, snod->offs, snod->len,
654                                           &key, snod->sqnum, 1, &used,
655                                           old_size, new_size);
656                         break;
657                 }
658                 default:
659                         ubifs_err(c, "unexpected node type %d in bud LEB %d:%d",
660                                   snod->type, lnum, snod->offs);
661                         err = -EINVAL;
662                         goto out_dump;
663                 }
664                 if (err)
665                         goto out;
666         }
667
668         ubifs_assert(ubifs_search_bud(c, lnum));
669         ubifs_assert(sleb->endpt - offs >= used);
670         ubifs_assert(sleb->endpt % c->min_io_size == 0);
671
672         b->dirty = sleb->endpt - offs - used;
673         b->free = c->leb_size - sleb->endpt;
674         dbg_mnt("bud LEB %d replied: dirty %d, free %d",
675                 lnum, b->dirty, b->free);
676
677 out:
678         ubifs_scan_destroy(sleb);
679         return err;
680
681 out_dump:
682         ubifs_err(c, "bad node is at LEB %d:%d", lnum, snod->offs);
683         ubifs_dump_node(c, snod->node);
684         ubifs_scan_destroy(sleb);
685         return -EINVAL;
686 }
687
688 /**
689  * replay_buds - replay all buds.
690  * @c: UBIFS file-system description object
691  *
692  * This function returns zero in case of success and a negative error code in
693  * case of failure.
694  */
695 static int replay_buds(struct ubifs_info *c)
696 {
697         struct bud_entry *b;
698         int err;
699         unsigned long long prev_sqnum = 0;
700
701         list_for_each_entry(b, &c->replay_buds, list) {
702                 err = replay_bud(c, b);
703                 if (err)
704                         return err;
705
706                 ubifs_assert(b->sqnum > prev_sqnum);
707                 prev_sqnum = b->sqnum;
708         }
709
710         return 0;
711 }
712
713 /**
714  * destroy_bud_list - destroy the list of buds to replay.
715  * @c: UBIFS file-system description object
716  */
717 static void destroy_bud_list(struct ubifs_info *c)
718 {
719         struct bud_entry *b;
720
721         while (!list_empty(&c->replay_buds)) {
722                 b = list_entry(c->replay_buds.next, struct bud_entry, list);
723                 list_del(&b->list);
724                 kfree(b);
725         }
726 }
727
728 /**
729  * add_replay_bud - add a bud to the list of buds to replay.
730  * @c: UBIFS file-system description object
731  * @lnum: bud logical eraseblock number to replay
732  * @offs: bud start offset
733  * @jhead: journal head to which this bud belongs
734  * @sqnum: reference node sequence number
735  *
736  * This function returns zero in case of success and a negative error code in
737  * case of failure.
738  */
739 static int add_replay_bud(struct ubifs_info *c, int lnum, int offs, int jhead,
740                           unsigned long long sqnum)
741 {
742         struct ubifs_bud *bud;
743         struct bud_entry *b;
744
745         dbg_mnt("add replay bud LEB %d:%d, head %d", lnum, offs, jhead);
746
747         bud = kmalloc(sizeof(struct ubifs_bud), GFP_KERNEL);
748         if (!bud)
749                 return -ENOMEM;
750
751         b = kmalloc(sizeof(struct bud_entry), GFP_KERNEL);
752         if (!b) {
753                 kfree(bud);
754                 return -ENOMEM;
755         }
756
757         bud->lnum = lnum;
758         bud->start = offs;
759         bud->jhead = jhead;
760         ubifs_add_bud(c, bud);
761
762         b->bud = bud;
763         b->sqnum = sqnum;
764         list_add_tail(&b->list, &c->replay_buds);
765
766         return 0;
767 }
768
769 /**
770  * validate_ref - validate a reference node.
771  * @c: UBIFS file-system description object
772  * @ref: the reference node to validate
773  * @ref_lnum: LEB number of the reference node
774  * @ref_offs: reference node offset
775  *
776  * This function returns %1 if a bud reference already exists for the LEB. %0 is
777  * returned if the reference node is new, otherwise %-EINVAL is returned if
778  * validation failed.
779  */
780 static int validate_ref(struct ubifs_info *c, const struct ubifs_ref_node *ref)
781 {
782         struct ubifs_bud *bud;
783         int lnum = le32_to_cpu(ref->lnum);
784         unsigned int offs = le32_to_cpu(ref->offs);
785         unsigned int jhead = le32_to_cpu(ref->jhead);
786
787         /*
788          * ref->offs may point to the end of LEB when the journal head points
789          * to the end of LEB and we write reference node for it during commit.
790          * So this is why we require 'offs > c->leb_size'.
791          */
792         if (jhead >= c->jhead_cnt || lnum >= c->leb_cnt ||
793             lnum < c->main_first || offs > c->leb_size ||
794             offs & (c->min_io_size - 1))
795                 return -EINVAL;
796
797         /* Make sure we have not already looked at this bud */
798         bud = ubifs_search_bud(c, lnum);
799         if (bud) {
800                 if (bud->jhead == jhead && bud->start <= offs)
801                         return 1;
802                 ubifs_err(c, "bud at LEB %d:%d was already referred", lnum, offs);
803                 return -EINVAL;
804         }
805
806         return 0;
807 }
808
809 /**
810  * replay_log_leb - replay a log logical eraseblock.
811  * @c: UBIFS file-system description object
812  * @lnum: log logical eraseblock to replay
813  * @offs: offset to start replaying from
814  * @sbuf: scan buffer
815  *
816  * This function replays a log LEB and returns zero in case of success, %1 if
817  * this is the last LEB in the log, and a negative error code in case of
818  * failure.
819  */
820 static int replay_log_leb(struct ubifs_info *c, int lnum, int offs, void *sbuf)
821 {
822         int err;
823         struct ubifs_scan_leb *sleb;
824         struct ubifs_scan_node *snod;
825         const struct ubifs_cs_node *node;
826
827         dbg_mnt("replay log LEB %d:%d", lnum, offs);
828         sleb = ubifs_scan(c, lnum, offs, sbuf, c->need_recovery);
829         if (IS_ERR(sleb)) {
830                 if (PTR_ERR(sleb) != -EUCLEAN || !c->need_recovery)
831                         return PTR_ERR(sleb);
832                 /*
833                  * Note, the below function will recover this log LEB only if
834                  * it is the last, because unclean reboots can possibly corrupt
835                  * only the tail of the log.
836                  */
837                 sleb = ubifs_recover_log_leb(c, lnum, offs, sbuf);
838                 if (IS_ERR(sleb))
839                         return PTR_ERR(sleb);
840         }
841
842         if (sleb->nodes_cnt == 0) {
843                 err = 1;
844                 goto out;
845         }
846
847         node = sleb->buf;
848         snod = list_entry(sleb->nodes.next, struct ubifs_scan_node, list);
849         if (c->cs_sqnum == 0) {
850                 /*
851                  * This is the first log LEB we are looking at, make sure that
852                  * the first node is a commit start node. Also record its
853                  * sequence number so that UBIFS can determine where the log
854                  * ends, because all nodes which were have higher sequence
855                  * numbers.
856                  */
857                 if (snod->type != UBIFS_CS_NODE) {
858                         ubifs_err(c, "first log node at LEB %d:%d is not CS node",
859                                   lnum, offs);
860                         goto out_dump;
861                 }
862                 if (le64_to_cpu(node->cmt_no) != c->cmt_no) {
863                         ubifs_err(c, "first CS node at LEB %d:%d has wrong commit number %llu expected %llu",
864                                   lnum, offs,
865                                   (unsigned long long)le64_to_cpu(node->cmt_no),
866                                   c->cmt_no);
867                         goto out_dump;
868                 }
869
870                 c->cs_sqnum = le64_to_cpu(node->ch.sqnum);
871                 dbg_mnt("commit start sqnum %llu", c->cs_sqnum);
872         }
873
874         if (snod->sqnum < c->cs_sqnum) {
875                 /*
876                  * This means that we reached end of log and now
877                  * look to the older log data, which was already
878                  * committed but the eraseblock was not erased (UBIFS
879                  * only un-maps it). So this basically means we have to
880                  * exit with "end of log" code.
881                  */
882                 err = 1;
883                 goto out;
884         }
885
886         /* Make sure the first node sits at offset zero of the LEB */
887         if (snod->offs != 0) {
888                 ubifs_err(c, "first node is not at zero offset");
889                 goto out_dump;
890         }
891
892         list_for_each_entry(snod, &sleb->nodes, list) {
893                 cond_resched();
894
895                 if (snod->sqnum >= SQNUM_WATERMARK) {
896                         ubifs_err(c, "file system's life ended");
897                         goto out_dump;
898                 }
899
900                 if (snod->sqnum < c->cs_sqnum) {
901                         ubifs_err(c, "bad sqnum %llu, commit sqnum %llu",
902                                   snod->sqnum, c->cs_sqnum);
903                         goto out_dump;
904                 }
905
906                 if (snod->sqnum > c->max_sqnum)
907                         c->max_sqnum = snod->sqnum;
908
909                 switch (snod->type) {
910                 case UBIFS_REF_NODE: {
911                         const struct ubifs_ref_node *ref = snod->node;
912
913                         err = validate_ref(c, ref);
914                         if (err == 1)
915                                 break; /* Already have this bud */
916                         if (err)
917                                 goto out_dump;
918
919                         err = add_replay_bud(c, le32_to_cpu(ref->lnum),
920                                              le32_to_cpu(ref->offs),
921                                              le32_to_cpu(ref->jhead),
922                                              snod->sqnum);
923                         if (err)
924                                 goto out;
925
926                         break;
927                 }
928                 case UBIFS_CS_NODE:
929                         /* Make sure it sits at the beginning of LEB */
930                         if (snod->offs != 0) {
931                                 ubifs_err(c, "unexpected node in log");
932                                 goto out_dump;
933                         }
934                         break;
935                 default:
936                         ubifs_err(c, "unexpected node in log");
937                         goto out_dump;
938                 }
939         }
940
941         if (sleb->endpt || c->lhead_offs >= c->leb_size) {
942                 c->lhead_lnum = lnum;
943                 c->lhead_offs = sleb->endpt;
944         }
945
946         err = !sleb->endpt;
947 out:
948         ubifs_scan_destroy(sleb);
949         return err;
950
951 out_dump:
952         ubifs_err(c, "log error detected while replaying the log at LEB %d:%d",
953                   lnum, offs + snod->offs);
954         ubifs_dump_node(c, snod->node);
955         ubifs_scan_destroy(sleb);
956         return -EINVAL;
957 }
958
959 /**
960  * take_ihead - update the status of the index head in lprops to 'taken'.
961  * @c: UBIFS file-system description object
962  *
963  * This function returns the amount of free space in the index head LEB or a
964  * negative error code.
965  */
966 static int take_ihead(struct ubifs_info *c)
967 {
968         const struct ubifs_lprops *lp;
969         int err, free;
970
971         ubifs_get_lprops(c);
972
973         lp = ubifs_lpt_lookup_dirty(c, c->ihead_lnum);
974         if (IS_ERR(lp)) {
975                 err = PTR_ERR(lp);
976                 goto out;
977         }
978
979         free = lp->free;
980
981         lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,
982                              lp->flags | LPROPS_TAKEN, 0);
983         if (IS_ERR(lp)) {
984                 err = PTR_ERR(lp);
985                 goto out;
986         }
987
988         err = free;
989 out:
990         ubifs_release_lprops(c);
991         return err;
992 }
993
994 /**
995  * ubifs_replay_journal - replay journal.
996  * @c: UBIFS file-system description object
997  *
998  * This function scans the journal, replays and cleans it up. It makes sure all
999  * memory data structures related to uncommitted journal are built (dirty TNC
1000  * tree, tree of buds, modified lprops, etc).
1001  */
1002 int ubifs_replay_journal(struct ubifs_info *c)
1003 {
1004         int err, lnum, free;
1005
1006         BUILD_BUG_ON(UBIFS_TRUN_KEY > 5);
1007
1008         /* Update the status of the index head in lprops to 'taken' */
1009         free = take_ihead(c);
1010         if (free < 0)
1011                 return free; /* Error code */
1012
1013         if (c->ihead_offs != c->leb_size - free) {
1014                 ubifs_err(c, "bad index head LEB %d:%d", c->ihead_lnum,
1015                           c->ihead_offs);
1016                 return -EINVAL;
1017         }
1018
1019         dbg_mnt("start replaying the journal");
1020         c->replaying = 1;
1021         lnum = c->ltail_lnum = c->lhead_lnum;
1022
1023         do {
1024                 err = replay_log_leb(c, lnum, 0, c->sbuf);
1025                 if (err == 1) {
1026                         if (lnum != c->lhead_lnum)
1027                                 /* We hit the end of the log */
1028                                 break;
1029
1030                         /*
1031                          * The head of the log must always start with the
1032                          * "commit start" node on a properly formatted UBIFS.
1033                          * But we found no nodes at all, which means that
1034                          * someting went wrong and we cannot proceed mounting
1035                          * the file-system.
1036                          */
1037                         ubifs_err(c, "no UBIFS nodes found at the log head LEB %d:%d, possibly corrupted",
1038                                   lnum, 0);
1039                         err = -EINVAL;
1040                 }
1041                 if (err)
1042                         goto out;
1043                 lnum = ubifs_next_log_lnum(c, lnum);
1044         } while (lnum != c->ltail_lnum);
1045
1046         err = replay_buds(c);
1047         if (err)
1048                 goto out;
1049
1050         err = apply_replay_list(c);
1051         if (err)
1052                 goto out;
1053
1054         err = set_buds_lprops(c);
1055         if (err)
1056                 goto out;
1057
1058         /*
1059          * UBIFS budgeting calculations use @c->bi.uncommitted_idx variable
1060          * to roughly estimate index growth. Things like @c->bi.min_idx_lebs
1061          * depend on it. This means we have to initialize it to make sure
1062          * budgeting works properly.
1063          */
1064         c->bi.uncommitted_idx = atomic_long_read(&c->dirty_zn_cnt);
1065         c->bi.uncommitted_idx *= c->max_idx_node_sz;
1066
1067         ubifs_assert(c->bud_bytes <= c->max_bud_bytes || c->need_recovery);
1068         dbg_mnt("finished, log head LEB %d:%d, max_sqnum %llu, highest_inum %lu",
1069                 c->lhead_lnum, c->lhead_offs, c->max_sqnum,
1070                 (unsigned long)c->highest_inum);
1071 out:
1072         destroy_replay_list(c);
1073         destroy_bud_list(c);
1074         c->replaying = 0;
1075         return err;
1076 }