URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [rtos/] [ecos-3.0/] [packages/] [fs/] [jffs2/] [current/] [src/] [nodelist.c] - Blame information for rev 838

Go to most recent revision | Details | Compare with Previous | View Log


/*
 * JFFS2 -- Journalling Flash File System, Version 2.
 *
 * Copyright (C) 2001-2003 Red Hat, Inc.
 *
 * Created by David Woodhouse <dwmw2@infradead.org>
 *
 * For licensing information, see the file 'LICENCE' in this directory.
 *
 * $Id: nodelist.c,v 1.102 2005/07/28 12:45:10 dedekind Exp $
 *
 */
 
#include <linux/kernel.h>
#include <linux/sched.h>
#include <linux/fs.h>
#include <linux/mtd/mtd.h>
#include <linux/rbtree.h>
#include <linux/crc32.h>
#include <linux/slab.h>
#include <linux/pagemap.h>
#include "nodelist.h"
 
void jffs2_add_fd_to_list(struct jffs2_sb_info *c, struct jffs2_full_dirent *new, struct jffs2_full_dirent **list)
{
        struct jffs2_full_dirent **prev = list;
 
        JFFS2_DBG_DENTLIST("add dirent \"%s\", ino #%u\n", new->name, new->ino);
 
        while ((*prev) && (*prev)->nhash <= new->nhash) {
                if ((*prev)->nhash == new->nhash && !strcmp((*prev)->name, new->name)) {
                        /* Duplicate. Free one */
                        if (new->version < (*prev)->version) {
                                JFFS2_DBG_DENTLIST("Eep! Marking new dirent node is obsolete, old is \"%s\", ino #%u\n",
                                        (*prev)->name, (*prev)->ino);
                                jffs2_mark_node_obsolete(c, new->raw);
                                jffs2_free_full_dirent(new);
                        } else {
                                JFFS2_DBG_DENTLIST("marking old dirent \"%s\", ino #%u bsolete\n",
                                        (*prev)->name, (*prev)->ino);
                                new->next = (*prev)->next;
                                jffs2_mark_node_obsolete(c, ((*prev)->raw));
                                jffs2_free_full_dirent(*prev);
                                *prev = new;
                        }
                        return;
                }
                prev = &((*prev)->next);
        }
        new->next = *prev;
        *prev = new;
}
 
void jffs2_obsolete_node_frag(struct jffs2_sb_info *c, struct jffs2_node_frag *this)
{
        if (this->node) {
                this->node->frags--;
                if (!this->node->frags) {
                        /* The node has no valid frags left. It's totally obsoleted */
                        JFFS2_DBG_FRAGTREE2("marking old node @0x%08x (0x%04x-0x%04x) obsolete\n",
                                ref_offset(this->node->raw), this->node->ofs, this->node->ofs+this->node->size);
                        jffs2_mark_node_obsolete(c, this->node->raw);
                        jffs2_free_full_dnode(this->node);
                } else {
                        JFFS2_DBG_FRAGTREE2("marking old node @0x%08x (0x%04x-0x%04x) REF_NORMAL. frags is %d\n",
                                ref_offset(this->node->raw), this->node->ofs, this->node->ofs+this->node->size, this->node->frags);
                        mark_ref_normal(this->node->raw);
                }
 
        }
        jffs2_free_node_frag(this);
}
 
static void jffs2_fragtree_insert(struct jffs2_node_frag *newfrag, struct jffs2_node_frag *base)
{
        struct rb_node *parent = &base->rb;
        struct rb_node **link = &parent;
 
        JFFS2_DBG_FRAGTREE2("insert frag (0x%04x-0x%04x)\n", newfrag->ofs, newfrag->ofs + newfrag->size);
 
        while (*link) {
                parent = *link;
                base = rb_entry(parent, struct jffs2_node_frag, rb);
 
                JFFS2_DBG_FRAGTREE2("considering frag at 0x%08x\n", base->ofs);
                if (newfrag->ofs > base->ofs)
                        link = &base->rb.rb_right;
                else if (newfrag->ofs < base->ofs)
                        link = &base->rb.rb_left;
                else {
                        JFFS2_ERROR("duplicate frag at %08x (%p,%p)\n", newfrag->ofs, newfrag, base);
                        BUG();
                }
        }
 
        rb_link_node(&newfrag->rb, &base->rb, link);
}
 
