xref: /src/sys/ufs/chfs/chfs_readinode.c

/*	$NetBSD: chfs_readinode.c,v 1.8.4.1 2014/09/08 18:57:58 msaitoh Exp $	*/

/*-
 * Copyright (c) 2010 Department of Software Engineering,
 *		      University of Szeged, Hungary
 * Copyright (C) 2010 David Tengeri <dtengeri (at) inf.u-szeged.hu>
 * Copyright (C) 2010 Tamas Toth <ttoth (at) inf.u-szeged.hu>
 * Copyright (C) 2010 Adam Hoka <ahoka (at) NetBSD.org>
 * All rights reserved.
 *
 * This code is derived from software contributed to The NetBSD Foundation
 * by the Department of Software Engineering, University of Szeged, Hungary
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <sys/buf.h>

#include "chfs.h"

/* tmp node operations */
int chfs_check_td_data(struct chfs_mount *,
    struct chfs_tmp_dnode *);
int chfs_check_td_node(struct chfs_mount *,
    struct chfs_tmp_dnode *);
struct chfs_node_ref *chfs_first_valid_data_ref(struct chfs_node_ref *);
int chfs_add_tmp_dnode_to_tree(struct chfs_mount *,
    struct chfs_readinode_info *,
    struct chfs_tmp_dnode *);
void chfs_add_tmp_dnode_to_tdi(struct chfs_tmp_dnode_info *,
	struct chfs_tmp_dnode *);
void chfs_remove_tmp_dnode_from_tdi(struct chfs_tmp_dnode_info *,
	struct chfs_tmp_dnode *);
static void chfs_kill_td(struct chfs_mount *,
    struct chfs_tmp_dnode *);
static void chfs_kill_tdi(struct chfs_mount *,
    struct chfs_tmp_dnode_info *);
/* frag node operations */
struct chfs_node_frag *new_fragment(struct chfs_full_dnode *,
    uint32_t,
    uint32_t);
int no_overlapping_node(struct rb_tree *, struct chfs_node_frag *,
    struct chfs_node_frag *, uint32_t);
int chfs_add_frag_to_fragtree(struct chfs_mount *,
    struct rb_tree *,
    struct chfs_node_frag *);
void chfs_obsolete_node_frag(struct chfs_mount *,
    struct chfs_node_frag *);
/* general node operations */
int chfs_get_data_nodes(struct chfs_mount *,
    struct chfs_inode *,
    struct chfs_readinode_info *);
int chfs_build_fragtree(struct chfs_mount *,
    struct chfs_inode *,
    struct chfs_readinode_info *);



/* tmp node rbtree operations */
static signed int
tmp_node_compare_nodes(void *ctx, const void *n1, const void *n2)
{
	const struct chfs_tmp_dnode_info *tdi1 = n1;
	const struct chfs_tmp_dnode_info *tdi2 = n2;

	return (tdi1->tmpnode->node->ofs - tdi2->tmpnode->node->ofs);
}

static signed int
tmp_node_compare_key(void *ctx, const void *n, const void *key)
{
	const struct chfs_tmp_dnode_info *tdi = n;
	uint64_t ofs =  *(const uint64_t *)key;

	return (tdi->tmpnode->node->ofs - ofs);
}

const rb_tree_ops_t tmp_node_rbtree_ops = {
	.rbto_compare_nodes = tmp_node_compare_nodes,
	.rbto_compare_key = tmp_node_compare_key,
	.rbto_node_offset = offsetof(struct chfs_tmp_dnode_info, rb_node),
	.rbto_context = NULL
};


/* frag node rbtree operations */
static signed int
frag_compare_nodes(void *ctx, const void *n1, const void *n2)
{
	const struct chfs_node_frag *frag1 = n1;
	const struct chfs_node_frag *frag2 = n2;

	return (frag1->ofs - frag2->ofs);
}

static signed int
frag_compare_key(void *ctx, const void *n, const void *key)
{
	const struct chfs_node_frag *frag = n;
	uint64_t ofs = *(const uint64_t *)key;

	return (frag->ofs - ofs);
}

const rb_tree_ops_t frag_rbtree_ops = {
	.rbto_compare_nodes = frag_compare_nodes,
	.rbto_compare_key   = frag_compare_key,
	.rbto_node_offset = offsetof(struct chfs_node_frag, rb_node),
	.rbto_context = NULL
};


/*
 * chfs_check_td_data - checks the data CRC of the node
 *
 * Returns: 0 - if everything OK;
 * 	    	1 - if CRC is incorrect;
 * 	    	2 - else;
 *	    	error code if an error occured.
 */
int
chfs_check_td_data(struct chfs_mount *chmp,
    struct chfs_tmp_dnode *td)
{
	int err;
	size_t retlen, len, totlen;
	uint32_t crc;
	uint64_t ofs;
	char *buf;
	struct chfs_node_ref *nref = td->node->nref;

	KASSERT(mutex_owned(&chmp->chm_lock_mountfields));
	KASSERT(!mutex_owned(&chmp->chm_lock_sizes));

	ofs = CHFS_GET_OFS(nref->nref_offset) + sizeof(struct chfs_flash_data_node);
	len = td->node->size;
	if (!len)
		return 0;

