uffs_tree.c

nandflash文件系统源代码

{
	int hash;
	TreeNode *node;
	struct uffs_treeSt *tree = &(dev->tree);
	u16 x;

	hash = GET_DATA_HASH(father, serial);
	x = tree->dataEntry[hash];
	while(x != EMPTY_NODE) {
		node = FROM_IDX(x, &(tree->dis));

		if(node->u.data.father == father &&
			node->u.data.serial == serial)
				return node;

		x = node->hashNext;
	}
	return NULL;
}

TreeNode * uffs_FindDirNodeByBlock(uffs_Device *dev, u16 block)
{
	int hash;
	TreeNode *node;
	struct uffs_treeSt *tree = &(dev->tree);
	u16 x;

	for(hash = 0; hash < DIR_NODE_ENTRY_LEN; hash++) {
		x = tree->dirEntry[hash];
		while(x != EMPTY_NODE) {
			node = FROM_IDX(x, &(tree->dis));
			if(node->u.dir.block == block)
				return node;
			x = node->hashNext;
		}
	}
	return NULL;
}

TreeNode * uffs_FindErasedNodeByBlock(uffs_Device *dev, u16 block)
{
	TreeNode *node;
	node = dev->tree.erased;
	while(node) {
		if(node->u.list.block == block) return node;
		node = node->u.list.next;
	}
		
	return NULL;
}

TreeNode * uffs_FindBadNodeByBlock(uffs_Device *dev, u16 block)
{
	TreeNode *node;
	node = dev->tree.bad;
	while(node) {
		if(node->u.list.block == block) return node;
		node = node->u.list.next;
	}
		
	return NULL;
}

TreeNode * uffs_FindFileNodeByBlock(uffs_Device *dev, u16 block)
{
	int hash;
	TreeNode *node;
	struct uffs_treeSt *tree = &(dev->tree);
	u16 x;

	for(hash = 0; hash < FILE_NODE_ENTRY_LEN; hash++) {
		x = tree->fileEntry[hash];
		while(x != EMPTY_NODE) {
			node = FROM_IDX(x, &(tree->dis));
			if(node->u.file.block == block)
				return node;
			x = node->hashNext;
		}
	}
	return NULL;
}

TreeNode * uffs_FindDataNodeByBlock(uffs_Device *dev, u16 block)
{
	int hash;
	TreeNode *node;
	struct uffs_treeSt *tree = &(dev->tree);
	u16 x;

	for(hash = 0; hash < DATA_NODE_ENTRY_LEN; hash++) {
		x = tree->dataEntry[hash];
		while(x != EMPTY_NODE) {
			node = FROM_IDX(x, &(tree->dis));
			if(node->u.data.block == block)
				return node;
			x = node->hashNext;
		}
	}
	return NULL;
}

TreeNode * uffs_FindNodeByBlock(uffs_Device *dev, u16 block, int *region)
{
	TreeNode *node = NULL;
	if(*region & SEARCH_REGION_DATA) {
		node = uffs_FindDataNodeByBlock(dev, block);
		if(node) {
			*region &= SEARCH_REGION_DATA;
			return node;
		}
	}
	if(*region & SEARCH_REGION_FILE) {
		node = uffs_FindFileNodeByBlock(dev, block);
		if(node) {
			*region &= SEARCH_REGION_FILE;
			return node;
		}
	}
	if(*region & SEARCH_REGION_DIR) {
		node = uffs_FindDirNodeByBlock(dev, block);
		if(node) {
			*region &= SEARCH_REGION_DIR;
			return node;
		}
	}
	if(*region & SEARCH_REGION_ERASED) {
		node = uffs_FindErasedNodeByBlock(dev, block);
		if(node) {
			*region &= SEARCH_REGION_ERASED;
			return node;
		}
	}
	if(*region & SEARCH_REGION_BAD) {
		node = uffs_FindBadNodeByBlock(dev, block);
		if(node) {
			*region &= SEARCH_REGION_BAD;
			return node;
		}
	}
	return node;
}