/* Doesn't set inode->i_size */
static int jffs2_add_frag_to_fragtree(struct jffs2_sb_info *c, struct rb_root *list, struct jffs2_node_frag *newfrag)
{
        struct jffs2_node_frag *this;
        uint32_t lastend;
 
        /* Skip all the nodes which are completed before this one starts */
        this = jffs2_lookup_node_frag(list, newfrag->node->ofs);
 
        if (this) {
                JFFS2_DBG_FRAGTREE2("lookup gave frag 0x%04x-0x%04x; phys 0x%08x (*%p)\n",
                          this->ofs, this->ofs+this->size, this->node?(ref_offset(this->node->raw)):0xffffffff, this);
                lastend = this->ofs + this->size;
        } else {
                JFFS2_DBG_FRAGTREE2("lookup gave no frag\n");
                lastend = 0;
        }
 
        /* See if we ran off the end of the list */
        if (lastend <= newfrag->ofs) {
                /* We did */
 
                /* Check if 'this' node was on the same page as the new node.
                   If so, both 'this' and the new node get marked REF_NORMAL so
                   the GC can take a look.
                */
                if (lastend && (lastend-1) >> PAGE_CACHE_SHIFT == newfrag->ofs >> PAGE_CACHE_SHIFT) {
                        if (this->node)
                                mark_ref_normal(this->node->raw);
                        mark_ref_normal(newfrag->node->raw);
                }
 
                if (lastend < newfrag->node->ofs) {
                        /* ... and we need to put a hole in before the new node */
                        struct jffs2_node_frag *holefrag = jffs2_alloc_node_frag();
                        if (!holefrag) {
                                jffs2_free_node_frag(newfrag);
                                return -ENOMEM;
                        }
                        holefrag->ofs = lastend;
                        holefrag->size = newfrag->node->ofs - lastend;
                        holefrag->node = NULL;
                        if (this) {
                                /* By definition, the 'this' node has no right-hand child,
                                   because there are no frags with offset greater than it.
                                   So that's where we want to put the hole */
                                JFFS2_DBG_FRAGTREE2("adding hole frag (%p) on right of node at (%p)\n", holefrag, this);
                                rb_link_node(&holefrag->rb, &this->rb, &this->rb.rb_right);
                        } else {
                                JFFS2_DBG_FRAGTREE2("adding hole frag (%p) at root of tree\n", holefrag);
                                rb_link_node(&holefrag->rb, NULL, &list->rb_node);
                        }
                        rb_insert_color(&holefrag->rb, list);
                        this = holefrag;
                }
                if (this) {
                        /* By definition, the 'this' node has no right-hand child,
                           because there are no frags with offset greater than it.
                           So that's where we want to put new fragment */
                        JFFS2_DBG_FRAGTREE2("adding new frag (%p) on right of node at (%p)\n", newfrag, this);
                        rb_link_node(&newfrag->rb, &this->rb, &this->rb.rb_right);
                } else {
                        JFFS2_DBG_FRAGTREE2("adding new frag (%p) at root of tree\n", newfrag);
                        rb_link_node(&newfrag->rb, NULL, &list->rb_node);
                }
                rb_insert_color(&newfrag->rb, list);
                return 0;
        }
 
        JFFS2_DBG_FRAGTREE2("dealing with frag 0x%04x-0x%04x; phys 0x%08x (*%p)\n",
                  this->ofs, this->ofs+this->size, this->node?(ref_offset(this->node->raw)):0xffffffff, this);
 
        /* OK. 'this' is pointing at the first frag that newfrag->ofs at least partially obsoletes,
         * - i.e. newfrag->ofs < this->ofs+this->size && newfrag->ofs >= this->ofs
         */
        if (newfrag->ofs > this->ofs) {
                /* This node isn't completely obsoleted. The start of it remains valid */
 
                /* Mark the new node and the partially covered node REF_NORMAL -- let
                   the GC take a look at them */
                mark_ref_normal(newfrag->node->raw);
                if (this->node)
                        mark_ref_normal(this->node->raw);
 
                if (this->ofs + this->size > newfrag->ofs + newfrag->size) {
                        /* The new node splits 'this' frag into two */
                        struct jffs2_node_frag *newfrag2 = jffs2_alloc_node_frag();
                        if (!newfrag2) {
                                jffs2_free_node_frag(newfrag);
                                return -ENOMEM;
                        }
                        if (this->node)
                                JFFS2_DBG_FRAGTREE2("split old frag 0x%04x-0x%04x, phys 0x%08x\n",
                                        this->ofs, this->ofs+this->size, ref_offset(this->node->raw));
                        else
                                JFFS2_DBG_FRAGTREE2("split old hole frag 0x%04x-0x%04x\n",
                                        this->ofs, this->ofs+this->size, ref_offset(this->node->raw));
 
                        /* New second frag pointing to this's node */
                        newfrag2->ofs = newfrag->ofs + newfrag->size;
                        newfrag2->size = (this->ofs+this->size) - newfrag2->ofs;
                        newfrag2->node = this->node;
                        if (this->node)
                                this->node->frags++;
 
                        /* Adjust size of original 'this' */
                        this->size = newfrag->ofs - this->ofs;
 
                        /* Now, we know there's no node with offset
                           greater than this->ofs but smaller than
                           newfrag2->ofs or newfrag->ofs, for obvious
                           reasons. So we can do a tree insert from
                           'this' to insert newfrag, and a tree insert
                           from newfrag to insert newfrag2. */
                        jffs2_fragtree_insert(newfrag, this);
                        rb_insert_color(&newfrag->rb, list);
 
                        jffs2_fragtree_insert(newfrag2, newfrag);
                        rb_insert_color(&newfrag2->rb, list);
 
                        return 0;
                }
                /* New node just reduces 'this' frag in size, doesn't split it */
                this->size = newfrag->ofs - this->ofs;
 
                /* Again, we know it lives down here in the tree */
                jffs2_fragtree_insert(newfrag, this);
                rb_insert_color(&newfrag->rb, list);
        } else {
                /* New frag starts at the same point as 'this' used to. Replace
                   it in the tree without doing a delete and insertion */
                JFFS2_DBG_FRAGTREE2("inserting newfrag (*%p),%d-%d in before 'this' (*%p),%d-%d\n",
                          newfrag, newfrag->ofs, newfrag->ofs+newfrag->size, this, this->ofs, this->ofs+this->size);
 
                rb_replace_node(&this->rb, &newfrag->rb, list);
 
                if (newfrag->ofs + newfrag->size >= this->ofs+this->size) {
                        JFFS2_DBG_FRAGTREE2("obsoleting node frag %p (%x-%x)\n", this, this->ofs, this->ofs+this->size);
                        jffs2_obsolete_node_frag(c, this);
                } else {
                        this->ofs += newfrag->size;
                        this->size -= newfrag->size;
 
                        jffs2_fragtree_insert(this, newfrag);
                        rb_insert_color(&this->rb, list);
                        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(newfrag)) && newfrag->ofs + newfrag->size >= this->ofs + this->size) {
                /* 'this' frag is obsoleted completely. */
                JFFS2_DBG_FRAGTREE2("obsoleting node frag %p (%x-%x) and removing from tree\n",
                        this, this->ofs, this->ofs+this->size);
                rb_erase(&this->rb, list);
                jffs2_obsolete_node_frag(c, this);
        }
        /* Now we're pointing at the first frag which isn't totally obsoleted by
           the new frag */
 
        if (!this || newfrag->ofs + newfrag->size == this->ofs) {
                return 0;
        }
        /* Still some overlap but we don't need to move it in the tree */
        this->size = (this->ofs + this->size) - (newfrag->ofs + newfrag->size);
        this->ofs = newfrag->ofs + newfrag->size;
 
        /* And mark them REF_NORMAL so the GC takes a look at them */
        if (this->node)
                mark_ref_normal(this->node->raw);
        mark_ref_normal(newfrag->node->raw);
 
        return 0;
}
 