	/* Read data. */
	buf = kmem_alloc(len, KM_SLEEP);
	if (!buf) {
		dbg("allocating error\n");
		return 2;
	}
	err = chfs_read_leb(chmp, nref->nref_lnr, buf, ofs, len, &retlen);
	if (err) {
		dbg("error while reading: %d\n", err);
		err = 2;
		goto out;
	}

	/* Check crc. */
	if (len != retlen) {
		dbg("len:%zu, retlen:%zu\n", len, retlen);
		err = 2;
		goto out;
	}
	crc = crc32(0, (uint8_t *)buf, len);

	if (crc != td->data_crc) {
		dbg("crc failed, calculated: 0x%x, orig: 0x%x\n", crc, td->data_crc);
		kmem_free(buf, len);
		return 1;
	}

	/* Correct sizes. */
	CHFS_MARK_REF_NORMAL(nref);
	totlen = CHFS_PAD(sizeof(struct chfs_flash_data_node) + len);

	mutex_enter(&chmp->chm_lock_sizes);
	chfs_change_size_unchecked(chmp, &chmp->chm_blocks[nref->nref_lnr], -totlen);
	chfs_change_size_used(chmp, &chmp->chm_blocks[nref->nref_lnr], totlen);
	mutex_exit(&chmp->chm_lock_sizes);
	KASSERT(chmp->chm_blocks[nref->nref_lnr].used_size <= chmp->chm_ebh->eb_size);

	err = 0;
out:
	kmem_free(buf, len);
	return err;
}

/* chfs_check_td_node - checks a temporary node */
int
chfs_check_td_node(struct chfs_mount *chmp, struct chfs_tmp_dnode *td)
{
	int ret;

	if (CHFS_REF_FLAGS(td->node->nref) != CHFS_UNCHECKED_NODE_MASK)
		return 0;

	ret = chfs_check_td_data(chmp, td);
	return ret;
}

/*
 * chfs_first_valid_data_ref -
 * returns the first valid nref after the given nref
 */
struct chfs_node_ref *
chfs_first_valid_data_ref(struct chfs_node_ref *nref)
{
	while (nref) {
		if (!CHFS_REF_OBSOLETE(nref)) {
#ifdef DGB_MSG_GC
			if (nref->nref_lnr == REF_EMPTY_NODE) {
				dbg("FIRST VALID IS EMPTY!\n");
			}
#endif
			return nref;
		}

		if (nref->nref_next) {
			nref = nref->nref_next;
		} else
			break;
	}
	return NULL;
}

/*
 * chfs_add_tmp_dnode_to_tdi -
 * adds a temporary node to a temporary node descriptor
 */
void
chfs_add_tmp_dnode_to_tdi(struct chfs_tmp_dnode_info *tdi,
	struct chfs_tmp_dnode *td)
{
	if (!tdi->tmpnode) {
	/* The chain is empty. */
		tdi->tmpnode = td;
	} else {
	/* Insert into the chain. */
		struct chfs_tmp_dnode *tmp = tdi->tmpnode;
		while (tmp->next) {
			tmp = tmp->next;
		}
		tmp->next = td;
	}
}

/*
 * chfs_remove_tmp_dnode_from_tdi -
 * removes a temporary node from its descriptor
 */
void
chfs_remove_tmp_dnode_from_tdi(struct chfs_tmp_dnode_info *tdi,
	struct chfs_tmp_dnode *td)
{
	if (tdi->tmpnode == td) {
	/* It's the first in the chain. */
		tdi->tmpnode = tdi->tmpnode->next;
	} else {
	/* Remove from the middle of the chain. */
		struct chfs_tmp_dnode *tmp = tdi->tmpnode->next;
		while (tmp->next && tmp->next != td) {
			tmp = tmp->next;
		}
		if (tmp->next) {
			tmp->next = td->next;
		}
	}
}

/* chfs_kill_td - removes all components of a temporary node */
static void
chfs_kill_td(struct chfs_mount *chmp,
    struct chfs_tmp_dnode *td)
{
	struct chfs_vnode_cache *vc;
	if (td->node) {
		mutex_enter(&chmp->chm_lock_vnocache);
		/* Remove the node from the vnode cache's data node chain. */
		vc = chfs_nref_to_vc(td->node->nref);
		chfs_remove_and_obsolete(chmp, vc, td->node->nref, &vc->dnode);
		mutex_exit(&chmp->chm_lock_vnocache);
	}

	chfs_free_tmp_dnode(td);
}

/* chfs_kill_tdi - removes a temporary node descriptor */
static void
chfs_kill_tdi(struct chfs_mount *chmp,
    struct chfs_tmp_dnode_info *tdi)
{
	struct chfs_tmp_dnode *next, *tmp = tdi->tmpnode;

	/* Iterate the chain and remove all temporary node from it. */
	while (tmp) {
		next = tmp->next;
		chfs_kill_td(chmp, tmp);
		tmp = next;
	}

	chfs_free_tmp_dnode_info(tdi);
}

/*
 * chfs_add_tmp_dnode_to_tree -
 * adds a temporary node to the temporary tree
 */
