tnc.rar_The Tree

/* * This file implements TNC (Tree Node Cache) which caches indexing nodes of * the UBIFS B-tree. * * At the moment the locking rules of the TNC tree are quite simple and * straightforward. We just have a mutex and lock it when we traverse the * tree. If a znode is not in memory, we read it from flash while still having * the mutex locked. */ #include <linux/crc32.h> #include <linux/slab.h> #include "ubifs.h" /* * Returned codes of 'matches_name()' and 'fallible_matches_name()' functions. * @NAME_LESS: name corresponding to the first argument is less than second * @NAME_MATCHES: names match * @NAME_GREATER: name corresponding to the second argument is greater than * first * @NOT_ON_MEDIA: node referred by zbranch does not exist on the media * * These constants were introduce to improve readability. */ enum { NAME_LESS = 0, NAME_MATCHES = 1, NAME_GREATER = 2, NOT_ON_MEDIA = 3, }; /** * insert_old_idx - record 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 %0 on success, and a negative error code on failure. * * For recovery, there must always be a complete intact version of the index on * flash at all times. That is called the "old index". It is the index as at the * time of the last successful commit. Many of the index nodes in the old index * may be dirty, but they must not be erased until the next successful commit * (at which point that index becomes the old index). * * That means that the garbage collection and the in-the-gaps method of * committing must be able to determine if an index node is in the old index. * Most of the old index nodes can be found by looking up the TNC using the * 'lookup_znode()' function. However, some of the old index nodes may have * been deleted from the current index or may have been changed so much that * they cannot be easily found. In those cases, an entry is added to an RB-tree. * That is what this function does. The RB-tree is ordered by LEB number and * offset because they uniquely identify the old index node. */ static int insert_old_idx(struct ubifs_info *c, int lnum, int offs) { struct ubifs_old_idx *old_idx, *o; struct rb_node **p, *parent = NULL; old_idx = kmalloc(sizeof(struct ubifs_old_idx), GFP_NOFS); if (unlikely(!old_idx)) return -ENOMEM; old_idx->lnum = lnum; old_idx->offs = offs; p = &c->old_idx.rb_node; while (*p) { parent = *p; o = rb_entry(parent, 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 { ubifs_err("old idx added twice!"); kfree(old_idx); return 0; } } rb_link_node(&old_idx->rb, parent, p); rb_insert_color(&old_idx->rb, &c->old_idx); return 0; } /** * insert_old_idx_znode - record a znode obsoleted since last commit start. * @c: UBIFS file-system description object * @znode: znode of obsoleted index node * * Returns %0 on success, and a negative error code on failure. */ int insert_old_idx_znode(struct ubifs_info *c, struct ubifs_znode *znode) { if (znode->parent) { struct ubifs_zbranch *zbr; zbr = &znode->parent->zbranch[znode->iip]; if (zbr->len) return insert_old_idx(c, zbr->lnum, zbr->offs); } else if (c->zroot.len) return insert_old_idx(c, c->zroot.lnum, c->zroot.offs); return 0; } /** * ins_clr_old_idx_znode - record a znode obsoleted since last commit start. * @c: UBIFS file-system description object * @znode: znode of obsoleted index node * * Returns %0 on success, and a negative error code on failure. */ static int ins_clr_old_idx_znode(struct ubifs_info *c, struct ubifs_znode *znode) { int err; if (znode->parent) { struct ubifs_zbranch *zbr; zbr = &znode->parent->zbranch[znode->iip]; if (zbr->len) { err = insert_old_idx(c, zbr->lnum, zbr->offs); if (err) return err; zbr->lnum = 0; zbr->offs = 0; zbr->len = 0; } } else if (c->zroot.len) { err = insert_old_idx(c, c->zroot.lnum, c->zroot.offs); if (err) return err; c->zroot.lnum = 0; c->zroot.offs = 0; c->zroot.len = 0; } return 0; } /** * destroy_old_idx - destroy the old_idx RB-tree. * @c: UBIFS file-system description object * * During start commit, the old_idx RB-tree is used to avoid overwriting index * nodes that were in the index last commit but have since been deleted. This * is necessary for recovery i.e. the old index must be kept intact until the * new index is successfully written. The old-idx RB-tree is used for the * in-the-gaps method of writing index nodes and is destroyed every commit. */ void destroy_old_idx(struct ubifs_info *c) { struct rb_node *this = c->old_idx.rb_node; struct ubifs_old_idx *old_idx; while (this) { if (this->rb_left) { this = this->rb_left; continue; } else if (this->rb_right) { this = this->rb_right; continue; } old_idx = rb_entry(this, struct ubifs_old_idx, rb); this = rb_parent(this); if (this) { if (this->rb_left == &old_idx->rb) this->rb_left = NULL; else this->rb_right = NULL; } kfree(old_idx); } c->old_idx = RB_ROOT; } /** * copy_znode - copy a dirty znode. * @c: UBIFS file-system description object * @znode: znode to copy * * A dirty znode being committed may not be changed, so it is copied. */ static struct ubifs_znode *copy_znode(struct ubifs_info *c, struct ubifs_znode *znode) { struct ubifs_znode *zn; zn = kmalloc(c->max_znode_sz, GFP_NOFS); if (unlikely(!zn)) return ERR_PTR(-ENOMEM); memcpy(zn, znode, c->max_znode_sz); zn->cnext = NULL; __set_bit(DIRTY_ZNODE, &zn->flags); __clear_bit(COW_ZNODE, &zn->flags); ubifs_assert(!test_bit(OBSOLETE_ZNODE, &znode->flags)); __set_bit(OBSOLETE_ZNODE, &znode->flags); if (znode->level != 0) { int i; const int n = zn->child_cnt; /* The children now have new parent */ for (i = 0; i < n; i++) { struct ubifs_zbranch *zbr = &zn->zbranch[i]; if (zbr->znode) zbr->znode->parent = zn; } } atomic_long_inc(&c->dirty_zn_cnt); return zn; } /** * add_idx_dirt - add dirt due to a dirty znode. * @c: UBIFS file-system description object * @lnum: LEB number of index node * @dirt: size of index node * * This function updates lprops dirty space and the new size of the index. */ static int add_idx_dirt(struct ubifs_info *c, int lnum, int dirt) { c->calc_idx_sz -= ALIGN(dirt, 8); return ubifs_add_dirt(c, lnum, dirt); } /** * dirty_cow_znode - ensure a znode is not being committed. * @c: UBIFS file-system description object * @zbr: branch of znode to check * * Returns dirtied znode on success or negative error code on failure. */ static struct ubifs_znode *dirty_cow_znode(struct ubifs_info *c, struct ubifs_zbranch *zbr) { struct ubifs_znode *znode = zbr->znode; struct ubifs_znode *zn; int err; if (!test_bit(COW_ZNODE, &znode->flags)) { /* znode is not being committed */ if (!test_and_set_bit(DIRTY_ZNODE, &znode->flags)) { atomic_long_inc(&c->dirty_zn_cnt); atomic_long_dec(&c->clean_zn_cnt); atomic_long_dec(&ubifs_clean_zn_cnt); err = add_idx_dirt(c, zbr->lnum, zbr->len); if (unlikely(err)) return ERR_PTR(err); } return znode; } zn = copy_znode(c, znode); if (IS_ERR(zn)) return zn; if (zbr->len) { err = insert_old_idx(c, zbr->lnum, zbr->offs); if (unlikely(err)) return ERR_PTR(err); err = add_idx_dirt(c, zbr->lnum, zbr->len); } else err = 0; zbr->znode = zn; zbr->lnum = 0; zbr->offs = 0; zbr->len = 0; if (unlikely(err)) return ERR_PTR(err); return zn; } /** * lnc_add - add a leaf node to the leaf node cache. * @c: UBIFS file-system description object * @zbr: zbranch of leaf node * @node: leaf node * * Leaf nodes are non-index nodes direct