nodemgmt.c

jffs2源代码基于2。6内核

/*
 * JFFS2 -- Journalling Flash File System, Version 2.
 *
 * Copyright (C) 2001-2003 Red Hat, Inc.
 *
 * Created by David Woodhouse <[e-mail]>
 *
 * For licensing information, see the file 'LICENCE' in this directory.
 *
 * $Id: nodemgmt.c,v 1.109 2004/10/07 15:08:47 havasi Exp $
 *
 */

#include <linux/kernel.h>
#include <linux/slab.h>
#include <linux/mtd/mtd.h>
#include <linux/compiler.h>
#include <linux/sched.h> /* For cond_resched() */
#include "nodelist.h"

/**
 *	jffs2_reserve_space - request physical space to write nodes to flash
 *	@c: superblock info
 *	@minsize: Minimum acceptable size of allocation
 *	@ofs: Returned value of node offset
 *	@len: Returned value of allocation length
 *	@prio: Allocation type - ALLOC_{NORMAL,DELETION}
 *
 *	Requests a block of physical space on the flash. Returns zero for success
 *	and puts 'ofs' and 'len' into the appriopriate place, or returns -ENOSPC
 *	or other error if appropriate.
 *
 *	If it returns zero, jffs2_reserve_space() also downs the per-filesystem
 *	allocation semaphore, to prevent more than one allocation from being
 *	active at any time. The semaphore is later released by jffs2_commit_allocation()
 *
 *	jffs2_reserve_space() may trigger garbage collection in order to make room
 *	for the requested allocation.
 */

static int jffs2_do_reserve_space(struct jffs2_sb_info *c,  uint32_t minsize, uint32_t *ofs, uint32_t *len);

int jffs2_reserve_space(struct jffs2_sb_info *c, uint32_t minsize, uint32_t *ofs, uint32_t *len, int prio)
{
	int ret = -EAGAIN;
	int blocksneeded = c->resv_blocks_write;
	/* align it */
	minsize = PAD(minsize);

	D1(printk(KERN_DEBUG "jffs2_reserve_space(): Requested 0x%x bytes\n", minsize));
	down(&c->alloc_sem);

	D1(printk(KERN_DEBUG "jffs2_reserve_space(): alloc sem got\n"));

	spin_lock(&c->erase_completion_lock);

	/* this needs a little more thought (true <tglx> :)) */
	while(ret == -EAGAIN) {
		while(c->nr_free_blocks + c->nr_erasing_blocks < blocksneeded) {
			int ret;
			uint32_t dirty, avail;

			/* calculate real dirty size
			 * dirty_size contains blocks on erase_pending_list
			 * those blocks are counted in c->nr_erasing_blocks.
			 * If one block is actually erased, it is not longer counted as dirty_space
			 * but it is counted in c->nr_erasing_blocks, so we add it and subtract it
			 * with c->nr_erasing_blocks * c->sector_size again.
			 * Blocks on erasable_list are counted as dirty_size, but not in c->nr_erasing_blocks
			 * This helps us to force gc and pick eventually a clean block to spread the load.
			 * We add unchecked_size here, as we hopefully will find some space to use.
			 * This will affect the sum only once, as gc first finishes checking
			 * of nodes.
			 */
			dirty = c->dirty_size + c->erasing_size - c->nr_erasing_blocks * c->sector_size + c->unchecked_size;
			if (dirty < c->nospc_dirty_size) {
				if (prio == ALLOC_DELETION && c->nr_free_blocks + c->nr_erasing_blocks >= c->resv_blocks_deletion) {
					printk(KERN_NOTICE "jffs2_reserve_space(): Low on dirty space to GC, but it's a deletion. Allowing...\n");
					break;
				}
				D1(printk(KERN_DEBUG "dirty size 0x%08x + unchecked_size 0x%08x < nospc_dirty_size 0x%08x, returning -ENOSPC\n",
					  dirty, c->unchecked_size, c->sector_size));

				spin_unlock(&c->erase_completion_lock);
				up(&c->alloc_sem);
				return -ENOSPC;
			}
			
			/* Calc possibly available space. Possibly available means that we
			 * don't know, if unchecked size contains obsoleted nodes, which could give us some
			 * more usable space. This will affect the sum only once, as gc first finishes checking
			 * of nodes.
			 + Return -ENOSPC, if the maximum possibly available space is less or equal than 
			 * blocksneeded * sector_size.
			 * This blocks endless gc looping on a filesystem, which is nearly full, even if
			 * the check above passes.
			 */
			avail = c->free_size + c->dirty_size + c->erasing_size + c->unchecked_size;
			if ( (avail / c->sector_size) <= blocksneeded) {
				if (prio == ALLOC_DELETION && c->nr_free_blocks + c->nr_erasing_blocks >= c->resv_blocks_deletion) {
					printk(KERN_NOTICE "jffs2_reserve_space(): Low on possibly available space, but it's a deletion. Allowing...\n");
					break;
				}

				D1(printk(KERN_DEBUG "max. available size 0x%08x  < blocksneeded * sector_size 0x%08x, returning -ENOSPC\n",
					  avail, blocksneeded * c->sector_size));
				spin_unlock(&c->erase_completion_lock);
				up(&c->alloc_sem);
				return -ENOSPC;
			}

			up(&c->alloc_sem);

			D1(printk(KERN_DEBUG "Triggering GC pass. nr_free_blocks %d, nr_erasing_blocks %d, free_size 0x%08x, dirty_size 0x%08x, wasted_size 0x%08x, used_size 0x%08x, erasing_size 0x%08x, bad_size 0x%08x (total 0x%08x of 0x%08x)\n",
				  c->nr_free_blocks, c->nr_erasing_blocks, c->free_size, c->dirty_size, c->wasted_size, c->used_size, c->erasing_size, c->bad_size,
				  c->free_size + c->dirty_size + c->wasted_size + c->used_size + c->erasing_size + c->bad_size, c->flash_size));
			spin_unlock(&c->erase_completion_lock);
			
			ret = jffs2_garbage_collect_pass(c);
			if (ret)
				return ret;

			cond_resched();

			if (signal_pending(current))
				return -EINTR;

			down(&c->alloc_sem);
			spin_lock(&c->erase_completion_lock);
		}

		ret = jffs2_do_reserve_space(c, minsize, ofs, len);
		if (ret) {
			D1(printk(KERN_DEBUG "jffs2_reserve_space: ret is %d\n", ret));
		}
	}
	spin_unlock(&c->erase_completion_lock);
	if (ret)
		up(&c->alloc_sem);
	return ret;
}