int
chfs_add_tmp_dnode_to_tree(struct chfs_mount *chmp,
    struct chfs_readinode_info *rii,
    struct chfs_tmp_dnode *newtd)
{
	uint64_t end_ofs = newtd->node->ofs + newtd->node->size;
	struct chfs_tmp_dnode_info *this;
	struct rb_node *node, *prev_node;
	struct chfs_tmp_dnode_info *newtdi;

	node = rb_tree_find_node(&rii->tdi_root, &newtd->node->ofs);
	if (node) {
		this = (struct chfs_tmp_dnode_info *)node;
		while (this->tmpnode->overlapped) {
			prev_node = rb_tree_iterate(&rii->tdi_root, node, RB_DIR_LEFT);
			if (!prev_node) {
				this->tmpnode->overlapped = 0;
				break;
			}
			node = prev_node;
			this = (struct chfs_tmp_dnode_info *)node;
		}
	}

	while (node) {
		this = (struct chfs_tmp_dnode_info *)node;
		if (this->tmpnode->node->ofs > end_ofs)
			break;

		struct chfs_tmp_dnode *tmp_td = this->tmpnode;
		while (tmp_td) {
			if (tmp_td->version == newtd->version) {
				/* This is a new version of an old node. */
				if (!chfs_check_td_node(chmp, tmp_td)) {
					dbg("calling kill td 0\n");
					chfs_kill_td(chmp, newtd);
					return 0;
				} else {
					chfs_remove_tmp_dnode_from_tdi(this, tmp_td);
					chfs_kill_td(chmp, tmp_td);
					chfs_add_tmp_dnode_to_tdi(this, newtd);
					return 0;
				}
			}
			if (tmp_td->version < newtd->version &&
				tmp_td->node->ofs >= newtd->node->ofs &&
				tmp_td->node->ofs + tmp_td->node->size <= end_ofs) {
				/* New node entirely overlaps 'this' */
				if (chfs_check_td_node(chmp, newtd)) {
					dbg("calling kill td 2\n");
					chfs_kill_td(chmp, newtd);
					return 0;
				}
				/* ... and is good. Kill 'this' and any subsequent nodes which are also overlapped */
				while (tmp_td && tmp_td->node->ofs + tmp_td->node->size <= end_ofs) {
					struct rb_node *next = rb_tree_iterate(&rii->tdi_root, this, RB_DIR_RIGHT);
					struct chfs_tmp_dnode_info *next_tdi = (struct chfs_tmp_dnode_info *)next;
					struct chfs_tmp_dnode *next_td = NULL;
					if (tmp_td->next) {
						next_td = tmp_td->next;
					} else if (next_tdi) {
						next_td = next_tdi->tmpnode;
					}
					if (tmp_td->version < newtd->version) {
						chfs_remove_tmp_dnode_from_tdi(this, tmp_td);
						chfs_kill_td(chmp, tmp_td);
						if (!this->tmpnode) {
							rb_tree_remove_node(&rii->tdi_root, this);
							chfs_kill_tdi(chmp, this);
							this = next_tdi;
						}
					}
					tmp_td = next_td;
				}
				continue;
			}
			if (tmp_td->version > newtd->version &&
				tmp_td->node->ofs <= newtd->node->ofs &&
				tmp_td->node->ofs + tmp_td->node->size >= end_ofs) {
				/* New node entirely overlapped by 'this' */
				if (!chfs_check_td_node(chmp, tmp_td)) {
					dbg("this version: %llu\n",
						(unsigned long long)tmp_td->version);
					dbg("this ofs: %llu, size: %u\n",
						(unsigned long long)tmp_td->node->ofs,
						tmp_td->node->size);
					dbg("calling kill td 4\n");
					chfs_kill_td(chmp, newtd);
					return 0;
				}
				/* ... but 'this' was bad. Replace it... */
				chfs_remove_tmp_dnode_from_tdi(this, tmp_td);
				chfs_kill_td(chmp, tmp_td);
				if (!this->tmpnode) {
					rb_tree_remove_node(&rii->tdi_root, this);
					chfs_kill_tdi(chmp, this);
				}
				dbg("calling kill td 5\n");
				chfs_kill_td(chmp, newtd);
				break;
			}
			tmp_td = tmp_td->next;
		}
		node = rb_tree_iterate(&rii->tdi_root, node, RB_DIR_RIGHT);
	}

	newtdi = chfs_alloc_tmp_dnode_info();
	chfs_add_tmp_dnode_to_tdi(newtdi, newtd);
	/* We neither completely obsoleted nor were completely
	   obsoleted by an earlier node. Insert into the tree */
	struct chfs_tmp_dnode_info *tmp_tdi = rb_tree_insert_node(&rii->tdi_root, newtdi);
	if (tmp_tdi != newtdi) {
		chfs_remove_tmp_dnode_from_tdi(newtdi, newtd);
		chfs_add_tmp_dnode_to_tdi(tmp_tdi, newtd);
		chfs_kill_tdi(chmp, newtdi);
	}

