// -*- 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;