int jffs2_reserve_space_gc(struct jffs2_sb_info *c, uint32_t minsize, uint32_t *ofs, uint32_t *len)
{
	int ret = -EAGAIN;
	minsize = PAD(minsize);

	D1(printk(KERN_DEBUG "jffs2_reserve_space_gc(): Requested 0x%x bytes\n", minsize));

	spin_lock(&c->erase_completion_lock);
	while(ret == -EAGAIN) {
		ret = jffs2_do_reserve_space(c, minsize, ofs, len);
		if (ret) {
		        D1(printk(KERN_DEBUG "jffs2_reserve_space_gc: looping, ret is %d\n", ret));
		}
	}
	spin_unlock(&c->erase_completion_lock);
	return ret;
}

/* Called with alloc sem _and_ erase_completion_lock */
static int jffs2_do_reserve_space(struct jffs2_sb_info *c,  uint32_t minsize, uint32_t *ofs, uint32_t *len)
{
	struct jffs2_eraseblock *jeb = c->nextblock;
	
 restart:
	if (jeb && minsize > jeb->free_size) {
		/* Skip the end of this block and file it as having some dirty space */
		/* If there's a pending write to it, flush now */
		if (jffs2_wbuf_dirty(c)) {
			spin_unlock(&c->erase_completion_lock);
			D1(printk(KERN_DEBUG "jffs2_do_reserve_space: Flushing write buffer\n"));			    
			jffs2_flush_wbuf_pad(c);
			spin_lock(&c->erase_completion_lock);
			jeb = c->nextblock;
			goto restart;
		}
		c->wasted_size += jeb->free_size;
		c->free_size -= jeb->free_size;
		jeb->wasted_size += jeb->free_size;
		jeb->free_size = 0;
		
		/* Check, if we have a dirty block now, or if it was dirty already */
		if (ISDIRTY (jeb->wasted_size + jeb->dirty_size)) {
			c->dirty_size += jeb->wasted_size;
			c->wasted_size -= jeb->wasted_size;
			jeb->dirty_size += jeb->wasted_size;
			jeb->wasted_size = 0;
			if (VERYDIRTY(c, jeb->dirty_size)) {
				D1(printk(KERN_DEBUG "Adding full erase block at 0x%08x to very_dirty_list (free 0x%08x, dirty 0x%08x, used 0x%08x\n",
				  jeb->offset, jeb->free_size, jeb->dirty_size, jeb->used_size));
				list_add_tail(&jeb->list, &c->very_dirty_list);
			} else {
				D1(printk(KERN_DEBUG "Adding full erase block at 0x%08x to dirty_list (free 0x%08x, dirty 0x%08x, used 0x%08x\n",
				  jeb->offset, jeb->free_size, jeb->dirty_size, jeb->used_size));
				list_add_tail(&jeb->list, &c->dirty_list);
			}
		} else { 
			D1(printk(KERN_DEBUG "Adding full erase block at 0x%08x to clean_list (free 0x%08x, dirty 0x%08x, used 0x%08x\n",
			  jeb->offset, jeb->free_size, jeb->dirty_size, jeb->used_size));
			list_add_tail(&jeb->list, &c->clean_list);
		}
		c->nextblock = jeb = NULL;
	}
	
	if (!jeb) {
		struct list_head *next;
		/* Take the next block off the 'free' list */

		if (list_empty(&c->free_list)) {

			if (!c->nr_erasing_blocks && 
			    !list_empty(&c->erasable_list)) {
				struct jffs2_eraseblock *ejeb;

				ejeb = list_entry(c->erasable_list.next, struct jffs2_eraseblock, list);
				list_del(&ejeb->list);
				list_add_tail(&ejeb->list, &c->erase_pending_list);
				c->nr_erasing_blocks++;
				jffs2_erase_pending_trigger(c);
				D1(printk(KERN_DEBUG "jffs2_do_reserve_space: Triggering erase of erasable block at 0x%08x\n",
					  ejeb->offset));
			}

			if (!c->nr_erasing_blocks && 
			    !list_empty(&c->erasable_pending_wbuf_list)) {
				D1(printk(KERN_DEBUG "jffs2_do_reserve_space: Flushing write buffer\n"));
				/* c->nextblock is NULL, no update to c->nextblock allowed */			    
				spin_unlock(&c->erase_completion_lock);
				jffs2_flush_wbuf_pad(c);
				spin_lock(&c->erase_completion_lock);
				/* Have another go. It'll be on the erasable_list now */
				return -EAGAIN;
			}

			if (!c->nr_erasing_blocks) {
				/* Ouch. We're in GC, or we wouldn't have got here.
				   And there's no space left. At all. */
				printk(KERN_CRIT "Argh. No free space left for GC. nr_erasing_blocks is %d. nr_free_blocks is %d. (erasableempty: %s, erasingempty: %s, erasependingempty: %s)\n", 
				       c->nr_erasing_blocks, c->nr_free_blocks, list_empty(&c->erasable_list)?"yes":"no", 
				       list_empty(&c->erasing_list)?"yes":"no", list_empty(&c->erase_pending_list)?"yes":"no");
				return -ENOSPC;
			}

			spin_unlock(&c->erase_completion_lock);
			/* Don't wait for it; just erase one right now */
			jffs2_erase_pending_blocks(c, 1);
			spin_lock(&c->erase_completion_lock);

			/* An erase may have failed, decreasing the
			   amount of free space available. So we must
			   restart from the beginning */
			return -EAGAIN;
		}

		next = c->free_list.next;
		list_del(next);
		c->nextblock = jeb = list_entry(next, struct jffs2_eraseblock, list);
		c->nr_free_blocks--;

		if (jeb->free_size != c->sector_size - c->cleanmarker_size) {
			printk(KERN_WARNING "Eep. Block 0x%08x taken from free_list had free_size of 0x%08x!!\n", jeb->offset, jeb->free_size);
			goto restart;
		}
	}
	/* OK, jeb (==c->nextblock) is now pointing at a block which definitely has
	   enough space */
	*ofs = jeb->offset + (c->sector_size - jeb->free_size);
	*len = jeb->free_size;

	if (c->cleanmarker_size && jeb->used_size == c->cleanmarker_size &&
	    !jeb->first_node->next_in_ino) {
		/* Only node in it beforehand was a CLEANMARKER node (we think). 
		   So mark it obsolete now that there's going to be another node
		   in the block. This will reduce used_size to zero but We've 
		   already set c->nextblock so that jffs2_mark_node_obsolete()
		   won't try to refile it to the dirty_list.
		*/
		spin_unlock(&c->erase_completion_lock);
		jffs2_mark_node_obsolete(c, jeb->first_node);
		spin_lock(&c->erase_completion_lock);
	}

	D1(printk(KERN_DEBUG "jffs2_do_reserve_space(): Giving 0x%x bytes at 0x%x\n", *len, *ofs));
	return 0;
}