	/* If there's anything behind that overlaps us, note it */
	node = rb_tree_iterate(&rii->tdi_root, node, RB_DIR_LEFT);
	if (node) {
		while (1) {
			this = (struct chfs_tmp_dnode_info *)node;
			if (this->tmpnode->node->ofs + this->tmpnode->node->size > newtd->node->ofs) {
				newtd->overlapped = 1;
			}
			if (!this->tmpnode->overlapped)
				break;

			prev_node = rb_tree_iterate(&rii->tdi_root, node, RB_DIR_LEFT);
			if (!prev_node) {
				this->tmpnode->overlapped = 0;
				break;
			}
			node = prev_node;
		}
	}

	/* If the new node overlaps anything ahead, note it */
	node = rb_tree_iterate(&rii->tdi_root, node, RB_DIR_RIGHT);
	this = (struct chfs_tmp_dnode_info *)node;
	while (this && this->tmpnode->node->ofs < end_ofs) {
		this->tmpnode->overlapped = 1;
		node = rb_tree_iterate(&rii->tdi_root, node, RB_DIR_RIGHT);
		this = (struct chfs_tmp_dnode_info *)node;
	}
	return 0;
}


/* new_fragment - creates a new fragment for a data node */
struct chfs_node_frag *
new_fragment(struct chfs_full_dnode *fdn, uint32_t ofs, uint32_t size)
{
	struct chfs_node_frag *newfrag;
	newfrag = chfs_alloc_node_frag();
	if (newfrag) {
		/* Initialize fragment. */
		newfrag->ofs = ofs;
		newfrag->size = size;
		newfrag->node = fdn;
		if (newfrag->node) {
			newfrag->node->frags++;
		}
	} else {
		chfs_err("cannot allocate a chfs_node_frag object\n");
	}
	return newfrag;
}

/*
 * no_overlapping_node - inserts a node to the fragtree
 * Puts hole frag into the holes between fragments.
 */
int
no_overlapping_node(struct rb_tree *fragtree,
    struct chfs_node_frag *newfrag,
    struct chfs_node_frag *this, uint32_t lastend)
{
	if (lastend < newfrag->node->ofs) {
		struct chfs_node_frag *holefrag;

		holefrag = new_fragment(NULL, lastend, newfrag->node->ofs - lastend);
		if (!holefrag) {
			chfs_free_node_frag(newfrag);
			return ENOMEM;
		}

		rb_tree_insert_node(fragtree, holefrag);
	}

	rb_tree_insert_node(fragtree, newfrag);

	return 0;
}

/*
 * chfs_add_frag_to_fragtree -
 * adds a fragment to a data node's fragtree
 */
int
chfs_add_frag_to_fragtree(struct chfs_mount *chmp,
    struct rb_tree *fragtree,
    struct chfs_node_frag *newfrag)
{
	struct chfs_node_frag *this;
	uint32_t lastend;
	KASSERT(mutex_owned(&chmp->chm_lock_mountfields));

	/* Find the offset of frag which is before the new one. */
	this = (struct chfs_node_frag *)rb_tree_find_node_leq(fragtree, &newfrag->ofs);

	if (this) {
		lastend = this->ofs + this->size;
	} else {
		lastend = 0;
	}

	/* New fragment is end of the file and there is no overlapping. */
	if (lastend <= newfrag->ofs) {
		if (lastend && (lastend - 1) >> PAGE_SHIFT == newfrag->ofs >> PAGE_SHIFT) {
			if (this->node)
				CHFS_MARK_REF_NORMAL(this->node->nref);
			CHFS_MARK_REF_NORMAL(newfrag->node->nref);
		}
		return no_overlapping_node(fragtree, newfrag, this, lastend);
	}

	if (newfrag->ofs > this->ofs) {
		CHFS_MARK_REF_NORMAL(newfrag->node->nref);
		if (this->node)
			CHFS_MARK_REF_NORMAL(this->node->nref);

		if (this->ofs + this->size > newfrag->ofs + newfrag->size) {
			/* Newfrag is inside of this. */
			struct chfs_node_frag *newfrag2;

			newfrag2 = new_fragment(this->node, newfrag->ofs + newfrag->size,
			    this->ofs + this->size - newfrag->ofs - newfrag->size);
			if (!newfrag2)
				return ENOMEM;

			this->size = newfrag->ofs - this->ofs;

			rb_tree_insert_node(fragtree, newfrag);
			rb_tree_insert_node(fragtree, newfrag2);

			return 0;
		}
		/* Newfrag is bottom of this. */
		this->size = newfrag->ofs - this->ofs;
		rb_tree_insert_node(fragtree, newfrag);
	} else {
		/* Newfrag start at same point */
		//TODO replace instead of remove and insert
		rb_tree_remove_node(fragtree, this);
		rb_tree_insert_node(fragtree, newfrag);

		if (newfrag->ofs + newfrag->size >= this->ofs+this->size) {
			chfs_obsolete_node_frag(chmp, this);
		} else {
			this->ofs += newfrag->size;
			this->size -= newfrag->size;

			rb_tree_insert_node(fragtree, this);
			return 0;
		}
	}
	/* OK, now we have newfrag added in the correct place in the tree, but
	   frag_next(newfrag) may be a fragment which is overlapped by it
	*/
	while ((this = frag_next(fragtree, newfrag)) && newfrag->ofs + newfrag->size >= this->ofs + this->size) {
		rb_tree_remove_node(fragtree, this);
		chfs_obsolete_node_frag(chmp, this);
	}

