ubixfs.cpp
stddef.h
stdlib.h
unistd.h
string.h
assert.h
iostream
ubixfs.h
btree.h
src/sys/ubixfsv2/ubixfs.cpp
btree.h
stdlib.h
ubixfs.h
ubixos/types.h
sys/_types.h
stddef.h
string.h
btreeheader.h
file.h
sys/types.h
fsAbstract.h
types.h
unistd.h
device.h
assert.h
iostream
stdio.h
dirent.h

    #include<stddef.h>
    #include<stdlib.h>
    #include<unistd.h>
    #include<string.h>
    #include<assert.h>
    #include<iostream>

    #include"ubixfs.h"
    #include"btree.h"

    usingnamespacestd;

    UbixFS::UbixFS(void){
    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
    UbixFS::printSuperBlock(void){
    printf("superBlock->name...........%s\n",superBlock->name);
    printf("superBlock->magic1.........%X\n",superBlock->magic1);
    printf("superBlock->fsByteOrder....%d\n",superBlock->fsByteOrder);
    printf("superBlock->blockSize......%d\n",superBlock->blockSize);
    printf("superBlock->blockShift.....%d\n",superBlock->blockShift);
    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);
    printf("superBlock->blocksPerAG....%d\n",superBlock->blocksPerAG);
    printf("superBlock->AGShift........%d\n",superBlock->AGShift);
    printf("superBlock->numAGs.........%d\n",superBlock->numAGs);
    printf("superBlock->lastUsedAG.....%d\n",superBlock->lastUsedAG);
    printf("superBlock->flags..........%X\n",superBlock->flags);
    printf("superBlock->magic3.........%X\n",superBlock->magic3);
    return;
    }//UbixFS::printSuperBlock

    int
    UbixFS::vfs_init(void){
    assert(device);
    size_tresult;
    cout<<"vfs_init()"<<endl;
    assert(device);

    if(device==NULL)return-1;
    if(superBlock!=NULL)deletesuperBlock;
    superBlock=newdiskSuperBlock;
    assert(superBlock);
    if(superBlock==NULL)return-1;

    //readinthesuperBlock.It'salwaysthelastblockonthepartition
    cout<<"readinginsuperBlock"<<endl;
    device->read(device,superBlock,device->sectors-1,1);
    cout<<"done"<<endl;

    assert(superBlock->magic1==UBIXFS_MAGIC1);
    assert(superBlock->magic2==UBIXFS_MAGIC2);
    assert(superBlock->magic3==UBIXFS_MAGIC3);
    assert(strcmp(superBlock->name,"UbixFS")==0);
    assert((1<<superBlock->blockShift)==superBlock->blockSize);
    assert((unsigned)(1<<superBlock->AGShift)==superBlock->blocksPerAG);
    assert(superBlock->flags==UBIXFS_CLEAN);

    if(freeBlockList!=NULL)delete[]freeBlockList;
    freeBlockList=newsignedchar[superBlock->batSectors*512];
    assert(freeBlockList);
    memset(freeBlockList,0,superBlock->batSectors*512);

    device->read(device,
    freeBlockList,
    device->sectors-superBlock->batSectors-1,
    superBlock->batSectors
    );//device->read()

    root=newfileDescriptor;
    assert(root);
    memset(root,0,sizeof(fileDescriptor));
    cout<<"allocatingrootdirinode"<<endl;
    root->inode=newubixfsInode;
    memset(root->inode,0,sizeof(ubixfsInode));
    cout<<"rootdirinodestartingsector:"<<
    ((superBlock->rootDir.AG<<superBlock->AGShift)
    +superBlock->rootDir.start)*(superBlock->blockSize/512)
    <<endl;

    cout<<"readinginrootdirinode"<<endl;

    device->read(device,
    root->inode,
    ((superBlock->rootDir.AG<<superBlock->AGShift)
    +superBlock->rootDir.start)*(superBlock->blockSize/512),
    sizeof(ubixfsInode)/512
    );
    cout<<"done"<<endl;
    ubixfsInode*rootInode=static_cast<ubixfsInode*>(root->inode);
    assert(rootInode);

    /*thebTreeconstructornowloadsintheheader*/

    rootInode->data.btPtr=newbTree(this,root);
    rootInode->data.btPtr->Info();
    printSuperBlock();
    return0;
    }//UbixFS::init

    int
    UbixFS::vfs_format(device_t*dev){
    cout<<"vfs_format()"<<endl;
    charsector[512];
    uInt32blocks,batSect,batSize;
    if(dev==NULL)return-1;

    //zerooutthesector
    memset(&sector,0x0,sizeof(sector));

    //fillthedriveinwithzeroedoutsectors
    cout<<"dev->sectors:"<<dev->sectors<<endl;
    cout<<"clearingdevice...";

    for(unsignedinti=0;i<dev->sectors;i++){
    dev->write(dev,&sector,i,1);
    }//fori

    cout<<"done"<<endl;

    //allocateanewsuperBlockandclearit

    diskSuperBlock*sb=newdiskSuperBlock;
    if(sb==NULL)return-1;
    memset(sb,0,sizeof(diskSuperBlock));

    //dev->sectorsisthenumberof512bytesectors

    blocks=(dev->sectors-1)/8;//4kblocks
    batSize=(dev->sectors-1)%8;//remainder

    //computetheBATsize

    while((batSize*4096)<blocks){
    batSize+=8;
    --blocks;
    }//while

    //batSizeisinsectors
    batSect=blocks*8;

    strcpy(sb->name,"UbixFS");
    sb->magic1=UBIXFS_MAGIC1;
    sb->fsByteOrder=0;
    sb->blockSize=4096;
    sb->blockShift=12;
    sb->numBlocks=blocks;
    sb->usedBlocks=2;//rootdirtakestwoblocks(inode+bTreeheader)
    sb->inodeCount=1;
    sb->inodeSize=4096;
    sb->magic2=UBIXFS_MAGIC2;
    sb->blocksPerAG=2048;
    sb->AGShift=11;
    sb->numAGs=(sb->numBlocks+2047)/2048;
    sb->lastUsedAG=0;

    //theBATexistsoutsideourofficialblockcount,sono
    //entriesintheBATneedtobesetforit
    sb->batSectors=batSize;

    sb->flags=0x434C454E;//CLEN
    sb->logBlocks.AG=0;
    sb->logBlocks.start=0;
    sb->logBlocks.len=0;
    sb->logStart=0;
    sb->logEnd=0;
    sb->magic3=UBIXFS_MAGIC3;
    sb->indicies.AG=0;
    sb->indicies.start=0;
    sb->indicies.len=0;

    sb->rootDir.AG=0;
    sb->rootDir.start=0;
    sb->rootDir.len=1;

    //writeoutthesuperBlock

    dev->write(dev,sb,dev->sectors-1,1);

    //markthefirsttwo4kblocksused
    memset(&sector,0,sizeof(sector));
    sector[0]=(1<<7)|(1<<6);

    //writeoutthefirstsectoroftheBAT

    dev->write(dev,&sector,batSect,1);
    //cleartherest
    sector[0]=0;

    //writeouttherestoftheBAT

    for(unsignedinti=1;i<batSize;i++){
    dev->write(dev,&sector,(batSect)+i,1);
    }//fori

    /*allocatepartoftherootdir*/

    //sanitychecks
    assert(sb->blockSize);
    assert((unsigned)sb->blockSize>=sizeof(bTreeHeader));

    bTreeHeader*bth=newbTreeHeader;
    assert(bth);
    memset(bth,0,sizeof(bTreeHeader));

    bth->firstDeleted=-1;
    bth->firstNodeOffset=-1;
    bth->treeDepth=1;
    bth->treeWidth=0;
    bth->treeLeafCount=0;

    /*createtherootdirinodehere*/

    ubixfsInode*inode=newubixfsInode;
    assert(inode);
    if(inode==NULL)return-1;
    memset(inode,0,sizeof(ubixfsInode));

    inode->magic1=UBIXFS_INODE_MAGIC;

    //inodespointtothemselves
    inode->inodeNum.AG=0;
    inode->inodeNum.start=0;
    inode->inodeNum.len=1;

    //rootdirhasnoparentdirectory
    inode->parent.iAddr.AG=0;
    inode->parent.iAddr.start=0;
    inode->parent.iAddr.len=0;

    /*thisispartoftherootdirstructure(thebTreeHeader)*/
    inode->blocks.direct[0].AG=0;
    inode->blocks.direct[0].start=1;
    inode->blocks.direct[0].len=1;

    inode->blocks.maxDirectRange=sizeof(bTreeHeader);
    inode->blocks.size=sizeof(bTreeHeader);

    strcpy(inode->name,"/");
    inode->uid=getuid();
    inode->gid=getgid();
    //inode->mode
    inode->flags=INODE_DIRECTORY;
    //inode->createTime
    //inode->lastModifiedTime
    //inode->type

    inode->attributes.AG=0;
    inode->attributes.start=0;
    inode->attributes.len=0;

    inode->inodeSize=sb->inodeSize;

    /*
    *nextandprevareusedinmemorytoholdpointerstothenext/prev
    *inodesinthisdir.Ondisktheymayhaveanothervalue,butfor
    *nowtheyshouldbesettonull.
    */

    inode->next.offset=0;
    inode->prev.offset=0;

    //writeoutthe"root"dirinode

    dev->write(dev,
    inode,
    ((inode->inodeNum.AG<<sb->AGShift)+
    inode->inodeNum.start)*(sb->blockSize/512),
    sb->inodeSize/512
    );//dev->write

    //writeoutthe"root"dir

    dev->write(dev,
    bth,
    ((inode->blocks.direct[0].AG<<sb->AGShift)+
    inode->blocks.direct[0].start)*(sb->blockSize/512),
    sb->blockSize/512
    );//dev->write

    deleteinode;
    deletebth;
    deletesb;
    cout<<"formatcomplete"<<endl;
    return0;
    }//UbixFS::vfs_format

    void*
    UbixFS::vfs_mknod(constchar*path,mode_tmode){
    returnmknod(path,0,mode);//<-thisprobablyisn'tcorrect
    }//UbixFS::vfs_mknod

    int
    UbixFS::vfs_open(constchar*filename,fileDescriptor*fd,intflags,...){
    if(filename==NULL||fd==NULL)return-1;
    flags=flags;
    fd->inode=NULL;
    fd->offset=0;
    fd->size=0;
    //lookupthefilehere
    return0;
    }//UbixFS::vfs_open

    size_t
    UbixFS::vfs_read(fileDescriptor*fd,void*data,off_toffset,size_tsize){

    unsignedinti;
    off_tsum,startingBlock;
    size_trunSize,sectorCount,totalSize,bSize;//blockSize
    ubixfsInode*inode=NULL;

    if(fd==NULL||data==NULL)return~0;

    if(size==0)return0;//don'tfailifsizeis0?

    assert(device);
    assert(superBlock);

    inode=static_cast<ubixfsInode*>(fd->inode);

    assert(inode);

    bSize=superBlock->blockSize;

    totalSize=sum=i=0;

    while(size>0){

    /*
    *placecheckheretoseewhichsetofblockswe'relookingthrough
    */

    //scanthroughdirectblocks
    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;

    //startingBlockisin4kblocks
    startingBlock*=(bSize/512);
    //startingBlockisnowinsectors

    if(runSize>=size){
    runSize=size;
    size=0;
    }else{
    size-=runSize;
    }//else

    sectorCount=runSize/512;

    cout<<"device->read(device,data,"<<startingBlock<<",";
    cout<<sectorCount<<");"<<endl;

    device->read(device,data,startingBlock,sectorCount);

    (uInt8*)data+=runSize;
    totalSize+=runSize;
    }//while
    returntotalSize;
    }//UbixFS::vfs_read

    size_t
    UbixFS::vfs_write(fileDescriptor*fd,void*data,off_toffset,size_tsize){
    //char*sector[512];//usedtopad
    unsignedinti,whichBlocks;
    off_tsum,startingBlock,EORPos,maxRange;
    size_trunSize,runRemainder,sectorCount,totalSize,bSize;//blockSize
    ubixfsInode*inode=NULL;
    blockRunbr;

    if(fd==NULL||data==NULL)return~0;

    if(size==0)return0;//don'tfailifsizeis0?

    assert(device);
    assert(superBlock);

    inode=static_cast<ubixfsInode*>(fd->inode);

    assert(inode);

    bSize=superBlock->blockSize;
    assert(bSize!=0);

    totalSize=sum=i=whichBlocks=0;

    EORPos=offset+size;//computeEndOfRunPosition
    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){
    /*
    *Theoffset+sizeisgreaterthanthesizeofthefile,soweneedto
    *extendoutthefile.Scanthroughthedirectblocks(FIXLATER)
    *tofindoutwhereweneedtoextend
    */
    switch(whichBlocks){
    case0:
    while(i<NUM_DIRECT_BLOCKS&&inode->blocks.direct[i].len!=0)++i;
    //iholdswhichdirectblockwe'regoingtoaddto
    break;
    case1:
    case2:
    assert(false);//UNFINISHED
    break;
    default:
    assert(false);//sanitycheck
    }//switch

    /*
    *NOTE:it'spossiblethatifwescanthroughtofindwherethe
    *rungoes,wemightbeabletoextendthepreviousblockextent.
    *Thiswillrequirethatwesetupbr.starttobewherewe'dliketo
    *startlookingthroughthefreeblocklist,andthenmodifying
    *getFreeBlock()tohonourthat.
    */

    br.AG=inode->inodeNum.AG;//requestasaneallocationgroup
    br.start=0;//getFreeBlock()willignorethis

    /*
    *Thelengththatweneedisdeterminedbyhowmuchextraslackwe
    *alreadyhaveinthepre-allocatedblocks.
    *e.g.(assumes4kblocks)
    *bSize=4096
    *maxRange=4096
    *size=3000
    *offset=3000
    *size=4000
    *[---datablock---][---datablock---]<----blocksondisk
    *<-filedata-><----actualfilesize
    *<-----><----slack
    *[datablocksize]<----maxRange
    *|<----offset
    ******************<----newdata
    *
    *Intheaboveexample,you'dneedatleastonemoreblocktowrite
    *outthedata.
    *((offset+size)-maxRange+(bSize-1))/bSize
    *((3000+4000)-4096+(4095))/4096==1(roundeddown)
    *Andthenweexpanditbyalittleextrasowedon'thavetokeep
    *lookingformoreblocks.Currentlyweuse32kofslack(or8blocks)
    */

    br.len=((EORPos-maxRange+(bSize-1))/bSize);

    if(br.len<8)br.len=8;//weallocate32kifthefileneedstogrow

    br=getFreeBlock(br);
    assert(br.len>0);
    switch(whichBlocks){
    case0:
    inode->blocks.direct[i]=br;
    inode->blocks.maxDirectRange+=br.len*bSize;
    break;
    case1:
    assert(false);//UNFINISHED
    inode->blocks.maxIndirectRange+=br.len*bSize;
    break;
    case2:
    assert(false);//UNFINISHED
    inode->blocks.maxDoubleIndirectRange+=br.len*bSize;
    break;
    default:
    assert(false);//sanitycheck
    }//switch

    inode->blocks.size=EORPos;
    }//if

    runRemainder=size%512;
    size-=runRemainder;

    totalSize=sum=i=0;

    while(size>0){

    /*
    *placecheckheretoseewhichsetofblockswe'relookingthrough
    */

    //scanthroughdirectblocks
    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;

    //startingBlockisin4kblocks
    startingBlock*=(bSize/512);
    //startingBlockisnowinsectors

    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
    returntotalSize;
    }//UbixFS::vfs_write

    int
    UbixFS::vfs_stop(void){
    if(vfs_sync()!=0)return-1;

    //youmustdeletetherootdirfirst,incaseitneedsto
    //stillwriteanythingout

    if(root!=NULL){
    ubixfsInode*rootInode=static_cast<ubixfsInode*>(root->inode);
    deleterootInode->data.btPtr;
    deleterootInode;
    root->inode=NULL;

    }//if

    deleteroot;
    delete[]freeBlockList;
    deletesuperBlock;

    freeBlockList=NULL;
    superBlock=NULL;
    root=NULL;

    /*
    *Thedeviceisn'tnullatthispoint,allowingforpeopletorestart
    *themountpoint.Or,alternatively,toblowthingsup.
    */

    return0;
    }//UbixFS::vfs_stop

    int
    UbixFS::vfs_sync(void){
    if(device==NULL||superBlock==NULL||freeBlockList==NULL)return-1;
    device->write(device,
    freeBlockList,
    device->sectors-superBlock->batSectors-1,
    superBlock->batSectors
    );
    device->write(device,superBlock,device->sectors-1,1);
    return0;
    }//UbixFS::vfs_sync

    void
    UbixFS::setFreeBlock(blockRunibr){
    signedchar*ptr;

    if(superBlock==NULL||freeBlockList==NULL)return;
    if(ibr.len==0)return;
    ptr=freeBlockList+((ibr.AG<<superBlock->AGShift)>>3);
    ptr+=ibr.start>>3;

    if(ibr.start%8!=0){

    ibr.len-=ibr.start%8;
    }//if

    }//UbixFS::setFreeBlock

    blockRun
    UbixFS::getFreeBlock(blockRunibr){
    signedchar*ptr;
    signedchar*holdPtr;
    int32count,holdCount;

    blockRunobr={0,0,0};//outputblockrun

    //Checktomakesurenoneofthesearenull
    if(device==NULL||freeBlockList==NULL||superBlock==NULL)returnobr;

    if(ibr.len==0)returnobr;

    if(ibr.len>superBlock->numBlocks)returnobr;

    if(ibr.len==1)returngetFreeBlock(ibr.AG);
    /*
    *countistheblockfromthebaseofthelist.
    *Sincewe'regivenaspecificAGtolookthrough,westartthecountat
    *AG<<AGShift,whereAGShiftistheshiftvalueofthenumberofblocks
    *inanAG
    */

    count=(ibr.AG<<superBlock->AGShift);

    /*
    *ThefreeBlockListisabitmapofthefree/usedblocks.
    *Used=onbit
    *Unused=offbit
    *Thereare8bitsperbyte(hopefully)andsowehavetodividethecount
    *by8togetourstartingbyteoffsettolookfrom
    */

    ptr=freeBlockList+(count>>3);

    rescan:
    //lookforthefirstfree8blocks(thismaycreateholes)
    while(*ptr!=0){
    ++ptr;
    count+=8;
    if(count+8>superBlock->numBlocks){
    ptr=freeBlockList;
    count=0;
    }//if
    }//while*ptr!=0

    holdPtr=ptr;
    holdCount=count;

    for(unsignedshorti=0;i<((ibr.len+7)/8);i++){
    ++ptr;
    count+=8;
    if(count+8>superBlock->numBlocks){
    ptr=freeBlockList;
    count=0;
    gotorescan;
    }//if
    if(*ptr!=0)gotorescan;
    }//fori

    //wehavefoundarangeofblocksthatworkforus

    obr.AG=holdCount/superBlock->blocksPerAG;
    obr.start=holdCount%superBlock->blocksPerAG;
    obr.len=ibr.len;

    for(unsignedshorti=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;//incrementthenumberofusedblocks
    returnobr;
    }//UbixFS::getFreeBlock

    blockRun
    UbixFS::getFreeBlock(uInt32AG){
    //AG==AllocationGroup
    blockRunbr;
    signedchar*ptr;
    int32count;
    int32subCount=128;

    br.AG=0;
    br.start=0;
    br.len=0;
    //Checktomakesureneitherofthesearenull
    if(device==NULL||freeBlockList==NULL||superBlock==NULL)returnbr;

    //Arethereanyblocksavailable?
    if(superBlock->numBlocks==superBlock->usedBlocks)returnbr;

    /*
    *countistheblockfromthebaseofthelist.
    *Sincewe'regivenaspecificAGtolookthrough,westartthecountat
    *AG<<AGShift,whereAGShiftistheshiftvalueofthenumberofblocks
    *inanAG
    */

    count=(AG<<superBlock->AGShift);

    /*
    *ThefreeBlockListisabitmapofthefree/usedblocks.
    *Used=onbit
    *Unused=offbit
    *Thereare8bitsperbyte(hopefully)andsowehavetodividethecount
    *by8togetourstartingbyteoffsettolookfrom
    */

    ptr=freeBlockList+(count>>3);

    //ScanthroughthefreeBlockList

    rescan:
    while(*ptr==-1){
    ++ptr;
    count+=8;
    if(count+8>superBlock->numBlocks)break;
    }//while*ptr==-1

    subCount=128;

    do{
    if((*ptr&subCount)==0)break;
    subCount>>=1;
    ++count;
    if(count==superBlock->numBlocks){
    count=0;
    ptr=freeBlockList;
    gotorescan;
    }//if
    }while(subCount>1);

    *ptr|=subCount;//markthisblockasused
    ++superBlock->usedBlocks;//incrementthenumberofusedblocks

    br.AG=count/superBlock->blocksPerAG;
    br.start=count%superBlock->blocksPerAG;
    br.len=1;
    returnbr;//returntheallocatedblocknumber
    }//Ubixfs::getFreeBlock

    uInt32
    UbixFS::getNextAG(void){

    if(superBlock->lastUsedAG==superBlock->numAGs)
    superBlock->lastUsedAG=0;
    else
    superBlock->lastUsedAG++;
    returnsuperBlock->lastUsedAG;

    }//UbixFS::getNextAG

    /*
    *UbixFS::getFreeBlock(void)
    *uponsuccessreturnsafreeblockbasedonthenextAGafterthelastUsedAG
    *failurereturns-1
    */

    blockRun
    UbixFS::getFreeBlock(void){
    returngetFreeBlock(getNextAG());
    }//UbixFS::getFreeBlock

    blockRun
    UbixFS::get8FreeBlocks(uInt32AG){
    //AG==AllocationGroup
    blockRunbr;
    signedchar*ptr;
    signedchar*endPtr;
    int32count;

    br.AG=0;
    br.start=0;
    br.len=0;

    if(device==NULL||freeBlockList==NULL||superBlock==NULL)returnbr;

    //Arethereanyblocksavailable?
    if(superBlock->usedBlocks+8>superBlock->numBlocks)returnbr;

    /*
    *countistheblockfromthebaseofthelist.
    *Sincewe'regivenaspecificAGtolookthrough,westartthecountat
    *AG<<AGShift,whereAGShiftistheshiftvalueofthenumberofblocks
    *inanAG
    */

    count=(AG<<superBlock->AGShift);

    ptr=freeBlockList+(count>>3);

    endPtr=freeBlockList+(superBlock->numBlocks>>3);

    boolsecondTime=false;
    while(*ptr!=0){
    ++ptr;
    count+=8;
    if(ptr==endPtr){
    if(secondTime)
    returnbr;
    else
    secondTime=true;

    count=0;
    ptr=freeBlockList;
    }//if
    }//while

    *ptr=-1;//mark8blocksastaken

    br.AG=count/superBlock->blocksPerAG;
    br.start=count%superBlock->blocksPerAG;
    br.len=8;
    returnbr;
    }//UbixFS::get8FreeBlocks

    void*
    UbixFS::mknod(constchar*filename,ubixfsInode*parent,mode_tmode){
    ubixfsInode*inode=NULL;

    inode=newubixfsInode;
    assert(inode);
    if(inode==NULL)returnNULL;
    memset(inode,0,sizeof(ubixfsInode));

    inode->magic1=UBIXFS_INODE_MAGIC;

    /*
    *inretrospect..I'mnotsurewhyparentwouldbenull..onlythe
    *rootdirectorywouldhaveanullparent,butthat'smanuallyallocated
    *invfs_format()
    */

    if(parent==NULL){
    inode->inodeNum=getFreeBlock();
    inode->parent.iAddr.AG=0;
    inode->parent.iAddr.start=0;
    inode->parent.iAddr.len=0;
    }else{
    inode->inodeNum=getFreeBlock(parent->inodeNum.AG);
    inode->parent.iAddr=parent->inodeNum;
    }//else

    strncpy(inode->name,filename,MAX_FILENAME_LENGTH);

    inode->uid=getuid();
    inode->gid=getgid();
    //inode->mode
    inode->flags=mode;
    //inode->createTime
    //inode->lastModifiedTime
    inode->inodeSize=superBlock->inodeSize;

    inode->attributes.AG=0;
    inode->attributes.start=0;
    inode->attributes.len=0;

    //inode->type

    /*
    *nextandprevareusedinmemorytoholdpointerstothenext/prev
    *inodesinthisdir.Ondisktheymayhaveanothervalue,butfor
    *nowtheyshouldbesettonull.
    */

    inode->next.offset=0;
    inode->prev.offset=0;
    inode->refCount=0;
    ++superBlock->inodeCount;
    returninode;
    }//UbixFS::mknod

    int
    UbixFS::vfs_mkdir(constchar*path,mode_tmode){
    charname[MAX_FILENAME_LENGTH];
    unsignedintstart,end,len,nameStart;
    ubixfsInode*dir=static_cast<ubixfsInode*>(root->inode);
    ubixfsInode*inode=NULL;

    assert(path);//badinput:vfs_mkdir(NULL);
    assert(*path);//badinput:vfs_mkdir("");

    memset(&name,0,sizeof(name));
    //findthedirname
    len=strlen(path);

    assert(path[0]=='/');//badinput:vfsisn'tdoingitsjob
    assert(len>1);//badinput:mkdir/

    //removetrailing"/"ifpresent
    if(path[len-1]=='/')--len;

    assert(len>1);//badinput:mkdir//

    nameStart=len-1;

    assert(path[nameStart]!='/');//badinput:mkdir/a//

    /*
    *we'reguaranteedbytheassert()abovethatthereis
    *atleastone"/"beforeourlocation.Ifyouremovetheassert
    *youmightneedtomakesurenameStartstaysabove0inthefollowing
    *while
    */

    while(path[nameStart]!='/')--nameStart;
    ++nameStart;
    assert(len-nameStart>0);

    /*e.g.
    *v---------------------start
    *v------------------end
    *v------nameStart
    */usr/local/data/dirname/<---ignorestrailing/
    *<---------23---------->len
    */

    start=end=1;//skipleading/
    while(end<nameStart){
    do{++end;}while(path[end]!='/');

    assert(end-start+1<sizeof(name));
    //thisisprobablywrong:
    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);

    /*
    *keepinmindthatthereasonforpassinginthenameisbecause
    *wethoughtaboutallowingkeynamestobedifferentfrominode
    *names.Inretrospect,Idon'tthinkthat'sagoodideasinceadir
    *listingwillprinttheactualdirnameinsteadof.and..
    *Thus:thefirstparameterofbtPtr->Insert()maygoaway.
    */

    assert(dir->data.btPtr->Insert(inode->name,inode));

    return0;
    }//UbixFS::vfs_mkdir

    void
    UbixFS::printFreeBlockList(uInt32AG){
    unsignedintj;
    if(superBlock==NULL||freeBlockList==NULL)return;
    printf("AG=%d\n",AG);
    for(unsignedinti=0;i<superBlock->blocksPerAG/8;i++){
    j=128;
    signedcharfoo=freeBlockList[(AG<<superBlock->AGShift)+i];
    while(j>0){
    if((foo&j)==j)
    printf("1");
    else
    printf("0");
    j>>=1;

    }
    }//fori
    printf("\n");
    return;
    }//UbixFS::printFreeBlockList

    UbixFS::~UbixFS(void){
    delete[]freeBlockList;
    return;
    }