/* Given an inode, probably with existing list of fragments, add the new node
 * to the fragment list.
 */
int jffs2_add_full_dnode_to_inode(struct jffs2_sb_info *c, struct jffs2_inode_info *f, struct jffs2_full_dnode *fn)
{
        int ret;
        struct jffs2_node_frag *newfrag;
 
        if (unlikely(!fn->size))
                return 0;
 
        newfrag = jffs2_alloc_node_frag();
        if (unlikely(!newfrag))
                return -ENOMEM;
 
        JFFS2_DBG_FRAGTREE("adding node %#04x-%#04x @0x%08x on flash, newfrag *%p\n",
                  fn->ofs, fn->ofs+fn->size, ref_offset(fn->raw), newfrag);
 
        newfrag->ofs = fn->ofs;
        newfrag->size = fn->size;
        newfrag->node = fn;
        newfrag->node->frags = 1;
 
        ret = jffs2_add_frag_to_fragtree(c, &f->fragtree, newfrag);
        if (unlikely(ret))
                return ret;
 
        /* If we now share a page with other nodes, mark either previous
           or next node REF_NORMAL, as appropriate.  */
        if (newfrag->ofs & (PAGE_CACHE_SIZE-1)) {
                struct jffs2_node_frag *prev = frag_prev(newfrag);
 
                mark_ref_normal(fn->raw);
                /* If we don't start at zero there's _always_ a previous */
                if (prev->node)
                        mark_ref_normal(prev->node->raw);
        }
 
        if ((newfrag->ofs+newfrag->size) & (PAGE_CACHE_SIZE-1)) {
                struct jffs2_node_frag *next = frag_next(newfrag);
 
                if (next) {
                        mark_ref_normal(fn->raw);
                        if (next->node)
                                mark_ref_normal(next->node->raw);
                }
        }
        jffs2_dbg_fragtree_paranoia_check_nolock(f);
        jffs2_dbg_dump_fragtree_nolock(f);
        return 0;
}
 
 
void jffs2_set_inocache_state(struct jffs2_sb_info *c, struct jffs2_inode_cache *ic, int state)
{
        spin_lock(&c->inocache_lock);
        ic->state = state;
        wake_up(&c->inocache_wq);
        spin_unlock(&c->inocache_lock);
}
 
/* During mount, this needs no locking. During normal operation, its
   callers want to do other stuff while still holding the inocache_lock.
   Rather than introducing special case get_ino_cache functions or
   callbacks, we just let the caller do the locking itself. */
 
struct jffs2_inode_cache *jffs2_get_ino_cache(struct jffs2_sb_info *c, uint32_t ino)
{
        struct jffs2_inode_cache *ret;
 
        ret = c->inocache_list[ino % INOCACHE_HASHSIZE];
        while (ret && ret->ino < ino) {
                ret = ret->next;
        }
 
        if (ret && ret->ino != ino)
                ret = NULL;
 
        return ret;
}
 
void jffs2_add_ino_cache (struct jffs2_sb_info *c, struct jffs2_inode_cache *new)
{
        struct jffs2_inode_cache **prev;
 
        spin_lock(&c->inocache_lock);
        if (!new->ino)
                new->ino = ++c->highest_ino;
 
        JFFS2_DBG_INOCACHE("add %p (ino #%u)\n", new, new->ino);
 
        prev = &c->inocache_list[new->ino % INOCACHE_HASHSIZE];
 
        while ((*prev) && (*prev)->ino < new->ino) {
                prev = &(*prev)->next;
        }
        new->next = *prev;
        *prev = new;
 
        spin_unlock(&c->inocache_lock);
}
 
void jffs2_del_ino_cache(struct jffs2_sb_info *c, struct jffs2_inode_cache *old)
{
        struct jffs2_inode_cache **prev;
 
        JFFS2_DBG_INOCACHE("del %p (ino #%u)\n", old, old->ino);
        spin_lock(&c->inocache_lock);
 
        prev = &c->inocache_list[old->ino % INOCACHE_HASHSIZE];
 
        while ((*prev) && (*prev)->ino < old->ino) {
                prev = &(*prev)->next;
        }
        if ((*prev) == old) {
                *prev = old->next;
        }
 
        /* Free it now unless it's in READING or CLEARING state, which
           are the transitions upon read_inode() and clear_inode(). The
           rest of the time we know nobody else is looking at it, and
           if it's held by read_inode() or clear_inode() they'll free it
           for themselves. */
        if (old->state != INO_STATE_READING && old->state != INO_STATE_CLEARING)
                jffs2_free_inode_cache(old);
 
        spin_unlock(&c->inocache_lock);
}
 
void jffs2_free_ino_caches(struct jffs2_sb_info *c)
{
        int i;
        struct jffs2_inode_cache *this, *next;
 
        for (i=0; i<INOCACHE_HASHSIZE; i++) {
                this = c->inocache_list[i];
                while (this) {
                        next = this->next;
                        jffs2_free_inode_cache(this);
                        this = next;
                }
                c->inocache_list[i] = NULL;
        }
}
 
