2 * JFFS2 -- Journalling Flash File System, Version 2.
4 * Copyright (C) 2001-2003 Red Hat, Inc.
6 * Created by David Woodhouse <dwmw2@infradead.org>
8 * For licensing information, see the file 'LICENCE' in this directory.
10 * $Id: nodelist.c,v 1.100 2005/07/22 10:32:08 dedekind Exp $
14 #include <linux/kernel.h>
15 #include <linux/sched.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>
24 void jffs2_add_fd_to_list(struct jffs2_sb_info *c, struct jffs2_full_dirent *new, struct jffs2_full_dirent **list)
26 struct jffs2_full_dirent **prev = list;
27 D1(printk(KERN_DEBUG "jffs2_add_fd_to_list( %p, %p (->%p))\n", new, list, *list));
29 while ((*prev) && (*prev)->nhash <= new->nhash) {
30 if ((*prev)->nhash == new->nhash && !strcmp((*prev)->name, new->name)) {
31 /* Duplicate. Free one */
32 if (new->version < (*prev)->version) {
33 D1(printk(KERN_DEBUG "Eep! Marking new dirent node obsolete\n"));
34 D1(printk(KERN_DEBUG "New dirent is \"%s\"->ino #%u. Old is \"%s\"->ino #%u\n", new->name, new->ino, (*prev)->name, (*prev)->ino));
35 jffs2_mark_node_obsolete(c, new->raw);
36 jffs2_free_full_dirent(new);
38 D1(printk(KERN_DEBUG "Marking old dirent node (ino #%u) obsolete\n", (*prev)->ino));
39 new->next = (*prev)->next;
40 jffs2_mark_node_obsolete(c, ((*prev)->raw));
41 jffs2_free_full_dirent(*prev);
46 prev = &((*prev)->next);
53 printk(KERN_DEBUG "Dirent \"%s\" (hash 0x%08x, ino #%u\n", (*list)->name, (*list)->nhash, (*list)->ino);
54 list = &(*list)->next;
59 * Put a new tmp_dnode_info into the temporaty RB-tree, keeping the list in
60 * order of increasing version.
62 static void jffs2_add_tn_to_tree(struct jffs2_tmp_dnode_info *tn, struct rb_root *list)
64 struct rb_node **p = &list->rb_node;
65 struct rb_node * parent = NULL;
66 struct jffs2_tmp_dnode_info *this;
70 this = rb_entry(parent, struct jffs2_tmp_dnode_info, rb);
72 /* There may actually be a collision here, but it doesn't
73 actually matter. As long as the two nodes with the same
74 version are together, it's all fine. */
75 if (tn->version < this->version)
81 rb_link_node(&tn->rb, parent, p);
82 rb_insert_color(&tn->rb, list);
85 static void jffs2_free_tmp_dnode_info_list(struct rb_root *list)
88 struct jffs2_tmp_dnode_info *tn;
92 /* Now at bottom of tree */
96 else if (this->rb_right)
97 this = this->rb_right;
99 tn = rb_entry(this, struct jffs2_tmp_dnode_info, rb);
100 jffs2_free_full_dnode(tn->fn);
101 jffs2_free_tmp_dnode_info(tn);
103 this = this->rb_parent;
107 if (this->rb_left == &tn->rb)
108 this->rb_left = NULL;
109 else if (this->rb_right == &tn->rb)
110 this->rb_right = NULL;
114 list->rb_node = NULL;
117 static void jffs2_free_full_dirent_list(struct jffs2_full_dirent *fd)
119 struct jffs2_full_dirent *next;
123 jffs2_free_full_dirent(fd);
128 /* Returns first valid node after 'ref'. May return 'ref' */
129 static struct jffs2_raw_node_ref *jffs2_first_valid_node(struct jffs2_raw_node_ref *ref)
131 while (ref && ref->next_in_ino) {
132 if (!ref_obsolete(ref))
134 D1(printk(KERN_DEBUG "node at 0x%08x is obsoleted. Ignoring.\n", ref_offset(ref)));
135 ref = ref->next_in_ino;
141 * Helper function for jffs2_get_inode_nodes().
142 * It is called every time an directory entry node is found.
144 * Returns: 0 on succes;
145 * 1 if the node should be marked obsolete;
146 * negative error code on failure.
149 read_direntry(struct jffs2_sb_info *c,
150 struct jffs2_raw_node_ref *ref,
151 struct jffs2_raw_dirent *rd,
153 struct jffs2_full_dirent **fdp,
154 int32_t *latest_mctime,
155 uint32_t *mctime_ver)
157 struct jffs2_full_dirent *fd;
159 /* The direntry nodes are checked during the flash scanning */
160 BUG_ON(ref_flags(ref) == REF_UNCHECKED);
161 /* Obsoleted. This cannot happen, surely? dwmw2 20020308 */
162 BUG_ON(ref_obsolete(ref));
165 if (unlikely(PAD((rd->nsize + sizeof(*rd))) != PAD(je32_to_cpu(rd->totlen)))) {
166 printk(KERN_ERR "Error! Illegal nsize in node at %#08x: nsize %#02x, totlen %#04x\n",
167 ref_offset(ref), rd->nsize, je32_to_cpu(rd->totlen));
171 fd = jffs2_alloc_full_dirent(rd->nsize + 1);
176 fd->version = je32_to_cpu(rd->version);
177 fd->ino = je32_to_cpu(rd->ino);
180 /* Pick out the mctime of the latest dirent */
181 if(fd->version > *mctime_ver) {
182 *mctime_ver = fd->version;
183 *latest_mctime = je32_to_cpu(rd->mctime);
187 * Copy as much of the name as possible from the raw
188 * dirent we've already read from the flash.
190 if (read > sizeof(*rd))
191 memcpy(&fd->name[0], &rd->name[0],
192 min_t(uint32_t, rd->nsize, (read - sizeof(*rd)) ));
194 /* Do we need to copy any more of the name directly from the flash? */
195 if (rd->nsize + sizeof(*rd) > read) {
198 int already = read - sizeof(*rd);
200 err = jffs2_flash_read(c, (ref_offset(ref)) + read,
201 rd->nsize - already, &read, &fd->name[already]);
202 if (unlikely(read != rd->nsize - already) && likely(!err))
206 printk(KERN_WARNING "Read remainder of name: error %d\n", err);
207 jffs2_free_full_dirent(fd);
212 fd->nhash = full_name_hash(fd->name, rd->nsize);
214 fd->name[rd->nsize] = '\0';
217 * Wheee. We now have a complete jffs2_full_dirent structure, with
218 * the name in it and everything. Link it into the list
220 D1(printk(KERN_DEBUG "Adding fd \"%s\", ino #%u\n", fd->name, fd->ino));
222 jffs2_add_fd_to_list(c, fd, fdp);
228 * Helper function for jffs2_get_inode_nodes().
229 * It is called every time an inode node is found.
231 * Returns: 0 on succes;
232 * 1 if the node should be marked obsolete;
233 * negative error code on failure.
236 read_dnode(struct jffs2_sb_info *c,
237 struct jffs2_raw_node_ref *ref,
238 struct jffs2_raw_inode *rd,
241 int32_t *latest_mctime,
242 uint32_t *mctime_ver)
244 struct jffs2_eraseblock *jeb;
245 struct jffs2_tmp_dnode_info *tn;
247 /* Obsoleted. This cannot happen, surely? dwmw2 20020308 */
248 BUG_ON(ref_obsolete(ref));
250 /* If we've never checked the CRCs on this node, check them now */
251 if (ref_flags(ref) == REF_UNCHECKED) {
254 crc = crc32(0, rd, sizeof(*rd) - 8);
255 if (unlikely(crc != je32_to_cpu(rd->node_crc))) {
256 printk(KERN_WARNING "Header CRC failed on node at %#08x: read %#08x, calculated %#08x\n",
257 ref_offset(ref), je32_to_cpu(rd->node_crc), crc);
262 if (unlikely(je32_to_cpu(rd->offset) > je32_to_cpu(rd->isize)) ||
263 unlikely(PAD(je32_to_cpu(rd->csize) + sizeof(*rd)) != PAD(je32_to_cpu(rd->totlen)))) {
264 printk(KERN_WARNING "Inode corrupted at %#08x, totlen %d, #ino %d, version %d, "
265 "isize %d, csize %d, dsize %d \n",
266 ref_offset(ref), je32_to_cpu(rd->totlen), je32_to_cpu(rd->ino),
267 je32_to_cpu(rd->version), je32_to_cpu(rd->isize),
268 je32_to_cpu(rd->csize), je32_to_cpu(rd->dsize));
272 if (rd->compr != JFFS2_COMPR_ZERO && je32_to_cpu(rd->csize)) {
273 unsigned char *buf = NULL;
274 uint32_t pointed = 0;
278 err = c->mtd->point (c->mtd, ref_offset(ref) + sizeof(*rd), je32_to_cpu(rd->csize),
280 if (unlikely(read < je32_to_cpu(rd->csize)) && likely(!err)) {
281 D1(printk(KERN_DEBUG "MTD point returned len too short: 0x%zx\n", read));
282 c->mtd->unpoint(c->mtd, buf, ref_offset(ref) + sizeof(*rd),
283 je32_to_cpu(rd->csize));
284 } else if (unlikely(err)){
285 D1(printk(KERN_DEBUG "MTD point failed %d\n", err));
287 pointed = 1; /* succefully pointed to device */
291 buf = kmalloc(je32_to_cpu(rd->csize), GFP_KERNEL);
295 err = jffs2_flash_read(c, ref_offset(ref) + sizeof(*rd), je32_to_cpu(rd->csize),
297 if (unlikely(read != je32_to_cpu(rd->csize)) && likely(!err))
304 crc = crc32(0, buf, je32_to_cpu(rd->csize));
309 c->mtd->unpoint(c->mtd, buf, ref_offset(ref) + sizeof(*rd), je32_to_cpu(rd->csize));
312 if (crc != je32_to_cpu(rd->data_crc)) {
313 printk(KERN_NOTICE "Data CRC failed on node at %#08x: read %#08x, calculated %#08x\n",
314 ref_offset(ref), je32_to_cpu(rd->data_crc), crc);
320 /* Mark the node as having been checked and fix the accounting accordingly */
321 jeb = &c->blocks[ref->flash_offset / c->sector_size];
322 len = ref_totlen(c, jeb, ref);
324 spin_lock(&c->erase_completion_lock);
325 jeb->used_size += len;
326 jeb->unchecked_size -= len;
328 c->unchecked_size -= len;
330 /* If node covers at least a whole page, or if it starts at the
331 beginning of a page and runs to the end of the file, or if
332 it's a hole node, mark it REF_PRISTINE, else REF_NORMAL.
334 If it's actually overlapped, it'll get made NORMAL (or OBSOLETE)
335 when the overlapping node(s) get added to the tree anyway.
337 if ((je32_to_cpu(rd->dsize) >= PAGE_CACHE_SIZE) ||
338 ( ((je32_to_cpu(rd->offset) & (PAGE_CACHE_SIZE-1))==0) &&
339 (je32_to_cpu(rd->dsize) + je32_to_cpu(rd->offset) == je32_to_cpu(rd->isize)))) {
340 D1(printk(KERN_DEBUG "Marking node at %#08x REF_PRISTINE\n", ref_offset(ref)));
341 ref->flash_offset = ref_offset(ref) | REF_PRISTINE;
343 D1(printk(KERN_DEBUG "Marking node at %#08x REF_NORMAL\n", ref_offset(ref)));
344 ref->flash_offset = ref_offset(ref) | REF_NORMAL;
346 spin_unlock(&c->erase_completion_lock);
349 tn = jffs2_alloc_tmp_dnode_info();
351 D1(printk(KERN_DEBUG "alloc tn failed\n"));
355 tn->fn = jffs2_alloc_full_dnode();
357 D1(printk(KERN_DEBUG "alloc fn failed\n"));
358 jffs2_free_tmp_dnode_info(tn);
362 tn->version = je32_to_cpu(rd->version);
363 tn->fn->ofs = je32_to_cpu(rd->offset);
366 /* There was a bug where we wrote hole nodes out with
367 csize/dsize swapped. Deal with it */
368 if (rd->compr == JFFS2_COMPR_ZERO && !je32_to_cpu(rd->dsize) && je32_to_cpu(rd->csize))
369 tn->fn->size = je32_to_cpu(rd->csize);
370 else // normal case...
371 tn->fn->size = je32_to_cpu(rd->dsize);
373 D1(printk(KERN_DEBUG "dnode @%08x: ver %u, offset %#04x, dsize %#04x\n",
374 ref_offset(ref), je32_to_cpu(rd->version),
375 je32_to_cpu(rd->offset), je32_to_cpu(rd->dsize)));
377 jffs2_add_tn_to_tree(tn, tnp);
383 * Helper function for jffs2_get_inode_nodes().
384 * It is called every time an unknown node is found.
386 * Returns: 0 on succes;
387 * 1 if the node should be marked obsolete;
388 * negative error code on failure.
391 read_unknown(struct jffs2_sb_info *c,
392 struct jffs2_raw_node_ref *ref,
393 struct jffs2_unknown_node *un,
396 /* We don't mark unknown nodes as REF_UNCHECKED */
397 BUG_ON(ref_flags(ref) == REF_UNCHECKED);
399 un->nodetype = cpu_to_je16(JFFS2_NODE_ACCURATE | je16_to_cpu(un->nodetype));
401 if (crc32(0, un, sizeof(struct jffs2_unknown_node) - 4) != je32_to_cpu(un->hdr_crc)) {
403 /* Hmmm. This should have been caught at scan time. */
404 printk(KERN_WARNING "Warning! Node header CRC failed at %#08x. "
405 "But it must have been OK earlier.\n", ref_offset(ref));
406 D1(printk(KERN_DEBUG "Node was: { %#04x, %#04x, %#08x, %#08x }\n",
407 je16_to_cpu(un->magic), je16_to_cpu(un->nodetype),
408 je32_to_cpu(un->totlen), je32_to_cpu(un->hdr_crc)));
411 switch(je16_to_cpu(un->nodetype) & JFFS2_COMPAT_MASK) {
413 case JFFS2_FEATURE_INCOMPAT:
414 printk(KERN_NOTICE "Unknown INCOMPAT nodetype %#04X at %#08x\n",
415 je16_to_cpu(un->nodetype), ref_offset(ref));
420 case JFFS2_FEATURE_ROCOMPAT:
421 printk(KERN_NOTICE "Unknown ROCOMPAT nodetype %#04X at %#08x\n",
422 je16_to_cpu(un->nodetype), ref_offset(ref));
423 BUG_ON(!(c->flags & JFFS2_SB_FLAG_RO));
426 case JFFS2_FEATURE_RWCOMPAT_COPY:
427 printk(KERN_NOTICE "Unknown RWCOMPAT_COPY nodetype %#04X at %#08x\n",
428 je16_to_cpu(un->nodetype), ref_offset(ref));
431 case JFFS2_FEATURE_RWCOMPAT_DELETE:
432 printk(KERN_NOTICE "Unknown RWCOMPAT_DELETE nodetype %#04X at %#08x\n",
433 je16_to_cpu(un->nodetype), ref_offset(ref));
441 /* Get tmp_dnode_info and full_dirent for all non-obsolete nodes associated
442 with this ino, returning the former in order of version */
444 int jffs2_get_inode_nodes(struct jffs2_sb_info *c, struct jffs2_inode_info *f,
445 struct rb_root *tnp, struct jffs2_full_dirent **fdp,
446 uint32_t *highest_version, uint32_t *latest_mctime,
447 uint32_t *mctime_ver)
449 struct jffs2_raw_node_ref *ref, *valid_ref;
450 struct rb_root ret_tn = RB_ROOT;
451 struct jffs2_full_dirent *ret_fd = NULL;
452 union jffs2_node_union node;
458 D1(printk(KERN_DEBUG "jffs2_get_inode_nodes(): ino #%u\n", f->inocache->ino));
460 spin_lock(&c->erase_completion_lock);
462 valid_ref = jffs2_first_valid_node(f->inocache->nodes);
464 if (!valid_ref && (f->inocache->ino != 1))
465 printk(KERN_WARNING "Eep. No valid nodes for ino #%u\n", f->inocache->ino);
468 /* We can hold a pointer to a non-obsolete node without the spinlock,
469 but _obsolete_ nodes may disappear at any time, if the block
470 they're in gets erased. So if we mark 'ref' obsolete while we're
471 not holding the lock, it can go away immediately. For that reason,
472 we find the next valid node first, before processing 'ref'.
475 valid_ref = jffs2_first_valid_node(ref->next_in_ino);
476 spin_unlock(&c->erase_completion_lock);
481 err = jffs2_flash_read(c, (ref_offset(ref)),
482 min_t(uint32_t, ref_totlen(c, NULL, ref), sizeof(node)),
483 &retlen, (void *)&node);
485 printk(KERN_WARNING "error %d reading node at 0x%08x in get_inode_nodes()\n", err, ref_offset(ref));
489 switch (je16_to_cpu(node.u.nodetype)) {
491 case JFFS2_NODETYPE_DIRENT:
492 D1(printk(KERN_DEBUG "Node at %08x (%d) is a dirent node\n", ref_offset(ref), ref_flags(ref)));
494 if (retlen < sizeof(node.d)) {
495 printk(KERN_WARNING "Warning! Short read dirent at %#08x\n", ref_offset(ref));
500 err = read_direntry(c, ref, &node.d, retlen, &ret_fd, latest_mctime, mctime_ver);
502 jffs2_mark_node_obsolete(c, ref);
504 } else if (unlikely(err))
507 if (je32_to_cpu(node.d.version) > *highest_version)
508 *highest_version = je32_to_cpu(node.d.version);
512 case JFFS2_NODETYPE_INODE:
513 D1(printk(KERN_DEBUG "Node at %08x (%d) is a data node\n", ref_offset(ref), ref_flags(ref)));
515 if (retlen < sizeof(node.i)) {
516 printk(KERN_WARNING "Warning! Short read dnode at %#08x\n", ref_offset(ref));
521 err = read_dnode(c, ref, &node.i, retlen, &ret_tn, latest_mctime, mctime_ver);
523 jffs2_mark_node_obsolete(c, ref);
525 } else if (unlikely(err))
528 if (je32_to_cpu(node.i.version) > *highest_version)
529 *highest_version = je32_to_cpu(node.i.version);
531 D1(printk(KERN_DEBUG "version %d, highest_version now %d\n",
532 je32_to_cpu(node.i.version), *highest_version));
537 /* Check we've managed to read at least the common node header */
538 if (retlen < sizeof(struct jffs2_unknown_node)) {
539 printk(KERN_WARNING "Warning! Short read unknown node at %#08x\n",
544 err = read_unknown(c, ref, &node.u, retlen);
546 jffs2_mark_node_obsolete(c, ref);
548 } else if (unlikely(err))
552 spin_lock(&c->erase_completion_lock);
555 spin_unlock(&c->erase_completion_lock);
562 jffs2_free_tmp_dnode_info_list(&ret_tn);
563 jffs2_free_full_dirent_list(ret_fd);
567 void jffs2_set_inocache_state(struct jffs2_sb_info *c, struct jffs2_inode_cache *ic, int state)
569 spin_lock(&c->inocache_lock);
571 wake_up(&c->inocache_wq);
572 spin_unlock(&c->inocache_lock);
575 /* During mount, this needs no locking. During normal operation, its
576 callers want to do other stuff while still holding the inocache_lock.
577 Rather than introducing special case get_ino_cache functions or
578 callbacks, we just let the caller do the locking itself. */
580 struct jffs2_inode_cache *jffs2_get_ino_cache(struct jffs2_sb_info *c, uint32_t ino)
582 struct jffs2_inode_cache *ret;
584 D2(printk(KERN_DEBUG "jffs2_get_ino_cache(): ino %u\n", ino));
586 ret = c->inocache_list[ino % INOCACHE_HASHSIZE];
587 while (ret && ret->ino < ino) {
591 if (ret && ret->ino != ino)
594 D2(printk(KERN_DEBUG "jffs2_get_ino_cache found %p for ino %u\n", ret, ino));
598 void jffs2_add_ino_cache (struct jffs2_sb_info *c, struct jffs2_inode_cache *new)
600 struct jffs2_inode_cache **prev;
602 spin_lock(&c->inocache_lock);
604 new->ino = ++c->highest_ino;
606 D2(printk(KERN_DEBUG "jffs2_add_ino_cache: Add %p (ino #%u)\n", new, new->ino));
608 prev = &c->inocache_list[new->ino % INOCACHE_HASHSIZE];
610 while ((*prev) && (*prev)->ino < new->ino) {
611 prev = &(*prev)->next;
616 spin_unlock(&c->inocache_lock);
619 void jffs2_del_ino_cache(struct jffs2_sb_info *c, struct jffs2_inode_cache *old)
621 struct jffs2_inode_cache **prev;
622 D1(printk(KERN_DEBUG "jffs2_del_ino_cache: Del %p (ino #%u)\n", old, old->ino));
623 spin_lock(&c->inocache_lock);
625 prev = &c->inocache_list[old->ino % INOCACHE_HASHSIZE];
627 while ((*prev) && (*prev)->ino < old->ino) {
628 prev = &(*prev)->next;
630 if ((*prev) == old) {
634 /* Free it now unless it's in READING or CLEARING state, which
635 are the transitions upon read_inode() and clear_inode(). The
636 rest of the time we know nobody else is looking at it, and
637 if it's held by read_inode() or clear_inode() they'll free it
639 if (old->state != INO_STATE_READING && old->state != INO_STATE_CLEARING)
640 jffs2_free_inode_cache(old);
642 spin_unlock(&c->inocache_lock);
645 void jffs2_free_ino_caches(struct jffs2_sb_info *c)
648 struct jffs2_inode_cache *this, *next;
650 for (i=0; i<INOCACHE_HASHSIZE; i++) {
651 this = c->inocache_list[i];
654 jffs2_free_inode_cache(this);
657 c->inocache_list[i] = NULL;
661 void jffs2_free_raw_node_refs(struct jffs2_sb_info *c)
664 struct jffs2_raw_node_ref *this, *next;
666 for (i=0; i<c->nr_blocks; i++) {
667 this = c->blocks[i].first_node;
669 next = this->next_phys;
670 jffs2_free_raw_node_ref(this);
673 c->blocks[i].first_node = c->blocks[i].last_node = NULL;
677 struct jffs2_node_frag *jffs2_lookup_node_frag(struct rb_root *fragtree, uint32_t offset)
679 /* The common case in lookup is that there will be a node
680 which precisely matches. So we go looking for that first */
681 struct rb_node *next;
682 struct jffs2_node_frag *prev = NULL;
683 struct jffs2_node_frag *frag = NULL;
685 D2(printk(KERN_DEBUG "jffs2_lookup_node_frag(%p, %d)\n", fragtree, offset));
687 next = fragtree->rb_node;
690 frag = rb_entry(next, struct jffs2_node_frag, rb);
692 D2(printk(KERN_DEBUG "Considering frag %d-%d (%p). left %p, right %p\n",
693 frag->ofs, frag->ofs+frag->size, frag, frag->rb.rb_left, frag->rb.rb_right));
694 if (frag->ofs + frag->size <= offset) {
695 D2(printk(KERN_DEBUG "Going right from frag %d-%d, before the region we care about\n",
696 frag->ofs, frag->ofs+frag->size));
697 /* Remember the closest smaller match on the way down */
698 if (!prev || frag->ofs > prev->ofs)
700 next = frag->rb.rb_right;
701 } else if (frag->ofs > offset) {
702 D2(printk(KERN_DEBUG "Going left from frag %d-%d, after the region we care about\n",
703 frag->ofs, frag->ofs+frag->size));
704 next = frag->rb.rb_left;
706 D2(printk(KERN_DEBUG "Returning frag %d,%d, matched\n",
707 frag->ofs, frag->ofs+frag->size));
712 /* Exact match not found. Go back up looking at each parent,
713 and return the closest smaller one */
716 D2(printk(KERN_DEBUG "No match. Returning frag %d,%d, closest previous\n",
717 prev->ofs, prev->ofs+prev->size));
719 D2(printk(KERN_DEBUG "Returning NULL, empty fragtree\n"));
724 /* Pass 'c' argument to indicate that nodes should be marked obsolete as
726 void jffs2_kill_fragtree(struct rb_root *root, struct jffs2_sb_info *c)
728 struct jffs2_node_frag *frag;
729 struct jffs2_node_frag *parent;
734 frag = (rb_entry(root->rb_node, struct jffs2_node_frag, rb));
737 if (frag->rb.rb_left) {
738 D2(printk(KERN_DEBUG "Going left from frag (%p) %d-%d\n",
739 frag, frag->ofs, frag->ofs+frag->size));
740 frag = frag_left(frag);
743 if (frag->rb.rb_right) {
744 D2(printk(KERN_DEBUG "Going right from frag (%p) %d-%d\n",
745 frag, frag->ofs, frag->ofs+frag->size));
746 frag = frag_right(frag);
750 D2(printk(KERN_DEBUG "jffs2_kill_fragtree: frag at 0x%x-0x%x: node %p, frags %d--\n",
751 frag->ofs, frag->ofs+frag->size, frag->node,
752 frag->node?frag->node->frags:0));
754 if (frag->node && !(--frag->node->frags)) {
755 /* Not a hole, and it's the final remaining frag
756 of this node. Free the node */
758 jffs2_mark_node_obsolete(c, frag->node->raw);
760 jffs2_free_full_dnode(frag->node);
762 parent = frag_parent(frag);
764 if (frag_left(parent) == frag)
765 parent->rb.rb_left = NULL;
767 parent->rb.rb_right = NULL;
770 jffs2_free_node_frag(frag);
777 void jffs2_fragtree_insert(struct jffs2_node_frag *newfrag, struct jffs2_node_frag *base)
779 struct rb_node *parent = &base->rb;
780 struct rb_node **link = &parent;
782 D2(printk(KERN_DEBUG "jffs2_fragtree_insert(%p; %d-%d, %p)\n", newfrag,
783 newfrag->ofs, newfrag->ofs+newfrag->size, base));
787 base = rb_entry(parent, struct jffs2_node_frag, rb);
789 D2(printk(KERN_DEBUG "fragtree_insert considering frag at 0x%x\n", base->ofs));
790 if (newfrag->ofs > base->ofs)
791 link = &base->rb.rb_right;
792 else if (newfrag->ofs < base->ofs)
793 link = &base->rb.rb_left;
795 printk(KERN_CRIT "Duplicate frag at %08x (%p,%p)\n", newfrag->ofs, newfrag, base);
800 rb_link_node(&newfrag->rb, &base->rb, link);