11da177e4SLinus Torvalds /* 21da177e4SLinus Torvalds * JFFS2 -- Journalling Flash File System, Version 2. 31da177e4SLinus Torvalds * 41da177e4SLinus Torvalds * Copyright (C) 2001-2003 Red Hat, Inc. 51da177e4SLinus Torvalds * 61da177e4SLinus Torvalds * Created by David Woodhouse <dwmw2@infradead.org> 71da177e4SLinus Torvalds * 81da177e4SLinus Torvalds * For licensing information, see the file 'LICENCE' in this directory. 91da177e4SLinus Torvalds * 10f97117d1SArtem B. Bityutskiy * $Id: nodelist.c,v 1.101 2005/07/27 14:46:11 dedekind Exp $ 111da177e4SLinus Torvalds * 121da177e4SLinus Torvalds */ 131da177e4SLinus Torvalds 141da177e4SLinus Torvalds #include <linux/kernel.h> 151da177e4SLinus Torvalds #include <linux/sched.h> 161da177e4SLinus Torvalds #include <linux/fs.h> 171da177e4SLinus Torvalds #include <linux/mtd/mtd.h> 181da177e4SLinus Torvalds #include <linux/rbtree.h> 191da177e4SLinus Torvalds #include <linux/crc32.h> 201da177e4SLinus Torvalds #include <linux/slab.h> 211da177e4SLinus Torvalds #include <linux/pagemap.h> 221da177e4SLinus Torvalds #include "nodelist.h" 231da177e4SLinus Torvalds 241da177e4SLinus Torvalds void jffs2_add_fd_to_list(struct jffs2_sb_info *c, struct jffs2_full_dirent *new, struct jffs2_full_dirent **list) 251da177e4SLinus Torvalds { 261da177e4SLinus Torvalds struct jffs2_full_dirent **prev = list; 271da177e4SLinus Torvalds D1(printk(KERN_DEBUG "jffs2_add_fd_to_list( %p, %p (->%p))\n", new, list, *list)); 281da177e4SLinus Torvalds 291da177e4SLinus Torvalds while ((*prev) && (*prev)->nhash <= new->nhash) { 301da177e4SLinus Torvalds if ((*prev)->nhash == new->nhash && !strcmp((*prev)->name, new->name)) { 311da177e4SLinus Torvalds /* Duplicate. Free one */ 321da177e4SLinus Torvalds if (new->version < (*prev)->version) { 331da177e4SLinus Torvalds D1(printk(KERN_DEBUG "Eep! Marking new dirent node obsolete\n")); 341da177e4SLinus Torvalds D1(printk(KERN_DEBUG "New dirent is \"%s\"->ino #%u. Old is \"%s\"->ino #%u\n", new->name, new->ino, (*prev)->name, (*prev)->ino)); 351da177e4SLinus Torvalds jffs2_mark_node_obsolete(c, new->raw); 361da177e4SLinus Torvalds jffs2_free_full_dirent(new); 371da177e4SLinus Torvalds } else { 381da177e4SLinus Torvalds D1(printk(KERN_DEBUG "Marking old dirent node (ino #%u) obsolete\n", (*prev)->ino)); 391da177e4SLinus Torvalds new->next = (*prev)->next; 401da177e4SLinus Torvalds jffs2_mark_node_obsolete(c, ((*prev)->raw)); 411da177e4SLinus Torvalds jffs2_free_full_dirent(*prev); 421da177e4SLinus Torvalds *prev = new; 431da177e4SLinus Torvalds } 441da177e4SLinus Torvalds goto out; 451da177e4SLinus Torvalds } 461da177e4SLinus Torvalds prev = &((*prev)->next); 471da177e4SLinus Torvalds } 481da177e4SLinus Torvalds new->next = *prev; 491da177e4SLinus Torvalds *prev = new; 501da177e4SLinus Torvalds 511da177e4SLinus Torvalds out: 521da177e4SLinus Torvalds D2(while(*list) { 531da177e4SLinus Torvalds printk(KERN_DEBUG "Dirent \"%s\" (hash 0x%08x, ino #%u\n", (*list)->name, (*list)->nhash, (*list)->ino); 541da177e4SLinus Torvalds list = &(*list)->next; 551da177e4SLinus Torvalds }); 561da177e4SLinus Torvalds } 571da177e4SLinus Torvalds 58f97117d1SArtem B. Bityutskiy void jffs2_obsolete_node_frag(struct jffs2_sb_info *c, struct jffs2_node_frag *this) 591da177e4SLinus Torvalds { 60f97117d1SArtem B. Bityutskiy if (this->node) { 61f97117d1SArtem B. Bityutskiy this->node->frags--; 62f97117d1SArtem B. Bityutskiy if (!this->node->frags) { 63f97117d1SArtem B. Bityutskiy /* The node has no valid frags left. It's totally obsoleted */ 64f97117d1SArtem B. Bityutskiy D2(printk(KERN_DEBUG "Marking old node @0x%08x (0x%04x-0x%04x) obsolete\n", 65f97117d1SArtem B. Bityutskiy ref_offset(this->node->raw), this->node->ofs, this->node->ofs+this->node->size)); 66f97117d1SArtem B. Bityutskiy jffs2_mark_node_obsolete(c, this->node->raw); 67f97117d1SArtem B. Bityutskiy jffs2_free_full_dnode(this->node); 68f97117d1SArtem B. Bityutskiy } else { 69f97117d1SArtem B. Bityutskiy D2(printk(KERN_DEBUG "Marking old node @0x%08x (0x%04x-0x%04x) REF_NORMAL. frags is %d\n", 70f97117d1SArtem B. Bityutskiy ref_offset(this->node->raw), this->node->ofs, this->node->ofs+this->node->size, 71f97117d1SArtem B. Bityutskiy this->node->frags)); 72f97117d1SArtem B. Bityutskiy mark_ref_normal(this->node->raw); 731da177e4SLinus Torvalds } 741da177e4SLinus Torvalds 75f97117d1SArtem B. Bityutskiy } 76f97117d1SArtem B. Bityutskiy jffs2_free_node_frag(this); 779dee7503SDavid Woodhouse } 789dee7503SDavid Woodhouse 79f97117d1SArtem B. Bityutskiy static void jffs2_fragtree_insert(struct jffs2_node_frag *newfrag, struct jffs2_node_frag *base) 801da177e4SLinus Torvalds { 81f97117d1SArtem B. Bityutskiy struct rb_node *parent = &base->rb; 82f97117d1SArtem B. Bityutskiy struct rb_node **link = &parent; 831da177e4SLinus Torvalds 84f97117d1SArtem B. Bityutskiy D2(printk(KERN_DEBUG "jffs2_fragtree_insert(%p; %d-%d, %p)\n", newfrag, 85f97117d1SArtem B. Bityutskiy newfrag->ofs, newfrag->ofs+newfrag->size, base)); 869dee7503SDavid Woodhouse 87f97117d1SArtem B. Bityutskiy while (*link) { 88f97117d1SArtem B. Bityutskiy parent = *link; 89f97117d1SArtem B. Bityutskiy base = rb_entry(parent, struct jffs2_node_frag, rb); 90f97117d1SArtem B. Bityutskiy 91f97117d1SArtem B. Bityutskiy D2(printk(KERN_DEBUG "fragtree_insert considering frag at 0x%x\n", base->ofs)); 92f97117d1SArtem B. Bityutskiy if (newfrag->ofs > base->ofs) 93f97117d1SArtem B. Bityutskiy link = &base->rb.rb_right; 94f97117d1SArtem B. Bityutskiy else if (newfrag->ofs < base->ofs) 95f97117d1SArtem B. Bityutskiy link = &base->rb.rb_left; 969dee7503SDavid Woodhouse else { 97f97117d1SArtem B. Bityutskiy printk(KERN_CRIT "Duplicate frag at %08x (%p,%p)\n", newfrag->ofs, newfrag, base); 98dae6227fSArtem B. Bityutskiy BUG(); 99dae6227fSArtem B. Bityutskiy } 100dae6227fSArtem B. Bityutskiy } 101dae6227fSArtem B. Bityutskiy 102f97117d1SArtem B. Bityutskiy rb_link_node(&newfrag->rb, &base->rb, link); 103dae6227fSArtem B. Bityutskiy } 104dae6227fSArtem B. Bityutskiy 105f97117d1SArtem B. Bityutskiy /* Doesn't set inode->i_size */ 106f97117d1SArtem B. Bityutskiy static int jffs2_add_frag_to_fragtree(struct jffs2_sb_info *c, struct rb_root *list, struct jffs2_node_frag *newfrag) 1071da177e4SLinus Torvalds { 108f97117d1SArtem B. Bityutskiy struct jffs2_node_frag *this; 109f97117d1SArtem B. Bityutskiy uint32_t lastend; 1101da177e4SLinus Torvalds 111f97117d1SArtem B. Bityutskiy /* Skip all the nodes which are completed before this one starts */ 112f97117d1SArtem B. Bityutskiy this = jffs2_lookup_node_frag(list, newfrag->node->ofs); 1131da177e4SLinus Torvalds 114f97117d1SArtem B. Bityutskiy if (this) { 115f97117d1SArtem B. Bityutskiy D2(printk(KERN_DEBUG "j_a_f_d_t_f: Lookup gave frag 0x%04x-0x%04x; phys 0x%08x (*%p)\n", 116f97117d1SArtem B. Bityutskiy this->ofs, this->ofs+this->size, this->node?(ref_offset(this->node->raw)):0xffffffff, this)); 117f97117d1SArtem B. Bityutskiy lastend = this->ofs + this->size; 118f97117d1SArtem B. Bityutskiy } else { 119f97117d1SArtem B. Bityutskiy D2(printk(KERN_DEBUG "j_a_f_d_t_f: Lookup gave no frag\n")); 120f97117d1SArtem B. Bityutskiy lastend = 0; 121f97117d1SArtem B. Bityutskiy } 1221da177e4SLinus Torvalds 123f97117d1SArtem B. Bityutskiy /* See if we ran off the end of the list */ 124f97117d1SArtem B. Bityutskiy if (lastend <= newfrag->ofs) { 125f97117d1SArtem B. Bityutskiy /* We did */ 1261da177e4SLinus Torvalds 127f97117d1SArtem B. Bityutskiy /* Check if 'this' node was on the same page as the new node. 128f97117d1SArtem B. Bityutskiy If so, both 'this' and the new node get marked REF_NORMAL so 129f97117d1SArtem B. Bityutskiy the GC can take a look. 1301da177e4SLinus Torvalds */ 131f97117d1SArtem B. Bityutskiy if (lastend && (lastend-1) >> PAGE_CACHE_SHIFT == newfrag->ofs >> PAGE_CACHE_SHIFT) { 132f97117d1SArtem B. Bityutskiy if (this->node) 133f97117d1SArtem B. Bityutskiy mark_ref_normal(this->node->raw); 134f97117d1SArtem B. Bityutskiy mark_ref_normal(newfrag->node->raw); 1351da177e4SLinus Torvalds } 1361da177e4SLinus Torvalds 137f97117d1SArtem B. Bityutskiy if (lastend < newfrag->node->ofs) { 138f97117d1SArtem B. Bityutskiy /* ... and we need to put a hole in before the new node */ 139f97117d1SArtem B. Bityutskiy struct jffs2_node_frag *holefrag = jffs2_alloc_node_frag(); 140f97117d1SArtem B. Bityutskiy if (!holefrag) { 141f97117d1SArtem B. Bityutskiy jffs2_free_node_frag(newfrag); 142f97117d1SArtem B. Bityutskiy return -ENOMEM; 143f97117d1SArtem B. Bityutskiy } 144f97117d1SArtem B. Bityutskiy holefrag->ofs = lastend; 145f97117d1SArtem B. Bityutskiy holefrag->size = newfrag->node->ofs - lastend; 146f97117d1SArtem B. Bityutskiy holefrag->node = NULL; 147f97117d1SArtem B. Bityutskiy if (this) { 148f97117d1SArtem B. Bityutskiy /* By definition, the 'this' node has no right-hand child, 149f97117d1SArtem B. Bityutskiy because there are no frags with offset greater than it. 150f97117d1SArtem B. Bityutskiy So that's where we want to put the hole */ 151f97117d1SArtem B. Bityutskiy D2(printk(KERN_DEBUG "Adding hole frag (%p) on right of node at (%p)\n", holefrag, this)); 152f97117d1SArtem B. Bityutskiy rb_link_node(&holefrag->rb, &this->rb, &this->rb.rb_right); 153f97117d1SArtem B. Bityutskiy } else { 154f97117d1SArtem B. Bityutskiy D2(printk(KERN_DEBUG "Adding hole frag (%p) at root of tree\n", holefrag)); 155f97117d1SArtem B. Bityutskiy rb_link_node(&holefrag->rb, NULL, &list->rb_node); 156f97117d1SArtem B. Bityutskiy } 157f97117d1SArtem B. Bityutskiy rb_insert_color(&holefrag->rb, list); 158f97117d1SArtem B. Bityutskiy this = holefrag; 159f97117d1SArtem B. Bityutskiy } 160f97117d1SArtem B. Bityutskiy if (this) { 161f97117d1SArtem B. Bityutskiy /* By definition, the 'this' node has no right-hand child, 162f97117d1SArtem B. Bityutskiy because there are no frags with offset greater than it. 163f97117d1SArtem B. Bityutskiy So that's where we want to put new fragment */ 164f97117d1SArtem B. Bityutskiy D2(printk(KERN_DEBUG "Adding new frag (%p) on right of node at (%p)\n", newfrag, this)); 165f97117d1SArtem B. Bityutskiy rb_link_node(&newfrag->rb, &this->rb, &this->rb.rb_right); 166f97117d1SArtem B. Bityutskiy } else { 167f97117d1SArtem B. Bityutskiy D2(printk(KERN_DEBUG "Adding new frag (%p) at root of tree\n", newfrag)); 168f97117d1SArtem B. Bityutskiy rb_link_node(&newfrag->rb, NULL, &list->rb_node); 169f97117d1SArtem B. Bityutskiy } 170f97117d1SArtem B. Bityutskiy rb_insert_color(&newfrag->rb, list); 171f97117d1SArtem B. Bityutskiy return 0; 1721da177e4SLinus Torvalds } 173dae6227fSArtem B. Bityutskiy 174f97117d1SArtem B. Bityutskiy D2(printk(KERN_DEBUG "j_a_f_d_t_f: dealing with frag 0x%04x-0x%04x; phys 0x%08x (*%p)\n", 175f97117d1SArtem B. Bityutskiy this->ofs, this->ofs+this->size, this->node?(ref_offset(this->node->raw)):0xffffffff, this)); 176dae6227fSArtem B. Bityutskiy 177f97117d1SArtem B. Bityutskiy /* OK. 'this' is pointing at the first frag that newfrag->ofs at least partially obsoletes, 178f97117d1SArtem B. Bityutskiy * - i.e. newfrag->ofs < this->ofs+this->size && newfrag->ofs >= this->ofs 179f97117d1SArtem B. Bityutskiy */ 180f97117d1SArtem B. Bityutskiy if (newfrag->ofs > this->ofs) { 181f97117d1SArtem B. Bityutskiy /* This node isn't completely obsoleted. The start of it remains valid */ 1821da177e4SLinus Torvalds 183f97117d1SArtem B. Bityutskiy /* Mark the new node and the partially covered node REF_NORMAL -- let 184f97117d1SArtem B. Bityutskiy the GC take a look at them */ 185f97117d1SArtem B. Bityutskiy mark_ref_normal(newfrag->node->raw); 186f97117d1SArtem B. Bityutskiy if (this->node) 187f97117d1SArtem B. Bityutskiy mark_ref_normal(this->node->raw); 1881da177e4SLinus Torvalds 189f97117d1SArtem B. Bityutskiy if (this->ofs + this->size > newfrag->ofs + newfrag->size) { 190f97117d1SArtem B. Bityutskiy /* The new node splits 'this' frag into two */ 191f97117d1SArtem B. Bityutskiy struct jffs2_node_frag *newfrag2 = jffs2_alloc_node_frag(); 192f97117d1SArtem B. Bityutskiy if (!newfrag2) { 193f97117d1SArtem B. Bityutskiy jffs2_free_node_frag(newfrag); 194f97117d1SArtem B. Bityutskiy return -ENOMEM; 1951da177e4SLinus Torvalds } 196f97117d1SArtem B. Bityutskiy D2(printk(KERN_DEBUG "split old frag 0x%04x-0x%04x -->", this->ofs, this->ofs+this->size); 197f97117d1SArtem B. Bityutskiy if (this->node) 198f97117d1SArtem B. Bityutskiy printk("phys 0x%08x\n", ref_offset(this->node->raw)); 199f97117d1SArtem B. Bityutskiy else 200f97117d1SArtem B. Bityutskiy printk("hole\n"); 201f97117d1SArtem B. Bityutskiy ) 202dae6227fSArtem B. Bityutskiy 203f97117d1SArtem B. Bityutskiy /* New second frag pointing to this's node */ 204f97117d1SArtem B. Bityutskiy newfrag2->ofs = newfrag->ofs + newfrag->size; 205f97117d1SArtem B. Bityutskiy newfrag2->size = (this->ofs+this->size) - newfrag2->ofs; 206f97117d1SArtem B. Bityutskiy newfrag2->node = this->node; 207f97117d1SArtem B. Bityutskiy if (this->node) 208f97117d1SArtem B. Bityutskiy this->node->frags++; 209dae6227fSArtem B. Bityutskiy 210f97117d1SArtem B. Bityutskiy /* Adjust size of original 'this' */ 211f97117d1SArtem B. Bityutskiy this->size = newfrag->ofs - this->ofs; 2121da177e4SLinus Torvalds 213f97117d1SArtem B. Bityutskiy /* Now, we know there's no node with offset 214f97117d1SArtem B. Bityutskiy greater than this->ofs but smaller than 215f97117d1SArtem B. Bityutskiy newfrag2->ofs or newfrag->ofs, for obvious 216f97117d1SArtem B. Bityutskiy reasons. So we can do a tree insert from 217f97117d1SArtem B. Bityutskiy 'this' to insert newfrag, and a tree insert 218f97117d1SArtem B. Bityutskiy from newfrag to insert newfrag2. */ 219f97117d1SArtem B. Bityutskiy jffs2_fragtree_insert(newfrag, this); 220f97117d1SArtem B. Bityutskiy rb_insert_color(&newfrag->rb, list); 2211da177e4SLinus Torvalds 222f97117d1SArtem B. Bityutskiy jffs2_fragtree_insert(newfrag2, newfrag); 223f97117d1SArtem B. Bityutskiy rb_insert_color(&newfrag2->rb, list); 2241da177e4SLinus Torvalds 2251da177e4SLinus Torvalds return 0; 2261da177e4SLinus Torvalds } 227f97117d1SArtem B. Bityutskiy /* New node just reduces 'this' frag in size, doesn't split it */ 228f97117d1SArtem B. Bityutskiy this->size = newfrag->ofs - this->ofs; 229f97117d1SArtem B. Bityutskiy 230f97117d1SArtem B. Bityutskiy /* Again, we know it lives down here in the tree */ 231f97117d1SArtem B. Bityutskiy jffs2_fragtree_insert(newfrag, this); 232f97117d1SArtem B. Bityutskiy rb_insert_color(&newfrag->rb, list); 233f97117d1SArtem B. Bityutskiy } else { 234f97117d1SArtem B. Bityutskiy /* New frag starts at the same point as 'this' used to. Replace 235f97117d1SArtem B. Bityutskiy it in the tree without doing a delete and insertion */ 236f97117d1SArtem B. Bityutskiy D2(printk(KERN_DEBUG "Inserting newfrag (*%p),%d-%d in before 'this' (*%p),%d-%d\n", 237f97117d1SArtem B. Bityutskiy newfrag, newfrag->ofs, newfrag->ofs+newfrag->size, 238f97117d1SArtem B. Bityutskiy this, this->ofs, this->ofs+this->size)); 239f97117d1SArtem B. Bityutskiy 240f97117d1SArtem B. Bityutskiy rb_replace_node(&this->rb, &newfrag->rb, list); 241f97117d1SArtem B. Bityutskiy 242f97117d1SArtem B. Bityutskiy if (newfrag->ofs + newfrag->size >= this->ofs+this->size) { 243f97117d1SArtem B. Bityutskiy D2(printk(KERN_DEBUG "Obsoleting node frag %p (%x-%x)\n", this, this->ofs, this->ofs+this->size)); 244f97117d1SArtem B. Bityutskiy jffs2_obsolete_node_frag(c, this); 245f97117d1SArtem B. Bityutskiy } else { 246f97117d1SArtem B. Bityutskiy this->ofs += newfrag->size; 247f97117d1SArtem B. Bityutskiy this->size -= newfrag->size; 248f97117d1SArtem B. Bityutskiy 249f97117d1SArtem B. Bityutskiy jffs2_fragtree_insert(this, newfrag); 250f97117d1SArtem B. Bityutskiy rb_insert_color(&this->rb, list); 251f97117d1SArtem B. Bityutskiy return 0; 252f97117d1SArtem B. Bityutskiy } 253f97117d1SArtem B. Bityutskiy } 254f97117d1SArtem B. Bityutskiy /* OK, now we have newfrag added in the correct place in the tree, but 255f97117d1SArtem B. Bityutskiy frag_next(newfrag) may be a fragment which is overlapped by it 256f97117d1SArtem B. Bityutskiy */ 257f97117d1SArtem B. Bityutskiy while ((this = frag_next(newfrag)) && newfrag->ofs + newfrag->size >= this->ofs + this->size) { 258f97117d1SArtem B. Bityutskiy /* 'this' frag is obsoleted completely. */ 259f97117d1SArtem B. Bityutskiy D2(printk(KERN_DEBUG "Obsoleting node frag %p (%x-%x) and removing from tree\n", this, this->ofs, this->ofs+this->size)); 260f97117d1SArtem B. Bityutskiy rb_erase(&this->rb, list); 261f97117d1SArtem B. Bityutskiy jffs2_obsolete_node_frag(c, this); 262f97117d1SArtem B. Bityutskiy } 263f97117d1SArtem B. Bityutskiy /* Now we're pointing at the first frag which isn't totally obsoleted by 264f97117d1SArtem B. Bityutskiy the new frag */ 265f97117d1SArtem B. Bityutskiy 266f97117d1SArtem B. Bityutskiy if (!this || newfrag->ofs + newfrag->size == this->ofs) { 267f97117d1SArtem B. Bityutskiy return 0; 268f97117d1SArtem B. Bityutskiy } 269f97117d1SArtem B. Bityutskiy /* Still some overlap but we don't need to move it in the tree */ 270f97117d1SArtem B. Bityutskiy this->size = (this->ofs + this->size) - (newfrag->ofs + newfrag->size); 271f97117d1SArtem B. Bityutskiy this->ofs = newfrag->ofs + newfrag->size; 272f97117d1SArtem B. Bityutskiy 273f97117d1SArtem B. Bityutskiy /* And mark them REF_NORMAL so the GC takes a look at them */ 274f97117d1SArtem B. Bityutskiy if (this->node) 275f97117d1SArtem B. Bityutskiy mark_ref_normal(this->node->raw); 276f97117d1SArtem B. Bityutskiy mark_ref_normal(newfrag->node->raw); 277f97117d1SArtem B. Bityutskiy 278f97117d1SArtem B. Bityutskiy return 0; 279f97117d1SArtem B. Bityutskiy } 280f97117d1SArtem B. Bityutskiy 281f97117d1SArtem B. Bityutskiy /* Given an inode, probably with existing list of fragments, add the new node 282f97117d1SArtem B. Bityutskiy * to the fragment list. 283f97117d1SArtem B. Bityutskiy */ 284f97117d1SArtem B. Bityutskiy int jffs2_add_full_dnode_to_inode(struct jffs2_sb_info *c, struct jffs2_inode_info *f, struct jffs2_full_dnode *fn) 285f97117d1SArtem B. Bityutskiy { 286f97117d1SArtem B. Bityutskiy int ret; 287f97117d1SArtem B. Bityutskiy struct jffs2_node_frag *newfrag; 288f97117d1SArtem B. Bityutskiy 289f97117d1SArtem B. Bityutskiy D1(printk(KERN_DEBUG "jffs2_add_full_dnode_to_inode(ino #%u, f %p, fn %p)\n", f->inocache->ino, f, fn)); 290f97117d1SArtem B. Bityutskiy 291f97117d1SArtem B. Bityutskiy if (unlikely(!fn->size)) 292f97117d1SArtem B. Bityutskiy return 0; 293f97117d1SArtem B. Bityutskiy 294f97117d1SArtem B. Bityutskiy newfrag = jffs2_alloc_node_frag(); 295f97117d1SArtem B. Bityutskiy if (unlikely(!newfrag)) 296f97117d1SArtem B. Bityutskiy return -ENOMEM; 297f97117d1SArtem B. Bityutskiy 298f97117d1SArtem B. Bityutskiy D2(printk(KERN_DEBUG "adding node %04x-%04x @0x%08x on flash, newfrag *%p\n", 299f97117d1SArtem B. Bityutskiy fn->ofs, fn->ofs+fn->size, ref_offset(fn->raw), newfrag)); 300f97117d1SArtem B. Bityutskiy 301f97117d1SArtem B. Bityutskiy newfrag->ofs = fn->ofs; 302f97117d1SArtem B. Bityutskiy newfrag->size = fn->size; 303f97117d1SArtem B. Bityutskiy newfrag->node = fn; 304f97117d1SArtem B. Bityutskiy newfrag->node->frags = 1; 305f97117d1SArtem B. Bityutskiy 306f97117d1SArtem B. Bityutskiy ret = jffs2_add_frag_to_fragtree(c, &f->fragtree, newfrag); 307f97117d1SArtem B. Bityutskiy if (unlikely(ret)) 308f97117d1SArtem B. Bityutskiy return ret; 309f97117d1SArtem B. Bityutskiy 310f97117d1SArtem B. Bityutskiy /* If we now share a page with other nodes, mark either previous 311f97117d1SArtem B. Bityutskiy or next node REF_NORMAL, as appropriate. */ 312f97117d1SArtem B. Bityutskiy if (newfrag->ofs & (PAGE_CACHE_SIZE-1)) { 313f97117d1SArtem B. Bityutskiy struct jffs2_node_frag *prev = frag_prev(newfrag); 314f97117d1SArtem B. Bityutskiy 315f97117d1SArtem B. Bityutskiy mark_ref_normal(fn->raw); 316f97117d1SArtem B. Bityutskiy /* If we don't start at zero there's _always_ a previous */ 317f97117d1SArtem B. Bityutskiy if (prev->node) 318f97117d1SArtem B. Bityutskiy mark_ref_normal(prev->node->raw); 319f97117d1SArtem B. Bityutskiy } 320f97117d1SArtem B. Bityutskiy 321f97117d1SArtem B. Bityutskiy if ((newfrag->ofs+newfrag->size) & (PAGE_CACHE_SIZE-1)) { 322f97117d1SArtem B. Bityutskiy struct jffs2_node_frag *next = frag_next(newfrag); 323f97117d1SArtem B. Bityutskiy 324f97117d1SArtem B. Bityutskiy if (next) { 325f97117d1SArtem B. Bityutskiy mark_ref_normal(fn->raw); 326f97117d1SArtem B. Bityutskiy if (next->node) 327f97117d1SArtem B. Bityutskiy mark_ref_normal(next->node->raw); 328f97117d1SArtem B. Bityutskiy } 329f97117d1SArtem B. Bityutskiy } 330f97117d1SArtem B. Bityutskiy jffs2_dbg_fragtree_paranoia_check_nolock(f); 331f97117d1SArtem B. Bityutskiy jffs2_dbg_dump_fragtree_nolock(f); 332f97117d1SArtem B. Bityutskiy return 0; 333f97117d1SArtem B. Bityutskiy } 334f97117d1SArtem B. Bityutskiy 3351da177e4SLinus Torvalds 3361da177e4SLinus Torvalds void jffs2_set_inocache_state(struct jffs2_sb_info *c, struct jffs2_inode_cache *ic, int state) 3371da177e4SLinus Torvalds { 3381da177e4SLinus Torvalds spin_lock(&c->inocache_lock); 3391da177e4SLinus Torvalds ic->state = state; 3401da177e4SLinus Torvalds wake_up(&c->inocache_wq); 3411da177e4SLinus Torvalds spin_unlock(&c->inocache_lock); 3421da177e4SLinus Torvalds } 3431da177e4SLinus Torvalds 3441da177e4SLinus Torvalds /* During mount, this needs no locking. During normal operation, its 3451da177e4SLinus Torvalds callers want to do other stuff while still holding the inocache_lock. 3461da177e4SLinus Torvalds Rather than introducing special case get_ino_cache functions or 3471da177e4SLinus Torvalds callbacks, we just let the caller do the locking itself. */ 3481da177e4SLinus Torvalds 3491da177e4SLinus Torvalds struct jffs2_inode_cache *jffs2_get_ino_cache(struct jffs2_sb_info *c, uint32_t ino) 3501da177e4SLinus Torvalds { 3511da177e4SLinus Torvalds struct jffs2_inode_cache *ret; 3521da177e4SLinus Torvalds 3531da177e4SLinus Torvalds D2(printk(KERN_DEBUG "jffs2_get_ino_cache(): ino %u\n", ino)); 3541da177e4SLinus Torvalds 3551da177e4SLinus Torvalds ret = c->inocache_list[ino % INOCACHE_HASHSIZE]; 3561da177e4SLinus Torvalds while (ret && ret->ino < ino) { 3571da177e4SLinus Torvalds ret = ret->next; 3581da177e4SLinus Torvalds } 3591da177e4SLinus Torvalds 3601da177e4SLinus Torvalds if (ret && ret->ino != ino) 3611da177e4SLinus Torvalds ret = NULL; 3621da177e4SLinus Torvalds 3631da177e4SLinus Torvalds D2(printk(KERN_DEBUG "jffs2_get_ino_cache found %p for ino %u\n", ret, ino)); 3641da177e4SLinus Torvalds return ret; 3651da177e4SLinus Torvalds } 3661da177e4SLinus Torvalds 3671da177e4SLinus Torvalds void jffs2_add_ino_cache (struct jffs2_sb_info *c, struct jffs2_inode_cache *new) 3681da177e4SLinus Torvalds { 3691da177e4SLinus Torvalds struct jffs2_inode_cache **prev; 3707d27c814SThomas Gleixner 3711da177e4SLinus Torvalds spin_lock(&c->inocache_lock); 3727d200960SDavid Woodhouse if (!new->ino) 3737d200960SDavid Woodhouse new->ino = ++c->highest_ino; 3747d200960SDavid Woodhouse 3757d200960SDavid Woodhouse D2(printk(KERN_DEBUG "jffs2_add_ino_cache: Add %p (ino #%u)\n", new, new->ino)); 3761da177e4SLinus Torvalds 3771da177e4SLinus Torvalds prev = &c->inocache_list[new->ino % INOCACHE_HASHSIZE]; 3781da177e4SLinus Torvalds 3791da177e4SLinus Torvalds while ((*prev) && (*prev)->ino < new->ino) { 3801da177e4SLinus Torvalds prev = &(*prev)->next; 3811da177e4SLinus Torvalds } 3821da177e4SLinus Torvalds new->next = *prev; 3831da177e4SLinus Torvalds *prev = new; 3841da177e4SLinus Torvalds 3851da177e4SLinus Torvalds spin_unlock(&c->inocache_lock); 3861da177e4SLinus Torvalds } 3871da177e4SLinus Torvalds 3881da177e4SLinus Torvalds void jffs2_del_ino_cache(struct jffs2_sb_info *c, struct jffs2_inode_cache *old) 3891da177e4SLinus Torvalds { 3901da177e4SLinus Torvalds struct jffs2_inode_cache **prev; 39167e345d1SDavid Woodhouse D1(printk(KERN_DEBUG "jffs2_del_ino_cache: Del %p (ino #%u)\n", old, old->ino)); 3921da177e4SLinus Torvalds spin_lock(&c->inocache_lock); 3931da177e4SLinus Torvalds 3941da177e4SLinus Torvalds prev = &c->inocache_list[old->ino % INOCACHE_HASHSIZE]; 3951da177e4SLinus Torvalds 3961da177e4SLinus Torvalds while ((*prev) && (*prev)->ino < old->ino) { 3971da177e4SLinus Torvalds prev = &(*prev)->next; 3981da177e4SLinus Torvalds } 3991da177e4SLinus Torvalds if ((*prev) == old) { 4001da177e4SLinus Torvalds *prev = old->next; 4011da177e4SLinus Torvalds } 4021da177e4SLinus Torvalds 40367e345d1SDavid Woodhouse /* Free it now unless it's in READING or CLEARING state, which 40467e345d1SDavid Woodhouse are the transitions upon read_inode() and clear_inode(). The 40567e345d1SDavid Woodhouse rest of the time we know nobody else is looking at it, and 40667e345d1SDavid Woodhouse if it's held by read_inode() or clear_inode() they'll free it 40767e345d1SDavid Woodhouse for themselves. */ 40867e345d1SDavid Woodhouse if (old->state != INO_STATE_READING && old->state != INO_STATE_CLEARING) 40967e345d1SDavid Woodhouse jffs2_free_inode_cache(old); 41067e345d1SDavid Woodhouse 4111da177e4SLinus Torvalds spin_unlock(&c->inocache_lock); 4121da177e4SLinus Torvalds } 4131da177e4SLinus Torvalds 4141da177e4SLinus Torvalds void jffs2_free_ino_caches(struct jffs2_sb_info *c) 4151da177e4SLinus Torvalds { 4161da177e4SLinus Torvalds int i; 4171da177e4SLinus Torvalds struct jffs2_inode_cache *this, *next; 4181da177e4SLinus Torvalds 4191da177e4SLinus Torvalds for (i=0; i<INOCACHE_HASHSIZE; i++) { 4201da177e4SLinus Torvalds this = c->inocache_list[i]; 4211da177e4SLinus Torvalds while (this) { 4221da177e4SLinus Torvalds next = this->next; 4231da177e4SLinus Torvalds jffs2_free_inode_cache(this); 4241da177e4SLinus Torvalds this = next; 4251da177e4SLinus Torvalds } 4261da177e4SLinus Torvalds c->inocache_list[i] = NULL; 4271da177e4SLinus Torvalds } 4281da177e4SLinus Torvalds } 4291da177e4SLinus Torvalds 4301da177e4SLinus Torvalds void jffs2_free_raw_node_refs(struct jffs2_sb_info *c) 4311da177e4SLinus Torvalds { 4321da177e4SLinus Torvalds int i; 4331da177e4SLinus Torvalds struct jffs2_raw_node_ref *this, *next; 4341da177e4SLinus Torvalds 4351da177e4SLinus Torvalds for (i=0; i<c->nr_blocks; i++) { 4361da177e4SLinus Torvalds this = c->blocks[i].first_node; 4371da177e4SLinus Torvalds while(this) { 4381da177e4SLinus Torvalds next = this->next_phys; 4391da177e4SLinus Torvalds jffs2_free_raw_node_ref(this); 4401da177e4SLinus Torvalds this = next; 4411da177e4SLinus Torvalds } 4421da177e4SLinus Torvalds c->blocks[i].first_node = c->blocks[i].last_node = NULL; 4431da177e4SLinus Torvalds } 4441da177e4SLinus Torvalds } 4451da177e4SLinus Torvalds 4461da177e4SLinus Torvalds struct jffs2_node_frag *jffs2_lookup_node_frag(struct rb_root *fragtree, uint32_t offset) 4471da177e4SLinus Torvalds { 4481da177e4SLinus Torvalds /* The common case in lookup is that there will be a node 4491da177e4SLinus Torvalds which precisely matches. So we go looking for that first */ 4501da177e4SLinus Torvalds struct rb_node *next; 4511da177e4SLinus Torvalds struct jffs2_node_frag *prev = NULL; 4521da177e4SLinus Torvalds struct jffs2_node_frag *frag = NULL; 4531da177e4SLinus Torvalds 4541da177e4SLinus Torvalds D2(printk(KERN_DEBUG "jffs2_lookup_node_frag(%p, %d)\n", fragtree, offset)); 4551da177e4SLinus Torvalds 4561da177e4SLinus Torvalds next = fragtree->rb_node; 4571da177e4SLinus Torvalds 4581da177e4SLinus Torvalds while(next) { 4591da177e4SLinus Torvalds frag = rb_entry(next, struct jffs2_node_frag, rb); 4601da177e4SLinus Torvalds 4611da177e4SLinus Torvalds D2(printk(KERN_DEBUG "Considering frag %d-%d (%p). left %p, right %p\n", 4621da177e4SLinus Torvalds frag->ofs, frag->ofs+frag->size, frag, frag->rb.rb_left, frag->rb.rb_right)); 4631da177e4SLinus Torvalds if (frag->ofs + frag->size <= offset) { 4641da177e4SLinus Torvalds D2(printk(KERN_DEBUG "Going right from frag %d-%d, before the region we care about\n", 4651da177e4SLinus Torvalds frag->ofs, frag->ofs+frag->size)); 4661da177e4SLinus Torvalds /* Remember the closest smaller match on the way down */ 4671da177e4SLinus Torvalds if (!prev || frag->ofs > prev->ofs) 4681da177e4SLinus Torvalds prev = frag; 4691da177e4SLinus Torvalds next = frag->rb.rb_right; 4701da177e4SLinus Torvalds } else if (frag->ofs > offset) { 4711da177e4SLinus Torvalds D2(printk(KERN_DEBUG "Going left from frag %d-%d, after the region we care about\n", 4721da177e4SLinus Torvalds frag->ofs, frag->ofs+frag->size)); 4731da177e4SLinus Torvalds next = frag->rb.rb_left; 4741da177e4SLinus Torvalds } else { 4751da177e4SLinus Torvalds D2(printk(KERN_DEBUG "Returning frag %d,%d, matched\n", 4761da177e4SLinus Torvalds frag->ofs, frag->ofs+frag->size)); 4771da177e4SLinus Torvalds return frag; 4781da177e4SLinus Torvalds } 4791da177e4SLinus Torvalds } 4801da177e4SLinus Torvalds 4811da177e4SLinus Torvalds /* Exact match not found. Go back up looking at each parent, 4821da177e4SLinus Torvalds and return the closest smaller one */ 4831da177e4SLinus Torvalds 4841da177e4SLinus Torvalds if (prev) 4851da177e4SLinus Torvalds D2(printk(KERN_DEBUG "No match. Returning frag %d,%d, closest previous\n", 4861da177e4SLinus Torvalds prev->ofs, prev->ofs+prev->size)); 4871da177e4SLinus Torvalds else 4881da177e4SLinus Torvalds D2(printk(KERN_DEBUG "Returning NULL, empty fragtree\n")); 4891da177e4SLinus Torvalds 4901da177e4SLinus Torvalds return prev; 4911da177e4SLinus Torvalds } 4921da177e4SLinus Torvalds 4931da177e4SLinus Torvalds /* Pass 'c' argument to indicate that nodes should be marked obsolete as 4941da177e4SLinus Torvalds they're killed. */ 4951da177e4SLinus Torvalds void jffs2_kill_fragtree(struct rb_root *root, struct jffs2_sb_info *c) 4961da177e4SLinus Torvalds { 4971da177e4SLinus Torvalds struct jffs2_node_frag *frag; 4981da177e4SLinus Torvalds struct jffs2_node_frag *parent; 4991da177e4SLinus Torvalds 5001da177e4SLinus Torvalds if (!root->rb_node) 5011da177e4SLinus Torvalds return; 5021da177e4SLinus Torvalds 5031da177e4SLinus Torvalds frag = (rb_entry(root->rb_node, struct jffs2_node_frag, rb)); 5041da177e4SLinus Torvalds 5051da177e4SLinus Torvalds while(frag) { 5061da177e4SLinus Torvalds if (frag->rb.rb_left) { 5071da177e4SLinus Torvalds D2(printk(KERN_DEBUG "Going left from frag (%p) %d-%d\n", 5081da177e4SLinus Torvalds frag, frag->ofs, frag->ofs+frag->size)); 5091da177e4SLinus Torvalds frag = frag_left(frag); 5101da177e4SLinus Torvalds continue; 5111da177e4SLinus Torvalds } 5121da177e4SLinus Torvalds if (frag->rb.rb_right) { 5131da177e4SLinus Torvalds D2(printk(KERN_DEBUG "Going right from frag (%p) %d-%d\n", 5141da177e4SLinus Torvalds frag, frag->ofs, frag->ofs+frag->size)); 5151da177e4SLinus Torvalds frag = frag_right(frag); 5161da177e4SLinus Torvalds continue; 5171da177e4SLinus Torvalds } 5181da177e4SLinus Torvalds 5191da177e4SLinus Torvalds D2(printk(KERN_DEBUG "jffs2_kill_fragtree: frag at 0x%x-0x%x: node %p, frags %d--\n", 5201da177e4SLinus Torvalds frag->ofs, frag->ofs+frag->size, frag->node, 5211da177e4SLinus Torvalds frag->node?frag->node->frags:0)); 5221da177e4SLinus Torvalds 5231da177e4SLinus Torvalds if (frag->node && !(--frag->node->frags)) { 5241da177e4SLinus Torvalds /* Not a hole, and it's the final remaining frag 5251da177e4SLinus Torvalds of this node. Free the node */ 5261da177e4SLinus Torvalds if (c) 5271da177e4SLinus Torvalds jffs2_mark_node_obsolete(c, frag->node->raw); 5281da177e4SLinus Torvalds 5291da177e4SLinus Torvalds jffs2_free_full_dnode(frag->node); 5301da177e4SLinus Torvalds } 5311da177e4SLinus Torvalds parent = frag_parent(frag); 5321da177e4SLinus Torvalds if (parent) { 5331da177e4SLinus Torvalds if (frag_left(parent) == frag) 5341da177e4SLinus Torvalds parent->rb.rb_left = NULL; 5351da177e4SLinus Torvalds else 5361da177e4SLinus Torvalds parent->rb.rb_right = NULL; 5371da177e4SLinus Torvalds } 5381da177e4SLinus Torvalds 5391da177e4SLinus Torvalds jffs2_free_node_frag(frag); 5401da177e4SLinus Torvalds frag = parent; 5411da177e4SLinus Torvalds 5421da177e4SLinus Torvalds cond_resched(); 5431da177e4SLinus Torvalds } 5441da177e4SLinus Torvalds } 545