	if (!this || newfrag->ofs + newfrag->size == this->ofs)
		return 0;

	this->size = (this->ofs + this->size) - (newfrag->ofs + newfrag->size);
	this->ofs = newfrag->ofs + newfrag->size;

	if (this->node)
		CHFS_MARK_REF_NORMAL(this->node->nref);
	CHFS_MARK_REF_NORMAL(newfrag->node->nref);

	return 0;
}

/*
 * chfs_remove_frags_of_node -
 * removes all fragments from a fragtree and DOESN'T OBSOLETE them
 */
void
chfs_remove_frags_of_node(struct chfs_mount *chmp, struct rb_tree *fragtree,
	struct chfs_node_ref *nref)
{
	KASSERT(mutex_owned(&chmp->chm_lock_mountfields));
	struct chfs_node_frag *this, *next;

	if (nref == NULL) {
		return;
	}

	/* Iterate the tree and clean all elements. */
	this = (struct chfs_node_frag *)RB_TREE_MIN(fragtree);
	while (this) {
		next = frag_next(fragtree, this);
		if (this->node->nref == nref) {
			rb_tree_remove_node(fragtree, this);
			chfs_free_node_frag(this);
		}
		this = next;
	}
}

/*
 * chfs_kill_fragtree -
 * removes all fragments from a fragtree and OBSOLETES them
 */
void
chfs_kill_fragtree(struct chfs_mount *chmp, struct rb_tree *fragtree)
{
	KASSERT(mutex_owned(&chmp->chm_lock_mountfields));
	struct chfs_node_frag *this, *next;

	/* Iterate the tree and clean all elements. */
	this = (struct chfs_node_frag *)RB_TREE_MIN(fragtree);
	while (this) {
		next = frag_next(fragtree, this);
		rb_tree_remove_node(fragtree, this);
		chfs_obsolete_node_frag(chmp, this);
		this = next;
	}
}

/* chfs_truncate_fragtree - truncates the tree to a specified size */
uint32_t
chfs_truncate_fragtree(struct chfs_mount *chmp,
	struct rb_tree *fragtree, uint32_t size)
{
	KASSERT(mutex_owned(&chmp->chm_lock_mountfields));
	struct chfs_node_frag *frag;

	dbg("truncate to size: %u\n", size);

	frag = (struct chfs_node_frag *)rb_tree_find_node_leq(fragtree, &size);

	/* Find the last frag before size and set its new size. */
	if (frag && frag->ofs != size) {
		if (frag->ofs + frag->size > size) {
			frag->size = size - frag->ofs;
		}
		frag = frag_next(fragtree, frag);
	}

	/* Delete frags after new size. */
	while (frag && frag->ofs >= size) {
		struct chfs_node_frag *next = frag_next(fragtree, frag);

		rb_tree_remove_node(fragtree, frag);
		chfs_obsolete_node_frag(chmp, frag);
		frag = next;
	}

	if (size == 0) {
		return 0;
	}

	frag = frag_last(fragtree);

	if (!frag) {
		return 0;
	}

	if (frag->ofs + frag->size < size) {
		return frag->ofs + frag->size;
	}

	/* FIXME Should we check the postion of the last node? (PAGE_CACHE size, etc.) */
	if (frag->node && (frag->ofs & (PAGE_SIZE - 1)) == 0) {
		frag->node->nref->nref_offset =
			CHFS_GET_OFS(frag->node->nref->nref_offset) | CHFS_PRISTINE_NODE_MASK;
	}

	return size;
}

/* chfs_obsolete_node_frag - obsoletes a fragment of a node */
void
chfs_obsolete_node_frag(struct chfs_mount *chmp,
    struct chfs_node_frag *this)
{
	struct chfs_vnode_cache *vc;
	KASSERT(mutex_owned(&chmp->chm_lock_mountfields));
	if (this->node) {
	/* The fragment is in a node. */
		KASSERT(this->node->frags != 0);
		this->node->frags--;
		if (this->node->frags == 0) {
		/* This is the last fragment. (There is no more.) */
			KASSERT(!CHFS_REF_OBSOLETE(this->node->nref));
			mutex_enter(&chmp->chm_lock_vnocache);
			vc = chfs_nref_to_vc(this->node->nref);
			dbg("[MARK] lnr: %u ofs: %u\n", this->node->nref->nref_lnr,
				this->node->nref->nref_offset);

			chfs_remove_and_obsolete(chmp, vc, this->node->nref, &vc->dnode);
			mutex_exit(&chmp->chm_lock_vnocache);

			chfs_free_full_dnode(this->node);
		} else {
		/* There is more frags in the node. */
			CHFS_MARK_REF_NORMAL(this->node->nref);
		}
	}
	chfs_free_node_frag(this);
}

/* chfs_add_full_dnode_to_inode - adds a data node to an inode */
int
chfs_add_full_dnode_to_inode(struct chfs_mount *chmp,
    struct chfs_inode *ip,
    struct chfs_full_dnode *fd)
{
	int ret;
	struct chfs_node_frag *newfrag;
	KASSERT(mutex_owned(&chmp->chm_lock_mountfields));

	if (unlikely(!fd->size))
		return 0;

