super.c

mtd最新cvs的ffs系统

// -*- mode: cpp; mode: fold -*-
// Description                                                          /*{{{*/
// $Id: super.c,v 1.1 2000/03/27 07:14:15 dwmw2 Exp $
/* ######################################################################

   Microsoft Flash File System 2 
   
   Information for the FFS2.0 was found in Microsoft's knowledge base,
   http://msdn.microsoft.com/isapi/msdnlib.idc?theURL=/library/specs/S346A.HTM
   Try searching for "Flash File System" if it has been moved
   
   The filesystem can run in two modes, directly on a MTD or indirectly
   through the block system. The FFS2 filesystem was really designed for 
   linearly mapped flash, it has no block alignment aside from the
   erase unit size which makes it difficult to fit into the block 
   device model.

   While operating the filesystem runs in such a way that a crash will not
   damage the consistency of the filesystem. All crashes will result in 
   allocated but unreferenced blocks that can be easially reclaimed by
   probing the entire allocation tree. There is a risk that a file entry 
   pointer could be partialy written to. In this case that entry pointer is
   useless - the simplest way out is to reclaim that block and set the 
   pointer back to FF. There is, unfortunately, no really good mechanism to
   do that directly :<
   
   TODO:
     - Byte swapping (Carefull, the structures are returned directly from
       bh's!)
     - Compression check should be equal sizes not by compress ID
     - Write routine needs to handle more cases, particularly overwriting,
       not just append
     - Directory additions should check and reclaim very long directories
       that are mostly empty by using superceeds
     - Use a constant inode scheme like the latest FAT driver does (2.2.11)
     - Rename
     - Block reclimation
     - Built in fsck on load - search for unreferenced blocks
     - Look at extensions to handle symlinks, device nodes and ownership.
       Can be done using the extension mechanism that is built in quite 
       directly.
     - Setting the new mtimes isn't right, it needs to go back over the list
       and reset the mtime valid flags. Mtime on empty newly created things
       is wrong too, it needs to use the value of the item itself.
     - Get support for QNX's BPE decompressor.
     - Split this foolish thing up into smaller modules
     - unlink seems to not flush the dentry cache?
   
   ##################################################################### */
									/*}}} */
#include <linux/fs.h>
#include <linux/module.h>
#include <linux/types.h>
#include <linux/errno.h>
#include <linux/malloc.h>
#include <linux/locks.h>
#include <linux/init.h>
#include <linux/blkdev.h>
#include "ffs2_fs.h"
#include "ffs2_fs_sb.h"
#include "ffs2_fs_i.h"
#include "local.h"
#include "io.h"

#include <asm/uaccess.h>

static struct super_operations ffs2_ops;
static struct inode_operations *ffs2_inoops[];

// ffs2_getbh - Get a bh, consulting our cache first			/*{{{*/
// ---------------------------------------------------------------------
/* Because of the random jumps in operations like reading a directory we
   keep a small cache of 4 most recent requests. This prevents BH trashing
   when we lookup block allocation then block then the next allocation
   etc. The speed gain on block devices is substantial. */
static struct buffer_head *ffs2_getbh(struct ffs_read *r,unsigned long loc)
{
   unsigned int I;
   unsigned int old = 0;
   unsigned int age = r->curage;
   
   // Search
   for (I = 0; I != sizeof(r->bh)/sizeof(*r->bh); I++)
   {
      if (r->bh[I] == 0)
	 continue;
      
      if (r->bh[I]->b_blocknr == loc)
	 break;
      if (age > r->age[I])
      {
	 old = I;
	 age = r->age[I];
      }	 
   }   
   
   // Miss
   if (I >= sizeof(r->bh)/sizeof(*r->bh))
   {
      I = old;
      
      // Free the old bh
      if (r->bh[I] != 0)
	 brelse(r->bh[I]);
      if ((r->bh[I] = bread(r->super->s_dev,loc,BLOCK_SIZE)) == NULL)
	 return 0;
   }   
   
   r->age[I] = r->curage++;
   return r->bh[I];
}
									/*}}}*/
