lpt_commit.rar_Commit!

/* * 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