defrag.c

PDA上的CF CARD 文件系统的建立程式

/*************************************************************
File Name: DEFRAG.C					     *
**************************************************************
Programmer: MSC
Last Modified Date: 2000/02/29
Compiler : GNU Cross-compiler/SDS
Platform : X86 protection mode, MIPS, Dragonball
Usage :
	defrag functions for RAMDisk 3.5
	This function collects all free blocks and merges them
	into a single free block. Besides block management,
	this function must be careful with the opened files.
*************************************************************/
#include <sys/syscall.h>

//#include <ansi_c/stdio.h>
/**** modified by chilong 8/23/2001 ****/
#include <stdio.h>
/**** modified by chilong 8/23/2001 ****/


#include <ramdisk.h>
#include <piece.h>
#include <dskblk.h>
#include <defrag.h>



#ifdef RAMDISK_ID



/* basic.c */
extern int		InitRD;
//extern int		RDerrno;

extern void		*RD_BootBegin;

extern int		RD_SemaphoreID;

/* piece.c */
extern unsigned long	RDPieceSize;
extern void		**RD_PLT;
#ifdef RAMDISK_USE_VARIABLE_SIZE_BLOCK
	// variable block size
#else
	// fixed block size
	extern unsigned long RDSystemBlockSize;
#endif

/* dskblk.c */
extern struct diskBlock	*RD_FirstFreeBlock;

/* fio.c */
extern struct RD_FILE	**RD_HandleTable;

//extern char StrTemp[80];



/*************************************************************
The entry information list is the list of the directory entry
location of every file and directory in the RAMDisk.

e.g., the content of the RAMDisk is

Directory name		Starting block addr	Dir entry addr
\			0x10000000		0x0
\DIR1			0x20000000		0x10000000
\DIR2			0x30000000		0x10000040
\DIR1\hehe.txt		0x31000000		0x20000000
\DIR1\hoho.txt		0x34000000		0x20000040
\file1.txt		0x38000000		0x10000080
\DIR2\haha.txt		0x40000000		0x30000000

The complete entry information list will be:

 ----------       ----------       ----------       ----------
|   NULL   |     |0x30000000|     |0x10000080|     |0x20000040|
 ----------       ----------       ----------       ----------
|   NULL   | <-- |          | <-- |          | <-- |          | <--
 ----------       ----------       ----------       ----------
|          | --> |          | --> |          | --> |          | -->
 ----------       ----------       ----------       ----------
    head	\DIR2\haha.txt	   \file1.txt	  \DIR1\hoho.txt

		 ----------       ----------       ----------
		|0x20000000|     |0x10000040|     |0x10000000|
		 ----------       ----------       ----------
	    <-- |          | <-- |          | <-- |          |
		 ----------       ----------       ----------
	    --> |          | --> |          | --> |   NULL   |
		 ----------       ----------       ----------
	       \DIR1\hehe.txt	    \DIR2	     \DIR1

Note that the element in the list are descendingly sorted
according to the starting block address of the file/dir. This
is why double linked list is not used here.

Defrag is done from high address to low address. It is much faster
to find the corresponding entry of a block if the list is
descendingly ordered.
**************************************************************/



/*************************************************************
Fuction : readDirEntryInfo
	read the directory entry information of a directory
Input:
	entryList - the head of the entry list
	startBlock - the starting block of the directory
Output:
	0	no error is found
	-1	system error (check RDerrno)
Note:
**************************************************************/
int readDirEntryInfo(struct entryInfo *head, struct diskBlock *startBlock)
{
  struct diskBlock *curBlock;
  struct directory *curEntry;
  struct entryInfo *eInfo;
  int i;
  char noMore = 0;

  curBlock = startBlock;
  while (curBlock != NULL)
  {
	if (RD_checkBlockLocation(curBlock) == -1)
	{
		return -1;
	}

	curEntry = (struct directory *)((unsigned long)curBlock + sizeof(struct diskBlock));

	for (i = 0; i < DIR_BLOCK_SIZE; i += sizeof(struct directory))
	{
		if (curEntry->name[0] == FREE_ENTRY)
		{
			// a free entry is reached, there will be no occupied entry after it
			noMore = 1;
			break;
		}

		if (curEntry->name[0] != DELETED_ENTRY)
		{
			// this entry is valid, add it to the list
			eInfo = (struct entryInfo *)ap_malloc(sizeof(struct entryInfo));
			if (eInfo == NULL)
			{
				RDerrno = ERROR_ALLOC_MEM;
				return -1;
			}
			eInfo->theEntry = curEntry;
			eInfo->prev = eInfo->next = NULL;
			eLInsert(head, eInfo);

			// call recursively if this entry is a directory
			if ((curEntry->attribute & DA_DIR) == DA_DIR)
			{
				// this entry is a dir, recursive call
				if (readDirEntryInfo(head, curEntry->startBlock) == -1)
					return -1;
			}
		}

		// try next entry
		curEntry = (struct directory *)((unsigned long)curEntry + sizeof(struct directory));
	}

	if (noMore == 1)
		break;

	// done checking current block, go to the next block
	curBlock = (struct diskBlock *)curBlock->nextBlock;
  }

  return 0;
}



