// SPDX-License-Identifier: GPL-2.0-only/* * This file is part of UBIFS. * * Copyright (C) 2006-2008 Nokia Corporation. * * Authors: Adrian Hunter *          Artem Bityutskiy (Битюцкий Артём) */ /* * This file implements commit-related functionality of the LEB properties * subsystem. */ #include <linux/crc16.h>#include <linux/slab.h>#include <linux/random.h>#include "ubifs.h" static int dbg_populate_lsave(struct ubifs_info *c); /** * first_dirty_cnode - find first dirty cnode. * @c: UBIFS file-system description object * @nnode: nnode at which to start * * This function returns the first dirty cnode or %NULL if there is not one. */static struct ubifs_cnode *first_dirty_cnode(const struct ubifs_info *c, struct ubifs_nnode *nnode){	ubifs_assert(c, nnode);	while (1) {		int i, cont = 0; 		for (i = 0; i < UBIFS_LPT_FANOUT; i++) {			struct ubifs_cnode *cnode; 			cnode = nnode->nbranch[i].cnode;			if (cnode &&			    test_bit(DIRTY_CNODE, &cnode->flags)) {				if (cnode->level == 0)					return cnode;				nnode = (struct ubifs_nnode *)cnode;				cont = 1;				break;			}		}		if (!cont)			return (struct ubifs_cnode *)nnode;	}} /** * next_dirty_cnode - find next dirty cnode. * @c: UBIFS file-system description object * @cnode: cnode from which to begin searching * * This function returns the next dirty cnode or %NULL if there is not one. */static struct ubifs_cnode *next_dirty_cnode(const struct ubifs_info *c, struct ubifs_cnode *cnode){	struct ubifs_nnode *nnode;	int i; 	ubifs_assert(c, cnode);	nnode = cnode->parent;	if (!nnode)		return NULL;	for (i = cnode->iip + 1; i < UBIFS_LPT_FANOUT; i++) {		cnode = nnode->nbranch[i].cnode;		if (cnode && test_bit(DIRTY_CNODE, &cnode->flags)) {			if (cnode->level == 0)				return cnode; /* cnode is a pnode */			/* cnode is a nnode */			return first_dirty_cnode(c, (struct ubifs_nnode *)cnode);		}	}	return (struct ubifs_cnode *)nnode;} /** * get_cnodes_to_commit - create list of dirty cnodes to commit. * @c: UBIFS file-system description object * * This function returns the number of cnodes to commit. */static int get_cnodes_to_commit(struct ubifs_info *c){	struct ubifs_cnode *cnode, *cnext;	int cnt = 0; 	if (!c->nroot)		return 0; 	if (!test_bit(DIRTY_CNODE, &c->nroot->flags))		return 0; 	c->lpt_cnext = first_dirty_cnode(c, c->nroot);	cnode = c->lpt_cnext;	if (!cnode)		return 0;	cnt += 1;	while (1) {		ubifs_assert(c, !test_bit(COW_CNODE, &cnode->flags));		__set_bit(COW_CNODE, &cnode->flags);		cnext = next_dirty_cnode(c, cnode);		if (!cnext) {			cnode->cnext = c->lpt_cnext;			break;		}		cnode->cnext = cnext;		cnode = cnext;		cnt += 1;	}	dbg_cmt("committing %d cnodes", cnt);	dbg_lp("committing %d cnodes", cnt);	ubifs_assert(c, cnt == c->dirty_nn_cnt + c->dirty_pn_cnt);	return cnt;} /** * upd_ltab - update LPT LEB properties. * @c: UBIFS file-system description object * @lnum: LEB number * @free: amount of free space * @dirty: amount of dirty space to add */static void upd_ltab(struct ubifs_info *c, int lnum, int free, int dirty){	dbg_lp("LEB %d free %d dirty %d to %d +%d",	       lnum, c->ltab[lnum - c->lpt_first].free,	       c->ltab[lnum - c->lpt_first].dirty, free, dirty);	ubifs_assert(c, lnum >= c->lpt_first && lnum <= c->lpt_last);	c->ltab[lnum - c->lpt_first].free = free;	c->ltab[lnum - c->lpt_first].dirty += dirty;} /** * alloc_lpt_leb - allocate an LPT LEB that is empty. * @c: UBIFS file-system description object * @lnum: LEB number is passed and returned here * * This function finds the next empty LEB in the ltab starting from @lnum. If a * an empty LEB is found it is returned in @lnum and the function returns %0. * Otherwise the function returns -ENOSPC.  Note however, that LPT is designed * never to run out of space. */static int alloc_lpt_leb(struct ubifs_info *c, int *lnum){	int i, n; 	n = *lnum - c->lpt_first + 1;	for (i = n; i < c->lpt_lebs; i++) {		if (c->ltab[i].tgc || c->ltab[i].cmt)			continue;		if (c->ltab[i].free == c->leb_size) {			c->ltab[i].cmt = 1;			*lnum = i + c->lpt_first;			return 0;		}	} 	for (i = 0; i < n; i++) {		if (c->ltab[i].tgc || c->ltab[i].cmt)			continue;		if (c->ltab[i].free == c->leb_size) {			c->ltab[i].cmt = 1;			*lnum = i + c->lpt_first;			return 0;		}	}	return -ENOSPC;} /** * layout_cnodes - layout cnodes for commit. * @c: UBIFS file-system description object * * This function returns %0 on success and a negative error code on failure. */static int layout_cnodes(struct ubifs_info *c){	int lnum, offs, len, alen, done_lsave, done_ltab, err;	struct ubifs_cnode *cnode; 	err = dbg_chk_lpt_sz(c, 0, 0);	if (err)		return err;	cnode = c->lpt_cnext;	if (!cnode)		return 0;	lnum = c->nhead_lnum;	offs = c->nhead_offs;	/* Try to place lsave and ltab nicely */	done_lsave = !c->big_lpt;	done_ltab = 0;	if (!done_lsave && offs + c->lsave_sz <= c->leb_size) {		done_lsave = 1;		c->lsave_lnum = lnum;		c->lsave_offs = offs;		offs += c->lsave_sz;		dbg_chk_lpt_sz(c, 1, c->lsave_sz);	} 	if (offs + c->ltab_sz <= c->leb_size) {		done_ltab = 1;		c->ltab_lnum = lnum;		c->ltab_offs = offs;		offs += c->ltab_sz;		dbg_chk_lpt_sz(c, 1, c->ltab_sz);	} 	do {		if (cnode->level) {			len = c->nnode_sz;			c->dirty_nn_cnt -= 1;		} else {			len = c->pnode_sz;			c->dirty_pn_cnt -= 1;		}		while (offs + len > c->leb_size) {			alen = ALIGN(offs, c->min_io_size);			upd_ltab(c, lnum, c->leb_size - alen, alen - offs);			dbg_chk_lpt_sz(c, 2, c->leb_size - offs);			err = alloc_lpt_leb(c, &lnum);			if (err)				goto no_space;			offs = 0;			ubifs_assert(c, lnum >= c->lpt_first &&				     lnum <= c->lpt_last);			/* Try to place lsave and ltab nicely */			if (!done_lsave) {				done_lsave = 1;				c->lsave_lnum = lnum;				c->lsave_offs = offs;				offs += c->lsave_sz;				dbg_chk_lpt_sz(c, 1, c->lsave_sz);				continue;			}			if (!done_ltab) {				done_ltab = 1;				c->ltab_lnum = lnum;				c->ltab_offs = offs;				offs += c->ltab_sz;				dbg_chk_lpt_sz(c, 1, c->ltab_sz);				continue;			}			break;		}		if (cnode->parent) {			cnode->parent->nbranch[cnode->iip].lnum = lnum;			cnode->parent->nbranch[cnode->iip].offs = offs;		} else {			c->lpt_lnum = lnum;			c->lpt_offs = offs;		}		offs += len;		dbg_chk_lpt_sz(c, 1, len);		cnode = cnode->cnext;	} while (cnode && cnode != c->lpt_cnext); 	/* Make sure to place LPT's save table */	if (!done_lsave) {		if (offs + c->lsave_sz > c->leb_size) {			alen = ALIGN(offs, c->min_io_size);			upd_ltab(c, lnum, c->leb_size - alen, alen - offs);			dbg_chk_lpt_sz(c, 2, c->leb_size - offs);			err = alloc_lpt_leb(c, &lnum);			if (err)				goto no_space;			offs = 0;			ubifs_assert(c, lnum >= c->lpt_first &&				     lnum <= c->lpt_last);		}		done_lsave = 1;		c->lsave_lnum = lnum;		c->lsave_offs = offs;		offs += c->lsave_sz;		dbg_chk_lpt_sz(c, 1, c->lsave_sz);	} 	/* Make sure to place LPT's own lprops table */	if (!done_ltab) {		if (offs + c->ltab_sz > c->leb_size) {			alen = ALIGN(offs, c->min_io_size);			upd_ltab(c, lnum, c->leb_size - alen, alen - offs);			dbg_chk_lpt_sz(c, 2, c->leb_size - offs);			err = alloc_lpt_leb(c, &lnum);			if (err)				goto no_space;			offs = 0;			ubifs_assert(c, lnum >= c->lpt_first &&				     lnum <= c->lpt_last);		}		c->ltab_lnum = lnum;		c->ltab_offs = offs;		offs += c->ltab_sz;		dbg_chk_lpt_sz(c, 1, c->ltab_sz);	} 	alen = ALIGN(offs, c->min_io_size);	upd_ltab(c, lnum, c->leb_size - alen, alen - offs);	dbg_chk_lpt_sz(c, 4, alen - offs);	err = dbg_chk_lpt_sz(c, 3, alen);	if (err)		return err;	return 0; no_space:	ubifs_err(c, "LPT out of space at LEB %d:%d needing %d, done_ltab %d, done_lsave %d",		  lnum, offs, len, done_ltab, done_lsave);	ubifs_dump_lpt_info(c);	ubifs_dump_lpt_lebs(c);	dump_stack();	return err;} /** * realloc_lpt_leb - allocate an LPT LEB that is empty. * @c: UBIFS file-system description object * @lnum: LEB number is passed and returned here * * This function duplicates exactly the results of the function alloc_lpt_leb. * It is used during end commit to reallocate the same LEB numbers that were * allocated by alloc_lpt_leb during start commit. * * This function finds the next LEB that was allocated by the alloc_lpt_leb * function starting from @lnum. If a LEB is found it is returned in @lnum and * the function returns %0. Otherwise the function returns -ENOSPC. * Note however, that LPT is designed never to run out of space. */static int realloc_lpt_leb(struct ubifs_info *c, int *lnum){	int i, n; 	n = *lnum - c->lpt_first + 1;	for (i = n; i < c->lpt_lebs; i++)		if (c->ltab[i].cmt) {			c->ltab[i].cmt = 0;			*lnum = i + c->lpt_first;			return 0;		} 	for (i = 0; i < n; i++)		if (c->ltab[i].cmt) {			c->ltab[i].cmt = 0;			*lnum = i + c->lpt_first;			return 0;		}	return -ENOSPC;} /** * write_cnodes - write cnodes for commit. * @c: UBIFS file-system description object * * This function returns %0 on success and a negative error code on failure. */static int write_cnodes(struct ubifs_info *c){	int lnum, offs, len, from, err, wlen, alen, done_ltab, done_lsave;	struct ubifs_cnode *cnode;	void *buf = c->lpt_buf; 	cnode = c->lpt_cnext;	if (!cnode)		return 0;	lnum = c->nhead_lnum;	offs = c->nhead_offs;	from = offs;	/* Ensure empty LEB is unmapped */	if (offs == 0) {		err = ubifs_leb_unmap(c, lnum);		if (err)			return err;	}	/* Try to place lsave and ltab nicely */	done_lsave = !c->big_lpt;	done_ltab = 0;	if (!done_lsave && offs + c->lsave_sz <= c->leb_size) {		done_lsave = 1;		ubifs_pack_lsave(c, buf + offs, c->lsave);		offs += c->lsave_sz;		dbg_chk_lpt_sz(c, 1, c->lsave_sz);	} 	if (offs + c->ltab_sz <= c->leb_size) {		done_ltab = 1;		ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);		offs += c->ltab_sz;		dbg_chk_lpt_sz(c, 1, c->ltab_sz);	} 	/* Loop for each cnode */	do {		if (cnode->level)			len = c->nnode_sz;		else			len = c->pnode_sz;		while (offs + len > c->leb_size) {			wlen = offs - from;			if (wlen) {				alen = ALIGN(wlen, c->min_io_size);				memset(buf + offs, 0xff, alen - wlen);				err = ubifs_leb_write(c, lnum, buf + from, from,						       alen);				if (err)					return err;			}			dbg_chk_lpt_sz(c, 2, c->leb_size - offs);			err = realloc_lpt_leb(c, &lnum);			if (err)				goto no_space;			offs = from = 0;			ubifs_assert(c, lnum >= c->lpt_first &&				     lnum <= c->lpt_last);			err = ubifs_leb_unmap(c, lnum);			if (err)				return err;			/* Try to place lsave and ltab nicely */			if (!done_lsave) {				done_lsave = 1;				ubifs_pack_lsave(c, buf + offs, c->lsave);				offs += c->lsave_sz;				dbg_chk_lpt_sz(c, 1, c->lsave_sz);				continue;			}			if (!done_ltab) {				done_ltab = 1;				ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);				offs += c->ltab_sz;				dbg_chk_lpt_sz(c, 1, c->ltab_sz);				continue;			}			break;		}		if (cnode->level)			ubifs_pack_nnode(c, buf + offs,					 (struct ubifs_nnode *)cnode);		else			ubifs_pack_pnode(c, buf + offs,					 (struct ubifs_pnode *)cnode);		/*		 * The reason for the barriers is the same as in case of TNC.		 * See comment in 'write_index()'. 'dirty_cow_nnode()' and		 * 'dirty_cow_pnode()' are the functions for which this is		 * important.		 */		clear_bit(DIRTY_CNODE, &cnode->flags);		smp_mb__before_atomic();		clear_bit(COW_CNODE, &cnode->flags);		smp_mb__after_atomic();		offs += len;		dbg_chk_lpt_sz(c, 1, len);		cnode = cnode->cnext;	} while (cnode && cnode != c->lpt_cnext); 	/* Make sure to place LPT's save table */	if (!done_lsave) {		if (offs + c->lsave_sz > c->leb_size) {			wlen = offs - from;			alen = ALIGN(wlen, c->min_io_size);			memset(buf + offs, 0xff, alen - wlen);			err = ubifs_leb_write(c, lnum, buf + from, from, alen);			if (err)				return err;			dbg_chk_lpt_sz(c, 2, c->leb_size - offs);			err = realloc_lpt_leb(c, &lnum);			if (err)				goto no_space;			offs = from = 0;			ubifs_assert(c, lnum >= c->lpt_first &&				     lnum <= c->lpt_last);			err = ubifs_leb_unmap(c, lnum);			if (err)				return err;		}		done_lsave = 1;		ubifs_pack_lsave(c, buf + offs, c->lsave);		offs += c->lsave_sz;		dbg_chk_lpt_sz(c, 1, c->lsave_sz);	} 	/* Make sure to place LPT's own lprops table */	if (!done_ltab) {		if (offs + c->ltab_sz > c->leb_size) {			wlen = offs - from;			alen = ALIGN(wlen, c->min_io_size);			memset(buf + offs, 0xff, alen - wlen);			err = ubifs_leb_write(c, lnum, buf + from, from, alen);			if (err)				return err;			dbg_chk_lpt_sz(c, 2, c->leb_size - offs);			err = realloc_lpt_leb(c, &lnum);			if (err)				goto no_space;			offs = from = 0;			ubifs_assert(c, lnum >= c->lpt_first &&				     lnum <= c->lpt_last);

Lines 1–500 of 1995. Load more