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