1 // SPDX-License-Identifier: GPL-2.0-only
2 /*
3  * This file is part of UBIFS.
4  *
5  * Copyright (C) 2006-2008 Nokia Corporation.
6  *
7  * Authors: Adrian Hunter
8  *          Artem Bityutskiy (Битюцкий Артём)
9  */
10 
11 /*
12  * This file implements commit-related functionality of the LEB properties
13  * subsystem.
14  */
15 
16 #include <linux/crc16.h>
17 #include <linux/slab.h>
18 #include <linux/random.h>
19 #include "ubifs.h"
20 
21 static int dbg_populate_lsave(struct ubifs_info *c);
22 
23 /**
24  * first_dirty_cnode - find first dirty cnode.
25  * @c: UBIFS file-system description object
26  * @nnode: nnode at which to start
27  *
28  * This function returns the first dirty cnode or %NULL if there is not one.
29  */
first_dirty_cnode(const struct ubifs_info * c,struct ubifs_nnode * nnode)30 static struct ubifs_cnode *first_dirty_cnode(const struct ubifs_info *c, struct ubifs_nnode *nnode)
31 {
32 	ubifs_assert(c, nnode);
33 	while (1) {
34 		int i, cont = 0;
35 
36 		for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
37 			struct ubifs_cnode *cnode;
38 
39 			cnode = nnode->nbranch[i].cnode;
40 			if (cnode &&
41 			    test_bit(DIRTY_CNODE, &cnode->flags)) {
42 				if (cnode->level == 0)
43 					return cnode;
44 				nnode = (struct ubifs_nnode *)cnode;
45 				cont = 1;
46 				break;
47 			}
48 		}
49 		if (!cont)
50 			return (struct ubifs_cnode *)nnode;
51 	}
52 }
53 
54 /**
55  * next_dirty_cnode - find next dirty cnode.
56  * @c: UBIFS file-system description object
57  * @cnode: cnode from which to begin searching
58  *
59  * This function returns the next dirty cnode or %NULL if there is not one.
60  */
next_dirty_cnode(const struct ubifs_info * c,struct ubifs_cnode * cnode)61 static struct ubifs_cnode *next_dirty_cnode(const struct ubifs_info *c, struct ubifs_cnode *cnode)
62 {
63 	struct ubifs_nnode *nnode;
64 	int i;
65 
66 	ubifs_assert(c, cnode);
67 	nnode = cnode->parent;
68 	if (!nnode)
69 		return NULL;
70 	for (i = cnode->iip + 1; i < UBIFS_LPT_FANOUT; i++) {
71 		cnode = nnode->nbranch[i].cnode;
72 		if (cnode && test_bit(DIRTY_CNODE, &cnode->flags)) {
73 			if (cnode->level == 0)
74 				return cnode; /* cnode is a pnode */
75 			/* cnode is a nnode */
76 			return first_dirty_cnode(c, (struct ubifs_nnode *)cnode);
77 		}
78 	}
79 	return (struct ubifs_cnode *)nnode;
80 }
81 
82 /**
83  * get_cnodes_to_commit - create list of dirty cnodes to commit.
84  * @c: UBIFS file-system description object
85  *
86  * This function returns the number of cnodes to commit.
87  */
get_cnodes_to_commit(struct ubifs_info * c)88 static int get_cnodes_to_commit(struct ubifs_info *c)
89 {
90 	struct ubifs_cnode *cnode, *cnext;
91 	int cnt = 0;
92 
93 	if (!c->nroot)
94 		return 0;
95 
96 	if (!test_bit(DIRTY_CNODE, &c->nroot->flags))
97 		return 0;
98 
99 	c->lpt_cnext = first_dirty_cnode(c, c->nroot);
100 	cnode = c->lpt_cnext;
101 	if (!cnode)
102 		return 0;
103 	cnt += 1;
104 	while (1) {
105 		ubifs_assert(c, !test_bit(COW_CNODE, &cnode->flags));
106 		__set_bit(COW_CNODE, &cnode->flags);
107 		cnext = next_dirty_cnode(c, cnode);
108 		if (!cnext) {
109 			cnode->cnext = c->lpt_cnext;
110 			break;
111 		}
112 		cnode->cnext = cnext;
113 		cnode = cnext;
114 		cnt += 1;
115 	}
116 	dbg_cmt("committing %d cnodes", cnt);
117 	dbg_lp("committing %d cnodes", cnt);
118 	ubifs_assert(c, cnt == c->dirty_nn_cnt + c->dirty_pn_cnt);
119 	return cnt;
120 }
121 
122 /**
123  * upd_ltab - update LPT LEB properties.
124  * @c: UBIFS file-system description object
125  * @lnum: LEB number
126  * @free: amount of free space
127  * @dirty: amount of dirty space to add
128  */
upd_ltab(struct ubifs_info * c,int lnum,int free,int dirty)129 static void upd_ltab(struct ubifs_info *c, int lnum, int free, int dirty)
130 {
131 	dbg_lp("LEB %d free %d dirty %d to %d +%d",
132 	       lnum, c->ltab[lnum - c->lpt_first].free,
133 	       c->ltab[lnum - c->lpt_first].dirty, free, dirty);
134 	ubifs_assert(c, lnum >= c->lpt_first && lnum <= c->lpt_last);
135 	c->ltab[lnum - c->lpt_first].free = free;
136 	c->ltab[lnum - c->lpt_first].dirty += dirty;
137 }
138 
139 /**
140  * alloc_lpt_leb - allocate an LPT LEB that is empty.
141  * @c: UBIFS file-system description object
142  * @lnum: LEB number is passed and returned here
143  *
144  * This function finds the next empty LEB in the ltab starting from @lnum. If a
145  * an empty LEB is found it is returned in @lnum and the function returns %0.
146  * Otherwise the function returns -ENOSPC.  Note however, that LPT is designed
147  * never to run out of space.
148  */
alloc_lpt_leb(struct ubifs_info * c,int * lnum)149 static int alloc_lpt_leb(struct ubifs_info *c, int *lnum)
150 {
151 	int i, n;
152 
153 	n = *lnum - c->lpt_first + 1;
154 	for (i = n; i < c->lpt_lebs; i++) {
155 		if (c->ltab[i].tgc || c->ltab[i].cmt)
156 			continue;
157 		if (c->ltab[i].free == c->leb_size) {
158 			c->ltab[i].cmt = 1;
159 			*lnum = i + c->lpt_first;
160 			return 0;
161 		}
162 	}
163 
164 	for (i = 0; i < n; i++) {
165 		if (c->ltab[i].tgc || c->ltab[i].cmt)
166 			continue;
167 		if (c->ltab[i].free == c->leb_size) {
168 			c->ltab[i].cmt = 1;
169 			*lnum = i + c->lpt_first;
170 			return 0;
171 		}
172 	}
173 	return -ENOSPC;
174 }
175 
176 /**
177  * layout_cnodes - layout cnodes for commit.
178  * @c: UBIFS file-system description object
179  *
180  * This function returns %0 on success and a negative error code on failure.
181  */
layout_cnodes(struct ubifs_info * c)182 static int layout_cnodes(struct ubifs_info *c)
183 {
184 	int lnum, offs, len, alen, done_lsave, done_ltab, err;
185 	struct ubifs_cnode *cnode;
186 
187 	err = dbg_chk_lpt_sz(c, 0, 0);
188 	if (err)
189 		return err;
190 	cnode = c->lpt_cnext;
191 	if (!cnode)
192 		return 0;
193 	lnum = c->nhead_lnum;
194 	offs = c->nhead_offs;
195 	/* Try to place lsave and ltab nicely */
196 	done_lsave = !c->big_lpt;
197 	done_ltab = 0;
198 	if (!done_lsave && offs + c->lsave_sz <= c->leb_size) {
199 		done_lsave = 1;
200 		c->lsave_lnum = lnum;
201 		c->lsave_offs = offs;
202 		offs += c->lsave_sz;
203 		dbg_chk_lpt_sz(c, 1, c->lsave_sz);
204 	}
205 
206 	if (offs + c->ltab_sz <= c->leb_size) {
207 		done_ltab = 1;
208 		c->ltab_lnum = lnum;
209 		c->ltab_offs = offs;
210 		offs += c->ltab_sz;
211 		dbg_chk_lpt_sz(c, 1, c->ltab_sz);
212 	}
213 
214 	do {
215 		if (cnode->level) {
216 			len = c->nnode_sz;
217 			c->dirty_nn_cnt -= 1;
218 		} else {
219 			len = c->pnode_sz;
220 			c->dirty_pn_cnt -= 1;
221 		}
222 		while (offs + len > c->leb_size) {
223 			alen = ALIGN(offs, c->min_io_size);
224 			upd_ltab(c, lnum, c->leb_size - alen, alen - offs);
225 			dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
226 			err = alloc_lpt_leb(c, &lnum);
227 			if (err)
228 				goto no_space;
229 			offs = 0;
230 			ubifs_assert(c, lnum >= c->lpt_first &&
231 				     lnum <= c->lpt_last);
232 			/* Try to place lsave and ltab nicely */
233 			if (!done_lsave) {
234 				done_lsave = 1;
235 				c->lsave_lnum = lnum;
236 				c->lsave_offs = offs;
237 				offs += c->lsave_sz;
238 				dbg_chk_lpt_sz(c, 1, c->lsave_sz);
239 				continue;
240 			}
241 			if (!done_ltab) {
242 				done_ltab = 1;
243 				c->ltab_lnum = lnum;
244 				c->ltab_offs = offs;
245 				offs += c->ltab_sz;
246 				dbg_chk_lpt_sz(c, 1, c->ltab_sz);
247 				continue;
248 			}
249 			break;
250 		}
251 		if (cnode->parent) {
252 			cnode->parent->nbranch[cnode->iip].lnum = lnum;
253 			cnode->parent->nbranch[cnode->iip].offs = offs;
254 		} else {
255 			c->lpt_lnum = lnum;
256 			c->lpt_offs = offs;
257 		}
258 		offs += len;
259 		dbg_chk_lpt_sz(c, 1, len);
260 		cnode = cnode->cnext;
261 	} while (cnode && cnode != c->lpt_cnext);
262 
263 	/* Make sure to place LPT's save table */
264 	if (!done_lsave) {
265 		if (offs + c->lsave_sz > c->leb_size) {
266 			alen = ALIGN(offs, c->min_io_size);
267 			upd_ltab(c, lnum, c->leb_size - alen, alen - offs);
268 			dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
269 			err = alloc_lpt_leb(c, &lnum);
270 			if (err)
271 				goto no_space;
272 			offs = 0;
273 			ubifs_assert(c, lnum >= c->lpt_first &&
274 				     lnum <= c->lpt_last);
275 		}
276 		done_lsave = 1;
277 		c->lsave_lnum = lnum;
278 		c->lsave_offs = offs;
279 		offs += c->lsave_sz;
280 		dbg_chk_lpt_sz(c, 1, c->lsave_sz);
281 	}
282 
283 	/* Make sure to place LPT's own lprops table */
284 	if (!done_ltab) {
285 		if (offs + c->ltab_sz > c->leb_size) {
286 			alen = ALIGN(offs, c->min_io_size);
287 			upd_ltab(c, lnum, c->leb_size - alen, alen - offs);
288 			dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
289 			err = alloc_lpt_leb(c, &lnum);
290 			if (err)
291 				goto no_space;
292 			offs = 0;
293 			ubifs_assert(c, lnum >= c->lpt_first &&
294 				     lnum <= c->lpt_last);
295 		}
296 		c->ltab_lnum = lnum;
297 		c->ltab_offs = offs;
298 		offs += c->ltab_sz;
299 		dbg_chk_lpt_sz(c, 1, c->ltab_sz);
300 	}
301 
302 	alen = ALIGN(offs, c->min_io_size);
303 	upd_ltab(c, lnum, c->leb_size - alen, alen - offs);
304 	dbg_chk_lpt_sz(c, 4, alen - offs);
305 	err = dbg_chk_lpt_sz(c, 3, alen);
306 	if (err)
307 		return err;
308 	return 0;
309 
310 no_space:
311 	ubifs_err(c, "LPT out of space at LEB %d:%d needing %d, done_ltab %d, done_lsave %d",
312 		  lnum, offs, len, done_ltab, done_lsave);
313 	ubifs_dump_lpt_info(c);
314 	ubifs_dump_lpt_lebs(c);
315 	dump_stack();
316 	return err;
317 }
318 
319 /**
320  * realloc_lpt_leb - allocate an LPT LEB that is empty.
321  * @c: UBIFS file-system description object
322  * @lnum: LEB number is passed and returned here
323  *
324  * This function duplicates exactly the results of the function alloc_lpt_leb.
325  * It is used during end commit to reallocate the same LEB numbers that were
326  * allocated by alloc_lpt_leb during start commit.
327  *
328  * This function finds the next LEB that was allocated by the alloc_lpt_leb
329  * function starting from @lnum. If a LEB is found it is returned in @lnum and
330  * the function returns %0. Otherwise the function returns -ENOSPC.
331  * Note however, that LPT is designed never to run out of space.
332  */
realloc_lpt_leb(struct ubifs_info * c,int * lnum)333 static int realloc_lpt_leb(struct ubifs_info *c, int *lnum)
334 {
335 	int i, n;
336 
337 	n = *lnum - c->lpt_first + 1;
338 	for (i = n; i < c->lpt_lebs; i++)
339 		if (c->ltab[i].cmt) {
340 			c->ltab[i].cmt = 0;
341 			*lnum = i + c->lpt_first;
342 			return 0;
343 		}
344 
345 	for (i = 0; i < n; i++)
346 		if (c->ltab[i].cmt) {
347 			c->ltab[i].cmt = 0;
348 			*lnum = i + c->lpt_first;
349 			return 0;
350 		}
351 	return -ENOSPC;
352 }
353 
354 /**
355  * write_cnodes - write cnodes for commit.
356  * @c: UBIFS file-system description object
357  *
358  * This function returns %0 on success and a negative error code on failure.
359  */
write_cnodes(struct ubifs_info * c)360 static int write_cnodes(struct ubifs_info *c)
361 {
362 	int lnum, offs, len, from, err, wlen, alen, done_ltab, done_lsave;
363 	struct ubifs_cnode *cnode;
364 	void *buf = c->lpt_buf;
365 
366 	cnode = c->lpt_cnext;
367 	if (!cnode)
368 		return 0;
369 	lnum = c->nhead_lnum;
370 	offs = c->nhead_offs;
371 	from = offs;
372 	/* Ensure empty LEB is unmapped */
373 	if (offs == 0) {
374 		err = ubifs_leb_unmap(c, lnum);
375 		if (err)
376 			return err;
377 	}
378 	/* Try to place lsave and ltab nicely */
379 	done_lsave = !c->big_lpt;
380 	done_ltab = 0;
381 	if (!done_lsave && offs + c->lsave_sz <= c->leb_size) {
382 		done_lsave = 1;
383 		ubifs_pack_lsave(c, buf + offs, c->lsave);
384 		offs += c->lsave_sz;
385 		dbg_chk_lpt_sz(c, 1, c->lsave_sz);
386 	}
387 
388 	if (offs + c->ltab_sz <= c->leb_size) {
389 		done_ltab = 1;
390 		ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);
391 		offs += c->ltab_sz;
392 		dbg_chk_lpt_sz(c, 1, c->ltab_sz);
393 	}
394 
395 	/* Loop for each cnode */
396 	do {
397 		if (cnode->level)
398 			len = c->nnode_sz;
399 		else
400 			len = c->pnode_sz;
401 		while (offs + len > c->leb_size) {
402 			wlen = offs - from;
403 			if (wlen) {
404 				alen = ALIGN(wlen, c->min_io_size);
405 				memset(buf + offs, 0xff, alen - wlen);
406 				err = ubifs_leb_write(c, lnum, buf + from, from,
407 						       alen);
408 				if (err)
409 					return err;
410 			}
411 			dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
412 			err = realloc_lpt_leb(c, &lnum);
413 			if (err)
414 				goto no_space;
415 			offs = from = 0;
416 			ubifs_assert(c, lnum >= c->lpt_first &&
417 				     lnum <= c->lpt_last);
418 			err = ubifs_leb_unmap(c, lnum);
419 			if (err)
420 				return err;
421 			/* Try to place lsave and ltab nicely */
422 			if (!done_lsave) {
423 				done_lsave = 1;
424 				ubifs_pack_lsave(c, buf + offs, c->lsave);
425 				offs += c->lsave_sz;
426 				dbg_chk_lpt_sz(c, 1, c->lsave_sz);
427 				continue;
428 			}
429 			if (!done_ltab) {
430 				done_ltab = 1;
431 				ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);
432 				offs += c->ltab_sz;
433 				dbg_chk_lpt_sz(c, 1, c->ltab_sz);
434 				continue;
435 			}
436 			break;
437 		}
438 		if (cnode->level)
439 			ubifs_pack_nnode(c, buf + offs,
440 					 (struct ubifs_nnode *)cnode);
441 		else
442 			ubifs_pack_pnode(c, buf + offs,
443 					 (struct ubifs_pnode *)cnode);
444 		/*
445 		 * The reason for the barriers is the same as in case of TNC.
446 		 * See comment in 'write_index()'. 'dirty_cow_nnode()' and
447 		 * 'dirty_cow_pnode()' are the functions for which this is
448 		 * important.
449 		 */
450 		clear_bit(DIRTY_CNODE, &cnode->flags);
451 		smp_mb__before_atomic();
452 		clear_bit(COW_CNODE, &cnode->flags);
453 		smp_mb__after_atomic();
454 		offs += len;
455 		dbg_chk_lpt_sz(c, 1, len);
456 		cnode = cnode->cnext;
457 	} while (cnode && cnode != c->lpt_cnext);
458 
459 	/* Make sure to place LPT's save table */
460 	if (!done_lsave) {
461 		if (offs + c->lsave_sz > c->leb_size) {
462 			wlen = offs - from;
463 			alen = ALIGN(wlen, c->min_io_size);
464 			memset(buf + offs, 0xff, alen - wlen);
465 			err = ubifs_leb_write(c, lnum, buf + from, from, alen);
466 			if (err)
467 				return err;
468 			dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
469 			err = realloc_lpt_leb(c, &lnum);
470 			if (err)
471 				goto no_space;
472 			offs = from = 0;
473 			ubifs_assert(c, lnum >= c->lpt_first &&
474 				     lnum <= c->lpt_last);
475 			err = ubifs_leb_unmap(c, lnum);
476 			if (err)
477 				return err;
478 		}
479 		done_lsave = 1;
480 		ubifs_pack_lsave(c, buf + offs, c->lsave);
481 		offs += c->lsave_sz;
482 		dbg_chk_lpt_sz(c, 1, c->lsave_sz);
483 	}
484 
485 	/* Make sure to place LPT's own lprops table */
486 	if (!done_ltab) {
487 		if (offs + c->ltab_sz > c->leb_size) {
488 			wlen = offs - from;
489 			alen = ALIGN(wlen, c->min_io_size);
490 			memset(buf + offs, 0xff, alen - wlen);
491 			err = ubifs_leb_write(c, lnum, buf + from, from, alen);
492 			if (err)
493 				return err;
494 			dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
495 			err = realloc_lpt_leb(c, &lnum);
496 			if (err)
497 				goto no_space;
498 			offs = from = 0;
499 			ubifs_assert(c, lnum >= c->lpt_first &&
500 				     lnum <= c->lpt_last);
501 			err = ubifs_leb_unmap(c, lnum);
502 			if (err)
503 				return err;
504 		}
505 		ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);
506 		offs += c->ltab_sz;
507 		dbg_chk_lpt_sz(c, 1, c->ltab_sz);
508 	}
509 
510 	/* Write remaining data in buffer */
511 	wlen = offs - from;
512 	alen = ALIGN(wlen, c->min_io_size);
513 	memset(buf + offs, 0xff, alen - wlen);
514 	err = ubifs_leb_write(c, lnum, buf + from, from, alen);
515 	if (err)
516 		return err;
517 
518 	dbg_chk_lpt_sz(c, 4, alen - wlen);
519 	err = dbg_chk_lpt_sz(c, 3, ALIGN(offs, c->min_io_size));
520 	if (err)
521 		return err;
522 
523 	c->nhead_lnum = lnum;
524 	c->nhead_offs = ALIGN(offs, c->min_io_size);
525 
526 	dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs);
527 	dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs);
528 	dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs);
529 	if (c->big_lpt)
530 		dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs);
531 
532 	return 0;
533 
534 no_space:
535 	ubifs_err(c, "LPT out of space mismatch at LEB %d:%d needing %d, done_ltab %d, done_lsave %d",
536 		  lnum, offs, len, done_ltab, done_lsave);
537 	ubifs_dump_lpt_info(c);
538 	ubifs_dump_lpt_lebs(c);
539 	dump_stack();
540 	return err;
541 }
542 
543 /**
544  * next_pnode_to_dirty - find next pnode to dirty.
545  * @c: UBIFS file-system description object
546  * @pnode: pnode
547  *
548  * This function returns the next pnode to dirty or %NULL if there are no more
549  * pnodes.  Note that pnodes that have never been written (lnum == 0) are
550  * skipped.
551  */
next_pnode_to_dirty(struct ubifs_info * c,struct ubifs_pnode * pnode)552 static struct ubifs_pnode *next_pnode_to_dirty(struct ubifs_info *c,
553 					       struct ubifs_pnode *pnode)
554 {
555 	struct ubifs_nnode *nnode;
556 	int iip;
557 
558 	/* Try to go right */
559 	nnode = pnode->parent;
560 	for (iip = pnode->iip + 1; iip < UBIFS_LPT_FANOUT; iip++) {
561 		if (nnode->nbranch[iip].lnum)
562 			return ubifs_get_pnode(c, nnode, iip);
563 	}
564 
565 	/* Go up while can't go right */
566 	do {
567 		iip = nnode->iip + 1;
568 		nnode = nnode->parent;
569 		if (!nnode)
570 			return NULL;
571 		for (; iip < UBIFS_LPT_FANOUT; iip++) {
572 			if (nnode->nbranch[iip].lnum)
573 				break;
574 		}
575 	} while (iip >= UBIFS_LPT_FANOUT);
576 
577 	/* Go right */
578 	nnode = ubifs_get_nnode(c, nnode, iip);
579 	if (IS_ERR(nnode))
580 		return (void *)nnode;
581 
582 	/* Go down to level 1 */
583 	while (nnode->level > 1) {
584 		for (iip = 0; iip < UBIFS_LPT_FANOUT; iip++) {
585 			if (nnode->nbranch[iip].lnum)
586 				break;
587 		}
588 		if (iip >= UBIFS_LPT_FANOUT) {
589 			/*
590 			 * Should not happen, but we need to keep going
591 			 * if it does.
592 			 */
593 			iip = 0;
594 		}
595 		nnode = ubifs_get_nnode(c, nnode, iip);
596 		if (IS_ERR(nnode))
597 			return (void *)nnode;
598 	}
599 
600 	for (iip = 0; iip < UBIFS_LPT_FANOUT; iip++)
601 		if (nnode->nbranch[iip].lnum)
602 			break;
603 	if (iip >= UBIFS_LPT_FANOUT)
604 		/* Should not happen, but we need to keep going if it does */
605 		iip = 0;
606 	return ubifs_get_pnode(c, nnode, iip);
607 }
608 
609 /**
610  * add_pnode_dirt - add dirty space to LPT LEB properties.
611  * @c: UBIFS file-system description object
612  * @pnode: pnode for which to add dirt
613  */
add_pnode_dirt(struct ubifs_info * c,struct ubifs_pnode * pnode)614 static void add_pnode_dirt(struct ubifs_info *c, struct ubifs_pnode *pnode)
615 {
616 	ubifs_add_lpt_dirt(c, pnode->parent->nbranch[pnode->iip].lnum,
617 			   c->pnode_sz);
618 }
619 
620 /**
621  * do_make_pnode_dirty - mark a pnode dirty.
622  * @c: UBIFS file-system description object
623  * @pnode: pnode to mark dirty
624  */
do_make_pnode_dirty(struct ubifs_info * c,struct ubifs_pnode * pnode)625 static void do_make_pnode_dirty(struct ubifs_info *c, struct ubifs_pnode *pnode)
626 {
627 	/* Assumes cnext list is empty i.e. not called during commit */
628 	if (!test_and_set_bit(DIRTY_CNODE, &pnode->flags)) {
629 		struct ubifs_nnode *nnode;
630 
631 		c->dirty_pn_cnt += 1;
632 		add_pnode_dirt(c, pnode);
633 		/* Mark parent and ancestors dirty too */
634 		nnode = pnode->parent;
635 		while (nnode) {
636 			if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
637 				c->dirty_nn_cnt += 1;
638 				ubifs_add_nnode_dirt(c, nnode);
639 				nnode = nnode->parent;
640 			} else
641 				break;
642 		}
643 	}
644 }
645 
646 /**
647  * make_tree_dirty - mark the entire LEB properties tree dirty.
648  * @c: UBIFS file-system description object
649  *
650  * This function is used by the "small" LPT model to cause the entire LEB
651  * properties tree to be written.  The "small" LPT model does not use LPT
652  * garbage collection because it is more efficient to write the entire tree
653  * (because it is small).
654  *
655  * This function returns %0 on success and a negative error code on failure.
656  */
make_tree_dirty(struct ubifs_info * c)657 static int make_tree_dirty(struct ubifs_info *c)
658 {
659 	struct ubifs_pnode *pnode;
660 
661 	pnode = ubifs_pnode_lookup(c, 0);
662 	if (IS_ERR(pnode))
663 		return PTR_ERR(pnode);
664 
665 	while (pnode) {
666 		do_make_pnode_dirty(c, pnode);
667 		pnode = next_pnode_to_dirty(c, pnode);
668 		if (IS_ERR(pnode))
669 			return PTR_ERR(pnode);
670 	}
671 	return 0;
672 }
673 
674 /**
675  * need_write_all - determine if the LPT area is running out of free space.
676  * @c: UBIFS file-system description object
677  *
678  * This function returns %1 if the LPT area is running out of free space and %0
679  * if it is not.
680  */
need_write_all(struct ubifs_info * c)681 static int need_write_all(struct ubifs_info *c)
682 {
683 	long long free = 0;
684 	int i;
685 
686 	for (i = 0; i < c->lpt_lebs; i++) {
687 		if (i + c->lpt_first == c->nhead_lnum)
688 			free += c->leb_size - c->nhead_offs;
689 		else if (c->ltab[i].free == c->leb_size)
690 			free += c->leb_size;
691 		else if (c->ltab[i].free + c->ltab[i].dirty == c->leb_size)
692 			free += c->leb_size;
693 	}
694 	/* Less than twice the size left */
695 	if (free <= c->lpt_sz * 2)
696 		return 1;
697 	return 0;
698 }
699 
700 /**
701  * lpt_tgc_start - start trivial garbage collection of LPT LEBs.
702  * @c: UBIFS file-system description object
703  *
704  * LPT trivial garbage collection is where a LPT LEB contains only dirty and
705  * free space and so may be reused as soon as the next commit is completed.
706  * This function is called during start commit to mark LPT LEBs for trivial GC.
707  */
lpt_tgc_start(struct ubifs_info * c)708 static void lpt_tgc_start(struct ubifs_info *c)
709 {
710 	int i;
711 
712 	for (i = 0; i < c->lpt_lebs; i++) {
713 		if (i + c->lpt_first == c->nhead_lnum)
714 			continue;
715 		if (c->ltab[i].dirty > 0 &&
716 		    c->ltab[i].free + c->ltab[i].dirty == c->leb_size) {
717 			c->ltab[i].tgc = 1;
718 			c->ltab[i].free = c->leb_size;
719 			c->ltab[i].dirty = 0;
720 			dbg_lp("LEB %d", i + c->lpt_first);
721 		}
722 	}
723 }
724 
725 /**
726  * lpt_tgc_end - end trivial garbage collection of LPT LEBs.
727  * @c: UBIFS file-system description object
728  *
729  * LPT trivial garbage collection is where a LPT LEB contains only dirty and
730  * free space and so may be reused as soon as the next commit is completed.
731  * This function is called after the commit is completed (master node has been
732  * written) and un-maps LPT LEBs that were marked for trivial GC.
733  */
lpt_tgc_end(struct ubifs_info * c)734 static int lpt_tgc_end(struct ubifs_info *c)
735 {
736 	int i, err;
737 
738 	for (i = 0; i < c->lpt_lebs; i++)
739 		if (c->ltab[i].tgc) {
740 			err = ubifs_leb_unmap(c, i + c->lpt_first);
741 			if (err)
742 				return err;
743 			c->ltab[i].tgc = 0;
744 			dbg_lp("LEB %d", i + c->lpt_first);
745 		}
746 	return 0;
747 }
748 
749 /**
750  * populate_lsave - fill the lsave array with important LEB numbers.
751  * @c: the UBIFS file-system description object
752  *
753  * This function is only called for the "big" model. It records a small number
754  * of LEB numbers of important LEBs.  Important LEBs are ones that are (from
755  * most important to least important): empty, freeable, freeable index, dirty
756  * index, dirty or free. Upon mount, we read this list of LEB numbers and bring
757  * their pnodes into memory.  That will stop us from having to scan the LPT
758  * straight away. For the "small" model we assume that scanning the LPT is no
759  * big deal.
760  */
populate_lsave(struct ubifs_info * c)761 static void populate_lsave(struct ubifs_info *c)
762 {
763 	struct ubifs_lprops *lprops;
764 	struct ubifs_lpt_heap *heap;
765 	int i, cnt = 0;
766 
767 	ubifs_assert(c, c->big_lpt);
768 	if (!(c->lpt_drty_flgs & LSAVE_DIRTY)) {
769 		c->lpt_drty_flgs |= LSAVE_DIRTY;
770 		ubifs_add_lpt_dirt(c, c->lsave_lnum, c->lsave_sz);
771 	}
772 
773 	if (dbg_populate_lsave(c))
774 		return;
775 
776 	list_for_each_entry(lprops, &c->empty_list, list) {
777 		c->lsave[cnt++] = lprops->lnum;
778 		if (cnt >= c->lsave_cnt)
779 			return;
780 	}
781 	list_for_each_entry(lprops, &c->freeable_list, list) {
782 		c->lsave[cnt++] = lprops->lnum;
783 		if (cnt >= c->lsave_cnt)
784 			return;
785 	}
786 	list_for_each_entry(lprops, &c->frdi_idx_list, list) {
787 		c->lsave[cnt++] = lprops->lnum;
788 		if (cnt >= c->lsave_cnt)
789 			return;
790 	}
791 	heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
792 	for (i = 0; i < heap->cnt; i++) {
793 		c->lsave[cnt++] = heap->arr[i]->lnum;
794 		if (cnt >= c->lsave_cnt)
795 			return;
796 	}
797 	heap = &c->lpt_heap[LPROPS_DIRTY - 1];
798 	for (i = 0; i < heap->cnt; i++) {
799 		c->lsave[cnt++] = heap->arr[i]->lnum;
800 		if (cnt >= c->lsave_cnt)
801 			return;
802 	}
803 	heap = &c->lpt_heap[LPROPS_FREE - 1];
804 	for (i = 0; i < heap->cnt; i++) {
805 		c->lsave[cnt++] = heap->arr[i]->lnum;
806 		if (cnt >= c->lsave_cnt)
807 			return;
808 	}
809 	/* Fill it up completely */
810 	while (cnt < c->lsave_cnt)
811 		c->lsave[cnt++] = c->main_first;
812 }
813 
814 /**
815  * nnode_lookup - lookup a nnode in the LPT.
816  * @c: UBIFS file-system description object
817  * @i: nnode number
818  *
819  * This function returns a pointer to the nnode on success or a negative
820  * error code on failure.
821  */
nnode_lookup(struct ubifs_info * c,int i)822 static struct ubifs_nnode *nnode_lookup(struct ubifs_info *c, int i)
823 {
824 	int err, iip;
825 	struct ubifs_nnode *nnode;
826 
827 	if (!c->nroot) {
828 		err = ubifs_read_nnode(c, NULL, 0);
829 		if (err)
830 			return ERR_PTR(err);
831 	}
832 	nnode = c->nroot;
833 	while (1) {
834 		iip = i & (UBIFS_LPT_FANOUT - 1);
835 		i >>= UBIFS_LPT_FANOUT_SHIFT;
836 		if (!i)
837 			break;
838 		nnode = ubifs_get_nnode(c, nnode, iip);
839 		if (IS_ERR(nnode))
840 			return nnode;
841 	}
842 	return nnode;
843 }
844 
845 /**
846  * make_nnode_dirty - find a nnode and, if found, make it dirty.
847  * @c: UBIFS file-system description object
848  * @node_num: nnode number of nnode to make dirty
849  * @lnum: LEB number where nnode was written
850  * @offs: offset where nnode was written
851  *
852  * This function is used by LPT garbage collection.  LPT garbage collection is
853  * used only for the "big" LPT model (c->big_lpt == 1).  Garbage collection
854  * simply involves marking all the nodes in the LEB being garbage-collected as
855  * dirty.  The dirty nodes are written next commit, after which the LEB is free
856  * to be reused.
857  *
858  * This function returns %0 on success and a negative error code on failure.
859  */
make_nnode_dirty(struct ubifs_info * c,int node_num,int lnum,int offs)860 static int make_nnode_dirty(struct ubifs_info *c, int node_num, int lnum,
861 			    int offs)
862 {
863 	struct ubifs_nnode *nnode;
864 
865 	nnode = nnode_lookup(c, node_num);
866 	if (IS_ERR(nnode))
867 		return PTR_ERR(nnode);
868 	if (nnode->parent) {
869 		struct ubifs_nbranch *branch;
870 
871 		branch = &nnode->parent->nbranch[nnode->iip];
872 		if (branch->lnum != lnum || branch->offs != offs)
873 			return 0; /* nnode is obsolete */
874 	} else if (c->lpt_lnum != lnum || c->lpt_offs != offs)
875 			return 0; /* nnode is obsolete */
876 	/* Assumes cnext list is empty i.e. not called during commit */
877 	if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
878 		c->dirty_nn_cnt += 1;
879 		ubifs_add_nnode_dirt(c, nnode);
880 		/* Mark parent and ancestors dirty too */
881 		nnode = nnode->parent;
882 		while (nnode) {
883 			if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
884 				c->dirty_nn_cnt += 1;
885 				ubifs_add_nnode_dirt(c, nnode);
886 				nnode = nnode->parent;
887 			} else
888 				break;
889 		}
890 	}
891 	return 0;
892 }
893 
894 /**
895  * make_pnode_dirty - find a pnode and, if found, make it dirty.
896  * @c: UBIFS file-system description object
897  * @node_num: pnode number of pnode to make dirty
898  * @lnum: LEB number where pnode was written
899  * @offs: offset where pnode was written
900  *
901  * This function is used by LPT garbage collection.  LPT garbage collection is
902  * used only for the "big" LPT model (c->big_lpt == 1).  Garbage collection
903  * simply involves marking all the nodes in the LEB being garbage-collected as
904  * dirty.  The dirty nodes are written next commit, after which the LEB is free
905  * to be reused.
906  *
907  * This function returns %0 on success and a negative error code on failure.
908  */
make_pnode_dirty(struct ubifs_info * c,int node_num,int lnum,int offs)909 static int make_pnode_dirty(struct ubifs_info *c, int node_num, int lnum,
910 			    int offs)
911 {
912 	struct ubifs_pnode *pnode;
913 	struct ubifs_nbranch *branch;
914 
915 	pnode = ubifs_pnode_lookup(c, node_num);
916 	if (IS_ERR(pnode))
917 		return PTR_ERR(pnode);
918 	branch = &pnode->parent->nbranch[pnode->iip];
919 	if (branch->lnum != lnum || branch->offs != offs)
920 		return 0;
921 	do_make_pnode_dirty(c, pnode);
922 	return 0;
923 }
924 
925 /**
926  * make_ltab_dirty - make ltab node dirty.
927  * @c: UBIFS file-system description object
928  * @lnum: LEB number where ltab was written
929  * @offs: offset where ltab was written
930  *
931  * This function is used by LPT garbage collection.  LPT garbage collection is
932  * used only for the "big" LPT model (c->big_lpt == 1).  Garbage collection
933  * simply involves marking all the nodes in the LEB being garbage-collected as
934  * dirty.  The dirty nodes are written next commit, after which the LEB is free
935  * to be reused.
936  *
937  * This function returns %0 on success and a negative error code on failure.
938  */
make_ltab_dirty(struct ubifs_info * c,int lnum,int offs)939 static int make_ltab_dirty(struct ubifs_info *c, int lnum, int offs)
940 {
941 	if (lnum != c->ltab_lnum || offs != c->ltab_offs)
942 		return 0; /* This ltab node is obsolete */
943 	if (!(c->lpt_drty_flgs & LTAB_DIRTY)) {
944 		c->lpt_drty_flgs |= LTAB_DIRTY;
945 		ubifs_add_lpt_dirt(c, c->ltab_lnum, c->ltab_sz);
946 	}
947 	return 0;
948 }
949 
950 /**
951  * make_lsave_dirty - make lsave node dirty.
952  * @c: UBIFS file-system description object
953  * @lnum: LEB number where lsave was written
954  * @offs: offset where lsave was written
955  *
956  * This function is used by LPT garbage collection.  LPT garbage collection is
957  * used only for the "big" LPT model (c->big_lpt == 1).  Garbage collection
958  * simply involves marking all the nodes in the LEB being garbage-collected as
959  * dirty.  The dirty nodes are written next commit, after which the LEB is free
960  * to be reused.
961  *
962  * This function returns %0 on success and a negative error code on failure.
963  */
make_lsave_dirty(struct ubifs_info * c,int lnum,int offs)964 static int make_lsave_dirty(struct ubifs_info *c, int lnum, int offs)
965 {
966 	if (lnum != c->lsave_lnum || offs != c->lsave_offs)
967 		return 0; /* This lsave node is obsolete */
968 	if (!(c->lpt_drty_flgs & LSAVE_DIRTY)) {
969 		c->lpt_drty_flgs |= LSAVE_DIRTY;
970 		ubifs_add_lpt_dirt(c, c->lsave_lnum, c->lsave_sz);
971 	}
972 	return 0;
973 }
974 
975 /**
976  * make_node_dirty - make node dirty.
977  * @c: UBIFS file-system description object
978  * @node_type: LPT node type
979  * @node_num: node number
980  * @lnum: LEB number where node was written
981  * @offs: offset where node was written
982  *
983  * This function is used by LPT garbage collection.  LPT garbage collection is
984  * used only for the "big" LPT model (c->big_lpt == 1).  Garbage collection
985  * simply involves marking all the nodes in the LEB being garbage-collected as
986  * dirty.  The dirty nodes are written next commit, after which the LEB is free
987  * to be reused.
988  *
989  * This function returns %0 on success and a negative error code on failure.
990  */
make_node_dirty(struct ubifs_info * c,int node_type,int node_num,int lnum,int offs)991 static int make_node_dirty(struct ubifs_info *c, int node_type, int node_num,
992 			   int lnum, int offs)
993 {
994 	switch (node_type) {
995 	case UBIFS_LPT_NNODE:
996 		return make_nnode_dirty(c, node_num, lnum, offs);
997 	case UBIFS_LPT_PNODE:
998 		return make_pnode_dirty(c, node_num, lnum, offs);
999 	case UBIFS_LPT_LTAB:
1000 		return make_ltab_dirty(c, lnum, offs);
1001 	case UBIFS_LPT_LSAVE:
1002 		return make_lsave_dirty(c, lnum, offs);
1003 	}
1004 	return -EINVAL;
1005 }
1006 
1007 /**
1008  * get_lpt_node_len - return the length of a node based on its type.
1009  * @c: UBIFS file-system description object
1010  * @node_type: LPT node type
1011  */
get_lpt_node_len(const struct ubifs_info * c,int node_type)1012 static int get_lpt_node_len(const struct ubifs_info *c, int node_type)
1013 {
1014 	switch (node_type) {
1015 	case UBIFS_LPT_NNODE:
1016 		return c->nnode_sz;
1017 	case UBIFS_LPT_PNODE:
1018 		return c->pnode_sz;
1019 	case UBIFS_LPT_LTAB:
1020 		return c->ltab_sz;
1021 	case UBIFS_LPT_LSAVE:
1022 		return c->lsave_sz;
1023 	}
1024 	return 0;
1025 }
1026 
1027 /**
1028  * get_pad_len - return the length of padding in a buffer.
1029  * @c: UBIFS file-system description object
1030  * @buf: buffer
1031  * @len: length of buffer
1032  */
get_pad_len(const struct ubifs_info * c,uint8_t * buf,int len)1033 static int get_pad_len(const struct ubifs_info *c, uint8_t *buf, int len)
1034 {
1035 	int offs, pad_len;
1036 
1037 	if (c->min_io_size == 1)
1038 		return 0;
1039 	offs = c->leb_size - len;
1040 	pad_len = ALIGN(offs, c->min_io_size) - offs;
1041 	return pad_len;
1042 }
1043 
1044 /**
1045  * get_lpt_node_type - return type (and node number) of a node in a buffer.
1046  * @c: UBIFS file-system description object
1047  * @buf: buffer
1048  * @node_num: node number is returned here
1049  */
get_lpt_node_type(const struct ubifs_info * c,uint8_t * buf,int * node_num)1050 static int get_lpt_node_type(const struct ubifs_info *c, uint8_t *buf,
1051 			     int *node_num)
1052 {
1053 	uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1054 	int pos = 0, node_type;
1055 
1056 	node_type = ubifs_unpack_bits(c, &addr, &pos, UBIFS_LPT_TYPE_BITS);
1057 	*node_num = ubifs_unpack_bits(c, &addr, &pos, c->pcnt_bits);
1058 	return node_type;
1059 }
1060 
1061 /**
1062  * is_a_node - determine if a buffer contains a node.
1063  * @c: UBIFS file-system description object
1064  * @buf: buffer
1065  * @len: length of buffer
1066  *
1067  * This function returns %1 if the buffer contains a node or %0 if it does not.
1068  */
is_a_node(const struct ubifs_info * c,uint8_t * buf,int len)1069 static int is_a_node(const struct ubifs_info *c, uint8_t *buf, int len)
1070 {
1071 	uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1072 	int pos = 0, node_type, node_len;
1073 	uint16_t crc, calc_crc;
1074 
1075 	if (len < UBIFS_LPT_CRC_BYTES + (UBIFS_LPT_TYPE_BITS + 7) / 8)
1076 		return 0;
1077 	node_type = ubifs_unpack_bits(c, &addr, &pos, UBIFS_LPT_TYPE_BITS);
1078 	if (node_type == UBIFS_LPT_NOT_A_NODE)
1079 		return 0;
1080 	node_len = get_lpt_node_len(c, node_type);
1081 	if (!node_len || node_len > len)
1082 		return 0;
1083 	pos = 0;
1084 	addr = buf;
1085 	crc = ubifs_unpack_bits(c, &addr, &pos, UBIFS_LPT_CRC_BITS);
1086 	calc_crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
1087 			 node_len - UBIFS_LPT_CRC_BYTES);
1088 	if (crc != calc_crc)
1089 		return 0;
1090 	return 1;
1091 }
1092 
1093 /**
1094  * lpt_gc_lnum - garbage collect a LPT LEB.
1095  * @c: UBIFS file-system description object
1096  * @lnum: LEB number to garbage collect
1097  *
1098  * LPT garbage collection is used only for the "big" LPT model
1099  * (c->big_lpt == 1).  Garbage collection simply involves marking all the nodes
1100  * in the LEB being garbage-collected as dirty.  The dirty nodes are written
1101  * next commit, after which the LEB is free to be reused.
1102  *
1103  * This function returns %0 on success and a negative error code on failure.
1104  */
lpt_gc_lnum(struct ubifs_info * c,int lnum)1105 static int lpt_gc_lnum(struct ubifs_info *c, int lnum)
1106 {
1107 	int err, len = c->leb_size, node_type, node_num, node_len, offs;
1108 	void *buf = c->lpt_buf;
1109 
1110 	dbg_lp("LEB %d", lnum);
1111 
1112 	err = ubifs_leb_read(c, lnum, buf, 0, c->leb_size, 1);
1113 	if (err)
1114 		return err;
1115 
1116 	while (1) {
1117 		if (!is_a_node(c, buf, len)) {
1118 			int pad_len;
1119 
1120 			pad_len = get_pad_len(c, buf, len);
1121 			if (pad_len) {
1122 				buf += pad_len;
1123 				len -= pad_len;
1124 				continue;
1125 			}
1126 			return 0;
1127 		}
1128 		node_type = get_lpt_node_type(c, buf, &node_num);
1129 		node_len = get_lpt_node_len(c, node_type);
1130 		offs = c->leb_size - len;
1131 		ubifs_assert(c, node_len != 0);
1132 		mutex_lock(&c->lp_mutex);
1133 		err = make_node_dirty(c, node_type, node_num, lnum, offs);
1134 		mutex_unlock(&c->lp_mutex);
1135 		if (err)
1136 			return err;
1137 		buf += node_len;
1138 		len -= node_len;
1139 	}
1140 	return 0;
1141 }
1142 
1143 /**
1144  * lpt_gc - LPT garbage collection.
1145  * @c: UBIFS file-system description object
1146  *
1147  * Select a LPT LEB for LPT garbage collection and call 'lpt_gc_lnum()'.
1148  * Returns %0 on success and a negative error code on failure.
1149  */
lpt_gc(struct ubifs_info * c)1150 static int lpt_gc(struct ubifs_info *c)
1151 {
1152 	int i, lnum = -1, dirty = 0;
1153 
1154 	mutex_lock(&c->lp_mutex);
1155 	for (i = 0; i < c->lpt_lebs; i++) {
1156 		ubifs_assert(c, !c->ltab[i].tgc);
1157 		if (i + c->lpt_first == c->nhead_lnum ||
1158 		    c->ltab[i].free + c->ltab[i].dirty == c->leb_size)
1159 			continue;
1160 		if (c->ltab[i].dirty > dirty) {
1161 			dirty = c->ltab[i].dirty;
1162 			lnum = i + c->lpt_first;
1163 		}
1164 	}
1165 	mutex_unlock(&c->lp_mutex);
1166 	if (lnum == -1)
1167 		return -ENOSPC;
1168 	return lpt_gc_lnum(c, lnum);
1169 }
1170 
1171 /**
1172  * ubifs_lpt_start_commit - UBIFS commit starts.
1173  * @c: the UBIFS file-system description object
1174  *
1175  * This function has to be called when UBIFS starts the commit operation.
1176  * This function "freezes" all currently dirty LEB properties and does not
1177  * change them anymore. Further changes are saved and tracked separately
1178  * because they are not part of this commit. This function returns zero in case
1179  * of success and a negative error code in case of failure.
1180  */
ubifs_lpt_start_commit(struct ubifs_info * c)1181 int ubifs_lpt_start_commit(struct ubifs_info *c)
1182 {
1183 	int err, cnt;
1184 
1185 	dbg_lp("");
1186 
1187 	mutex_lock(&c->lp_mutex);
1188 	err = dbg_chk_lpt_free_spc(c);
1189 	if (err)
1190 		goto out;
1191 	err = dbg_check_ltab(c);
1192 	if (err)
1193 		goto out;
1194 
1195 	if (c->check_lpt_free) {
1196 		/*
1197 		 * We ensure there is enough free space in
1198 		 * ubifs_lpt_post_commit() by marking nodes dirty. That
1199 		 * information is lost when we unmount, so we also need
1200 		 * to check free space once after mounting also.
1201 		 */
1202 		c->check_lpt_free = 0;
1203 		while (need_write_all(c)) {
1204 			mutex_unlock(&c->lp_mutex);
1205 			err = lpt_gc(c);
1206 			if (err)
1207 				return err;
1208 			mutex_lock(&c->lp_mutex);
1209 		}
1210 	}
1211 
1212 	lpt_tgc_start(c);
1213 
1214 	if (!c->dirty_pn_cnt) {
1215 		dbg_cmt("no cnodes to commit");
1216 		err = 0;
1217 		goto out;
1218 	}
1219 
1220 	if (!c->big_lpt && need_write_all(c)) {
1221 		/* If needed, write everything */
1222 		err = make_tree_dirty(c);
1223 		if (err)
1224 			goto out;
1225 		lpt_tgc_start(c);
1226 	}
1227 
1228 	if (c->big_lpt)
1229 		populate_lsave(c);
1230 
1231 	cnt = get_cnodes_to_commit(c);
1232 	ubifs_assert(c, cnt != 0);
1233 
1234 	err = layout_cnodes(c);
1235 	if (err)
1236 		goto out;
1237 
1238 	err = ubifs_lpt_calc_hash(c, c->mst_node->hash_lpt);
1239 	if (err)
1240 		goto out;
1241 
1242 	/* Copy the LPT's own lprops for end commit to write */
1243 	memcpy(c->ltab_cmt, c->ltab,
1244 	       sizeof(struct ubifs_lpt_lprops) * c->lpt_lebs);
1245 	c->lpt_drty_flgs &= ~(LTAB_DIRTY | LSAVE_DIRTY);
1246 
1247 out:
1248 	mutex_unlock(&c->lp_mutex);
1249 	return err;
1250 }
1251 
1252 /**
1253  * free_obsolete_cnodes - free obsolete cnodes for commit end.
1254  * @c: UBIFS file-system description object
1255  */
free_obsolete_cnodes(struct ubifs_info * c)1256 static void free_obsolete_cnodes(struct ubifs_info *c)
1257 {
1258 	struct ubifs_cnode *cnode, *cnext;
1259 
1260 	cnext = c->lpt_cnext;
1261 	if (!cnext)
1262 		return;
1263 	do {
1264 		cnode = cnext;
1265 		cnext = cnode->cnext;
1266 		if (test_bit(OBSOLETE_CNODE, &cnode->flags))
1267 			kfree(cnode);
1268 		else
1269 			cnode->cnext = NULL;
1270 	} while (cnext != c->lpt_cnext);
1271 	c->lpt_cnext = NULL;
1272 }
1273 
1274 /**
1275  * ubifs_lpt_end_commit - finish the commit operation.
1276  * @c: the UBIFS file-system description object
1277  *
1278  * This function has to be called when the commit operation finishes. It
1279  * flushes the changes which were "frozen" by 'ubifs_lprops_start_commit()' to
1280  * the media. Returns zero in case of success and a negative error code in case
1281  * of failure.
1282  */
ubifs_lpt_end_commit(struct ubifs_info * c)1283 int ubifs_lpt_end_commit(struct ubifs_info *c)
1284 {
1285 	int err;
1286 
1287 	dbg_lp("");
1288 
1289 	if (!c->lpt_cnext)
1290 		return 0;
1291 
1292 	err = write_cnodes(c);
1293 	if (err)
1294 		return err;
1295 
1296 	mutex_lock(&c->lp_mutex);
1297 	free_obsolete_cnodes(c);
1298 	mutex_unlock(&c->lp_mutex);
1299 
1300 	return 0;
1301 }
1302 
1303 /**
1304  * ubifs_lpt_post_commit - post commit LPT trivial GC and LPT GC.
1305  * @c: UBIFS file-system description object
1306  *
1307  * LPT trivial GC is completed after a commit. Also LPT GC is done after a
1308  * commit for the "big" LPT model.
1309  */
ubifs_lpt_post_commit(struct ubifs_info * c)1310 int ubifs_lpt_post_commit(struct ubifs_info *c)
1311 {
1312 	int err;
1313 
1314 	mutex_lock(&c->lp_mutex);
1315 	err = lpt_tgc_end(c);
1316 	if (err)
1317 		goto out;
1318 	if (c->big_lpt)
1319 		while (need_write_all(c)) {
1320 			mutex_unlock(&c->lp_mutex);
1321 			err = lpt_gc(c);
1322 			if (err)
1323 				return err;
1324 			mutex_lock(&c->lp_mutex);
1325 		}
1326 out:
1327 	mutex_unlock(&c->lp_mutex);
1328 	return err;
1329 }
1330 
1331 /**
1332  * first_nnode - find the first nnode in memory.
1333  * @c: UBIFS file-system description object
1334  * @hght: height of tree where nnode found is returned here
1335  *
1336  * This function returns a pointer to the nnode found or %NULL if no nnode is
1337  * found. This function is a helper to 'ubifs_lpt_free()'.
1338  */
first_nnode(struct ubifs_info * c,int * hght)1339 static struct ubifs_nnode *first_nnode(struct ubifs_info *c, int *hght)
1340 {
1341 	struct ubifs_nnode *nnode;
1342 	int h, i, found;
1343 
1344 	nnode = c->nroot;
1345 	*hght = 0;
1346 	if (!nnode)
1347 		return NULL;
1348 	for (h = 1; h < c->lpt_hght; h++) {
1349 		found = 0;
1350 		for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1351 			if (nnode->nbranch[i].nnode) {
1352 				found = 1;
1353 				nnode = nnode->nbranch[i].nnode;
1354 				*hght = h;
1355 				break;
1356 			}
1357 		}
1358 		if (!found)
1359 			break;
1360 	}
1361 	return nnode;
1362 }
1363 
1364 /**
1365  * next_nnode - find the next nnode in memory.
1366  * @c: UBIFS file-system description object
1367  * @nnode: nnode from which to start.
1368  * @hght: height of tree where nnode is, is passed and returned here
1369  *
1370  * This function returns a pointer to the nnode found or %NULL if no nnode is
1371  * found. This function is a helper to 'ubifs_lpt_free()'.
1372  */
next_nnode(struct ubifs_info * c,struct ubifs_nnode * nnode,int * hght)1373 static struct ubifs_nnode *next_nnode(struct ubifs_info *c,
1374 				      struct ubifs_nnode *nnode, int *hght)
1375 {
1376 	struct ubifs_nnode *parent;
1377 	int iip, h, i, found;
1378 
1379 	parent = nnode->parent;
1380 	if (!parent)
1381 		return NULL;
1382 	if (nnode->iip == UBIFS_LPT_FANOUT - 1) {
1383 		*hght -= 1;
1384 		return parent;
1385 	}
1386 	for (iip = nnode->iip + 1; iip < UBIFS_LPT_FANOUT; iip++) {
1387 		nnode = parent->nbranch[iip].nnode;
1388 		if (nnode)
1389 			break;
1390 	}
1391 	if (!nnode) {
1392 		*hght -= 1;
1393 		return parent;
1394 	}
1395 	for (h = *hght + 1; h < c->lpt_hght; h++) {
1396 		found = 0;
1397 		for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1398 			if (nnode->nbranch[i].nnode) {
1399 				found = 1;
1400 				nnode = nnode->nbranch[i].nnode;
1401 				*hght = h;
1402 				break;
1403 			}
1404 		}
1405 		if (!found)
1406 			break;
1407 	}
1408 	return nnode;
1409 }
1410 
1411 /**
1412  * ubifs_lpt_free - free resources owned by the LPT.
1413  * @c: UBIFS file-system description object
1414  * @wr_only: free only resources used for writing
1415  */
ubifs_lpt_free(struct ubifs_info * c,int wr_only)1416 void ubifs_lpt_free(struct ubifs_info *c, int wr_only)
1417 {
1418 	struct ubifs_nnode *nnode;
1419 	int i, hght;
1420 
1421 	/* Free write-only things first */
1422 
1423 	free_obsolete_cnodes(c); /* Leftover from a failed commit */
1424 
1425 	vfree(c->ltab_cmt);
1426 	c->ltab_cmt = NULL;
1427 	vfree(c->lpt_buf);
1428 	c->lpt_buf = NULL;
1429 	kfree(c->lsave);
1430 	c->lsave = NULL;
1431 
1432 	if (wr_only)
1433 		return;
1434 
1435 	/* Now free the rest */
1436 
1437 	nnode = first_nnode(c, &hght);
1438 	while (nnode) {
1439 		for (i = 0; i < UBIFS_LPT_FANOUT; i++)
1440 			kfree(nnode->nbranch[i].nnode);
1441 		nnode = next_nnode(c, nnode, &hght);
1442 	}
1443 	for (i = 0; i < LPROPS_HEAP_CNT; i++)
1444 		kfree(c->lpt_heap[i].arr);
1445 	kfree(c->dirty_idx.arr);
1446 	kfree(c->nroot);
1447 	vfree(c->ltab);
1448 	kfree(c->lpt_nod_buf);
1449 }
1450 
1451 /*
1452  * Everything below is related to debugging.
1453  */
1454 
1455 /**
1456  * dbg_is_all_ff - determine if a buffer contains only 0xFF bytes.
1457  * @buf: buffer
1458  * @len: buffer length
1459  */
dbg_is_all_ff(uint8_t * buf,int len)1460 static int dbg_is_all_ff(uint8_t *buf, int len)
1461 {
1462 	int i;
1463 
1464 	for (i = 0; i < len; i++)
1465 		if (buf[i] != 0xff)
1466 			return 0;
1467 	return 1;
1468 }
1469 
1470 /**
1471  * dbg_is_nnode_dirty - determine if a nnode is dirty.
1472  * @c: the UBIFS file-system description object
1473  * @lnum: LEB number where nnode was written
1474  * @offs: offset where nnode was written
1475  */
dbg_is_nnode_dirty(struct ubifs_info * c,int lnum,int offs)1476 static int dbg_is_nnode_dirty(struct ubifs_info *c, int lnum, int offs)
1477 {
1478 	struct ubifs_nnode *nnode;
1479 	int hght;
1480 
1481 	/* Entire tree is in memory so first_nnode / next_nnode are OK */
1482 	nnode = first_nnode(c, &hght);
1483 	for (; nnode; nnode = next_nnode(c, nnode, &hght)) {
1484 		struct ubifs_nbranch *branch;
1485 
1486 		cond_resched();
1487 		if (nnode->parent) {
1488 			branch = &nnode->parent->nbranch[nnode->iip];
1489 			if (branch->lnum != lnum || branch->offs != offs)
1490 				continue;
1491 			if (test_bit(DIRTY_CNODE, &nnode->flags))
1492 				return 1;
1493 			return 0;
1494 		} else {
1495 			if (c->lpt_lnum != lnum || c->lpt_offs != offs)
1496 				continue;
1497 			if (test_bit(DIRTY_CNODE, &nnode->flags))
1498 				return 1;
1499 			return 0;
1500 		}
1501 	}
1502 	return 1;
1503 }
1504 
1505 /**
1506  * dbg_is_pnode_dirty - determine if a pnode is dirty.
1507  * @c: the UBIFS file-system description object
1508  * @lnum: LEB number where pnode was written
1509  * @offs: offset where pnode was written
1510  */
dbg_is_pnode_dirty(struct ubifs_info * c,int lnum,int offs)1511 static int dbg_is_pnode_dirty(struct ubifs_info *c, int lnum, int offs)
1512 {
1513 	int i, cnt;
1514 
1515 	cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
1516 	for (i = 0; i < cnt; i++) {
1517 		struct ubifs_pnode *pnode;
1518 		struct ubifs_nbranch *branch;
1519 
1520 		cond_resched();
1521 		pnode = ubifs_pnode_lookup(c, i);
1522 		if (IS_ERR(pnode))
1523 			return PTR_ERR(pnode);
1524 		branch = &pnode->parent->nbranch[pnode->iip];
1525 		if (branch->lnum != lnum || branch->offs != offs)
1526 			continue;
1527 		if (test_bit(DIRTY_CNODE, &pnode->flags))
1528 			return 1;
1529 		return 0;
1530 	}
1531 	return 1;
1532 }
1533 
1534 /**
1535  * dbg_is_ltab_dirty - determine if a ltab node is dirty.
1536  * @c: the UBIFS file-system description object
1537  * @lnum: LEB number where ltab node was written
1538  * @offs: offset where ltab node was written
1539  */
dbg_is_ltab_dirty(struct ubifs_info * c,int lnum,int offs)1540 static int dbg_is_ltab_dirty(struct ubifs_info *c, int lnum, int offs)
1541 {
1542 	if (lnum != c->ltab_lnum || offs != c->ltab_offs)
1543 		return 1;
1544 	return (c->lpt_drty_flgs & LTAB_DIRTY) != 0;
1545 }
1546 
1547 /**
1548  * dbg_is_lsave_dirty - determine if a lsave node is dirty.
1549  * @c: the UBIFS file-system description object
1550  * @lnum: LEB number where lsave node was written
1551  * @offs: offset where lsave node was written
1552  */
dbg_is_lsave_dirty(struct ubifs_info * c,int lnum,int offs)1553 static int dbg_is_lsave_dirty(struct ubifs_info *c, int lnum, int offs)
1554 {
1555 	if (lnum != c->lsave_lnum || offs != c->lsave_offs)
1556 		return 1;
1557 	return (c->lpt_drty_flgs & LSAVE_DIRTY) != 0;
1558 }
1559 
1560 /**
1561  * dbg_is_node_dirty - determine if a node is dirty.
1562  * @c: the UBIFS file-system description object
1563  * @node_type: node type
1564  * @lnum: LEB number where node was written
1565  * @offs: offset where node was written
1566  */
dbg_is_node_dirty(struct ubifs_info * c,int node_type,int lnum,int offs)1567 static int dbg_is_node_dirty(struct ubifs_info *c, int node_type, int lnum,
1568 			     int offs)
1569 {
1570 	switch (node_type) {
1571 	case UBIFS_LPT_NNODE:
1572 		return dbg_is_nnode_dirty(c, lnum, offs);
1573 	case UBIFS_LPT_PNODE:
1574 		return dbg_is_pnode_dirty(c, lnum, offs);
1575 	case UBIFS_LPT_LTAB:
1576 		return dbg_is_ltab_dirty(c, lnum, offs);
1577 	case UBIFS_LPT_LSAVE:
1578 		return dbg_is_lsave_dirty(c, lnum, offs);
1579 	}
1580 	return 1;
1581 }
1582 
1583 /**
1584  * dbg_check_ltab_lnum - check the ltab for a LPT LEB number.
1585  * @c: the UBIFS file-system description object
1586  * @lnum: LEB number where node was written
1587  *
1588  * This function returns %0 on success and a negative error code on failure.
1589  */
dbg_check_ltab_lnum(struct ubifs_info * c,int lnum)1590 static int dbg_check_ltab_lnum(struct ubifs_info *c, int lnum)
1591 {
1592 	int err, len = c->leb_size, dirty = 0, node_type, node_num, node_len;
1593 	int ret;
1594 	void *buf, *p;
1595 
1596 	if (!dbg_is_chk_lprops(c))
1597 		return 0;
1598 
1599 	buf = p = __vmalloc(c->leb_size, GFP_NOFS);
1600 	if (!buf) {
1601 		ubifs_err(c, "cannot allocate memory for ltab checking");
1602 		return 0;
1603 	}
1604 
1605 	dbg_lp("LEB %d", lnum);
1606 
1607 	err = ubifs_leb_read(c, lnum, buf, 0, c->leb_size, 1);
1608 	if (err)
1609 		goto out;
1610 
1611 	while (1) {
1612 		if (!is_a_node(c, p, len)) {
1613 			int i, pad_len;
1614 
1615 			pad_len = get_pad_len(c, p, len);
1616 			if (pad_len) {
1617 				p += pad_len;
1618 				len -= pad_len;
1619 				dirty += pad_len;
1620 				continue;
1621 			}
1622 			if (!dbg_is_all_ff(p, len)) {
1623 				ubifs_err(c, "invalid empty space in LEB %d at %d",
1624 					  lnum, c->leb_size - len);
1625 				err = -EINVAL;
1626 			}
1627 			i = lnum - c->lpt_first;
1628 			if (len != c->ltab[i].free) {
1629 				ubifs_err(c, "invalid free space in LEB %d (free %d, expected %d)",
1630 					  lnum, len, c->ltab[i].free);
1631 				err = -EINVAL;
1632 			}
1633 			if (dirty != c->ltab[i].dirty) {
1634 				ubifs_err(c, "invalid dirty space in LEB %d (dirty %d, expected %d)",
1635 					  lnum, dirty, c->ltab[i].dirty);
1636 				err = -EINVAL;
1637 			}
1638 			goto out;
1639 		}
1640 		node_type = get_lpt_node_type(c, p, &node_num);
1641 		node_len = get_lpt_node_len(c, node_type);
1642 		ret = dbg_is_node_dirty(c, node_type, lnum, c->leb_size - len);
1643 		if (ret == 1)
1644 			dirty += node_len;
1645 		p += node_len;
1646 		len -= node_len;
1647 	}
1648 
1649 	err = 0;
1650 out:
1651 	vfree(buf);
1652 	return err;
1653 }
1654 
1655 /**
1656  * dbg_check_ltab - check the free and dirty space in the ltab.
1657  * @c: the UBIFS file-system description object
1658  *
1659  * This function returns %0 on success and a negative error code on failure.
1660  */
dbg_check_ltab(struct ubifs_info * c)1661 int dbg_check_ltab(struct ubifs_info *c)
1662 {
1663 	int lnum, err, i, cnt;
1664 
1665 	if (!dbg_is_chk_lprops(c))
1666 		return 0;
1667 
1668 	/* Bring the entire tree into memory */
1669 	cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
1670 	for (i = 0; i < cnt; i++) {
1671 		struct ubifs_pnode *pnode;
1672 
1673 		pnode = ubifs_pnode_lookup(c, i);
1674 		if (IS_ERR(pnode))
1675 			return PTR_ERR(pnode);
1676 		cond_resched();
1677 	}
1678 
1679 	/* Check nodes */
1680 	err = dbg_check_lpt_nodes(c, (struct ubifs_cnode *)c->nroot, 0, 0);
1681 	if (err)
1682 		return err;
1683 
1684 	/* Check each LEB */
1685 	for (lnum = c->lpt_first; lnum <= c->lpt_last; lnum++) {
1686 		err = dbg_check_ltab_lnum(c, lnum);
1687 		if (err) {
1688 			ubifs_err(c, "failed at LEB %d", lnum);
1689 			return err;
1690 		}
1691 	}
1692 
1693 	dbg_lp("succeeded");
1694 	return 0;
1695 }
1696 
1697 /**
1698  * dbg_chk_lpt_free_spc - check LPT free space is enough to write entire LPT.
1699  * @c: the UBIFS file-system description object
1700  *
1701  * This function returns %0 on success and a negative error code on failure.
1702  */
dbg_chk_lpt_free_spc(struct ubifs_info * c)1703 int dbg_chk_lpt_free_spc(struct ubifs_info *c)
1704 {
1705 	long long free = 0;
1706 	int i;
1707 
1708 	if (!dbg_is_chk_lprops(c))
1709 		return 0;
1710 
1711 	for (i = 0; i < c->lpt_lebs; i++) {
1712 		if (c->ltab[i].tgc || c->ltab[i].cmt)
1713 			continue;
1714 		if (i + c->lpt_first == c->nhead_lnum)
1715 			free += c->leb_size - c->nhead_offs;
1716 		else if (c->ltab[i].free == c->leb_size)
1717 			free += c->leb_size;
1718 	}
1719 	if (free < c->lpt_sz) {
1720 		ubifs_err(c, "LPT space error: free %lld lpt_sz %lld",
1721 			  free, c->lpt_sz);
1722 		ubifs_dump_lpt_info(c);
1723 		ubifs_dump_lpt_lebs(c);
1724 		dump_stack();
1725 		return -EINVAL;
1726 	}
1727 	return 0;
1728 }
1729 
1730 /**
1731  * dbg_chk_lpt_sz - check LPT does not write more than LPT size.
1732  * @c: the UBIFS file-system description object
1733  * @action: what to do
1734  * @len: length written
1735  *
1736  * This function returns %0 on success and a negative error code on failure.
1737  * The @action argument may be one of:
1738  *   o %0 - LPT debugging checking starts, initialize debugging variables;
1739  *   o %1 - wrote an LPT node, increase LPT size by @len bytes;
1740  *   o %2 - switched to a different LEB and wasted @len bytes;
1741  *   o %3 - check that we've written the right number of bytes.
1742  *   o %4 - wasted @len bytes;
1743  */
dbg_chk_lpt_sz(struct ubifs_info * c,int action,int len)1744 int dbg_chk_lpt_sz(struct ubifs_info *c, int action, int len)
1745 {
1746 	struct ubifs_debug_info *d = c->dbg;
1747 	long long chk_lpt_sz, lpt_sz;
1748 	int err = 0;
1749 
1750 	if (!dbg_is_chk_lprops(c))
1751 		return 0;
1752 
1753 	switch (action) {
1754 	case 0:
1755 		d->chk_lpt_sz = 0;
1756 		d->chk_lpt_sz2 = 0;
1757 		d->chk_lpt_lebs = 0;
1758 		d->chk_lpt_wastage = 0;
1759 		if (c->dirty_pn_cnt > c->pnode_cnt) {
1760 			ubifs_err(c, "dirty pnodes %d exceed max %d",
1761 				  c->dirty_pn_cnt, c->pnode_cnt);
1762 			err = -EINVAL;
1763 		}
1764 		if (c->dirty_nn_cnt > c->nnode_cnt) {
1765 			ubifs_err(c, "dirty nnodes %d exceed max %d",
1766 				  c->dirty_nn_cnt, c->nnode_cnt);
1767 			err = -EINVAL;
1768 		}
1769 		return err;
1770 	case 1:
1771 		d->chk_lpt_sz += len;
1772 		return 0;
1773 	case 2:
1774 		d->chk_lpt_sz += len;
1775 		d->chk_lpt_wastage += len;
1776 		d->chk_lpt_lebs += 1;
1777 		return 0;
1778 	case 3:
1779 		chk_lpt_sz = c->leb_size;
1780 		chk_lpt_sz *= d->chk_lpt_lebs;
1781 		chk_lpt_sz += len - c->nhead_offs;
1782 		if (d->chk_lpt_sz != chk_lpt_sz) {
1783 			ubifs_err(c, "LPT wrote %lld but space used was %lld",
1784 				  d->chk_lpt_sz, chk_lpt_sz);
1785 			err = -EINVAL;
1786 		}
1787 		if (d->chk_lpt_sz > c->lpt_sz) {
1788 			ubifs_err(c, "LPT wrote %lld but lpt_sz is %lld",
1789 				  d->chk_lpt_sz, c->lpt_sz);
1790 			err = -EINVAL;
1791 		}
1792 		if (d->chk_lpt_sz2 && d->chk_lpt_sz != d->chk_lpt_sz2) {
1793 			ubifs_err(c, "LPT layout size %lld but wrote %lld",
1794 				  d->chk_lpt_sz, d->chk_lpt_sz2);
1795 			err = -EINVAL;
1796 		}
1797 		if (d->chk_lpt_sz2 && d->new_nhead_offs != len) {
1798 			ubifs_err(c, "LPT new nhead offs: expected %d was %d",
1799 				  d->new_nhead_offs, len);
1800 			err = -EINVAL;
1801 		}
1802 		lpt_sz = (long long)c->pnode_cnt * c->pnode_sz;
1803 		lpt_sz += (long long)c->nnode_cnt * c->nnode_sz;
1804 		lpt_sz += c->ltab_sz;
1805 		if (c->big_lpt)
1806 			lpt_sz += c->lsave_sz;
1807 		if (d->chk_lpt_sz - d->chk_lpt_wastage > lpt_sz) {
1808 			ubifs_err(c, "LPT chk_lpt_sz %lld + waste %lld exceeds %lld",
1809 				  d->chk_lpt_sz, d->chk_lpt_wastage, lpt_sz);
1810 			err = -EINVAL;
1811 		}
1812 		if (err) {
1813 			ubifs_dump_lpt_info(c);
1814 			ubifs_dump_lpt_lebs(c);
1815 			dump_stack();
1816 		}
1817 		d->chk_lpt_sz2 = d->chk_lpt_sz;
1818 		d->chk_lpt_sz = 0;
1819 		d->chk_lpt_wastage = 0;
1820 		d->chk_lpt_lebs = 0;
1821 		d->new_nhead_offs = len;
1822 		return err;
1823 	case 4:
1824 		d->chk_lpt_sz += len;
1825 		d->chk_lpt_wastage += len;
1826 		return 0;
1827 	default:
1828 		return -EINVAL;
1829 	}
1830 }
1831 
1832 /**
1833  * dump_lpt_leb - dump an LPT LEB.
1834  * @c: UBIFS file-system description object
1835  * @lnum: LEB number to dump
1836  *
1837  * This function dumps an LEB from LPT area. Nodes in this area are very
1838  * different to nodes in the main area (e.g., they do not have common headers,
1839  * they do not have 8-byte alignments, etc), so we have a separate function to
1840  * dump LPT area LEBs. Note, LPT has to be locked by the caller.
1841  */
dump_lpt_leb(const struct ubifs_info * c,int lnum)1842 static void dump_lpt_leb(const struct ubifs_info *c, int lnum)
1843 {
1844 	int err, len = c->leb_size, node_type, node_num, node_len, offs;
1845 	void *buf, *p;
1846 
1847 	pr_err("(pid %d) start dumping LEB %d\n", current->pid, lnum);
1848 	buf = p = __vmalloc(c->leb_size, GFP_NOFS);
1849 	if (!buf) {
1850 		ubifs_err(c, "cannot allocate memory to dump LPT");
1851 		return;
1852 	}
1853 
1854 	err = ubifs_leb_read(c, lnum, buf, 0, c->leb_size, 1);
1855 	if (err)
1856 		goto out;
1857 
1858 	while (1) {
1859 		offs = c->leb_size - len;
1860 		if (!is_a_node(c, p, len)) {
1861 			int pad_len;
1862 
1863 			pad_len = get_pad_len(c, p, len);
1864 			if (pad_len) {
1865 				pr_err("LEB %d:%d, pad %d bytes\n",
1866 				       lnum, offs, pad_len);
1867 				p += pad_len;
1868 				len -= pad_len;
1869 				continue;
1870 			}
1871 			if (len)
1872 				pr_err("LEB %d:%d, free %d bytes\n",
1873 				       lnum, offs, len);
1874 			break;
1875 		}
1876 
1877 		node_type = get_lpt_node_type(c, p, &node_num);
1878 		switch (node_type) {
1879 		case UBIFS_LPT_PNODE:
1880 		{
1881 			node_len = c->pnode_sz;
1882 			if (c->big_lpt)
1883 				pr_err("LEB %d:%d, pnode num %d\n",
1884 				       lnum, offs, node_num);
1885 			else
1886 				pr_err("LEB %d:%d, pnode\n", lnum, offs);
1887 			break;
1888 		}
1889 		case UBIFS_LPT_NNODE:
1890 		{
1891 			int i;
1892 			struct ubifs_nnode nnode;
1893 
1894 			node_len = c->nnode_sz;
1895 			if (c->big_lpt)
1896 				pr_err("LEB %d:%d, nnode num %d, ",
1897 				       lnum, offs, node_num);
1898 			else
1899 				pr_err("LEB %d:%d, nnode, ",
1900 				       lnum, offs);
1901 			err = ubifs_unpack_nnode(c, p, &nnode);
1902 			if (err) {
1903 				pr_err("failed to unpack_node, error %d\n",
1904 				       err);
1905 				break;
1906 			}
1907 			for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1908 				pr_cont("%d:%d", nnode.nbranch[i].lnum,
1909 				       nnode.nbranch[i].offs);
1910 				if (i != UBIFS_LPT_FANOUT - 1)
1911 					pr_cont(", ");
1912 			}
1913 			pr_cont("\n");
1914 			break;
1915 		}
1916 		case UBIFS_LPT_LTAB:
1917 			node_len = c->ltab_sz;
1918 			pr_err("LEB %d:%d, ltab\n", lnum, offs);
1919 			break;
1920 		case UBIFS_LPT_LSAVE:
1921 			node_len = c->lsave_sz;
1922 			pr_err("LEB %d:%d, lsave len\n", lnum, offs);
1923 			break;
1924 		default:
1925 			ubifs_err(c, "LPT node type %d not recognized", node_type);
1926 			goto out;
1927 		}
1928 
1929 		p += node_len;
1930 		len -= node_len;
1931 	}
1932 
1933 	pr_err("(pid %d) finish dumping LEB %d\n", current->pid, lnum);
1934 out:
1935 	vfree(buf);
1936 	return;
1937 }
1938 
1939 /**
1940  * ubifs_dump_lpt_lebs - dump LPT lebs.
1941  * @c: UBIFS file-system description object
1942  *
1943  * This function dumps all LPT LEBs. The caller has to make sure the LPT is
1944  * locked.
1945  */
ubifs_dump_lpt_lebs(const struct ubifs_info * c)1946 void ubifs_dump_lpt_lebs(const struct ubifs_info *c)
1947 {
1948 	int i;
1949 
1950 	pr_err("(pid %d) start dumping all LPT LEBs\n", current->pid);
1951 	for (i = 0; i < c->lpt_lebs; i++)
1952 		dump_lpt_leb(c, i + c->lpt_first);
1953 	pr_err("(pid %d) finish dumping all LPT LEBs\n", current->pid);
1954 }
1955 
1956 /**
1957  * dbg_populate_lsave - debugging version of 'populate_lsave()'
1958  * @c: UBIFS file-system description object
1959  *
1960  * This is a debugging version for 'populate_lsave()' which populates lsave
1961  * with random LEBs instead of useful LEBs, which is good for test coverage.
1962  * Returns zero if lsave has not been populated (this debugging feature is
1963  * disabled) an non-zero if lsave has been populated.
1964  */
dbg_populate_lsave(struct ubifs_info * c)1965 static int dbg_populate_lsave(struct ubifs_info *c)
1966 {
1967 	struct ubifs_lprops *lprops;
1968 	struct ubifs_lpt_heap *heap;
1969 	int i;
1970 
1971 	if (!dbg_is_chk_gen(c))
1972 		return 0;
1973 	if (prandom_u32() & 3)
1974 		return 0;
1975 
1976 	for (i = 0; i < c->lsave_cnt; i++)
1977 		c->lsave[i] = c->main_first;
1978 
1979 	list_for_each_entry(lprops, &c->empty_list, list)
1980 		c->lsave[prandom_u32() % c->lsave_cnt] = lprops->lnum;
1981 	list_for_each_entry(lprops, &c->freeable_list, list)
1982 		c->lsave[prandom_u32() % c->lsave_cnt] = lprops->lnum;
1983 	list_for_each_entry(lprops, &c->frdi_idx_list, list)
1984 		c->lsave[prandom_u32() % c->lsave_cnt] = lprops->lnum;
1985 
1986 	heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
1987 	for (i = 0; i < heap->cnt; i++)
1988 		c->lsave[prandom_u32() % c->lsave_cnt] = heap->arr[i]->lnum;
1989 	heap = &c->lpt_heap[LPROPS_DIRTY - 1];
1990 	for (i = 0; i < heap->cnt; i++)
1991 		c->lsave[prandom_u32() % c->lsave_cnt] = heap->arr[i]->lnum;
1992 	heap = &c->lpt_heap[LPROPS_FREE - 1];
1993 	for (i = 0; i < heap->cnt; i++)
1994 		c->lsave[prandom_u32() % c->lsave_cnt] = heap->arr[i]->lnum;
1995 
1996 	return 1;
1997 }
1998