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 extern kmem_cache_t *fm_cache;
29 extern kmem_cache_t *node_cache;
31 /* This function creates a new shiny flash memory control structure. */
32 struct jffs_fmcontrol *
33 jffs_build_begin(struct jffs_control *c, int unit)
35 struct jffs_fmcontrol *fmc;
38 D3(printk("jffs_build_begin()\n"));
39 fmc = (struct jffs_fmcontrol *)kmalloc(sizeof(struct jffs_fmcontrol),
42 D(printk("jffs_build_begin(): Allocation of "
43 "struct jffs_fmcontrol failed!\n"));
44 return (struct jffs_fmcontrol *)0;
46 DJM(no_jffs_fmcontrol++);
48 mtd = get_mtd_device(NULL, unit);
52 DJM(no_jffs_fmcontrol--);
56 /* Retrieve the size of the flash memory. */
57 fmc->flash_size = mtd->size;
58 D3(printk(" fmc->flash_size = %d bytes\n", fmc->flash_size));
62 fmc->free_size = mtd->size;
63 fmc->sector_size = mtd->erasesize;
64 fmc->max_chunk_size = fmc->sector_size >> 1;
67 + 1 x max_chunk_size, for when a nodes overlaps the end of a sector
68 + 1 x max_chunk_size again, which ought to be enough to handle
69 the case where a rename causes a name to grow, and GC has
70 to write out larger nodes than the ones it's obsoleting.
71 We should fix it so it doesn't have to write the name
73 + another 2 sectors because people keep getting GC stuck and
74 we don't know why. This scares me - I want formal proof
75 of correctness of whatever number we put here. dwmw2.
77 fmc->min_free_size = fmc->sector_size << 2;
84 init_MUTEX(&fmc->biglock);
89 /* When the flash memory scan has completed, this function should be called
90 before use of the control structure. */
92 jffs_build_end(struct jffs_fmcontrol *fmc)
94 D3(printk("jffs_build_end()\n"));
97 fmc->head = fmc->head_extra;
98 fmc->tail = fmc->tail_extra;
100 else if (fmc->head_extra) {
101 fmc->tail_extra->next = fmc->head;
102 fmc->head->prev = fmc->tail_extra;
103 fmc->head = fmc->head_extra;
105 fmc->head_extra = 0; /* These two instructions should be omitted. */
107 D3(jffs_print_fmcontrol(fmc));
111 /* Call this function when the file system is unmounted. This function
112 frees all memory used by this module. */
114 jffs_cleanup_fmcontrol(struct jffs_fmcontrol *fmc)
118 struct jffs_fm *next = fmc->head;
120 while ((cur = next)) {
124 put_mtd_device(fmc->mtd);
126 DJM(no_jffs_fmcontrol--);
131 /* This function returns the size of the first chunk of free space on the
132 flash memory. This function will return something nonzero if the flash
133 memory contains any free space. */
135 jffs_free_size1(struct jffs_fmcontrol *fmc)
139 __u32 end = fmc->flash_size;
142 /* There is nothing on the flash. */
143 return fmc->flash_size;
146 /* Compute the beginning and ending of the contents of the flash. */
147 head = fmc->head->offset;
148 tail = fmc->tail->offset + fmc->tail->size;
152 ASSERT(else if (tail > end) {
153 printk(KERN_WARNING "jffs_free_size1(): tail > end\n");
165 /* This function will return something nonzero in case there are two free
166 areas on the flash. Like this:
168 +----------------+------------------+----------------+
169 | FREE 1 | USED / DIRTY | FREE 2 |
170 +----------------+------------------+----------------+
172 fmc->tail ------------------------^
174 The value returned, will be the size of the first empty area on the
175 flash, in this case marked "FREE 1". */
177 jffs_free_size2(struct jffs_fmcontrol *fmc)
180 __u32 head = fmc->head->offset;
181 __u32 tail = fmc->tail->offset + fmc->tail->size;
182 if (tail == fmc->flash_size) {
194 /* Allocate a chunk of flash memory. If there is enough space on the
195 device, a reference to the associated node is stored in the jffs_fm
198 jffs_fmalloc(struct jffs_fmcontrol *fmc, __u32 size, struct jffs_node *node,
199 struct jffs_fm **result)
202 __u32 free_chunk_size1;
203 __u32 free_chunk_size2;
205 D2(printk("jffs_fmalloc(): fmc = 0x%p, size = %d, "
206 "node = 0x%p\n", fmc, size, node));
210 if (!(fm = jffs_alloc_fm())) {
211 D(printk("jffs_fmalloc(): kmalloc() failed! (fm)\n"));
215 free_chunk_size1 = jffs_free_size1(fmc);
216 free_chunk_size2 = jffs_free_size2(fmc);
217 if (free_chunk_size1 + free_chunk_size2 != fmc->free_size) {
218 printk(KERN_WARNING "Free size accounting screwed\n");
219 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);
222 D3(printk("jffs_fmalloc(): free_chunk_size1 = %u, "
223 "free_chunk_size2 = %u\n",
224 free_chunk_size1, free_chunk_size2));
226 if (size <= free_chunk_size1) {
227 if (!(fm->nodes = (struct jffs_node_ref *)
228 kmalloc(sizeof(struct jffs_node_ref),
230 D(printk("jffs_fmalloc(): kmalloc() failed! "
235 DJM(no_jffs_node_ref++);
236 fm->nodes->node = node;
239 fm->offset = fmc->tail->offset + fmc->tail->size;
240 if (fm->offset == fmc->flash_size) {
243 ASSERT(else if (fm->offset > fmc->flash_size) {
244 printk(KERN_WARNING "jffs_fmalloc(): "
245 "offset > flash_end\n");
250 /* There don't have to be files in the file
255 fmc->free_size -= size;
256 fmc->used_size += size;
258 else if (size > free_chunk_size2) {
259 printk(KERN_WARNING "JFFS: Tried to allocate a too "
260 "large flash memory chunk. (size = %u)\n", size);
265 fm->offset = fmc->tail->offset + fmc->tail->size;
266 fm->size = free_chunk_size1;
268 fmc->free_size -= fm->size;
269 fmc->dirty_size += fm->size; /* Changed by simonk. This seemingly fixes a
270 bug that caused infinite garbage collection.
271 It previously set fmc->dirty_size to size (which is the
272 size of the requested chunk).
283 fm->prev = fmc->tail;
284 fmc->tail->next = fm;
288 D3(jffs_print_fmcontrol(fmc));
289 D3(jffs_print_fm(fm));
295 /* The on-flash space is not needed anymore by the passed node. Remove
296 the reference to the node from the node list. If the data chunk in
297 the flash memory isn't used by any more nodes anymore (fm->nodes == 0),
298 then mark that chunk as dirty. */
300 jffs_fmfree(struct jffs_fmcontrol *fmc, struct jffs_fm *fm, struct jffs_node *node)
302 struct jffs_node_ref *ref;
303 struct jffs_node_ref *prev;
306 D2(printk("jffs_fmfree(): node->ino = %u, node->version = %u\n",
307 node->ino, node->version));
309 ASSERT(if (!fmc || !fm || !fm->nodes) {
310 printk(KERN_ERR "jffs_fmfree(): fmc: 0x%p, fm: 0x%p, "
312 fmc, fm, (fm ? fm->nodes : 0));
316 /* Find the reference to the node that is going to be removed
318 for (ref = fm->nodes, prev = 0; ref; ref = ref->next) {
319 if (ref->node == node) {
321 prev->next = ref->next;
324 fm->nodes = ref->next;
327 DJM(no_jffs_node_ref--);
334 /* If the data chunk in the flash memory isn't used anymore
335 just mark it as obsolete. */
337 /* No node uses this chunk so let's remove it. */
338 fmc->used_size -= fm->size;
339 fmc->dirty_size += fm->size;
340 #if defined(JFFS_MARK_OBSOLETE) && JFFS_MARK_OBSOLETE
341 if (jffs_mark_obsolete(fmc, fm->offset) < 0) {
342 D1(printk("jffs_fmfree(): Failed to mark an on-flash "
343 "node obsolete!\n"));
350 printk(KERN_WARNING "***jffs_fmfree(): "
351 "Didn't delete any node reference!\n");
358 /* This allocation function is used during the initialization of
361 jffs_fmalloced(struct jffs_fmcontrol *fmc, __u32 offset, __u32 size,
362 struct jffs_node *node)
366 D3(printk("jffs_fmalloced()\n"));
368 if (!(fm = jffs_alloc_fm())) {
369 D(printk("jffs_fmalloced(0x%p, %u, %u, 0x%p): failed!\n",
370 fmc, offset, size, node));
379 /* `node' exists and it should be associated with the
380 jffs_fm structure `fm'. */
381 if (!(fm->nodes = (struct jffs_node_ref *)
382 kmalloc(sizeof(struct jffs_node_ref),
384 D(printk("jffs_fmalloced(): !fm->nodes\n"));
388 DJM(no_jffs_node_ref++);
389 fm->nodes->node = node;
391 fmc->used_size += size;
392 fmc->free_size -= size;
395 /* If there is no node, then this is just a chunk of dirt. */
396 fmc->dirty_size += size;
397 fmc->free_size -= size;
400 if (fmc->head_extra) {
401 fm->prev = fmc->tail_extra;
402 fmc->tail_extra->next = fm;
403 fmc->tail_extra = fm;
405 else if (!fmc->head) {
409 else if (fmc->tail->offset + fmc->tail->size < offset) {
410 fmc->head_extra = fm;
411 fmc->tail_extra = fm;
414 fm->prev = fmc->tail;
415 fmc->tail->next = fm;
418 D3(jffs_print_fmcontrol(fmc));
419 D3(jffs_print_fm(fm));
424 /* Add a new node to an already existing jffs_fm struct. */
426 jffs_add_node(struct jffs_node *node)
428 struct jffs_node_ref *ref;
430 D3(printk("jffs_add_node(): ino = %u\n", node->ino));
432 ref = (struct jffs_node_ref *)kmalloc(sizeof(struct jffs_node_ref),
437 DJM(no_jffs_node_ref++);
439 ref->next = node->fm->nodes;
440 node->fm->nodes = ref;
445 /* Free a part of some allocated space. */
447 jffs_fmfree_partly(struct jffs_fmcontrol *fmc, struct jffs_fm *fm, __u32 size)
449 D1(printk("***jffs_fmfree_partly(): fm = 0x%p, fm->nodes = 0x%p, "
450 "fm->nodes->node->ino = %u, size = %u\n",
451 fm, (fm ? fm->nodes : 0),
452 (!fm ? 0 : (!fm->nodes ? 0 : fm->nodes->node->ino)), size));
456 DJM(no_jffs_node_ref--);
459 fmc->used_size -= fm->size;
460 if (fm == fmc->tail) {
462 fmc->free_size += size;
464 fmc->dirty_size += fm->size;
468 /* Find the jffs_fm struct that contains the end of the data chunk that
469 begins at the logical beginning of the flash memory and spans `size'
470 bytes. If we want to erase a sector of the flash memory, we use this
471 function to find where the sector limit cuts a chunk of data. */
473 jffs_cut_node(struct jffs_fmcontrol *fmc, __u32 size)
483 printk(KERN_ERR "jffs_cut_node(): fmc == NULL\n");
494 else if (pos > size) {
507 /* Move the head of the fmc structures and delete the obsolete parts. */
509 jffs_sync_erase(struct jffs_fmcontrol *fmc, int erased_size)
515 printk(KERN_ERR "jffs_sync_erase(): fmc == NULL\n");
519 fmc->dirty_size -= erased_size;
520 fmc->free_size += erased_size;
522 for (fm = fmc->head; fm && (erased_size > 0);) {
523 if (erased_size >= fm->size) {
524 erased_size -= fm->size;
532 fm->size -= erased_size;
533 fm->offset += erased_size;
540 /* Return the oldest used node in the flash memory. */
542 jffs_get_oldest_node(struct jffs_fmcontrol *fmc)
545 struct jffs_node_ref *nref;
546 struct jffs_node *node = 0;
549 printk(KERN_ERR "jffs_get_oldest_node(): fmc == NULL\n");
553 for (fm = fmc->head; fm && !fm->nodes; fm = fm->next);
559 /* The oldest node is the last one in the reference list. This list
560 shouldn't be too long; just one or perhaps two elements. */
561 for (nref = fm->nodes; nref; nref = nref->next) {
565 D2(printk("jffs_get_oldest_node(): ino = %u, version = %u\n",
566 (node ? node->ino : 0), (node ? node->version : 0)));
572 #if defined(JFFS_MARK_OBSOLETE) && JFFS_MARK_OBSOLETE
574 /* Mark an on-flash node as obsolete.
576 Note that this is just an optimization that isn't necessary for the
577 filesystem to work. */
580 jffs_mark_obsolete(struct jffs_fmcontrol *fmc, __u32 fm_offset)
582 /* The `accurate_pos' holds the position of the accurate byte
583 in the jffs_raw_inode structure that we are going to mark
585 __u32 accurate_pos = fm_offset + JFFS_RAW_INODE_ACCURATE_OFFSET;
586 unsigned char zero = 0x00;
589 D3(printk("jffs_mark_obsolete(): accurate_pos = %u\n", accurate_pos));
591 printk(KERN_ERR "jffs_mark_obsolete(): fmc == NULL\n");
595 /* Write 0x00 to the raw inode's accurate member. Don't care
596 about the return value. */
597 MTD_WRITE(fmc->mtd, accurate_pos, 1, &len, &zero);
601 #endif /* JFFS_MARK_OBSOLETE */
603 /* check if it's possible to erase the wanted range, and if not, return
604 * the range that IS erasable, or a negative error code.
607 jffs_flash_erasable_size(struct mtd_info *mtd, __u32 offset, __u32 size)
611 /* assume that sector size for a partition is constant even
612 * if it spans more than one chip (you usually put the same
613 * type of chips in a system)
616 ssize = mtd->erasesize;
618 if (offset % ssize) {
619 printk(KERN_WARNING "jffs_flash_erasable_size() given non-aligned offset %x (erasesize %lx)\n", offset, ssize);
620 /* The offset is not sector size aligned. */
623 else if (offset > mtd->size) {
624 printk(KERN_WARNING "jffs_flash_erasable_size given offset off the end of device (%x > %x)\n", offset, mtd->size);
627 else if (offset + size > mtd->size) {
628 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);
632 return (size / ssize) * ssize;
636 /* How much dirty flash memory is possible to erase at the moment? */
638 jffs_erasable_size(struct jffs_fmcontrol *fmc)
645 printk(KERN_ERR "jffs_erasable_size(): fmc = NULL\n");
650 /* The flash memory is totally empty. No nodes. No dirt.
655 /* Calculate how much space that is dirty. */
656 for (fm = fmc->head; fm && !fm->nodes; fm = fm->next) {
657 if (size && fm->offset == 0) {
658 /* We have reached the beginning of the flash. */
664 /* Someone's signature contained this:
665 There's a fine line between fishing and just standing on
666 the shore like an idiot... */
667 ret = jffs_flash_erasable_size(fmc->mtd, fmc->head->offset, size);
669 ASSERT(if (ret < 0) {
670 printk("jffs_erasable_size: flash_erasable_size() "
671 "returned something less than zero (%ld).\n", ret);
672 printk("jffs_erasable_size: offset = 0x%08x\n",
676 /* If there is dirt on the flash (which is the reason to why
677 this function was called in the first place) but no space is
678 possible to erase right now, the initial part of the list of
679 jffs_fm structs, that hold place for dirty space, could perhaps
680 be shortened. The list's initial "dirty" elements are merged
681 into just one large dirty jffs_fm struct. This operation must
682 only be performed if nothing is possible to erase. Otherwise,
683 jffs_clear_end_of_node() won't work as expected. */
685 struct jffs_fm *head = fmc->head;
687 /* While there are two dirty nodes beside each other.*/
688 while (head->nodes == 0
690 && head->next->nodes == 0) {
692 head->size += del->size;
693 head->next = del->next;
695 del->next->prev = head;
701 return (ret >= 0 ? ret : 0);
704 struct jffs_fm *jffs_alloc_fm(void)
708 fm = kmem_cache_alloc(fm_cache,GFP_KERNEL);
709 DJM(if (fm) no_jffs_fm++;);
714 void jffs_free_fm(struct jffs_fm *n)
716 kmem_cache_free(fm_cache,n);
722 struct jffs_node *jffs_alloc_node(void)
726 n = (struct jffs_node *)kmem_cache_alloc(node_cache,GFP_KERNEL);
732 void jffs_free_node(struct jffs_node *n)
734 kmem_cache_free(node_cache,n);
739 int jffs_get_node_inuse(void)
745 jffs_print_fmcontrol(struct jffs_fmcontrol *fmc)
747 D(printk("struct jffs_fmcontrol: 0x%p\n", fmc));
749 D(printk(" %u, /* flash_size */\n", fmc->flash_size));
750 D(printk(" %u, /* used_size */\n", fmc->used_size));
751 D(printk(" %u, /* dirty_size */\n", fmc->dirty_size));
752 D(printk(" %u, /* free_size */\n", fmc->free_size));
753 D(printk(" %u, /* sector_size */\n", fmc->sector_size));
754 D(printk(" %u, /* min_free_size */\n", fmc->min_free_size));
755 D(printk(" %u, /* max_chunk_size */\n", fmc->max_chunk_size));
756 D(printk(" 0x%p, /* mtd */\n", fmc->mtd));
757 D(printk(" 0x%p, /* head */ "
758 "(head->offset = 0x%08x)\n",
759 fmc->head, (fmc->head ? fmc->head->offset : 0)));
760 D(printk(" 0x%p, /* tail */ "
761 "(tail->offset + tail->size = 0x%08x)\n",
763 (fmc->tail ? fmc->tail->offset + fmc->tail->size : 0)));
764 D(printk(" 0x%p, /* head_extra */\n", fmc->head_extra));
765 D(printk(" 0x%p, /* tail_extra */\n", fmc->tail_extra));
770 jffs_print_fm(struct jffs_fm *fm)
772 D(printk("struct jffs_fm: 0x%p\n", fm));
774 D(printk(" 0x%08x, /* offset */\n", fm->offset));
775 D(printk(" %u, /* size */\n", fm->size));
776 D(printk(" 0x%p, /* prev */\n", fm->prev));
777 D(printk(" 0x%p, /* next */\n", fm->next));
778 D(printk(" 0x%p, /* nodes */\n", fm->nodes));
783 jffs_print_node_ref(struct jffs_node_ref *ref)
785 D(printk("struct jffs_node_ref: 0x%p\n", ref));
787 D(printk(" 0x%p, /* node */\n", ref->node));
788 D(printk(" 0x%p, /* next */\n", ref->next));