/**
 *	jffs2_add_physical_node_ref - add a physical node reference to the list
 *	@c: superblock info
 *	@new: new node reference to add
 *	@len: length of this physical node
 *	@dirty: dirty flag for new node
 *
 *	Should only be used to report nodes for which space has been allocated 
 *	by jffs2_reserve_space.
 *
 *	Must be called with the alloc_sem held.
 */
 
int jffs2_add_physical_node_ref(struct jffs2_sb_info *c, struct jffs2_raw_node_ref *new)
{
	struct jffs2_eraseblock *jeb;
	uint32_t len;

	jeb = &c->blocks[new->flash_offset / c->sector_size];
	len = ref_totlen(c, jeb, new);

	D1(printk(KERN_DEBUG "jffs2_add_physical_node_ref(): Node at 0x%x(%d), size 0x%x\n", ref_offset(new), ref_flags(new), len));
#if 1
	if (jeb != c->nextblock || (ref_offset(new)) != jeb->offset + (c->sector_size - jeb->free_size)) {
		printk(KERN_WARNING "argh. node added in wrong place\n");
		jffs2_free_raw_node_ref(new);
		return -EINVAL;
	}
#endif
	spin_lock(&c->erase_completion_lock);

	if (!jeb->first_node)
		jeb->first_node = new;
	if (jeb->last_node)
		jeb->last_node->next_phys = new;
	jeb->last_node = new;

	jeb->free_size -= len;
	c->free_size -= len;
	if (ref_obsolete(new)) {
		jeb->dirty_size += len;
		c->dirty_size += len;
	} else {
		jeb->used_size += len;
		c->used_size += len;
	}

	if (!jeb->free_size && !jeb->dirty_size) {
		/* If it lives on the dirty_list, jffs2_reserve_space will put it there */
		D1(printk(KERN_DEBUG "Adding full erase block at 0x%08x to clean_list (free 0x%08x, dirty 0x%08x, used 0x%08x\n",
			  jeb->offset, jeb->free_size, jeb->dirty_size, jeb->used_size));
		if (jffs2_wbuf_dirty(c)) {
			/* Flush the last write in the block if it's outstanding */
			spin_unlock(&c->erase_completion_lock);
			jffs2_flush_wbuf_pad(c);
			spin_lock(&c->erase_completion_lock);
		}

		list_add_tail(&jeb->list, &c->clean_list);
		c->nextblock = NULL;
	}
	ACCT_SANITY_CHECK(c,jeb);
	D1(ACCT_PARANOIA_CHECK(jeb));

	spin_unlock(&c->erase_completion_lock);

	return 0;
}


