tnc_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 TNC functions for committing */ #include <linux/random.h> #include "ubifs.h" /** * make_idx_node - make an index node for fill-the-gaps method of TNC commit. * @c: UBIFS file-system description object * @idx: buffer in which to place new index node * @znode: znode from which to make new index node * @lnum: LEB number where new index node will be written * @offs: offset where new index node will be written * @len: length of new index node */ static int make_idx_node(struct ubifs_info *c, struct ubifs_idx_node *idx, struct ubifs_znode *znode, int lnum, int offs, int len) { struct ubifs_znode *zp; int i, err; /* Make index node */ idx->ch.node_type = UBIFS_IDX_NODE; idx->child_cnt = cpu_to_le16(znode->child_cnt); idx->level = cpu_to_le16(znode->level); for (i = 0; i < znode->child_cnt; i++) { struct ubifs_branch *br = ubifs_idx_branch(c, idx, i); struct ubifs_zbranch *zbr = &znode->zbranch[i]; key_write_idx(c, &zbr->key, &br->key); br->lnum = cpu_to_le32(zbr->lnum); br->offs = cpu_to_le32(zbr->offs); br->len = cpu_to_le32(zbr->len); if (!zbr->lnum || !zbr->len) { ubifs_err("bad ref in znode"); ubifs_dump_znode(c, znode); if (zbr->znode) ubifs_dump_znode(c, zbr->znode); } } ubifs_prepare_node(c, idx, len, 0); znode->lnum = lnum; znode->offs = offs; znode->len = len; err = insert_old_idx_znode(c, znode); /* Update the parent */ zp = znode->parent; if (zp) { struct ubifs_zbranch *zbr; zbr = &zp->zbranch[znode->iip]; zbr->lnum = lnum; zbr->offs = offs; zbr->len = len; } else { c->zroot.lnum = lnum; c->zroot.offs = offs; c->zroot.len = len; } c->calc_idx_sz += ALIGN(len, 8); atomic_long_dec(&c->dirty_zn_cnt); ubifs_assert(ubifs_zn_dirty(znode)); ubifs_assert(ubifs_zn_cow(znode)); /* * Note, unlike 'write_index()' we do not add memory barriers here * because this function is called with @c->tnc_mutex locked. */ __clear_bit(DIRTY_ZNODE, &znode->flags); __clear_bit(COW_ZNODE, &znode->flags); return err; } /** * fill_gap - make index nodes in gaps in dirty index LEBs. * @c: UBIFS file-system description object * @lnum: LEB number that gap appears in * @gap_start: offset of start of gap * @gap_end: offset of end of gap * @dirt: adds dirty space to this * * This function returns the number of index nodes written into the gap. */ static int fill_gap(struct ubifs_info *c, int lnum, int gap_start, int gap_end, int *dirt) { int len, gap_remains, gap_pos, written, pad_len; ubifs_assert((gap_start & 7) == 0); ubifs_assert((gap_end & 7) == 0); ubifs_assert(gap_end >= gap_start); gap_remains = gap_end - gap_start; if (!gap_remains) return 0; gap_pos = gap_start; written = 0; while (c->enext) { len = ubifs_idx_node_sz(c, c->enext->child_cnt); if (len < gap_remains) { struct ubifs_znode *znode = c->enext; const int alen = ALIGN(len, 8); int err; ubifs_assert(alen <= gap_remains); err = make_idx_node(c, c->ileb_buf + gap_pos, znode, lnum, gap_pos, len); if (err) return err; gap_remains -= alen; gap_pos += alen; c->enext = znode->cnext; if (c->enext == c->cnext) c->enext = NULL; written += 1; } else break; } if (gap_end == c->leb_size) { c->ileb_len = ALIGN(gap_pos, c->min_io_size); /* Pad to end of min_io_size */ pad_len = c->ileb_len - gap_pos; } else /* Pad to end of gap */ pad_len = gap_remains; dbg_gc("LEB %d:%d to %d len %d nodes written %d wasted bytes %d", lnum, gap_start, gap_end, gap_end - gap_start, written, pad_len); ubifs_pad(c, c->ileb_buf + gap_pos, pad_len); *dirt += pad_len; return written; } /** * find_old_idx - find an index node obsoleted since the last commit start. * @c: UBIFS file-system description object * @lnum: LEB number of obsoleted index node * @offs: offset of obsoleted index node * * Returns %1 if found and %0 otherwise. */ static int find_old_idx(struct ubifs_info *c, int lnum, int offs) { struct ubifs_old_idx *o; struct rb_node *p; p = c->old_idx.rb_node; while (p) { o = rb_entry(p, struct ubifs_old_idx, rb); if (lnum < o->lnum) p = p->rb_left; else if (lnum > o->lnum) p = p->rb_right; else if (offs < o->offs) p = p->rb_left; else if (offs > o->offs) p = p->rb_right; else return 1; } return 0; } /** * is_idx_node_in_use - determine if an index node can be overwritten. * @c: UBIFS file-system description object * @key: key of index node * @level: index node level * @lnum: LEB number of index node * @offs: offset of index node * * If @key / @lnum / @offs identify an index node that was not part of the old * index, then this function returns %0 (obsolete). Else if the index node was * part of the old index but is now dirty %1 is returned, else if it is clean %2 * is returned. A negative error code is returned on failure. */ static int is_idx_node_in_use(struct ubifs_info *c, union ubifs_key *key, int level, int lnum, int offs) { int ret; ret = is_idx_node_in_tnc(c, key, level, lnum, offs); if (ret < 0) return ret; /* Error code */ if (ret == 0) if (find_old_idx(c, lnum, offs)) return 1; return ret; } /** * layout_leb_in_gaps - layout index nodes using in-the-gaps method. * @c: UBIFS file-system description object * @p: return LEB number here * * This function lays out new index nodes for dirty znodes using in-the-gaps * method of TNC commit. * This function merely puts the next znode into the next gap, making no attempt * to try to maximise the number of znodes that fit. * This function returns the number of index nodes written into the gaps, or a * negative error code on failure. */ static int layout_leb_in_gaps(struct ubifs_info *c, int *p) { struct ubifs_scan_leb *sleb; struct ubifs_scan_node *snod; int lnum, dirt = 0, gap_start, gap_end, err, written, tot_written; tot_written = 0; /* Get an index LEB with lots of obsolete index nodes */ lnum = ubifs_find_dirty_idx_leb(c); if (lnum < 0) /* * There also may be dirt in the index head that could be * filled, however we do not check there at present. */ return lnum; /* Error code */ *p = lnum; dbg_gc("LEB %d", lnum); /* * Scan the index LEB. We use the generic scan for this even though * it is more comprehensive and less efficient than is needed for this * purpose. */ sleb = ubifs_scan(c, lnum, 0, c->ileb_buf, 0); c->ileb_len = 0; if (IS_ERR(sleb)) return PTR_ERR(sleb); gap_start = 0; list_for_each_entry(snod, &sleb->nodes, list) { struct ubifs_idx_node *idx; int in_use, level; ubifs_assert(snod->type == UBIFS_IDX_NODE); idx = snod->node; key_read(c, ubifs_idx_key(c, idx), &snod->key); level = le16_to_cpu(idx->level); /* Determine if the index node is in use (not obsolete) */ in_use = is_idx_node_in_use(c, &snod->key, level, lnum, snod->offs); if (in_use < 0) { ubifs_scan_destroy(sleb); return in_use; /* Error code */ } if (in_use) { if (in_use == 1) dirt += ALIGN(snod->len, 8); /* * The obsolete index nodes form gaps that can be * overwritten. This gap has ended beca