+static int check_tn_node(struct jffs2_sb_info *c, struct jffs2_tmp_dnode_info *tn)
+{
+ int ret;
+
+ BUG_ON(ref_obsolete(tn->fn->raw));
+
+ /* We only check the data CRC of unchecked nodes */
+ if (ref_flags(tn->fn->raw) != REF_UNCHECKED)
+ return 0;
+
+ dbg_readinode("check node %#04x-%#04x, phys offs %#08x\n",
+ tn->fn->ofs, tn->fn->ofs + tn->fn->size, ref_offset(tn->fn->raw));
+
+ ret = check_node_data(c, tn);
+ if (unlikely(ret < 0)) {
+ JFFS2_ERROR("check_node_data() returned error: %d.\n",
+ ret);
+ } else if (unlikely(ret > 0)) {
+ dbg_readinode("CRC error, mark it obsolete.\n");
+ jffs2_mark_node_obsolete(c, tn->fn->raw);
+ }
+
+ return ret;
+}
+
+static struct jffs2_tmp_dnode_info *jffs2_lookup_tn(struct rb_root *tn_root, uint32_t offset)
+{
+ struct rb_node *next;
+ struct jffs2_tmp_dnode_info *tn = NULL;
+
+ dbg_readinode("root %p, offset %d\n", tn_root, offset);
+
+ next = tn_root->rb_node;
+
+ while (next) {
+ tn = rb_entry(next, struct jffs2_tmp_dnode_info, rb);
+
+ if (tn->fn->ofs < offset)
+ next = tn->rb.rb_right;
+ else if (tn->fn->ofs >= offset)
+ next = tn->rb.rb_left;
+ else
+ break;
+ }
+
+ return tn;
+}
+
+
+static void jffs2_kill_tn(struct jffs2_sb_info *c, struct jffs2_tmp_dnode_info *tn)
+{
+ jffs2_mark_node_obsolete(c, tn->fn->raw);
+ jffs2_free_full_dnode(tn->fn);
+ jffs2_free_tmp_dnode_info(tn);
+}
+/*
+ * This function is used when we read an inode. Data nodes arrive in
+ * arbitrary order -- they may be older or newer than the nodes which
+ * are already in the tree. Where overlaps occur, the older node can
+ * be discarded as long as the newer passes the CRC check. We don't
+ * bother to keep track of holes in this rbtree, and neither do we deal
+ * with frags -- we can have multiple entries starting at the same
+ * offset, and the one with the smallest length will come first in the
+ * ordering.
+ *
+ * Returns 0 if the node was handled (including marking it obsolete)
+ * < 0 an if error occurred
+ */
+static int jffs2_add_tn_to_tree(struct jffs2_sb_info *c,
+ struct jffs2_readinode_info *rii,
+ struct jffs2_tmp_dnode_info *tn)
+{
+ uint32_t fn_end = tn->fn->ofs + tn->fn->size;
+ struct jffs2_tmp_dnode_info *this, *ptn;
+
+ dbg_readinode("insert fragment %#04x-%#04x, ver %u at %08x\n", tn->fn->ofs, fn_end, tn->version, ref_offset(tn->fn->raw));
+
+ /* If a node has zero dsize, we only have to keep if it if it might be the
+ node with highest version -- i.e. the one which will end up as f->metadata.
+ Note that such nodes won't be REF_UNCHECKED since there are no data to
+ check anyway. */
+ if (!tn->fn->size) {
+ if (rii->mdata_tn) {
+ if (rii->mdata_tn->version < tn->version) {
+ /* We had a candidate mdata node already */
+ dbg_readinode("kill old mdata with ver %d\n", rii->mdata_tn->version);
+ jffs2_kill_tn(c, rii->mdata_tn);
+ } else {
+ dbg_readinode("kill new mdata with ver %d (older than existing %d\n",
+ tn->version, rii->mdata_tn->version);
+ jffs2_kill_tn(c, tn);
+ return 0;
+ }
+ }
+ rii->mdata_tn = tn;
+ dbg_readinode("keep new mdata with ver %d\n", tn->version);
+ return 0;
+ }
+
+ /* Find the earliest node which _may_ be relevant to this one */
+ this = jffs2_lookup_tn(&rii->tn_root, tn->fn->ofs);
+ if (this) {
+ /* If the node is coincident with another at a lower address,
+ back up until the other node is found. It may be relevant */
+ while (this->overlapped) {
+ ptn = tn_prev(this);
+ if (!ptn) {
+ /*
+ * We killed a node which set the overlapped
+ * flags during the scan. Fix it up.
+ */
+ this->overlapped = 0;
+ break;
+ }
+ this = ptn;
+ }
+ dbg_readinode("'this' found %#04x-%#04x (%s)\n", this->fn->ofs, this->fn->ofs + this->fn->size, this->fn ? "data" : "hole");
+ }
+
+ while (this) {
+ if (this->fn->ofs > fn_end)
+ break;
+ dbg_readinode("Ponder this ver %d, 0x%x-0x%x\n",
+ this->version, this->fn->ofs, this->fn->size);
+
+ if (this->version == tn->version) {
+ /* Version number collision means REF_PRISTINE GC. Accept either of them
+ as long as the CRC is correct. Check the one we have already... */
+ if (!check_tn_node(c, this)) {
+ /* The one we already had was OK. Keep it and throw away the new one */
+ dbg_readinode("Like old node. Throw away new\n");
+ jffs2_kill_tn(c, tn);
+ return 0;
+ } else {
+ /* Who cares if the new one is good; keep it for now anyway. */
+ dbg_readinode("Like new node. Throw away old\n");
+ rb_replace_node(&this->rb, &tn->rb, &rii->tn_root);
+ jffs2_kill_tn(c, this);
+ /* Same overlapping from in front and behind */
+ return 0;
+ }
+ }
+ if (this->version < tn->version &&
+ this->fn->ofs >= tn->fn->ofs &&
+ this->fn->ofs + this->fn->size <= fn_end) {
+ /* New node entirely overlaps 'this' */
+ if (check_tn_node(c, tn)) {
+ dbg_readinode("new node bad CRC\n");
+ jffs2_kill_tn(c, tn);
+ return 0;
+ }
+ /* ... and is good. Kill 'this' and any subsequent nodes which are also overlapped */
+ while (this && this->fn->ofs + this->fn->size <= fn_end) {
+ struct jffs2_tmp_dnode_info *next = tn_next(this);
+ if (this->version < tn->version) {
+ tn_erase(this, &rii->tn_root);
+ dbg_readinode("Kill overlapped ver %d, 0x%x-0x%x\n",
+ this->version, this->fn->ofs,
+ this->fn->ofs+this->fn->size);
+ jffs2_kill_tn(c, this);
+ }
+ this = next;
+ }
+ dbg_readinode("Done killing overlapped nodes\n");
+ continue;
+ }
+ if (this->version > tn->version &&
+ this->fn->ofs <= tn->fn->ofs &&
+ this->fn->ofs+this->fn->size >= fn_end) {
+ /* New node entirely overlapped by 'this' */
+ if (!check_tn_node(c, this)) {
+ dbg_readinode("Good CRC on old node. Kill new\n");
+ jffs2_kill_tn(c, tn);
+ return 0;
+ }
+ /* ... but 'this' was bad. Replace it... */
+ dbg_readinode("Bad CRC on old overlapping node. Kill it\n");
+ tn_erase(this, &rii->tn_root);
+ jffs2_kill_tn(c, this);
+ break;
+ }
+
+ this = tn_next(this);
+ }
+
+ /* We neither completely obsoleted nor were completely
+ obsoleted by an earlier node. Insert into the tree */
+ {
+ struct rb_node *parent;
+ struct rb_node **link = &rii->tn_root.rb_node;
+ struct jffs2_tmp_dnode_info *insert_point = NULL;
+
+ while (*link) {
+ parent = *link;
+ insert_point = rb_entry(parent, struct jffs2_tmp_dnode_info, rb);
+ if (tn->fn->ofs > insert_point->fn->ofs)
+ link = &insert_point->rb.rb_right;
+ else if (tn->fn->ofs < insert_point->fn->ofs ||
+ tn->fn->size < insert_point->fn->size)
+ link = &insert_point->rb.rb_left;
+ else
+ link = &insert_point->rb.rb_right;
+ }
+ rb_link_node(&tn->rb, &insert_point->rb, link);
+ rb_insert_color(&tn->rb, &rii->tn_root);
+ }
+
+ /* If there's anything behind that overlaps us, note it */
+ this = tn_prev(tn);
+ if (this) {
+ while (1) {
+ if (this->fn->ofs + this->fn->size > tn->fn->ofs) {
+ dbg_readinode("Node is overlapped by %p (v %d, 0x%x-0x%x)\n",
+ this, this->version, this->fn->ofs,
+ this->fn->ofs+this->fn->size);
+ tn->overlapped = 1;
+ break;
+ }
+ if (!this->overlapped)
+ break;
+
+ ptn = tn_prev(this);
+ if (!ptn) {
+ /*
+ * We killed a node which set the overlapped
+ * flags during the scan. Fix it up.
+ */
+ this->overlapped = 0;
+ break;
+ }
+ this = ptn;
+ }
+ }
+
+ /* If the new node overlaps anything ahead, note it */
+ this = tn_next(tn);
+ while (this && this->fn->ofs < fn_end) {
+ this->overlapped = 1;
+ dbg_readinode("Node ver %d, 0x%x-0x%x is overlapped\n",
+ this->version, this->fn->ofs,
+ this->fn->ofs+this->fn->size);
+ this = tn_next(this);
+ }
+ return 0;
+}
+
+/* Trivial function to remove the last node in the tree. Which by definition
+ has no right-hand -- so can be removed just by making its only child (if
+ any) take its place under its parent. */
+static void eat_last(struct rb_root *root, struct rb_node *node)
+{
+ struct rb_node *parent = rb_parent(node);
+ struct rb_node **link;
+
+ /* LAST! */
+ BUG_ON(node->rb_right);
+
+ if (!parent)
+ link = &root->rb_node;
+ else if (node == parent->rb_left)
+ link = &parent->rb_left;
+ else
+ link = &parent->rb_right;
+
+ *link = node->rb_left;
+ /* Colour doesn't matter now. Only the parent pointer. */
+ if (node->rb_left)
+ node->rb_left->rb_parent_color = node->rb_parent_color;
+}
+
+/* We put this in reverse order, so we can just use eat_last */
+static void ver_insert(struct rb_root *ver_root, struct jffs2_tmp_dnode_info *tn)