diff --git a/src/sys/ubixfsv2/btree.cpp b/src/sys/ubixfsv2/btree.cpp index 1664c2c..114018d 100644 --- a/src/sys/ubixfsv2/btree.cpp +++ b/src/sys/ubixfsv2/btree.cpp @@ -11,20 +11,33 @@ using namespace std; #define VERIFY(x, y, z, n) if ((x) != (y)) { cout << "verify " << z << " failed" << endl; PrintWholeTree(); } -bTree::bTree(void) { +bTree::bTree(UbixFS * filesystem, fileDescriptor * myfd) { + size_t result = 0; + root = NULL; tag = 0; + fs = filesystem; + fd = myfd; header = new bTreeHeader; assert(header); memset(header, 0, sizeof(bTreeHeader)); - header->treeDepth = 1; - header->treeWidth = 0; - header->treeLeafCount = 0; - header->firstDeleted = -1; - header->firstNodeOffset = sizeof(bTreeHeader); + assert(fs); + result = fs->vfs_read(fd, header, 0, sizeof(bTreeHeader)); + assert(result == sizeof(bTreeHeader)); + + // If there are any files in this dir, load the first node of the b+tree + if (header->treeLeafCount != 0) { + assert(header->firstNodeOffset != 0); + root = new bNode; + assert(root); + result = fs->vfs_read(fd, root, header->firstNodeOffset, sizeof(bNode)); + assert(result == sizeof(bNode)); + } // if + } // bTree::bTree bTree::bTree(const char * key, ubixfsInode * inode) { +/* once the FS and the bTree are interfaced, this should go away */ root = NULL; tag = 0; header = new bTreeHeader; @@ -530,13 +543,15 @@ ubixfsInode * bTree::Find(const char * key) { +/* ubixfsInode * tmp = GetFirstNode(); while (tmp!=NULL) { if (strcmp(tmp->name, key) == 0) return tmp; tmp = tmp->next.iPtr; } return NULL; -// return treeSearch(root, key); +*/ + return treeSearch(root, key); } // bTree::Find ubixfsInode * @@ -566,23 +581,19 @@ if (bnode->leaf) return inodeSearch(GetFirstNode(bnode), key); -/* - * if (bnode->head[0] != NULL) - * return inodeSearch((ubixfsInode *)bnode->head[0], key); - * else - * return inodeSearch((ubixfsInode *)bnode->head[1], key); - */ -// cout << "key: " << key << " keys[0]: " << bnode->keys[0] << " result: " << strcmp(key, bnode->keys[0]) << endl; - if (strcmp(key, bnode->keys[0]) < 0) + if (strcmp(key, bnode->keys[0]) < 0) { return treeSearch(bnode->head[0].bPtr, key); + } // if - if (strcmp(key, bnode->keys[bnode->used-1]) >= 0) + if (strcmp(key, bnode->keys[bnode->used-1]) >= 0) { return treeSearch(bnode->head[bnode->used].bPtr, key); + } // if for (unsigned int i = 1; i < bnode->used; i++) { - if (strcmp(key, bnode->keys[i]) < 0) + if (strcmp(key, bnode->keys[i]) < 0) { return treeSearch(bnode->head[i].bPtr, key); + } // if } // for i return NULL; diff --git a/src/sys/ubixfsv2/btree.h b/src/sys/ubixfsv2/btree.h index 9f95821..edd28ee 100644 --- a/src/sys/ubixfsv2/btree.h +++ b/src/sys/ubixfsv2/btree.h @@ -5,6 +5,7 @@ #include "ubixfs.h" #include "btreeheader.h" +#include "file.h" #define B_NODE_MAGIC_1 0xDEADBEEF #define B_NODE_MAGIC_2 0x1900BABE @@ -35,33 +36,35 @@ class bTree { protected: - bNode * root; - uInt32 tag; - bTreeHeader * header; - ubixfsInode * treeSearch(bNode *, const char *); - ubixfsInode * inodeSearch(ubixfsInode *, const char *); - void splitNode(bNode *); - bNode * allocEmptyNode(void); - void insertNode(bNode *, const char *, bNode *); - bNode * findLeafNode(bNode *, const char *); - void Print(bNode *); - void saveNode(FILE *, bNode *, void *); + bNode * root; + UbixFS * fs; + bTreeHeader * header; + fileDescriptor * fd; + uInt32 tag; + ubixfsInode * treeSearch(bNode *, const char *); + ubixfsInode * inodeSearch(ubixfsInode *, const char *); + void splitNode(bNode *); + bNode * allocEmptyNode(void); + void insertNode(bNode *, const char *, bNode *); + bNode * findLeafNode(bNode *, const char *); + void Print(bNode *); + void saveNode(FILE *, bNode *, void *); public: - bTree(const char *, ubixfsInode *); - bTree(void); - ubixfsInode * Find(const char *); - ubixfsInode * GetFirstNode(void); - ubixfsInode * GetFirstNode(bNode *); - bool Delete(const char *); - void Info(void); - void Info(const bNode *); - bool Insert(const char *, ubixfsInode *); - bool Save(const char *); - bool Load(const char *); - void Print(void); - void PrintWholeTree(void); - bool Verify(void); - ~bTree(void); + bTree(const char *, ubixfsInode *); + bTree(UbixFS *, fileDescriptor *); + ubixfsInode * Find(const char *); + ubixfsInode * GetFirstNode(void); + ubixfsInode * GetFirstNode(bNode *); + bool Delete(const char *); + void Info(void); + void Info(const bNode *); + bool Insert(const char *, ubixfsInode *); + bool Save(const char *); + bool Load(const char *); + void Print(void); + void PrintWholeTree(void); + bool Verify(void); + ~bTree(void); friend class UbixFS; }; // bTree #endif // !BTREE_H diff --git a/src/sys/ubixfsv2/fsAbstract.h b/src/sys/ubixfsv2/fsAbstract.h index f553489..9658881 100644 --- a/src/sys/ubixfsv2/fsAbstract.h +++ b/src/sys/ubixfsv2/fsAbstract.h @@ -24,15 +24,17 @@ /* Dir I/O */ virtual int vfs_opendir(DIR *,const char *) { return -1; }; virtual int vfs_closedir(DIR *) { return -1; }; - virtual int vfs_mkdir(const char *,mode_t) { return -1; }; + virtual int vfs_mkdir(const char *, mode_t) { return -1; }; + virtual int vfs_rmdir(const char *) { return -1; }; virtual int vfs_readdir(DIR *,struct dirent *) { return -1; }; /* FS Functions */ virtual int vfs_init(void) { return -1; }; virtual int vfs_format(device_t *) { return -1; }; + virtual void * vfs_mknod(const char *, mode_t) { return NULL; }; + virtual int vfs_purge(void) { return -1; }; virtual int vfs_stop(void) { return -1; }; virtual int vfs_sync(void) { return -1; }; - virtual void * vfs_mknod(const char *, mode_t) { return NULL; }; /* Misc Functions */ virtual int vfs_unlink(const char *) { return -1; }; diff --git a/src/sys/ubixfsv2/main.cpp b/src/sys/ubixfsv2/main.cpp index 9e77d6d..8bdff45 100644 --- a/src/sys/ubixfsv2/main.cpp +++ b/src/sys/ubixfsv2/main.cpp @@ -15,6 +15,7 @@ UbixFS * fs = new UbixFS(ramDrive); fs->vfs_format(ramDrive); fs->vfs_init(); + fs->vfs_mkdir("/testdir", 0); fs->vfs_stop(); dev_ramDestroy(); diff --git a/src/sys/ubixfsv2/ubixfs.cpp b/src/sys/ubixfsv2/ubixfs.cpp index 0ad3bc7..f938ddb 100644 --- a/src/sys/ubixfsv2/ubixfs.cpp +++ b/src/sys/ubixfsv2/ubixfs.cpp @@ -105,21 +105,10 @@ cout << "done" << endl; ubixfsInode * rootInode = static_cast(root->inode); assert(rootInode); - rootInode->data.btPtr = new bTree(); -cout << "reading in root dir header" << endl; - result = vfs_read(root, rootInode->data.btPtr->header, 0, sizeof(bTreeHeader)); - assert(result == sizeof(bTreeHeader)); -/* - device->read(device, - rootInode->data.btPtr->header, - ((rootInode->blocks.direct[0].AG << superBlock->AGShift) - + rootInode->blocks.direct[0].start) - * (superBlock->blockSize / 512), - sizeof(bTreeHeader) / 512 - ); - */ -cout << "done" << endl; + /* the bTree constructor now loads in the header */ + + rootInode->data.btPtr = new bTree(this, root); rootInode->data.btPtr->Info(); printSuperBlock(); return 0; @@ -314,8 +303,8 @@ void * UbixFS::vfs_mknod(const char *path, mode_t mode) { - return mknod(path, 0); -} // UbixFS::mknod + return mknod(path, 0, mode); // <- this probably isn't correct +} // UbixFS::vfs_mknod int UbixFS::vfs_open(const char * filename, fileDescriptor * fd, int flags, ...) { @@ -365,15 +354,11 @@ } while (i < NUM_DIRECT_BLOCKS); -cout << "i == " << i << endl; startingBlock = (inode->blocks.direct[i].AG << superBlock->AGShift) + inode->blocks.direct[i].start + ((offset - sum) / bSize); -cout << "inode->blocks.direct[" << i << "]." << inode->blocks.direct[i].len; -cout << endl; runSize = inode->blocks.direct[i].len * bSize; -cout << "runSize: " << runSize << endl; // startingBlock is in 4k blocks startingBlock *= (bSize / 512); // startingBlock is now in sectors @@ -400,11 +385,12 @@ size_t UbixFS::vfs_write(fileDescriptor * fd, void * data, off_t offset, size_t size) { - - unsigned int i; - off_t sum, startingBlock; - size_t runSize, sectorCount, totalSize, bSize; // blockSize + // char * sector[512]; // used to pad + unsigned int i, whichBlocks; + off_t sum, startingBlock, EORPos, maxRange; + size_t runSize, runRemainder, sectorCount, totalSize, bSize; // blockSize ubixfsInode * inode = NULL; + blockRun br; if (fd == NULL || data == NULL) return ~0; @@ -418,9 +404,152 @@ assert(inode); bSize = superBlock->blockSize; + assert(bSize != 0); + + totalSize = sum = i = whichBlocks = 0; + + EORPos = offset + size; // compute End Of Run Position + maxRange = inode->blocks.maxDirectRange; + + if (inode->blocks.maxIndirectRange > maxRange) { + maxRange = inode->blocks.maxIndirectRange; + whichBlocks = 1; + } + + if (inode->blocks.maxDoubleIndirectRange > maxRange) { + maxRange = inode->blocks.maxDoubleIndirectRange; + whichBlocks = 2; + } + + if (EORPos > maxRange) { + /* + * The offset+size is greater than the size of the file, so we need to + * extend out the file. Scan through the direct blocks (FIX LATER) + * to find out where we need to extend + */ + switch (whichBlocks) { + case 0: + while (i < NUM_DIRECT_BLOCKS && inode->blocks.direct[i].len != 0) ++i; + // i holds which direct block we're going to add to + break; + case 1: + case 2: + assert(false); // UNFINISHED + break; + default: + assert(false); // sanity check + } // switch + + /* + * NOTE: it's possible that if we scan through to find where the + * run goes, we might be able to extend the previous block extent. + * This will require that we set up br.start to be where we'd like to + * start looking through the free block list, and then modifying + * getFreeBlock() to honour that. + */ + + br.AG = inode->inodeNum.AG; // request a sane allocation group + br.start = 0; // getFreeBlock() will ignore this + + /* + * The length that we need is determined by how much extra slack we + * already have in the pre-allocated blocks. + * e.g. (assumes 4k blocks) + * bSize = 4096 + * maxRange = 4096 + * size = 3000 + * offset = 3000 + * size = 4000 + * [--- data block ---][--- data block ---] <---- blocks on disk + * <-file data-> <---- actual file size + * <-----> <---- slack + * [ data block size ] <---- maxRange + * | <---- offset + * ***************** <---- new data + * + * In the above example, you'd need at least one more block to write + * out the data. + * ((offset + size) - maxRange + (bSize-1)) / bSize + * ((3000 + 4000) - 4096 + (4095)) / 4096 == 1 (rounded down) + * And then we expand it by a little extra so we don't have to keep + * looking for more blocks. Currently we use 32k of slack (or 8 blocks) + */ + + br.len = ((EORPos - maxRange + (bSize-1)) / bSize); + + if (br.len < 8) br.len = 8; // we allocate 32k if the file needs to grow + + br = getFreeBlock(br); + assert(br.len > 0); + switch (whichBlocks) { + case 0: + inode->blocks.direct[i] = br; + inode->blocks.maxDirectRange += br.len * bSize; + break; + case 1: + assert(false); // UNFINISHED + inode->blocks.maxIndirectRange += br.len * bSize; + break; + case 2: + assert(false); // UNFINISHED + inode->blocks.maxDoubleIndirectRange += br.len * bSize; + break; + default: + assert(false); // sanity check + } // switch + + inode->blocks.size = EORPos; + } // if + + + runRemainder = size % 512; + size -= runRemainder; totalSize = sum = i = 0; + while (size > 0) { + + /* + * place check here to see which set of blocks we're looking through + */ + + // scan through direct blocks + do { + if (offset >= sum && offset < sum + inode->blocks.direct[i].len * bSize) + break; + + sum += inode->blocks.direct[i++].len * bSize; + + } while (i < NUM_DIRECT_BLOCKS); + + startingBlock = (inode->blocks.direct[i].AG << superBlock->AGShift) + + inode->blocks.direct[i].start + ((offset - sum) / bSize); + + runSize = inode->blocks.direct[i].len * bSize; + + // startingBlock is in 4k blocks + startingBlock *= (bSize / 512); + // startingBlock is now in sectors + + if (runSize >= size) { + runSize = size; + size = 0; + } else { + size -= runSize; + } // else + + sectorCount = runSize / 512; + + cout << "device->write(device, data, " << startingBlock << ", "; + cout << sectorCount << ");" << endl; + + device->write(device, data, startingBlock, sectorCount); + + (uInt8 *)data += runSize; + totalSize += runSize; + } // while + + assert(runRemainder != 0); // UNFINISHED return totalSize; } // UbixFS::vfs_write @@ -703,7 +832,7 @@ } // UbixFS::get8FreeBlocks void * -UbixFS::mknod(const char *filename, ubixfsInode * parent) { +UbixFS::mknod(const char *filename, ubixfsInode * parent, mode_t mode) { ubixfsInode * inode = NULL; inode = new ubixfsInode; @@ -734,7 +863,7 @@ inode->uid = getuid(); inode->gid = getgid(); // inode->mode - // inode->flags + inode->flags = mode; // inode->createTime // inode->lastModifiedTime inode->inodeSize = superBlock->inodeSize; @@ -758,6 +887,81 @@ return inode; } // UbixFS::mknod +int +UbixFS::vfs_mkdir(const char * path, mode_t mode) { + char name[MAX_FILENAME_LENGTH]; + unsigned int start, end, len, nameStart; + ubixfsInode * dir = static_cast(root->inode); + ubixfsInode * inode = NULL; + + assert(path); // bad input: vfs_mkdir(NULL); + assert(*path); // bad input: vfs_mkdir(""); + + memset(&name, 0, sizeof(name)); + // find the dir name + len = strlen(path); + + assert(path[0] == '/'); // bad input: vfs isn't doing its job + assert(len > 1); // bad input: mkdir / + + // remove trailing "/" if present + if (path[len-1] == '/') --len; + + assert(len > 1); // bad input: mkdir // + + nameStart = len-1; + + assert(path[nameStart] != '/'); // bad input: mkdir /a// + + /* + * we're guaranteed by the assert() above that there is + * at least one "/" before our location. If you remove the assert + * you might need to make sure nameStart stays above 0 in the following + * while + */ + + while (path[nameStart] != '/') --nameStart; + ++nameStart; + assert(len - nameStart > 0); + + /* e.g. + * v--------------------- start + * v------------------ end + * v------ nameStart + * /usr/local/data/dirname/ <--- ignores trailing / + * <---------23----------> len + */ + + start = end = 1; // skip leading / + while (end < nameStart) { + do { ++end; } while(path[end] != '/'); + + assert(end-start+1 < sizeof(name)); + // this is probably wrong: + strncpy(name, &path[start], end-start+1); + cout << name << endl; + dir = dir->data.btPtr->Find(name); + assert(dir); + assert(dir->flags & INODE_DIRECTORY == INODE_DIRECTORY); + start = ++end; + } + + strncpy(name, &path[nameStart], len - nameStart); + inode = (ubixfsInode *)mknod(name, dir, mode | INODE_DIRECTORY); + + /* + * keep in mind that the reason for passing in the name is because + * we thought about allowing key names to be different from inode + * names. In retrospect, I don't think that's a good idea since a dir + * listing will print the actual dir name instead of . and .. + * Thus: the first parameter of btPtr->Insert() may go away. + */ + + assert(dir->data.btPtr->Insert(inode->name, inode)); + + return 0; +} // UbixFS::vfs_mkdir + void UbixFS::printFreeBlockList(uInt32 AG) { unsigned int j; diff --git a/src/sys/ubixfsv2/ubixfs.h b/src/sys/ubixfsv2/ubixfs.h index c207fd5..595e6f4 100644 --- a/src/sys/ubixfsv2/ubixfs.h +++ b/src/sys/ubixfsv2/ubixfs.h @@ -140,7 +140,7 @@ blockRun getFreeBlock(void); blockRun get8FreeBlocks(uInt32); uInt32 getNextAG(void); - void * mknod(const char *, ubixfsInode *); + void * mknod(const char *, ubixfsInode *, mode_t); void printSuperBlock(void); void printFreeBlockList(uInt32); void setFreeBlock(blockRun); @@ -150,7 +150,8 @@ virtual int vfs_init(void); virtual int vfs_format(device_t *); virtual void * vfs_mknod(const char *, mode_t); - virtual int vfs_open(const char *, fileDescriptor *,int,...); + virtual int vfs_mkdir(const char *, mode_t); + virtual int vfs_open(const char *, fileDescriptor *, int, ...); virtual size_t vfs_read(fileDescriptor *, void *, off_t, size_t); virtual size_t vfs_write(fileDescriptor *, void *, off_t, size_t); virtual int vfs_sync(void);