# ubixfs.cpp

Go to the documentation of this file.

    00001 #include <stddef.h>
    00002 #include <stdlib.h>
    00003 #include <unistd.h>
    00004 #include <string.h>
    00005 #include <assert.h>
    00006 #include <iostream>
    00007
    00008 #include "ubixfs.h"
    00009 #include "btree.h"
    00010
    00011 using namespace std;
    00012
    00013 UbixFS::UbixFS(void) {
    00014   device = NULL;
    00015   freeBlockList = NULL;
    00016   superBlock = NULL;
    00017   root = NULL;
    00018 } // UbixFS::UbixFS
    00019
    00020
    00021 UbixFS::UbixFS(device_t * dev) {
    00022   device = dev;
    00023   freeBlockList = NULL;
    00024   superBlock = NULL;
    00025   root = NULL;
    00026 } // UbixFS::UbixFS
    00027
    00028 void
    00029 UbixFS::printSuperBlock(void) {
    00030   printf("superBlock->name........... %s\n", superBlock->name);
    00031   printf("superBlock->magic1......... %X\n", superBlock->magic1);
    00032   printf("superBlock->fsByteOrder.... %d\n", superBlock->fsByteOrder);
    00033   printf("superBlock->blockSize...... %d\n", superBlock->blockSize);
    00034   printf("superBlock->blockShift..... %d\n", superBlock->blockShift);
    00035   printf("superBlock->numBlocks...... %lld\n", superBlock->numBlocks);
    00036   printf("superBlock->usedBlocks..... %lld\n", superBlock->usedBlocks);
    00037   printf("superBlock->batSectors..... %d\n", superBlock->batSectors);
    00038   printf("superBlock->inodeCount..... %d\n", superBlock->inodeCount);
    00039   printf("superBlock->magic2......... %X\n", superBlock->magic2);
    00040   printf("superBlock->blocksPerAG.... %d\n", superBlock->blocksPerAG);
    00041   printf("superBlock->AGShift........ %d\n", superBlock->AGShift);
    00042   printf("superBlock->numAGs......... %d\n", superBlock->numAGs);
    00043   printf("superBlock->lastUsedAG..... %d\n", superBlock->lastUsedAG);
    00044   printf("superBlock->flags.......... %X\n", superBlock->flags);
    00045   printf("superBlock->magic3......... %X\n", superBlock->magic3);
    00046   return;
    00047 } // UbixFS::printSuperBlock
    00048
    00049 int
    00050 UbixFS::vfs_init(void) {
    00051 assert(device);
    00052   size_t result;
    00053   cout << "vfs_init()" << endl;
    00054   assert(device);
    00055
    00056   if (device == NULL) return -1;
    00057   if (superBlock != NULL) delete superBlock;
    00058   superBlock = new diskSuperBlock;
    00059 assert(superBlock);
    00060   if (superBlock == NULL) return -1;
    00061
    00062   // read in the superBlock. It's always the last block on the partition
    00063 cout << "reading in superBlock" << endl;
    00064   device->read(device, superBlock, device->sectors-1, 1);
    00065 cout << "done" << endl;
    00066
    00067   assert(superBlock->magic1 == UBIXFS_MAGIC1);
    00068   assert(superBlock->magic2 == UBIXFS_MAGIC2);
    00069   assert(superBlock->magic3 == UBIXFS_MAGIC3);
    00070   assert(strcmp(superBlock->name, "UbixFS") == 0);
    00071   assert((1 << superBlock->blockShift) == superBlock->blockSize);
    00072   assert((unsigned)(1 << superBlock->AGShift) == superBlock->blocksPerAG);
    00073   assert(superBlock->flags == UBIXFS_CLEAN);
    00074
    00075   if (freeBlockList != NULL) delete [] freeBlockList;
    00076   freeBlockList = new signed char[superBlock->batSectors*512];
    00077 assert(freeBlockList);
    00078   memset(freeBlockList, 0, superBlock->batSectors*512);
    00079
    00080   device->read(device,
    00081                freeBlockList,
    00082                device->sectors - superBlock->batSectors-1,
    00083                superBlock->batSectors
    00084               ); // device->read()
    00085
    00086   root = new fileDescriptor;
    00087   assert(root);
    00088   memset(root, 0, sizeof(fileDescriptor));
    00089 cout << "allocating root dir inode" << endl;
    00090   root->inode = new ubixfsInode;
    00091   memset(root->inode, 0, sizeof(ubixfsInode));
    00092 cout << "root dir inode starting sector: " <<
    00093                ((superBlock->rootDir.AG << superBlock->AGShift)
    00094                + superBlock->rootDir.start) * (superBlock->blockSize / 512)
    00095      << endl;
    00096
    00097 cout << "reading in root dir inode" << endl;
    00098
    00099   device->read(device,
    00100                root->inode,
    00101                ((superBlock->rootDir.AG << superBlock->AGShift)
    00102                  + superBlock->rootDir.start) * (superBlock->blockSize / 512),
    00103                sizeof(ubixfsInode) / 512
    00104               );
    00105 cout << "done" << endl;
    00106   ubixfsInode * rootInode = static_cast<ubixfsInode *>(root->inode);
    00107   assert(rootInode);
    00108
    00109   /* the bTree constructor now loads in the header */
    00110
    00111   rootInode->data.btPtr = new bTree(this, root);
    00112   rootInode->data.btPtr->Info();
    00113   printSuperBlock();
    00114   return 0;
    00115 } // UbixFS::init
    00116
    00117 int
    00118 UbixFS::vfs_format(device_t * dev) {
    00119   cout << "vfs_format()" << endl;
    00120   char sector[512];
    00121   uInt32 blocks, batSect, batSize;
    00122   if (dev == NULL) return -1;
    00123
    00124   // zero out the sector
    00125   memset(&sector, 0x0, sizeof(sector));
    00126
    00127   // fill the drive in with zeroed out sectors
    00128   cout << "dev->sectors: " << dev->sectors << endl;
    00129   cout << "clearing device...";
    00130
    00131   for (unsigned int i = 0; i < dev->sectors; i++) {
    00132     dev->write(dev, &sector, i, 1);
    00133   } // for i
    00134
    00135   cout << "done" << endl;
    00136
    00137   // allocate a new superBlock and clear it
    00138
    00139   diskSuperBlock *sb = new diskSuperBlock;
    00140   if (sb == NULL) return -1;
    00141   memset(sb, 0, sizeof(diskSuperBlock));
    00142
    00143   // dev->sectors is the number of 512 byte sectors
    00144
    00145   blocks = (dev->sectors-1) / 8;     // 4k blocks
    00146   batSize = (dev->sectors-1) % 8;    // remainder
    00147
    00148   // compute the BAT size
    00149
    00150   while ((batSize * 4096) < blocks) {
    00151     batSize += 8;
    00152     --blocks;
    00153   } // while
    00154
    00155   // batSize is in sectors
    00156   batSect = blocks * 8;
    00157
    00158   strcpy(sb->name, "UbixFS");
    00159   sb->magic1 = UBIXFS_MAGIC1;
    00160   sb->fsByteOrder = 0;
    00161   sb->blockSize = 4096;
    00162   sb->blockShift = 12;
    00163   sb->numBlocks = blocks;
    00164   sb->usedBlocks = 2;  // root dir takes two blocks (inode + bTree header)
    00165   sb->inodeCount = 1;
    00166   sb->inodeSize = 4096;
    00167   sb->magic2 = UBIXFS_MAGIC2;
    00168   sb->blocksPerAG = 2048;
    00169   sb->AGShift = 11;
    00170   sb->numAGs = (sb->numBlocks+2047) / 2048;
    00171   sb->lastUsedAG = 0;
    00172
    00173   // the BAT exists outside our official block count, so no
    00174   // entries in the BAT need to be set for it
    00175   sb->batSectors = batSize;
    00176
    00177   sb->flags = 0x434C454E; // CLEN
    00178   sb->logBlocks.AG = 0;
    00179   sb->logBlocks.start = 0;
    00180   sb->logBlocks.len = 0;
    00181   sb->logStart = 0;
    00182   sb->logEnd = 0;
    00183   sb->magic3 = UBIXFS_MAGIC3;
    00184   sb->indicies.AG = 0;
    00185   sb->indicies.start = 0;
    00186   sb->indicies.len = 0;
    00187
    00188   sb->rootDir.AG = 0;
    00189   sb->rootDir.start = 0;
    00190   sb->rootDir.len = 1;
    00191
    00192   // write out the superBlock
    00193
    00194   dev->write(dev, sb, dev->sectors-1, 1);
    00195
    00196   // mark the first two 4k blocks used
    00197   memset(&sector, 0, sizeof(sector));
    00198   sector[0] = (1 << 7) | (1 << 6);
    00199
    00200   // write out the first sector of the BAT
    00201
    00202   dev->write(dev, &sector, batSect, 1);
    00203   // clear the rest
    00204   sector[0] = 0;
    00205
    00206   // write out the rest of the BAT
    00207
    00208   for (unsigned int i = 1; i < batSize; i++) {
    00209     dev->write(dev, &sector, (batSect)+i, 1);
    00210   } // for i
    00211
    00212   /* allocate part of the root dir */
    00213
    00214   // sanity checks
    00215   assert(sb->blockSize);
    00216   assert((unsigned)sb->blockSize >= sizeof(bTreeHeader));
    00217
    00218   bTreeHeader * bth = new bTreeHeader;
    00219   assert(bth);
    00220   memset(bth, 0, sizeof(bTreeHeader));
    00221
    00222   bth->firstDeleted = -1;
    00223   bth->firstNodeOffset = -1;
    00224   bth->treeDepth = 1;
    00225   bth->treeWidth = 0;
    00226   bth->treeLeafCount = 0;
    00227
    00228   /* create the root dir inode here */
    00229
    00230   ubixfsInode * inode = new ubixfsInode;
    00231   assert(inode);
    00232   if (inode == NULL) return -1;
    00233   memset(inode, 0, sizeof(ubixfsInode));
    00234
    00235   inode->magic1 = UBIXFS_INODE_MAGIC;
    00236
    00237   // inodes point to themselves
    00238   inode->inodeNum.AG = 0;
    00239   inode->inodeNum.start = 0;
    00240   inode->inodeNum.len = 1;
    00241
    00242   // root dir has no parent directory
    00243   inode->parent.iAddr.AG = 0;
    00244   inode->parent.iAddr.start = 0;
    00245   inode->parent.iAddr.len = 0;
    00246
    00247   /* this is part of the root dir structure (the bTreeHeader) */
    00248   inode->blocks.direct[0].AG = 0;
    00249   inode->blocks.direct[0].start = 1;
    00250   inode->blocks.direct[0].len = 1;
    00251
    00252   inode->blocks.maxDirectRange = sizeof(bTreeHeader);
    00253   inode->blocks.size = sizeof(bTreeHeader);
    00254
    00255   strcpy(inode->name, "/");
    00256   inode->uid = getuid();
    00257   inode->gid = getgid();
    00258   // inode->mode
    00259   inode->flags = INODE_DIRECTORY;
    00260   // inode->createTime
    00261   // inode->lastModifiedTime
    00262   // inode->type
    00263
    00264   inode->attributes.AG = 0;
    00265   inode->attributes.start = 0;
    00266   inode->attributes.len = 0;
    00267
    00268   inode->inodeSize = sb->inodeSize;
    00269
    00270   /*
    00271    * next and prev are used in memory to hold pointers to the next/prev
    00272    * inodes in this dir.  On disk they may have another value, but for
    00273    * now they should be set to null.
    00274    */
    00275
    00276   inode->next.offset = 0;
    00277   inode->prev.offset = 0;
    00278
    00279   // write out the "root" dir inode
    00280
    00281   dev->write(dev,
    00282              inode,
    00283              ((inode->inodeNum.AG << sb->AGShift) +
    00284               inode->inodeNum.start) * (sb->blockSize / 512),
    00285              sb->inodeSize / 512
    00286             ); // dev->write
    00287
    00288   // write out the "root" dir
    00289
    00290   dev->write(dev,
    00291              bth,
    00292              ((inode->blocks.direct[0].AG << sb->AGShift) +
    00293               inode->blocks.direct[0].start) * (sb->blockSize / 512),
    00294              sb->blockSize / 512
    00295             ); // dev->write
    00296
    00297   delete inode;
    00298   delete bth;
    00299   delete sb;
    00300   cout << "format complete" << endl;
    00301   return 0;
    00302 } // UbixFS::vfs_format
    00303
    00304 void *
    00305 UbixFS::vfs_mknod(const char *path, mode_t mode) {
    00306   return mknod(path, 0, mode);  // <- this probably isn't correct
    00307 } // UbixFS::vfs_mknod
    00308
    00309 int
    00310 UbixFS::vfs_open(const char * filename, fileDescriptor * fd, int flags, ...) {
    00311   if (filename == NULL || fd == NULL) return -1;
    00312   flags = flags;
    00313   fd->inode = NULL;
    00314   fd->offset = 0;
    00315   fd->size = 0;
    00316   // look up the file here
    00317   return 0;
    00318 } // UbixFS::vfs_open
    00319
    00320 size_t
    00321 UbixFS::vfs_read(fileDescriptor * fd, void * data, off_t offset, size_t size) {
    00322
    00323   unsigned int i;
    00324   off_t sum, startingBlock;
    00325   size_t runSize, sectorCount, totalSize, bSize; // blockSize
    00326   ubixfsInode * inode = NULL;
    00327
    00328   if (fd == NULL || data == NULL) return ~0;
    00329
    00330   if (size == 0) return 0; // don't fail if size is 0?
    00331
    00332   assert(device);
    00333   assert(superBlock);
    00334
    00335   inode = static_cast<ubixfsInode *>(fd->inode);
    00336
    00337   assert(inode);
    00338
    00339   bSize = superBlock->blockSize;
    00340
    00341   totalSize = sum = i = 0;
    00342
    00343   while (size > 0) {
    00344
    00345     /*
    00346      * place check here to see which set of blocks we're looking through
    00347      */
    00348
    00349     // scan through direct blocks
    00350     do {
    00351       if (offset >= sum && offset < sum + inode->blocks.direct[i].len * bSize)          break;
    00352
    00353       sum += inode->blocks.direct[i++].len * bSize;
    00354
    00355     } while (i < NUM_DIRECT_BLOCKS);
    00356
    00357     startingBlock = (inode->blocks.direct[i].AG << superBlock->AGShift) +
    00358                      inode->blocks.direct[i].start + ((offset - sum) / bSize);
    00359
    00360     runSize = inode->blocks.direct[i].len * bSize;
    00361
    00362     // startingBlock is in 4k blocks
    00363     startingBlock *= (bSize / 512);
    00364     // startingBlock is now in sectors
    00365
    00366     if (runSize >= size) {
    00367       runSize = size;
    00368       size = 0;
    00369     } else {
    00370       size -= runSize;
    00371     } // else
    00372
    00373     sectorCount = runSize / 512;
    00374
    00375     cout << "device->read(device, data, " << startingBlock << ", ";
    00376     cout << sectorCount << ");" << endl;
    00377
    00378     device->read(device, data, startingBlock, sectorCount);
    00379
    00380     (uInt8 *)data += runSize;
    00381     totalSize += runSize;
    00382   } // while
    00383   return totalSize;
    00384 } // UbixFS::vfs_read
    00385
    00386 size_t
    00387 UbixFS::vfs_write(fileDescriptor * fd, void * data, off_t offset, size_t size) {
    00388   // char * sector[512];  // used to pad
    00389   unsigned int i, whichBlocks;
    00390   off_t sum, startingBlock, EORPos, maxRange;
    00391   size_t runSize, runRemainder, sectorCount, totalSize, bSize; // blockSize
    00392   ubixfsInode * inode = NULL;
    00393   blockRun br;
    00394
    00395   if (fd == NULL || data == NULL) return ~0;
    00396
    00397   if (size == 0) return 0; // don't fail if size is 0?
    00398
    00399   assert(device);
    00400   assert(superBlock);
    00401
    00402   inode = static_cast<ubixfsInode *>(fd->inode);
    00403
    00404   assert(inode);
    00405
    00406   bSize = superBlock->blockSize;
    00407   assert(bSize != 0);
    00408
    00409   totalSize = sum = i = whichBlocks = 0;
    00410
    00411   EORPos = offset + size;  // compute End Of Run Position
    00412   maxRange = inode->blocks.maxDirectRange;
    00413
    00414   if (inode->blocks.maxIndirectRange > maxRange) {
    00415     maxRange = inode->blocks.maxIndirectRange;
    00416     whichBlocks = 1;
    00417   }
    00418
    00419   if (inode->blocks.maxDoubleIndirectRange > maxRange) {
    00420     maxRange = inode->blocks.maxDoubleIndirectRange;
    00421     whichBlocks = 2;
    00422   }
    00423
    00424   if (EORPos > maxRange) {
    00425     /*
    00426      * The offset+size is greater than the size of the file, so we need to
    00427      * extend out the file. Scan through the direct blocks (FIX LATER)
    00428      * to find out where we need to extend
    00429      */
    00430     switch (whichBlocks) {
    00431       case 0:
    00432         while (i < NUM_DIRECT_BLOCKS && inode->blocks.direct[i].len != 0) ++i;
    00433         // i holds which direct block we're going to add to
    00434         break;
    00435       case 1:
    00436       case 2:
    00437         assert(false);  // UNFINISHED
    00438         break;
    00439       default:
    00440         assert(false);  // sanity check
    00441     } // switch
    00442
    00443     /*
    00444      * NOTE: it's possible that if we scan through to find where the
    00445      * run goes, we might be able to extend the previous block extent.
    00446      * This will require that we set up br.start to be where we'd like to
    00447      * start looking through the free block list, and then modifying
    00448      * getFreeBlock() to honour that.
    00449      */
    00450
    00451     br.AG = inode->inodeNum.AG;        // request a sane allocation group
    00452     br.start = 0;                      // getFreeBlock() will ignore this
    00453
    00454     /*
    00455      * The length that we need is determined by how much extra slack we
    00456      * already have in the pre-allocated blocks.
    00457      * e.g. (assumes 4k blocks)
    00458      * bSize = 4096
    00459      * maxRange = 4096
    00460      * size = 3000
    00461      * offset = 3000
    00462      * size = 4000
    00463      * [--- data block ---][--- data block ---]  <---- blocks on disk
    00464      * <-file data->                             <---- actual file size
    00465      *              <----->                      <---- slack
    00466      * [  data block size ]                      <---- maxRange
    00467      *              |                            <---- offset
    00468      *              *****************            <---- new data
    00469      *
    00470      * In the above example, you'd need at least one more block to write
    00471      * out the data.
    00472      * ((offset + size) - maxRange + (bSize-1)) / bSize
    00473      * ((3000 + 4000) - 4096 + (4095)) / 4096 == 1 (rounded down)
    00474      * And then we expand it by a little extra so we don't have to keep
    00475      * looking for more blocks. Currently we use 32k of slack (or 8 blocks)
    00476      */
    00477
    00478     br.len = ((EORPos - maxRange + (bSize-1)) / bSize);
    00479
    00480     if (br.len < 8) br.len = 8;  // we allocate 32k if the file needs to grow
    00481
    00482     br = getFreeBlock(br);
    00483     assert(br.len > 0);
    00484     switch (whichBlocks) {
    00485       case 0:
    00486         inode->blocks.direct[i] = br;
    00487         inode->blocks.maxDirectRange += br.len * bSize;
    00488         break;
    00489       case 1:
    00490         assert(false); // UNFINISHED
    00491         inode->blocks.maxIndirectRange += br.len * bSize;
    00492         break;
    00493       case 2:
    00494         assert(false); // UNFINISHED
    00495         inode->blocks.maxDoubleIndirectRange += br.len * bSize;
    00496         break;
    00497       default:
    00498         assert(false); // sanity check
    00499     } // switch
    00500
    00501     inode->blocks.size = EORPos;
    00502   } // if
    00503
    00504
    00505   runRemainder = size % 512;
    00506   size -= runRemainder;
    00507
    00508   totalSize = sum = i = 0;
    00509
    00510   while (size > 0) {
    00511
    00512     /*
    00513      * place check here to see which set of blocks we're looking through
    00514      */
    00515
    00516     // scan through direct blocks
    00517     do {
    00518       if (offset >= sum && offset < sum + inode->blocks.direct[i].len * bSize)
    00519         break;
    00520
    00521       sum += inode->blocks.direct[i++].len * bSize;
    00522
    00523     } while (i < NUM_DIRECT_BLOCKS);
    00524
    00525     startingBlock = (inode->blocks.direct[i].AG << superBlock->AGShift) +
    00526                      inode->blocks.direct[i].start + ((offset - sum) / bSize);
    00527
    00528     runSize = inode->blocks.direct[i].len * bSize;
    00529
    00530     // startingBlock is in 4k blocks
    00531     startingBlock *= (bSize / 512);
    00532     // startingBlock is now in sectors
    00533
    00534     if (runSize >= size) {
    00535       runSize = size;
    00536       size = 0;
    00537     } else {
    00538       size -= runSize;
    00539     } // else
    00540
    00541     sectorCount = runSize / 512;
    00542
    00543     cout << "device->write(device, data, " << startingBlock << ", ";
    00544     cout << sectorCount << ");" << endl;
    00545
    00546     device->write(device, data, startingBlock, sectorCount);
    00547
    00548     (uInt8 *)data += runSize;
    00549     totalSize += runSize;
    00550   } // while
    00551
    00552   assert(runRemainder != 0);  // UNFINISHED
    00553   return totalSize;
    00554 } // UbixFS::vfs_write
    00555
    00556 int
    00557 UbixFS::vfs_stop(void) {
    00558   if (vfs_sync() != 0) return -1;
    00559
    00560   // you must delete the root dir first, in case it needs to
    00561   // still write anything out
    00562
    00563   if (root != NULL) {
    00564     ubixfsInode * rootInode = static_cast<ubixfsInode *>(root->inode);
    00565     delete rootInode->data.btPtr;
    00566     delete rootInode;
    00567     root->inode = NULL;
    00568
    00569   } // if
    00570
    00571   delete root;
    00572   delete [] freeBlockList;
    00573   delete superBlock;
    00574
    00575   freeBlockList = NULL;
    00576   superBlock = NULL;
    00577   root = NULL;
    00578
    00579   /*
    00580    * The device isn't null at this point, allowing for people to restart
    00581    * the mount point. Or, alternatively, to blow things up.
    00582    */
    00583
    00584   return 0;
    00585 } // UbixFS::vfs_stop
    00586
    00587 int
    00588 UbixFS::vfs_sync(void) {
    00589   if (device == NULL || superBlock == NULL || freeBlockList == NULL) return -1;
    00590   device->write(device,
    00591                 freeBlockList,
    00592                 device->sectors - superBlock->batSectors - 1,
    00593                 superBlock->batSectors
    00594                );
    00595   device->write(device, superBlock, device->sectors-1, 1);
    00596   return 0;
    00597 } // UbixFS::vfs_sync
    00598
    00599 void
    00600 UbixFS::setFreeBlock(blockRun ibr) {
    00601   signed char * ptr;
    00602
    00603   if (superBlock == NULL || freeBlockList == NULL) return;
    00604   if (ibr.len == 0) return;
    00605   ptr = freeBlockList + ((ibr.AG << superBlock->AGShift) >> 3);
    00606   ptr += ibr.start >> 3;
    00607
    00608   if (ibr.start % 8 != 0) {
    00609
    00610     ibr.len -= ibr.start % 8;
    00611   } // if
    00612
    00613 } // UbixFS::setFreeBlock
    00614
    00615 blockRun
    00616 UbixFS::getFreeBlock(blockRun ibr) {
    00617   signed char * ptr;
    00618   signed char * holdPtr;
    00619   int32 count, holdCount;
    00620
    00621   blockRun obr = {0, 0, 0};  // output block run
    00622
    00623   // Check to make sure none of these are null
    00624   if (device == NULL || freeBlockList == NULL || superBlock == NULL) return obr;
    00625
    00626   if (ibr.len == 0) return obr;
    00627
    00628   if (ibr.len > superBlock->numBlocks) return obr;
    00629
    00630   if (ibr.len == 1) return getFreeBlock(ibr.AG);
    00631   /*
    00632    * count is the block from the base of the list.
    00633    * Since we're given a specific AG to look through, we start the count at
    00634    * AG << AGShift, where AGShift is the shift value of the number of blocks
    00635    * in an AG
    00636    */
    00637
    00638   count = (ibr.AG << superBlock->AGShift);
    00639
    00640   /*
    00641    * The freeBlockList is a bit map of the free/used blocks.
    00642    * Used = on bit
    00643    * Unused = off bit
    00644    * There are 8 bits per byte (hopefully) and so we have to divide the count
    00645    * by 8 to get our starting byte offset to look from
    00646    */
    00647
    00648   ptr = freeBlockList + (count >> 3);
    00649
    00650 rescan:
    00651   // look for the first free 8 blocks (this may create holes)
    00652   while (*ptr != 0) {
    00653     ++ptr;
    00654     count += 8;
    00655     if (count+8 > superBlock->numBlocks) {
    00656       ptr = freeBlockList;
    00657       count = 0;
    00658     } // if
    00659   } // while *ptr != 0
    00660
    00661   holdPtr = ptr;
    00662   holdCount = count;
    00663
    00664   for (unsigned short i = 0; i < ((ibr.len+7) / 8); i++) {
    00665     ++ptr;
    00666     count += 8;
    00667     if (count+8 > superBlock->numBlocks) {
    00668       ptr = freeBlockList;
    00669       count = 0;
    00670       goto rescan;
    00671     } // if
    00672     if (*ptr != 0) goto rescan;
    00673   } // for i
    00674
    00675   // we have found a range of blocks that work for us
    00676
    00677   obr.AG = holdCount / superBlock->blocksPerAG;
    00678   obr.start = holdCount % superBlock->blocksPerAG;
    00679   obr.len = ibr.len;
    00680
    00681   for (unsigned short i = 0; i < (ibr.len / 8); i++) {
    00682     *holdPtr = -1;
    00683     ++holdPtr;
    00684   } // for
    00685
    00686   if (ibr.len % 8 != 0) *holdPtr = (-1 << (8-(ibr.len % 8)));
    00687
    00688   superBlock->usedBlocks += ibr.len;   // increment the number of used blocks
    00689   return obr;
    00690 } // UbixFS::getFreeBlock
    00691
    00692 blockRun
    00693 UbixFS::getFreeBlock(uInt32 AG) {
    00694   // AG == AllocationGroup
    00695   blockRun br;
    00696   signed char * ptr;
    00697   int32 count;
    00698   int32 subCount = 128;
    00699
    00700   br.AG = 0;
    00701   br.start = 0;
    00702   br.len = 0;
    00703   // Check to make sure neither of these are null
    00704   if (device == NULL || freeBlockList == NULL || superBlock == NULL) return br;
    00705
    00706   // Are there any blocks available?
    00707   if (superBlock->numBlocks == superBlock->usedBlocks) return br;
    00708
    00709   /*
    00710    * count is the block from the base of the list.
    00711    * Since we're given a specific AG to look through, we start the count at
    00712    * AG << AGShift, where AGShift is the shift value of the number of blocks
    00713    * in an AG
    00714    */
    00715
    00716   count = (AG << superBlock->AGShift);
    00717
    00718   /*
    00719    * The freeBlockList is a bit map of the free/used blocks.
    00720    * Used = on bit
    00721    * Unused = off bit
    00722    * There are 8 bits per byte (hopefully) and so we have to divide the count
    00723    * by 8 to get our starting byte offset to look from
    00724    */
    00725
    00726   ptr = freeBlockList + (count >> 3);
    00727
    00728   // Scan through the freeBlockList
    00729
    00730 rescan:
    00731   while (*ptr == -1) {
    00732     ++ptr;
    00733     count += 8;
    00734     if (count+8 > superBlock->numBlocks) break;
    00735   } // while *ptr == -1
    00736
    00737   subCount = 128;
    00738
    00739   do {
    00740     if ((*ptr & subCount) == 0) break;
    00741     subCount >>= 1;
    00742     ++count;
    00743     if (count == superBlock->numBlocks) {
    00744       count = 0;
    00745       ptr = freeBlockList;
    00746       goto rescan;
    00747     } // if
    00748   } while(subCount > 1);
    00749
    00750   *ptr |= subCount;           // mark this block as used
    00751   ++superBlock->usedBlocks;   // increment the number of used blocks
    00752
    00753   br.AG = count / superBlock->blocksPerAG;
    00754   br.start = count % superBlock->blocksPerAG;
    00755   br.len = 1;
    00756   return br;               // return the allocated block number
    00757 } // Ubixfs::getFreeBlock
    00758
    00759 uInt32
    00760 UbixFS::getNextAG(void) {
    00761
    00762   if (superBlock->lastUsedAG == superBlock->numAGs)
    00763     superBlock->lastUsedAG = 0;
    00764   else
    00765     superBlock->lastUsedAG++;
    00766   return superBlock->lastUsedAG;
    00767
    00768 } // UbixFS::getNextAG
    00769
    00770 /*
    00771  * UbixFS::getFreeBlock(void)
    00772  * upon success returns a free block based on the next AG after the lastUsedAG
    00773  * failure returns -1
    00774  */
    00775
    00776 blockRun
    00777 UbixFS::getFreeBlock(void) {
    00778   return getFreeBlock(getNextAG());
    00779 } // UbixFS::getFreeBlock
    00780
    00781 blockRun
    00782 UbixFS::get8FreeBlocks(uInt32 AG) {
    00783   // AG == AllocationGroup
    00784   blockRun br;
    00785   signed char * ptr;
    00786   signed char * endPtr;
    00787   int32 count;
    00788
    00789   br.AG = 0;
    00790   br.start = 0;
    00791   br.len = 0;
    00792
    00793   if (device == NULL || freeBlockList == NULL || superBlock == NULL) return br;
    00794
    00795   // Are there any blocks available?
    00796   if (superBlock->usedBlocks+8 > superBlock->numBlocks) return br;
    00797
    00798   /*
    00799    * count is the block from the base of the list.
    00800    * Since we're given a specific AG to look through, we start the count at
    00801    * AG << AGShift, where AGShift is the shift value of the number of blocks
    00802    * in an AG
    00803    */
    00804
    00805   count = (AG << superBlock->AGShift);
    00806
    00807   ptr = freeBlockList + (count >> 3);
    00808
    00809   endPtr = freeBlockList + (superBlock->numBlocks >> 3);
    00810
    00811   bool secondTime = false;
    00812   while (*ptr != 0) {
    00813     ++ptr;
    00814     count += 8;
    00815     if (ptr == endPtr) {
    00816       if (secondTime)
    00817         return br;
    00818       else
    00819         secondTime = true;
    00820
    00821       count = 0;
    00822       ptr = freeBlockList;
    00823     } // if
    00824   } // while
    00825
    00826   *ptr = -1;   // mark 8 blocks as taken
    00827
    00828   br.AG = count / superBlock->blocksPerAG;
    00829   br.start = count % superBlock->blocksPerAG;
    00830   br.len = 8;
    00831   return br;
    00832 } // UbixFS::get8FreeBlocks
    00833
    00834 void *
    00835 UbixFS::mknod(const char *filename, ubixfsInode * parent, mode_t mode) {
    00836   ubixfsInode * inode = NULL;
    00837
    00838   inode = new ubixfsInode;
    00839   assert(inode);
    00840   if (inode == NULL) return NULL;
    00841   memset(inode, 0, sizeof(ubixfsInode));
    00842
    00843   inode->magic1 = UBIXFS_INODE_MAGIC;
    00844
    00845   /*
    00846    * in retrospect.. I'm not sure why parent would be null.. only the
    00847    * root directory would have a null parent, but that's manually allocated
    00848    * in vfs_format()
    00849    */
    00850
    00851   if (parent == NULL) {
    00852     inode->inodeNum = getFreeBlock();
    00853     inode->parent.iAddr.AG = 0;
    00854     inode->parent.iAddr.start = 0;
    00855     inode->parent.iAddr.len = 0;
    00856   } else {
    00857     inode->inodeNum = getFreeBlock(parent->inodeNum.AG);
    00858     inode->parent.iAddr = parent->inodeNum;
    00859   } // else
    00860
    00861   strncpy(inode->name, filename, MAX_FILENAME_LENGTH);
    00862
    00863   inode->uid = getuid();
    00864   inode->gid = getgid();
    00865   // inode->mode
    00866   inode->flags = mode;
    00867   // inode->createTime
    00868   // inode->lastModifiedTime
    00869   inode->inodeSize = superBlock->inodeSize;
    00870
    00871   inode->attributes.AG = 0;
    00872   inode->attributes.start = 0;
    00873   inode->attributes.len = 0;
    00874
    00875   // inode->type
    00876
    00877   /*
    00878    * next and prev are used in memory to hold pointers to the next/prev
    00879    * inodes in this dir.  On disk they may have another value, but for
    00880    * now they should be set to null.
    00881    */
    00882
    00883   inode->next.offset = 0;
    00884   inode->prev.offset = 0;
    00885   inode->refCount = 0;
    00886   ++superBlock->inodeCount;
    00887   return inode;
    00888 } // UbixFS::mknod
    00889
    00890 int
    00891 UbixFS::vfs_mkdir(const char * path, mode_t mode) {
    00892   char name[MAX_FILENAME_LENGTH];
    00893   unsigned int start, end, len, nameStart;
    00894   ubixfsInode * dir = static_cast<ubixfsInode *>(root->inode);
    00895   ubixfsInode * inode = NULL;
    00896
    00897   assert(path);                     // bad input: vfs_mkdir(NULL);
    00898   assert(*path);                    // bad input: vfs_mkdir("");
    00899
    00900   memset(&name, 0, sizeof(name));
    00901   // find the dir name
    00902   len = strlen(path);
    00903
    00904   assert(path[0] == '/');           // bad input: vfs isn't doing its job
    00905   assert(len > 1);                  // bad input: mkdir /
    00906
    00907   // remove trailing "/" if present
    00908   if (path[len-1] == '/') --len;
    00909
    00910   assert(len > 1);                  // bad input: mkdir //
    00911
    00912   nameStart = len-1;
    00913
    00914   assert(path[nameStart] != '/');   // bad input: mkdir /a//
    00915
    00916   /*
    00917    * we're guaranteed by the assert() above that there is
    00918    * at least one "/" before our location. If you remove the assert
    00919    * you might need to make sure nameStart stays above 0 in the following
    00920    * while
    00921    */
    00922
    00923   while (path[nameStart] != '/') --nameStart;
    00924   ++nameStart;
    00925   assert(len - nameStart > 0);
    00926
    00927   /* e.g.
    00928    *   v--------------------- start
    00929    *      v------------------ end
    00930    *                  v------ nameStart
    00931    *  /usr/local/data/dirname/  <--- ignores trailing /
    00932    *  <---------23----------> len
    00933    */
    00934
    00935   start = end = 1;   // skip leading /
    00936   while (end < nameStart) {
    00937     do { ++end; } while(path[end] != '/');
    00938
    00939     assert(end-start+1 < sizeof(name));
    00940     // this is probably wrong:
    00941     strncpy(name, &path[start], end-start+1);
    00942     cout << name << endl;
    00943     dir = dir->data.btPtr->Find(name);
    00944     assert(dir);
    00945     assert(dir->flags & INODE_DIRECTORY == INODE_DIRECTORY);
    00946     start = ++end;
    00947   }
    00948
    00949   strncpy(name, &path[nameStart], len - nameStart);
    00950   inode = (ubixfsInode *)mknod(name, dir, mode | INODE_DIRECTORY);
    00951
    00952   /*
    00953    * keep in mind that the reason for passing in the name is because
    00954    * we thought about allowing key names to be different from inode
    00955    * names. In retrospect, I don't think that's a good idea since a dir
    00956    * listing will print the actual dir name instead of . and ..
    00957    * Thus: the first parameter of btPtr->Insert() may go away.
    00958    */
    00959
    00960   assert(dir->data.btPtr->Insert(inode->name, inode));
    00961
    00962   return 0;
    00963 } // UbixFS::vfs_mkdir
    00964
    00965 void
    00966 UbixFS::printFreeBlockList(uInt32 AG) {
    00967   unsigned int j;
    00968   if (superBlock == NULL || freeBlockList == NULL) return;
    00969   printf("AG = %d\n", AG);
    00970   for (unsigned int i = 0; i < superBlock->blocksPerAG / 8; i++) {
    00971     j = 128;
    00972     signed char foo = freeBlockList[(AG << superBlock->AGShift)+i];
    00973     while (j > 0) {
    00974       if ((foo & j) == j)
    00975         printf("1");
    00976       else
    00977         printf("0");
    00978       j >>= 1;
    00979
    00980     }
    00981   } // for i
    00982   printf("\n");
    00983   return;
    00984 } // UbixFS::printFreeBlockList
    00985
    00986 UbixFS::~UbixFS(void) {
    00987   delete [] freeBlockList;
    00988   return;
    00989 }