void jffs2_free_raw_node_refs(struct jffs2_sb_info *c)
{
        int i;
        struct jffs2_raw_node_ref *this, *next;
 
        for (i=0; i<c->nr_blocks; i++) {
                this = c->blocks[i].first_node;
                while(this) {
                        next = this->next_phys;
                        jffs2_free_raw_node_ref(this);
                        this = next;
                }
                c->blocks[i].first_node = c->blocks[i].last_node = NULL;
        }
}
 
struct jffs2_node_frag *jffs2_lookup_node_frag(struct rb_root *fragtree, uint32_t offset)
{
        /* The common case in lookup is that there will be a node
           which precisely matches. So we go looking for that first */
        struct rb_node *next;
        struct jffs2_node_frag *prev = NULL;
        struct jffs2_node_frag *frag = NULL;
 
        JFFS2_DBG_FRAGTREE2("root %p, offset %d\n", fragtree, offset);
 
        next = fragtree->rb_node;
 
        while(next) {
                frag = rb_entry(next, struct jffs2_node_frag, rb);
 
                JFFS2_DBG_FRAGTREE2("considering frag %#04x-%#04x (%p). left %p, right %p\n",
                          frag->ofs, frag->ofs+frag->size, frag, frag->rb.rb_left, frag->rb.rb_right);
                if (frag->ofs + frag->size <= offset) {
                        JFFS2_DBG_FRAGTREE2("going right from frag %#04x-%#04x, before the region we care about\n",
                                  frag->ofs, frag->ofs+frag->size);
                        /* Remember the closest smaller match on the way down */
                        if (!prev || frag->ofs > prev->ofs)
                                prev = frag;
                        next = frag->rb.rb_right;
                } else if (frag->ofs > offset) {
                        JFFS2_DBG_FRAGTREE2("going left from frag %#04x-%#04x, after the region we care about\n",
                                  frag->ofs, frag->ofs+frag->size);
                        next = frag->rb.rb_left;
                } else {
                        JFFS2_DBG_FRAGTREE2("returning frag %#04x-%#04x, matched\n",
                                  frag->ofs, frag->ofs+frag->size);
                        return frag;
                }
        }
 
        /* Exact match not found. Go back up looking at each parent,
           and return the closest smaller one */
 
        if (prev)
                JFFS2_DBG_FRAGTREE2("no match. Returning frag %#04x-%#04x, closest previous\n",
                          prev->ofs, prev->ofs+prev->size);
        else
                JFFS2_DBG_FRAGTREE2("returning NULL, empty fragtree\n");
 
        return prev;
}
 
/* Pass 'c' argument to indicate that nodes should be marked obsolete as
   they're killed. */
void jffs2_kill_fragtree(struct rb_root *root, struct jffs2_sb_info *c)
{
        struct jffs2_node_frag *frag;
        struct jffs2_node_frag *parent;
 
        if (!root->rb_node)
                return;
 
        JFFS2_DBG_FRAGTREE("killing\n");
 
        frag = (rb_entry(root->rb_node, struct jffs2_node_frag, rb));
        while(frag) {
                if (frag->rb.rb_left) {
                        JFFS2_DBG_FRAGTREE2("going left from frag (%p) %#04x-%#04x\n",
                                frag, frag->ofs, frag->ofs+frag->size);
                        frag = frag_left(frag);
                        continue;
                }
                if (frag->rb.rb_right) {
                        JFFS2_DBG_FRAGTREE2("going right from frag (%p) %#04x-%#04x\n",
                                  frag, frag->ofs, frag->ofs+frag->size);
                        frag = frag_right(frag);
                        continue;
                }
 
                JFFS2_DBG_FRAGTREE2("frag %#04x-%#04x: node %p, frags %d\n",
                          frag->ofs, frag->ofs+frag->size, frag->node, frag->node?frag->node->frags:0);
 
                if (frag->node && !(--frag->node->frags)) {
                        /* Not a hole, and it's the final remaining frag
                           of this node. Free the node */
                        if (c)
                                jffs2_mark_node_obsolete(c, frag->node->raw);
 
                        jffs2_free_full_dnode(frag->node);
                }
                parent = frag_parent(frag);
                if (parent) {
                        if (frag_left(parent) == frag)
                                parent->rb.rb_left = NULL;
                        else
                                parent->rb.rb_right = NULL;
                }
 
                jffs2_free_node_frag(frag);
                frag = parent;
 
                cond_resched();
        }
}

Browse

Tools

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [rtos/] [ecos-3.0/] [packages/] [fs/] [jffs2/] [current/] [src/] [nodelist.c] - Blame information for rev 838

