2 * JFFS -- Journaling Flash File System, Linux implementation.
4 * Copyright (C) 1999, 2000 Axis Communications AB.
6 * Created by Finn Hakansson <finn@axis.com>.
8 * This is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
13 * $Id: jffs_fm.c,v 1.27 2001/09/20 12:29:47 dwmw2 Exp $
15 * Ported to Linux 2.3.x and MTD:
16 * Copyright (C) 2000 Alexander Larsson (alex@cendio.se), Cendio Systems AB
19 #include <linux/slab.h>
20 #include <linux/blkdev.h>
21 #include <linux/jffs.h>
24 #if defined(JFFS_MARK_OBSOLETE) && JFFS_MARK_OBSOLETE
25 static int jffs_mark_obsolete(struct jffs_fmcontrol
*fmc
, __u32 fm_offset
);
28 static struct jffs_fm
*jffs_alloc_fm(void);
29 static void jffs_free_fm(struct jffs_fm
*n
);
31 extern kmem_cache_t
*fm_cache
;
32 extern kmem_cache_t
*node_cache
;
34 #if CONFIG_JFFS_FS_VERBOSE > 0
36 jffs_print_fmcontrol(struct jffs_fmcontrol
*fmc
)
38 D(printk("struct jffs_fmcontrol: 0x%p\n", fmc
));
40 D(printk(" %u, /* flash_size */\n", fmc
->flash_size
));
41 D(printk(" %u, /* used_size */\n", fmc
->used_size
));
42 D(printk(" %u, /* dirty_size */\n", fmc
->dirty_size
));
43 D(printk(" %u, /* free_size */\n", fmc
->free_size
));
44 D(printk(" %u, /* sector_size */\n", fmc
->sector_size
));
45 D(printk(" %u, /* min_free_size */\n", fmc
->min_free_size
));
46 D(printk(" %u, /* max_chunk_size */\n", fmc
->max_chunk_size
));
47 D(printk(" 0x%p, /* mtd */\n", fmc
->mtd
));
48 D(printk(" 0x%p, /* head */ "
49 "(head->offset = 0x%08x)\n",
50 fmc
->head
, (fmc
->head
? fmc
->head
->offset
: 0)));
51 D(printk(" 0x%p, /* tail */ "
52 "(tail->offset + tail->size = 0x%08x)\n",
54 (fmc
->tail
? fmc
->tail
->offset
+ fmc
->tail
->size
: 0)));
55 D(printk(" 0x%p, /* head_extra */\n", fmc
->head_extra
));
56 D(printk(" 0x%p, /* tail_extra */\n", fmc
->tail_extra
));
59 #endif /* CONFIG_JFFS_FS_VERBOSE > 0 */
61 #if CONFIG_JFFS_FS_VERBOSE > 2
63 jffs_print_fm(struct jffs_fm
*fm
)
65 D(printk("struct jffs_fm: 0x%p\n", fm
));
67 D(printk(" 0x%08x, /* offset */\n", fm
->offset
));
68 D(printk(" %u, /* size */\n", fm
->size
));
69 D(printk(" 0x%p, /* prev */\n", fm
->prev
));
70 D(printk(" 0x%p, /* next */\n", fm
->next
));
71 D(printk(" 0x%p, /* nodes */\n", fm
->nodes
));
74 #endif /* CONFIG_JFFS_FS_VERBOSE > 2 */
78 jffs_print_node_ref(struct jffs_node_ref
*ref
)
80 D(printk("struct jffs_node_ref: 0x%p\n", ref
));
82 D(printk(" 0x%p, /* node */\n", ref
->node
));
83 D(printk(" 0x%p, /* next */\n", ref
->next
));
88 /* This function creates a new shiny flash memory control structure. */
89 struct jffs_fmcontrol
*
90 jffs_build_begin(struct jffs_control
*c
, int unit
)
92 struct jffs_fmcontrol
*fmc
;
95 D3(printk("jffs_build_begin()\n"));
96 fmc
= (struct jffs_fmcontrol
*)kmalloc(sizeof(struct jffs_fmcontrol
),
99 D(printk("jffs_build_begin(): Allocation of "
100 "struct jffs_fmcontrol failed!\n"));
101 return (struct jffs_fmcontrol
*)0;
103 DJM(no_jffs_fmcontrol
++);
105 mtd
= get_mtd_device(NULL
, unit
);
109 DJM(no_jffs_fmcontrol
--);
113 /* Retrieve the size of the flash memory. */
114 fmc
->flash_size
= mtd
->size
;
115 D3(printk(" fmc->flash_size = %d bytes\n", fmc
->flash_size
));
119 fmc
->free_size
= mtd
->size
;
120 fmc
->sector_size
= mtd
->erasesize
;
121 fmc
->max_chunk_size
= fmc
->sector_size
>> 1;
124 + 1 x max_chunk_size, for when a nodes overlaps the end of a sector
125 + 1 x max_chunk_size again, which ought to be enough to handle
126 the case where a rename causes a name to grow, and GC has
127 to write out larger nodes than the ones it's obsoleting.
128 We should fix it so it doesn't have to write the name
130 + another 2 sectors because people keep getting GC stuck and
131 we don't know why. This scares me - I want formal proof
132 of correctness of whatever number we put here. dwmw2.
134 fmc
->min_free_size
= fmc
->sector_size
<< 2;
139 fmc
->head_extra
= NULL
;
140 fmc
->tail_extra
= NULL
;
141 init_MUTEX(&fmc
->biglock
);
146 /* When the flash memory scan has completed, this function should be called
147 before use of the control structure. */
149 jffs_build_end(struct jffs_fmcontrol
*fmc
)
151 D3(printk("jffs_build_end()\n"));
154 fmc
->head
= fmc
->head_extra
;
155 fmc
->tail
= fmc
->tail_extra
;
157 else if (fmc
->head_extra
) {
158 fmc
->tail_extra
->next
= fmc
->head
;
159 fmc
->head
->prev
= fmc
->tail_extra
;
160 fmc
->head
= fmc
->head_extra
;
162 fmc
->head_extra
= NULL
; /* These two instructions should be omitted. */
163 fmc
->tail_extra
= NULL
;
164 D3(jffs_print_fmcontrol(fmc
));
168 /* Call this function when the file system is unmounted. This function
169 frees all memory used by this module. */
171 jffs_cleanup_fmcontrol(struct jffs_fmcontrol
*fmc
)
174 struct jffs_fm
*next
= fmc
->head
;
176 struct jffs_fm
*cur
= next
;
180 put_mtd_device(fmc
->mtd
);
182 DJM(no_jffs_fmcontrol
--);
187 /* This function returns the size of the first chunk of free space on the
188 flash memory. This function will return something nonzero if the flash
189 memory contains any free space. */
191 jffs_free_size1(struct jffs_fmcontrol
*fmc
)
195 __u32 end
= fmc
->flash_size
;
198 /* There is nothing on the flash. */
199 return fmc
->flash_size
;
202 /* Compute the beginning and ending of the contents of the flash. */
203 head
= fmc
->head
->offset
;
204 tail
= fmc
->tail
->offset
+ fmc
->tail
->size
;
208 ASSERT(else if (tail
> end
) {
209 printk(KERN_WARNING
"jffs_free_size1(): tail > end\n");
221 /* This function will return something nonzero in case there are two free
222 areas on the flash. Like this:
224 +----------------+------------------+----------------+
225 | FREE 1 | USED / DIRTY | FREE 2 |
226 +----------------+------------------+----------------+
228 fmc->tail ------------------------^
230 The value returned, will be the size of the first empty area on the
231 flash, in this case marked "FREE 1". */
233 jffs_free_size2(struct jffs_fmcontrol
*fmc
)
236 __u32 head
= fmc
->head
->offset
;
237 __u32 tail
= fmc
->tail
->offset
+ fmc
->tail
->size
;
238 if (tail
== fmc
->flash_size
) {
250 /* Allocate a chunk of flash memory. If there is enough space on the
251 device, a reference to the associated node is stored in the jffs_fm
254 jffs_fmalloc(struct jffs_fmcontrol
*fmc
, __u32 size
, struct jffs_node
*node
,
255 struct jffs_fm
**result
)
258 __u32 free_chunk_size1
;
259 __u32 free_chunk_size2
;
261 D2(printk("jffs_fmalloc(): fmc = 0x%p, size = %d, "
262 "node = 0x%p\n", fmc
, size
, node
));
266 if (!(fm
= jffs_alloc_fm())) {
267 D(printk("jffs_fmalloc(): kmalloc() failed! (fm)\n"));
271 free_chunk_size1
= jffs_free_size1(fmc
);
272 free_chunk_size2
= jffs_free_size2(fmc
);
273 if (free_chunk_size1
+ free_chunk_size2
!= fmc
->free_size
) {
274 printk(KERN_WARNING
"Free size accounting screwed\n");
275 printk(KERN_WARNING
"free_chunk_size1 == 0x%x, free_chunk_size2 == 0x%x, fmc->free_size == 0x%x\n", free_chunk_size1
, free_chunk_size2
, fmc
->free_size
);
278 D3(printk("jffs_fmalloc(): free_chunk_size1 = %u, "
279 "free_chunk_size2 = %u\n",
280 free_chunk_size1
, free_chunk_size2
));
282 if (size
<= free_chunk_size1
) {
283 if (!(fm
->nodes
= (struct jffs_node_ref
*)
284 kmalloc(sizeof(struct jffs_node_ref
),
286 D(printk("jffs_fmalloc(): kmalloc() failed! "
291 DJM(no_jffs_node_ref
++);
292 fm
->nodes
->node
= node
;
293 fm
->nodes
->next
= NULL
;
295 fm
->offset
= fmc
->tail
->offset
+ fmc
->tail
->size
;
296 if (fm
->offset
== fmc
->flash_size
) {
299 ASSERT(else if (fm
->offset
> fmc
->flash_size
) {
300 printk(KERN_WARNING
"jffs_fmalloc(): "
301 "offset > flash_end\n");
306 /* There don't have to be files in the file
311 fmc
->free_size
-= size
;
312 fmc
->used_size
+= size
;
314 else if (size
> free_chunk_size2
) {
315 printk(KERN_WARNING
"JFFS: Tried to allocate a too "
316 "large flash memory chunk. (size = %u)\n", size
);
321 fm
->offset
= fmc
->tail
->offset
+ fmc
->tail
->size
;
322 fm
->size
= free_chunk_size1
;
324 fmc
->free_size
-= fm
->size
;
325 fmc
->dirty_size
+= fm
->size
; /* Changed by simonk. This seemingly fixes a
326 bug that caused infinite garbage collection.
327 It previously set fmc->dirty_size to size (which is the
328 size of the requested chunk).
339 fm
->prev
= fmc
->tail
;
340 fmc
->tail
->next
= fm
;
344 D3(jffs_print_fmcontrol(fmc
));
345 D3(jffs_print_fm(fm
));
351 /* The on-flash space is not needed anymore by the passed node. Remove
352 the reference to the node from the node list. If the data chunk in
353 the flash memory isn't used by any more nodes anymore (fm->nodes == 0),
354 then mark that chunk as dirty. */
356 jffs_fmfree(struct jffs_fmcontrol
*fmc
, struct jffs_fm
*fm
, struct jffs_node
*node
)
358 struct jffs_node_ref
*ref
;
359 struct jffs_node_ref
*prev
;
362 D2(printk("jffs_fmfree(): node->ino = %u, node->version = %u\n",
363 node
->ino
, node
->version
));
365 ASSERT(if (!fmc
|| !fm
|| !fm
->nodes
) {
366 printk(KERN_ERR
"jffs_fmfree(): fmc: 0x%p, fm: 0x%p, "
368 fmc
, fm
, (fm
? fm
->nodes
: NULL
));
372 /* Find the reference to the node that is going to be removed
374 for (ref
= fm
->nodes
, prev
= NULL
; ref
; ref
= ref
->next
) {
375 if (ref
->node
== node
) {
377 prev
->next
= ref
->next
;
380 fm
->nodes
= ref
->next
;
383 DJM(no_jffs_node_ref
--);
390 /* If the data chunk in the flash memory isn't used anymore
391 just mark it as obsolete. */
393 /* No node uses this chunk so let's remove it. */
394 fmc
->used_size
-= fm
->size
;
395 fmc
->dirty_size
+= fm
->size
;
396 #if defined(JFFS_MARK_OBSOLETE) && JFFS_MARK_OBSOLETE
397 if (jffs_mark_obsolete(fmc
, fm
->offset
) < 0) {
398 D1(printk("jffs_fmfree(): Failed to mark an on-flash "
399 "node obsolete!\n"));
406 printk(KERN_WARNING
"***jffs_fmfree(): "
407 "Didn't delete any node reference!\n");
414 /* This allocation function is used during the initialization of
417 jffs_fmalloced(struct jffs_fmcontrol
*fmc
, __u32 offset
, __u32 size
,
418 struct jffs_node
*node
)
422 D3(printk("jffs_fmalloced()\n"));
424 if (!(fm
= jffs_alloc_fm())) {
425 D(printk("jffs_fmalloced(0x%p, %u, %u, 0x%p): failed!\n",
426 fmc
, offset
, size
, node
));
435 /* `node' exists and it should be associated with the
436 jffs_fm structure `fm'. */
437 if (!(fm
->nodes
= (struct jffs_node_ref
*)
438 kmalloc(sizeof(struct jffs_node_ref
),
440 D(printk("jffs_fmalloced(): !fm->nodes\n"));
444 DJM(no_jffs_node_ref
++);
445 fm
->nodes
->node
= node
;
446 fm
->nodes
->next
= NULL
;
447 fmc
->used_size
+= size
;
448 fmc
->free_size
-= size
;
451 /* If there is no node, then this is just a chunk of dirt. */
452 fmc
->dirty_size
+= size
;
453 fmc
->free_size
-= size
;
456 if (fmc
->head_extra
) {
457 fm
->prev
= fmc
->tail_extra
;
458 fmc
->tail_extra
->next
= fm
;
459 fmc
->tail_extra
= fm
;
461 else if (!fmc
->head
) {
465 else if (fmc
->tail
->offset
+ fmc
->tail
->size
< offset
) {
466 fmc
->head_extra
= fm
;
467 fmc
->tail_extra
= fm
;
470 fm
->prev
= fmc
->tail
;
471 fmc
->tail
->next
= fm
;
474 D3(jffs_print_fmcontrol(fmc
));
475 D3(jffs_print_fm(fm
));
480 /* Add a new node to an already existing jffs_fm struct. */
482 jffs_add_node(struct jffs_node
*node
)
484 struct jffs_node_ref
*ref
;
486 D3(printk("jffs_add_node(): ino = %u\n", node
->ino
));
488 ref
= (struct jffs_node_ref
*)kmalloc(sizeof(struct jffs_node_ref
),
493 DJM(no_jffs_node_ref
++);
495 ref
->next
= node
->fm
->nodes
;
496 node
->fm
->nodes
= ref
;
501 /* Free a part of some allocated space. */
503 jffs_fmfree_partly(struct jffs_fmcontrol
*fmc
, struct jffs_fm
*fm
, __u32 size
)
505 D1(printk("***jffs_fmfree_partly(): fm = 0x%p, fm->nodes = 0x%p, "
506 "fm->nodes->node->ino = %u, size = %u\n",
507 fm
, (fm
? fm
->nodes
: 0),
508 (!fm
? 0 : (!fm
->nodes
? 0 : fm
->nodes
->node
->ino
)), size
));
512 DJM(no_jffs_node_ref
--);
515 fmc
->used_size
-= fm
->size
;
516 if (fm
== fmc
->tail
) {
518 fmc
->free_size
+= size
;
520 fmc
->dirty_size
+= fm
->size
;
524 /* Find the jffs_fm struct that contains the end of the data chunk that
525 begins at the logical beginning of the flash memory and spans `size'
526 bytes. If we want to erase a sector of the flash memory, we use this
527 function to find where the sector limit cuts a chunk of data. */
529 jffs_cut_node(struct jffs_fmcontrol
*fmc
, __u32 size
)
539 printk(KERN_ERR
"jffs_cut_node(): fmc == NULL\n");
550 else if (pos
> size
) {
563 /* Move the head of the fmc structures and delete the obsolete parts. */
565 jffs_sync_erase(struct jffs_fmcontrol
*fmc
, int erased_size
)
571 printk(KERN_ERR
"jffs_sync_erase(): fmc == NULL\n");
575 fmc
->dirty_size
-= erased_size
;
576 fmc
->free_size
+= erased_size
;
578 for (fm
= fmc
->head
; fm
&& (erased_size
> 0);) {
579 if (erased_size
>= fm
->size
) {
580 erased_size
-= fm
->size
;
588 fm
->size
-= erased_size
;
589 fm
->offset
+= erased_size
;
596 /* Return the oldest used node in the flash memory. */
598 jffs_get_oldest_node(struct jffs_fmcontrol
*fmc
)
601 struct jffs_node_ref
*nref
;
602 struct jffs_node
*node
= NULL
;
605 printk(KERN_ERR
"jffs_get_oldest_node(): fmc == NULL\n");
609 for (fm
= fmc
->head
; fm
&& !fm
->nodes
; fm
= fm
->next
);
615 /* The oldest node is the last one in the reference list. This list
616 shouldn't be too long; just one or perhaps two elements. */
617 for (nref
= fm
->nodes
; nref
; nref
= nref
->next
) {
621 D2(printk("jffs_get_oldest_node(): ino = %u, version = %u\n",
622 (node
? node
->ino
: 0), (node
? node
->version
: 0)));
628 #if defined(JFFS_MARK_OBSOLETE) && JFFS_MARK_OBSOLETE
630 /* Mark an on-flash node as obsolete.
632 Note that this is just an optimization that isn't necessary for the
633 filesystem to work. */
636 jffs_mark_obsolete(struct jffs_fmcontrol
*fmc
, __u32 fm_offset
)
638 /* The `accurate_pos' holds the position of the accurate byte
639 in the jffs_raw_inode structure that we are going to mark
641 __u32 accurate_pos
= fm_offset
+ JFFS_RAW_INODE_ACCURATE_OFFSET
;
642 unsigned char zero
= 0x00;
645 D3(printk("jffs_mark_obsolete(): accurate_pos = %u\n", accurate_pos
));
647 printk(KERN_ERR
"jffs_mark_obsolete(): fmc == NULL\n");
651 /* Write 0x00 to the raw inode's accurate member. Don't care
652 about the return value. */
653 MTD_WRITE(fmc
->mtd
, accurate_pos
, 1, &len
, &zero
);
657 #endif /* JFFS_MARK_OBSOLETE */
659 /* check if it's possible to erase the wanted range, and if not, return
660 * the range that IS erasable, or a negative error code.
663 jffs_flash_erasable_size(struct mtd_info
*mtd
, __u32 offset
, __u32 size
)
667 /* assume that sector size for a partition is constant even
668 * if it spans more than one chip (you usually put the same
669 * type of chips in a system)
672 ssize
= mtd
->erasesize
;
674 if (offset
% ssize
) {
675 printk(KERN_WARNING
"jffs_flash_erasable_size() given non-aligned offset %x (erasesize %lx)\n", offset
, ssize
);
676 /* The offset is not sector size aligned. */
679 else if (offset
> mtd
->size
) {
680 printk(KERN_WARNING
"jffs_flash_erasable_size given offset off the end of device (%x > %x)\n", offset
, mtd
->size
);
683 else if (offset
+ size
> mtd
->size
) {
684 printk(KERN_WARNING
"jffs_flash_erasable_size() given length which runs off the end of device (ofs %x + len %x = %x, > %x)\n", offset
,size
, offset
+size
, mtd
->size
);
688 return (size
/ ssize
) * ssize
;
692 /* How much dirty flash memory is possible to erase at the moment? */
694 jffs_erasable_size(struct jffs_fmcontrol
*fmc
)
701 printk(KERN_ERR
"jffs_erasable_size(): fmc = NULL\n");
706 /* The flash memory is totally empty. No nodes. No dirt.
711 /* Calculate how much space that is dirty. */
712 for (fm
= fmc
->head
; fm
&& !fm
->nodes
; fm
= fm
->next
) {
713 if (size
&& fm
->offset
== 0) {
714 /* We have reached the beginning of the flash. */
720 /* Someone's signature contained this:
721 There's a fine line between fishing and just standing on
722 the shore like an idiot... */
723 ret
= jffs_flash_erasable_size(fmc
->mtd
, fmc
->head
->offset
, size
);
725 ASSERT(if (ret
< 0) {
726 printk("jffs_erasable_size: flash_erasable_size() "
727 "returned something less than zero (%ld).\n", ret
);
728 printk("jffs_erasable_size: offset = 0x%08x\n",
732 /* If there is dirt on the flash (which is the reason to why
733 this function was called in the first place) but no space is
734 possible to erase right now, the initial part of the list of
735 jffs_fm structs, that hold place for dirty space, could perhaps
736 be shortened. The list's initial "dirty" elements are merged
737 into just one large dirty jffs_fm struct. This operation must
738 only be performed if nothing is possible to erase. Otherwise,
739 jffs_clear_end_of_node() won't work as expected. */
741 struct jffs_fm
*head
= fmc
->head
;
743 /* While there are two dirty nodes beside each other.*/
744 while (head
->nodes
== 0
746 && head
->next
->nodes
== 0) {
748 head
->size
+= del
->size
;
749 head
->next
= del
->next
;
751 del
->next
->prev
= head
;
757 return (ret
>= 0 ? ret
: 0);
760 static struct jffs_fm
*jffs_alloc_fm(void)
764 fm
= kmem_cache_alloc(fm_cache
,GFP_KERNEL
);
765 DJM(if (fm
) no_jffs_fm
++;);
770 static void jffs_free_fm(struct jffs_fm
*n
)
772 kmem_cache_free(fm_cache
,n
);
778 struct jffs_node
*jffs_alloc_node(void)
782 n
= (struct jffs_node
*)kmem_cache_alloc(node_cache
,GFP_KERNEL
);
788 void jffs_free_node(struct jffs_node
*n
)
790 kmem_cache_free(node_cache
,n
);
795 int jffs_get_node_inuse(void)