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