// ffs2_read - Perform a read operation					/*{{{*/
// ---------------------------------------------------------------------
/* This performs a read operation with no alignment constraints. If it is 
   possible to return the entire requested block in someone elses memory
   (a MTD window or a buffer head) then that will be done, otherwise a
   copy is performed to the given temporary memory and that is returned
   instead. This will automatically free the ffs_read structure as it
   executes. Count must be a small number, below 128. Using the 
   ahead/behind values it is possible to make multiple requests to 
   do reading */
unsigned char *ffs2_read(struct ffs_read *r,unsigned long block,
			 unsigned long offset,unsigned long count)
{
   unsigned long loc;
   unsigned long left;
   unsigned char *pos;

   if (getFFS2_sb(r->super).Boot.TotalBlockCount != 0 &&
       block >= getFFS2_sb(r->super).Boot.TotalBlockCount)
      return 0;

   r->block = block;
   r->offset = offset;

   block += getFFS2_sb(r->super).ZeroBlock;
   loc = getFFS2_sb(r->super).EraseSize*block + offset;

   // We can return a bh..
   if ((loc >> BLOCK_SIZE_BITS) == ((loc + count - 1) >> BLOCK_SIZE_BITS))
   {
      struct buffer_head *bh = ffs2_getbh(r,loc >> BLOCK_SIZE_BITS);
      if (bh == 0)
	 return 0;
      
      r->behind = loc & (BLOCK_SIZE-1);
      r->ahead = BLOCK_SIZE - r->behind;
      r->p = bh->b_data + r->behind;
      return r->p;
   }
   
   // Doomed :>
   if (count > sizeof(r->temp))
   {
      printk("ffs2: Reading too much");
      return 0;
   }
   
   // Need to use the temp buffer
   pos = r->temp;
   memset(r->temp,0,sizeof(r->temp));
   left = count;
   while (left != 0)
   {
      unsigned long behind;
      unsigned long ahead;
      struct buffer_head *bh = ffs2_getbh(r,loc >> BLOCK_SIZE_BITS);
      if (bh == 0)
	 return 0;
      
      behind = loc & (BLOCK_SIZE-1);
      ahead = BLOCK_SIZE - behind;
      if (left < ahead)
	 ahead = left;
      memcpy(pos,bh->b_data + behind,ahead);
      pos += ahead;
      loc += ahead;
      left -= ahead;
   }
   r->behind = 0;
   r->ahead = count;
   r->p = r->temp;
   return r->p;
}
									/*}}}*/
// ffs2_relse - Release the read structure				/*{{{*/
// ---------------------------------------------------------------------
/* This releases any cached BHs, it is important to call it! */
void ffs2_relse(struct ffs_read *r)
{
   unsigned I;
   for (I = 0; I != sizeof(r->bh)/sizeof(*r->bh); I++)
   {
      if (r->bh[I] != 0)
	 brelse(r->bh[I]);
   }
   memset(r,0,sizeof(*r));
}
									/*}}}*/

// ffs2_write - Write data to the flash					/*{{{*/
// ---------------------------------------------------------------------
/* Copy the given data into the buffer cache */
int ffs2_write(struct ffs_read *r,unsigned long block,
	       unsigned long offset,unsigned char *from,unsigned long count)
{
   unsigned long loc;
   unsigned long left;

   if (getFFS2_sb(r->super).Boot.TotalBlockCount != 0 &&
       block >= getFFS2_sb(r->super).Boot.TotalBlockCount)
      return 0;

   r->block = block;
   r->offset = offset;

   block += getFFS2_sb(r->super).ZeroBlock;
   loc = getFFS2_sb(r->super).EraseSize*block + offset;

   /* Copy over the new data, this should probably use a mechansim that
      doesnt read in the old contents if the write buffer is the full 
      length */
   left = count;
   while (left != 0)
   {
      unsigned long behind;
      unsigned long ahead;
      struct buffer_head *bh = ffs2_getbh(r,loc >> BLOCK_SIZE_BITS);
      if (bh == 0)
	 return -1;
      
      /*printk("Writing %lu to %lu\n",left,loc);
      {
	 unsigned long I;
	 for (I = 0; I < left; I++)
	    printk("%x ",from[I]);
	 printk("\n");
      }*/
      
      behind = loc & (BLOCK_SIZE-1);
      ahead = BLOCK_SIZE - behind;
      if (left < ahead)
	 ahead = left;
      memcpy(bh->b_data + behind,from,ahead);
      from += ahead;
      loc += ahead;
      left -= ahead;

      // Dirty the buffer
      mark_buffer_uptodate(bh, 1);
      mark_buffer_dirty(bh,0);
   }
   r->behind = 0;
   r->ahead = 0;
   r->p = 0;
   return 0;
}
									/*}}}*/