TreeNode * uffs_FindDirNodeByName(uffs_Device *dev, const char *name, u32 len, u16 sum, u16 father)
{
	int i;
	u16 x;
	TreeNode *node;
	struct uffs_treeSt *tree = &(dev->tree);
	
	for(i = 0; i < DIR_NODE_ENTRY_LEN; i++) {
		x = tree->dirEntry[i];
		while(x != EMPTY_NODE) {
			node = FROM_IDX(x, &(tree->dis));
			if(node->u.dir.checkSum == sum && node->u.dir.father == father) {
				//read file name from flash, and compare...
				if(uffs_CompareFileNameWithTreeNode(dev, name, len, sum, node, UFFS_TYPE_DIR) == U_TRUE) {
					//Got it!
					return node;
				}
			}
			x = node->hashNext;
		}
	}
	return NULL;

}

UBOOL uffs_CompareFileName(const char *src, int src_len, const char *des)
{
	while(src_len-- > 0) {
		if(*src++ != *des++) return U_FALSE;
	}
	return U_TRUE;
}

UBOOL uffs_CompareFileNameWithTreeNode(uffs_Device *dev, const char *name, u32 len, u16 sum, TreeNode *node, int type)
{
	u16 page;
	uffs_blockInfo *bc;
	uffs_Tags *tag;
	URET ret = U_FAIL;
	uffs_fileInfo fi;
	u16 block;

	if (type == UFFS_TYPE_DIR)
		block = node->u.dir.block;
	else
		block = node->u.file.block;

	bc = uffs_GetBlockInfo(dev, block);

	if(bc == NULL) {
		uffs_Perror(UFFS_ERR_SERIOUS, PFX"can't get block info %d\n", block);
		return U_FALSE;
	}

	//dir|file name must resident in pageID == 0
	uffs_LoadBlockInfo(dev, bc, UFFS_ALL_PAGES);
	page = uffs_FindBestPageInBlock(dev, bc, 0);

	tag = &(bc->spares[page].tag);
	if(tag->dataSum != sum) {
		uffs_Perror(UFFS_ERR_NORMAL, PFX"the obj's sum in tag is different with given sum!\n");
		uffs_PutBlockInfo(dev, bc);
		return U_FALSE;
	}

	ret = dev->ops->ReadPageData(dev, block, page, (u8 *)(&fi), 0, sizeof(uffs_fileInfo));
	if(ret == U_FAIL) {
		uffs_PutBlockInfo(dev, bc);
		uffs_Perror(UFFS_ERR_SERIOUS, PFX"I/O error ?\n");
		return U_FALSE;
	}

	if(fi.name_len == len) {
		if(uffs_CompareFileName(fi.name, fi.name_len, name) == U_TRUE) {
			uffs_PutBlockInfo(dev, bc);
			return U_TRUE;
		}
	}

	uffs_PutBlockInfo(dev, bc);
	return U_FALSE;
}


/* calculate file length */
static URET _BuildTreeStepThree(uffs_Device *dev)
{
	int i;
	u16 x;
	TreeNode *work;
	TreeNode *node;
	struct uffs_treeSt *tree;
	struct ubufm *dis;
	u16 blockSave;

	TreeNode *cache = NULL;
	u16 cacheSerial = INVALID_UFFS_SERIAL;


	//FIX ME!! a cache system MUST be designed to accelerate this procedure
	//FIX ME!! otherwise a huge file nodes or data nodes would drag system from fast booting

	tree = &(dev->tree);
	dis = &(tree->dis);

	uffs_Perror(UFFS_ERR_NOISY, PFX"build tree step three\n");

	for(i = 0; i < DATA_NODE_ENTRY_LEN; i++) {
		x = tree->dataEntry[i];
		while(x != EMPTY_NODE) {
			work = FROM_IDX(x, dis);
			if(work->u.data.father == cacheSerial) {
				node = cache;
			}
			else {
				node = uffs_FindFileNodeFromTree(dev, work->u.data.father);
				cache = node;
				cacheSerial = work->u.data.father;
			}
			if(node == NULL) {
				x = work->hashNext;
				//this data block do not belong any file ?
				//should be erased.
				uffs_Perror(UFFS_ERR_NORMAL, PFX"find a orphan data block:%d, father:%d, serial:%d, will be erased!\n", 
					work->u.data.block, work->u.data.father, work->u.data.serial);
				uffs_BreakFromEntry(dev, UFFS_TYPE_DATA, work);
				blockSave = work->u.data.block;
				work->u.list.block = blockSave;
				dev->ops->EraseBlock(dev, blockSave);
				uffs_InsertToErasedListTail(dev, work);
			}
			else {
				node->u.file.len += work->u.data.len;
				x = work->hashNext;
			}
		}
	}

	return U_SUCC;
}

