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