jffs_fm.c

mtd最新cvs jffs文件系统分析

/*
 * JFFS -- Journaling Flash File System, Linux implementation.
 *
 * Copyright (C) 1999, 2000  Axis Communications AB.
 *
 * Created by Finn Hakansson <[e-mail]>.
 *
 * This is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * $Id: jffs_fm.c,v 1.31 2003/07/21 15:09:02 trini Exp $
 *
 * Ported to Linux 2.3.x and MTD:
 * Copyright (C) 2000  Alexander Larsson ([e-mail]), Cendio Systems AB
 *
 */
#define __NO_VERSION__
#include <linux/slab.h>
#include <linux/blkdev.h>
#include <linux/jffs.h>
#include <linux/compatmac.h>
#include "jffs_fm.h"

#if (LINUX_VERSION_CODE < KERNEL_VERSION(2,5,2)) && !defined(minor)
#define minor(x) MINOR(x)
#define major(x) MAJOR(x)
#endif

#if defined(JFFS_MARK_OBSOLETE) && JFFS_MARK_OBSOLETE
static int jffs_mark_obsolete(struct jffs_fmcontrol *fmc, __u32 fm_offset);
#endif

extern kmem_cache_t     *fm_cache;
extern kmem_cache_t     *node_cache;

/* This function creates a new shiny flash memory control structure.  */
struct jffs_fmcontrol *
jffs_build_begin(struct jffs_control *c, kdev_t dev)
{
	struct jffs_fmcontrol *fmc;
	struct mtd_info *mtd;
	
	D3(printk("jffs_build_begin()\n"));
	fmc = (struct jffs_fmcontrol *)kmalloc(sizeof(struct jffs_fmcontrol),
					       GFP_KERNEL);
	if (!fmc) {
		D(printk("jffs_build_begin(): Allocation of "
			 "struct jffs_fmcontrol failed!\n"));
		return (struct jffs_fmcontrol *)0;
	}
	DJM(no_jffs_fmcontrol++);

	mtd = get_mtd_device(NULL, minor(dev));

	if (!mtd) {
		kfree(fmc);
		DJM(no_jffs_fmcontrol--);
		return NULL;
	}
	
	/* Retrieve the size of the flash memory.  */
	fmc->flash_size = mtd->size;
	D3(printk("  fmc->flash_size = %d bytes\n", fmc->flash_size));

	fmc->used_size = 0;
	fmc->dirty_size = 0;
	fmc->free_size = mtd->size;
	fmc->sector_size = mtd->erasesize;
	fmc->max_chunk_size = fmc->sector_size >> 1;
	/* min_free_size:
	   1 sector, obviously.
	   + 1 x max_chunk_size, for when a nodes overlaps the end of a sector
	   + 1 x max_chunk_size again, which ought to be enough to handle 
		   the case where a rename causes a name to grow, and GC has
		   to write out larger nodes than the ones it's obsoleting.
		   We should fix it so it doesn't have to write the name
		   _every_ time. Later.
	   + another 2 sectors because people keep getting GC stuck and
	           we don't know why. This scares me - I want formal proof
		   of correctness of whatever number we put here. dwmw2.
	*/
	fmc->min_free_size = fmc->sector_size << 2;
	fmc->mtd = mtd;
	fmc->c = c;
	fmc->head = 0;
	fmc->tail = 0;
	fmc->head_extra = 0;
	fmc->tail_extra = 0;
	init_MUTEX(&fmc->biglock);
	return fmc;
}


/* When the flash memory scan has completed, this function should be called
   before use of the control structure.  */