/** 
 * \brief build tree structure from flash
 * \param[in] dev uffs device
 */
URET uffs_BuildTree(uffs_Device *dev)
{
	URET ret;

	/***** step one: scan all page spares, classify DIR/FILE/DATA nodes,
			check bad blocks/uncompleted(conflicted) blocks as well *****/
	/* if the disk is big and full filled of data this step could be the most time consuming .... */
	ret = _BuildTreeStepOne(dev);
	if(ret != U_SUCC) {
		uffs_Perror(UFFS_ERR_SERIOUS, PFX"build tree step one fail!\n");
		return ret;
	}

	/***** step two: randomize the erased blocks, for ware-leveling purpose *****/
	/* this step is very fast :) */
	ret = _BuildTreeStepTwo(dev);
	if(ret != U_SUCC) {
		uffs_Perror(UFFS_ERR_SERIOUS, PFX"build tree step two fail!\n");
		return ret;
	}

	/***** step three: check DATA nodes, find orphan nodes and erase them *****/
	/* if there are a lot of files and disk is fully filled, this step could be very time consuming ... */
	ret = _BuildTreeStepThree(dev);
	if(ret != U_SUCC) {
		uffs_Perror(UFFS_ERR_SERIOUS, PFX"build tree step three fail!\n");
		return ret;
	}
	
	return U_SUCC;
}

/** 
 * find a free file or dir serial NO
 * \param[in] dev uffs device
 * \return if no free serial found, return #INVALID_UFFS_SERIAL
 */
u16 uffs_FindFreeFsnSerial(uffs_Device *dev)
{
	u16 i;
	TreeNode *node;

	//TODO!! Do we need a faster serial number generating method?
	//		 it depends on how often creating files or directories

	for(i = ROOT_DIR_ID + 1; i < MAX_UFFS_SERIAL; i++) {
		node = uffs_FindDirNodeFromTree(dev, i);
		if(node == NULL) {
			node = uffs_FindFileNodeFromTree(dev, i);
			if(node == NULL) return i;
		}
	}
	return INVALID_UFFS_SERIAL;
}

TreeNode * uffs_GetErased(uffs_Device *dev)
{
	TreeNode *node = NULL;
	if(dev->tree.erased) {
		node = dev->tree.erased;
		dev->tree.erased->u.list.prev = NULL;
		dev->tree.erased = dev->tree.erased->u.list.next;
		if(dev->tree.erased == NULL) dev->tree.erased_tail = NULL;
	}
	dev->tree.erasedCount--;

	return node;
}

static void _InsertToEntry(uffs_Device *dev, u16 *entry, int hash, TreeNode *node)
{
	struct uffs_treeSt *tree = &(dev->tree);

	node->hashNext = entry[hash];
#ifdef TREE_NODE_USE_DOUBLE_LINK
	node->hashPrev = EMPTY_NODE;
	if(entry[hash] != EMPTY_NODE) {
		FROM_IDX(entry[hash], &(tree->dis))->hashPrev = TO_IDX(node, &(tree->dis));
	}
#endif
	entry[hash] = TO_IDX(node, &(tree->dis));
}

//static void _BreakFromEntry(uffs_Device *dev, u16 *entry, int hash, TreeNode *node)
//{
//	TreeNode *work;
//	struct uffs_treeSt *tree = &(dev->tree);
//	struct ubufm *dis = &(tree->dis);
//	
//	if(node->hashPrev != EMPTY_NODE) {
//		work = FROM_IDX(node->hashPrev, dis);
//		work->hashNext = node->hashNext;
//	}
//	if(node->hashNext != EMPTY_NODE) {
//		work = FROM_IDX(node->hashNext, dis);
//		work->hashPrev = node->hashPrev;
//	}
//	if(entry[hash] == TO_IDX(node, dis)) {
//		entry[hash] = node->hashNext;
//	}
//}

#ifndef TREE_NODE_USE_DOUBLE_LINK
TreeNode * _FindPrevNodeFromEntry(uffs_Device *dev, u16 start, u16 find)
{
	TreeNode *work;
	while (start != EMPTY_NODE) {
		work = FROM_IDX(start, &(dev->tree.dis));
		if (work->hashNext == find) {
			return work;
		}
	}
	return NULL;
}
#endif

