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