diff --git a/src/sys/ubixfsv2/btree.cpp b/src/sys/ubixfsv2/btree.cpp index 117899b..70eb5ac 100644 --- a/src/sys/ubixfsv2/btree.cpp +++ b/src/sys/ubixfsv2/btree.cpp @@ -11,11 +11,24 @@ using namespace std; #define VERIFY(x, y, z, n) if ((x) != (y)) { cout << "verify " << z << " failed" << endl; PrintWholeTree(); } +bTree::bTree(void) { + tag = 0; + header = new bTreeHeader; + assert(header); + memset(header, 0, sizeof(bTreeHeader)); + header->treeDepth = 1; + header->treeWidth = 0; + header->treeLeafCount = 0; +} // bTree::bTree + bTree::bTree(const char * key, ubixfsInode * inode) : root(NULL) { tag = 0; - header.treeDepth = 1; - header.treeWidth = 0; - header.treeLeafCount = 0; + header = new bTreeHeader; + assert(header); + memset(header, 0, sizeof(bTreeHeader)); + header->treeDepth = 1; + header->treeWidth = 0; + header->treeLeafCount = 0; if (inode == NULL) return; root = allocEmptyNode(); if (root == NULL) return; @@ -47,9 +60,12 @@ // note: this code is right out of the constructor if (root == NULL) { - header.treeDepth = 1; - header.treeWidth = 0; - header.treeLeafCount = 0; + if (header == NULL) header = new bTreeHeader; + assert(header); + memset(header, 0, sizeof(bTreeHeader)); + header->treeDepth = 1; + header->treeWidth = 0; + header->treeLeafCount = 0; root = allocEmptyNode(); assert(root); if (root == NULL) return false; @@ -74,7 +90,7 @@ // PrintWholeTree(); // cout << "Insert(" << key << ")" << endl; //Info(bnode); - ++header.treeLeafCount; + ++header->treeLeafCount; /* * Find the leaf node the inode goes into */ @@ -237,7 +253,7 @@ bnode->childCount[curSlot] = (B_MAX_CHILD_COUNT+1) >> 1; bnode->childCount[curSlot+1] -= bnode->childCount[curSlot]; bnode->present[curSlot] = true; - ++header.treeWidth; + ++header->treeWidth; if (++bnode->used == B_MAX_KEYS) splitNode(bnode); } // if leaf is full @@ -314,7 +330,7 @@ if (oldNode == root) { // allocate a new root node - ++header.treeDepth; + ++header->treeDepth; root = allocEmptyNode(); oldNode->parent.bPtr = root; newNode->parent.bPtr = root; @@ -451,7 +467,14 @@ void bTree::Info(void) { ubixfsInode * inode = NULL; + + cout << "tree depth: " << header->treeDepth << endl; + cout << "tree width: " << header->treeWidth << endl; + cout << "tree leaf count: " << header->treeLeafCount << endl; + cout << "tag: " << tag << endl; + if (root == NULL) return; + for (unsigned int i = 0; i <= root->used; i++) { cout << "CC[" << i << "]: " << root->childCount[i] << " "; } // for i @@ -658,14 +681,13 @@ cout << "tags: " << tag << endl; lseek(fileno(fd), tag * sizeof(bNode), SEEK_END); - header.firstNodeOffset = sizeof(bNode); - header.firstDeleted = -1; + header->firstNodeOffset = sizeof(bNode); + header->firstDeleted = -1; void * tmpPtr = malloc(sizeof(bNode)); assert(tmpPtr); uPtr = (ubixfsInode *)tmpPtr; memset(tmpPtr, 0, sizeof(bNode)); - memcpy(tmpPtr, &header, sizeof(header)); - fwrite(tmpPtr, sizeof(bNode), 1, fd); + fwrite(header, sizeof(bTreeHeader), 1, fd); saveNode(fd, root, tmpPtr); fclose(fd); @@ -718,7 +740,7 @@ } // bTree::PrintWholeTree; bTree::~bTree(void) { - cout << "tree depth: " << header.treeDepth << endl; - cout << "tree width: " << header.treeWidth << endl; - cout << "tree leaf count: " << header.treeLeafCount << endl; + cout << "tree depth: " << header->treeDepth << endl; + cout << "tree width: " << header->treeWidth << endl; + cout << "tree leaf count: " << header->treeLeafCount << endl; } // bTree::~bTree diff --git a/src/sys/ubixfsv2/btree.h b/src/sys/ubixfsv2/btree.h index 0b5d71a..9f95821 100644 --- a/src/sys/ubixfsv2/btree.h +++ b/src/sys/ubixfsv2/btree.h @@ -37,7 +37,7 @@ protected: bNode * root; uInt32 tag; - bTreeHeader header; + bTreeHeader * header; ubixfsInode * treeSearch(bNode *, const char *); ubixfsInode * inodeSearch(ubixfsInode *, const char *); void splitNode(bNode *); @@ -48,7 +48,7 @@ void saveNode(FILE *, bNode *, void *); public: bTree(const char *, ubixfsInode *); - bTree(void) : root(NULL) { }; + bTree(void); ubixfsInode * Find(const char *); ubixfsInode * GetFirstNode(void); ubixfsInode * GetFirstNode(bNode *); diff --git a/src/sys/ubixfsv2/main.cpp b/src/sys/ubixfsv2/main.cpp index 294254e..97e9441 100644 --- a/src/sys/ubixfsv2/main.cpp +++ b/src/sys/ubixfsv2/main.cpp @@ -13,7 +13,7 @@ device_t * ramDrive = dev_ramDrive(); UbixFS * fs = new UbixFS(ramDrive); -// fs->vfs_format(ramDrive); + fs->vfs_format(ramDrive); fs->vfs_init(); dev_ramDestroy(); diff --git a/src/sys/ubixfsv2/ubixfs.cpp b/src/sys/ubixfsv2/ubixfs.cpp index 04d5c89..d8e402f 100644 --- a/src/sys/ubixfsv2/ubixfs.cpp +++ b/src/sys/ubixfsv2/ubixfs.cpp @@ -14,12 +14,14 @@ device = NULL; freeBlockList = NULL; superBlock = NULL; + root = NULL; } // UbixFS::UbixFS UbixFS::UbixFS(device_t * dev) { device = dev; freeBlockList = NULL; superBlock = NULL; + root = NULL; } // UbixFS::UbixFS void @@ -29,8 +31,8 @@ printf("superBlock->fsByteOrder.....%d\n", superBlock->fsByteOrder); printf("superBlock->blockSize.......%d\n", superBlock->blockSize); printf("superBlock->blockShift......%d\n", superBlock->blockShift); - printf("superBlock->numBlocks.......%d\n", superBlock->numBlocks); - printf("superBlock->usedBlocks......%d\n", superBlock->usedBlocks); + printf("superBlock->numBlocks.......%lld\n", superBlock->numBlocks); + printf("superBlock->usedBlocks......%lld\n", superBlock->usedBlocks); printf("superBlock->batSectors......%d\n", superBlock->batSectors); printf("superBlock->inodeCount......%d\n", superBlock->inodeCount); printf("superBlock->magic2..........%X\n", superBlock->magic2); @@ -72,20 +74,136 @@ freeBlockList = new signed char[superBlock->batSectors*512]; assert(freeBlockList); memset(freeBlockList, 0, superBlock->batSectors*512); - -cout << "reading in freeBlockList" << endl; +printf("block list before reading it in: \n"); + printFreeBlockList(0); device->read(device, freeBlockList, device->sectors - superBlock->batSectors-1, superBlock->batSectors ); // device->read() +printf("block list after reading it in: \n"); + printFreeBlockList(0); + + +cout << "allocating root dir inode" << endl; + root = new ubixfsInode; + memset(root, 0, sizeof(ubixfsInode)); +cout << "root dir inode starting sector: " << + ((superBlock->rootDir.AG << superBlock->AGShift) + + superBlock->rootDir.start) * (superBlock->blockSize / 512) + << endl; + +cout << "reading in root dir" << endl; + + device->read(device, + root, + ((superBlock->rootDir.AG << superBlock->AGShift) + + superBlock->rootDir.start) * (superBlock->blockSize / 512), + sizeof(ubixfsInode) / 512 + ); +cout << "done" << endl; + root->data.btPtr = new bTree(); +cout << "reading in root dir header" << endl; + device->read(device, + root->data.btPtr->header, + ((root->blocks.direct[0].AG << superBlock->AGShift) + + root->blocks.direct[0].start) + * (superBlock->blockSize / 512), + sizeof(bTreeHeader) / 512 + ); +cout << "done" << endl; + root->data.btPtr->Info(); printSuperBlock(); - + blockRun br; + br.AG = 0; + br.start = 0; + br.len = 15; + br = getFreeBlock(br); return 0; } // UbixFS::init blockRun +UbixFS::getFreeBlock(blockRun ibr) { + signed char * ptr; + signed char * holdPtr; + int32 count, holdCount; + + blockRun obr = {0, 0, 0}; + printf("before allocation: \n"); + printFreeBlockList(0); + + // Check to make sure none of these are null + if (device == NULL || freeBlockList == NULL || superBlock == NULL) return obr; + + if (ibr.len == 0) return obr; + + if (ibr.len > superBlock->numBlocks) return obr; + + if (ibr.len == 1) return getFreeBlock(ibr.AG); + /* + * count is the block from the base of the list. + * Since we're given a specific AG to look through, we start the count at + * AG << AGShift, where AGShift is the shift value of the number of blocks + * in an AG + */ + + count = (ibr.AG << superBlock->AGShift); + + /* + * The freeBlockList is a bit map of the free/used blocks. + * Used = on bit + * Unused = off bit + * There are 8 bits per byte (hopefully) and so we have to divide the count + * by 8 to get our starting byte offset to look from + */ + + ptr = freeBlockList + (count >> 3); + +rescan: + // look for the first free 8 blocks (this may create holes) + while (*ptr != 0) { + ++ptr; + count += 8; + if (count+8 > superBlock->numBlocks) { + ptr = freeBlockList; + count = 0; + } // if + } // while *ptr != 0 + + holdPtr = ptr; + holdCount = count; + + for (unsigned short i = 0; i < ((ibr.len+7) / 8); i++) { + ++ptr; + count += 8; + if (count+8 > superBlock->numBlocks) { + ptr = freeBlockList; + count = 0; + goto rescan; + } // if + if (*ptr != 0) goto rescan; + } // for i + + // we have found a range of blocks that work for us + + obr.AG = holdCount / superBlock->blocksPerAG; + obr.start = holdCount % superBlock->blocksPerAG; + obr.len = ibr.len; + + for (unsigned short i = 0; i < (ibr.len / 8); i++) { + *holdPtr = -1; + ++holdPtr; + } // for + + if (ibr.len % 8 != 0) *holdPtr = (-1 << (8-(ibr.len % 8))); + + superBlock->usedBlocks += ibr.len; // increment the number of used blocks + printFreeBlockList(ibr.AG); + return obr; +} // UbixFS::getFreeBlock + +blockRun UbixFS::getFreeBlock(uInt32 AG) { // AG == AllocationGroup blockRun br; @@ -93,7 +211,7 @@ int32 count; int32 subCount = 128; - br.allocationGroup = 0; + br.AG = 0; br.start = 0; br.len = 0; // Check to make sure neither of these are null @@ -146,7 +264,7 @@ *ptr |= subCount; // mark this block as used ++superBlock->usedBlocks; // increment the number of used blocks - br.allocationGroup = count / superBlock->blocksPerAG; + br.AG = count / superBlock->blocksPerAG; br.start = count % superBlock->blocksPerAG; br.len = 1; return br; // return the allocated block number @@ -182,7 +300,7 @@ signed char * endPtr; int32 count; - br.allocationGroup = 0; + br.AG = 0; br.start = 0; br.len = 0; @@ -221,7 +339,7 @@ *ptr = -1; // mark 8 blocks as taken - br.allocationGroup = count / superBlock->blocksPerAG; + br.AG = count / superBlock->blocksPerAG; br.start = count % superBlock->blocksPerAG; br.len = 8; return br; @@ -239,11 +357,11 @@ // inode->magic1 = ; if (parent == NULL) { inode->inodeNum = getFreeBlock(); - inode->parent.iAddr.allocationGroup = 0; + inode->parent.iAddr.AG = 0; inode->parent.iAddr.start = 0; inode->parent.iAddr.len = 0; } else { - inode->inodeNum = getFreeBlock(parent->inodeNum.allocationGroup); + inode->inodeNum = getFreeBlock(parent->inodeNum.AG); inode->parent.iAddr = parent->inodeNum; } // else @@ -275,6 +393,27 @@ return mknod(path, 0); } // UbixFS::mknod +void +UbixFS::printFreeBlockList(uInt32 AG) { + unsigned int j; + if (superBlock == NULL || freeBlockList == NULL) return; + printf("AG = %d\n", AG); + for (unsigned int i = 0; i < superBlock->blocksPerAG / 8; i++) { + j = 128; + signed char foo = freeBlockList[(AG << superBlock->AGShift)+i]; + while (j > 0) { + if ((foo & j) == j) + printf("1"); + else + printf("0"); + j >>= 1; + + } + } // for i + printf("\n"); + return; +} // UbixFS::printFreeBlockList + int UbixFS::vfs_format(device_t * dev) { cout << "vfs_format()" << endl; @@ -283,7 +422,7 @@ if (dev == NULL) return -1; // zero out the sector - memset(§or, 0, sizeof(sector)); + memset(§or, 0x0, sizeof(sector)); // fill the drive in with zeroed out sectors cout << "dev->sectors: " << dev->sectors << endl; @@ -335,17 +474,17 @@ sb->batSectors = batSize; sb->flags = 0x434C454E; // CLEN - sb->logBlocks.allocationGroup = 0; + sb->logBlocks.AG = 0; sb->logBlocks.start = 0; sb->logBlocks.len = 0; sb->logStart = 0; sb->logEnd = 0; sb->magic3 = UBIXFS_MAGIC3; - sb->indicies.allocationGroup = 0; + sb->indicies.AG = 0; sb->indicies.start = 0; sb->indicies.len = 0; - sb->rootDir.allocationGroup = 0; + sb->rootDir.AG = 0; sb->rootDir.start = 0; sb->rootDir.len = 1; @@ -357,16 +496,19 @@ cout << "batSize: " << batSize << endl; // mark the first two 4k blocks used + memset(§or, 0, sizeof(sector)); sector[0] = (1 << 7) | (1 << 6); +cout << endl; // write out the first sector of the BAT cout << "Writing BAT - 1 - " << endl; - dev->write(dev, §or, batSect / 8, 1); + dev->write(dev, §or, batSect, 1); // clear the rest sector[0] = 0; + memset(§or, 0, sizeof(sector)); // write out the rest of the BAT cout << "Writing BAT - 2 - " << endl; for (unsigned int i = 1; i < batSize; i++) { - dev->write(dev, §or, (batSect / 8)+i, 1); + dev->write(dev, §or, (batSect)+i, 1); } // for i cout << "Finished writing BAT" << endl; /* allocate part of the root dir */ @@ -377,8 +519,10 @@ cout << "allocating bTree header" << endl; bTreeHeader * bth = new bTreeHeader; assert(bth); - memset(bth, 0, sb->blockSize); - bth->firstDeleted = bth->firstNodeOffset = -1; + memset(bth, 0, sizeof(bTreeHeader)); + bth->firstDeleted = -1; + bth->firstNodeOffset = -1; + //bth-> /* create the root dir inode here */ cout << "creating root inode" << endl; @@ -388,15 +532,15 @@ memset(inode, 0, sizeof(ubixfsInode)); // inode->magic1 = ; - inode->inodeNum.allocationGroup = 0; + inode->inodeNum.AG = 0; inode->inodeNum.start = 0; inode->inodeNum.len = 1; - inode->parent.iAddr.allocationGroup = 0; + inode->parent.iAddr.AG = 0; inode->parent.iAddr.start = 0; inode->parent.iAddr.len = 0; - inode->blocks.direct[0].allocationGroup = 0; + inode->blocks.direct[0].AG = 0; inode->blocks.direct[0].start = 1; inode->blocks.direct[0].len = 1; // inode->blocks.maxDirectRange = 1; diff --git a/src/sys/ubixfsv2/ubixfs.h b/src/sys/ubixfsv2/ubixfs.h index 9fb5881..b306567 100644 --- a/src/sys/ubixfsv2/ubixfs.h +++ b/src/sys/ubixfsv2/ubixfs.h @@ -34,7 +34,7 @@ typedef struct blockRun { - int allocationGroup __attribute__ ((packed)); + int AG __attribute__ ((packed)); unsigned short start __attribute__ ((packed)); unsigned short len __attribute__ ((packed)); } inodeAddr; @@ -131,12 +131,15 @@ protected: signed char * freeBlockList; diskSuperBlock * superBlock; + ubixfsInode * root; + blockRun getFreeBlock(blockRun); blockRun getFreeBlock(uInt32); blockRun getFreeBlock(void); blockRun get8FreeBlocks(uInt32); void * mknod(const char *, ubixfsInode *); uInt32 getNextAG(void); void printSuperBlock(void); + void printFreeBlockList(uInt32); public: UbixFS(void); UbixFS(device_t *);