diff --git a/src/sys/ubixfsv2/Makefile b/src/sys/ubixfsv2/Makefile new file mode 100644 index 0000000..0e4f7e2 --- /dev/null +++ b/src/sys/ubixfsv2/Makefile @@ -0,0 +1,50 @@ +# $Id$ +# Application Makefile (C) 2002-2004 The UbixOS Project + +#Linker +LD = ld + +#Binary File Name +BINARY = ubixfs + +#Delete Program +REMOVE = rm -f + +#Objects +OBJS = main.o vfs.o ubixfs.o btree.o + +#Includes +INCLUDES = -I./include -I./ + +#CFLAGS + +CFLAGS = -O + +all: $(BINARY) + +# Link The Binary +$(BINARY) : $(OBJS) + $(CXX) $(CFLAGS) -o $@ $(OBJS) + +# Compile the source files +.cpp.o: + $(CXX) -ggdb -W -Wall $(CFLAGS) $(INCLUDES) -c -o $@ $< + +.cc.o: + $(CXX) -W -Wall $(CFLAGS) $(INCLUDES) -c -o $@ $< + +.cc.s: + $(CXX) -W -Wall $(CFLAGS) $(INCLUDES) -S -o $@ $< + +.c.o: + $(CC) -W -Wall $(CFLAGS) $(INCLUDES) -c -o $@ $< + +.c.s: + $(CC) -W -Wall $(CFLAGS) $(INCLUDES) -S -o $@ $< + +.S.o: + $(CC) -Wall $(CLFAGS) $(INCLUDES) -c -o $@ $< + +# Clean Up The junk +clean: + $(REMOVE) $(OBJS) $(BINARY) *.core diff --git a/src/sys/ubixfsv2/btree.cpp b/src/sys/ubixfsv2/btree.cpp new file mode 100644 index 0000000..71e03fd --- /dev/null +++ b/src/sys/ubixfsv2/btree.cpp @@ -0,0 +1,381 @@ +// http://www.cs.msstate.edu/~cs2314/global/BTreeAnimation/algorithm.html +#include +#include +#include +#include "btree.h" +#include "inode.h" +#include "assert.h" + + +bTree::bTree(ubixfsInode * inode) : root(NULL) { + if (inode == NULL) return; + root = allocEmptyNode(); + if (root == NULL) return; + root->used = 1; + root->parent = NULL; + root->leafNode = true; + root->childCount[1] = 1; + +cout << "---Creating " << inode->name << "---" << endl; + strncpy(root->keys[0], inode->name, B_MAX_NAME_LENGTH); + // insert pointer to data page to the right of the data + root->childHead[1] = (void *)inode; + root->childTail[1] = (void *)inode; + + root->present[1] = true; + if (inode != NULL) { + inode->next = inode->prev = NULL; + } // if + return; +} // bTree:bTree + +bool +bTree::Insert(ubixfsInode * inode) { + bNode * bnode = root; + ubixfsInode * tmpInode = NULL; + unsigned int curSlot = 0; + + if (bnode == NULL || inode == NULL) return false; + + /* + * Find the leaf node the inode goes into + */ + assert(bnode->used); + + while (bnode != NULL && !bnode->leafNode) { + if (strcmp(inode->name, bnode->keys[0] < 0)) + bnode = (bNode *)bnode->childHead[0]; + else + if (strcmp(inode->name, bnode->keys[bnode->used-1]) >= 0) + bnode = (bNode *)bnode->childHead[bnode->used]; + else { + for (unsigned int i = 1; i < bnode->used; i++) { + if (strcmp(inode->name, bnode->keys[i]) < 0) { + bnode = (bNode *)bnode->childHead[i]; + break; + } // if + } // for i + } // else + } // while + + /* + * + */ +cout << "--used: " << bnode->used << endl; + if (strcmp(inode->name, bnode->keys[curSlot = 0]) < 0) + tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; + else + if (strcmp(inode->name, bnode->keys[(curSlot = bnode->used)-1]) >= 0) + tmpInode = (ubixfsInode *)bnode->childHead[bnode->used]; + else { +cout << "used: " << bnode->used << endl; + for (curSlot = 1; curSlot < bnode->used; curSlot++) { +cout << inode->name << " ~~ " << bnode->keys[curSlot] << endl; + if (strcmp(inode->name, bnode->keys[curSlot]) < 0) { + tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; + break; + } // if + } // for curSlot + tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; + } // else + + if (tmpInode == NULL) { + /* + * This is the first node in this leaf + */ + bnode->childHead[curSlot] = bnode->childTail[curSlot] = inode; + bnode->present[curSlot] = true; + + if (curSlot == 0) { + + if (bnode->childHead[1] != NULL) { + ubixfsInode * iptr = (ubixfsInode *)bnode->childHead[1]; + inode->prev = iptr->prev; + inode->next = iptr; + iptr->prev = inode; + if (inode->prev != NULL) inode->prev->next = inode; + } else { + inode->next = inode->prev = NULL; + } // else + + } else { + ++bnode->used; + } + + } else { + /* + * Add node to leaf page. Scan through to find where it goes. + */ + + if (strcmp(inode->name, ((ubixfsInode *)bnode->childHead[curSlot])->name) < 0) + { + inode->next = (ubixfsInode *)bnode->childHead[curSlot]; + inode->prev = inode->next->prev; + inode->next->prev = inode; + if (inode->prev != NULL) inode->prev->next = inode; + bnode->childHead[curSlot] = (void *)inode; + } else + if (strcmp(inode->name, ((ubixfsInode *)bnode->childTail[curSlot])->name) > 0) { + inode->prev = (ubixfsInode *)bnode->childTail[curSlot]; + inode->next = inode->prev->next; + inode->prev->next = inode; + if (inode->next != NULL) inode->next->prev = inode; + bnode->childTail[curSlot] = inode; + } else { + ubixfsInode * tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; + for (unsigned int i = 1; i < bnode->childCount[curSlot]; i++) { +// cout << "strcmp(" << inode->name << ", " << tmpInode->name << ") == " << +// strcmp(inode->name, tmpInode->name) << endl; + if (strcmp(inode->name, tmpInode->name) < 0) { + inode->next = tmpInode; + inode->prev = tmpInode->prev; + inode->next->prev = inode; + inode->prev->next = inode; + break; + } // if + tmpInode = tmpInode->next; + } // for i + } // else + } // else + + if (++bnode->childCount[curSlot] == B_MAX_CHILD_COUNT) { + cout << "slot[" << curSlot << "] is full" << endl; + cout << "slot[" << curSlot+1 << "]->childCount is: " << bnode->childCount[curSlot+1] << endl; +cout << "---- before split ----" << endl; + Info(); + if (curSlot != bnode->used) { + int shift = bnode->used - curSlot +1; +cout << "shift: " << shift << endl; + memmove(&bnode->childHead[curSlot+1], + &bnode->childHead[curSlot], + sizeof(bnode->childHead[0]) * shift); + memmove(&bnode->childTail[curSlot+1], + &bnode->childTail[curSlot], + sizeof(bnode->childTail[0]) * shift); + memmove(&bnode->present[curSlot+1], + &bnode->present[curSlot], + sizeof(bnode->present[0]) * shift); + memmove(&bnode->childCount[curSlot+1], + &bnode->childCount[curSlot], + sizeof(bnode->childCount[0]) * shift); + + memmove(&bnode->keys[curSlot+1], + &bnode->keys[curSlot], + sizeof(bnode->keys[0]) * (shift-1)); + memset(bnode->keys[curSlot], 0, B_MAX_NAME_LENGTH); + } else { + bnode->childHead[curSlot+1] = bnode->childHead[curSlot]; + bnode->childTail[curSlot+1] = bnode->childTail[curSlot]; + bnode->childCount[curSlot+1] = bnode->childCount[curSlot]; + bnode->present[curSlot+1] = bnode->present[curSlot]; + } // else + + ubixfsInode * tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; + assert(tmpInode); + for (unsigned int i = 0; i < (B_MAX_CHILD_COUNT+1) >> 1; i++) { + tmpInode = tmpInode->next; + } // for i + + strncpy(bnode->keys[curSlot], tmpInode->name, B_MAX_NAME_LENGTH); + bnode->childHead[curSlot+1] = (void *)tmpInode; + bnode->childTail[curSlot] = (void *)tmpInode->prev; + bnode->childCount[curSlot] = (B_MAX_CHILD_COUNT+1) >> 1; + bnode->childCount[curSlot+1] -= bnode->childCount[curSlot]; + bnode->present[curSlot] = true; + ++bnode->used; +cout << "--- After split ---" << endl; +Info(); + } // if leaf is full + + return true; +} // bTree::Insert + +void +bTree::splitNode(bNode * oldNode) { + assert(oldNode); + if (oldNode == NULL) return; + if (oldNode->used != B_MAX_KEYS) return; + + bNode * newNode = allocEmptyNode(); + if (newNode == NULL) return; + + unsigned int splitLoc = (B_MAX_KEYS+1) >> 1; + unsigned int shift = B_MAX_KEYS - splitLoc; + + newNode->used = (B_MAX_KEYS+1) >> 1; + newNode->parent = oldNode->parent; + newNode->leafNode = oldNode->leafNode; + + memcpy(&newNode->keys[0], + &oldNode->keys[splitLoc], + sizeof(newNode->keys[0]) * shift); + + memset(&oldNode->keys[splitLoc], 0, sizeof(newNode->keys[0]) * shift); + + memcpy(&newNode->present[0], + &oldNode->present[splitLoc], + sizeof(newNode->present[0]) * shift); + + memset(&oldNode->present[splitLoc], 0, sizeof(newNode->present[0]) * shift); + + memcpy(&newNode->childHead[0], + &oldNode->childHead[splitLoc], + sizeof(newNode->childHead[0]) * shift); + + memset(&oldNode->childHead[splitLoc], 0, sizeof(newNode->childHead[0]) * shift); + + memcpy(&newNode->childTail[0], + &oldNode->childTail[splitLoc], + sizeof(newNode->childTail[0]) * shift); + + memset(&oldNode->childTail[splitLoc], 0, sizeof(newNode->childTail[0]) * shift); + + memcpy(&newNode->childCount[0], + &oldNode->childCount[splitLoc], + sizeof(newNode->childCount[0]) * shift); + + memset(&oldNode->childCount[splitLoc], 0, sizeof(newNode->childCount[0]) * shift); + + if (oldNode == root) { + // allocate a new root node + root = allocEmptyNode(); + oldNode->parent = root; + newNode->parent = root; + strncpy(root->keys[0], newNode->keys[0], B_MAX_NAME_LENGTH); + root->childHead[0] = oldNode; + root->childTail[0] = root->childTail[1] = NULL; + root->childHead[1] = newNode; + root->used = 1; + root->leafNode = false; + root->present[0] = root->present[1] = true; + root->childCount[0] = oldNode->used; + root->childCount[1] = newNode->used; + } else { + if (++oldNode->parent->used == B_MAX_KEYS) splitNode(oldNode->parent); + } // esle + return; +} // bTree::splitNode + +bNode * +bTree::allocEmptyNode(void) { + bNode * newNode = (bNode *)malloc(sizeof(bNode)); + + memset(newNode, 0, sizeof(bNode)); + newNode->magic1 = B_NODE_MAGIC_1; + newNode->magic2 = B_NODE_MAGIC_2; + + return newNode; +} // bTree::allocEmptyNode + +void +bTree::Info(void) { + ubixfsInode * inode = NULL; + if (root == NULL) return; + cout << "root->used: " << root->used << endl; + for (unsigned int i = 0; i <= root->used; i++) { + inode = (ubixfsInode *)root->childHead[i]; +cout << "root->childCount[i]: " << root->childCount[i] << endl; + for (unsigned int j = 0; j < root->childCount[i]; j++) { + assert(inode); + cout << "[" << i << "].[" << j << "]->" << inode->name << endl; + inode = inode->next; + } // for j + } // for i + +} // bTree::Info + +void +bTree::Print(void) { + ubixfsInode * node = GetFirstNode(); + while (node != NULL) { + cout << node->name << endl; + node = node->next; + } +} // bTree::Print + +ubixfsInode * +bTree::Find(const char * key) { + return treeSearch(root, key); +} // bTree::Find + +ubixfsInode * +bTree::inodeSearch(ubixfsInode * inode, const char * key) { + if (inode == NULL || key == NULL) return NULL; + int result = strcmp(inode->name, key); + if (result == 0) return inode; + + if (result < 0) { + inode = inode->next; + while (inode != NULL && (result = strcmp(inode->name, key) >= 0)) { + inode = inode->next; + } // while + } else { + inode = inode->prev; + while (inode != NULL && (result = strcmp(inode->name, key) <= 0)) { + inode = inode->prev; + } // while + } // else + return (result == 0 ? inode : NULL); +} // bTree::inodeSearch + +ubixfsInode * +bTree::treeSearch(bNode * bnode, const char * key) { + + if (bnode == NULL || key == NULL) return NULL; + + if (bnode->used == 0) return NULL; + if (bnode->leafNode) + if (bnode->childHead[0] != NULL) + return inodeSearch((ubixfsInode *)bnode->childHead[0], key); + else + return inodeSearch((ubixfsInode *)bnode->childHead[1], key); + +cout << "key: " << key << " keys[0]: " << bnode->keys[0] << " result: " << strcmp(key, bnode->keys[0]) << endl; + if (strcmp(key, bnode->keys[0]) < 0) + return treeSearch((bNode *)bnode->childHead[0], key); + + if (strcmp(key, bnode->keys[bnode->used-1]) >= 0) + return treeSearch((bNode *)bnode->childHead[bnode->used], key); + + for (unsigned int i = 1; i < bnode->used; i++) { + if (strcmp(key, bnode->keys[i]) < 0) + return treeSearch((bNode *)bnode->childHead[i], key); + } // for i + + return NULL; +} // bTree::treeSearch + +ubixfsInode * +bTree::GetFirstNode(void) { + bNode * tmpNode = root; + if (tmpNode == NULL) return NULL; + + if (root->leafNode) { + if (root->used == 0) return NULL; + if (root->used == 1 && root->childHead[0] == NULL) + return (ubixfsInode *) root->childHead[1]; + else + return (ubixfsInode *) root->childHead[0]; + } // if + while (!tmpNode->leafNode) tmpNode = (bNode *)tmpNode->childHead[0]; + return (ubixfsInode *)tmpNode->childHead[0]; +} // bTree::GetFirstNode + +bool +bTree::Save(const char * filename) { + if (filename == NULL) return false; + return true; +} // bTree::Save + +bool +bTree::Load(const char * filename) { + if (filename == NULL) return false; + return true; +} // bTree::Load + +bool +bTree::Delete(const char * key) { + + if (key == NULL) return false; + return true; +} // bTree::Delete diff --git a/src/sys/ubixfsv2/btree.h b/src/sys/ubixfsv2/btree.h new file mode 100644 index 0000000..00c6e38 --- /dev/null +++ b/src/sys/ubixfsv2/btree.h @@ -0,0 +1,47 @@ +#ifndef BTREE_H +#define BTREE_H + +#include "superblock.h" +#include "inode.h" + +#define B_NODE_MAGIC_1 0xDEADBEEF +#define B_NODE_MAGIC_2 0x1900BABE + +#define B_MAX_KEYS 14 +#define B_MAX_NAME_LENGTH 256 +#define B_MAX_CHILD_COUNT 4 + +typedef struct bNode { + uInt32 magic1 __attribute__ ((packed)); + uInt32 used __attribute__ ((packed)); + char keys[B_MAX_KEYS][B_MAX_NAME_LENGTH] __attribute__ ((packed)); + bool present[B_MAX_KEYS] __attribute__ ((packed)); + void * childHead[(B_MAX_KEYS+1)*8/sizeof(void *)] __attribute__ ((packed)); + void * childTail[(B_MAX_KEYS+1)*8/sizeof(void *)] __attribute__ ((packed)); + uInt32 childCount[B_MAX_KEYS+1] __attribute__ ((packed)); + bNode * parent __attribute__ ((packed)); + bool leafNode __attribute__ ((packed)); + uInt32 magic2 __attribute__ ((packed)); +} bNode; // bNode + +class bTree { + protected: + bNode * root; + ubixfsInode * treeSearch(bNode *, const char *); + ubixfsInode * inodeSearch(ubixfsInode *, const char *); + void splitNode(bNode *); + bNode * allocEmptyNode(void); + public: + bTree(ubixfsInode *); + bTree(void) : root(NULL) { }; + ubixfsInode * Find(const char *); + ubixfsInode * GetFirstNode(void); + bool Delete(const char *); + void Info(void); + bool Insert(ubixfsInode *); + bool Save(const char *); + bool Load(const char *); + void Print(void); + ~bTree(void) { }; +}; // bTree +#endif // !BTREE_H diff --git a/src/sys/ubixfsv2/inode.h b/src/sys/ubixfsv2/inode.h new file mode 100644 index 0000000..7f5931e --- /dev/null +++ b/src/sys/ubixfsv2/inode.h @@ -0,0 +1,52 @@ +#ifndef INODE_H +#define INODE_H + +#include "superblock.h" + +#define INODE_IN_USE 0x00000001 +#define ATTR_INODE 0x00000004 +#define INODE_LOGGED 0x00000008 +#define INODE_DELETED 0x00000010 +#define PERMANENT_FLAGS 0x0000ffff +#define INODE_NO_CACHE 0x00010000 +#define INODE_WAS_WRITTEN 0x00020000 +#define NO_TRANSACTION 0x00040000 + +#define NUM_DIRECT_BLOCKS 12 +#define MAX_FILENAME_LENGTH 256 + +typedef struct dataStream { + blockRun direct[NUM_DIRECT_BLOCKS]; + off_t maxDirectRange; + blockRun indirect; + off_t maxIndirectRange; + blockRun double_indirect; + off_t maxDoubleIndirectRange; + off_t size; +} dataStream; + +typedef struct ubixfsInode { + int32 magic1 __attribute__ ((packed)); + inodeAddr inodeNum __attribute__ ((packed)); + char name[MAX_FILENAME_LENGTH] __attribute__ ((packed)); + int32 uid __attribute__ ((packed)); + int32 gid __attribute__ ((packed)); + int32 mode __attribute__ ((packed)); + int32 flags __attribute__ ((packed)); + // uInt64 createTime __attribute_ ((packed)); + // uInt64 lastModifiedTime __attribute__ (packed)); +// inodeAddr attributes __attribute__ ((packed)); + uInt32 type __attribute__ ((packed)); + int32 inodeSize __attribute__ ((packed)); + ubixfsInode * parentBigPtr __attribute__ ((packed)); + ubixfsInode * parent __attribute__ ((packed)); + ubixfsInode * nextBigPtr __attribute__ ((packed)); + ubixfsInode * next __attribute__ ((packed)); + ubixfsInode * prevBigPtr __attribute__ ((packed)); + ubixfsInode * prev __attribute__ ((packed)); +// binodeEtc *etc ?? + dataStream data __attribute__ ((packed)); + int32 pad[4] __attribute__ ((packed)); + int32 smallData[1] __attribute__ ((packed)); +} ubixfsInode; +#endif diff --git a/src/sys/ubixfsv2/main.cpp b/src/sys/ubixfsv2/main.cpp new file mode 100644 index 0000000..2c1fc90 --- /dev/null +++ b/src/sys/ubixfsv2/main.cpp @@ -0,0 +1,88 @@ +#include +#include +#include "inode.h" +#include "superblock.h" +#include "vfs.h" +#include "btree.h" + +using namespace std; + +int +main(void) { + int i = 0; + ubixfsInode * inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); + memset(inode, 0, sizeof(ubixfsInode)); + strcpy(inode -> name, "h"); + bTree * tree = new bTree(inode); + + inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); + memset(inode, 0, sizeof(ubixfsInode)); + strcpy(inode->name, "m"); +cout << "---Inserting " << inode->name << "---" << endl; + tree->Insert(inode); + + inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); + memset(inode, 0, sizeof(ubixfsInode)); + strcpy(inode->name, "a"); +cout << "---Inserting " << inode->name << "---" << endl; + tree->Insert(inode); + + inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); + memset(inode, 0, sizeof(ubixfsInode)); + strcpy(inode->name, "b"); +cout << "---Inserting " << inode->name << "---" << endl; + tree->Insert(inode); + + inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); + memset(inode, 0, sizeof(ubixfsInode)); + strcpy(inode->name, "c"); +cout << "---Inserting " << inode->name << "---" << endl; + tree->Insert(inode); + + inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); + memset(inode, 0, sizeof(ubixfsInode)); + strcpy(inode->name, "d"); +cout << "---Inserting " << inode->name << "---" << endl; + tree->Insert(inode); + + inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); + memset(inode, 0, sizeof(ubixfsInode)); + strcpy(inode->name, "e"); +cout << "---Inserting " << inode->name << "---" << endl; + tree->Insert(inode); + + inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); + memset(inode, 0, sizeof(ubixfsInode)); + strcpy(inode->name, "f"); +cout << "---Inserting " << inode->name << "---" << endl; + tree->Insert(inode); + + inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); + memset(inode, 0, sizeof(ubixfsInode)); + strcpy(inode->name, "g"); +cout << "---Inserting " << inode->name << "---" << endl; + tree->Insert(inode); + + inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); + memset(inode, 0, sizeof(ubixfsInode)); + strcpy(inode->name, "j"); +cout << "---Inserting " << inode->name << "---" << endl; + tree->Insert(inode); + + inode = (ubixfsInode *)malloc(sizeof(ubixfsInode)); + memset(inode, 0, sizeof(ubixfsInode)); + strcpy(inode->name, "n"); +cout << "---Inserting " << inode->name << "---" << endl; + tree->Insert(inode); + + ubixfsInode * tmpInode = tree->GetFirstNode(); + if (tmpInode == NULL) cout << "GetFirstNode() returns null" << endl; + while (tmpInode != NULL) { + cout << "node[" << i++ << "]: " << tmpInode->name << endl; + tmpInode = tmpInode->next; + } // while + cout << sizeof(struct bNode) << endl; + tree->Info(); + free(inode); + return 0; +} diff --git a/src/sys/ubixfsv2/origbtree.cpp b/src/sys/ubixfsv2/origbtree.cpp new file mode 100644 index 0000000..08aafbc --- /dev/null +++ b/src/sys/ubixfsv2/origbtree.cpp @@ -0,0 +1,503 @@ +// http://www.cs.msstate.edu/~cs2314/global/BTreeAnimation/algorithm.html +#include +#include +#include +#include "btree.h" +#include "inode.h" +#include "assert.h" + + +bTree::bTree(ubixfsInode * inode) : root(NULL) { + if (inode == NULL) return; + root = (bNode *)malloc(sizeof(bNode)); + if (root == NULL) return; + memset(root, 0, sizeof(bNode)); + root->magic1 = B_NODE_MAGIC_1; + root->magic2 = B_NODE_MAGIC_2; + root->used = 1; + root->parent = NULL; + root->leafNode = true; + root->childCount[1] = 1; + + strncpy(root->keys[0], inode->name, B_MAX_NAME_LENGTH); + // insert pointer to data page to the right of the data + root->childHead[1] = (void *)inode; + root->childTail[1] = (void *)inode; + + root->present[1] = true; + if (inode != NULL) { + inode->next = inode->prev = NULL; + } // if + return; +} // bTree:bTree + +bool +bTree::Insert(ubixfsInode * inode) { + bNode * bnode = root; + ubixfsInode * tmpInode = NULL; + unsigned int curSlot = 0; + + if (bnode == NULL || inode == NULL) return false; + + /* + * Find the leaf node the inode goes into + */ + assert(bnode->used); + + while (bnode != NULL && !bnode->leafNode) { + if (strcmp(inode->name, bnode->keys[0] < 0)) + bnode = (bNode *)bnode->childHead[0]; + else + if (strcmp(inode->name, bnode->keys[bnode->used-1]) >= 0) + bnode = (bNode *)bnode->childHead[bnode->used]; + else { + for (unsigned int i = 1; i < bnode->used; i++) { + if (strcmp(inode->name, bnode->keys[i]) < 0) { + bnode = (bNode *)bnode->childHead[i]; + break; + } // if + } // for i + } // else + } // while + + /* + * + */ + + if (strcmp(inode->name, bnode->keys[curSlot = 0]) < 0) + tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; + else + if (strcmp(inode->name, bnode->keys[(curSlot = bnode->used)-1]) >= 0) + tmpInode = (ubixfsInode *)bnode->childHead[bnode->used]; + else { + for (curSlot = 1; curSlot < bnode->used; curSlot++) { + if (strcmp(inode->name, bnode->keys[curSlot] < 0)) { + tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; + break; + } // if + } // for curSlot + } // else + + if (tmpInode == NULL) { + /* + * This is the first node in this leaf + */ + bnode->childHead[curSlot] = bnode->childTail[curSlot] = inode; + bnode->present[curSlot] = true; + + if (curSlot == 0) { + + if (bnode->childHead[1] != NULL) { + ubixfsInode * iptr = (ubixfsInode *)bnode->childHead[1]; + inode->prev = iptr->prev; + inode->next = iptr; + iptr->prev = inode; + if (inode->prev != NULL) inode->prev->next = inode; + } else { + inode->next = inode->prev = NULL; + } // else + + } else { + ++bnode->used; + } + + } else { + /* + * Add node to leaf page. Scan through to find where it goes. + */ + + if (strcmp(inode->name, ((ubixfsInode *)bnode->childHead[curSlot])->name) < 0) + { + inode->next = (ubixfsInode *)bnode->childHead[curSlot]; + inode->prev = inode->next->prev; + inode->next->prev = inode; + if (inode->prev != NULL) inode->prev->next = inode; + bnode->childHead[curSlot] = (void *)inode; + } else + if (strcmp(inode->name, ((ubixfsInode *)bnode->childTail[curSlot])->name) > 0) { + inode->prev = (ubixfsInode *)bnode->childTail[curSlot]; + inode->next = inode->prev->next; + inode->prev->next = inode; + if (inode->next != NULL) inode->next->prev = inode; + bnode->childTail[curSlot] = inode; + } else { + ubixfsInode * tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; + for (unsigned int i = 1; i < bnode->childCount[curSlot]; i++) { +// cout << "strcmp(" << inode->name << ", " << tmpInode->name << ") == " << +// strcmp(inode->name, tmpInode->name) << endl; + if (strcmp(inode->name, tmpInode->name) < 0) { + inode->next = tmpInode; + inode->prev = tmpInode->prev; + inode->next->prev = inode; + inode->prev->next = inode; + break; + } // if + tmpInode = tmpInode->next; + } // for i + } // else + } // else + + if (++bnode->childCount[curSlot] == B_MAX_CHILD_COUNT) { + cout << "slot[" << curSlot << "] is full" << endl; + cout << "slot[" << curSlot+1 << "]->childCount is: " << bnode->childCount[curSlot+1] << endl; +cout << "---- before split ----" << endl; + Info(); + if (curSlot != bnode->used) { + int shift = bnode->used - curSlot; + memmove(&bnode->childHead[curSlot+1], + &bnode->childHead[curSlot], + sizeof(bnode->childHead[0]) * shift); + memmove(&bnode->childTail[curSlot+1], + &bnode->childTail[curSlot], + sizeof(bnode->childTail[0]) * shift); + memmove(&bnode->present[curSlot+1], + &bnode->present[curSlot], + sizeof(bnode->present[0]) * shift); + memmove(&bnode->childCount[curSlot+1], + &bnode->childCount[curSlot], + sizeof(bnode->childCount[0]) * shift); + + memmove(&bnode->keys[curSlot+1], + &bnode->keys[curSlot], + sizeof(bnode->keys[0]) * shift); + memset(bnode->keys[curSlot], 0, B_MAX_NAME_LENGTH); + } else { + bnode->childHead[curSlot+1] = bnode->childHead[curSlot]; + bnode->childTail[curSlot+1] = bnode->childTail[curSlot]; + bnode->childCount[curSlot+1] = bnode->childCount[curSlot]; + bnode->present[curSlot+1] = bnode->present[curSlot]; + } // else + + ubixfsInode * tmpInode = (ubixfsInode *)bnode->childHead[curSlot]; + assert(tmpInode); + for (unsigned int i = 0; i < (B_MAX_CHILD_COUNT+1) >> 1; i++) { + tmpInode = tmpInode->next; + } // for i + + strncpy(bnode->keys[curSlot], tmpInode->name, B_MAX_NAME_LENGTH); + bnode->childHead[curSlot+1] = (void *)tmpInode; + bnode->childTail[curSlot] = (void *)tmpInode->prev; + bnode->childCount[curSlot] = (B_MAX_CHILD_COUNT+1) >> 1; + bnode->childCount[curSlot+1] -= bnode->childCount[curSlot]; + bnode->present[curSlot] = true; + ++bnode->used; +cout << "--- After split ---" << endl; +Info(); + } // if leaf is full + +#if 0 + if (strcmp(inode->name, bnode->key[0]) < 0) { + if (bnode->leafNode) { + + } + } else { + if (strcmp(inode->name, bnode->key[bnode->used]) >= 0) { + } else { + } + } // else + if (bnode->leafNode) { + if + for (unsigned int i = 0; i + } else { + + } // else + + /* + * first search to see if the key we're looking for already exists + * This may not be necessary, since if you've already allocated an + * i-node you might have looked first. But, we'll leave it in as a sanity + * check + */ + + assert(bnode->used); +restart: + for (unsigned int i = 0; i <= tmpNode->used; i++) { + if (i == tmpNode->used) goto skipCheck; +cout << "checking " << inode->name << " against " << tmpNode->keys[i]; + result = strcmp(inode->name, tmpNode->keys[i]); +cout << " result: " << result << endl; + if (result < 0) { + // our key is less than this key. Walk left +skipCheck: + // if we're in leaf nodes, just add it to the data page in the right + // place + if (tmpNode->leafNode) { + ubixfsInode * tmpInode = (ubixfsInode *)tmpNode->childHead[i]; + + // is this the first node in this data page? + if (tmpInode == NULL) { + if (i > 0) + inode->prev = (ubixfsInode *)tmpNode->childTail[i-1]; + else + inode->prev = NULL; + + if (i < B_MAX_KEYS) + inode->next = (ubixfsInode *)tmpNode->childHead[i+1]; + else + inode->next = NULL; + tmpNode->childHead[i] = tmpNode->childTail[i] = inode; + if (i != 0) ++tmpNode->used; + } else { + +cout << "CC[" << i << "]: " << tmpNode->childCount[i] << endl; + for (unsigned int j = 0; j <= tmpNode->childCount[i]; j++) { + if (j == tmpNode->childCount[i]) { + assert(tmpInode); + assert(inode); + inode->prev = tmpInode; + inode->next = tmpInode->next; + tmpInode->next = inode; + // if (inode->next != NULL) inode->next->prev = inode; + tmpNode->childTail[i] = inode; + break; + } // if +assert(inode); +assert(tmpInode); +cout << inode->name << endl; +cout << tmpInode->name << endl; + if (strcmp(inode->name, tmpInode->name) < 0) { + inode->next = tmpInode; + inode->prev = tmpInode->prev; + tmpInode->prev = inode; + if (j == 0) tmpNode->childHead[i] = inode; + break; + } // if +cout << "here2" << endl; + tmpInode = tmpInode->next; +cout << "here3" << endl; + } // for j + + } // else +assert(inode); + if (inode->prev != NULL) inode->prev->next = inode; + if (inode->next != NULL) inode->next->prev = inode; + + if (++tmpNode->childCount[i] == B_MAX_CHILD_COUNT) { + ubixfsInode * tmpInode = (ubixfsInode *)tmpNode->childHead[i]; + assert(tmpInode); + + for (int k = 0; k < ((B_MAX_CHILD_COUNT+1) >> 1); k++) { + tmpInode = (ubixfsInode *)tmpInode->next; + } // for k + +cout << "page is full. splitting. using: " << tmpInode->name << endl; + if (tmpNode->childHead[0] == NULL) { +Print(); +cout << "rotating left" << endl; +cout << "replacing " << tmpNode->keys[0] << " with " << tmpInode->name << endl; + memset(tmpNode->keys[0], 0, B_MAX_NAME_LENGTH); + strncpy(tmpNode->keys[0], tmpInode->name, B_MAX_NAME_LENGTH); + tmpNode->childHead[0] = tmpNode->childHead[1]; + tmpNode->childTail[0] = (void *)tmpInode->prev; + tmpNode->childHead[1] = (void *)tmpInode; +cout << "CC[0]: " << (int)tmpNode->childCount[0] << endl; +cout << "CC[1]: " << (int)tmpNode->childCount[1] << endl; + tmpNode->childCount[0] = (B_MAX_CHILD_COUNT+1) >> 1; + tmpNode->childCount[1] -= tmpNode->childCount[i]; + tmpNode->present[0] = true; +cout << "CC[0]: " << (int)tmpNode->childCount[0] << endl; +cout << "CC[1]: " << (int)tmpNode->childCount[1] << endl; +Print(); + return true; + } + + if (i != tmpNode->used) { + // if we're the last node, don't move things over + // shift denotes how many items to move over + int shift = tmpNode->used - i; +cout << "shift: " << shift << endl; + memmove(&tmpNode->childHead[i+1], + &tmpNode->childHead[i], + sizeof(tmpNode->childHead[0]) * shift); + memmove(&tmpNode->childTail[i+1], + &tmpNode->childTail[i], + sizeof(tmpNode->childTail[0]) * shift); + memmove(&tmpNode->present[i+1], + &tmpNode->present[i], + sizeof(tmpNode->present[0]) * shift); + memmove(&tmpNode->childCount[i+1], + &tmpNode->childCount[i], + sizeof(tmpNode->childCount[0]) * shift); + + memmove(&tmpNode->keys[i+1], + &tmpNode->keys[i], + sizeof(tmpNode->keys[0]) * shift); + memset(tmpNode->keys[i], 0, B_MAX_NAME_LENGTH); + } else { + tmpNode->childHead[i+1] = tmpNode->childHead[i]; + tmpNode->childTail[i+1] = tmpNode->childTail[i]; + tmpNode->childCount[i+1] = tmpNode->childCount[i]; + tmpNode->present[i+1] = tmpNode->present[i]; + } + + strncpy(tmpNode->keys[i], tmpInode->name, B_MAX_NAME_LENGTH); + tmpNode->childHead[i+1] = (void *)tmpInode; + tmpNode->childTail[i] = (void *)tmpInode->prev; + tmpNode->childCount[i] = (B_MAX_CHILD_COUNT+1) >> 1; + tmpNode->childCount[i+1] -= tmpNode->childCount[i]; + tmpNode->present[i] = true; + ++tmpNode->used; + + } // if + + return true; + + } else { + tmpNode = (bNode *)tmpNode->childHead[i]; + goto restart; + } // else !leafNode + } // if result < 0 + } // for i +#endif + return true; +} // bTree::Insert + +void +bTree::Info(void) { + ubixfsInode * inode = NULL; + if (root == NULL) return; + cout << "root->used: " << root->used << endl; + for (unsigned int i = 0; i <= root->used; i++) { + inode = (ubixfsInode *)root->childHead[i]; + for (unsigned int j = 0; j < root->childCount[i]; j++) { + assert(inode); + cout << "[" << i << "].[" << j << "]->" << inode->name << endl; + inode = inode->next; + } // for j + } // for i + +} // bTree::Info +void +bTree::Print(void) { + ubixfsInode * node = GetFirstNode(); + while (node != NULL) { + cout << node->name << endl; + node = node->next; + } +} // bTree::Print + +ubixfsInode * +bTree::Find(const char * key) { + return treeSearch(root, key); +} // bTree::Find + +ubixfsInode * +bTree::inodeSearch(ubixfsInode * inode, const char * key) { + if (inode == NULL || key == NULL) return NULL; + int result = strcmp(inode->name, key); + if (result == 0) return inode; + + if (result < 0) { + inode = inode->next; + while (inode != NULL && (result = strcmp(inode->name, key) >= 0)) { + inode = inode->next; + } // while + } else { + inode = inode->prev; + while (inode != NULL && (result = strcmp(inode->name, key) <= 0)) { + inode = inode->prev; + } // while + } // else + return (result == 0 ? inode : NULL); +} // bTree::inodeSearch + +ubixfsInode * +bTree::treeSearch(bNode * bnode, const char * key) { + + if (bnode == NULL || key == NULL) return NULL; + + if (bnode->used == 0) return NULL; + if (bnode->leafNode) + if (bnode->childHead[0] != NULL) + return inodeSearch((ubixfsInode *)bnode->childHead[0], key); + else + return inodeSearch((ubixfsInode *)bnode->childHead[1], key); + +cout << "key: " << key << " keys[0]: " << bnode->keys[0] << " result: " << strcmp(key, bnode->keys[0]) << endl; + if (strcmp(key, bnode->keys[0]) < 0) + return treeSearch((bNode *)bnode->childHead[0], key); + + if (strcmp(key, bnode->keys[bnode->used-1]) >= 0) + return treeSearch((bNode *)bnode->childHead[bnode->used], key); + + for (unsigned int i = 1; i < bnode->used; i++) { + if (strcmp(key, bnode->keys[i]) < 0) + return treeSearch((bNode *)bnode->childHead[i], key); + } // for i + + return NULL; +#if 0 +restart: + for (unsigned int i = 0; i <= bnode->used; i++) { + // if we're at the end of the list, follow the last link and continue + if (i == bnode->used) { + if (bnode->leafNode) { + inode = (ubixfsInode *)bnode->childHead[i]; + goto inodeSearch; + } else { + bnode = (bNode *)bnode->childHead[i]; + } + goto restart; + } // if + + result = strcmp(key, bnode->keys[i]); + + if (result < 0) { + // what we're looking for is somewhere down the left branch + // if we're in leaf nodes we need to scan through the inode list + if (bnode->leafNode) { + inode = (ubixfsInode *)bnode->childHead[i]; +inodeSearch: + while (inode != NULL) { + result = strcmp(inode->name, key); + if (result == 0) return inode; + if (result > 0) return NULL; + inode = inode->next; + } // while + return NULL; + } else { + // since we aren't in leaf nodes yet, travel left + bnode = (bNode *)bnode->childHead[i]; + goto restart; + } // else + } // if result < 0 + } // for + + return NULL; +#endif +} // bTree::treeSearch + +ubixfsInode * +bTree::GetFirstNode(void) { + bNode * tmpNode = root; + if (tmpNode == NULL) return NULL; + + if (root->leafNode) { + if (root->used == 0) return NULL; + if (root->used == 1 && root->childHead[0] == NULL) + return (ubixfsInode *) root->childHead[1]; + else + return (ubixfsInode *) root->childHead[0]; + } // if + while (!tmpNode->leafNode) tmpNode = (bNode *)tmpNode->childHead[0]; + return (ubixfsInode *)tmpNode->childHead[0]; +} // bTree::GetFirstNode + +bool +bTree::Save(const char * filename) { + if (filename == NULL) return false; + return true; +} // bTree::Save + +bool +bTree::Load(const char * filename) { + if (filename == NULL) return false; + return true; +} // bTree::Load + +bool +bTree::Delete(const char * key) { + + if (key == NULL) return false; + return true; +} // bTree::Delete diff --git a/src/sys/ubixfsv2/superblock.h b/src/sys/ubixfsv2/superblock.h new file mode 100644 index 0000000..b2eaef5 --- /dev/null +++ b/src/sys/ubixfsv2/superblock.h @@ -0,0 +1,63 @@ +#ifndef SUPERBLOCK_H +#define SUPERBLOCK_H + +#include + +typedef struct blockRun { + int allocationGroup __attribute__ ((packed)); + unsigned short start __attribute__ ((packed)); + unsigned short len __attribute__ ((packed)); +} inodeAddr; + +// typedef unsigned long long off_t; +typedef signed char int8; +typedef unsigned char uInt8; +typedef unsigned int uInt32; +typedef int int32; +typedef unsigned long long uInt64; +typedef signed long long int64; + +typedef struct diskSuperBlock { + char name[32] __attribute__ ((packed)); + int32 magic1 __attribute__ ((packed)); + int32 fsByteOrder __attribute__ ((packed)); + +// blockSize on disk (4096 for UbixFS v2) + uInt32 blockSize __attribute__ ((packed)); + +// number of bits needed to shift a block number to get a byte address + uInt32 blockShift __attribute__ ((packed)); + + off_t numBlocks __attribute__ ((packed)); + off_t usedBlocks __attribute__ ((packed)); + + int32 inodeSize __attribute__ ((packed)); + int32 magic2 __attribute__ ((packed)); + int32 blocksPerAG __attribute__ ((packed)); + int32 AGShift __attribute__ ((packed)); + int32 numAGs __attribute__ ((packed)); + +// flags tells whether the FS is clean (0x434C454E) or dirty (0x44495954) + int32 flags __attribute__ ((packed)); + +// journal information + blockRun logBlocks __attribute__ ((packed)); + off_t logStart __attribute__ ((packed)); + off_t logEnd __attribute__ ((packed)); + + int32 magic3 __attribute__ ((packed)); + +// root dir of the SYS container + inodeAddr rootDir __attribute__ ((packed)); + +// indicies + inodeAddr indicies __attribute__ ((packed)); + +// container list + inodeAddr containers __attribute__ ((packed)); + + int32 pad[8] __attribute__ ((packed)); + +} diskSuperBlock; + +#endif // !SUPERBLOCK_H diff --git a/src/sys/ubixfsv2/ubixfs.h b/src/sys/ubixfsv2/ubixfs.h new file mode 100644 index 0000000..1102f47 --- /dev/null +++ b/src/sys/ubixfsv2/ubixfs.h @@ -0,0 +1,19 @@ +#ifndef UBIXFS_H +#define UBIXFS_H + +#include "superblock.h" + +class UbixFS { + protected: + unsigned char * freeBlockList; + public: + UbixFS(void); + bool init(void); + bool format(void *, unsigned long long, int); + bool mount(void); + bool unmount(void); + bool verifyFS(void); + + virtual ~UbixFS(void); +}; // UbixFS +#endif // !UBIXFS_H diff --git a/src/sys/ubixfsv2/vfs.cpp b/src/sys/ubixfsv2/vfs.cpp new file mode 100644 index 0000000..daa28a7 --- /dev/null +++ b/src/sys/ubixfsv2/vfs.cpp @@ -0,0 +1,22 @@ +#include +#include "vfs.h" + +DiskFS::DiskFS(const char * filename) { + diskFile = fopen(filename, "r+"); +} // DiskFS::DiskFS + +int +DiskFS::write(const void * data, long offset, long size) { + if (diskFile == NULL) return 1; + fseek(diskFile, offset, SEEK_SET); + fwrite(data, size, 1, diskFile); + return 0; +} // DiskFS::write + +int +DiskFS::read(void * data, long offset, long size) { + if (diskFile == NULL) return 1; + fseek(diskFile, offset, SEEK_SET); + fread(data, size, 1, diskFile); + return 0; +} // DiskFS::read diff --git a/src/sys/ubixfsv2/vfs.h b/src/sys/ubixfsv2/vfs.h new file mode 100644 index 0000000..68548e9 --- /dev/null +++ b/src/sys/ubixfsv2/vfs.h @@ -0,0 +1,25 @@ +#ifndef VFS_H +#define VFS_H + +#include +#include + +class FileSystemAbstract { + protected: + public: + virtual int read(char *, long, long) = 0; + virtual int write(char *, long, long) = 0; + virtual ~FileSystemAbstract(void) {}; +}; // FileSystemAbstract + +class DiskFS : public FileSystemAbstract { + protected: + FILE * diskFile; + public: + DiskFS(const char *); + virtual int write(const void *, long, long); + virtual int read(void *, long, long); + virtual ~DiskFS(void) { }; +}; // DiskFS + +#endif // !VFS_H