// insert_region - Add a new region to the list of regions		/*{{{*/
// ---------------------------------------------------------------------
/* The purpose here is to take a region and add it to our sorted list of
   regions and merge it with the other regions in the list. */
static int insert_region(struct ffs2_free_space *spaces,unsigned int max,
			 unsigned long start,unsigned long len)
{
   unsigned int I;
   unsigned long end = start + len;
   for (I = 0; I < max-2; I++)
   {
      // Merge it with the last one
      if (spaces[I].Stop == start && spaces[I].Stop != 0)
      {
	 spaces[I].Stop = end;
	 
	 // Join with the next one too
	 if (end == spaces[I+1].Start)
	 {
	    spaces[I].Stop = spaces[I+1].Stop;
	    memmove(spaces + I+1,spaces + I+2,(max - I - 1)*sizeof(*spaces));
	 }	 
	 return 0;
      }
      
      // Merge it with the next one
      if (spaces[I].Start == end)
      {
	 spaces[I].Start = start;
	 return 0;
      }
      	 
      // Insert a new one
      if (spaces[I].Start > start || spaces[I].Stop == 0)
      {	 
	 memmove(spaces + I+1,spaces + I,(max - I - 1)*sizeof(*spaces));
	 spaces[I].Start = start;
	 spaces[I].Stop = end;
	 return 0;
      }
   }   
   
   printk("ffs2: Unable to sort allocation list");
   return -1;
}
									/*}}}*/
// ffs2_make_free_list - Generate the list of free regions		/*{{{*/
// ---------------------------------------------------------------------
/* This scans the block allocations and builds up a list of the free 
   regions. Due to the allocation model used this list should be 
   -short- but it is expensive to calculate the first time. */
static int ffs2_make_free_list(struct ffs_read *r,unsigned block)
{
   enum {max = 100};
   struct ffs2_sb_info *sb = &getFFS2_sb(r->super);
   struct ffs2_free_space spaces[max];
   struct ffs2_blockalloc *alloc;
   struct ffs2_sb_block *info = &sb->Blocks[block];
   unsigned long cur;
   unsigned long offset;
   
   memset(spaces,0,sizeof(spaces));
   
   // Record the end block
   if (insert_region(spaces,max, sb->EraseSize - FFS_SIZEOF_BLOCK,
		     FFS_SIZEOF_BLOCK) != 0)
      return -1;

   info->ReclaimableSpace = 0;
   for (cur = 0; ; cur++)
   {	  
      offset = sb->EraseSize - FFS_SIZEOF_BLOCK - 
	       (cur + 1)*FFS_SIZEOF_BLOCKALLOC;
      if (offset <= 100)
      {
	 printk("ffs2: Allocation list too long");
	 return -1;
      }
      
      // XX can be advoided
      if (ffs2_read(r,block,offset,FFS_SIZEOF_BLOCKALLOC) == 0)
	 return -1;
      alloc = (struct ffs2_blockalloc *)r->p;

      // Record the block alloc structure
      if (insert_region(spaces,max,offset,FFS_SIZEOF_BLOCKALLOC) != 0)
	 return -1;

      // Make sure it is allocated
      if (isflagset(alloc->Status,FFS_ALLOC_SMASK,FFS_ALLOC_ALLOCATED) == 0 &&
	  isflagset(alloc->Status,FFS_ALLOC_SMASK,FFS_ALLOC_DEALLOCATED) == 0)
      {
	 // End of the list
	 if (isflagset(alloc->Status,FFS_ALLOC_EMASK,FFS_ALLOC_END) != 0)
	    break;
	 continue;
      }      
      if (isflagset(alloc->Status,FFS_ALLOC_SMASK,FFS_ALLOC_DEALLOCATED) != 0)
	 info->ReclaimableSpace += alloc->Len;

      // Record the block data
      offset = (alloc->Offset[2] << 16) + (alloc->Offset[1] << 8) + alloc->Offset[0];
      if (insert_region(spaces,max,offset,alloc->Len) != 0)
	 return -1;

      // End of the list
      if (isflagset(alloc->Status,FFS_ALLOC_EMASK,FFS_ALLOC_END) != 0)
	 break;
   }

/*   printk("free list for %lu - %lu %lu\n",block,cur,r->location);
   for (cur = 0; spaces[cur].Stop != 0 || spaces[cur].Start != 0; cur++)
      printk("  at %lu %lu\n",spaces[cur].Start,spaces[cur].Stop);*/
   
   // Invert the list to get a list of free spaces
   cur = 0;
   if (spaces[0].Start != 0)
   {
      memmove(spaces+1,spaces,(max - 1)*sizeof(*spaces));
      spaces[0].Start = 1;
      spaces[0].Stop = 0;
   }
   info->FreeSpace = 0;
   info->LargestSpace = 0;
   for (; spaces[cur].Stop != 0 || spaces[cur].Start != 0; cur++)
   {
      spaces[cur].Start = spaces[cur].Stop;
      spaces[cur].Stop = spaces[cur+1].Start;
      if (spaces[cur].Stop == 0)
      {
	 spaces[cur].Start = 0;
	 continue;
      }
      
      info->FreeSpace += spaces[cur].Stop - spaces[cur].Start;
      if (info->LargestSpace < spaces[cur].Stop - spaces[cur].Start)
	 info->LargestSpace = spaces[cur].Stop - spaces[cur].Start;
   }

   // Store the allocation list
   info->FreeList = kmalloc(sizeof(*info->FreeList)*cur,GFP_KERNEL);
   memmove(info->FreeList,spaces,sizeof(*info->FreeList)*cur);
   
   return 0;
}
									/*}}}*/