int
jffs_build_end(struct jffs_fmcontrol *fmc, __u32 head_offset)
{
	D3(printk("jffs_build_end()\n"));

	if (!fmc->head) {
		fmc->head = fmc->head_extra;
		fmc->tail = fmc->tail_extra;
	}
	else if (fmc->head_extra) {
		struct jffs_fm *fm, *cur;

		if (head_offset == fmc->head->offset){
			fmc->tail->next = fmc->head_extra;
			fmc->head_extra->prev = fmc->tail;
			fmc->tail = fmc->tail_extra;
		}
		else {
			fmc->tail_extra->next = fmc->head;
			fmc->head->prev = fmc->tail_extra;
			fmc->head = fmc->head_extra;
			while (fmc->head->offset != head_offset){
				fmc->tail->next = fmc->head;
				fmc->head = fmc->head->next;
				fmc->head->prev = 0;
				fmc->tail->next->prev = fmc->tail;
				fmc->tail = fmc->tail->next;
				fmc->tail->next = 0;
			}
		}
				/* Make sure the only free space we have is between tail and head.
				 */
		for (cur = fmc->head; cur && cur != fmc->tail;) {
			if (cur->offset + cur->size < cur->next->offset) {
				if (!(fm = kmalloc(sizeof(struct jffs_fm), GFP_KERNEL))) {
					D(printk("jffs_buid_end(): kmalloc failed!\n"));
					return -ENOMEM;
				}
				DJM(no_jffs_fm++);
				fm->size = cur->next->offset - cur->offset - cur->size;
				fm->offset = cur->offset + cur->size;
				fm->nodes = 0;
				fm->next = cur->next;
				fm->prev = cur;
				cur->next->prev = fm;
				cur->next = fm;
				cur = fm->next;
				fmc->free_size -= fm->size;
				fmc->dirty_size += fm->size;
			}
			else if (cur->offset > cur->next->offset) {
				if (cur->offset + cur->size < fmc->flash_size){
					if (!(fm = kmalloc(sizeof(struct jffs_fm), GFP_KERNEL))){
						
						D(printk("jffs_buid_end(): kmalloc failed!\n"));
						return -ENOMEM;
					}
					DJM(no_jffs_fm++);
					fm->size = fmc->flash_size -
					           cur->offset - cur->size;
					fm->nodes = 0;
					fm->offset = cur->offset + cur->size;
					fm->next = cur->next;
					fm->prev = cur;
					cur->next->prev = fm;
					cur->next = fm;
					cur = fm->next;
					fmc->free_size -= fm->size;
					fmc->dirty_size += fm->size;
				}
				else {
					cur = cur->next;
				}
				if (cur->offset > 0) {
					
					if (!(fm = kmalloc(sizeof(struct jffs_fm), GFP_KERNEL))) {
						D(printk("jffs_buid_end(): kmalloc failed!\n"));
						return -ENOMEM;
					}
					DJM(no_jffs_fm++);
					fm->size = cur->offset;
					fm->nodes = 0;
					fm->offset = 0;
					fm->next = cur;
					fm->prev = cur->prev;
					cur->prev->next = fm;
					cur->prev = fm;
					fmc->free_size -= fm->size;
					fmc->dirty_size += fm->size;
				}
			}
			else if (cur->offset + cur->size != cur->next->offset) {
				printk("jffs_build_end(): Internal error.\n");
				return -EINVAL;
			}
			else {
				cur = cur->next;
			}
		}
	}
	fmc->head_extra = 0; /* These two instructions should be omitted.  */
	fmc->tail_extra = 0;
	D3(jffs_print_fmcontrol(fmc));
	return 0;
}


/* Call this function when the file system is unmounted.  This function
   frees all memory used by this module.  */
void
jffs_cleanup_fmcontrol(struct jffs_fmcontrol *fmc)
{
	if (fmc) {
		struct jffs_fm *cur;
		struct jffs_fm *next = fmc->head;

		while ((cur = next)) {
			next = next->next;
			jffs_free_fm(cur);
		}
		put_mtd_device(fmc->mtd);
		kfree(fmc);
		DJM(no_jffs_fmcontrol--);
	}
}


/* This function returns the size of the first chunk of free space on the
   flash memory.  This function will return something nonzero if the flash
   memory contains any free space.  */
__u32
jffs_free_size1(struct jffs_fmcontrol *fmc)
{
	__u32 head;
	__u32 tail;
	__u32 end = fmc->flash_size;

	if (!fmc->head) {
		/* There is nothing on the flash.  */
		return fmc->flash_size;
	}

	/* Compute the beginning and ending of the contents of the flash.  */
	head = fmc->head->offset;
	tail = fmc->tail->offset + fmc->tail->size;
	if (tail == end) {
		tail = 0;
	}
	ASSERT(else if (tail > end) {
		printk(KERN_WARNING "jffs_free_size1(): tail > end\n");
		tail = 0;
	});

	if (head <= tail) {
		return end - tail;
	}
	else {
		return head - tail;
	}
}

/* This function will return something nonzero in case there are two free
   areas on the flash.  Like this:

     +----------------+------------------+----------------+
     |     FREE 1     |   USED / DIRTY   |     FREE 2     |
     +----------------+------------------+----------------+
       fmc->head -----^
       fmc->tail ------------------------^

   The value returned, will be the size of the first empty area on the
   flash, in this case marked "FREE 1".  */
__u32
jffs_free_size2(struct jffs_fmcontrol *fmc)
{
	if (fmc->head) {
		__u32 head = fmc->head->offset;
		__u32 tail = fmc->tail->offset + fmc->tail->size;
		if (tail == fmc->flash_size) {
			tail = 0;
		}

		if (tail >= head) {
			return head;
		}
	}
	return 0;
}


/* Allocate a chunk of flash memory.  If there is enough space on the
   device, a reference to the associated node is stored in the jffs_fm
   struct.  */
int
jffs_fmalloc(struct jffs_fmcontrol *fmc, __u32 size, struct jffs_node *node,
	     struct jffs_fm **result)
{
	struct jffs_fm *fm;
	__u32 free_chunk_size1;
	__u32 free_chunk_size2;