	/* Create a new fragment from the data node and add it to the fragtree. */
	newfrag = new_fragment(fd, fd->ofs, fd->size);
	if (unlikely(!newfrag))
		return ENOMEM;

	ret = chfs_add_frag_to_fragtree(chmp, &ip->fragtree, newfrag);
	if (ret)
		return ret;

	/* Check previous fragment. */
	if (newfrag->ofs & (PAGE_SIZE - 1)) {
		struct chfs_node_frag *prev = frag_prev(&ip->fragtree, newfrag);

		CHFS_MARK_REF_NORMAL(fd->nref);
		if (prev->node)
			CHFS_MARK_REF_NORMAL(prev->node->nref);
	}

	/* Check next fragment. */
	if ((newfrag->ofs+newfrag->size) & (PAGE_SIZE - 1)) {
		struct chfs_node_frag *next = frag_next(&ip->fragtree, newfrag);

		if (next) {
			CHFS_MARK_REF_NORMAL(fd->nref);
			if (next->node)
				CHFS_MARK_REF_NORMAL(next->node->nref);
		}
	}

	return 0;
}


/* chfs_get_data_nodes - get temporary nodes of an inode */
int
chfs_get_data_nodes(struct chfs_mount *chmp,
    struct chfs_inode *ip,
    struct chfs_readinode_info *rii)
{
	uint32_t crc;
	int err;
	size_t len, retlen;
	struct chfs_node_ref *nref;
	struct chfs_flash_data_node *dnode;
	struct chfs_tmp_dnode *td;
	char* buf;

	len = sizeof(struct chfs_flash_data_node);
	buf = kmem_alloc(len, KM_SLEEP);

	dnode = kmem_alloc(len, KM_SLEEP);
	if (!dnode) {
		kmem_free(buf, len);
		return ENOMEM;
	}

	nref = chfs_first_valid_data_ref(ip->chvc->dnode);

	/* Update highest version. */
	rii->highest_version = ip->chvc->highest_version;

	while(nref && (struct chfs_vnode_cache *)nref != ip->chvc) {
		err = chfs_read_leb(chmp, nref->nref_lnr, buf, CHFS_GET_OFS(nref->nref_offset), len, &retlen);
		if (err || len != retlen)
			goto out;
		dnode = (struct chfs_flash_data_node*)buf;

		/* Check header crc. */
		crc = crc32(0, (uint8_t *)dnode, CHFS_NODE_HDR_SIZE - 4);
		if (crc != le32toh(dnode->hdr_crc)) {
			chfs_err("CRC check failed. calc: 0x%x orig: 0x%x\n", crc, le32toh(dnode->hdr_crc));
			goto cont;
		}

		/* Check header magic bitmask. */
		if (le16toh(dnode->magic) != CHFS_FS_MAGIC_BITMASK) {
			chfs_err("Wrong magic bitmask.\n");
			goto cont;
		}

		/* Check node crc. */
		crc = crc32(0, (uint8_t *)dnode, sizeof(*dnode) - 4);
		if (crc != le32toh(dnode->node_crc)) {
			chfs_err("Node CRC check failed. calc: 0x%x orig: 0x%x\n", crc, le32toh(dnode->node_crc));
			goto cont;
		}

		td = chfs_alloc_tmp_dnode();
		if (!td) {
			chfs_err("Can't allocate tmp dnode info.\n");
			err = ENOMEM;
			goto out;
		}

		/* We don't check data crc here, just add nodes to tmp frag tree, because
		 * we don't want to check nodes which have been overlapped by a new node
		 * with a higher version number.
		 */
		td->node = chfs_alloc_full_dnode();
		if (!td->node) {
			chfs_err("Can't allocate full dnode info.\n");
			err = ENOMEM;
			goto out_tmp_dnode;
		}
		td->version = le64toh(dnode->version);
		td->node->ofs = le64toh(dnode->offset);
		td->data_crc = le32toh(dnode->data_crc);
		td->node->nref = nref;
		td->node->size = le32toh(dnode->data_length);
		td->node->frags = 1;
		td->overlapped = 0;

		if (td->version > rii->highest_version) {
			rii->highest_version = td->version;
		}

		/* Add node to the tree. */
		err = chfs_add_tmp_dnode_to_tree(chmp, rii, td);
		if (err)
			goto out_full_dnode;

cont:
		nref = chfs_first_valid_data_ref(nref->nref_next);
	}

	ip->chvc->highest_version = rii->highest_version;
	return 0;

out_full_dnode:
	chfs_free_full_dnode(td->node);
out_tmp_dnode:
	chfs_free_tmp_dnode(td);
out:
	kmem_free(buf, len);
	kmem_free(dnode, len);
	return err;
}


/* chfs_build_fragtree - builds fragtree from temporary tree */
int
chfs_build_fragtree(struct chfs_mount *chmp, struct chfs_inode *ip,
    struct chfs_readinode_info *rii)
{
	struct chfs_tmp_dnode_info *pen, *last, *this;
	struct rb_tree ver_tree;    /* version tree, used only temporary */
	uint64_t high_ver = 0;
	KASSERT(mutex_owned(&chmp->chm_lock_mountfields));

	rb_tree_init(&ver_tree, &tmp_node_rbtree_ops);