// ffs2_prepare_info - Prepares the block info structures		/*{{{*/
// ---------------------------------------------------------------------
/* Generate a mapping of block sequence numbers to real block numbers and
   make sure that we have no holes. This also should repair any damage
   from an abortive reclimation process */
static int ffs2_prepare_info(struct ffs_read *r)
{
   unsigned I;
   struct ffs2_sb_info *sb = &getFFS2_sb(r->super);
   unsigned Blocks = sb->Boot.TotalBlockCount - sb->Boot.SpareBlockCount;

   sb->Blocks = kmalloc(sizeof(*sb->Blocks)*sb->Boot.TotalBlockCount,
			GFP_KERNEL);
   if (sb->Blocks == 0)
      return -1;
   memset(sb->Blocks,0,sizeof(*sb->Blocks)*sb->Boot.TotalBlockCount);
      
   // Generate the reverse mapping
   for (I = 0; I != Blocks; I++)
   {
      if (ffs2_make_free_list(r,sb->BlockMap[I]) != 0)
      {
	 kfree(sb->Blocks);
	 sb->Blocks = 0;
	 return -1;
      }            
      sb->Blocks[sb->BlockMap[I]].VirtualBlock = I;
   }
   
   return 0;
}
									/*}}}*/

// find_free_alloc - Find and allocate some space			/*{{{*/
// ---------------------------------------------------------------------
/* This tries to allocate some space for writing new data too. Block 
   acts as a hint of where to place the allocation or -1 if it does not
   matter. Writing consists of 
     1 Locate a free allocation block
     2 Extend the list
     3 Write the offset and length
     4 Indicate the block is allocated
   Failures can occure at any point. The only tricky failure is betten 3
   and 4, this is detected by ensuring the fields of an unused entry are
   actually FF. Once point 4 is passed then the block is permanently 
   allocated and a failure before it is linked into any lists will leave
   it hanging around forever. */
static unsigned long find_free_alloc(struct ffs_read *r,
				     struct ffs2_blockalloc *outalloc,
				     unsigned long len,long block)
{
   struct ffs2_sb_info *sb = &getFFS2_sb(r->super);
   struct ffs2_sb_block *info;
   unsigned int I;
   unsigned int writeblock;
   unsigned long cur;
   unsigned long offset;
   long best = -1;
   struct ffs2_blockalloc *alloc;