/** 
 * break the node from entry
 */
void uffs_BreakFromEntry(uffs_Device *dev, u8 type, TreeNode *node)
{
	u16 *entry;
	int hash;
	TreeNode *work;

	switch(type) {
	case UFFS_TYPE_DIR:
		hash = GET_DIR_HASH(node->u.dir.serial);
		entry = &(dev->tree.dirEntry[hash]);
		break;
	case UFFS_TYPE_FILE:
		hash = GET_FILE_HASH(node->u.file.serial);
		entry = &(dev->tree.fileEntry[hash]);
		break;
	case UFFS_TYPE_DATA:
		hash = GET_DATA_HASH(node->u.data.father, node->u.data.serial);
		entry = &(dev->tree.dataEntry[hash]);
		break;
	default:
		uffs_Perror(UFFS_ERR_SERIOUS, PFX"unknown type when break...\n");
		return;
	}
#ifdef TREE_NODE_USE_DOUBLE_LINK
	if(node->hashPrev != EMPTY_NODE) {
		work = FROM_IDX(node->hashPrev, &(dev->tree.dis));
		work->hashNext = node->hashNext;
	}
	if(node->hashNext != EMPTY_NODE) {
		work = FROM_IDX(node->hashNext, &(dev->tree.dis));
		work->hashPrev = node->hashPrev;
	}
#else
	if ((work = _FindPrevNodeFromEntry(dev, *entry, TO_IDX(node, &(dev->tree.dis)))) != NULL) {
		work->hashNext = node->hashNext;
	}
#endif

	if(*entry == TO_IDX(node, &(dev->tree.dis))) {
		*entry = node->hashNext;
	}
}

static void uffs_InsertToFileEntry(uffs_Device *dev, TreeNode *node)
{
	_InsertToEntry(dev, dev->tree.fileEntry, GET_FILE_HASH(node->u.file.serial), node);
}

static void uffs_InsertToDirEntry(uffs_Device *dev, TreeNode *node)
{
	_InsertToEntry(dev, dev->tree.dirEntry, GET_DIR_HASH(node->u.dir.serial), node);
}

static void uffs_InsertToDataEntry(uffs_Device *dev, TreeNode *node)
{
	_InsertToEntry(dev, dev->tree.dataEntry, GET_DATA_HASH(node->u.data.father, node->u.data.serial), node);
}

void uffs_InsertToErasedListHead(uffs_Device *dev, TreeNode *node)
{
	struct uffs_treeSt *tree;
	tree = &(dev->tree);

	node->u.list.next = tree->erased;
	node->u.list.prev = NULL;
	if(tree->erased) {
		tree->erased->u.list.prev = node;
	}

	tree->erased = node;
	if(node->u.list.next == tree->erased_tail) {
		tree->erased_tail = node;
	}
	tree->erasedCount++;
}

void uffs_InsertToErasedListTail(uffs_Device *dev, TreeNode *node)
{
	struct uffs_treeSt *tree;
	tree = &(dev->tree);

	node->u.list.next = NULL;
	node->u.list.prev = tree->erased_tail;
	if(tree->erased_tail) {
		tree->erased_tail->u.list.next = node;
	}

	tree->erased_tail = node;
	if(tree->erased == NULL) {
		tree->erased = node;
	}
	tree->erasedCount++;
}

void uffs_InsertToBadBlockList(uffs_Device *dev, TreeNode *node)
{
	struct uffs_treeSt *tree;
	tree = &(dev->tree);
	node->u.list.prev = NULL;
	node->u.list.next = tree->bad;
	if(tree->bad) {
		tree->bad->u.list.prev = node;
	}
	tree->bad = node;
	tree->badCount++;
}

/** 
 * set tree node block value
 */
void uffs_SetTreeNodeBlock(u8 type, TreeNode *node, u16 block)
{
	switch(type) {
	case UFFS_TYPE_FILE:
		node->u.file.block = block;
		break;
	case UFFS_TYPE_DIR:
		node->u.dir.block = block;
		break;
	case UFFS_TYPE_DATA:
		node->u.data.block = block;
		break;
	}
}