	/* Update highest version and latest node reference. */
	if (rii->mdata_tn) {
		high_ver = rii->mdata_tn->tmpnode->version;
		rii->latest_ref = rii->mdata_tn->tmpnode->node->nref;
	}

	/* Iterate the temporary tree in reverse order. */
	pen = (struct chfs_tmp_dnode_info *)RB_TREE_MAX(&rii->tdi_root);

	while((last = pen)) {
		pen = (struct chfs_tmp_dnode_info *)rb_tree_iterate(&rii->tdi_root, last, RB_DIR_LEFT);

		/* We build here a version tree from overlapped nodes. */
		rb_tree_remove_node(&rii->tdi_root, last);
		rb_tree_insert_node(&ver_tree, last);

		if (last->tmpnode->overlapped) {
			if (pen)
				continue;

			last->tmpnode->overlapped = 0;
		}

		this = (struct chfs_tmp_dnode_info *)RB_TREE_MAX(&ver_tree);

		/* Start to build the fragtree. */
		while (this) {
			struct chfs_tmp_dnode_info *vers_next;
			int ret;

			vers_next = (struct chfs_tmp_dnode_info *)rb_tree_iterate(&ver_tree, this, RB_DIR_LEFT);
			rb_tree_remove_node(&ver_tree, this);

			struct chfs_tmp_dnode *tmp_td = this->tmpnode;
			while (tmp_td) {
				struct chfs_tmp_dnode *next_td = tmp_td->next;

				/* Check temporary node. */
				if (chfs_check_td_node(chmp, tmp_td)) {
					if (next_td) {
						chfs_remove_tmp_dnode_from_tdi(this, tmp_td);
						chfs_kill_td(chmp, tmp_td);
					} else {
						break;
					}
				} else {
					if (tmp_td->version > high_ver) {
						high_ver = tmp_td->version;
						dbg("highver: %llu\n", (unsigned long long)high_ver);
						rii->latest_ref = tmp_td->node->nref;
					}

					/* Add node to inode and its fragtree. */
					ret = chfs_add_full_dnode_to_inode(chmp, ip, tmp_td->node);
					if (ret) {
						/* On error, clean the whole version tree. */
						while (1) {
							vers_next = (struct chfs_tmp_dnode_info *)rb_tree_iterate(&ver_tree, this, RB_DIR_LEFT);
							while (tmp_td) {
								next_td = tmp_td->next;

								chfs_free_full_dnode(tmp_td->node);
								chfs_remove_tmp_dnode_from_tdi(this, tmp_td);
								chfs_kill_td(chmp, tmp_td);
								tmp_td = next_td;
							}
							chfs_free_tmp_dnode_info(this);
							this = vers_next;
							if (!this)
								break;
							rb_tree_remove_node(&ver_tree, vers_next);
							chfs_kill_tdi(chmp, vers_next);
						}
						return ret;
					}

					/* Remove temporary node from temporary descriptor.
					 * Shouldn't obsolete tmp_td here, because tmp_td->node
					 * was added to the inode. */
					chfs_remove_tmp_dnode_from_tdi(this, tmp_td);
					chfs_free_tmp_dnode(tmp_td);
				}
				tmp_td = next_td;
			}
			/* Continue with the previous element of version tree. */
			chfs_kill_tdi(chmp, this);
			this = vers_next;
		}
	}

	return 0;
}

/* chfs_read_inode - checks the state of the inode then reads and builds it */
int chfs_read_inode(struct chfs_mount *chmp, struct chfs_inode *ip)
{
	struct chfs_vnode_cache *vc = ip->chvc;

	KASSERT(mutex_owned(&chmp->chm_lock_mountfields));

retry:
	mutex_enter(&chmp->chm_lock_vnocache);
	switch (vc->state) {
		case VNO_STATE_UNCHECKED:
			/* FALLTHROUGH */
		case VNO_STATE_CHECKEDABSENT:
			vc->state = VNO_STATE_READING;
			break;
		case VNO_STATE_CHECKING:
			/* FALLTHROUGH */
		case VNO_STATE_GC:
			mutex_exit(&chmp->chm_lock_vnocache);
			goto retry;
			break;
		case VNO_STATE_PRESENT:
			/* FALLTHROUGH */
		case VNO_STATE_READING:
			chfs_err("Reading inode #%llu in state %d!\n",
				(unsigned long long)vc->vno, vc->state);
			chfs_err("wants to read a nonexistent ino %llu\n",
				(unsigned long long)vc->vno);
			return ENOENT;
		default:
			panic("BUG() Bad vno cache state.");
	}
	mutex_exit(&chmp->chm_lock_vnocache);

	return chfs_read_inode_internal(chmp, ip);
}

/*
 * chfs_read_inode_internal - reads and builds an inode
 * Firstly get temporary nodes then build fragtree.
 */