void jffs2_complete_reservation(struct jffs2_sb_info *c)
{
	D1(printk(KERN_DEBUG "jffs2_complete_reservation()\n"));
	jffs2_garbage_collect_trigger(c);
	up(&c->alloc_sem);
}

static inline int on_list(struct list_head *obj, struct list_head *head)
{
	struct list_head *this;

	list_for_each(this, head) {
		if (this == obj) {
			D1(printk("%p is on list at %p\n", obj, head));
			return 1;

		}
	}
	return 0;
}

void jffs2_mark_node_obsolete(struct jffs2_sb_info *c, struct jffs2_raw_node_ref *ref)
{
	struct jffs2_eraseblock *jeb;
	int blocknr;
	struct jffs2_unknown_node n;
	int ret, addedsize;
	size_t retlen;

	if(!ref) {
		printk(KERN_NOTICE "EEEEEK. jffs2_mark_node_obsolete called with NULL node\n");
		return;
	}
	if (ref_obsolete(ref)) {
		D1(printk(KERN_DEBUG "jffs2_mark_node_obsolete called with already obsolete node at 0x%08x\n", ref_offset(ref)));
		return;
	}
	blocknr = ref->flash_offset / c->sector_size;
	if (blocknr >= c->nr_blocks) {
		printk(KERN_NOTICE "raw node at 0x%08x is off the end of device!\n", ref->flash_offset);
		BUG();