]>
git.proxmox.com Git - mirror_ubuntu-artful-kernel.git/blob - fs/jffs2/nodelist.c
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.115 2005/11/07 11:14:40 gleixner 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
;
28 dbg_dentlist ( "add dirent \" %s \" , ino #%u \n " , new -> name
, new -> ino
);
30 while ((* prev
) && (* prev
)-> nhash
<= new -> nhash
) {
31 if ((* prev
)-> nhash
== new -> nhash
&& ! strcmp ((* prev
)-> name
, new -> name
)) {
32 /* Duplicate. Free one */
33 if ( new -> version
< (* prev
)-> version
) {
34 dbg_dentlist ( "Eep! Marking new dirent node is obsolete, old is \" %s \" , ino #%u \n " ,
35 (* prev
)-> name
, (* prev
)-> ino
);
36 jffs2_mark_node_obsolete ( c
, new -> raw
);
37 jffs2_free_full_dirent ( new );
39 dbg_dentlist ( "marking old dirent \" %s \" , ino #%u bsolete \n " ,
40 (* prev
)-> name
, (* prev
)-> ino
);
41 new -> next
= (* prev
)-> next
;
42 jffs2_mark_node_obsolete ( c
, ((* prev
)-> raw
));
43 jffs2_free_full_dirent (* prev
);
48 prev
= &((* prev
)-> next
);
54 void jffs2_truncate_fragtree ( struct jffs2_sb_info
* c
, struct rb_root
* list
, uint32_t size
)
56 struct jffs2_node_frag
* frag
= jffs2_lookup_node_frag ( list
, size
);
58 dbg_fragtree ( "truncating fragtree to 0x%08x bytes \n " , size
);
60 /* We know frag->ofs <= size. That's what lookup does for us */
61 if ( frag
&& frag
-> ofs
!= size
) {
62 if ( frag
-> ofs
+ frag
-> size
> size
) {
63 frag
-> size
= size
- frag
-> ofs
;
65 frag
= frag_next ( frag
);
67 while ( frag
&& frag
-> ofs
>= size
) {
68 struct jffs2_node_frag
* next
= frag_next ( frag
);
70 frag_erase ( frag
, list
);
71 jffs2_obsolete_node_frag ( c
, frag
);
79 * If the last fragment starts at the RAM page boundary, it is
80 * REF_PRISTINE irrespective of its size.
82 frag
= frag_last ( list
);
83 if ( frag
-> node
&& ( frag
-> ofs
& ( PAGE_CACHE_SIZE
- 1 )) == 0 ) {
84 dbg_fragtree2 ( "marking the last fragment 0x%08x-0x%08x REF_PRISTINE. \n " ,
85 frag
-> ofs
, frag
-> ofs
+ frag
-> size
);
86 frag
-> node
-> raw
-> flash_offset
= ref_offset ( frag
-> node
-> raw
) | REF_PRISTINE
;
90 void jffs2_obsolete_node_frag ( struct jffs2_sb_info
* c
, struct jffs2_node_frag
* this )
94 if (! this -> node
-> frags
) {
95 /* The node has no valid frags left. It's totally obsoleted */
96 dbg_fragtree2 ( "marking old node @0x%08x (0x%04x-0x%04x) obsolete \n " ,
97 ref_offset ( this -> node
-> raw
), this -> node
-> ofs
, this -> node
-> ofs
+ this -> node
-> size
);
98 jffs2_mark_node_obsolete ( c
, this -> node
-> raw
);
99 jffs2_free_full_dnode ( this -> node
);
101 dbg_fragtree2 ( "marking old node @0x%08x (0x%04x-0x%04x) REF_NORMAL. frags is %d \n " ,
102 ref_offset ( this -> node
-> raw
), this -> node
-> ofs
, this -> node
-> ofs
+ this -> node
-> size
, this -> node
-> frags
);
103 mark_ref_normal ( this -> node
-> raw
);
107 jffs2_free_node_frag ( this );
110 static void jffs2_fragtree_insert ( struct jffs2_node_frag
* newfrag
, struct jffs2_node_frag
* base
)
112 struct rb_node
* parent
= & base
-> rb
;
113 struct rb_node
** link
= & parent
;
115 dbg_fragtree2 ( "insert frag (0x%04x-0x%04x) \n " , newfrag
-> ofs
, newfrag
-> ofs
+ newfrag
-> size
);
119 base
= rb_entry ( parent
, struct jffs2_node_frag
, rb
);
121 if ( newfrag
-> ofs
> base
-> ofs
)
122 link
= & base
-> rb
. rb_right
;
123 else if ( newfrag
-> ofs
< base
-> ofs
)
124 link
= & base
-> rb
. rb_left
;
126 JFFS2_ERROR ( "duplicate frag at %08x (%p,%p) \n " , newfrag
-> ofs
, newfrag
, base
);
131 rb_link_node (& newfrag
-> rb
, & base
-> rb
, link
);
135 * Allocate and initializes a new fragment.
137 static struct jffs2_node_frag
* new_fragment ( struct jffs2_full_dnode
* fn
, uint32_t ofs
, uint32_t size
)
139 struct jffs2_node_frag
* newfrag
;
141 newfrag
= jffs2_alloc_node_frag ();
142 if ( likely ( newfrag
)) {
144 newfrag
-> size
= size
;
147 JFFS2_ERROR ( "cannot allocate a jffs2_node_frag object \n " );
154 * Called when there is no overlapping fragment exist. Inserts a hole before the new
155 * fragment and inserts the new fragment to the fragtree.
157 static int no_overlapping_node ( struct jffs2_sb_info
* c
, struct rb_root
* root
,
158 struct jffs2_node_frag
* newfrag
,
159 struct jffs2_node_frag
* this , uint32_t lastend
)
161 if ( lastend
< newfrag
-> node
-> ofs
) {
162 /* put a hole in before the new fragment */
163 struct jffs2_node_frag
* holefrag
;
165 holefrag
= new_fragment ( NULL
, lastend
, newfrag
-> node
-> ofs
- lastend
);
166 if ( unlikely (! holefrag
)) {
167 jffs2_free_node_frag ( newfrag
);
172 /* By definition, the 'this' node has no right-hand child,
173 because there are no frags with offset greater than it.
174 So that's where we want to put the hole */
175 dbg_fragtree2 ( "add hole frag %#04x-%#04x on the right of the new frag. \n " ,
176 holefrag
-> ofs
, holefrag
-> ofs
+ holefrag
-> size
);
177 rb_link_node (& holefrag
-> rb
, & this -> rb
, & this -> rb
. rb_right
);
179 dbg_fragtree2 ( "Add hole frag %#04x-%#04x to the root of the tree. \n " ,
180 holefrag
-> ofs
, holefrag
-> ofs
+ holefrag
-> size
);
181 rb_link_node (& holefrag
-> rb
, NULL
, & root
-> rb_node
);
183 rb_insert_color (& holefrag
-> rb
, root
);
188 /* By definition, the 'this' node has no right-hand child,
189 because there are no frags with offset greater than it.
190 So that's where we want to put new fragment */
191 dbg_fragtree2 ( "add the new node at the right \n " );
192 rb_link_node (& newfrag
-> rb
, & this -> rb
, & this -> rb
. rb_right
);
194 dbg_fragtree2 ( "insert the new node at the root of the tree \n " );
195 rb_link_node (& newfrag
-> rb
, NULL
, & root
-> rb_node
);
197 rb_insert_color (& newfrag
-> rb
, root
);
202 /* Doesn't set inode->i_size */
203 static int jffs2_add_frag_to_fragtree ( struct jffs2_sb_info
* c
, struct rb_root
* root
, struct jffs2_node_frag
* newfrag
)
205 struct jffs2_node_frag
* this ;
208 /* Skip all the nodes which are completed before this one starts */
209 this = jffs2_lookup_node_frag ( root
, newfrag
-> node
-> ofs
);
212 dbg_fragtree2 ( "lookup gave frag 0x%04x-0x%04x; phys 0x%08x (*%p) \n " ,
213 this -> ofs
, this -> ofs
+ this -> size
, this -> node
?( ref_offset ( this -> node
-> raw
)): 0xffffffff , this );
214 lastend
= this -> ofs
+ this -> size
;
216 dbg_fragtree2 ( "lookup gave no frag \n " );
220 /* See if we ran off the end of the fragtree */
221 if ( lastend
<= newfrag
-> ofs
) {
224 /* Check if 'this' node was on the same page as the new node.
225 If so, both 'this' and the new node get marked REF_NORMAL so
226 the GC can take a look.
228 if ( lastend
&& ( lastend
- 1 ) >> PAGE_CACHE_SHIFT
== newfrag
-> ofs
>> PAGE_CACHE_SHIFT
) {
230 mark_ref_normal ( this -> node
-> raw
);
231 mark_ref_normal ( newfrag
-> node
-> raw
);
234 return no_overlapping_node ( c
, root
, newfrag
, this , lastend
);
238 dbg_fragtree2 ( "dealing with frag %u-%u, phys %#08x(%d). \n " ,
239 this -> ofs
, this -> ofs
+ this -> size
,
240 ref_offset ( this -> node
-> raw
), ref_flags ( this -> node
-> raw
));
242 dbg_fragtree2 ( "dealing with hole frag %u-%u. \n " ,
243 this -> ofs
, this -> ofs
+ this -> size
);
245 /* OK. 'this' is pointing at the first frag that newfrag->ofs at least partially obsoletes,
246 * - i.e. newfrag->ofs < this->ofs+this->size && newfrag->ofs >= this->ofs
248 if ( newfrag
-> ofs
> this -> ofs
) {
249 /* This node isn't completely obsoleted. The start of it remains valid */
251 /* Mark the new node and the partially covered node REF_NORMAL -- let
252 the GC take a look at them */
253 mark_ref_normal ( newfrag
-> node
-> raw
);
255 mark_ref_normal ( this -> node
-> raw
);
257 if ( this -> ofs
+ this -> size
> newfrag
-> ofs
+ newfrag
-> size
) {
258 /* The new node splits 'this' frag into two */
259 struct jffs2_node_frag
* newfrag2
;
262 dbg_fragtree2 ( "split old frag 0x%04x-0x%04x, phys 0x%08x \n " ,
263 this -> ofs
, this -> ofs
+ this -> size
, ref_offset ( this -> node
-> raw
));
265 dbg_fragtree2 ( "split old hole frag 0x%04x-0x%04x \n " ,
266 this -> ofs
, this -> ofs
+ this -> size
);
268 /* New second frag pointing to this's node */
269 newfrag2
= new_fragment ( this -> node
, newfrag
-> ofs
+ newfrag
-> size
,
270 this -> ofs
+ this -> size
- newfrag
-> ofs
- newfrag
-> size
);
271 if ( unlikely (! newfrag2
))
276 /* Adjust size of original 'this' */
277 this -> size
= newfrag
-> ofs
- this -> ofs
;
279 /* Now, we know there's no node with offset
280 greater than this->ofs but smaller than
281 newfrag2->ofs or newfrag->ofs, for obvious
282 reasons. So we can do a tree insert from
283 'this' to insert newfrag, and a tree insert
284 from newfrag to insert newfrag2. */
285 jffs2_fragtree_insert ( newfrag
, this );
286 rb_insert_color (& newfrag
-> rb
, root
);
288 jffs2_fragtree_insert ( newfrag2
, newfrag
);
289 rb_insert_color (& newfrag2
-> rb
, root
);
293 /* New node just reduces 'this' frag in size, doesn't split it */
294 this -> size
= newfrag
-> ofs
- this -> ofs
;
296 /* Again, we know it lives down here in the tree */
297 jffs2_fragtree_insert ( newfrag
, this );
298 rb_insert_color (& newfrag
-> rb
, root
);
300 /* New frag starts at the same point as 'this' used to. Replace
301 it in the tree without doing a delete and insertion */
302 dbg_fragtree2 ( "inserting newfrag (*%p),%d-%d in before 'this' (*%p),%d-%d \n " ,
303 newfrag
, newfrag
-> ofs
, newfrag
-> ofs
+ newfrag
-> size
, this , this -> ofs
, this -> ofs
+ this -> size
);
305 rb_replace_node (& this -> rb
, & newfrag
-> rb
, root
);
307 if ( newfrag
-> ofs
+ newfrag
-> size
>= this -> ofs
+ this -> size
) {
308 dbg_fragtree2 ( "obsoleting node frag %p (%x-%x) \n " , this , this -> ofs
, this -> ofs
+ this -> size
);
309 jffs2_obsolete_node_frag ( c
, this );
311 this -> ofs
+= newfrag
-> size
;
312 this -> size
-= newfrag
-> size
;
314 jffs2_fragtree_insert ( this , newfrag
);
315 rb_insert_color (& this -> rb
, root
);
319 /* OK, now we have newfrag added in the correct place in the tree, but
320 frag_next(newfrag) may be a fragment which is overlapped by it
322 while (( this = frag_next ( newfrag
)) && newfrag
-> ofs
+ newfrag
-> size
>= this -> ofs
+ this -> size
) {
323 /* 'this' frag is obsoleted completely. */
324 dbg_fragtree2 ( "obsoleting node frag %p (%x-%x) and removing from tree \n " ,
325 this , this -> ofs
, this -> ofs
+ this -> size
);
326 rb_erase (& this -> rb
, root
);
327 jffs2_obsolete_node_frag ( c
, this );
329 /* Now we're pointing at the first frag which isn't totally obsoleted by
332 if (! this || newfrag
-> ofs
+ newfrag
-> size
== this -> ofs
)
335 /* Still some overlap but we don't need to move it in the tree */
336 this -> size
= ( this -> ofs
+ this -> size
) - ( newfrag
-> ofs
+ newfrag
-> size
);
337 this -> ofs
= newfrag
-> ofs
+ newfrag
-> size
;
339 /* And mark them REF_NORMAL so the GC takes a look at them */
341 mark_ref_normal ( this -> node
-> raw
);
342 mark_ref_normal ( newfrag
-> node
-> raw
);
348 * Given an inode, probably with existing tree of fragments, add the new node
349 * to the fragment tree.
351 int jffs2_add_full_dnode_to_inode ( struct jffs2_sb_info
* c
, struct jffs2_inode_info
* f
, struct jffs2_full_dnode
* fn
)
354 struct jffs2_node_frag
* newfrag
;
356 if ( unlikely (! fn
-> size
))
359 newfrag
= new_fragment ( fn
, fn
-> ofs
, fn
-> size
);
360 if ( unlikely (! newfrag
))
362 newfrag
-> node
-> frags
= 1 ;
364 dbg_fragtree ( "adding node %#04x-%#04x @0x%08x on flash, newfrag *%p \n " ,
365 fn
-> ofs
, fn
-> ofs
+ fn
-> size
, ref_offset ( fn
-> raw
), newfrag
);
367 ret
= jffs2_add_frag_to_fragtree ( c
, & f
-> fragtree
, newfrag
);
371 /* If we now share a page with other nodes, mark either previous
372 or next node REF_NORMAL, as appropriate. */
373 if ( newfrag
-> ofs
& ( PAGE_CACHE_SIZE
- 1 )) {
374 struct jffs2_node_frag
* prev
= frag_prev ( newfrag
);
376 mark_ref_normal ( fn
-> raw
);
377 /* If we don't start at zero there's _always_ a previous */
379 mark_ref_normal ( prev
-> node
-> raw
);
382 if (( newfrag
-> ofs
+ newfrag
-> size
) & ( PAGE_CACHE_SIZE
- 1 )) {
383 struct jffs2_node_frag
* next
= frag_next ( newfrag
);
386 mark_ref_normal ( fn
-> raw
);
388 mark_ref_normal ( next
-> node
-> raw
);
391 jffs2_dbg_fragtree_paranoia_check_nolock ( f
);
397 * Check the data CRC of the node.
399 * Returns: 0 if the data CRC is correct;
401 * error code if an error occured.
403 static int check_node_data ( struct jffs2_sb_info
* c
, struct jffs2_tmp_dnode_info
* tn
)
405 struct jffs2_raw_node_ref
* ref
= tn
-> fn
-> raw
;
406 int err
= 0 , pointed
= 0 ;
407 struct jffs2_eraseblock
* jeb
;
408 unsigned char * buffer
;
409 uint32_t crc
, ofs
, retlen
, len
;
411 BUG_ON ( tn
-> csize
== 0 );
413 if (! jffs2_is_writebuffered ( c
))
416 /* Calculate how many bytes were already checked */
417 ofs
= ref_offset ( ref
) + sizeof ( struct jffs2_raw_inode
);
418 len
= ofs
% c
-> wbuf_pagesize
;
420 len
= c
-> wbuf_pagesize
- len
;
422 if ( len
>= tn
-> csize
) {
423 dbg_readinode ( "no need to check node at %#08x, data length %u, data starts at %#08x - it has already been checked. \n " ,
424 ref_offset ( ref
), tn
-> csize
, ofs
);
429 len
= tn
-> csize
- len
;
431 dbg_readinode ( "check node at %#08x, data length %u, partial CRC %#08x, correct CRC %#08x, data starts at %#08x, start checking from %#08x - %u bytes. \n " ,
432 ref_offset ( ref
), tn
-> csize
, tn
-> partial_crc
, tn
-> data_crc
, ofs
- len
, ofs
, len
);
435 /* TODO: instead, incapsulate point() stuff to jffs2_flash_read(),
436 * adding and jffs2_flash_read_end() interface. */
438 err
= c
-> mtd
-> point ( c
-> mtd
, ofs
, len
, & retlen
, & buffer
);
439 if (! err
&& retlen
< tn
-> csize
) {
440 JFFS2_WARNING ( "MTD point returned len too short: %u instead of %u. \n " , retlen
, tn
-> csize
);
441 c
-> mtd
-> unpoint ( c
-> mtd
, buffer
, ofs
, len
);
443 JFFS2_WARNING ( "MTD point failed: error code %d. \n " , err
);
445 pointed
= 1 ; /* succefully pointed to device */
450 buffer
= kmalloc ( len
, GFP_KERNEL
);
451 if ( unlikely (! buffer
))
454 /* TODO: this is very frequent pattern, make it a separate
456 err
= jffs2_flash_read ( c
, ofs
, len
, & retlen
, buffer
);
458 JFFS2_ERROR ( "can not read %d bytes from 0x%08x, error code: %d. \n " , len
, ofs
, err
);
463 JFFS2_ERROR ( "short read at %#08x: %d instead of %d. \n " , ofs
, retlen
, len
);
469 /* Continue calculating CRC */
470 crc
= crc32 ( tn
-> partial_crc
, buffer
, len
);
475 c
-> mtd
-> unpoint ( c
-> mtd
, buffer
, ofs
, len
);
478 if ( crc
!= tn
-> data_crc
) {
479 JFFS2_NOTICE ( "wrong data CRC in data node at 0x%08x: read %#08x, calculated %#08x. \n " ,
480 ofs
, tn
-> data_crc
, crc
);
485 jeb
= & c
-> blocks
[ ref
-> flash_offset
/ c
-> sector_size
];
486 len
= ref_totlen ( c
, jeb
, ref
);
489 * Mark the node as having been checked and fix the
490 * accounting accordingly.
492 spin_lock (& c
-> erase_completion_lock
);
493 jeb
-> used_size
+= len
;
494 jeb
-> unchecked_size
-= len
;
496 c
-> unchecked_size
-= len
;
497 spin_unlock (& c
-> erase_completion_lock
);
506 c
-> mtd
-> unpoint ( c
-> mtd
, buffer
, ofs
, len
);
512 * Helper function for jffs2_add_older_frag_to_fragtree().
514 * Checks the node if we are in the checking stage.
516 static int check_node ( struct jffs2_sb_info
* c
, struct jffs2_inode_info
* f
, struct jffs2_tmp_dnode_info
* tn
)
520 BUG_ON ( ref_obsolete ( tn
-> fn
-> raw
));
522 /* We only check the data CRC of unchecked nodes */
523 if ( ref_flags ( tn
-> fn
-> raw
) != REF_UNCHECKED
)
526 dbg_fragtree2 ( "check node %#04x-%#04x, phys offs %#08x. \n " ,
527 tn
-> fn
-> ofs
, tn
-> fn
-> ofs
+ tn
-> fn
-> size
, ref_offset ( tn
-> fn
-> raw
));
529 ret
= check_node_data ( c
, tn
);
530 if ( unlikely ( ret
< 0 )) {
531 JFFS2_ERROR ( "check_node_data() returned error: %d. \n " ,
533 } else if ( unlikely ( ret
> 0 )) {
534 dbg_fragtree2 ( "CRC error, mark it obsolete. \n " );
535 jffs2_mark_node_obsolete ( c
, tn
-> fn
-> raw
);
542 * Helper function for jffs2_add_older_frag_to_fragtree().
544 * Called when the new fragment that is being inserted
545 * splits a hole fragment.
547 static int split_hole ( struct jffs2_sb_info
* c
, struct rb_root
* root
,
548 struct jffs2_node_frag
* newfrag
, struct jffs2_node_frag
* hole
)
550 dbg_fragtree2 ( "fragment %#04x-%#04x splits the hole %#04x-%#04x \n " ,
551 newfrag
-> ofs
, newfrag
-> ofs
+ newfrag
-> size
, hole
-> ofs
, hole
-> ofs
+ hole
-> size
);
553 if ( hole
-> ofs
== newfrag
-> ofs
) {
555 * Well, the new fragment actually starts at the same offset as
558 if ( hole
-> ofs
+ hole
-> size
> newfrag
-> ofs
+ newfrag
-> size
) {
560 * We replace the overlapped left part of the hole by
564 dbg_fragtree2 ( "insert fragment %#04x-%#04x and cut the left part of the hole \n " ,
565 newfrag
-> ofs
, newfrag
-> ofs
+ newfrag
-> size
);
566 rb_replace_node (& hole
-> rb
, & newfrag
-> rb
, root
);
568 hole
-> ofs
+= newfrag
-> size
;
569 hole
-> size
-= newfrag
-> size
;
572 * We know that 'hole' should be the right hand
575 jffs2_fragtree_insert ( hole
, newfrag
);
576 rb_insert_color (& hole
-> rb
, root
);
579 * Ah, the new fragment is of the same size as the hole.
580 * Relace the hole by it.
582 dbg_fragtree2 ( "insert fragment %#04x-%#04x and overwrite hole \n " ,
583 newfrag
-> ofs
, newfrag
-> ofs
+ newfrag
-> size
);
584 rb_replace_node (& hole
-> rb
, & newfrag
-> rb
, root
);
585 jffs2_free_node_frag ( hole
);
588 /* The new fragment lefts some hole space at the left */
590 struct jffs2_node_frag
* newfrag2
= NULL
;
592 if ( hole
-> ofs
+ hole
-> size
> newfrag
-> ofs
+ newfrag
-> size
) {
593 /* The new frag also lefts some space at the right */
594 newfrag2
= new_fragment ( NULL
, newfrag
-> ofs
+
595 newfrag
-> size
, hole
-> ofs
+ hole
-> size
596 - newfrag
-> ofs
- newfrag
-> size
);
597 if ( unlikely (! newfrag2
)) {
598 jffs2_free_node_frag ( newfrag
);
603 hole
-> size
= newfrag
-> ofs
- hole
-> ofs
;
604 dbg_fragtree2 ( "left the hole %#04x-%#04x at the left and inserd fragment %#04x-%#04x \n " ,
605 hole
-> ofs
, hole
-> ofs
+ hole
-> size
, newfrag
-> ofs
, newfrag
-> ofs
+ newfrag
-> size
);
607 jffs2_fragtree_insert ( newfrag
, hole
);
608 rb_insert_color (& newfrag
-> rb
, root
);
611 dbg_fragtree2 ( "left the hole %#04x-%#04x at the right \n " ,
612 newfrag2
-> ofs
, newfrag2
-> ofs
+ newfrag2
-> size
);
613 jffs2_fragtree_insert ( newfrag2
, newfrag
);
614 rb_insert_color (& newfrag2
-> rb
, root
);
622 * This function is used when we build inode. It expects the nodes are passed
623 * in the decreasing version order. The whole point of this is to improve the
624 * inodes checking on NAND: we check the nodes' data CRC only when they are not
625 * obsoleted. Previously, add_frag_to_fragtree() function was used and
626 * nodes were passed to it in the increasing version ordes and CRCs of all
627 * nodes were checked.
629 * Note: tn->fn->size shouldn't be zero.
631 * Returns 0 if the node was inserted
632 * 1 if it wasn't inserted (since it is obsolete)
633 * < 0 an if error occured
635 int jffs2_add_older_frag_to_fragtree ( struct jffs2_sb_info
* c
, struct jffs2_inode_info
* f
,
636 struct jffs2_tmp_dnode_info
* tn
)
638 struct jffs2_node_frag
* this , * newfrag
;
640 struct jffs2_full_dnode
* fn
= tn
-> fn
;
641 struct rb_root
* root
= & f
-> fragtree
;
642 uint32_t fn_size
= fn
-> size
, fn_ofs
= fn
-> ofs
;
643 int err
, checked
= 0 ;
646 dbg_fragtree ( "insert fragment %#04x-%#04x, ver %u \n " , fn_ofs
, fn_ofs
+ fn_size
, tn
-> version
);
648 /* Skip all the nodes which are completed before this one starts */
649 this = jffs2_lookup_node_frag ( root
, fn_ofs
);
651 dbg_fragtree2 ( "'this' found %#04x-%#04x (%s) \n " , this -> ofs
, this -> ofs
+ this -> size
, this -> node
? "data" : "hole" );
654 lastend
= this -> ofs
+ this -> size
;
658 /* Detect the preliminary type of node */
659 if ( fn
-> size
>= PAGE_CACHE_SIZE
)
660 ref_flag
= REF_PRISTINE
;
662 ref_flag
= REF_NORMAL
;
664 /* See if we ran off the end of the root */
665 if ( lastend
<= fn_ofs
) {
669 * We are going to insert the new node into the
670 * fragment tree, so check it.
672 err
= check_node ( c
, f
, tn
);
678 newfrag
= new_fragment ( fn
, fn_ofs
, fn_size
);
679 if ( unlikely (! newfrag
))
682 err
= no_overlapping_node ( c
, root
, newfrag
, this , lastend
);
683 if ( unlikely ( err
!= 0 )) {
684 jffs2_free_node_frag ( newfrag
);
696 * fn_ofs < this->ofs + this->size && fn_ofs >= this->ofs.
698 * Remember, 'this' has higher version, any non-hole node
699 * which is already in the fragtree is newer then the newly
704 * 'this' is the hole fragment, so at least the
705 * beginning of the new fragment is valid.
709 * We are going to insert the new node into the
710 * fragment tree, so check it.
713 err
= check_node ( c
, f
, tn
);
714 if ( unlikely ( err
!= 0 ))
719 if ( this -> ofs
+ this -> size
>= fn_ofs
+ fn_size
) {
720 /* We split the hole on two parts */
723 newfrag
= new_fragment ( fn
, fn_ofs
, fn_size
);
724 if ( unlikely (! newfrag
))
727 err
= split_hole ( c
, root
, newfrag
, this );
734 * The beginning of the new fragment is valid since it
735 * overlaps the hole node.
738 ref_flag
= REF_NORMAL
;
741 newfrag
= new_fragment ( fn
, fn_ofs
,
742 this -> ofs
+ this -> size
- fn_ofs
);
743 if ( unlikely (! newfrag
))
746 if ( fn_ofs
== this -> ofs
) {
748 * The new node starts at the same offset as
749 * the hole and supersieds the hole.
751 dbg_fragtree2 ( "add the new fragment instead of hole %#04x-%#04x, refcnt %d \n " ,
752 fn_ofs
, fn_ofs
+ this -> ofs
+ this -> size
- fn_ofs
, fn
-> frags
);
754 rb_replace_node (& this -> rb
, & newfrag
-> rb
, root
);
755 jffs2_free_node_frag ( this );
758 * The hole becomes shorter as its right part
759 * is supersieded by the new fragment.
761 dbg_fragtree2 ( "reduce size of hole %#04x-%#04x to %#04x-%#04x \n " ,
762 this -> ofs
, this -> ofs
+ this -> size
, this -> ofs
, this -> ofs
+ this -> size
- newfrag
-> size
);
764 dbg_fragtree2 ( "add new fragment %#04x-%#04x, refcnt %d \n " , fn_ofs
,
765 fn_ofs
+ this -> ofs
+ this -> size
- fn_ofs
, fn
-> frags
);
767 this -> size
-= newfrag
-> size
;
768 jffs2_fragtree_insert ( newfrag
, this );
769 rb_insert_color (& newfrag
-> rb
, root
);
772 fn_ofs
+= newfrag
-> size
;
773 fn_size
-= newfrag
-> size
;
774 this = rb_entry ( rb_next (& newfrag
-> rb
),
775 struct jffs2_node_frag
, rb
);
777 dbg_fragtree2 ( "switch to the next 'this' fragment: %#04x-%#04x %s \n " ,
778 this -> ofs
, this -> ofs
+ this -> size
, this -> node
? "(data)" : "(hole)" );
782 * 'This' node is not the hole so it obsoletes the new fragment
783 * either fully or partially.
785 if ( this -> ofs
+ this -> size
>= fn_ofs
+ fn_size
) {
786 /* The new node is obsolete, drop it */
787 if ( fn
-> frags
== 0 ) {
788 dbg_fragtree2 ( "%#04x-%#04x is obsolete, mark it obsolete \n " , fn_ofs
, fn_ofs
+ fn_size
);
789 ref_flag
= REF_OBSOLETE
;
793 struct jffs2_node_frag
* new_this
;
795 /* 'This' node obsoletes the beginning of the new node */
796 dbg_fragtree2 ( "the beginning %#04x-%#04x is obsolete \n " , fn_ofs
, this -> ofs
+ this -> size
);
798 ref_flag
= REF_NORMAL
;
800 fn_size
-= this -> ofs
+ this -> size
- fn_ofs
;
801 fn_ofs
= this -> ofs
+ this -> size
;
802 dbg_fragtree2 ( "now considering %#04x-%#04x \n " , fn_ofs
, fn_ofs
+ fn_size
);
804 new_this
= rb_entry ( rb_next (& this -> rb
), struct jffs2_node_frag
, rb
);
807 * There is no next fragment. Add the rest of
808 * the new node as the right-hand child.
811 err
= check_node ( c
, f
, tn
);
812 if ( unlikely ( err
!= 0 ))
818 newfrag
= new_fragment ( fn
, fn_ofs
, fn_size
);
819 if ( unlikely (! newfrag
))
822 dbg_fragtree2 ( "there are no more fragments, insert %#04x-%#04x \n " ,
823 newfrag
-> ofs
, newfrag
-> ofs
+ newfrag
-> size
);
824 rb_link_node (& newfrag
-> rb
, & this -> rb
, & this -> rb
. rb_right
);
825 rb_insert_color (& newfrag
-> rb
, root
);
829 dbg_fragtree2 ( "switch to the next 'this' fragment: %#04x-%#04x %s \n " ,
830 this -> ofs
, this -> ofs
+ this -> size
, this -> node
? "(data)" : "(hole)" );
836 BUG_ON ( fn
-> size
< PAGE_CACHE_SIZE
&& ref_flag
== REF_PRISTINE
);
838 if ( ref_flag
== REF_OBSOLETE
) {
839 dbg_fragtree2 ( "the node is obsolete now \n " );
840 /* jffs2_mark_node_obsolete() will adjust space accounting */
841 jffs2_mark_node_obsolete ( c
, fn
-> raw
);
845 dbg_fragtree2 ( "the node is \" %s \" now \n " , ref_flag
== REF_NORMAL
? "REF_NORMAL" : "REF_PRISTINE" );
847 /* Space accounting was adjusted at check_node_data() */
848 spin_lock (& c
-> erase_completion_lock
);
849 fn
-> raw
-> flash_offset
= ref_offset ( fn
-> raw
) | ref_flag
;
850 spin_unlock (& c
-> erase_completion_lock
);
855 void jffs2_set_inocache_state ( struct jffs2_sb_info
* c
, struct jffs2_inode_cache
* ic
, int state
)
857 spin_lock (& c
-> inocache_lock
);
859 wake_up (& c
-> inocache_wq
);
860 spin_unlock (& c
-> inocache_lock
);
863 /* During mount, this needs no locking. During normal operation, its
864 callers want to do other stuff while still holding the inocache_lock.
865 Rather than introducing special case get_ino_cache functions or
866 callbacks, we just let the caller do the locking itself. */
868 struct jffs2_inode_cache
* jffs2_get_ino_cache ( struct jffs2_sb_info
* c
, uint32_t ino
)
870 struct jffs2_inode_cache
* ret
;
872 ret
= c
-> inocache_list
[ ino
% INOCACHE_HASHSIZE
];
873 while ( ret
&& ret
-> ino
< ino
) {
877 if ( ret
&& ret
-> ino
!= ino
)
883 void jffs2_add_ino_cache ( struct jffs2_sb_info
* c
, struct jffs2_inode_cache
* new )
885 struct jffs2_inode_cache
** prev
;
887 spin_lock (& c
-> inocache_lock
);
889 new -> ino
= ++ c
-> highest_ino
;
891 dbg_inocache ( "add %p (ino #%u) \n " , new , new -> ino
);
893 prev
= & c
-> inocache_list
[ new -> ino
% INOCACHE_HASHSIZE
];
895 while ((* prev
) && (* prev
)-> ino
< new -> ino
) {
896 prev
= &(* prev
)-> next
;
901 spin_unlock (& c
-> inocache_lock
);
904 void jffs2_del_ino_cache ( struct jffs2_sb_info
* c
, struct jffs2_inode_cache
* old
)
906 struct jffs2_inode_cache
** prev
;
908 dbg_inocache ( "del %p (ino #%u) \n " , old
, old
-> ino
);
909 spin_lock (& c
-> inocache_lock
);
911 prev
= & c
-> inocache_list
[ old
-> ino
% INOCACHE_HASHSIZE
];
913 while ((* prev
) && (* prev
)-> ino
< old
-> ino
) {
914 prev
= &(* prev
)-> next
;
916 if ((* prev
) == old
) {
920 /* Free it now unless it's in READING or CLEARING state, which
921 are the transitions upon read_inode() and clear_inode(). The
922 rest of the time we know nobody else is looking at it, and
923 if it's held by read_inode() or clear_inode() they'll free it
925 if ( old
-> state
!= INO_STATE_READING
&& old
-> state
!= INO_STATE_CLEARING
)
926 jffs2_free_inode_cache ( old
);
928 spin_unlock (& c
-> inocache_lock
);
931 void jffs2_free_ino_caches ( struct jffs2_sb_info
* c
)
934 struct jffs2_inode_cache
* this , * next
;
936 for ( i
= 0 ; i
< INOCACHE_HASHSIZE
; i
++) {
937 this = c
-> inocache_list
[ i
];
940 jffs2_free_inode_cache ( this );
943 c
-> inocache_list
[ i
] = NULL
;
947 void jffs2_free_raw_node_refs ( struct jffs2_sb_info
* c
)
950 struct jffs2_raw_node_ref
* this , * next
;
952 for ( i
= 0 ; i
< c
-> nr_blocks
; i
++) {
953 this = c
-> blocks
[ i
]. first_node
;
955 next
= this -> next_phys
;
956 jffs2_free_raw_node_ref ( this );
959 c
-> blocks
[ i
]. first_node
= c
-> blocks
[ i
]. last_node
= NULL
;
963 struct jffs2_node_frag
* jffs2_lookup_node_frag ( struct rb_root
* fragtree
, uint32_t offset
)
965 /* The common case in lookup is that there will be a node
966 which precisely matches. So we go looking for that first */
967 struct rb_node
* next
;
968 struct jffs2_node_frag
* prev
= NULL
;
969 struct jffs2_node_frag
* frag
= NULL
;
971 dbg_fragtree2 ( "root %p, offset %d \n " , fragtree
, offset
);
973 next
= fragtree
-> rb_node
;
976 frag
= rb_entry ( next
, struct jffs2_node_frag
, rb
);
978 if ( frag
-> ofs
+ frag
-> size
<= offset
) {
979 /* Remember the closest smaller match on the way down */
980 if (! prev
|| frag
-> ofs
> prev
-> ofs
)
982 next
= frag
-> rb
. rb_right
;
983 } else if ( frag
-> ofs
> offset
) {
984 next
= frag
-> rb
. rb_left
;
990 /* Exact match not found. Go back up looking at each parent,
991 and return the closest smaller one */
994 dbg_fragtree2 ( "no match. Returning frag %#04x-%#04x, closest previous \n " ,
995 prev
-> ofs
, prev
-> ofs
+ prev
-> size
);
997 dbg_fragtree2 ( "returning NULL, empty fragtree \n " );
1002 /* Pass 'c' argument to indicate that nodes should be marked obsolete as
1004 void jffs2_kill_fragtree ( struct rb_root
* root
, struct jffs2_sb_info
* c
)
1006 struct jffs2_node_frag
* frag
;
1007 struct jffs2_node_frag
* parent
;
1012 dbg_fragtree ( "killing \n " );
1014 frag
= ( rb_entry ( root
-> rb_node
, struct jffs2_node_frag
, rb
));
1016 if ( frag
-> rb
. rb_left
) {
1017 frag
= frag_left ( frag
);
1020 if ( frag
-> rb
. rb_right
) {
1021 frag
= frag_right ( frag
);
1025 if ( frag
-> node
&& !(-- frag
-> node
-> frags
)) {
1026 /* Not a hole, and it's the final remaining frag
1027 of this node. Free the node */
1029 jffs2_mark_node_obsolete ( c
, frag
-> node
-> raw
);
1031 jffs2_free_full_dnode ( frag
-> node
);
1033 parent
= frag_parent ( frag
);
1035 if ( frag_left ( parent
) == frag
)
1036 parent
-> rb
. rb_left
= NULL
;
1038 parent
-> rb
. rb_right
= NULL
;
1041 jffs2_free_node_frag ( frag
);