	D2(printk("jffs_fmalloc(): fmc = 0x%p, size = %d, "
		  "node = 0x%p\n", fmc, size, node));

	*result = 0;

	if (!(fm = jffs_alloc_fm())) {
		D(printk("jffs_fmalloc(): kmalloc() failed! (fm)\n"));
		return -ENOMEM;
	}

	free_chunk_size1 = jffs_free_size1(fmc);
	free_chunk_size2 = jffs_free_size2(fmc);
	if (free_chunk_size1 + free_chunk_size2 != fmc->free_size) {
		printk(KERN_WARNING "Free size accounting screwed\n");
		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);
	}

	D3(printk("jffs_fmalloc(): free_chunk_size1 = %u, "
		  "free_chunk_size2 = %u\n",
		  free_chunk_size1, free_chunk_size2));

	if (size <= free_chunk_size1) {
		if (!(fm->nodes = (struct jffs_node_ref *)
				  kmalloc(sizeof(struct jffs_node_ref),
					  GFP_KERNEL))) {
			D(printk("jffs_fmalloc(): kmalloc() failed! "
				 "(node_ref)\n"));
			jffs_free_fm(fm);
			return -ENOMEM;
		}
		DJM(no_jffs_node_ref++);
		fm->nodes->node = node;
		fm->nodes->next = 0;
		if (fmc->tail) {
			fm->offset = fmc->tail->offset + fmc->tail->size;
			if (fm->offset == fmc->flash_size) {
				fm->offset = 0;
			}
			ASSERT(else if (fm->offset > fmc->flash_size) {
				printk(KERN_WARNING "jffs_fmalloc(): "
				       "offset > flash_end\n");
				fm->offset = 0;
			});
		}
		else {
			/* There don't have to be files in the file
			   system yet.  */
			fm->offset = 0;
		}
		fm->size = size;
		fmc->free_size -= size;
		fmc->used_size += size;
	}
	else if (size > free_chunk_size2) {
		printk(KERN_WARNING "JFFS: Tried to allocate a too "
		       "large flash memory chunk. (size = %u)\n", size);
		jffs_free_fm(fm);
		return -ENOSPC;
	}
	else {
		fm->offset = fmc->tail->offset + fmc->tail->size;
		fm->size = free_chunk_size1;
		fm->nodes = 0;
		fmc->free_size -= fm->size;
		fmc->dirty_size += fm->size; /* Changed by simonk. This seemingly fixes a 
						bug that caused infinite garbage collection.
						It previously set fmc->dirty_size to size (which is the
						size of the requested chunk).
					     */
	}

	fm->next = 0;
	if (!fmc->head) {
		fm->prev = 0;
		fmc->head = fm;
		fmc->tail = fm;
	}
	else {
		fm->prev = fmc->tail;
		fmc->tail->next = fm;
		fmc->tail = fm;
	}

	D3(jffs_print_fmcontrol(fmc));
	D3(jffs_print_fm(fm));
	*result = fm;
	return 0;
}


/* The on-flash space is not needed anymore by the passed node.  Remove
   the reference to the node from the node list.  If the data chunk in
   the flash memory isn't used by any more nodes anymore (fm->nodes == 0),
   then mark that chunk as dirty.  */
int
jffs_fmfree(struct jffs_fmcontrol *fmc, struct jffs_fm *fm, struct jffs_node *node)
{
	struct jffs_node_ref *ref;
	struct jffs_node_ref *prev;
	ASSERT(int del = 0);

	D2(printk("jffs_fmfree(): node->ino = %u, node->version = %u\n",
		 node->ino, node->version));

	ASSERT(if (!fmc || !fm || !fm->nodes) {
		printk(KERN_ERR "jffs_fmfree(): fmc: 0x%p, fm: 0x%p, "
		       "fm->nodes: 0x%p\n",
		       fmc, fm, (fm ? fm->nodes : 0));
		return -1;
	});

	/* Find the reference to the node that is going to be removed
	   and remove it.  */
	for (ref = fm->nodes, prev = 0; ref; ref = ref->next) {
		if (ref->node == node) {
			if (prev) {
				prev->next = ref->next;
			}
			else {
				fm->nodes = ref->next;
			}
			kfree(ref);
			DJM(no_jffs_node_ref--);
			ASSERT(del = 1);
			break;
		}
		prev = ref;
	}

	/* If the data chunk in the flash memory isn't used anymore
	   just mark it as obsolete.  */
	if (!fm->nodes) {
		/* No node uses this chunk so let's remove it.  */
		fmc->used_size -= fm->size;
		fmc->dirty_size += fm->size;
#if defined(JFFS_MARK_OBSOLETE) && JFFS_MARK_OBSOLETE
		if (jffs_mark_obsolete(fmc, fm->offset) < 0) {
			D1(printk("jffs_fmfree(): Failed to mark an on-flash "
				  "node obsolete!\n"));
			return -1;
		}
#endif
	}

	ASSERT(if (!del) {