rom/filesys/SFS/FS/nodes.c

   1 #include "asmsupport.h"
   2
   3 #include <dos/dos.h>
   4 #include <exec/types.h>
   5 #include <proto/exec.h>
   6
   7 #include "nodes.h"
   8
   9 #include "adminspaces_protos.h"
  10 #include "cachebuffers_protos.h"
  11 #include "debug.h"
  12 #include "req_protos.h"
  13 #include "support_protos.h"
  14 #include "globals.h"
  15
  16
  17 extern LONG readcachebuffercheck(struct CacheBuffer **,ULONG,ULONG);
  18 extern void setchecksum(struct CacheBuffer *);
  19
  20 LONG parentnodecontainer(BLCK noderoot, struct CacheBuffer **io_cb) {
  21   BLCK childblock=(*io_cb)->blckno;
  22   NODE nodenumber=BE2L(((struct fsNodeContainer *)((*io_cb)->data))->be_nodenumber);
  23   LONG errorcode=0;
  24
  25   /* Looks for the parent of the passed-in CacheBuffer (fsNodeContainer)
  26      starting from the root.  It returns an error if any error occured.
  27      If error is 0 and io_cb is 0 as well, then there was no parent (ie,
  28      you asked parent of the root).  Otherwise io_cb should contain the
  29      parent of the passed-in NodeContainer. */
  30
  31   *io_cb=0;
  32
  33   while(noderoot!=childblock && (errorcode=readcachebuffercheck(io_cb, noderoot, NODECONTAINER_ID))==0) {
  34     struct fsNodeContainer *nc=(*io_cb)->data;
  35
  36     if(BE2L(nc->be_nodes)==1) {
  37       /* We've descended the tree to a leaf NodeContainer, something
  38          which should never happen if the passed-in CacheBuffer had
  39          contained a valid fsNodeContainer. */
  40
  41       req_unusual("Failed to locate the parent NodeContainer\n"\
  42                   "of block %ld.");
  43
  44       *io_cb=0;
  45
  46       return(INTERR_NODES);
  47     }
  48     else {
  49       UWORD containerentry=(nodenumber - BE2L(nc->be_nodenumber))/BE2L(nc->be_nodes);
  50
  51       noderoot=BE2L(nc->be_node[containerentry])>>globals->shifts_block32;
  52     }
  53   }
  54
  55   return(errorcode);
  56 }
  57
  58
  59
  60 int isfull(struct fsNodeContainer *nc) {
  61   BLCKn *p=nc->be_node;
  62   WORD n=globals->node_containers;
  63
  64   while(--n>=0) {
  65     if(*p==0 || (BE2L(*p) & 0x00000001)==0) {
  66       break;
  67     }
  68     p++;
  69   }
  70
  71   return(n<0);
  72 }
  73
  74
  75
  76 LONG markparentfull(BLCK noderoot, struct CacheBuffer *cb) {
  77   NODE nodenumber=BE2L(((struct fsNodeContainer *)(cb->data))->be_nodenumber);
  78   LONG errorcode;
  79
  80   if((errorcode=parentnodecontainer(noderoot, &cb))==0 && cb!=0) {
  81     struct fsNodeContainer *nc=cb->data;
  82
  83     preparecachebuffer(cb);
  84
  85     nc->be_node[(nodenumber-BE2L(nc->be_nodenumber))/BE2L(nc->be_nodes)]|=L2BE(0x00000001);
  86
  87     if((errorcode=storecachebuffer(cb))==0) {
  88       if(isfull(nc)) {        /* This container now is full as well!  Mark the next higher up container too then! */
  89         return(markparentfull(noderoot, cb));
  90       }
  91     }
  92   }
  93
  94   return(errorcode);
  95 }
  96
  97
  98
  99 LONG markparentempty(BLCK noderoot, struct CacheBuffer *cb) {
 100   NODE nodenumber=BE2L(((struct fsNodeContainer *)(cb->data))->be_nodenumber);
 101   LONG errorcode;
 102
 103   if((errorcode=parentnodecontainer(noderoot, &cb))==0 && cb!=0) {
 104     struct fsNodeContainer *nc=cb->data;
 105     int wasfull;
 106
 107     wasfull=isfull(nc);
 108
 109     preparecachebuffer(cb);
 110
 111     nc->be_node[(nodenumber-BE2L(nc->be_nodenumber))/BE2L(nc->be_nodes)]&=~L2BE(0x00000001);
 112
 113     if((errorcode=storecachebuffer(cb))==0) {
 114       if(wasfull) {
 115         /* This container was completely full before!  Mark the next higher up container too then! */
 116
 117         return(markparentempty(noderoot, cb));
 118       }
 119     }
 120   }
 121
 122   return(errorcode);
 123 }
 124
 125
 126
 127 LONG freecontainer(BLCK noderoot, struct CacheBuffer *cb) {
 128   NODE nodenumber=BE2L(((struct fsNodeContainer *)(cb->data))->be_nodenumber);
 129   LONG errorcode;
 130
 131   if((errorcode=parentnodecontainer(noderoot, &cb))==0 && cb!=0) {   /* This line also prevents the freeing of the noderoot. */
 132     struct fsNodeContainer *nc=cb->data;
 133     UWORD containerindex=(nodenumber-BE2L(nc->be_nodenumber))/BE2L(nc->be_nodes);
 134
 135     lockcachebuffer(cb);
 136
 137     if((errorcode=freeadminspace(BE2L(nc->be_node[containerindex])>>globals->shifts_block32))==0) {
 138
 139       unlockcachebuffer(cb);
 140
 141       preparecachebuffer(cb);
 142
 143       nc->be_node[containerindex]=0;
 144
 145       if((errorcode=storecachebuffer(cb))==0) {
 146         BLCKn *p=nc->be_node;
 147         WORD n=globals->node_containers;
 148
 149         while(n-->0) {
 150           if(*p++!=0) {
 151             break;
 152           }
 153         }
 154
 155         if(n<0) {          /* This container is now completely empty!  Free this NodeIndexContainer too then! */
 156           return(freecontainer(noderoot, cb));
 157         }
 158       }
 159     }
 160     else {
 161       unlockcachebuffer(cb);
 162     }
 163   }
 164
 165   return(errorcode);
 166 }
 167
 168
 169
 170 static LONG addnewnodelevel(BLCK noderoot, UWORD nodesize) {
 171   struct CacheBuffer *cb;
 172   LONG errorcode;
 173
 174   /* Adds a new level to the Node tree. */
 175
 176   _XDEBUG((DEBUG_NODES,"addnewnodelevel: Entry\n"));
 177
 178   if((errorcode=readcachebuffercheck(&cb, noderoot, NODECONTAINER_ID))==0) {
 179     struct CacheBuffer *newcb;
 180
 181     lockcachebuffer(cb);   /* Locking cb, because allocadminspace & storecachebuffer below may destroy it otherwise */
 182
 183     if((errorcode=allocadminspace(&newcb))==0) {
 184       struct fsNodeContainer *nc=cb->data;
 185       struct fsNodeContainer *newnc=newcb->data;
 186       BLCK newblock=newcb->blckno;
 187
 188       /* The newly allocated block will become a copy of the current root. */
 189
 190       newnc->bheader.id=NODECONTAINER_ID;
 191       newnc->bheader.be_ownblock=L2BE(newcb->blckno);
 192       newnc->be_nodenumber=nc->be_nodenumber;   // Be->Be copy!
 193       newnc->be_nodes=nc->be_nodes; // Be->Be copy!
 194       CopyMemQuick(nc->be_node, newnc->be_node, globals->bytes_block-sizeof(struct fsNodeContainer));
 195
 196       if((errorcode=storecachebuffer(newcb))==0) {
 197
 198         /* The current root will now be transformed into a new root. */
 199
 200         preparecachebuffer(cb);
 201
 202         if(BE2L(nc->be_nodes)==1) {
 203           nc->be_nodes=L2BE((globals->bytes_block-sizeof(struct fsNodeContainer))/nodesize);
 204         }
 205         else {
 206           nc->be_nodes=L2BE(BE2L(nc->be_nodes)*globals->node_containers);
 207         }
 208
 209         nc->be_node[0]=L2BE((newblock<<globals->shifts_block32)+1);  /* Tree is full from that point! */
 210
 211         ClearMemQuick(&nc->be_node[1], globals->bytes_block-sizeof(struct fsNodeContainer)-4);
 212
 213         errorcode=storecachebuffer(cb);
 214       }
 215     }
 216
 217     unlockcachebuffer(cb);
 218   }
 219
 220   _XDEBUG((DEBUG_NODES,"addnewnodelevel: Exiting with errorcode %ld\n",errorcode));
 221
 222   return(errorcode);
 223 }
 224
 225
 226
 227 LONG deletenode(BLCK noderoot, struct CacheBuffer *cb, struct fsNode *n, UWORD nodesize) {
 228   struct fsNodeContainer *nc=cb->data;
 229   UWORD nodecount=(globals->bytes_block-sizeof(struct fsNodeContainer))/nodesize;
 230   WORD i=nodecount;
 231   WORD empty=0;
 232   LONG errorcode;
 233
 234   preparecachebuffer(cb);
 235
 236   n->be_data=0;
 237
 238   n=(struct fsNode *)nc->be_node;
 239
 240   while(i-->0) {
 241     if(n->be_data==0) {
 242       empty++;
 243     }
 244     n=(struct fsNode *)((UBYTE *)n+nodesize);
 245   }
 246
 247   if((errorcode=storecachebuffer(cb))==0) {
 248     if(empty==1) {      /* NodeContainer was completely full before, so we need to mark it empty now. */
 249       errorcode=markparentempty(noderoot, cb);
 250     }
 251     else if(empty==nodecount) {         /* NodeContainer is now completely empty!  Free it! */
 252       errorcode=freecontainer(noderoot, cb);
 253     }
 254   }
 255
 256   return(errorcode);
 257 }
 258
 259
 260
 261 static LONG createnodecontainer(ULONG nodenumber, ULONG nodes, BLCK *returned_block) {
 262   struct CacheBuffer *cb;
 263   LONG errorcode;
 264
 265   _XDEBUG((DEBUG_NODES,"createnodecontainer: nodenumber = %ld, nodes = %ld\n",nodenumber,nodes));
 266
 267   if((errorcode=allocadminspace(&cb))==0) {
 268     struct fsNodeContainer *nc=cb->data;
 269
 270     nc->bheader.id=NODECONTAINER_ID;
 271     nc->bheader.be_ownblock=L2BE(cb->blckno);
 272
 273     nc->be_nodenumber=L2BE(nodenumber);
 274     nc->be_nodes=L2BE(nodes);
 275
 276     errorcode=storecachebuffer(cb);
 277     *returned_block=cb->blckno;
 278   }
 279
 280   _XDEBUG((DEBUG_NODES,"createnodecontainer: Exiting with errorcode %ld\n",errorcode));
 281
 282   return(errorcode);
 283 }
 284
 285
 286
 287 LONG createnode(BLCK noderoot, UWORD nodesize, struct CacheBuffer **returned_cb, struct fsNode **returned_node, NODE *returned_nodeno) {
 288   struct CacheBuffer *cb;
 289   UWORD nodecount=(globals->bytes_block-sizeof(struct fsNodeContainer))/nodesize;
 290   BLCK nodeindex=noderoot;
 291   LONG errorcode;
 292
 293   /* This function creates a new fsNode structure in a fsNodeContainer.  If needed
 294      it will create a new fsNodeContainers and a new fsNodeIndexContainer.  newoperation()
 295      should be called prior to calling this function. */
 296
 297 //  _XDEBUG((DEBUG_NODES,"createnode: Entry\n"));
 298
 299   while((errorcode=readcachebuffercheck(&cb, nodeindex, NODECONTAINER_ID))==0) {
 300     struct fsNodeContainer *nc=cb->data;
 301
 302     if(BE2L(nc->be_nodes)==1) {    // Is it a leaf-container?
 303       struct fsNode *n;
 304       WORD i=nodecount;
 305
 306       n=(struct fsNode *)nc->be_node;
 307
 308       while(i-->0) {
 309         if(n->be_data==0) {
 310           break;
 311         }
 312         n=(struct fsNode *)((UBYTE *)n+nodesize);
 313       }
 314
 315       if(i>=0) {
 316         /* Found an empty fsNode structure! */
 317
 318         preparecachebuffer(cb);
 319
 320         *returned_cb=cb;
 321         *returned_node=n;
 322         *returned_nodeno=BE2L(nc->be_nodenumber)+((UBYTE *)n-(UBYTE *)nc->be_node)/nodesize;
 323
 324         _XDEBUG((DEBUG_NODES,"createnode: Created Node %ld\n",*returned_nodeno));
 325
 326         /* Below we continue to look through the NodeContainer block.  We skip the entry
 327            we found to be unused, and see if there are any more unused entries.  If we
 328            do not find any more unused entries then this container is now full. */
 329
 330         n=(struct fsNode *)((UBYTE *)n+nodesize);
 331
 332         while(i-->0) {
 333           if(n->be_data==0) {
 334             break;
 335           }
 336           n=(struct fsNode *)((UBYTE *)n+nodesize);
 337         }
 338
 339         if(i<0) {
 340           /* No more empty fsNode structures in this block.  Mark parent full. */
 341           if((errorcode=markparentfull(noderoot, cb))!=0) {
 342             dumpcachebuffer(cb);
 343           }
 344         }
 345
 346         break;
 347       }
 348       else {
 349         /* What happened now is that we found a leaf-container which was
 350            completely filled.  In practice this should only happen when there
 351            is only a single NodeContainer (only this container), or when there
 352            was an error in one of the full-bits in a higher level container. */
 353
 354         if(noderoot!=nodeindex) {
 355           /*** Hmmm... it looks like there was a damaged full-bit or something.
 356                In this case we'd probably better call markcontainerfull. */
 357
 358           // errorcode=markcontainerfull(nc->parent,nc->nodenumber);
 359
 360           req("Couldn't find empty Node in NodeContainer at block %ld\n"\
 361               "while NodeIndexContainer indicated there should be one.\n",
 362               "Ok", cb->blckno);
 363
 364           errorcode=ERROR_DISK_FULL;
 365           break;
 366         }
 367         else {
 368           /* Container is completely filled. */
 369
 370           if((errorcode=addnewnodelevel(noderoot, nodesize))!=0) {
 371             break;
 372           }
 373
 374           nodeindex=noderoot;
 375         }
 376       }
 377     }
 378     else {   // This isn't a leaf container
 379       BLCKn *p=nc->be_node;
 380       WORD i=globals->node_containers;
 381
 382       /* We've read a normal container */
 383
 384       while(i-->0) {
 385         if(*p!=0 && (BE2L(*p) & 0x00000001)==0) {
 386           break;
 387         }
 388         p++;
 389       }
 390
 391       if(i>=0) {
 392         /* Found a not completely filled Container */
 393
 394         nodeindex=BE2L(*p)>>globals->shifts_block32;
 395       }
 396       else {
 397         /* Everything in the NodeIndexContainer was completely filled.  There possibly
 398            are some unused pointers in this block however.  */
 399
 400         _XDEBUG((DEBUG_NODES,"createnode: NodeContainer at block %ld has no empty Nodes\n",cb->blckno));
 401
 402         p=nc->be_node;
 403         i=globals->node_containers;
 404
 405         while(i-->0) {
 406           if(*p==0) {
 407             break;
 408           }
 409           p++;
 410         }
 411
 412         if(i>=0) {
 413           BLCK newblock;
 414           ULONG nodes;
 415
 416           /* Found an unused Container pointer */
 417
 418           preparecachebuffer(cb);
 419
 420           if(BE2L(nc->be_nodes)==(globals->bytes_block-sizeof(struct fsNodeContainer))/nodesize) {
 421             nodes=1;
 422           }
 423           else {
 424             nodes=BE2L(nc->be_nodes)/globals->node_containers;
 425           }
 426
 427           if((errorcode=createnodecontainer(BE2L(nc->be_nodenumber)+(p-nc->be_node)*BE2L(nc->be_nodes), nodes, &newblock))!=0) {
 428             dumpcachebuffer(cb);
 429             break;
 430           }
 431
 432           *p=L2BE(newblock<<globals->shifts_block32);
 433
 434           if((errorcode=storecachebuffer(cb))!=0) {
 435             break;
 436           }
 437         }
 438         else {
 439           /* Container is completely filled.  This must be the top-level NodeIndex container
 440              as otherwise the full-bit would have been wrong! */
 441
 442           if((errorcode=addnewnodelevel(noderoot, nodesize))!=0) {
 443             break;
 444           }
 445
 446           nodeindex=noderoot;
 447         }
 448       }
 449     }
 450   }
 451
 452 //  _XDEBUG((DEBUG_NODES,"createnode: Exiting with errorcode %ld\n",errorcode));
 453
 454   return(errorcode);
 455 }
 456
 457
 458
 459 LONG findnode(BLCK nodeindex,UWORD nodesize,NODE nodeno,struct CacheBuffer **returned_cb,struct fsNode **returned_node) {
 460   struct CacheBuffer *cb;
 461   LONG errorcode;
 462
 463   _XDEBUG((DEBUG_NODES,"findnode: Entry -- looking for nodeno %ld\n",nodeno));
 464
 465   /* Finds a specific node by number.  It returns the cachebuffer which contains the fsNode
 466      structure and a pointer to the fsNode structure directly. */
 467
 468   while((errorcode=readcachebuffercheck(&cb,nodeindex,NODECONTAINER_ID))==0) {
 469     struct fsNodeContainer *nc=cb->data;
 470
 471     _XDEBUG((DDEBUG_NODES,"findnode: Read NodeContainer at block %ld with nodenumber = %ld, nodes = %ld\n",nodeindex,BE2L(nc->be_nodenumber),BE2L(nc->be_nodes)));
 472
 473     if(BE2L(nc->be_nodes)==1) {
 474       /* We've descended the tree to a leaf NodeContainer */
 475
 476       *returned_cb=cb;
 477       *returned_node=(struct fsNode *)((UBYTE *)nc->be_node+nodesize*(nodeno-BE2L(nc->be_nodenumber)));
 478
 479       return(0);
 480     }
 481     else {
 482       UWORD containerentry=(nodeno-BE2L(nc->be_nodenumber))/BE2L(nc->be_nodes);
 483
 484       nodeindex=BE2L(nc->be_node[containerentry])>>globals->shifts_block32;
 485     }
 486   }
 487
 488   _XDEBUG((DEBUG_NODES,"findnode: Exiting with errorcode %ld\n",errorcode));
 489
 490   return(errorcode);
 491 }
 492