Line No.	Rev	Author	Line
1	786	skrzyp	`/*`
2			`* JFFS2 -- Journalling Flash File System, Version 2.`
3			`*`
4			`* Copyright (C) 2001-2003 Red Hat, Inc.`
5			`*`
6			`* Created by David Woodhouse <dwmw2@infradead.org>`
7			`*`
8			`* For licensing information, see the file 'LICENCE' in this directory.`
9			`*`
10			`* $Id: nodelist.c,v 1.102 2005/07/28 12:45:10 dedekind Exp $`
11			`*`
12			`*/`
13
14			`#include <linux/kernel.h>`
15			`#include <linux/sched.h>`
16			`#include <linux/fs.h>`
17			`#include <linux/mtd/mtd.h>`
18			`#include <linux/rbtree.h>`
19			`#include <linux/crc32.h>`
20			`#include <linux/slab.h>`
21			`#include <linux/pagemap.h>`
22			`#include "nodelist.h"`
23
24			`void jffs2_add_fd_to_list(struct jffs2_sb_info c, struct jffs2_full_dirent new, struct jffs2_full_dirent **list)`
25			`{`
26			`struct jffs2_full_dirent **prev = list;`
27
28			`JFFS2_DBG_DENTLIST("add dirent \"%s\", ino #%u\n", new->name, new->ino);`
29
30			`while ((prev) && (prev)->nhash <= new->nhash) {`
31			`if ((prev)->nhash == new->nhash && !strcmp((prev)->name, new->name)) {`
32			`/* Duplicate. Free one */`
33			`if (new->version < (*prev)->version) {`
34			`JFFS2_DBG_DENTLIST("Eep! Marking new dirent node is obsolete, old is \"%s\", ino #%u\n",`
35			`(prev)->name, (prev)->ino);`
36			`jffs2_mark_node_obsolete(c, new->raw);`
37			`jffs2_free_full_dirent(new);`
38			`} else {`
39			`JFFS2_DBG_DENTLIST("marking old dirent \"%s\", ino #%u bsolete\n",`
40			`(prev)->name, (prev)->ino);`
41			`new->next = (*prev)->next;`
42			`jffs2_mark_node_obsolete(c, ((*prev)->raw));`
43			`jffs2_free_full_dirent(*prev);`
44			`*prev = new;`
45			`}`
46			`return;`
47			`}`
48			`prev = &((*prev)->next);`
49			`}`
50			`new->next = *prev;`
51			`*prev = new;`
52			`}`
53
54			`void jffs2_obsolete_node_frag(struct jffs2_sb_info c, struct jffs2_node_frag this)`
55			`{`
56			`if (this->node) {`
57			`this->node->frags--;`
58			`if (!this->node->frags) {`
59			`/* The node has no valid frags left. It's totally obsoleted */`
60			`JFFS2_DBG_FRAGTREE2("marking old node @0x%08x (0x%04x-0x%04x) obsolete\n",`
61			`ref_offset(this->node->raw), this->node->ofs, this->node->ofs+this->node->size);`
62			`jffs2_mark_node_obsolete(c, this->node->raw);`
63			`jffs2_free_full_dnode(this->node);`
64			`} else {`
65			`JFFS2_DBG_FRAGTREE2("marking old node @0x%08x (0x%04x-0x%04x) REF_NORMAL. frags is %d\n",`
66			`ref_offset(this->node->raw), this->node->ofs, this->node->ofs+this->node->size, this->node->frags);`
67			`mark_ref_normal(this->node->raw);`
68			`}`
69
70			`}`
71			`jffs2_free_node_frag(this);`
72			`}`
73
74			`static void jffs2_fragtree_insert(struct jffs2_node_frag newfrag, struct jffs2_node_frag base)`
75			`{`
76			`struct rb_node *parent = &base->rb;`
77			`struct rb_node **link = &parent;`
78
79			`JFFS2_DBG_FRAGTREE2("insert frag (0x%04x-0x%04x)\n", newfrag->ofs, newfrag->ofs + newfrag->size);`
80
81			`while (*link) {`
82			`parent = *link;`
83			`base = rb_entry(parent, struct jffs2_node_frag, rb);`
84
85			`JFFS2_DBG_FRAGTREE2("considering frag at 0x%08x\n", base->ofs);`
86			`if (newfrag->ofs > base->ofs)`
87			`link = &base->rb.rb_right;`
88			`else if (newfrag->ofs < base->ofs)`
89			`link = &base->rb.rb_left;`
90			`else {`
91			`JFFS2_ERROR("duplicate frag at %08x (%p,%p)\n", newfrag->ofs, newfrag, base);`
92			`BUG();`
93			`}`
94			`}`
95
96			`rb_link_node(&newfrag->rb, &base->rb, link);`
97			`}`
98
99			`/* Doesn't set inode->i_size */`
100			`static int jffs2_add_frag_to_fragtree(struct jffs2_sb_info c, struct rb_root list, struct jffs2_node_frag *newfrag)`
101			`{`
102			`struct jffs2_node_frag *this;`
103			`uint32_t lastend;`
104
105			`/* Skip all the nodes which are completed before this one starts */`
106			`this = jffs2_lookup_node_frag(list, newfrag->node->ofs);`
107
108			`if (this) {`
109			`JFFS2_DBG_FRAGTREE2("lookup gave frag 0x%04x-0x%04x; phys 0x%08x (*%p)\n",`
110			`this->ofs, this->ofs+this->size, this->node?(ref_offset(this->node->raw)):0xffffffff, this);`
111			`lastend = this->ofs + this->size;`
112			`} else {`
113			`JFFS2_DBG_FRAGTREE2("lookup gave no frag\n");`
114			`lastend = 0;`
115			`}`
116
117			`/* See if we ran off the end of the list */`
118			`if (lastend <= newfrag->ofs) {`
119			`/* We did */`
120
121			`/* Check if 'this' node was on the same page as the new node.`
122			`If so, both 'this' and the new node get marked REF_NORMAL so`
123			`the GC can take a look.`
124			`*/`
125			`if (lastend && (lastend-1) >> PAGE_CACHE_SHIFT == newfrag->ofs >> PAGE_CACHE_SHIFT) {`
126			`if (this->node)`
127			`mark_ref_normal(this->node->raw);`
128			`mark_ref_normal(newfrag->node->raw);`
129			`}`
130
131			`if (lastend < newfrag->node->ofs) {`
132			`/* ... and we need to put a hole in before the new node */`
133			`struct jffs2_node_frag *holefrag = jffs2_alloc_node_frag();`
134			`if (!holefrag) {`
135			`jffs2_free_node_frag(newfrag);`
136			`return -ENOMEM;`
137			`}`
138			`holefrag->ofs = lastend;`
139			`holefrag->size = newfrag->node->ofs - lastend;`
140			`holefrag->node = NULL;`
141			`if (this) {`
142			`/* By definition, the 'this' node has no right-hand child,`
143			`because there are no frags with offset greater than it.`
144			`So that's where we want to put the hole */`
145			`JFFS2_DBG_FRAGTREE2("adding hole frag (%p) on right of node at (%p)\n", holefrag, this);`
146			`rb_link_node(&holefrag->rb, &this->rb, &this->rb.rb_right);`
147			`} else {`
148			`JFFS2_DBG_FRAGTREE2("adding hole frag (%p) at root of tree\n", holefrag);`
149			`rb_link_node(&holefrag->rb, NULL, &list->rb_node);`
150			`}`
151			`rb_insert_color(&holefrag->rb, list);`
152			`this = holefrag;`
153			`}`
154			`if (this) {`
155			`/* By definition, the 'this' node has no right-hand child,`
156			`because there are no frags with offset greater than it.`
157			`So that's where we want to put new fragment */`
158			`JFFS2_DBG_FRAGTREE2("adding new frag (%p) on right of node at (%p)\n", newfrag, this);`
159			`rb_link_node(&newfrag->rb, &this->rb, &this->rb.rb_right);`
160			`} else {`
161			`JFFS2_DBG_FRAGTREE2("adding new frag (%p) at root of tree\n", newfrag);`
162			`rb_link_node(&newfrag->rb, NULL, &list->rb_node);`
163			`}`
164			`rb_insert_color(&newfrag->rb, list);`
165			`return 0;`
166			`}`
167
168			`JFFS2_DBG_FRAGTREE2("dealing with frag 0x%04x-0x%04x; phys 0x%08x (*%p)\n",`
169			`this->ofs, this->ofs+this->size, this->node?(ref_offset(this->node->raw)):0xffffffff, this);`
170
171			`/* OK. 'this' is pointing at the first frag that newfrag->ofs at least partially obsoletes,`
172			`* - i.e. newfrag->ofs < this->ofs+this->size && newfrag->ofs >= this->ofs`
173			`*/`
174			`if (newfrag->ofs > this->ofs) {`
175			`/* This node isn't completely obsoleted. The start of it remains valid */`
176
177			`/* Mark the new node and the partially covered node REF_NORMAL -- let`
178			`the GC take a look at them */`
179			`mark_ref_normal(newfrag->node->raw);`
180			`if (this->node)`
181			`mark_ref_normal(this->node->raw);`
182
183			`if (this->ofs + this->size > newfrag->ofs + newfrag->size) {`
184			`/* The new node splits 'this' frag into two */`
185			`struct jffs2_node_frag *newfrag2 = jffs2_alloc_node_frag();`
186			`if (!newfrag2) {`
187			`jffs2_free_node_frag(newfrag);`
188			`return -ENOMEM;`
189			`}`
190			`if (this->node)`
191			`JFFS2_DBG_FRAGTREE2("split old frag 0x%04x-0x%04x, phys 0x%08x\n",`
192			`this->ofs, this->ofs+this->size, ref_offset(this->node->raw));`
193			`else`
194			`JFFS2_DBG_FRAGTREE2("split old hole frag 0x%04x-0x%04x\n",`
195			`this->ofs, this->ofs+this->size, ref_offset(this->node->raw));`
196
197			`/* New second frag pointing to this's node */`
198			`newfrag2->ofs = newfrag->ofs + newfrag->size;`
199			`newfrag2->size = (this->ofs+this->size) - newfrag2->ofs;`
200			`newfrag2->node = this->node;`
201			`if (this->node)`
202			`this->node->frags++;`
203
204			`/* Adjust size of original 'this' */`
205			`this->size = newfrag->ofs - this->ofs;`
206
207			`/* Now, we know there's no node with offset`
208			`greater than this->ofs but smaller than`
209			`newfrag2->ofs or newfrag->ofs, for obvious`
210			`reasons. So we can do a tree insert from`
211			`'this' to insert newfrag, and a tree insert`
212			`from newfrag to insert newfrag2. */`
213			`jffs2_fragtree_insert(newfrag, this);`
214			`rb_insert_color(&newfrag->rb, list);`
215
216			`jffs2_fragtree_insert(newfrag2, newfrag);`
217			`rb_insert_color(&newfrag2->rb, list);`
218
219			`return 0;`
220			`}`
221			`/* New node just reduces 'this' frag in size, doesn't split it */`
222			`this->size = newfrag->ofs - this->ofs;`
223
224			`/* Again, we know it lives down here in the tree */`
225			`jffs2_fragtree_insert(newfrag, this);`
226			`rb_insert_color(&newfrag->rb, list);`
227			`} else {`
228			`/* New frag starts at the same point as 'this' used to. Replace`
229			`it in the tree without doing a delete and insertion */`
230			`JFFS2_DBG_FRAGTREE2("inserting newfrag (%p),%d-%d in before 'this' (%p),%d-%d\n",`
231			`newfrag, newfrag->ofs, newfrag->ofs+newfrag->size, this, this->ofs, this->ofs+this->size);`
232
233			`rb_replace_node(&this->rb, &newfrag->rb, list);`
234
235			`if (newfrag->ofs + newfrag->size >= this->ofs+this->size) {`
236			`JFFS2_DBG_FRAGTREE2("obsoleting node frag %p (%x-%x)\n", this, this->ofs, this->ofs+this->size);`
237			`jffs2_obsolete_node_frag(c, this);`
238			`} else {`
239			`this->ofs += newfrag->size;`
240			`this->size -= newfrag->size;`
241
242			`jffs2_fragtree_insert(this, newfrag);`
243			`rb_insert_color(&this->rb, list);`
244			`return 0;`
245			`}`
246			`}`
247			`/* OK, now we have newfrag added in the correct place in the tree, but`
248			`frag_next(newfrag) may be a fragment which is overlapped by it`
249			`*/`
250			`while ((this = frag_next(newfrag)) && newfrag->ofs + newfrag->size >= this->ofs + this->size) {`
251			`/* 'this' frag is obsoleted completely. */`
252			`JFFS2_DBG_FRAGTREE2("obsoleting node frag %p (%x-%x) and removing from tree\n",`
253			`this, this->ofs, this->ofs+this->size);`
254			`rb_erase(&this->rb, list);`
255			`jffs2_obsolete_node_frag(c, this);`
256			`}`
257			`/* Now we're pointing at the first frag which isn't totally obsoleted by`
258			`the new frag */`
259
260			`if (!this \|\| newfrag->ofs + newfrag->size == this->ofs) {`
261			`return 0;`
262			`}`
263			`/* Still some overlap but we don't need to move it in the tree */`
264			`this->size = (this->ofs + this->size) - (newfrag->ofs + newfrag->size);`
265			`this->ofs = newfrag->ofs + newfrag->size;`
266
267			`/* And mark them REF_NORMAL so the GC takes a look at them */`
268			`if (this->node)`
269			`mark_ref_normal(this->node->raw);`
270			`mark_ref_normal(newfrag->node->raw);`
271
272			`return 0;`
273			`}`
274
275			`/* Given an inode, probably with existing list of fragments, add the new node`
276			`* to the fragment list.`
277			`*/`
278			`int jffs2_add_full_dnode_to_inode(struct jffs2_sb_info c, struct jffs2_inode_info f, struct jffs2_full_dnode *fn)`
279			`{`
280			`int ret;`
281			`struct jffs2_node_frag *newfrag;`
282
283			`if (unlikely(!fn->size))`
284			`return 0;`
285
286			`newfrag = jffs2_alloc_node_frag();`
287			`if (unlikely(!newfrag))`
288			`return -ENOMEM;`
289
290			`JFFS2_DBG_FRAGTREE("adding node %#04x-%#04x @0x%08x on flash, newfrag *%p\n",`
291			`fn->ofs, fn->ofs+fn->size, ref_offset(fn->raw), newfrag);`
292
293			`newfrag->ofs = fn->ofs;`
294			`newfrag->size = fn->size;`
295			`newfrag->node = fn;`
296			`newfrag->node->frags = 1;`
297
298			`ret = jffs2_add_frag_to_fragtree(c, &f->fragtree, newfrag);`
299			`if (unlikely(ret))`
300			`return ret;`
301
302			`/* If we now share a page with other nodes, mark either previous`
303			`or next node REF_NORMAL, as appropriate. */`
304			`if (newfrag->ofs & (PAGE_CACHE_SIZE-1)) {`
305			`struct jffs2_node_frag *prev = frag_prev(newfrag);`
306
307			`mark_ref_normal(fn->raw);`
308			`/* If we don't start at zero there's _always_ a previous */`
309			`if (prev->node)`
310			`mark_ref_normal(prev->node->raw);`
311			`}`
312
313			`if ((newfrag->ofs+newfrag->size) & (PAGE_CACHE_SIZE-1)) {`
314			`struct jffs2_node_frag *next = frag_next(newfrag);`
315
316			`if (next) {`
317			`mark_ref_normal(fn->raw);`
318			`if (next->node)`
319			`mark_ref_normal(next->node->raw);`
320			`}`
321			`}`
322			`jffs2_dbg_fragtree_paranoia_check_nolock(f);`
323			`jffs2_dbg_dump_fragtree_nolock(f);`
324			`return 0;`
325			`}`
326
327
328			`void jffs2_set_inocache_state(struct jffs2_sb_info c, struct jffs2_inode_cache ic, int state)`
329			`{`
330			`spin_lock(&c->inocache_lock);`
331			`ic->state = state;`
332			`wake_up(&c->inocache_wq);`
333			`spin_unlock(&c->inocache_lock);`
334			`}`
335
336			`/* During mount, this needs no locking. During normal operation, its`
337			`callers want to do other stuff while still holding the inocache_lock.`
338			`Rather than introducing special case get_ino_cache functions or`
339			`callbacks, we just let the caller do the locking itself. */`
340
341			`struct jffs2_inode_cache jffs2_get_ino_cache(struct jffs2_sb_info c, uint32_t ino)`
342			`{`
343			`struct jffs2_inode_cache *ret;`
344
345			`ret = c->inocache_list[ino % INOCACHE_HASHSIZE];`
346			`while (ret && ret->ino < ino) {`
347			`ret = ret->next;`
348			`}`
349
350			`if (ret && ret->ino != ino)`
351			`ret = NULL;`
352
353			`return ret;`
354			`}`
355
356			`void jffs2_add_ino_cache (struct jffs2_sb_info c, struct jffs2_inode_cache new)`
357			`{`
358			`struct jffs2_inode_cache **prev;`
359
360			`spin_lock(&c->inocache_lock);`
361			`if (!new->ino)`
362			`new->ino = ++c->highest_ino;`
363
364			`JFFS2_DBG_INOCACHE("add %p (ino #%u)\n", new, new->ino);`
365
366			`prev = &c->inocache_list[new->ino % INOCACHE_HASHSIZE];`
367
368			`while ((prev) && (prev)->ino < new->ino) {`
369			`prev = &(*prev)->next;`
370			`}`
371			`new->next = *prev;`
372			`*prev = new;`
373
374			`spin_unlock(&c->inocache_lock);`
375			`}`
376
377			`void jffs2_del_ino_cache(struct jffs2_sb_info c, struct jffs2_inode_cache old)`
378			`{`
379			`struct jffs2_inode_cache **prev;`
380
381			`JFFS2_DBG_INOCACHE("del %p (ino #%u)\n", old, old->ino);`
382			`spin_lock(&c->inocache_lock);`
383
384			`prev = &c->inocache_list[old->ino % INOCACHE_HASHSIZE];`
385
386			`while ((prev) && (prev)->ino < old->ino) {`
387			`prev = &(*prev)->next;`
388			`}`
389			`if ((*prev) == old) {`
390			`*prev = old->next;`
391			`}`
392
393			`/* Free it now unless it's in READING or CLEARING state, which`
394			`are the transitions upon read_inode() and clear_inode(). The`
395			`rest of the time we know nobody else is looking at it, and`
396			`if it's held by read_inode() or clear_inode() they'll free it`
397			`for themselves. */`
398			`if (old->state != INO_STATE_READING && old->state != INO_STATE_CLEARING)`
399			`jffs2_free_inode_cache(old);`
400
401			`spin_unlock(&c->inocache_lock);`
402			`}`
403
404			`void jffs2_free_ino_caches(struct jffs2_sb_info *c)`
405			`{`
406			`int i;`
407			`struct jffs2_inode_cache this, next;`
408
409			`for (i=0; i<INOCACHE_HASHSIZE; i++) {`
410			`this = c->inocache_list[i];`
411			`while (this) {`
412			`next = this->next;`
413			`jffs2_free_inode_cache(this);`
414			`this = next;`
415			`}`
416			`c->inocache_list[i] = NULL;`
417			`}`
418			`}`
419
420			`void jffs2_free_raw_node_refs(struct jffs2_sb_info *c)`
421			`{`
422			`int i;`
423			`struct jffs2_raw_node_ref this, next;`
424
425			`for (i=0; i<c->nr_blocks; i++) {`
426			`this = c->blocks[i].first_node;`
427			`while(this) {`
428			`next = this->next_phys;`
429			`jffs2_free_raw_node_ref(this);`
430			`this = next;`
431			`}`
432			`c->blocks[i].first_node = c->blocks[i].last_node = NULL;`
433			`}`
434			`}`
435
436			`struct jffs2_node_frag jffs2_lookup_node_frag(struct rb_root fragtree, uint32_t offset)`
437			`{`
438			`/* The common case in lookup is that there will be a node`
439			`which precisely matches. So we go looking for that first */`
440			`struct rb_node *next;`
441			`struct jffs2_node_frag *prev = NULL;`
442			`struct jffs2_node_frag *frag = NULL;`
443
444			`JFFS2_DBG_FRAGTREE2("root %p, offset %d\n", fragtree, offset);`
445
446			`next = fragtree->rb_node;`
447
448			`while(next) {`
449			`frag = rb_entry(next, struct jffs2_node_frag, rb);`
450
451			`JFFS2_DBG_FRAGTREE2("considering frag %#04x-%#04x (%p). left %p, right %p\n",`
452			`frag->ofs, frag->ofs+frag->size, frag, frag->rb.rb_left, frag->rb.rb_right);`
453			`if (frag->ofs + frag->size <= offset) {`
454			`JFFS2_DBG_FRAGTREE2("going right from frag %#04x-%#04x, before the region we care about\n",`
455			`frag->ofs, frag->ofs+frag->size);`
456			`/* Remember the closest smaller match on the way down */`
457			`if (!prev \|\| frag->ofs > prev->ofs)`
458			`prev = frag;`
459			`next = frag->rb.rb_right;`
460			`} else if (frag->ofs > offset) {`
461			`JFFS2_DBG_FRAGTREE2("going left from frag %#04x-%#04x, after the region we care about\n",`
462			`frag->ofs, frag->ofs+frag->size);`
463			`next = frag->rb.rb_left;`
464			`} else {`
465			`JFFS2_DBG_FRAGTREE2("returning frag %#04x-%#04x, matched\n",`
466			`frag->ofs, frag->ofs+frag->size);`
467			`return frag;`
468			`}`
469			`}`
470
471			`/* Exact match not found. Go back up looking at each parent,`
472			`and return the closest smaller one */`
473
474			`if (prev)`
475			`JFFS2_DBG_FRAGTREE2("no match. Returning frag %#04x-%#04x, closest previous\n",`
476			`prev->ofs, prev->ofs+prev->size);`
477			`else`
478			`JFFS2_DBG_FRAGTREE2("returning NULL, empty fragtree\n");`
479
480			`return prev;`
481			`}`
482
483			`/* Pass 'c' argument to indicate that nodes should be marked obsolete as`
484			`they're killed. */`
485			`void jffs2_kill_fragtree(struct rb_root root, struct jffs2_sb_info c)`
486			`{`
487			`struct jffs2_node_frag *frag;`
488			`struct jffs2_node_frag *parent;`
489
490			`if (!root->rb_node)`
491			`return;`
492
493			`JFFS2_DBG_FRAGTREE("killing\n");`
494
495			`frag = (rb_entry(root->rb_node, struct jffs2_node_frag, rb));`
496			`while(frag) {`
497			`if (frag->rb.rb_left) {`
498			`JFFS2_DBG_FRAGTREE2("going left from frag (%p) %#04x-%#04x\n",`
499			`frag, frag->ofs, frag->ofs+frag->size);`
500			`frag = frag_left(frag);`
501			`continue;`
502			`}`
503			`if (frag->rb.rb_right) {`
504			`JFFS2_DBG_FRAGTREE2("going right from frag (%p) %#04x-%#04x\n",`
505			`frag, frag->ofs, frag->ofs+frag->size);`
506			`frag = frag_right(frag);`
507			`continue;`
508			`}`
509
510			`JFFS2_DBG_FRAGTREE2("frag %#04x-%#04x: node %p, frags %d\n",`
511			`frag->ofs, frag->ofs+frag->size, frag->node, frag->node?frag->node->frags:0);`
512
513			`if (frag->node && !(--frag->node->frags)) {`
514			`/* Not a hole, and it's the final remaining frag`
515			`of this node. Free the node */`
516			`if (c)`
517			`jffs2_mark_node_obsolete(c, frag->node->raw);`
518
519			`jffs2_free_full_dnode(frag->node);`
520			`}`
521			`parent = frag_parent(frag);`
522			`if (parent) {`
523			`if (frag_left(parent) == frag)`
524			`parent->rb.rb_left = NULL;`
525			`else`
526			`parent->rb.rb_right = NULL;`
527			`}`
528
529			`jffs2_free_node_frag(frag);`
530			`frag = parent;`
531
532			`cond_resched();`
533			`}`
534			`}`