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