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>
25 #if defined(JFFS_MARK_OBSOLETE) && JFFS_MARK_OBSOLETE
26 static int jffs_mark_obsolete(struct jffs_fmcontrol
*fmc
, __u32 fm_offset
);
29 static struct jffs_fm
*jffs_alloc_fm(void);
30 static void jffs_free_fm(struct jffs_fm
*n
);
32 extern kmem_cache_t
*fm_cache
;
33 extern kmem_cache_t
*node_cache
;
35 #if CONFIG_JFFS_FS_VERBOSE > 0
37 jffs_print_fmcontrol(struct jffs_fmcontrol
*fmc
)
39 D(printk("struct jffs_fmcontrol: 0x%p\n", fmc
));
41 D(printk(" %u, /* flash_size */\n", fmc
->flash_size
));
42 D(printk(" %u, /* used_size */\n", fmc
->used_size
));
43 D(printk(" %u, /* dirty_size */\n", fmc
->dirty_size
));
44 D(printk(" %u, /* free_size */\n", fmc
->free_size
));
45 D(printk(" %u, /* sector_size */\n", fmc
->sector_size
));
46 D(printk(" %u, /* min_free_size */\n", fmc
->min_free_size
));
47 D(printk(" %u, /* max_chunk_size */\n", fmc
->max_chunk_size
));
48 D(printk(" 0x%p, /* mtd */\n", fmc
->mtd
));
49 D(printk(" 0x%p, /* head */ "
50 "(head->offset = 0x%08x)\n",
51 fmc
->head
, (fmc
->head
? fmc
->head
->offset
: 0)));
52 D(printk(" 0x%p, /* tail */ "
53 "(tail->offset + tail->size = 0x%08x)\n",
55 (fmc
->tail
? fmc
->tail
->offset
+ fmc
->tail
->size
: 0)));
56 D(printk(" 0x%p, /* head_extra */\n", fmc
->head_extra
));
57 D(printk(" 0x%p, /* tail_extra */\n", fmc
->tail_extra
));
60 #endif /* CONFIG_JFFS_FS_VERBOSE > 0 */
62 #if CONFIG_JFFS_FS_VERBOSE > 2
64 jffs_print_fm(struct jffs_fm
*fm
)
66 D(printk("struct jffs_fm: 0x%p\n", fm
));
68 D(printk(" 0x%08x, /* offset */\n", fm
->offset
));
69 D(printk(" %u, /* size */\n", fm
->size
));
70 D(printk(" 0x%p, /* prev */\n", fm
->prev
));
71 D(printk(" 0x%p, /* next */\n", fm
->next
));
72 D(printk(" 0x%p, /* nodes */\n", fm
->nodes
));
75 #endif /* CONFIG_JFFS_FS_VERBOSE > 2 */
79 jffs_print_node_ref(struct jffs_node_ref
*ref
)
81 D(printk("struct jffs_node_ref: 0x%p\n", ref
));
83 D(printk(" 0x%p, /* node */\n", ref
->node
));
84 D(printk(" 0x%p, /* next */\n", ref
->next
));
89 /* This function creates a new shiny flash memory control structure. */
90 struct jffs_fmcontrol
*
91 jffs_build_begin(struct jffs_control
*c
, int unit
)
93 struct jffs_fmcontrol
*fmc
;
96 D3(printk("jffs_build_begin()\n"));
97 fmc
= (struct jffs_fmcontrol
*)kmalloc(sizeof(struct jffs_fmcontrol
),
100 D(printk("jffs_build_begin(): Allocation of "
101 "struct jffs_fmcontrol failed!\n"));
102 return (struct jffs_fmcontrol
*)0;
104 DJM(no_jffs_fmcontrol
++);
106 mtd
= get_mtd_device(NULL
, unit
);
110 DJM(no_jffs_fmcontrol
--);
114 /* Retrieve the size of the flash memory. */
115 fmc
->flash_size
= mtd
->size
;
116 D3(printk(" fmc->flash_size = %d bytes\n", fmc
->flash_size
));
120 fmc
->free_size
= mtd
->size
;
121 fmc
->sector_size
= mtd
->erasesize
;
122 fmc
->max_chunk_size
= fmc
->sector_size
>> 1;
125 + 1 x max_chunk_size, for when a nodes overlaps the end of a sector
126 + 1 x max_chunk_size again, which ought to be enough to handle
127 the case where a rename causes a name to grow, and GC has
128 to write out larger nodes than the ones it's obsoleting.
129 We should fix it so it doesn't have to write the name
131 + another 2 sectors because people keep getting GC stuck and
132 we don't know why. This scares me - I want formal proof
133 of correctness of whatever number we put here. dwmw2.
135 fmc
->min_free_size
= fmc
->sector_size
<< 2;
140 fmc
->head_extra
= NULL
;
141 fmc
->tail_extra
= NULL
;
142 mutex_init(&fmc
->biglock
);
147 /* When the flash memory scan has completed, this function should be called
148 before use of the control structure. */
150 jffs_build_end(struct jffs_fmcontrol
*fmc
)
152 D3(printk("jffs_build_end()\n"));
155 fmc
->head
= fmc
->head_extra
;
156 fmc
->tail
= fmc
->tail_extra
;
158 else if (fmc
->head_extra
) {
159 fmc
->tail_extra
->next
= fmc
->head
;
160 fmc
->head
->prev
= fmc
->tail_extra
;
161 fmc
->head
= fmc
->head_extra
;
163 fmc
->head_extra
= NULL
; /* These two instructions should be omitted. */
164 fmc
->tail_extra
= NULL
;
165 D3(jffs_print_fmcontrol(fmc
));
169 /* Call this function when the file system is unmounted. This function
170 frees all memory used by this module. */
172 jffs_cleanup_fmcontrol(struct jffs_fmcontrol
*fmc
)
175 struct jffs_fm
*next
= fmc
->head
;
177 struct jffs_fm
*cur
= next
;
181 put_mtd_device(fmc
->mtd
);
183 DJM(no_jffs_fmcontrol
--);
188 /* This function returns the size of the first chunk of free space on the
189 flash memory. This function will return something nonzero if the flash
190 memory contains any free space. */
192 jffs_free_size1(struct jffs_fmcontrol
*fmc
)
196 __u32 end
= fmc
->flash_size
;
199 /* There is nothing on the flash. */
200 return fmc
->flash_size
;
203 /* Compute the beginning and ending of the contents of the flash. */
204 head
= fmc
->head
->offset
;
205 tail
= fmc
->tail
->offset
+ fmc
->tail
->size
;
209 ASSERT(else if (tail
> end
) {
210 printk(KERN_WARNING
"jffs_free_size1(): tail > end\n");
222 /* This function will return something nonzero in case there are two free
223 areas on the flash. Like this:
225 +----------------+------------------+----------------+
226 | FREE 1 | USED / DIRTY | FREE 2 |
227 +----------------+------------------+----------------+
229 fmc->tail ------------------------^
231 The value returned, will be the size of the first empty area on the
232 flash, in this case marked "FREE 1". */
234 jffs_free_size2(struct jffs_fmcontrol
*fmc
)
237 __u32 head
= fmc
->head
->offset
;
238 __u32 tail
= fmc
->tail
->offset
+ fmc
->tail
->size
;
239 if (tail
== fmc
->flash_size
) {
251 /* Allocate a chunk of flash memory. If there is enough space on the
252 device, a reference to the associated node is stored in the jffs_fm
255 jffs_fmalloc(struct jffs_fmcontrol
*fmc
, __u32 size
, struct jffs_node
*node
,
256 struct jffs_fm
**result
)
259 __u32 free_chunk_size1
;
260 __u32 free_chunk_size2
;
262 D2(printk("jffs_fmalloc(): fmc = 0x%p, size = %d, "
263 "node = 0x%p\n", fmc
, size
, node
));
267 if (!(fm
= jffs_alloc_fm())) {
268 D(printk("jffs_fmalloc(): kmalloc() failed! (fm)\n"));
272 free_chunk_size1
= jffs_free_size1(fmc
);
273 free_chunk_size2
= jffs_free_size2(fmc
);
274 if (free_chunk_size1
+ free_chunk_size2
!= fmc
->free_size
) {
275 printk(KERN_WARNING
"Free size accounting screwed\n");
276 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
);
279 D3(printk("jffs_fmalloc(): free_chunk_size1 = %u, "
280 "free_chunk_size2 = %u\n",
281 free_chunk_size1
, free_chunk_size2
));
283 if (size
<= free_chunk_size1
) {
284 if (!(fm
->nodes
= (struct jffs_node_ref
*)
285 kmalloc(sizeof(struct jffs_node_ref
),
287 D(printk("jffs_fmalloc(): kmalloc() failed! "
292 DJM(no_jffs_node_ref
++);
293 fm
->nodes
->node
= node
;
294 fm
->nodes
->next
= NULL
;
296 fm
->offset
= fmc
->tail
->offset
+ fmc
->tail
->size
;
297 if (fm
->offset
== fmc
->flash_size
) {
300 ASSERT(else if (fm
->offset
> fmc
->flash_size
) {
301 printk(KERN_WARNING
"jffs_fmalloc(): "
302 "offset > flash_end\n");
307 /* There don't have to be files in the file
312 fmc
->free_size
-= size
;
313 fmc
->used_size
+= size
;
315 else if (size
> free_chunk_size2
) {
316 printk(KERN_WARNING
"JFFS: Tried to allocate a too "
317 "large flash memory chunk. (size = %u)\n", size
);
322 fm
->offset
= fmc
->tail
->offset
+ fmc
->tail
->size
;
323 fm
->size
= free_chunk_size1
;
325 fmc
->free_size
-= fm
->size
;
326 fmc
->dirty_size
+= fm
->size
; /* Changed by simonk. This seemingly fixes a
327 bug that caused infinite garbage collection.
328 It previously set fmc->dirty_size to size (which is the
329 size of the requested chunk).
340 fm
->prev
= fmc
->tail
;
341 fmc
->tail
->next
= fm
;
345 D3(jffs_print_fmcontrol(fmc
));
346 D3(jffs_print_fm(fm
));
352 /* The on-flash space is not needed anymore by the passed node. Remove
353 the reference to the node from the node list. If the data chunk in
354 the flash memory isn't used by any more nodes anymore (fm->nodes == 0),
355 then mark that chunk as dirty. */
357 jffs_fmfree(struct jffs_fmcontrol
*fmc
, struct jffs_fm
*fm
, struct jffs_node
*node
)
359 struct jffs_node_ref
*ref
;
360 struct jffs_node_ref
*prev
;
363 D2(printk("jffs_fmfree(): node->ino = %u, node->version = %u\n",
364 node
->ino
, node
->version
));
366 ASSERT(if (!fmc
|| !fm
|| !fm
->nodes
) {
367 printk(KERN_ERR
"jffs_fmfree(): fmc: 0x%p, fm: 0x%p, "
369 fmc
, fm
, (fm
? fm
->nodes
: NULL
));
373 /* Find the reference to the node that is going to be removed
375 for (ref
= fm
->nodes
, prev
= NULL
; ref
; ref
= ref
->next
) {
376 if (ref
->node
== node
) {
378 prev
->next
= ref
->next
;
381 fm
->nodes
= ref
->next
;
384 DJM(no_jffs_node_ref
--);
391 /* If the data chunk in the flash memory isn't used anymore
392 just mark it as obsolete. */
394 /* No node uses this chunk so let's remove it. */
395 fmc
->used_size
-= fm
->size
;
396 fmc
->dirty_size
+= fm
->size
;
397 #if defined(JFFS_MARK_OBSOLETE) && JFFS_MARK_OBSOLETE
398 if (jffs_mark_obsolete(fmc
, fm
->offset
) < 0) {
399 D1(printk("jffs_fmfree(): Failed to mark an on-flash "
400 "node obsolete!\n"));
407 printk(KERN_WARNING
"***jffs_fmfree(): "
408 "Didn't delete any node reference!\n");
415 /* This allocation function is used during the initialization of
418 jffs_fmalloced(struct jffs_fmcontrol
*fmc
, __u32 offset
, __u32 size
,
419 struct jffs_node
*node
)
423 D3(printk("jffs_fmalloced()\n"));
425 if (!(fm
= jffs_alloc_fm())) {
426 D(printk("jffs_fmalloced(0x%p, %u, %u, 0x%p): failed!\n",
427 fmc
, offset
, size
, node
));
436 /* `node' exists and it should be associated with the
437 jffs_fm structure `fm'. */
438 if (!(fm
->nodes
= (struct jffs_node_ref
*)
439 kmalloc(sizeof(struct jffs_node_ref
),
441 D(printk("jffs_fmalloced(): !fm->nodes\n"));
445 DJM(no_jffs_node_ref
++);
446 fm
->nodes
->node
= node
;
447 fm
->nodes
->next
= NULL
;
448 fmc
->used_size
+= size
;
449 fmc
->free_size
-= size
;
452 /* If there is no node, then this is just a chunk of dirt. */
453 fmc
->dirty_size
+= size
;
454 fmc
->free_size
-= size
;
457 if (fmc
->head_extra
) {
458 fm
->prev
= fmc
->tail_extra
;
459 fmc
->tail_extra
->next
= fm
;
460 fmc
->tail_extra
= fm
;
462 else if (!fmc
->head
) {
466 else if (fmc
->tail
->offset
+ fmc
->tail
->size
< offset
) {
467 fmc
->head_extra
= fm
;
468 fmc
->tail_extra
= fm
;
471 fm
->prev
= fmc
->tail
;
472 fmc
->tail
->next
= fm
;
475 D3(jffs_print_fmcontrol(fmc
));
476 D3(jffs_print_fm(fm
));
481 /* Add a new node to an already existing jffs_fm struct. */
483 jffs_add_node(struct jffs_node
*node
)
485 struct jffs_node_ref
*ref
;
487 D3(printk("jffs_add_node(): ino = %u\n", node
->ino
));
489 ref
= (struct jffs_node_ref
*)kmalloc(sizeof(struct jffs_node_ref
),
494 DJM(no_jffs_node_ref
++);
496 ref
->next
= node
->fm
->nodes
;
497 node
->fm
->nodes
= ref
;
502 /* Free a part of some allocated space. */
504 jffs_fmfree_partly(struct jffs_fmcontrol
*fmc
, struct jffs_fm
*fm
, __u32 size
)
506 D1(printk("***jffs_fmfree_partly(): fm = 0x%p, fm->nodes = 0x%p, "
507 "fm->nodes->node->ino = %u, size = %u\n",
508 fm
, (fm
? fm
->nodes
: 0),
509 (!fm
? 0 : (!fm
->nodes
? 0 : fm
->nodes
->node
->ino
)), size
));
513 DJM(no_jffs_node_ref
--);
516 fmc
->used_size
-= fm
->size
;
517 if (fm
== fmc
->tail
) {
519 fmc
->free_size
+= size
;
521 fmc
->dirty_size
+= fm
->size
;
525 /* Find the jffs_fm struct that contains the end of the data chunk that
526 begins at the logical beginning of the flash memory and spans `size'
527 bytes. If we want to erase a sector of the flash memory, we use this
528 function to find where the sector limit cuts a chunk of data. */
530 jffs_cut_node(struct jffs_fmcontrol
*fmc
, __u32 size
)
540 printk(KERN_ERR
"jffs_cut_node(): fmc == NULL\n");
551 else if (pos
> size
) {
564 /* Move the head of the fmc structures and delete the obsolete parts. */
566 jffs_sync_erase(struct jffs_fmcontrol
*fmc
, int erased_size
)
572 printk(KERN_ERR
"jffs_sync_erase(): fmc == NULL\n");
576 fmc
->dirty_size
-= erased_size
;
577 fmc
->free_size
+= erased_size
;
579 for (fm
= fmc
->head
; fm
&& (erased_size
> 0);) {
580 if (erased_size
>= fm
->size
) {
581 erased_size
-= fm
->size
;
589 fm
->size
-= erased_size
;
590 fm
->offset
+= erased_size
;
597 /* Return the oldest used node in the flash memory. */
599 jffs_get_oldest_node(struct jffs_fmcontrol
*fmc
)
602 struct jffs_node_ref
*nref
;
603 struct jffs_node
*node
= NULL
;
606 printk(KERN_ERR
"jffs_get_oldest_node(): fmc == NULL\n");
610 for (fm
= fmc
->head
; fm
&& !fm
->nodes
; fm
= fm
->next
);
616 /* The oldest node is the last one in the reference list. This list
617 shouldn't be too long; just one or perhaps two elements. */
618 for (nref
= fm
->nodes
; nref
; nref
= nref
->next
) {
622 D2(printk("jffs_get_oldest_node(): ino = %u, version = %u\n",
623 (node
? node
->ino
: 0), (node
? node
->version
: 0)));
629 #if defined(JFFS_MARK_OBSOLETE) && JFFS_MARK_OBSOLETE
631 /* Mark an on-flash node as obsolete.
633 Note that this is just an optimization that isn't necessary for the
634 filesystem to work. */
637 jffs_mark_obsolete(struct jffs_fmcontrol
*fmc
, __u32 fm_offset
)
639 /* The `accurate_pos' holds the position of the accurate byte
640 in the jffs_raw_inode structure that we are going to mark
642 __u32 accurate_pos
= fm_offset
+ JFFS_RAW_INODE_ACCURATE_OFFSET
;
643 unsigned char zero
= 0x00;
646 D3(printk("jffs_mark_obsolete(): accurate_pos = %u\n", accurate_pos
));
648 printk(KERN_ERR
"jffs_mark_obsolete(): fmc == NULL\n");
652 /* Write 0x00 to the raw inode's accurate member. Don't care
653 about the return value. */
654 MTD_WRITE(fmc
->mtd
, accurate_pos
, 1, &len
, &zero
);
658 #endif /* JFFS_MARK_OBSOLETE */
660 /* check if it's possible to erase the wanted range, and if not, return
661 * the range that IS erasable, or a negative error code.
664 jffs_flash_erasable_size(struct mtd_info
*mtd
, __u32 offset
, __u32 size
)
668 /* assume that sector size for a partition is constant even
669 * if it spans more than one chip (you usually put the same
670 * type of chips in a system)
673 ssize
= mtd
->erasesize
;
675 if (offset
% ssize
) {
676 printk(KERN_WARNING
"jffs_flash_erasable_size() given non-aligned offset %x (erasesize %lx)\n", offset
, ssize
);
677 /* The offset is not sector size aligned. */
680 else if (offset
> mtd
->size
) {
681 printk(KERN_WARNING
"jffs_flash_erasable_size given offset off the end of device (%x > %x)\n", offset
, mtd
->size
);
684 else if (offset
+ size
> mtd
->size
) {
685 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
);
689 return (size
/ ssize
) * ssize
;
693 /* How much dirty flash memory is possible to erase at the moment? */
695 jffs_erasable_size(struct jffs_fmcontrol
*fmc
)
702 printk(KERN_ERR
"jffs_erasable_size(): fmc = NULL\n");
707 /* The flash memory is totally empty. No nodes. No dirt.
712 /* Calculate how much space that is dirty. */
713 for (fm
= fmc
->head
; fm
&& !fm
->nodes
; fm
= fm
->next
) {
714 if (size
&& fm
->offset
== 0) {
715 /* We have reached the beginning of the flash. */
721 /* Someone's signature contained this:
722 There's a fine line between fishing and just standing on
723 the shore like an idiot... */
724 ret
= jffs_flash_erasable_size(fmc
->mtd
, fmc
->head
->offset
, size
);
726 ASSERT(if (ret
< 0) {
727 printk("jffs_erasable_size: flash_erasable_size() "
728 "returned something less than zero (%ld).\n", ret
);
729 printk("jffs_erasable_size: offset = 0x%08x\n",
733 /* If there is dirt on the flash (which is the reason to why
734 this function was called in the first place) but no space is
735 possible to erase right now, the initial part of the list of
736 jffs_fm structs, that hold place for dirty space, could perhaps
737 be shortened. The list's initial "dirty" elements are merged
738 into just one large dirty jffs_fm struct. This operation must
739 only be performed if nothing is possible to erase. Otherwise,
740 jffs_clear_end_of_node() won't work as expected. */
742 struct jffs_fm
*head
= fmc
->head
;
744 /* While there are two dirty nodes beside each other.*/
745 while (head
->nodes
== 0
747 && head
->next
->nodes
== 0) {
749 head
->size
+= del
->size
;
750 head
->next
= del
->next
;
752 del
->next
->prev
= head
;
758 return (ret
>= 0 ? ret
: 0);
761 static struct jffs_fm
*jffs_alloc_fm(void)
765 fm
= kmem_cache_alloc(fm_cache
,GFP_KERNEL
);
766 DJM(if (fm
) no_jffs_fm
++;);
771 static void jffs_free_fm(struct jffs_fm
*n
)
773 kmem_cache_free(fm_cache
,n
);
779 struct jffs_node
*jffs_alloc_node(void)
783 n
= (struct jffs_node
*)kmem_cache_alloc(node_cache
,GFP_KERNEL
);
789 void jffs_free_node(struct jffs_node
*n
)
791 kmem_cache_free(node_cache
,n
);
796 int jffs_get_node_inuse(void)