/*
* This file is part of UBIFS.
*
* Copyright (C) 2006-2008 Nokia Corporation.
*
* This program is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 as published by
* the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
* more details.
*
* You should have received a copy of the GNU General Public License along with
* this program; if not, write to the Free Software Foundation, Inc., 51
* Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*
* 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(struct ubifs_nnode *nnode)
{
ubifs_assert(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.
* @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(struct ubifs_cnode *cnode)
{
struct ubifs_nnode *nnode;
int i;
ubifs_assert(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((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->nroot);
cnode = c->lpt_cnext;
if (!cnode)
return 0;
cnt += 1;
while (1) {
ubifs_assert(!test_bit(COW_CNODE, &cnode->flags));
__set_bit(COW_CNODE, &cnode->flags);
cnext = next_dirty_cnode(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(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(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(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(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(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
