2 * JFFS2 -- Journalling Flash File System, Version 2.
4 * Copyright (C) 2001-2003 Red Hat, Inc.
6 * Created by David Woodhouse <dwmw2@redhat.com>
8 * For licensing information, see the file 'LICENCE' in this directory.
10 * $Id: nodelist.c,v 1.80 2003/10/04 08:33:06 dwmw2 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
;
58 /* Put a new tmp_dnode_info into the list, keeping the list in
59 order of increasing version
61 void jffs2_add_tn_to_list(struct jffs2_tmp_dnode_info
*tn
, struct jffs2_tmp_dnode_info
**list
)
63 struct jffs2_tmp_dnode_info
**prev
= list
;
65 while ((*prev
) && (*prev
)->version
< tn
->version
) {
66 prev
= &((*prev
)->next
);
72 static void jffs2_free_tmp_dnode_info_list(struct jffs2_tmp_dnode_info
*tn
)
74 struct jffs2_tmp_dnode_info
*next
;
79 jffs2_free_full_dnode(next
->fn
);
80 jffs2_free_tmp_dnode_info(next
);
84 static void jffs2_free_full_dirent_list(struct jffs2_full_dirent
*fd
)
86 struct jffs2_full_dirent
*next
;
90 jffs2_free_full_dirent(fd
);
96 /* Get tmp_dnode_info and full_dirent for all non-obsolete nodes associated
97 with this ino, returning the former in order of version */
99 int jffs2_get_inode_nodes(struct jffs2_sb_info
*c
, ino_t ino
, struct jffs2_inode_info
*f
,
100 struct jffs2_tmp_dnode_info
**tnp
, struct jffs2_full_dirent
**fdp
,
101 uint32_t *highest_version
, uint32_t *latest_mctime
,
102 uint32_t *mctime_ver
)
104 struct jffs2_raw_node_ref
*ref
= f
->inocache
->nodes
;
105 struct jffs2_tmp_dnode_info
*tn
, *ret_tn
= NULL
;
106 struct jffs2_full_dirent
*fd
, *ret_fd
= NULL
;
108 union jffs2_node_union node
;
114 D1(printk(KERN_DEBUG
"jffs2_get_inode_nodes(): ino #%lu\n", ino
));
115 if (!f
->inocache
->nodes
) {
116 printk(KERN_WARNING
"Eep. no nodes for ino #%lu\n", (unsigned long)ino
);
119 spin_lock(&c
->erase_completion_lock
);
121 for (ref
= f
->inocache
->nodes
; ref
&& ref
->next_in_ino
; ref
= ref
->next_in_ino
) {
122 /* Work out whether it's a data node or a dirent node */
123 if (ref_obsolete(ref
)) {
124 /* FIXME: On NAND flash we may need to read these */
125 D1(printk(KERN_DEBUG
"node at 0x%08x is obsoleted. Ignoring.\n", ref_offset(ref
)));
128 /* We can hold a pointer to a non-obsolete node without the spinlock,
129 but _obsolete_ nodes may disappear at any time, if the block
130 they're in gets erased */
131 spin_unlock(&c
->erase_completion_lock
);
136 err
= jffs2_flash_read(c
, (ref_offset(ref
)), min_t(uint32_t, ref
->totlen
, sizeof(node
)), &retlen
, (void *)&node
);
138 printk(KERN_WARNING
"error %d reading node at 0x%08x in get_inode_nodes()\n", err
, ref_offset(ref
));
143 /* Check we've managed to read at least the common node header */
144 if (retlen
< min_t(uint32_t, ref
->totlen
, sizeof(node
.u
))) {
145 printk(KERN_WARNING
"short read in get_inode_nodes()\n");
150 switch (je16_to_cpu(node
.u
.nodetype
)) {
151 case JFFS2_NODETYPE_DIRENT
:
152 D1(printk(KERN_DEBUG
"Node at %08x (%d) is a dirent node\n", ref_offset(ref
), ref_flags(ref
)));
153 if (ref_flags(ref
) == REF_UNCHECKED
) {
154 printk(KERN_WARNING
"BUG: Dirent node at 0x%08x never got checked? How?\n", ref_offset(ref
));
157 if (retlen
< sizeof(node
.d
)) {
158 printk(KERN_WARNING
"short read in get_inode_nodes()\n");
163 if (PAD((node
.d
.nsize
+ sizeof (node
.d
))) != PAD(je32_to_cpu (node
.d
.totlen
))) {
164 printk(KERN_NOTICE
"jffs2_get_inode_nodes(): Illegal nsize in node at 0x%08x: nsize 0x%02x, totlen %04x\n",
165 ref_offset(ref
), node
.d
.nsize
, je32_to_cpu(node
.d
.totlen
));
166 jffs2_mark_node_obsolete(c
, ref
);
167 spin_lock(&c
->erase_completion_lock
);
170 if (je32_to_cpu(node
.d
.version
) > *highest_version
)
171 *highest_version
= je32_to_cpu(node
.d
.version
);
172 if (ref_obsolete(ref
)) {
173 /* Obsoleted. This cannot happen, surely? dwmw2 20020308 */
174 printk(KERN_ERR
"Dirent node at 0x%08x became obsolete while we weren't looking\n",
179 fd
= jffs2_alloc_full_dirent(node
.d
.nsize
+1);
184 memset(fd
,0,sizeof(struct jffs2_full_dirent
) + node
.d
.nsize
+1);
186 fd
->version
= je32_to_cpu(node
.d
.version
);
187 fd
->ino
= je32_to_cpu(node
.d
.ino
);
188 fd
->type
= node
.d
.type
;
190 /* Pick out the mctime of the latest dirent */
191 if(fd
->version
> *mctime_ver
) {
192 *mctime_ver
= fd
->version
;
193 *latest_mctime
= je32_to_cpu(node
.d
.mctime
);
196 /* memcpy as much of the name as possible from the raw
197 dirent we've already read from the flash
199 if (retlen
> sizeof(struct jffs2_raw_dirent
))
200 memcpy(&fd
->name
[0], &node
.d
.name
[0], min_t(uint32_t, node
.d
.nsize
, (retlen
-sizeof(struct jffs2_raw_dirent
))));
202 /* Do we need to copy any more of the name directly
205 if (node
.d
.nsize
+ sizeof(struct jffs2_raw_dirent
) > retlen
) {
207 int already
= retlen
- sizeof(struct jffs2_raw_dirent
);
209 err
= jffs2_flash_read(c
, (ref_offset(ref
)) + retlen
,
210 node
.d
.nsize
- already
, &retlen
, &fd
->name
[already
]);
211 if (!err
&& retlen
!= node
.d
.nsize
- already
)
215 printk(KERN_WARNING
"Read remainder of name in jffs2_get_inode_nodes(): error %d\n", err
);
216 jffs2_free_full_dirent(fd
);
220 fd
->nhash
= full_name_hash(fd
->name
, node
.d
.nsize
);
222 /* Wheee. We now have a complete jffs2_full_dirent structure, with
223 the name in it and everything. Link it into the list
225 D1(printk(KERN_DEBUG
"Adding fd \"%s\", ino #%u\n", fd
->name
, fd
->ino
));
226 jffs2_add_fd_to_list(c
, fd
, &ret_fd
);
229 case JFFS2_NODETYPE_INODE
:
230 D1(printk(KERN_DEBUG
"Node at %08x (%d) is a data node\n", ref_offset(ref
), ref_flags(ref
)));
231 if (retlen
< sizeof(node
.i
)) {
232 printk(KERN_WARNING
"read too short for dnode\n");
236 if (je32_to_cpu(node
.i
.version
) > *highest_version
)
237 *highest_version
= je32_to_cpu(node
.i
.version
);
238 D1(printk(KERN_DEBUG
"version %d, highest_version now %d\n", je32_to_cpu(node
.i
.version
), *highest_version
));
240 if (ref_obsolete(ref
)) {
241 /* Obsoleted. This cannot happen, surely? dwmw2 20020308 */
242 printk(KERN_ERR
"Inode node at 0x%08x became obsolete while we weren't looking\n",
247 /* If we've never checked the CRCs on this node, check them now. */
248 if (ref_flags(ref
) == REF_UNCHECKED
) {
250 struct jffs2_eraseblock
*jeb
;
252 crc
= crc32(0, &node
, sizeof(node
.i
)-8);
253 if (crc
!= je32_to_cpu(node
.i
.node_crc
)) {
254 printk(KERN_NOTICE
"jffs2_get_inode_nodes(): CRC failed on node at 0x%08x: Read 0x%08x, calculated 0x%08x\n",
255 ref_offset(ref
), je32_to_cpu(node
.i
.node_crc
), crc
);
256 jffs2_mark_node_obsolete(c
, ref
);
257 spin_lock(&c
->erase_completion_lock
);
262 if ( je32_to_cpu(node
.i
.offset
) > je32_to_cpu(node
.i
.isize
) ||
263 PAD(je32_to_cpu(node
.i
.csize
) + sizeof (node
.i
)) != PAD(je32_to_cpu(node
.i
.totlen
))) {
264 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",
265 ref_offset(ref
), je32_to_cpu(node
.i
.totlen
), je32_to_cpu(node
.i
.ino
),
266 je32_to_cpu(node
.i
.version
), je32_to_cpu(node
.i
.isize
),
267 je32_to_cpu(node
.i
.csize
), je32_to_cpu(node
.i
.dsize
));
268 jffs2_mark_node_obsolete(c
, ref
);
269 spin_lock(&c
->erase_completion_lock
);
273 if (node
.i
.compr
!= JFFS2_COMPR_ZERO
&& je32_to_cpu(node
.i
.csize
)) {
274 unsigned char *buf
=NULL
;
275 uint32_t pointed
= 0;
278 err
= c
->mtd
->point (c
->mtd
, ref_offset(ref
) + sizeof(node
.i
), je32_to_cpu(node
.i
.csize
),
280 if (!err
&& retlen
< je32_to_cpu(node
.i
.csize
)) {
281 D1(printk(KERN_DEBUG
"MTD point returned len too short: 0x%zx\n", retlen
));
282 c
->mtd
->unpoint(c
->mtd
, buf
, ref_offset(ref
) + sizeof(node
.i
), je32_to_cpu(node
.i
.csize
));
284 D1(printk(KERN_DEBUG
"MTD point failed %d\n", err
));
286 pointed
= 1; /* succefully pointed to device */
290 buf
= kmalloc(je32_to_cpu(node
.i
.csize
), GFP_KERNEL
);
294 err
= jffs2_flash_read(c
, ref_offset(ref
) + sizeof(node
.i
), je32_to_cpu(node
.i
.csize
),
296 if (!err
&& retlen
!= je32_to_cpu(node
.i
.csize
))
303 crc
= crc32(0, buf
, je32_to_cpu(node
.i
.csize
));
308 c
->mtd
->unpoint(c
->mtd
, buf
, ref_offset(ref
) + sizeof(node
.i
), je32_to_cpu(node
.i
.csize
));
311 if (crc
!= je32_to_cpu(node
.i
.data_crc
)) {
312 printk(KERN_NOTICE
"jffs2_get_inode_nodes(): Data CRC failed on node at 0x%08x: Read 0x%08x, calculated 0x%08x\n",
313 ref_offset(ref
), je32_to_cpu(node
.i
.data_crc
), crc
);
314 jffs2_mark_node_obsolete(c
, ref
);
315 spin_lock(&c
->erase_completion_lock
);
321 /* Mark the node as having been checked and fix the accounting accordingly */
322 spin_lock(&c
->erase_completion_lock
);
323 jeb
= &c
->blocks
[ref
->flash_offset
/ c
->sector_size
];
324 jeb
->used_size
+= ref
->totlen
;
325 jeb
->unchecked_size
-= ref
->totlen
;
326 c
->used_size
+= ref
->totlen
;
327 c
->unchecked_size
-= ref
->totlen
;
329 /* If node covers at least a whole page, or if it starts at the
330 beginning of a page and runs to the end of the file, or if
331 it's a hole node, mark it REF_PRISTINE, else REF_NORMAL.
333 If it's actually overlapped, it'll get made NORMAL (or OBSOLETE)
334 when the overlapping node(s) get added to the tree anyway.
336 if ((je32_to_cpu(node
.i
.dsize
) >= PAGE_CACHE_SIZE
) ||
337 ( ((je32_to_cpu(node
.i
.offset
)&(PAGE_CACHE_SIZE
-1))==0) &&
338 (je32_to_cpu(node
.i
.dsize
)+je32_to_cpu(node
.i
.offset
) == je32_to_cpu(node
.i
.isize
)))) {
339 D1(printk(KERN_DEBUG
"Marking node at 0x%08x REF_PRISTINE\n", ref_offset(ref
)));
340 ref
->flash_offset
= ref_offset(ref
) | REF_PRISTINE
;
342 D1(printk(KERN_DEBUG
"Marking node at 0x%08x REF_NORMAL\n", ref_offset(ref
)));
343 ref
->flash_offset
= ref_offset(ref
) | REF_NORMAL
;
345 spin_unlock(&c
->erase_completion_lock
);
348 tn
= jffs2_alloc_tmp_dnode_info();
350 D1(printk(KERN_DEBUG
"alloc tn failed\n"));
355 tn
->fn
= jffs2_alloc_full_dnode();
357 D1(printk(KERN_DEBUG
"alloc fn failed\n"));
359 jffs2_free_tmp_dnode_info(tn
);
362 tn
->version
= je32_to_cpu(node
.i
.version
);
363 tn
->fn
->ofs
= je32_to_cpu(node
.i
.offset
);
364 /* There was a bug where we wrote hole nodes out with
365 csize/dsize swapped. Deal with it */
366 if (node
.i
.compr
== JFFS2_COMPR_ZERO
&& !je32_to_cpu(node
.i
.dsize
) && je32_to_cpu(node
.i
.csize
))
367 tn
->fn
->size
= je32_to_cpu(node
.i
.csize
);
368 else // normal case...
369 tn
->fn
->size
= je32_to_cpu(node
.i
.dsize
);
371 D1(printk(KERN_DEBUG
"dnode @%08x: ver %u, offset %04x, dsize %04x\n",
372 ref_offset(ref
), je32_to_cpu(node
.i
.version
),
373 je32_to_cpu(node
.i
.offset
), je32_to_cpu(node
.i
.dsize
)));
374 jffs2_add_tn_to_list(tn
, &ret_tn
);
378 if (ref_flags(ref
) == REF_UNCHECKED
) {
379 struct jffs2_eraseblock
*jeb
;
381 printk(KERN_ERR
"Eep. Unknown node type %04x at %08x was marked REF_UNCHECKED\n",
382 je16_to_cpu(node
.u
.nodetype
), ref_offset(ref
));
384 /* Mark the node as having been checked and fix the accounting accordingly */
385 spin_lock(&c
->erase_completion_lock
);
386 jeb
= &c
->blocks
[ref
->flash_offset
/ c
->sector_size
];
387 jeb
->used_size
+= ref
->totlen
;
388 jeb
->unchecked_size
-= ref
->totlen
;
389 c
->used_size
+= ref
->totlen
;
390 c
->unchecked_size
-= ref
->totlen
;
392 mark_ref_normal(ref
);
393 spin_unlock(&c
->erase_completion_lock
);
395 node
.u
.nodetype
= cpu_to_je16(JFFS2_NODE_ACCURATE
| je16_to_cpu(node
.u
.nodetype
));
396 if (crc32(0, &node
, sizeof(struct jffs2_unknown_node
)-4) != je32_to_cpu(node
.u
.hdr_crc
)) {
397 /* Hmmm. This should have been caught at scan time. */
398 printk(KERN_ERR
"Node header CRC failed at %08x. But it must have been OK earlier.\n",
400 printk(KERN_ERR
"Node was: { %04x, %04x, %08x, %08x }\n",
401 je16_to_cpu(node
.u
.magic
), je16_to_cpu(node
.u
.nodetype
), je32_to_cpu(node
.u
.totlen
),
402 je32_to_cpu(node
.u
.hdr_crc
));
403 jffs2_mark_node_obsolete(c
, ref
);
404 } else switch(je16_to_cpu(node
.u
.nodetype
) & JFFS2_COMPAT_MASK
) {
405 case JFFS2_FEATURE_INCOMPAT
:
406 printk(KERN_NOTICE
"Unknown INCOMPAT nodetype %04X at %08x\n", je16_to_cpu(node
.u
.nodetype
), ref_offset(ref
));
410 case JFFS2_FEATURE_ROCOMPAT
:
411 printk(KERN_NOTICE
"Unknown ROCOMPAT nodetype %04X at %08x\n", je16_to_cpu(node
.u
.nodetype
), ref_offset(ref
));
412 if (!(c
->flags
& JFFS2_SB_FLAG_RO
))
415 case JFFS2_FEATURE_RWCOMPAT_COPY
:
416 printk(KERN_NOTICE
"Unknown RWCOMPAT_COPY nodetype %04X at %08x\n", je16_to_cpu(node
.u
.nodetype
), ref_offset(ref
));
418 case JFFS2_FEATURE_RWCOMPAT_DELETE
:
419 printk(KERN_NOTICE
"Unknown RWCOMPAT_DELETE nodetype %04X at %08x\n", je16_to_cpu(node
.u
.nodetype
), ref_offset(ref
));
420 jffs2_mark_node_obsolete(c
, ref
);
425 spin_lock(&c
->erase_completion_lock
);
428 spin_unlock(&c
->erase_completion_lock
);
435 jffs2_free_tmp_dnode_info_list(ret_tn
);
436 jffs2_free_full_dirent_list(ret_fd
);
440 void jffs2_set_inocache_state(struct jffs2_sb_info
*c
, struct jffs2_inode_cache
*ic
, int state
)
442 spin_lock(&c
->inocache_lock
);
444 wake_up(&c
->inocache_wq
);
445 spin_unlock(&c
->inocache_lock
);
448 /* During mount, this needs no locking. During normal operation, its
449 callers want to do other stuff while still holding the inocache_lock.
450 Rather than introducing special case get_ino_cache functions or
451 callbacks, we just let the caller do the locking itself. */
453 struct jffs2_inode_cache
*jffs2_get_ino_cache(struct jffs2_sb_info
*c
, uint32_t ino
)
455 struct jffs2_inode_cache
*ret
;
457 D2(printk(KERN_DEBUG
"jffs2_get_ino_cache(): ino %u\n", ino
));
459 ret
= c
->inocache_list
[ino
% INOCACHE_HASHSIZE
];
460 while (ret
&& ret
->ino
< ino
) {
464 if (ret
&& ret
->ino
!= ino
)
467 D2(printk(KERN_DEBUG
"jffs2_get_ino_cache found %p for ino %u\n", ret
, ino
));
471 void jffs2_add_ino_cache (struct jffs2_sb_info
*c
, struct jffs2_inode_cache
*new)
473 struct jffs2_inode_cache
**prev
;
474 D2(printk(KERN_DEBUG
"jffs2_add_ino_cache: Add %p (ino #%u)\n", new, new->ino
));
475 spin_lock(&c
->inocache_lock
);
477 prev
= &c
->inocache_list
[new->ino
% INOCACHE_HASHSIZE
];
479 while ((*prev
) && (*prev
)->ino
< new->ino
) {
480 prev
= &(*prev
)->next
;
485 spin_unlock(&c
->inocache_lock
);
488 void jffs2_del_ino_cache(struct jffs2_sb_info
*c
, struct jffs2_inode_cache
*old
)
490 struct jffs2_inode_cache
**prev
;
491 D2(printk(KERN_DEBUG
"jffs2_del_ino_cache: Del %p (ino #%u)\n", old
, old
->ino
));
492 spin_lock(&c
->inocache_lock
);
494 prev
= &c
->inocache_list
[old
->ino
% INOCACHE_HASHSIZE
];
496 while ((*prev
) && (*prev
)->ino
< old
->ino
) {
497 prev
= &(*prev
)->next
;
499 if ((*prev
) == old
) {
503 spin_unlock(&c
->inocache_lock
);
506 void jffs2_free_ino_caches(struct jffs2_sb_info
*c
)
509 struct jffs2_inode_cache
*this, *next
;
511 for (i
=0; i
<INOCACHE_HASHSIZE
; i
++) {
512 this = c
->inocache_list
[i
];
515 D2(printk(KERN_DEBUG
"jffs2_free_ino_caches: Freeing ino #%u at %p\n", this->ino
, this));
516 jffs2_free_inode_cache(this);
519 c
->inocache_list
[i
] = NULL
;
523 void jffs2_free_raw_node_refs(struct jffs2_sb_info
*c
)
526 struct jffs2_raw_node_ref
*this, *next
;
528 for (i
=0; i
<c
->nr_blocks
; i
++) {
529 this = c
->blocks
[i
].first_node
;
531 next
= this->next_phys
;
532 jffs2_free_raw_node_ref(this);
535 c
->blocks
[i
].first_node
= c
->blocks
[i
].last_node
= NULL
;
539 struct jffs2_node_frag
*jffs2_lookup_node_frag(struct rb_root
*fragtree
, uint32_t offset
)
541 /* The common case in lookup is that there will be a node
542 which precisely matches. So we go looking for that first */
543 struct rb_node
*next
;
544 struct jffs2_node_frag
*prev
= NULL
;
545 struct jffs2_node_frag
*frag
= NULL
;
547 D2(printk(KERN_DEBUG
"jffs2_lookup_node_frag(%p, %d)\n", fragtree
, offset
));
549 next
= fragtree
->rb_node
;
552 frag
= rb_entry(next
, struct jffs2_node_frag
, rb
);
554 D2(printk(KERN_DEBUG
"Considering frag %d-%d (%p). left %p, right %p\n",
555 frag
->ofs
, frag
->ofs
+frag
->size
, frag
, frag
->rb
.rb_left
, frag
->rb
.rb_right
));
556 if (frag
->ofs
+ frag
->size
<= offset
) {
557 D2(printk(KERN_DEBUG
"Going right from frag %d-%d, before the region we care about\n",
558 frag
->ofs
, frag
->ofs
+frag
->size
));
559 /* Remember the closest smaller match on the way down */
560 if (!prev
|| frag
->ofs
> prev
->ofs
)
562 next
= frag
->rb
.rb_right
;
563 } else if (frag
->ofs
> offset
) {
564 D2(printk(KERN_DEBUG
"Going left from frag %d-%d, after the region we care about\n",
565 frag
->ofs
, frag
->ofs
+frag
->size
));
566 next
= frag
->rb
.rb_left
;
568 D2(printk(KERN_DEBUG
"Returning frag %d,%d, matched\n",
569 frag
->ofs
, frag
->ofs
+frag
->size
));
574 /* Exact match not found. Go back up looking at each parent,
575 and return the closest smaller one */
578 D2(printk(KERN_DEBUG
"No match. Returning frag %d,%d, closest previous\n",
579 prev
->ofs
, prev
->ofs
+prev
->size
));
581 D2(printk(KERN_DEBUG
"Returning NULL, empty fragtree\n"));
586 /* Pass 'c' argument to indicate that nodes should be marked obsolete as
588 void jffs2_kill_fragtree(struct rb_root
*root
, struct jffs2_sb_info
*c
)
590 struct jffs2_node_frag
*frag
;
591 struct jffs2_node_frag
*parent
;
596 frag
= (rb_entry(root
->rb_node
, struct jffs2_node_frag
, rb
));
599 if (frag
->rb
.rb_left
) {
600 D2(printk(KERN_DEBUG
"Going left from frag (%p) %d-%d\n",
601 frag
, frag
->ofs
, frag
->ofs
+frag
->size
));
602 frag
= frag_left(frag
);
605 if (frag
->rb
.rb_right
) {
606 D2(printk(KERN_DEBUG
"Going right from frag (%p) %d-%d\n",
607 frag
, frag
->ofs
, frag
->ofs
+frag
->size
));
608 frag
= frag_right(frag
);
612 D2(printk(KERN_DEBUG
"jffs2_kill_fragtree: frag at 0x%x-0x%x: node %p, frags %d--\n",
613 frag
->ofs
, frag
->ofs
+frag
->size
, frag
->node
,
614 frag
->node
?frag
->node
->frags
:0));
616 if (frag
->node
&& !(--frag
->node
->frags
)) {
617 /* Not a hole, and it's the final remaining frag
618 of this node. Free the node */
620 jffs2_mark_node_obsolete(c
, frag
->node
->raw
);
622 jffs2_free_full_dnode(frag
->node
);
624 parent
= frag_parent(frag
);
626 if (frag_left(parent
) == frag
)
627 parent
->rb
.rb_left
= NULL
;
629 parent
->rb
.rb_right
= NULL
;
632 jffs2_free_node_frag(frag
);
637 void jffs2_fragtree_insert(struct jffs2_node_frag
*newfrag
, struct jffs2_node_frag
*base
)
639 struct rb_node
*parent
= &base
->rb
;
640 struct rb_node
**link
= &parent
;
642 D2(printk(KERN_DEBUG
"jffs2_fragtree_insert(%p; %d-%d, %p)\n", newfrag
,
643 newfrag
->ofs
, newfrag
->ofs
+newfrag
->size
, base
));
647 base
= rb_entry(parent
, struct jffs2_node_frag
, rb
);
649 D2(printk(KERN_DEBUG
"fragtree_insert considering frag at 0x%x\n", base
->ofs
));
650 if (newfrag
->ofs
> base
->ofs
)
651 link
= &base
->rb
.rb_right
;
652 else if (newfrag
->ofs
< base
->ofs
)
653 link
= &base
->rb
.rb_left
;
655 printk(KERN_CRIT
"Duplicate frag at %08x (%p,%p)\n", newfrag
->ofs
, newfrag
, base
);
660 rb_link_node(&newfrag
->rb
, &base
->rb
, link
);