/*************************************************************
Fuction : clearDirEntryInfo
	clear the directory entry information list
Input:
	head - the head of the entry information list
Output:
	none
**************************************************************/
void clearDirEntryInfo(struct entryInfo *head)
{
  struct entryInfo *current;
  struct entryInfo *next;

  current = (struct entryInfo *)(head->next);
  while (current != NULL)
  {
	next = (struct entryInfo *)(current->next);

	ap_free(current);

	current = next;
  }

  return;
}



/*************************************************************
Fuction : eLInsert
	insert an entry information into the information list
Input:
	head - the head of the entry information list
	entry - the target entry
Output:
	none
Note:
	Entries are inserted descendingly according to the
	start block address.
**************************************************************/
void eLInsert(struct entryInfo *head, struct entryInfo *entry)
{
  struct entryInfo *current;
  struct entryInfo *previous;

  current = (struct entryInfo *)(head->next);
  previous = head;

  while (current != NULL)
  {
	if ((unsigned long)((entry->theEntry)->startBlock) > (unsigned long)((current->theEntry)->startBlock))
	{
		// this entry has higher starting block address than the current entry
		// insert this entry before the current entry
		previous->next = (void *)entry;
		entry->prev = (void *)previous;
		entry->next = (void *)current;
		current->prev = (void *)entry;
		return;
	}
	previous = current;
	current = (struct entryInfo *)(current->next);
  }

  // this entry has the smallest starting block address or the list is empty
  previous->next = (void *)entry;
  entry->prev = (void *)previous;

  return;
}



/*************************************************************
Fuction : eLRemove
	remove an entry information node from the information list
Input:
	head - the head of the entry information list
	entry - the target entry
Output:
	none
Note:
	Only the target entry node is removed.
**************************************************************/
void eLRemove(struct entryInfo *head, struct entryInfo *entry)
{
  // remove the target entry
  if (entry->prev != NULL)
	((struct entryInfo *)(entry->prev))->next = entry->next;
  if (entry->next != NULL)
	((struct entryInfo *)(entry->next))->prev = entry->prev;

  ap_free(entry);

  return;
}



/*************************************************************
Fuction : eLUpdate
	update the entry addresses of the entries within a block
	that is a directory block which has been moved
Input:
	head - the head of the entry information list
	block - the starting location of the target block
	offset - the offset of movement
Output:
	none
Note:
**************************************************************/
void eLUpdate(struct entryInfo *head, void *block, long offset)
{
  struct entryInfo *current;
//  struct entryInfo *next;

  current = (struct entryInfo *)(head->next);
  while (current != NULL)
  {
	if (((unsigned long)(current->theEntry) >= (unsigned long)block) && ((unsigned long)(current->theEntry) < (unsigned long)block + DIR_BLOCK_SIZE))
		current->theEntry = (struct directory *)((unsigned long)current->theEntry + offset);
	current = (struct entryInfo *)(current->next);
  }

  return;
}



/*************************************************************
Fuction : pLInsert
	insert a piece information into the information list
Input:
	head - the head of the piece information list
	piece - the target piece information
Output:
	none
Note:
	Piece info are inserted ascendingly according to the
	start piece address.
**************************************************************/
void pLInsert(struct pieceInfo *head, struct pieceInfo *pieceInfo)
{
  struct pieceInfo *current;
  struct pieceInfo *previous;

  current = (struct pieceInfo *)(head->next);
  previous = head;

  while (current != NULL)
  {
	if (pieceInfo->piece < current->piece)
	{
		// this piece has lower starting block address than the current piece
		// insert this piece before the current piece
		previous->next = (void *)pieceInfo;
		pieceInfo->next = (void *)current;

		return;
	}

	previous = current;
	current = (struct pieceInfo *)(current->next);
  }

  // this piece has the highest starting block address or the list is empty
  previous->next = (void *)pieceInfo;

  return;
}



/*************************************************************
Fuction : clearPieceInfo
	clear the  information list
Input:
	head - the head of the entry information list
Output:
	none
**************************************************************/
void clearPieceInfo(struct pieceInfo *head)
{
  struct pieceInfo *current;
  struct pieceInfo *next;

  current = (struct pieceInfo *)(head->next);
  while (current != NULL)
  {
	next = (struct pieceInfo *)(current->next);

	ap_free(current);

	current = next;
  }

  return;