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