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 * 101da177e4SLinus Torvalds * $Id: nodelist.c,v 1.90 2004/12/08 17:59:20 dwmw2 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 581da177e4SLinus Torvalds /* Put a new tmp_dnode_info into the list, keeping the list in 591da177e4SLinus Torvalds order of increasing version 601da177e4SLinus Torvalds */ 611da177e4SLinus Torvalds static void jffs2_add_tn_to_list(struct jffs2_tmp_dnode_info *tn, struct jffs2_tmp_dnode_info **list) 621da177e4SLinus Torvalds { 631da177e4SLinus Torvalds struct jffs2_tmp_dnode_info **prev = list; 641da177e4SLinus Torvalds 651da177e4SLinus Torvalds while ((*prev) && (*prev)->version < tn->version) { 661da177e4SLinus Torvalds prev = &((*prev)->next); 671da177e4SLinus Torvalds } 681da177e4SLinus Torvalds tn->next = (*prev); 691da177e4SLinus Torvalds *prev = tn; 701da177e4SLinus Torvalds } 711da177e4SLinus Torvalds 721da177e4SLinus Torvalds static void jffs2_free_tmp_dnode_info_list(struct jffs2_tmp_dnode_info *tn) 731da177e4SLinus Torvalds { 741da177e4SLinus Torvalds struct jffs2_tmp_dnode_info *next; 751da177e4SLinus Torvalds 761da177e4SLinus Torvalds while (tn) { 771da177e4SLinus Torvalds next = tn; 781da177e4SLinus Torvalds tn = tn->next; 791da177e4SLinus Torvalds jffs2_free_full_dnode(next->fn); 801da177e4SLinus Torvalds jffs2_free_tmp_dnode_info(next); 811da177e4SLinus Torvalds } 821da177e4SLinus Torvalds } 831da177e4SLinus Torvalds 841da177e4SLinus Torvalds static void jffs2_free_full_dirent_list(struct jffs2_full_dirent *fd) 851da177e4SLinus Torvalds { 861da177e4SLinus Torvalds struct jffs2_full_dirent *next; 871da177e4SLinus Torvalds 881da177e4SLinus Torvalds while (fd) { 891da177e4SLinus Torvalds next = fd->next; 901da177e4SLinus Torvalds jffs2_free_full_dirent(fd); 911da177e4SLinus Torvalds fd = next; 921da177e4SLinus Torvalds } 931da177e4SLinus Torvalds } 941da177e4SLinus Torvalds 951da177e4SLinus Torvalds /* Returns first valid node after 'ref'. May return 'ref' */ 961da177e4SLinus Torvalds static struct jffs2_raw_node_ref *jffs2_first_valid_node(struct jffs2_raw_node_ref *ref) 971da177e4SLinus Torvalds { 981da177e4SLinus Torvalds while (ref && ref->next_in_ino) { 991da177e4SLinus Torvalds if (!ref_obsolete(ref)) 1001da177e4SLinus Torvalds return ref; 1011da177e4SLinus Torvalds D1(printk(KERN_DEBUG "node at 0x%08x is obsoleted. Ignoring.\n", ref_offset(ref))); 1021da177e4SLinus Torvalds ref = ref->next_in_ino; 1031da177e4SLinus Torvalds } 1041da177e4SLinus Torvalds return NULL; 1051da177e4SLinus Torvalds } 1061da177e4SLinus Torvalds 1071da177e4SLinus Torvalds /* Get tmp_dnode_info and full_dirent for all non-obsolete nodes associated 1081da177e4SLinus Torvalds with this ino, returning the former in order of version */ 1091da177e4SLinus Torvalds 1101da177e4SLinus Torvalds int jffs2_get_inode_nodes(struct jffs2_sb_info *c, struct jffs2_inode_info *f, 1111da177e4SLinus Torvalds struct jffs2_tmp_dnode_info **tnp, struct jffs2_full_dirent **fdp, 1121da177e4SLinus Torvalds uint32_t *highest_version, uint32_t *latest_mctime, 1131da177e4SLinus Torvalds uint32_t *mctime_ver) 1141da177e4SLinus Torvalds { 1151da177e4SLinus Torvalds struct jffs2_raw_node_ref *ref, *valid_ref; 1161da177e4SLinus Torvalds struct jffs2_tmp_dnode_info *tn, *ret_tn = NULL; 1171da177e4SLinus Torvalds struct jffs2_full_dirent *fd, *ret_fd = NULL; 1181da177e4SLinus Torvalds union jffs2_node_union node; 1191da177e4SLinus Torvalds size_t retlen; 1201da177e4SLinus Torvalds int err; 1211da177e4SLinus Torvalds 1221da177e4SLinus Torvalds *mctime_ver = 0; 1231da177e4SLinus Torvalds 1241da177e4SLinus Torvalds D1(printk(KERN_DEBUG "jffs2_get_inode_nodes(): ino #%u\n", f->inocache->ino)); 1251da177e4SLinus Torvalds 1261da177e4SLinus Torvalds spin_lock(&c->erase_completion_lock); 1271da177e4SLinus Torvalds 1281da177e4SLinus Torvalds valid_ref = jffs2_first_valid_node(f->inocache->nodes); 1291da177e4SLinus Torvalds 1301da177e4SLinus Torvalds if (!valid_ref) 1311da177e4SLinus Torvalds printk(KERN_WARNING "Eep. No valid nodes for ino #%u\n", f->inocache->ino); 1321da177e4SLinus Torvalds 1331da177e4SLinus Torvalds while (valid_ref) { 1341da177e4SLinus Torvalds /* We can hold a pointer to a non-obsolete node without the spinlock, 1351da177e4SLinus Torvalds but _obsolete_ nodes may disappear at any time, if the block 1361da177e4SLinus Torvalds they're in gets erased. So if we mark 'ref' obsolete while we're 1371da177e4SLinus Torvalds not holding the lock, it can go away immediately. For that reason, 1381da177e4SLinus Torvalds we find the next valid node first, before processing 'ref'. 1391da177e4SLinus Torvalds */ 1401da177e4SLinus Torvalds ref = valid_ref; 1411da177e4SLinus Torvalds valid_ref = jffs2_first_valid_node(ref->next_in_ino); 1421da177e4SLinus Torvalds spin_unlock(&c->erase_completion_lock); 1431da177e4SLinus Torvalds 1441da177e4SLinus Torvalds cond_resched(); 1451da177e4SLinus Torvalds 1461da177e4SLinus Torvalds /* FIXME: point() */ 1471da177e4SLinus Torvalds err = jffs2_flash_read(c, (ref_offset(ref)), 1481da177e4SLinus Torvalds min_t(uint32_t, ref_totlen(c, NULL, ref), sizeof(node)), 1491da177e4SLinus Torvalds &retlen, (void *)&node); 1501da177e4SLinus Torvalds if (err) { 1511da177e4SLinus Torvalds printk(KERN_WARNING "error %d reading node at 0x%08x in get_inode_nodes()\n", err, ref_offset(ref)); 1521da177e4SLinus Torvalds goto free_out; 1531da177e4SLinus Torvalds } 1541da177e4SLinus Torvalds 1551da177e4SLinus Torvalds 1561da177e4SLinus Torvalds /* Check we've managed to read at least the common node header */ 1571da177e4SLinus Torvalds if (retlen < min_t(uint32_t, ref_totlen(c, NULL, ref), sizeof(node.u))) { 1581da177e4SLinus Torvalds printk(KERN_WARNING "short read in get_inode_nodes()\n"); 1591da177e4SLinus Torvalds err = -EIO; 1601da177e4SLinus Torvalds goto free_out; 1611da177e4SLinus Torvalds } 1621da177e4SLinus Torvalds 1631da177e4SLinus Torvalds switch (je16_to_cpu(node.u.nodetype)) { 1641da177e4SLinus Torvalds case JFFS2_NODETYPE_DIRENT: 1651da177e4SLinus Torvalds D1(printk(KERN_DEBUG "Node at %08x (%d) is a dirent node\n", ref_offset(ref), ref_flags(ref))); 1661da177e4SLinus Torvalds if (ref_flags(ref) == REF_UNCHECKED) { 1671da177e4SLinus Torvalds printk(KERN_WARNING "BUG: Dirent node at 0x%08x never got checked? How?\n", ref_offset(ref)); 1681da177e4SLinus Torvalds BUG(); 1691da177e4SLinus Torvalds } 1701da177e4SLinus Torvalds if (retlen < sizeof(node.d)) { 1711da177e4SLinus Torvalds printk(KERN_WARNING "short read in get_inode_nodes()\n"); 1721da177e4SLinus Torvalds err = -EIO; 1731da177e4SLinus Torvalds goto free_out; 1741da177e4SLinus Torvalds } 1751da177e4SLinus Torvalds /* sanity check */ 1761da177e4SLinus Torvalds if (PAD((node.d.nsize + sizeof (node.d))) != PAD(je32_to_cpu (node.d.totlen))) { 1771da177e4SLinus Torvalds printk(KERN_NOTICE "jffs2_get_inode_nodes(): Illegal nsize in node at 0x%08x: nsize 0x%02x, totlen %04x\n", 1781da177e4SLinus Torvalds ref_offset(ref), node.d.nsize, je32_to_cpu(node.d.totlen)); 1791da177e4SLinus Torvalds jffs2_mark_node_obsolete(c, ref); 1801da177e4SLinus Torvalds spin_lock(&c->erase_completion_lock); 1811da177e4SLinus Torvalds continue; 1821da177e4SLinus Torvalds } 1831da177e4SLinus Torvalds if (je32_to_cpu(node.d.version) > *highest_version) 1841da177e4SLinus Torvalds *highest_version = je32_to_cpu(node.d.version); 1851da177e4SLinus Torvalds if (ref_obsolete(ref)) { 1861da177e4SLinus Torvalds /* Obsoleted. This cannot happen, surely? dwmw2 20020308 */ 1871da177e4SLinus Torvalds printk(KERN_ERR "Dirent node at 0x%08x became obsolete while we weren't looking\n", 1881da177e4SLinus Torvalds ref_offset(ref)); 1891da177e4SLinus Torvalds BUG(); 1901da177e4SLinus Torvalds } 1911da177e4SLinus Torvalds 1921da177e4SLinus Torvalds fd = jffs2_alloc_full_dirent(node.d.nsize+1); 1931da177e4SLinus Torvalds if (!fd) { 1941da177e4SLinus Torvalds err = -ENOMEM; 1951da177e4SLinus Torvalds goto free_out; 1961da177e4SLinus Torvalds } 1971da177e4SLinus Torvalds fd->raw = ref; 1981da177e4SLinus Torvalds fd->version = je32_to_cpu(node.d.version); 1991da177e4SLinus Torvalds fd->ino = je32_to_cpu(node.d.ino); 2001da177e4SLinus Torvalds fd->type = node.d.type; 2011da177e4SLinus Torvalds 2021da177e4SLinus Torvalds /* Pick out the mctime of the latest dirent */ 2031da177e4SLinus Torvalds if(fd->version > *mctime_ver) { 2041da177e4SLinus Torvalds *mctime_ver = fd->version; 2051da177e4SLinus Torvalds *latest_mctime = je32_to_cpu(node.d.mctime); 2061da177e4SLinus Torvalds } 2071da177e4SLinus Torvalds 2081da177e4SLinus Torvalds /* memcpy as much of the name as possible from the raw 2091da177e4SLinus Torvalds dirent we've already read from the flash 2101da177e4SLinus Torvalds */ 2111da177e4SLinus Torvalds if (retlen > sizeof(struct jffs2_raw_dirent)) 2121da177e4SLinus Torvalds memcpy(&fd->name[0], &node.d.name[0], min_t(uint32_t, node.d.nsize, (retlen-sizeof(struct jffs2_raw_dirent)))); 2131da177e4SLinus Torvalds 2141da177e4SLinus Torvalds /* Do we need to copy any more of the name directly 2151da177e4SLinus Torvalds from the flash? 2161da177e4SLinus Torvalds */ 2171da177e4SLinus Torvalds if (node.d.nsize + sizeof(struct jffs2_raw_dirent) > retlen) { 2181da177e4SLinus Torvalds /* FIXME: point() */ 2191da177e4SLinus Torvalds int already = retlen - sizeof(struct jffs2_raw_dirent); 2201da177e4SLinus Torvalds 2211da177e4SLinus Torvalds err = jffs2_flash_read(c, (ref_offset(ref)) + retlen, 2221da177e4SLinus Torvalds node.d.nsize - already, &retlen, &fd->name[already]); 2231da177e4SLinus Torvalds if (!err && retlen != node.d.nsize - already) 2241da177e4SLinus Torvalds err = -EIO; 2251da177e4SLinus Torvalds 2261da177e4SLinus Torvalds if (err) { 2271da177e4SLinus Torvalds printk(KERN_WARNING "Read remainder of name in jffs2_get_inode_nodes(): error %d\n", err); 2281da177e4SLinus Torvalds jffs2_free_full_dirent(fd); 2291da177e4SLinus Torvalds goto free_out; 2301da177e4SLinus Torvalds } 2311da177e4SLinus Torvalds } 2321da177e4SLinus Torvalds fd->nhash = full_name_hash(fd->name, node.d.nsize); 2331da177e4SLinus Torvalds fd->next = NULL; 2341da177e4SLinus Torvalds fd->name[node.d.nsize] = '\0'; 2351da177e4SLinus Torvalds /* Wheee. We now have a complete jffs2_full_dirent structure, with 2361da177e4SLinus Torvalds the name in it and everything. Link it into the list 2371da177e4SLinus Torvalds */ 2381da177e4SLinus Torvalds D1(printk(KERN_DEBUG "Adding fd \"%s\", ino #%u\n", fd->name, fd->ino)); 2391da177e4SLinus Torvalds jffs2_add_fd_to_list(c, fd, &ret_fd); 2401da177e4SLinus Torvalds break; 2411da177e4SLinus Torvalds 2421da177e4SLinus Torvalds case JFFS2_NODETYPE_INODE: 2431da177e4SLinus Torvalds D1(printk(KERN_DEBUG "Node at %08x (%d) is a data node\n", ref_offset(ref), ref_flags(ref))); 2441da177e4SLinus Torvalds if (retlen < sizeof(node.i)) { 2451da177e4SLinus Torvalds printk(KERN_WARNING "read too short for dnode\n"); 2461da177e4SLinus Torvalds err = -EIO; 2471da177e4SLinus Torvalds goto free_out; 2481da177e4SLinus Torvalds } 2491da177e4SLinus Torvalds if (je32_to_cpu(node.i.version) > *highest_version) 2501da177e4SLinus Torvalds *highest_version = je32_to_cpu(node.i.version); 2511da177e4SLinus Torvalds D1(printk(KERN_DEBUG "version %d, highest_version now %d\n", je32_to_cpu(node.i.version), *highest_version)); 2521da177e4SLinus Torvalds 2531da177e4SLinus Torvalds if (ref_obsolete(ref)) { 2541da177e4SLinus Torvalds /* Obsoleted. This cannot happen, surely? dwmw2 20020308 */ 2551da177e4SLinus Torvalds printk(KERN_ERR "Inode node at 0x%08x became obsolete while we weren't looking\n", 2561da177e4SLinus Torvalds ref_offset(ref)); 2571da177e4SLinus Torvalds BUG(); 2581da177e4SLinus Torvalds } 2591da177e4SLinus Torvalds 2601da177e4SLinus Torvalds /* If we've never checked the CRCs on this node, check them now. */ 2611da177e4SLinus Torvalds if (ref_flags(ref) == REF_UNCHECKED) { 2621da177e4SLinus Torvalds uint32_t crc, len; 2631da177e4SLinus Torvalds struct jffs2_eraseblock *jeb; 2641da177e4SLinus Torvalds 2651da177e4SLinus Torvalds crc = crc32(0, &node, sizeof(node.i)-8); 2661da177e4SLinus Torvalds if (crc != je32_to_cpu(node.i.node_crc)) { 2671da177e4SLinus Torvalds printk(KERN_NOTICE "jffs2_get_inode_nodes(): CRC failed on node at 0x%08x: Read 0x%08x, calculated 0x%08x\n", 2681da177e4SLinus Torvalds ref_offset(ref), je32_to_cpu(node.i.node_crc), crc); 2691da177e4SLinus Torvalds jffs2_mark_node_obsolete(c, ref); 2701da177e4SLinus Torvalds spin_lock(&c->erase_completion_lock); 2711da177e4SLinus Torvalds continue; 2721da177e4SLinus Torvalds } 2731da177e4SLinus Torvalds 2741da177e4SLinus Torvalds /* sanity checks */ 2751da177e4SLinus Torvalds if ( je32_to_cpu(node.i.offset) > je32_to_cpu(node.i.isize) || 2761da177e4SLinus Torvalds PAD(je32_to_cpu(node.i.csize) + sizeof (node.i)) != PAD(je32_to_cpu(node.i.totlen))) { 2771da177e4SLinus Torvalds printk(KERN_NOTICE "jffs2_get_inode_nodes(): Inode corrupted at 0x%08x, totlen %d, #ino %d, version %d, isize %d, csize %d, dsize %d \n", 2781da177e4SLinus Torvalds ref_offset(ref), je32_to_cpu(node.i.totlen), je32_to_cpu(node.i.ino), 2791da177e4SLinus Torvalds je32_to_cpu(node.i.version), je32_to_cpu(node.i.isize), 2801da177e4SLinus Torvalds je32_to_cpu(node.i.csize), je32_to_cpu(node.i.dsize)); 2811da177e4SLinus Torvalds jffs2_mark_node_obsolete(c, ref); 2821da177e4SLinus Torvalds spin_lock(&c->erase_completion_lock); 2831da177e4SLinus Torvalds continue; 2841da177e4SLinus Torvalds } 2851da177e4SLinus Torvalds 2861da177e4SLinus Torvalds if (node.i.compr != JFFS2_COMPR_ZERO && je32_to_cpu(node.i.csize)) { 2871da177e4SLinus Torvalds unsigned char *buf=NULL; 2881da177e4SLinus Torvalds uint32_t pointed = 0; 2891da177e4SLinus Torvalds #ifndef __ECOS 2901da177e4SLinus Torvalds if (c->mtd->point) { 2911da177e4SLinus Torvalds err = c->mtd->point (c->mtd, ref_offset(ref) + sizeof(node.i), je32_to_cpu(node.i.csize), 2921da177e4SLinus Torvalds &retlen, &buf); 2931da177e4SLinus Torvalds if (!err && retlen < je32_to_cpu(node.i.csize)) { 2941da177e4SLinus Torvalds D1(printk(KERN_DEBUG "MTD point returned len too short: 0x%zx\n", retlen)); 2951da177e4SLinus Torvalds c->mtd->unpoint(c->mtd, buf, ref_offset(ref) + sizeof(node.i), je32_to_cpu(node.i.csize)); 2961da177e4SLinus Torvalds } else if (err){ 2971da177e4SLinus Torvalds D1(printk(KERN_DEBUG "MTD point failed %d\n", err)); 2981da177e4SLinus Torvalds } else 2991da177e4SLinus Torvalds pointed = 1; /* succefully pointed to device */ 3001da177e4SLinus Torvalds } 3011da177e4SLinus Torvalds #endif 3021da177e4SLinus Torvalds if(!pointed){ 3031da177e4SLinus Torvalds buf = kmalloc(je32_to_cpu(node.i.csize), GFP_KERNEL); 3041da177e4SLinus Torvalds if (!buf) 3051da177e4SLinus Torvalds return -ENOMEM; 3061da177e4SLinus Torvalds 3071da177e4SLinus Torvalds err = jffs2_flash_read(c, ref_offset(ref) + sizeof(node.i), je32_to_cpu(node.i.csize), 3081da177e4SLinus Torvalds &retlen, buf); 3091da177e4SLinus Torvalds if (!err && retlen != je32_to_cpu(node.i.csize)) 3101da177e4SLinus Torvalds err = -EIO; 3111da177e4SLinus Torvalds if (err) { 3121da177e4SLinus Torvalds kfree(buf); 3131da177e4SLinus Torvalds return err; 3141da177e4SLinus Torvalds } 3151da177e4SLinus Torvalds } 3161da177e4SLinus Torvalds crc = crc32(0, buf, je32_to_cpu(node.i.csize)); 3171da177e4SLinus Torvalds if(!pointed) 3181da177e4SLinus Torvalds kfree(buf); 3191da177e4SLinus Torvalds #ifndef __ECOS 3201da177e4SLinus Torvalds else 3211da177e4SLinus Torvalds c->mtd->unpoint(c->mtd, buf, ref_offset(ref) + sizeof(node.i), je32_to_cpu(node.i.csize)); 3221da177e4SLinus Torvalds #endif 3231da177e4SLinus Torvalds 3241da177e4SLinus Torvalds if (crc != je32_to_cpu(node.i.data_crc)) { 3251da177e4SLinus Torvalds printk(KERN_NOTICE "jffs2_get_inode_nodes(): Data CRC failed on node at 0x%08x: Read 0x%08x, calculated 0x%08x\n", 3261da177e4SLinus Torvalds ref_offset(ref), je32_to_cpu(node.i.data_crc), crc); 3271da177e4SLinus Torvalds jffs2_mark_node_obsolete(c, ref); 3281da177e4SLinus Torvalds spin_lock(&c->erase_completion_lock); 3291da177e4SLinus Torvalds continue; 3301da177e4SLinus Torvalds } 3311da177e4SLinus Torvalds 3321da177e4SLinus Torvalds } 3331da177e4SLinus Torvalds 3341da177e4SLinus Torvalds /* Mark the node as having been checked and fix the accounting accordingly */ 3351da177e4SLinus Torvalds spin_lock(&c->erase_completion_lock); 3361da177e4SLinus Torvalds jeb = &c->blocks[ref->flash_offset / c->sector_size]; 3371da177e4SLinus Torvalds len = ref_totlen(c, jeb, ref); 3381da177e4SLinus Torvalds 3391da177e4SLinus Torvalds jeb->used_size += len; 3401da177e4SLinus Torvalds jeb->unchecked_size -= len; 3411da177e4SLinus Torvalds c->used_size += len; 3421da177e4SLinus Torvalds c->unchecked_size -= len; 3431da177e4SLinus Torvalds 3441da177e4SLinus Torvalds /* If node covers at least a whole page, or if it starts at the 3451da177e4SLinus Torvalds beginning of a page and runs to the end of the file, or if 3461da177e4SLinus Torvalds it's a hole node, mark it REF_PRISTINE, else REF_NORMAL. 3471da177e4SLinus Torvalds 3481da177e4SLinus Torvalds If it's actually overlapped, it'll get made NORMAL (or OBSOLETE) 3491da177e4SLinus Torvalds when the overlapping node(s) get added to the tree anyway. 3501da177e4SLinus Torvalds */ 3511da177e4SLinus Torvalds if ((je32_to_cpu(node.i.dsize) >= PAGE_CACHE_SIZE) || 3521da177e4SLinus Torvalds ( ((je32_to_cpu(node.i.offset)&(PAGE_CACHE_SIZE-1))==0) && 3531da177e4SLinus Torvalds (je32_to_cpu(node.i.dsize)+je32_to_cpu(node.i.offset) == je32_to_cpu(node.i.isize)))) { 3541da177e4SLinus Torvalds D1(printk(KERN_DEBUG "Marking node at 0x%08x REF_PRISTINE\n", ref_offset(ref))); 3551da177e4SLinus Torvalds ref->flash_offset = ref_offset(ref) | REF_PRISTINE; 3561da177e4SLinus Torvalds } else { 3571da177e4SLinus Torvalds D1(printk(KERN_DEBUG "Marking node at 0x%08x REF_NORMAL\n", ref_offset(ref))); 3581da177e4SLinus Torvalds ref->flash_offset = ref_offset(ref) | REF_NORMAL; 3591da177e4SLinus Torvalds } 3601da177e4SLinus Torvalds spin_unlock(&c->erase_completion_lock); 3611da177e4SLinus Torvalds } 3621da177e4SLinus Torvalds 3631da177e4SLinus Torvalds tn = jffs2_alloc_tmp_dnode_info(); 3641da177e4SLinus Torvalds if (!tn) { 3651da177e4SLinus Torvalds D1(printk(KERN_DEBUG "alloc tn failed\n")); 3661da177e4SLinus Torvalds err = -ENOMEM; 3671da177e4SLinus Torvalds goto free_out; 3681da177e4SLinus Torvalds } 3691da177e4SLinus Torvalds 3701da177e4SLinus Torvalds tn->fn = jffs2_alloc_full_dnode(); 3711da177e4SLinus Torvalds if (!tn->fn) { 3721da177e4SLinus Torvalds D1(printk(KERN_DEBUG "alloc fn failed\n")); 3731da177e4SLinus Torvalds err = -ENOMEM; 3741da177e4SLinus Torvalds jffs2_free_tmp_dnode_info(tn); 3751da177e4SLinus Torvalds goto free_out; 3761da177e4SLinus Torvalds } 3771da177e4SLinus Torvalds tn->version = je32_to_cpu(node.i.version); 3781da177e4SLinus Torvalds tn->fn->ofs = je32_to_cpu(node.i.offset); 3791da177e4SLinus Torvalds /* There was a bug where we wrote hole nodes out with 3801da177e4SLinus Torvalds csize/dsize swapped. Deal with it */ 3811da177e4SLinus Torvalds if (node.i.compr == JFFS2_COMPR_ZERO && !je32_to_cpu(node.i.dsize) && je32_to_cpu(node.i.csize)) 3821da177e4SLinus Torvalds tn->fn->size = je32_to_cpu(node.i.csize); 3831da177e4SLinus Torvalds else // normal case... 3841da177e4SLinus Torvalds tn->fn->size = je32_to_cpu(node.i.dsize); 3851da177e4SLinus Torvalds tn->fn->raw = ref; 3861da177e4SLinus Torvalds D1(printk(KERN_DEBUG "dnode @%08x: ver %u, offset %04x, dsize %04x\n", 3871da177e4SLinus Torvalds ref_offset(ref), je32_to_cpu(node.i.version), 3881da177e4SLinus Torvalds je32_to_cpu(node.i.offset), je32_to_cpu(node.i.dsize))); 3891da177e4SLinus Torvalds jffs2_add_tn_to_list(tn, &ret_tn); 3901da177e4SLinus Torvalds break; 3911da177e4SLinus Torvalds 3921da177e4SLinus Torvalds default: 3931da177e4SLinus Torvalds if (ref_flags(ref) == REF_UNCHECKED) { 3941da177e4SLinus Torvalds struct jffs2_eraseblock *jeb; 3951da177e4SLinus Torvalds uint32_t len; 3961da177e4SLinus Torvalds 3971da177e4SLinus Torvalds printk(KERN_ERR "Eep. Unknown node type %04x at %08x was marked REF_UNCHECKED\n", 3981da177e4SLinus Torvalds je16_to_cpu(node.u.nodetype), ref_offset(ref)); 3991da177e4SLinus Torvalds 4001da177e4SLinus Torvalds /* Mark the node as having been checked and fix the accounting accordingly */ 4011da177e4SLinus Torvalds spin_lock(&c->erase_completion_lock); 4021da177e4SLinus Torvalds jeb = &c->blocks[ref->flash_offset / c->sector_size]; 4031da177e4SLinus Torvalds len = ref_totlen(c, jeb, ref); 4041da177e4SLinus Torvalds 4051da177e4SLinus Torvalds jeb->used_size += len; 4061da177e4SLinus Torvalds jeb->unchecked_size -= len; 4071da177e4SLinus Torvalds c->used_size += len; 4081da177e4SLinus Torvalds c->unchecked_size -= len; 4091da177e4SLinus Torvalds 4101da177e4SLinus Torvalds mark_ref_normal(ref); 4111da177e4SLinus Torvalds spin_unlock(&c->erase_completion_lock); 4121da177e4SLinus Torvalds } 4131da177e4SLinus Torvalds node.u.nodetype = cpu_to_je16(JFFS2_NODE_ACCURATE | je16_to_cpu(node.u.nodetype)); 4141da177e4SLinus Torvalds if (crc32(0, &node, sizeof(struct jffs2_unknown_node)-4) != je32_to_cpu(node.u.hdr_crc)) { 4151da177e4SLinus Torvalds /* Hmmm. This should have been caught at scan time. */ 4161da177e4SLinus Torvalds printk(KERN_ERR "Node header CRC failed at %08x. But it must have been OK earlier.\n", 4171da177e4SLinus Torvalds ref_offset(ref)); 4181da177e4SLinus Torvalds printk(KERN_ERR "Node was: { %04x, %04x, %08x, %08x }\n", 4191da177e4SLinus Torvalds je16_to_cpu(node.u.magic), je16_to_cpu(node.u.nodetype), je32_to_cpu(node.u.totlen), 4201da177e4SLinus Torvalds je32_to_cpu(node.u.hdr_crc)); 4211da177e4SLinus Torvalds jffs2_mark_node_obsolete(c, ref); 4221da177e4SLinus Torvalds } else switch(je16_to_cpu(node.u.nodetype) & JFFS2_COMPAT_MASK) { 4231da177e4SLinus Torvalds case JFFS2_FEATURE_INCOMPAT: 4241da177e4SLinus Torvalds printk(KERN_NOTICE "Unknown INCOMPAT nodetype %04X at %08x\n", je16_to_cpu(node.u.nodetype), ref_offset(ref)); 4251da177e4SLinus Torvalds /* EEP */ 4261da177e4SLinus Torvalds BUG(); 4271da177e4SLinus Torvalds break; 4281da177e4SLinus Torvalds case JFFS2_FEATURE_ROCOMPAT: 4291da177e4SLinus Torvalds printk(KERN_NOTICE "Unknown ROCOMPAT nodetype %04X at %08x\n", je16_to_cpu(node.u.nodetype), ref_offset(ref)); 4301da177e4SLinus Torvalds if (!(c->flags & JFFS2_SB_FLAG_RO)) 4311da177e4SLinus Torvalds BUG(); 4321da177e4SLinus Torvalds break; 4331da177e4SLinus Torvalds case JFFS2_FEATURE_RWCOMPAT_COPY: 4341da177e4SLinus Torvalds printk(KERN_NOTICE "Unknown RWCOMPAT_COPY nodetype %04X at %08x\n", je16_to_cpu(node.u.nodetype), ref_offset(ref)); 4351da177e4SLinus Torvalds break; 4361da177e4SLinus Torvalds case JFFS2_FEATURE_RWCOMPAT_DELETE: 4371da177e4SLinus Torvalds printk(KERN_NOTICE "Unknown RWCOMPAT_DELETE nodetype %04X at %08x\n", je16_to_cpu(node.u.nodetype), ref_offset(ref)); 4381da177e4SLinus Torvalds jffs2_mark_node_obsolete(c, ref); 4391da177e4SLinus Torvalds break; 4401da177e4SLinus Torvalds } 4411da177e4SLinus Torvalds 4421da177e4SLinus Torvalds } 4431da177e4SLinus Torvalds spin_lock(&c->erase_completion_lock); 4441da177e4SLinus Torvalds 4451da177e4SLinus Torvalds } 4461da177e4SLinus Torvalds spin_unlock(&c->erase_completion_lock); 4471da177e4SLinus Torvalds *tnp = ret_tn; 4481da177e4SLinus Torvalds *fdp = ret_fd; 4491da177e4SLinus Torvalds 4501da177e4SLinus Torvalds return 0; 4511da177e4SLinus Torvalds 4521da177e4SLinus Torvalds free_out: 4531da177e4SLinus Torvalds jffs2_free_tmp_dnode_info_list(ret_tn); 4541da177e4SLinus Torvalds jffs2_free_full_dirent_list(ret_fd); 4551da177e4SLinus Torvalds return err; 4561da177e4SLinus Torvalds } 4571da177e4SLinus Torvalds 4581da177e4SLinus Torvalds void jffs2_set_inocache_state(struct jffs2_sb_info *c, struct jffs2_inode_cache *ic, int state) 4591da177e4SLinus Torvalds { 4601da177e4SLinus Torvalds spin_lock(&c->inocache_lock); 4611da177e4SLinus Torvalds ic->state = state; 4621da177e4SLinus Torvalds wake_up(&c->inocache_wq); 4631da177e4SLinus Torvalds spin_unlock(&c->inocache_lock); 4641da177e4SLinus Torvalds } 4651da177e4SLinus Torvalds 4661da177e4SLinus Torvalds /* During mount, this needs no locking. During normal operation, its 4671da177e4SLinus Torvalds callers want to do other stuff while still holding the inocache_lock. 4681da177e4SLinus Torvalds Rather than introducing special case get_ino_cache functions or 4691da177e4SLinus Torvalds callbacks, we just let the caller do the locking itself. */ 4701da177e4SLinus Torvalds 4711da177e4SLinus Torvalds struct jffs2_inode_cache *jffs2_get_ino_cache(struct jffs2_sb_info *c, uint32_t ino) 4721da177e4SLinus Torvalds { 4731da177e4SLinus Torvalds struct jffs2_inode_cache *ret; 4741da177e4SLinus Torvalds 4751da177e4SLinus Torvalds D2(printk(KERN_DEBUG "jffs2_get_ino_cache(): ino %u\n", ino)); 4761da177e4SLinus Torvalds 4771da177e4SLinus Torvalds ret = c->inocache_list[ino % INOCACHE_HASHSIZE]; 4781da177e4SLinus Torvalds while (ret && ret->ino < ino) { 4791da177e4SLinus Torvalds ret = ret->next; 4801da177e4SLinus Torvalds } 4811da177e4SLinus Torvalds 4821da177e4SLinus Torvalds if (ret && ret->ino != ino) 4831da177e4SLinus Torvalds ret = NULL; 4841da177e4SLinus Torvalds 4851da177e4SLinus Torvalds D2(printk(KERN_DEBUG "jffs2_get_ino_cache found %p for ino %u\n", ret, ino)); 4861da177e4SLinus Torvalds return ret; 4871da177e4SLinus Torvalds } 4881da177e4SLinus Torvalds 4891da177e4SLinus Torvalds void jffs2_add_ino_cache (struct jffs2_sb_info *c, struct jffs2_inode_cache *new) 4901da177e4SLinus Torvalds { 4911da177e4SLinus Torvalds struct jffs2_inode_cache **prev; 4921da177e4SLinus Torvalds D2(printk(KERN_DEBUG "jffs2_add_ino_cache: Add %p (ino #%u)\n", new, new->ino)); 4931da177e4SLinus Torvalds spin_lock(&c->inocache_lock); 4941da177e4SLinus Torvalds 4951da177e4SLinus Torvalds prev = &c->inocache_list[new->ino % INOCACHE_HASHSIZE]; 4961da177e4SLinus Torvalds 4971da177e4SLinus Torvalds while ((*prev) && (*prev)->ino < new->ino) { 4981da177e4SLinus Torvalds prev = &(*prev)->next; 4991da177e4SLinus Torvalds } 5001da177e4SLinus Torvalds new->next = *prev; 5011da177e4SLinus Torvalds *prev = new; 5021da177e4SLinus Torvalds 5031da177e4SLinus Torvalds spin_unlock(&c->inocache_lock); 5041da177e4SLinus Torvalds } 5051da177e4SLinus Torvalds 5061da177e4SLinus Torvalds void jffs2_del_ino_cache(struct jffs2_sb_info *c, struct jffs2_inode_cache *old) 5071da177e4SLinus Torvalds { 5081da177e4SLinus Torvalds struct jffs2_inode_cache **prev; 5091da177e4SLinus Torvalds D2(printk(KERN_DEBUG "jffs2_del_ino_cache: Del %p (ino #%u)\n", old, old->ino)); 5101da177e4SLinus Torvalds spin_lock(&c->inocache_lock); 5111da177e4SLinus Torvalds 5121da177e4SLinus Torvalds prev = &c->inocache_list[old->ino % INOCACHE_HASHSIZE]; 5131da177e4SLinus Torvalds 5141da177e4SLinus Torvalds while ((*prev) && (*prev)->ino < old->ino) { 5151da177e4SLinus Torvalds prev = &(*prev)->next; 5161da177e4SLinus Torvalds } 5171da177e4SLinus Torvalds if ((*prev) == old) { 5181da177e4SLinus Torvalds *prev = old->next; 5191da177e4SLinus Torvalds } 5201da177e4SLinus Torvalds 5211da177e4SLinus Torvalds spin_unlock(&c->inocache_lock); 5221da177e4SLinus Torvalds } 5231da177e4SLinus Torvalds 5241da177e4SLinus Torvalds void jffs2_free_ino_caches(struct jffs2_sb_info *c) 5251da177e4SLinus Torvalds { 5261da177e4SLinus Torvalds int i; 5271da177e4SLinus Torvalds struct jffs2_inode_cache *this, *next; 5281da177e4SLinus Torvalds 5291da177e4SLinus Torvalds for (i=0; i<INOCACHE_HASHSIZE; i++) { 5301da177e4SLinus Torvalds this = c->inocache_list[i]; 5311da177e4SLinus Torvalds while (this) { 5321da177e4SLinus Torvalds next = this->next; 5331da177e4SLinus Torvalds D2(printk(KERN_DEBUG "jffs2_free_ino_caches: Freeing ino #%u at %p\n", this->ino, this)); 5341da177e4SLinus Torvalds jffs2_free_inode_cache(this); 5351da177e4SLinus Torvalds this = next; 5361da177e4SLinus Torvalds } 5371da177e4SLinus Torvalds c->inocache_list[i] = NULL; 5381da177e4SLinus Torvalds } 5391da177e4SLinus Torvalds } 5401da177e4SLinus Torvalds 5411da177e4SLinus Torvalds void jffs2_free_raw_node_refs(struct jffs2_sb_info *c) 5421da177e4SLinus Torvalds { 5431da177e4SLinus Torvalds int i; 5441da177e4SLinus Torvalds struct jffs2_raw_node_ref *this, *next; 5451da177e4SLinus Torvalds 5461da177e4SLinus Torvalds for (i=0; i<c->nr_blocks; i++) { 5471da177e4SLinus Torvalds this = c->blocks[i].first_node; 5481da177e4SLinus Torvalds while(this) { 5491da177e4SLinus Torvalds next = this->next_phys; 5501da177e4SLinus Torvalds jffs2_free_raw_node_ref(this); 5511da177e4SLinus Torvalds this = next; 5521da177e4SLinus Torvalds } 5531da177e4SLinus Torvalds c->blocks[i].first_node = c->blocks[i].last_node = NULL; 5541da177e4SLinus Torvalds } 5551da177e4SLinus Torvalds } 5561da177e4SLinus Torvalds 5571da177e4SLinus Torvalds struct jffs2_node_frag *jffs2_lookup_node_frag(struct rb_root *fragtree, uint32_t offset) 5581da177e4SLinus Torvalds { 5591da177e4SLinus Torvalds /* The common case in lookup is that there will be a node 5601da177e4SLinus Torvalds which precisely matches. So we go looking for that first */ 5611da177e4SLinus Torvalds struct rb_node *next; 5621da177e4SLinus Torvalds struct jffs2_node_frag *prev = NULL; 5631da177e4SLinus Torvalds struct jffs2_node_frag *frag = NULL; 5641da177e4SLinus Torvalds 5651da177e4SLinus Torvalds D2(printk(KERN_DEBUG "jffs2_lookup_node_frag(%p, %d)\n", fragtree, offset)); 5661da177e4SLinus Torvalds 5671da177e4SLinus Torvalds next = fragtree->rb_node; 5681da177e4SLinus Torvalds 5691da177e4SLinus Torvalds while(next) { 5701da177e4SLinus Torvalds frag = rb_entry(next, struct jffs2_node_frag, rb); 5711da177e4SLinus Torvalds 5721da177e4SLinus Torvalds D2(printk(KERN_DEBUG "Considering frag %d-%d (%p). left %p, right %p\n", 5731da177e4SLinus Torvalds frag->ofs, frag->ofs+frag->size, frag, frag->rb.rb_left, frag->rb.rb_right)); 5741da177e4SLinus Torvalds if (frag->ofs + frag->size <= offset) { 5751da177e4SLinus Torvalds D2(printk(KERN_DEBUG "Going right from frag %d-%d, before the region we care about\n", 5761da177e4SLinus Torvalds frag->ofs, frag->ofs+frag->size)); 5771da177e4SLinus Torvalds /* Remember the closest smaller match on the way down */ 5781da177e4SLinus Torvalds if (!prev || frag->ofs > prev->ofs) 5791da177e4SLinus Torvalds prev = frag; 5801da177e4SLinus Torvalds next = frag->rb.rb_right; 5811da177e4SLinus Torvalds } else if (frag->ofs > offset) { 5821da177e4SLinus Torvalds D2(printk(KERN_DEBUG "Going left from frag %d-%d, after the region we care about\n", 5831da177e4SLinus Torvalds frag->ofs, frag->ofs+frag->size)); 5841da177e4SLinus Torvalds next = frag->rb.rb_left; 5851da177e4SLinus Torvalds } else { 5861da177e4SLinus Torvalds D2(printk(KERN_DEBUG "Returning frag %d,%d, matched\n", 5871da177e4SLinus Torvalds frag->ofs, frag->ofs+frag->size)); 5881da177e4SLinus Torvalds return frag; 5891da177e4SLinus Torvalds } 5901da177e4SLinus Torvalds } 5911da177e4SLinus Torvalds 5921da177e4SLinus Torvalds /* Exact match not found. Go back up looking at each parent, 5931da177e4SLinus Torvalds and return the closest smaller one */ 5941da177e4SLinus Torvalds 5951da177e4SLinus Torvalds if (prev) 5961da177e4SLinus Torvalds D2(printk(KERN_DEBUG "No match. Returning frag %d,%d, closest previous\n", 5971da177e4SLinus Torvalds prev->ofs, prev->ofs+prev->size)); 5981da177e4SLinus Torvalds else 5991da177e4SLinus Torvalds D2(printk(KERN_DEBUG "Returning NULL, empty fragtree\n")); 6001da177e4SLinus Torvalds 6011da177e4SLinus Torvalds return prev; 6021da177e4SLinus Torvalds } 6031da177e4SLinus Torvalds 6041da177e4SLinus Torvalds /* Pass 'c' argument to indicate that nodes should be marked obsolete as 6051da177e4SLinus Torvalds they're killed. */ 6061da177e4SLinus Torvalds void jffs2_kill_fragtree(struct rb_root *root, struct jffs2_sb_info *c) 6071da177e4SLinus Torvalds { 6081da177e4SLinus Torvalds struct jffs2_node_frag *frag; 6091da177e4SLinus Torvalds struct jffs2_node_frag *parent; 6101da177e4SLinus Torvalds 6111da177e4SLinus Torvalds if (!root->rb_node) 6121da177e4SLinus Torvalds return; 6131da177e4SLinus Torvalds 6141da177e4SLinus Torvalds frag = (rb_entry(root->rb_node, struct jffs2_node_frag, rb)); 6151da177e4SLinus Torvalds 6161da177e4SLinus Torvalds while(frag) { 6171da177e4SLinus Torvalds if (frag->rb.rb_left) { 6181da177e4SLinus Torvalds D2(printk(KERN_DEBUG "Going left from frag (%p) %d-%d\n", 6191da177e4SLinus Torvalds frag, frag->ofs, frag->ofs+frag->size)); 6201da177e4SLinus Torvalds frag = frag_left(frag); 6211da177e4SLinus Torvalds continue; 6221da177e4SLinus Torvalds } 6231da177e4SLinus Torvalds if (frag->rb.rb_right) { 6241da177e4SLinus Torvalds D2(printk(KERN_DEBUG "Going right from frag (%p) %d-%d\n", 6251da177e4SLinus Torvalds frag, frag->ofs, frag->ofs+frag->size)); 6261da177e4SLinus Torvalds frag = frag_right(frag); 6271da177e4SLinus Torvalds continue; 6281da177e4SLinus Torvalds } 6291da177e4SLinus Torvalds 6301da177e4SLinus Torvalds D2(printk(KERN_DEBUG "jffs2_kill_fragtree: frag at 0x%x-0x%x: node %p, frags %d--\n", 6311da177e4SLinus Torvalds frag->ofs, frag->ofs+frag->size, frag->node, 6321da177e4SLinus Torvalds frag->node?frag->node->frags:0)); 6331da177e4SLinus Torvalds 6341da177e4SLinus Torvalds if (frag->node && !(--frag->node->frags)) { 6351da177e4SLinus Torvalds /* Not a hole, and it's the final remaining frag 6361da177e4SLinus Torvalds of this node. Free the node */ 6371da177e4SLinus Torvalds if (c) 6381da177e4SLinus Torvalds jffs2_mark_node_obsolete(c, frag->node->raw); 6391da177e4SLinus Torvalds 6401da177e4SLinus Torvalds jffs2_free_full_dnode(frag->node); 6411da177e4SLinus Torvalds } 6421da177e4SLinus Torvalds parent = frag_parent(frag); 6431da177e4SLinus Torvalds if (parent) { 6441da177e4SLinus Torvalds if (frag_left(parent) == frag) 6451da177e4SLinus Torvalds parent->rb.rb_left = NULL; 6461da177e4SLinus Torvalds else 6471da177e4SLinus Torvalds parent->rb.rb_right = NULL; 6481da177e4SLinus Torvalds } 6491da177e4SLinus Torvalds 6501da177e4SLinus Torvalds jffs2_free_node_frag(frag); 6511da177e4SLinus Torvalds frag = parent; 6521da177e4SLinus Torvalds 6531da177e4SLinus Torvalds cond_resched(); 6541da177e4SLinus Torvalds } 6551da177e4SLinus Torvalds } 6561da177e4SLinus Torvalds 6571da177e4SLinus Torvalds void jffs2_fragtree_insert(struct jffs2_node_frag *newfrag, struct jffs2_node_frag *base) 6581da177e4SLinus Torvalds { 6591da177e4SLinus Torvalds struct rb_node *parent = &base->rb; 6601da177e4SLinus Torvalds struct rb_node **link = &parent; 6611da177e4SLinus Torvalds 6621da177e4SLinus Torvalds D2(printk(KERN_DEBUG "jffs2_fragtree_insert(%p; %d-%d, %p)\n", newfrag, 6631da177e4SLinus Torvalds newfrag->ofs, newfrag->ofs+newfrag->size, base)); 6641da177e4SLinus Torvalds 6651da177e4SLinus Torvalds while (*link) { 6661da177e4SLinus Torvalds parent = *link; 6671da177e4SLinus Torvalds base = rb_entry(parent, struct jffs2_node_frag, rb); 6681da177e4SLinus Torvalds 6691da177e4SLinus Torvalds D2(printk(KERN_DEBUG "fragtree_insert considering frag at 0x%x\n", base->ofs)); 6701da177e4SLinus Torvalds if (newfrag->ofs > base->ofs) 6711da177e4SLinus Torvalds link = &base->rb.rb_right; 6721da177e4SLinus Torvalds else if (newfrag->ofs < base->ofs) 6731da177e4SLinus Torvalds link = &base->rb.rb_left; 6741da177e4SLinus Torvalds else { 6751da177e4SLinus Torvalds printk(KERN_CRIT "Duplicate frag at %08x (%p,%p)\n", newfrag->ofs, newfrag, base); 6761da177e4SLinus Torvalds BUG(); 6771da177e4SLinus Torvalds } 6781da177e4SLinus Torvalds } 6791da177e4SLinus Torvalds 6801da177e4SLinus Torvalds rb_link_node(&newfrag->rb, &base->rb, link); 6811da177e4SLinus Torvalds } 682