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