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 /* This function creates a new shiny flash memory control structure. */
35 struct jffs_fmcontrol
*
36 jffs_build_begin(struct jffs_control
*c
, int unit
)
38 struct jffs_fmcontrol
*fmc
;
41 D3(printk("jffs_build_begin()\n"));
42 fmc
= (struct jffs_fmcontrol
*)kmalloc(sizeof(struct jffs_fmcontrol
),
45 D(printk("jffs_build_begin(): Allocation of "
46 "struct jffs_fmcontrol failed!\n"));
47 return (struct jffs_fmcontrol
*)0;
49 DJM(no_jffs_fmcontrol
++);
51 mtd
= get_mtd_device(NULL
, unit
);
55 DJM(no_jffs_fmcontrol
--);
59 /* Retrieve the size of the flash memory. */
60 fmc
->flash_size
= mtd
->size
;
61 D3(printk(" fmc->flash_size = %d bytes\n", fmc
->flash_size
));
65 fmc
->free_size
= mtd
->size
;
66 fmc
->sector_size
= mtd
->erasesize
;
67 fmc
->max_chunk_size
= fmc
->sector_size
>> 1;
70 + 1 x max_chunk_size, for when a nodes overlaps the end of a sector
71 + 1 x max_chunk_size again, which ought to be enough to handle
72 the case where a rename causes a name to grow, and GC has
73 to write out larger nodes than the ones it's obsoleting.
74 We should fix it so it doesn't have to write the name
76 + another 2 sectors because people keep getting GC stuck and
77 we don't know why. This scares me - I want formal proof
78 of correctness of whatever number we put here. dwmw2.
80 fmc
->min_free_size
= fmc
->sector_size
<< 2;
85 fmc
->head_extra
= NULL
;
86 fmc
->tail_extra
= NULL
;
87 init_MUTEX(&fmc
->biglock
);
92 /* When the flash memory scan has completed, this function should be called
93 before use of the control structure. */
95 jffs_build_end(struct jffs_fmcontrol
*fmc
)
97 D3(printk("jffs_build_end()\n"));
100 fmc
->head
= fmc
->head_extra
;
101 fmc
->tail
= fmc
->tail_extra
;
103 else if (fmc
->head_extra
) {
104 fmc
->tail_extra
->next
= fmc
->head
;
105 fmc
->head
->prev
= fmc
->tail_extra
;
106 fmc
->head
= fmc
->head_extra
;
108 fmc
->head_extra
= NULL
; /* These two instructions should be omitted. */
109 fmc
->tail_extra
= NULL
;
110 D3(jffs_print_fmcontrol(fmc
));
114 /* Call this function when the file system is unmounted. This function
115 frees all memory used by this module. */
117 jffs_cleanup_fmcontrol(struct jffs_fmcontrol
*fmc
)
120 struct jffs_fm
*next
= fmc
->head
;
122 struct jffs_fm
*cur
= next
;
126 put_mtd_device(fmc
->mtd
);
128 DJM(no_jffs_fmcontrol
--);
133 /* This function returns the size of the first chunk of free space on the
134 flash memory. This function will return something nonzero if the flash
135 memory contains any free space. */
137 jffs_free_size1(struct jffs_fmcontrol
*fmc
)
141 __u32 end
= fmc
->flash_size
;
144 /* There is nothing on the flash. */
145 return fmc
->flash_size
;
148 /* Compute the beginning and ending of the contents of the flash. */
149 head
= fmc
->head
->offset
;
150 tail
= fmc
->tail
->offset
+ fmc
->tail
->size
;
154 ASSERT(else if (tail
> end
) {
155 printk(KERN_WARNING
"jffs_free_size1(): tail > end\n");
167 /* This function will return something nonzero in case there are two free
168 areas on the flash. Like this:
170 +----------------+------------------+----------------+
171 | FREE 1 | USED / DIRTY | FREE 2 |
172 +----------------+------------------+----------------+
174 fmc->tail ------------------------^
176 The value returned, will be the size of the first empty area on the
177 flash, in this case marked "FREE 1". */
179 jffs_free_size2(struct jffs_fmcontrol
*fmc
)
182 __u32 head
= fmc
->head
->offset
;
183 __u32 tail
= fmc
->tail
->offset
+ fmc
->tail
->size
;
184 if (tail
== fmc
->flash_size
) {
196 /* Allocate a chunk of flash memory. If there is enough space on the
197 device, a reference to the associated node is stored in the jffs_fm
200 jffs_fmalloc(struct jffs_fmcontrol
*fmc
, __u32 size
, struct jffs_node
*node
,
201 struct jffs_fm
**result
)
204 __u32 free_chunk_size1
;
205 __u32 free_chunk_size2
;
207 D2(printk("jffs_fmalloc(): fmc = 0x%p, size = %d, "
208 "node = 0x%p\n", fmc
, size
, node
));
212 if (!(fm
= jffs_alloc_fm())) {
213 D(printk("jffs_fmalloc(): kmalloc() failed! (fm)\n"));
217 free_chunk_size1
= jffs_free_size1(fmc
);
218 free_chunk_size2
= jffs_free_size2(fmc
);
219 if (free_chunk_size1
+ free_chunk_size2
!= fmc
->free_size
) {
220 printk(KERN_WARNING
"Free size accounting screwed\n");
221 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
);
224 D3(printk("jffs_fmalloc(): free_chunk_size1 = %u, "
225 "free_chunk_size2 = %u\n",
226 free_chunk_size1
, free_chunk_size2
));
228 if (size
<= free_chunk_size1
) {
229 if (!(fm
->nodes
= (struct jffs_node_ref
*)
230 kmalloc(sizeof(struct jffs_node_ref
),
232 D(printk("jffs_fmalloc(): kmalloc() failed! "
237 DJM(no_jffs_node_ref
++);
238 fm
->nodes
->node
= node
;
239 fm
->nodes
->next
= NULL
;
241 fm
->offset
= fmc
->tail
->offset
+ fmc
->tail
->size
;
242 if (fm
->offset
== fmc
->flash_size
) {
245 ASSERT(else if (fm
->offset
> fmc
->flash_size
) {
246 printk(KERN_WARNING
"jffs_fmalloc(): "
247 "offset > flash_end\n");
252 /* There don't have to be files in the file
257 fmc
->free_size
-= size
;
258 fmc
->used_size
+= size
;
260 else if (size
> free_chunk_size2
) {
261 printk(KERN_WARNING
"JFFS: Tried to allocate a too "
262 "large flash memory chunk. (size = %u)\n", size
);
267 fm
->offset
= fmc
->tail
->offset
+ fmc
->tail
->size
;
268 fm
->size
= free_chunk_size1
;
270 fmc
->free_size
-= fm
->size
;
271 fmc
->dirty_size
+= fm
->size
; /* Changed by simonk. This seemingly fixes a
272 bug that caused infinite garbage collection.
273 It previously set fmc->dirty_size to size (which is the
274 size of the requested chunk).
285 fm
->prev
= fmc
->tail
;
286 fmc
->tail
->next
= fm
;
290 D3(jffs_print_fmcontrol(fmc
));
291 D3(jffs_print_fm(fm
));
297 /* The on-flash space is not needed anymore by the passed node. Remove
298 the reference to the node from the node list. If the data chunk in
299 the flash memory isn't used by any more nodes anymore (fm->nodes == 0),
300 then mark that chunk as dirty. */
302 jffs_fmfree(struct jffs_fmcontrol
*fmc
, struct jffs_fm
*fm
, struct jffs_node
*node
)
304 struct jffs_node_ref
*ref
;
305 struct jffs_node_ref
*prev
;
308 D2(printk("jffs_fmfree(): node->ino = %u, node->version = %u\n",
309 node
->ino
, node
->version
));
311 ASSERT(if (!fmc
|| !fm
|| !fm
->nodes
) {
312 printk(KERN_ERR
"jffs_fmfree(): fmc: 0x%p, fm: 0x%p, "
314 fmc
, fm
, (fm
? fm
->nodes
: NULL
));
318 /* Find the reference to the node that is going to be removed
320 for (ref
= fm
->nodes
, prev
= NULL
; ref
; ref
= ref
->next
) {
321 if (ref
->node
== node
) {
323 prev
->next
= ref
->next
;
326 fm
->nodes
= ref
->next
;
329 DJM(no_jffs_node_ref
--);
336 /* If the data chunk in the flash memory isn't used anymore
337 just mark it as obsolete. */
339 /* No node uses this chunk so let's remove it. */
340 fmc
->used_size
-= fm
->size
;
341 fmc
->dirty_size
+= fm
->size
;
342 #if defined(JFFS_MARK_OBSOLETE) && JFFS_MARK_OBSOLETE
343 if (jffs_mark_obsolete(fmc
, fm
->offset
) < 0) {
344 D1(printk("jffs_fmfree(): Failed to mark an on-flash "
345 "node obsolete!\n"));
352 printk(KERN_WARNING
"***jffs_fmfree(): "
353 "Didn't delete any node reference!\n");
360 /* This allocation function is used during the initialization of
363 jffs_fmalloced(struct jffs_fmcontrol
*fmc
, __u32 offset
, __u32 size
,
364 struct jffs_node
*node
)
368 D3(printk("jffs_fmalloced()\n"));
370 if (!(fm
= jffs_alloc_fm())) {
371 D(printk("jffs_fmalloced(0x%p, %u, %u, 0x%p): failed!\n",
372 fmc
, offset
, size
, node
));
381 /* `node' exists and it should be associated with the
382 jffs_fm structure `fm'. */
383 if (!(fm
->nodes
= (struct jffs_node_ref
*)
384 kmalloc(sizeof(struct jffs_node_ref
),
386 D(printk("jffs_fmalloced(): !fm->nodes\n"));
390 DJM(no_jffs_node_ref
++);
391 fm
->nodes
->node
= node
;
392 fm
->nodes
->next
= NULL
;
393 fmc
->used_size
+= size
;
394 fmc
->free_size
-= size
;
397 /* If there is no node, then this is just a chunk of dirt. */
398 fmc
->dirty_size
+= size
;
399 fmc
->free_size
-= size
;
402 if (fmc
->head_extra
) {
403 fm
->prev
= fmc
->tail_extra
;
404 fmc
->tail_extra
->next
= fm
;
405 fmc
->tail_extra
= fm
;
407 else if (!fmc
->head
) {
411 else if (fmc
->tail
->offset
+ fmc
->tail
->size
< offset
) {
412 fmc
->head_extra
= fm
;
413 fmc
->tail_extra
= fm
;
416 fm
->prev
= fmc
->tail
;
417 fmc
->tail
->next
= fm
;
420 D3(jffs_print_fmcontrol(fmc
));
421 D3(jffs_print_fm(fm
));
426 /* Add a new node to an already existing jffs_fm struct. */
428 jffs_add_node(struct jffs_node
*node
)
430 struct jffs_node_ref
*ref
;
432 D3(printk("jffs_add_node(): ino = %u\n", node
->ino
));
434 ref
= (struct jffs_node_ref
*)kmalloc(sizeof(struct jffs_node_ref
),
439 DJM(no_jffs_node_ref
++);
441 ref
->next
= node
->fm
->nodes
;
442 node
->fm
->nodes
= ref
;
447 /* Free a part of some allocated space. */
449 jffs_fmfree_partly(struct jffs_fmcontrol
*fmc
, struct jffs_fm
*fm
, __u32 size
)
451 D1(printk("***jffs_fmfree_partly(): fm = 0x%p, fm->nodes = 0x%p, "
452 "fm->nodes->node->ino = %u, size = %u\n",
453 fm
, (fm
? fm
->nodes
: 0),
454 (!fm
? 0 : (!fm
->nodes
? 0 : fm
->nodes
->node
->ino
)), size
));
458 DJM(no_jffs_node_ref
--);
461 fmc
->used_size
-= fm
->size
;
462 if (fm
== fmc
->tail
) {
464 fmc
->free_size
+= size
;
466 fmc
->dirty_size
+= fm
->size
;
470 /* Find the jffs_fm struct that contains the end of the data chunk that
471 begins at the logical beginning of the flash memory and spans `size'
472 bytes. If we want to erase a sector of the flash memory, we use this
473 function to find where the sector limit cuts a chunk of data. */
475 jffs_cut_node(struct jffs_fmcontrol
*fmc
, __u32 size
)
485 printk(KERN_ERR
"jffs_cut_node(): fmc == NULL\n");
496 else if (pos
> size
) {
509 /* Move the head of the fmc structures and delete the obsolete parts. */
511 jffs_sync_erase(struct jffs_fmcontrol
*fmc
, int erased_size
)
517 printk(KERN_ERR
"jffs_sync_erase(): fmc == NULL\n");
521 fmc
->dirty_size
-= erased_size
;
522 fmc
->free_size
+= erased_size
;
524 for (fm
= fmc
->head
; fm
&& (erased_size
> 0);) {
525 if (erased_size
>= fm
->size
) {
526 erased_size
-= fm
->size
;
534 fm
->size
-= erased_size
;
535 fm
->offset
+= erased_size
;
542 /* Return the oldest used node in the flash memory. */
544 jffs_get_oldest_node(struct jffs_fmcontrol
*fmc
)
547 struct jffs_node_ref
*nref
;
548 struct jffs_node
*node
= NULL
;
551 printk(KERN_ERR
"jffs_get_oldest_node(): fmc == NULL\n");
555 for (fm
= fmc
->head
; fm
&& !fm
->nodes
; fm
= fm
->next
);
561 /* The oldest node is the last one in the reference list. This list
562 shouldn't be too long; just one or perhaps two elements. */
563 for (nref
= fm
->nodes
; nref
; nref
= nref
->next
) {
567 D2(printk("jffs_get_oldest_node(): ino = %u, version = %u\n",
568 (node
? node
->ino
: 0), (node
? node
->version
: 0)));
574 #if defined(JFFS_MARK_OBSOLETE) && JFFS_MARK_OBSOLETE
576 /* Mark an on-flash node as obsolete.
578 Note that this is just an optimization that isn't necessary for the
579 filesystem to work. */
582 jffs_mark_obsolete(struct jffs_fmcontrol
*fmc
, __u32 fm_offset
)
584 /* The `accurate_pos' holds the position of the accurate byte
585 in the jffs_raw_inode structure that we are going to mark
587 __u32 accurate_pos
= fm_offset
+ JFFS_RAW_INODE_ACCURATE_OFFSET
;
588 unsigned char zero
= 0x00;
591 D3(printk("jffs_mark_obsolete(): accurate_pos = %u\n", accurate_pos
));
593 printk(KERN_ERR
"jffs_mark_obsolete(): fmc == NULL\n");
597 /* Write 0x00 to the raw inode's accurate member. Don't care
598 about the return value. */
599 MTD_WRITE(fmc
->mtd
, accurate_pos
, 1, &len
, &zero
);
603 #endif /* JFFS_MARK_OBSOLETE */
605 /* check if it's possible to erase the wanted range, and if not, return
606 * the range that IS erasable, or a negative error code.
609 jffs_flash_erasable_size(struct mtd_info
*mtd
, __u32 offset
, __u32 size
)
613 /* assume that sector size for a partition is constant even
614 * if it spans more than one chip (you usually put the same
615 * type of chips in a system)
618 ssize
= mtd
->erasesize
;
620 if (offset
% ssize
) {
621 printk(KERN_WARNING
"jffs_flash_erasable_size() given non-aligned offset %x (erasesize %lx)\n", offset
, ssize
);
622 /* The offset is not sector size aligned. */
625 else if (offset
> mtd
->size
) {
626 printk(KERN_WARNING
"jffs_flash_erasable_size given offset off the end of device (%x > %x)\n", offset
, mtd
->size
);
629 else if (offset
+ size
> mtd
->size
) {
630 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
);
634 return (size
/ ssize
) * ssize
;
638 /* How much dirty flash memory is possible to erase at the moment? */
640 jffs_erasable_size(struct jffs_fmcontrol
*fmc
)
647 printk(KERN_ERR
"jffs_erasable_size(): fmc = NULL\n");
652 /* The flash memory is totally empty. No nodes. No dirt.
657 /* Calculate how much space that is dirty. */
658 for (fm
= fmc
->head
; fm
&& !fm
->nodes
; fm
= fm
->next
) {
659 if (size
&& fm
->offset
== 0) {
660 /* We have reached the beginning of the flash. */
666 /* Someone's signature contained this:
667 There's a fine line between fishing and just standing on
668 the shore like an idiot... */
669 ret
= jffs_flash_erasable_size(fmc
->mtd
, fmc
->head
->offset
, size
);
671 ASSERT(if (ret
< 0) {
672 printk("jffs_erasable_size: flash_erasable_size() "
673 "returned something less than zero (%ld).\n", ret
);
674 printk("jffs_erasable_size: offset = 0x%08x\n",
678 /* If there is dirt on the flash (which is the reason to why
679 this function was called in the first place) but no space is
680 possible to erase right now, the initial part of the list of
681 jffs_fm structs, that hold place for dirty space, could perhaps
682 be shortened. The list's initial "dirty" elements are merged
683 into just one large dirty jffs_fm struct. This operation must
684 only be performed if nothing is possible to erase. Otherwise,
685 jffs_clear_end_of_node() won't work as expected. */
687 struct jffs_fm
*head
= fmc
->head
;
689 /* While there are two dirty nodes beside each other.*/
690 while (head
->nodes
== 0
692 && head
->next
->nodes
== 0) {
694 head
->size
+= del
->size
;
695 head
->next
= del
->next
;
697 del
->next
->prev
= head
;
703 return (ret
>= 0 ? ret
: 0);
706 static struct jffs_fm
*jffs_alloc_fm(void)
710 fm
= kmem_cache_alloc(fm_cache
,GFP_KERNEL
);
711 DJM(if (fm
) no_jffs_fm
++;);
716 static void jffs_free_fm(struct jffs_fm
*n
)
718 kmem_cache_free(fm_cache
,n
);
724 struct jffs_node
*jffs_alloc_node(void)
728 n
= (struct jffs_node
*)kmem_cache_alloc(node_cache
,GFP_KERNEL
);
734 void jffs_free_node(struct jffs_node
*n
)
736 kmem_cache_free(node_cache
,n
);
741 int jffs_get_node_inuse(void)
747 jffs_print_fmcontrol(struct jffs_fmcontrol
*fmc
)
749 D(printk("struct jffs_fmcontrol: 0x%p\n", fmc
));
751 D(printk(" %u, /* flash_size */\n", fmc
->flash_size
));
752 D(printk(" %u, /* used_size */\n", fmc
->used_size
));
753 D(printk(" %u, /* dirty_size */\n", fmc
->dirty_size
));
754 D(printk(" %u, /* free_size */\n", fmc
->free_size
));
755 D(printk(" %u, /* sector_size */\n", fmc
->sector_size
));
756 D(printk(" %u, /* min_free_size */\n", fmc
->min_free_size
));
757 D(printk(" %u, /* max_chunk_size */\n", fmc
->max_chunk_size
));
758 D(printk(" 0x%p, /* mtd */\n", fmc
->mtd
));
759 D(printk(" 0x%p, /* head */ "
760 "(head->offset = 0x%08x)\n",
761 fmc
->head
, (fmc
->head
? fmc
->head
->offset
: 0)));
762 D(printk(" 0x%p, /* tail */ "
763 "(tail->offset + tail->size = 0x%08x)\n",
765 (fmc
->tail
? fmc
->tail
->offset
+ fmc
->tail
->size
: 0)));
766 D(printk(" 0x%p, /* head_extra */\n", fmc
->head_extra
));
767 D(printk(" 0x%p, /* tail_extra */\n", fmc
->tail_extra
));
772 jffs_print_fm(struct jffs_fm
*fm
)
774 D(printk("struct jffs_fm: 0x%p\n", fm
));
776 D(printk(" 0x%08x, /* offset */\n", fm
->offset
));
777 D(printk(" %u, /* size */\n", fm
->size
));
778 D(printk(" 0x%p, /* prev */\n", fm
->prev
));
779 D(printk(" 0x%p, /* next */\n", fm
->next
));
780 D(printk(" 0x%p, /* nodes */\n", fm
->nodes
));
786 jffs_print_node_ref(struct jffs_node_ref
*ref
)
788 D(printk("struct jffs_node_ref: 0x%p\n", ref
));
790 D(printk(" 0x%p, /* node */\n", ref
->node
));
791 D(printk(" 0x%p, /* next */\n", ref
->next
));