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