int
chfs_read_inode_internal(struct chfs_mount *chmp, struct chfs_inode *ip)
{
	int err;
	size_t len, retlen;
	char* buf;
	struct chfs_readinode_info rii;
	struct chfs_flash_vnode *fvnode;

	KASSERT(mutex_owned(&chmp->chm_lock_mountfields));

	len = sizeof(*fvnode);

	memset(&rii, 0, sizeof(rii));

	rb_tree_init(&rii.tdi_root, &tmp_node_rbtree_ops);

	/* Build a temporary node tree. */
	err = chfs_get_data_nodes(chmp, ip, &rii);
	if (err) {
		if (ip->chvc->state == VNO_STATE_READING)
			ip->chvc->state = VNO_STATE_CHECKEDABSENT;
		/* FIXME Should we kill fragtree or something here? */
		return err;
	}

	/* Build fragtree from temp nodes. */
	rb_tree_init(&ip->fragtree, &frag_rbtree_ops);

	err = chfs_build_fragtree(chmp, ip, &rii);
	if (err) {
		if (ip->chvc->state == VNO_STATE_READING)
			ip->chvc->state = VNO_STATE_CHECKEDABSENT;
		/* FIXME Should we kill fragtree or something here? */
		return err;
	}

	if (!rii.latest_ref) {
		return 0;
	}

	buf = kmem_alloc(len, KM_SLEEP);
	if (!buf)
		return ENOMEM;

	/* Set inode size from its vnode information node. */
	err = chfs_read_leb(chmp, ip->chvc->v->nref_lnr, buf, CHFS_GET_OFS(ip->chvc->v->nref_offset), len, &retlen);
	if (err || retlen != len) {
		kmem_free(buf, len);
		return err?err:EIO;
	}

	fvnode = (struct chfs_flash_vnode*)buf;

	dbg("set size from v: %u\n", fvnode->dn_size);
	chfs_set_vnode_size(ITOV(ip), fvnode->dn_size);
	uint32_t retsize = chfs_truncate_fragtree(chmp, &ip->fragtree, fvnode->dn_size);
	if (retsize != fvnode->dn_size) {
		dbg("Truncating failed. It is %u instead of %u\n", retsize, fvnode->dn_size);
	}

	kmem_free(buf, len);

	if (ip->chvc->state == VNO_STATE_READING) {
		ip->chvc->state = VNO_STATE_PRESENT;
	}

	return 0;
}

/* chfs_read_data - reads and checks data of a file */
int
chfs_read_data(struct chfs_mount* chmp, struct vnode *vp,
    struct buf *bp)
{
	off_t ofs;
	struct chfs_node_frag *frag;
	char * buf;
	int err = 0;
	size_t size, retlen;
	uint32_t crc;
	struct chfs_inode *ip = VTOI(vp);
	struct chfs_flash_data_node *dnode;
	struct chfs_node_ref *nref;

	memset(bp->b_data, 0, bp->b_bcount);

	/* Calculate the size of the file from its fragtree. */
	ofs = bp->b_blkno * PAGE_SIZE;
	frag = (struct chfs_node_frag *)rb_tree_find_node_leq(&ip->fragtree, &ofs);

	if (!frag || frag->ofs > ofs || frag->ofs + frag->size <= ofs) {
		bp->b_resid = 0;
		dbg("not found in frag tree\n");
		return 0;
	}

	if (!frag->node) {
		dbg("no node in frag\n");
		return 0;
	}

	nref = frag->node->nref;
	size = sizeof(*dnode) + frag->size;

	buf = kmem_alloc(size, KM_SLEEP);

	/* Read node from flash. */
	dbg("reading from lnr: %u, offset: %u, size: %zu\n", nref->nref_lnr, CHFS_GET_OFS(nref->nref_offset), size);
	err = chfs_read_leb(chmp, nref->nref_lnr, buf, CHFS_GET_OFS(nref->nref_offset), size, &retlen);
	if (err) {
		chfs_err("error after reading: %d\n", err);
		goto out;
	}
	if (retlen != size) {
		chfs_err("retlen: %zu != size: %zu\n", retlen, size);
		err = EIO;
		goto out;
	}

	/* Read data from flash. */
	dnode = (struct chfs_flash_data_node *)buf;
	crc = crc32(0, (uint8_t *)dnode, CHFS_NODE_HDR_SIZE - 4);
	if (crc != le32toh(dnode->hdr_crc)) {
		chfs_err("CRC check failed. calc: 0x%x orig: 0x%x\n", crc, le32toh(dnode->hdr_crc));
		err = EIO;
		goto out;
	}

	/* Check header magic bitmask. */
	if (le16toh(dnode->magic) != CHFS_FS_MAGIC_BITMASK) {
		chfs_err("Wrong magic bitmask.\n");
		err = EIO;
		goto out;
	}

	/* Check crc of node. */
	crc = crc32(0, (uint8_t *)dnode, sizeof(*dnode) - 4);
	if (crc != le32toh(dnode->node_crc)) {
		chfs_err("Node CRC check failed. calc: 0x%x orig: 0x%x\n", crc, le32toh(dnode->node_crc));
		err = EIO;
		goto out;
	}

	/* Check crc of data. */
	crc = crc32(0, (uint8_t *)dnode->data, dnode->data_length);
	if (crc != le32toh(dnode->data_crc)) {
		chfs_err("Data CRC check failed. calc: 0x%x orig: 0x%x\n", crc, le32toh(dnode->data_crc));
		err = EIO;
		goto out;
	}

	memcpy(bp->b_data, dnode->data, dnode->data_length);
	bp->b_resid = 0;

out:
	kmem_free(buf, size);
	return err;
}