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.6 2000/06/30 14:13:03 dwmw2 Exp $
15 * Ported to Linux 2.3.x and MTD:
16 * Copyright (C) 2000 Alexander Larsson (alex@cendio.se), Cendio Systems AB
19 #define __NO_VERSION__
20 #include <linux/malloc.h>
21 #include <linux/blkdev.h>
22 #include <linux/jffs.h>
25 #if defined(CONFIG_JFFS_FS_VERBOSE) && CONFIG_JFFS_FS_VERBOSE
35 #if defined(JFFS_MARK_OBSOLETE) && JFFS_MARK_OBSOLETE
36 static int jffs_mark_obsolete(struct jffs_fmcontrol
*fmc
, __u32 fm_offset
);
40 /* This function creates a new shiny flash memory control structure. */
41 struct jffs_fmcontrol
*
42 jffs_build_begin(struct jffs_control
*c
, kdev_t dev
)
44 struct jffs_fmcontrol
*fmc
;
47 D3(printk("jffs_build_begin()\n"));
48 fmc
= (struct jffs_fmcontrol
*)kmalloc(sizeof(struct jffs_fmcontrol
),
51 D(printk("jffs_build_begin(): Allocation of "
52 "struct jffs_fmcontrol failed!\n"));
53 return (struct jffs_fmcontrol
*)0;
55 DJM(no_jffs_fmcontrol
++);
57 mtd
= get_mtd_device(NULL
, MINOR(dev
));
62 /* Retrieve the size of the flash memory. */
64 fmc
->flash_size
= mtd
->size
;
65 D3(printk(" fmc->flash_start = 0x%08x\n", fmc
->flash_start
));
66 D3(printk(" fmc->flash_size = %d bytes\n", fmc
->flash_size
));
70 fmc
->sector_size
= 65536;
71 fmc
->max_chunk_size
= fmc
->sector_size
>> 1;
72 fmc
->min_free_size
= (fmc
->sector_size
<< 1) - fmc
->max_chunk_size
;
84 /* When the flash memory scan has completed, this function should be called
85 before use of the control structure. */
87 jffs_build_end(struct jffs_fmcontrol
*fmc
)
89 D3(printk("jffs_build_end()\n"));
92 fmc
->head
= fmc
->head_extra
;
93 fmc
->tail
= fmc
->tail_extra
;
95 else if (fmc
->head_extra
) {
96 fmc
->tail_extra
->next
= fmc
->head
;
97 fmc
->head
->prev
= fmc
->tail_extra
;
98 fmc
->head
= fmc
->head_extra
;
100 fmc
->head_extra
= 0; /* These two instructions should be omitted. */
102 D3(jffs_print_fmcontrol(fmc
));
106 /* Call this function when the file system is unmounted. This function
107 frees all memory used by this module. */
109 jffs_cleanup_fmcontrol(struct jffs_fmcontrol
*fmc
)
113 struct jffs_fm
*next
= fmc
->head
;
115 while ((cur
= next
)) {
120 put_mtd_device(fmc
->mtd
);
122 DJM(no_jffs_fmcontrol
--);
127 /* This function returns the size of the first chunk of free space on the
128 flash memory. This function will return something nonzero if the flash
129 memory contains any free space. */
131 jffs_free_size1(struct jffs_fmcontrol
*fmc
)
135 __u32 end
= fmc
->flash_start
+ fmc
->flash_size
;
138 /* There is nothing on the flash. */
139 return fmc
->flash_size
;
142 /* Compute the beginning and ending of the contents of the flash. */
143 head
= fmc
->head
->offset
;
144 tail
= fmc
->tail
->offset
+ fmc
->tail
->size
;
146 tail
= fmc
->flash_start
;
148 ASSERT(else if (tail
> end
) {
149 printk(KERN_WARNING
"jffs_free_size1(): tail > end\n");
150 tail
= fmc
->flash_start
;
161 /* This function will return something nonzero in case there are two free
162 areas on the flash. Like this:
164 +----------------+------------------+----------------+
165 | FREE 1 | USED / DIRTY | FREE 2 |
166 +----------------+------------------+----------------+
168 fmc->tail ------------------------^
170 The value returned, will be the size of the first empty area on the
171 flash, in this case marked "FREE 1". */
173 jffs_free_size2(struct jffs_fmcontrol
*fmc
)
176 __u32 head
= fmc
->head
->offset
;
177 __u32 tail
= fmc
->tail
->offset
+ fmc
->tail
->size
;
178 if (tail
== fmc
->flash_start
+ fmc
->flash_size
) {
179 tail
= fmc
->flash_start
;
183 return head
- fmc
->flash_start
;
190 /* Allocate a chunk of flash memory. If there is enough space on the
191 device, a reference to the associated node is stored in the jffs_fm
194 jffs_fmalloc(struct jffs_fmcontrol
*fmc
, __u32 size
, struct jffs_node
*node
,
195 struct jffs_fm
**result
)
198 __u32 free_chunk_size1
;
199 __u32 free_chunk_size2
;
201 D2(printk("jffs_fmalloc(): fmc = 0x%p, size = %d, "
202 "node = 0x%p\n", fmc
, size
, node
));
206 if (!(fm
= (struct jffs_fm
*)kmalloc(sizeof(struct jffs_fm
),
208 D(printk("jffs_fmalloc(): kmalloc() failed! (fm)\n"));
213 free_chunk_size1
= jffs_free_size1(fmc
);
214 free_chunk_size2
= jffs_free_size2(fmc
);
215 D3(printk("jffs_fmalloc(): free_chunk_size1 = %u, "
216 "free_chunk_size2 = %u\n",
217 free_chunk_size1
, free_chunk_size2
));
219 if (size
<= free_chunk_size1
) {
220 if (!(fm
->nodes
= (struct jffs_node_ref
*)
221 kmalloc(sizeof(struct jffs_node_ref
),
223 D(printk("jffs_fmalloc(): kmalloc() failed! "
229 DJM(no_jffs_node_ref
++);
230 fm
->nodes
->node
= node
;
233 fm
->offset
= fmc
->tail
->offset
+ fmc
->tail
->size
;
235 == fmc
->flash_start
+ fmc
->flash_size
) {
236 fm
->offset
= fmc
->flash_start
;
238 ASSERT(else if (fm
->offset
241 printk(KERN_WARNING
"jffs_fmalloc(): "
242 "offset > flash_end\n");
243 fm
->offset
= fmc
->flash_start
;
247 /* There don't have to be files in the file
249 fm
->offset
= fmc
->flash_start
;
252 fmc
->used_size
+= size
;
254 else if (size
> free_chunk_size2
) {
255 printk(KERN_WARNING
"JFFS: Tried to allocate a too "
256 "large flash memory chunk. (size = %u)\n", size
);
262 fm
->offset
= fmc
->tail
->offset
+ fmc
->tail
->size
;
263 fm
->size
= free_chunk_size1
;
265 fmc
->dirty_size
+= fm
->size
; /* Changed by simonk. This seemingly fixes a
266 bug that caused infinite garbage collection.
267 It previously set fmc->dirty_size to size (which is the
268 size of the requested chunk).
279 fm
->prev
= fmc
->tail
;
280 fmc
->tail
->next
= fm
;
284 D3(jffs_print_fmcontrol(fmc
));
285 D3(jffs_print_fm(fm
));
291 /* The on-flash space is not needed anymore by the passed node. Remove
292 the reference to the node from the node list. If the data chunk in
293 the flash memory isn't used by any more nodes anymore (fm->nodes == 0),
294 then mark that chunk as dirty. */
296 jffs_fmfree(struct jffs_fmcontrol
*fmc
, struct jffs_fm
*fm
, struct jffs_node
*node
)
298 struct jffs_node_ref
*ref
;
299 struct jffs_node_ref
*prev
;
302 D2(printk("jffs_fmfree(): node->ino = %u, node->version = %u\n",
303 node
->ino
, node
->version
));
305 ASSERT(if (!fmc
|| !fm
|| !fm
->nodes
) {
306 printk(KERN_ERR
"jffs_fmfree(): fmc: 0x%p, fm: 0x%p, "
308 fmc
, fm
, (fm
? fm
->nodes
: 0));
312 /* Find the reference to the node that is going to be removed
314 for (ref
= fm
->nodes
, prev
= 0; ref
; ref
= ref
->next
) {
315 if (ref
->node
== node
) {
317 prev
->next
= ref
->next
;
320 fm
->nodes
= ref
->next
;
323 DJM(no_jffs_node_ref
--);
330 /* If the data chunk in the flash memory isn't used anymore
331 just mark it as obsolete. */
333 /* No node uses this chunk so let's remove it. */
334 fmc
->used_size
-= fm
->size
;
335 fmc
->dirty_size
+= fm
->size
;
336 #if defined(JFFS_MARK_OBSOLETE) && JFFS_MARK_OBSOLETE
337 if (jffs_mark_obsolete(fmc
, fm
->offset
) < 0) {
338 D1(printk("jffs_fmfree(): Failed to mark an on-flash "
339 "node obsolete!\n"));
343 fmc
->c
->sb
->s_dirt
= 1;
347 printk(KERN_WARNING
"***jffs_fmfree(): "
348 "Didn't delete any node reference!\n");
355 /* This allocation function is used during the initialization of
358 jffs_fmalloced(struct jffs_fmcontrol
*fmc
, __u32 offset
, __u32 size
,
359 struct jffs_node
*node
)
363 D3(printk("jffs_fmalloced()\n"));
365 if (!(fm
= (struct jffs_fm
*)kmalloc(sizeof(struct jffs_fm
),
367 D(printk("jffs_fmalloced(0x%p, %u, %u, 0x%p): failed!\n",
368 fmc
, offset
, size
, node
));
378 /* `node' exists and it should be associated with the
379 jffs_fm structure `fm'. */
380 if (!(fm
->nodes
= (struct jffs_node_ref
*)
381 kmalloc(sizeof(struct jffs_node_ref
),
383 D(printk("jffs_fmalloced(): !fm->nodes\n"));
388 DJM(no_jffs_node_ref
++);
389 fm
->nodes
->node
= node
;
391 fmc
->used_size
+= size
;
394 /* If there is no node, then this is just a chunk of dirt. */
395 fmc
->dirty_size
+= size
;
398 if (fmc
->head_extra
) {
399 fm
->prev
= fmc
->tail_extra
;
400 fmc
->tail_extra
->next
= fm
;
401 fmc
->tail_extra
= fm
;
403 else if (!fmc
->head
) {
407 else if (fmc
->tail
->offset
+ fmc
->tail
->size
< offset
) {
408 fmc
->head_extra
= fm
;
409 fmc
->tail_extra
= fm
;
412 fm
->prev
= fmc
->tail
;
413 fmc
->tail
->next
= fm
;
416 D3(jffs_print_fmcontrol(fmc
));
417 D3(jffs_print_fm(fm
));
422 /* Add a new node to an already existing jffs_fm struct. */
424 jffs_add_node(struct jffs_node
*node
)
426 struct jffs_node_ref
*ref
;
427 struct jffs_fm
*fm
= node
->fm
;
428 int s
= sizeof(struct jffs_node_ref
);
430 D3(printk("jffs_add_node(): ino = %u\n", node
->ino
));
432 if (!(ref
= (struct jffs_node_ref
*)kmalloc(s
, GFP_KERNEL
))) {
435 DJM(no_jffs_node_ref
++);
437 ref
->next
= fm
->nodes
;
443 /* Free a part of some allocated space. */
445 jffs_fmfree_partly(struct jffs_fmcontrol
*fmc
, struct jffs_fm
*fm
, __u32 size
)
447 D1(printk("***jffs_fmfree_partly(): fm = 0x%p, fm->nodes = 0x%p, "
448 "fm->nodes->node->ino = %u, size = %u\n",
449 fm
, (fm
? fm
->nodes
: 0),
450 (!fm
? 0 : (!fm
->nodes
? 0 : fm
->nodes
->node
->ino
)), size
));
454 DJM(no_jffs_node_ref
--);
457 fmc
->used_size
-= fm
->size
;
458 if (fm
== fmc
->tail
) {
461 fmc
->dirty_size
+= fm
->size
;
465 /* Find the jffs_fm struct that contains the end of the data chunk that
466 begins at the logical beginning of the flash memory and spans `size'
467 bytes. If we want to erase a sector of the flash memory, we use this
468 function to find where the sector limit cuts a chunk of data. */
470 jffs_cut_node(struct jffs_fmcontrol
*fmc
, __u32 size
)
480 printk(KERN_ERR
"jffs_cut_node(): fmc == NULL\n");
491 else if (pos
> size
) {
504 /* Move the head of the fmc structures and delete the obsolete parts. */
506 jffs_sync_erase(struct jffs_fmcontrol
*fmc
, int erased_size
)
512 printk(KERN_ERR
"jffs_sync_erase(): fmc == NULL\n");
516 fmc
->dirty_size
-= erased_size
;
518 for (fm
= fmc
->head
; fm
&& (erased_size
> 0);) {
519 if (erased_size
>= fm
->size
) {
520 erased_size
-= fm
->size
;
529 fm
->size
-= erased_size
;
530 fm
->offset
+= erased_size
;
537 /* Return the oldest used node in the flash memory. */
539 jffs_get_oldest_node(struct jffs_fmcontrol
*fmc
)
542 struct jffs_node_ref
*nref
;
543 struct jffs_node
*node
= 0;
546 printk(KERN_ERR
"jffs_get_oldest_node(): fmc == NULL\n");
550 for (fm
= fmc
->head
; fm
&& !fm
->nodes
; fm
= fm
->next
);
556 /* The oldest node is the last one in the reference list. This list
557 shouldn't be too long; just one or perhaps two elements. */
558 for (nref
= fm
->nodes
; nref
; nref
= nref
->next
) {
562 D2(printk("jffs_get_oldest_node(): ino = %u, version = %u\n",
563 (node
? node
->ino
: 0), (node
? node
->version
: 0)));
569 #if defined(JFFS_MARK_OBSOLETE) && JFFS_MARK_OBSOLETE
571 /* Mark an on-flash node as obsolete.
573 Note that this is just an optimization that isn't necessary for the
574 filesystem to work. */
577 jffs_mark_obsolete(struct jffs_fmcontrol
*fmc
, __u32 fm_offset
)
579 /* The `accurate_pos' holds the position of the accurate byte
580 in the jffs_raw_inode structure that we are going to mark
582 __u32 accurate_pos
= fm_offset
+ JFFS_RAW_INODE_ACCURATE_OFFSET
;
583 unsigned char zero
= 0x00;
586 D3(printk("jffs_mark_obsolete(): accurate_pos = %u\n", accurate_pos
));
588 printk(KERN_ERR
"jffs_mark_obsolete(): fmc == NULL\n");
592 /* Write 0x00 to the raw inode's accurate member. Don't care
593 about the return value. */
594 MTD_WRITE(fmc
->mtd
, accurate_pos
, 1, &len
, &zero
);
598 #endif /* JFFS_MARK_OBSOLETE */
600 /* check if it's possible to erase the wanted range, and if not, return
601 * the range that IS erasable, or a negative error code.
604 jffs_flash_erasable_size(struct mtd_info
*mtd
, __u32 offset
, __u32 size
)
608 /* assume that sector size for a partition is constant even
609 * if it spans more than one chip (you usually put the same
610 * type of chips in a system)
613 ssize
= mtd
->erasesize
;
615 if (offset
% ssize
) {
616 /* The offset is not sector size aligned. */
619 else if (offset
> mtd
->size
) {
622 else if (offset
+ size
> mtd
->size
) {
626 return (size
/ ssize
) * ssize
;
630 /* How much dirty flash memory is possible to erase at the moment? */
632 jffs_erasable_size(struct jffs_fmcontrol
*fmc
)
639 printk(KERN_ERR
"jffs_erasable_size(): fmc = NULL\n");
644 /* The flash memory is totally empty. No nodes. No dirt.
649 /* Calculate how much space that is dirty. */
650 for (fm
= fmc
->head
; fm
&& !fm
->nodes
; fm
= fm
->next
) {
651 if (size
&& fm
->offset
== fmc
->flash_start
) {
652 /* We have reached the beginning of the flash. */
658 /* Someone's signature contained this:
659 There's a fine line between fishing and just standing on
660 the shore like an idiot... */
661 ret
= jffs_flash_erasable_size(fmc
->mtd
,
662 fmc
->head
->offset
- fmc
->flash_start
, size
);
664 ASSERT(if (ret
< 0) {
665 printk("jffs_erasable_size: flash_erasable_size() "
666 "returned something less than zero (%ld).\n", ret
);
667 printk("jffs_erasable_size: offset = 0x%08x\n",
668 fmc
->head
->offset
- fmc
->flash_start
);
671 /* If there is dirt on the flash (which is the reason to why
672 this function was called in the first place) but no space is
673 possible to erase right now, the initial part of the list of
674 jffs_fm structs, that hold place for dirty space, could perhaps
675 be shortened. The list's initial "dirty" elements are merged
676 into just one large dirty jffs_fm struct. This operation must
677 only be performed if nothing is possible to erase. Otherwise,
678 jffs_clear_end_of_node() won't work as expected. */
680 struct jffs_fm
*head
= fmc
->head
;
682 /* While there are two dirty nodes beside each other.*/
683 while (head
->nodes
== 0
685 && head
->next
->nodes
== 0) {
687 head
->size
+= del
->size
;
688 head
->next
= del
->next
;
690 del
->next
->prev
= head
;
697 return (ret
>= 0 ? ret
: 0);
702 jffs_print_fmcontrol(struct jffs_fmcontrol
*fmc
)
704 D(printk("struct jffs_fmcontrol: 0x%p\n", fmc
));
706 D(printk(" 0x%08x, /* flash_start */\n", fmc
->flash_start
));
707 D(printk(" %u, /* flash_size */\n", fmc
->flash_size
));
708 D(printk(" %u, /* used_size */\n", fmc
->used_size
));
709 D(printk(" %u, /* dirty_size */\n", fmc
->dirty_size
));
710 D(printk(" %u, /* sector_size */\n", fmc
->sector_size
));
711 D(printk(" %u, /* min_free_size */\n", fmc
->min_free_size
));
712 D(printk(" %u, /* max_chunk_size */\n", fmc
->max_chunk_size
));
713 D(printk(" 0x%p, /* mtd */\n", fmc
->mtd
));
714 D(printk(" 0x%p, /* head */ "
715 "(head->offset = 0x%08x)\n",
716 fmc
->head
, (fmc
->head
? fmc
->head
->offset
: 0)));
717 D(printk(" 0x%p, /* tail */ "
718 "(tail->offset + tail->size = 0x%08x)\n",
720 (fmc
->tail
? fmc
->tail
->offset
+ fmc
->tail
->size
: 0)));
721 D(printk(" 0x%p, /* head_extra */\n", fmc
->head_extra
));
722 D(printk(" 0x%p, /* tail_extra */\n", fmc
->tail_extra
));
727 jffs_print_fm(struct jffs_fm
*fm
)
729 D(printk("struct jffs_fm: 0x%p\n", fm
));
731 D(printk(" 0x%08x, /* offset */\n", fm
->offset
));
732 D(printk(" %u, /* size */\n", fm
->size
));
733 D(printk(" 0x%p, /* prev */\n", fm
->prev
));
734 D(printk(" 0x%p, /* next */\n", fm
->next
));
735 D(printk(" 0x%p, /* nodes */\n", fm
->nodes
));
740 jffs_print_node_ref(struct jffs_node_ref
*ref
)
742 D(printk("struct jffs_node_ref: 0x%p\n", ref
));
744 D(printk(" 0x%p, /* node */\n", ref
->node
));
745 D(printk(" 0x%p, /* next */\n", ref
->next
));