sys/src/cmd/hjfs/fs1.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <thread.h>
   4 #include <fcall.h>
   5 #include "dat.h"
   6 #include "fns.h"
   7
   8 int
   9 chref(Fs *fs, uvlong r, int stat)
  10 {
  11         uvlong i;
  12         int j;
  13         ulong rc;
  14         Buf *c;
  15
  16         i = fs->fstart + r / REFPERBLK;
  17         j = r % REFPERBLK;
  18         c = getbuf(fs->d, i, TREF, 0);
  19         if(c == nil)
  20                 return -1;
  21         if(stat < 0 && c->refs[j] < -stat)
  22                 c->refs[j] = 0;
  23         else
  24                 c->refs[j] += stat;
  25         rc = c->refs[j];
  26         if(stat != 0)
  27                 c->op |= BDELWRI;
  28         putbuf(c);
  29         return rc;
  30 }
  31
  32 static int
  33 qidcmp(Qid *a, Qid *b)
  34 {
  35         if(a->type != b->type)
  36                 return 1;
  37         if(a->path != b->path){
  38                 /* special case for dump, this is ok */
  39                 if(a->path==ROOTQID && b->path==DUMPROOTQID)
  40                         return 0;
  41                 return 1;
  42         }
  43         return 0;
  44 }
  45
  46 Dentry*
  47 getdent(FLoc *l, Buf *b)
  48 {
  49         Dentry *d;
  50
  51         d = &b->de[l->deind];
  52         if((d->mode & (DGONE | DALLOC)) == 0){
  53                 dprint("getdent: file gone, d=%llux, l=%llud/%d %llux, callerpc %#p\n",
  54                         d->path, l->blk, l->deind, l->path, getcallerpc(&l));
  55                 werrstr("phase error -- directory entry for nonexistent file");
  56                 return nil;
  57         }
  58         if(qidcmp(d, l) != 0){
  59                 dprint("getdent: wrong qid d=%llux != l=%llud/%d %llux, callerpc %#p\n",
  60                         d->path, l->blk, l->deind, l->path, getcallerpc(&l));
  61                 werrstr("phase error -- qid mismatch");
  62                 return nil;
  63         }
  64         return d;
  65 }
  66
  67 int
  68 getfree(Fs *fs, uvlong *r)
  69 {
  70         Dev *d;
  71         Buf *b;
  72         uvlong i, l, e;
  73         int j, have;
  74
  75         d = fs->d;
  76         while(nbrecv(fs->freelist, &l) > 0){
  77                 i = fs->fstart + l / REFPERBLK;
  78                 j = l % REFPERBLK;
  79                 b = getbuf(d, i, TREF, 0);
  80                 if(b != nil){
  81                         if(b->refs[j] == 0){
  82                                 b->refs[j] = 1;
  83                                 *r = l;
  84                                 goto found;
  85                         }
  86                         putbuf(b);
  87                 }
  88         }
  89
  90         b = getbuf(d, SUPERBLK, TSUPERBLOCK, 0);
  91         if(b == nil) {
  92                 werrstr("could not find superblock");
  93                 return -1;
  94         }
  95         e = b->sb.fend;
  96         putbuf(b);
  97
  98         have = 0;
  99         for(l = 0, i = fs->fstart; i < e; i++){
 100                 b = getbuf(d, i, TREF, 0);
 101                 if(b == nil){
 102                         l += REFPERBLK;
 103                         continue;
 104                 }
 105                 for(j = 0; j < REFPERBLK; j++, l++)
 106                         if(b->refs[j] == 0){
 107                                 if(!have){
 108                                         b->refs[j] = 1;
 109                                         *r = l;
 110                                         have = 1;
 111                                 }else if(nbsend(fs->freelist, &l) <= 0)
 112                                         goto found;
 113                         }
 114                 if(have)
 115                         goto found;
 116                 putbuf(b);
 117         }
 118         werrstr("disk full");
 119         return -1;
 120 found:
 121         b->op |= BDELWRI;
 122         putbuf(b);
 123         return 1;
 124 }
 125
 126 int
 127 putfree(Fs *fs, uvlong r)
 128 {
 129         int rc;
 130
 131         rc = chref(fs, r, -1);
 132         if(rc < 0)
 133                 return -1;
 134         if(rc == 0)
 135                 nbsend(fs->freelist, &r);
 136         return 1;
 137 }
 138
 139 static void
 140 createroot(Fs *fs)
 141 {
 142         uvlong r;
 143         Buf *c;
 144         Dentry *d;
 145
 146         if(getfree(fs, &r) < 0)
 147                 sysfatal("ream: getfree: %r");
 148         c = getbuf(fs->d, r, TDENTRY, 1);
 149         if(c == nil)
 150         error:
 151                 sysfatal("ream: getbuf: %r");
 152         memset(c->de, 0, sizeof(c->de));
 153         d = &c->de[0];
 154         strcpy(d->name, "/");
 155         d->mode = DALLOC | 0775;
 156         d->path = ROOTQID;
 157         d->type = QTDIR;
 158         d->uid = -1;
 159         d->muid = -1;
 160         d->gid = -1;
 161         d->mtime = time(0);
 162         d->atime = d->mtime;
 163         d++;
 164         strcpy(d->name, "/");
 165         d->mode = DALLOC | 0775;
 166         d->path = ROOTQID;
 167         d->type = QTDIR;
 168         d->uid = -1;
 169         d->muid = -1;
 170         d->gid = -1;
 171         d->mtime = time(0);
 172         d->atime = d->mtime;
 173         c->op |= BWRIM;
 174         putbuf(c);
 175         c = getbuf(fs->d, SUPERBLK, TSUPERBLOCK, 0);
 176         if(c == nil)
 177                 goto error;
 178         fs->root = r;
 179         c->sb.root = r;
 180         c->op |= BDELWRI;
 181         putbuf(c);
 182 }
 183
 184 void
 185 writeusers(Fs *fs)
 186 {
 187         Chan *ch;
 188
 189         ch = chanattach(fs, 0);
 190         if(ch == nil)
 191                 goto error;
 192         ch->uid = -1;
 193         chancreat(ch, "adm", DMDIR | 0775, OREAD);
 194         chanclunk(ch);
 195         ch = chanattach(fs, 0);
 196         if(ch == nil)
 197                 goto error;
 198         ch->uid = -1;
 199         if(chanwalk(ch, "adm") <= 0)
 200                 goto error;
 201         if(chanwalk(ch, "users") > 0){
 202                 if(chanopen(ch, OWRITE|OTRUNC) <= 0)
 203                         goto error;
 204         }else if(chancreat(ch, "users", 0664, OWRITE) <= 0)
 205                         goto error;
 206         if(userssave(fs, ch) < 0){
 207                 chanremove(ch);
 208                 ch = nil;
 209                 goto error;
 210         }
 211         chanclunk(ch);
 212         return;
 213 error:
 214         if(ch != nil)
 215                 chanclunk(ch);
 216         dprint("writeusers: %r\n");
 217 }
 218
 219 void
 220 readusers(Fs *fs)
 221 {
 222         Chan *ch;
 223
 224         ch = chanattach(fs, 0);
 225         if(ch == nil)
 226                 goto err;
 227         ch->uid = -1;
 228         if(chanwalk(ch, "adm") <= 0)
 229                 goto err;
 230         if(chanwalk(ch, "users") <= 0)
 231                 goto err;
 232         if(chanopen(ch, OREAD) < 0)
 233                 goto err;
 234         if(usersload(fs, ch) < 0)
 235                 goto err;
 236         chanclunk(ch);
 237         return;
 238 err:
 239         if(ch != nil)
 240                 chanclunk(ch);
 241         dprint("readusers: %r\nhjfs: using default user db\n");
 242 }
 243
 244 void
 245 ream(Fs *fs)
 246 {
 247         Dev *d;
 248         Buf *b, *c;
 249         uvlong i, firsti, lasti;
 250         int j, je;
 251
 252         d = fs->d;
 253         dprint("reaming %s\n", d->name);
 254         b = getbuf(d, SUPERBLK, TSUPERBLOCK, 1);
 255         if(b == nil)
 256         err:
 257                 sysfatal("ream: getbuf: %r");
 258         memset(&b->sb, 0, sizeof(b->sb));
 259         b->sb.magic = SUPERMAGIC;
 260         b->sb.size = d->size;
 261         b->sb.fstart = SUPERBLK + 1;
 262         fs->fstart = b->sb.fstart;
 263         b->sb.fend = b->sb.fstart + HOWMANY(b->sb.size * REFSIZ);
 264         b->sb.qidpath = DUMPROOTQID + 1;
 265         firsti = b->sb.fstart + SUPERBLK / REFPERBLK;
 266         lasti = b->sb.fstart + b->sb.fend / REFPERBLK;
 267         for(i = b->sb.fstart; i < b->sb.fend; i++){
 268                 c = getbuf(d, i, TREF, 1);
 269                 if(c == nil)
 270                         goto err;
 271                 memset(c->refs, 0, sizeof(c->refs));
 272                 if(i >= firsti && i <= lasti){
 273                         j = 0;
 274                         je = REFPERBLK;
 275                         if(i == firsti)
 276                                 j = SUPERBLK % REFPERBLK;
 277                         if(i == lasti)
 278                                 je = b->sb.fend % REFPERBLK;
 279                         for(; j < je; j++)
 280                                 c->refs[j] = 1;
 281                 }
 282                 if(i == b->sb.fend - 1){
 283                         j = b->sb.size % REFPERBLK;
 284                         if(j != 0)
 285                                 for(; j < REFPERBLK; j++)
 286                                         c->refs[j] = -1;
 287                 }
 288                 c->op |= BWRIM;
 289                 putbuf(c);
 290         }
 291         b->op |= BDELWRI;
 292         putbuf(b);
 293         createroot(fs);
 294         sync(1);
 295         dprint("ream successful\n");
 296 }
 297
 298 Fs *
 299 initfs(Dev *d, int doream, int flags)
 300 {
 301         Fs *fs;
 302         Buf *b;
 303         FLoc f;
 304
 305         fs = emalloc(sizeof(*fs));
 306         fs->d = d;
 307         if(doream)
 308                 ream(fs);
 309         b = getbuf(d, SUPERBLK, TSUPERBLOCK, 0);
 310         if(b == nil || b->sb.magic != SUPERMAGIC)
 311                 goto error;
 312         fs->root = b->sb.root;
 313         fs->fstart = b->sb.fstart;
 314         fs->freelist = chancreate(sizeof(uvlong), FREELISTLEN);
 315         f.blk = fs->root;
 316         f.deind = 0;
 317         f.path = ROOTQID;
 318         f.vers = 0;
 319         f.type = QTDIR;
 320         fs->rootloc = getloc(fs, f, nil);
 321         f.deind++;
 322         f.path = DUMPROOTQID;
 323         fs->dumprootloc = getloc(fs, f, nil);
 324         putbuf(b);
 325         fs->flags = flags;
 326         if(doream)
 327                 writeusers(fs);
 328         readusers(fs);
 329         dprint("fs is %s\n", d->name);
 330         return fs;
 331
 332 error:
 333         if(b != nil)
 334                 putbuf(b);
 335         free(fs);
 336         return nil;
 337 }
 338
 339 void
 340 chbegin(Chan *ch)
 341 {
 342         if((ch->flags & CHFNOLOCK) == 0)
 343                 rlock(ch->fs);
 344 }
 345
 346 void
 347 chend(Chan *ch)
 348 {
 349         if((ch->flags & CHFNOLOCK) == 0)
 350                 runlock(ch->fs);
 351 }
 352
 353 int
 354 newqid(Fs *fs, uvlong *q)
 355 {
 356         Buf *b;
 357
 358         b = getbuf(fs->d, SUPERBLK, TSUPERBLOCK, 0);
 359         if(b == nil)
 360                 return -1;
 361         *q = b->sb.qidpath++;
 362         b->op |= BDELWRI;
 363         putbuf(b);
 364         return 1;
 365 }
 366
 367 Loc *
 368 getloc(Fs *fs, FLoc f, Loc *next)
 369 {
 370         Loc *l;
 371
 372         qlock(&fs->loctree);
 373         if(next != nil && next->child != nil){
 374                 l = next->child;
 375                 do{
 376                         if(l->blk == f.blk && l->deind == f.deind){
 377                                 l->ref++;
 378                                 qunlock(&fs->loctree);
 379                                 return l;
 380                         }
 381                         l = l->cnext;
 382                 }while(l != next->child);
 383         }
 384         l = emalloc(sizeof(*l));
 385         l->ref = 1;
 386         l->FLoc = f;
 387         l->next = next;
 388         if(fs->rootloc != nil){
 389                 l->gnext = fs->rootloc;
 390                 l->gprev = l->gnext->gprev;
 391                 l->gnext->gprev = l;
 392                 l->gprev->gnext = l;
 393         }else
 394                 l->gnext = l->gprev = l;
 395         l->cprev = l->cnext = l;
 396         if(next != nil){
 397                 if(next->child == nil)
 398                         next->child = l;
 399                 else{
 400                         l->cnext = next->child;
 401                         l->cprev = next->child->cprev;
 402                         l->cnext->cprev = l;
 403                         l->cprev->cnext = l;
 404                 }
 405         }
 406         qunlock(&fs->loctree);
 407         return l;
 408 }
 409
 410 int
 411 haveloc(Fs *fs, uvlong blk, int deind, Loc *next)
 412 {
 413         Loc *l;
 414
 415         qlock(&fs->loctree);
 416         l = next->child;
 417         if(l != nil) do{
 418                 if(l->blk == blk && l->deind == deind){
 419                         qunlock(&fs->loctree);
 420                         return 1;
 421                 }
 422                 l = l->cnext;
 423         } while(l != next->child);
 424         qunlock(&fs->loctree);
 425         return 0;
 426 }
 427
 428 Loc *
 429 cloneloc(Fs *fs, Loc *l)
 430 {
 431         Loc *m;
 432
 433         qlock(&fs->loctree);
 434         for(m = l; m != nil; m = m->next)
 435                 m->ref++;
 436         qunlock(&fs->loctree);
 437         return l;
 438 }
 439
 440 void
 441 putloc(Fs *fs, Loc *l, int loop)
 442 {
 443         Loc *m;
 444         Buf *b;
 445
 446         qlock(&fs->loctree);
 447         if(!loop && --l->ref <= 0)
 448                 goto freeit;
 449         while(loop && l != nil && l->ref <= 1){
 450 freeit:
 451                 if((l->flags & LGONE) != 0){
 452                         /*
 453                          * safe to unlock here, the file is gone and
 454                          * we're the last reference.
 455                          */
 456                         qunlock(&fs->loctree);
 457                         b = getbuf(fs->d, l->blk, TDENTRY, 0);
 458                         if(b != nil){
 459                                 delete(fs, l, b);
 460                                 putbuf(b);
 461                         }
 462                         qlock(&fs->loctree);
 463                 }
 464                 l->cnext->cprev = l->cprev;
 465                 l->cprev->cnext = l->cnext;
 466                 l->gnext->gprev = l->gprev;
 467                 l->gprev->gnext = l->gnext;
 468                 if(l->next != nil && l->next->child == l){
 469                         if(l->cnext == l)
 470                                 l->next->child = nil;
 471                         else
 472                                 l->next->child = l->cnext;
 473                 }
 474                 m = l->next;
 475                 free(l);
 476                 l = m;
 477         }
 478         for(; loop && l != nil; l = l->next)
 479                 --l->ref;
 480         qunlock(&fs->loctree);
 481 }
 482
 483 static int
 484 dumpblk(Fs *fs, FLoc *, uvlong *l)
 485 {
 486         uvlong n;
 487         int i;
 488         Buf *b, *c;
 489         Dentry *d;
 490
 491         b = getbuf(fs->d, *l, TDONTCARE, 0);
 492         if(b == nil)
 493                 return -1;
 494         if(getfree(fs, &n) < 0){
 495         berr:
 496                 putbuf(b);
 497                 return -1;
 498         }
 499         c = getbuf(fs->d, n, b->type, 1);
 500         if(c == nil){
 501                 putfree(fs, n);
 502                 goto berr;
 503         }
 504         switch(b->type){
 505         case TINDIR:
 506                 memcpy(c->offs, b->offs, sizeof(b->offs));
 507                 for(i = 0; i < OFFPERBLK; i++)
 508                         if(b->offs[i] != 0)
 509                                 chref(fs, b->offs[i], 1);
 510                 break;
 511         case TRAW:
 512                 memcpy(c->data, b->data, sizeof(b->data));
 513                 break;
 514         case TDENTRY:
 515                 memcpy(c->de, b->de, sizeof(b->de));
 516                 for(d = b->de; d < &b->de[DEPERBLK]; d++){
 517                         if((d->mode & DALLOC) == 0)
 518                                 continue;
 519                         if((d->type & QTTMP) != 0)
 520                                 continue;
 521                         for(i = 0; i < NDIRECT; i++)
 522                                 if(d->db[i] != 0)
 523                                         chref(fs, d->db[i], 1);
 524                         for(i = 0; i < NINDIRECT; i++)
 525                                 if(d->ib[i] != 0)
 526                                         chref(fs, d->ib[i], 1);
 527                 }
 528                 break;
 529         default:
 530                 werrstr("dumpblk -- unknown type %d", b->type);
 531                 putfree(fs, n);
 532                 putbuf(c);
 533                 putbuf(b);
 534                 return -1;
 535         }
 536         c->op |= BDELWRI;
 537         putbuf(c);
 538         putbuf(b);
 539         putfree(fs, *l);
 540         *l = n;
 541         return 0;
 542 }
 543
 544 /*
 545  * getblk returns the address of a block in a file
 546  * given its relative address blk
 547  * the address are returned in *r
 548  * mode has to be one of:
 549  * - GBREAD: this block will only be read
 550  * - GBWRITE: this block will be written, but don't create it
 551  *            if it doesn't exist
 552  * - GBCREATE: this block will be written, create it if necessary
 553  * - GBOVERWR: like GBCREATE, but return an empty block if a dump
 554  *             would be necessary
 555  * return value is 1 if the block existed, -1 on error
 556  * a return value of 0 means the block did not exist
 557  * this is only an error in case of GBREAD and GBWRITE
 558  */
 559
 560 int
 561 getblk(Fs *fs, FLoc *L, Buf *bd, uvlong blk, uvlong *r, int mode)
 562 {
 563         uvlong k, l;
 564         uvlong *loc;
 565         int i, j, rc, prc;
 566         Buf *b;
 567         Dentry *d;
 568
 569         b = bd;
 570         d = getdent(L, b);
 571         if(d == nil){
 572                 dprint("getblk: dirent gone\n");
 573                 return -1;
 574         }
 575         if(blk < NDIRECT){
 576                 loc = &d->db[blk];
 577                 goto found;
 578         }
 579         blk -= NDIRECT;
 580         l = 1;
 581         for(i = 0; i < NINDIRECT; i++){
 582                 l *= OFFPERBLK;
 583                 if(blk < l)
 584                         break;
 585                 blk -= l;
 586         }
 587         if(i == NINDIRECT){
 588                 werrstr("getblk: block offset too large");
 589                 return -1;
 590         }
 591         loc = &d->ib[i];
 592         for(j = 0; j <= i; j++){
 593                 if(*loc == 0){
 594                         if(mode == GBREAD || mode == GBWRITE){
 595                                 if(b != bd)
 596                                         putbuf(b);
 597                                 return 0;
 598                         }
 599                         if(getfree(fs, loc) < 0){
 600                                 if(b != bd)
 601                                         putbuf(b);
 602                                 return -1;
 603                         }
 604                         b->op |= BDELWRI;
 605                         k = *loc;
 606                         if(b != bd)
 607                                 putbuf(b);
 608                         b = getbuf(fs->d, k, TINDIR, 1);
 609                         if(b == nil)
 610                                 return -1;
 611                         memset(b->offs, 0, sizeof(b->offs));
 612                         b->op |= BDELWRI;
 613                 }else{
 614                         if(mode != GBREAD && chref(fs, *loc, 0) > 1){
 615                                 if(dumpblk(fs, L, loc) < 0){
 616                                         if(b != bd)
 617                                                 putbuf(b);
 618                                         return -1;
 619                                 }
 620                                 b->op |= BDELWRI;
 621                         }
 622                         k = *loc;
 623                         if(b != bd)
 624                                 putbuf(b);
 625                         b = getbuf(fs->d, k, TINDIR, 0);
 626                         if(b == nil)
 627                                 return -1;
 628                 }
 629                 l /= OFFPERBLK;
 630                 loc = &b->offs[blk / l];
 631                 blk %= l;
 632         }
 633
 634 found:
 635         rc = 0;
 636         prc = 0;
 637         if(*loc != 0){
 638                 if(mode == GBREAD)
 639                         goto okay;
 640                 if((rc = chref(fs, *loc, 0)) > 1){
 641                         if(mode == GBOVERWR){
 642                                 putfree(fs, *loc);
 643                                 *loc = 0;
 644                                 b->op |= BDELWRI;
 645                                 prc = 1;
 646                                 goto new;
 647                         }
 648                         if(dumpblk(fs, L, loc) < 0){
 649                                 rc = -1;
 650                                 goto end;
 651                         }
 652                         b->op |= BDELWRI;
 653                 }
 654                 if(rc < 0)
 655                         goto end;
 656                 if(rc == 0){
 657                         dprint("getblk: block %lld has refcount 0\n");
 658                         werrstr("phase error -- getblk");
 659                         rc = -1;
 660                         goto end;
 661                 }
 662 okay:
 663                 *r = *loc;
 664                 rc = 1;
 665         }else if(mode == GBCREATE || mode == GBOVERWR){
 666 new:
 667                 rc = getfree(fs, r);
 668                 if(rc > 0){
 669                         *loc = *r;
 670                         b->op |= BDELWRI;
 671                         rc = prc;
 672                 }
 673         }
 674 end:
 675         if(b != bd)
 676                 putbuf(b);
 677         return rc;
 678 }
 679
 680 static void
 681 delindir(Fs *fs, uvlong *l, int n)
 682 {
 683         Buf *b;
 684         int k;
 685
 686         if(*l == 0)
 687                 return;
 688         if(chref(fs, *l, 0) > 1){
 689                 *l = 0;
 690                 return;
 691         }
 692         if(n > 0){
 693                 b = getbuf(fs->d, *l, TINDIR, 0);
 694                 if(b != nil){
 695                         for(k = 0; k < OFFPERBLK; k++)
 696                                 if(b->offs[k] != 0){
 697                                         delindir(fs, &b->offs[k], n-1);
 698                                         b->op |= BDELWRI;
 699                                 }
 700                         putbuf(b);
 701                 }
 702         }
 703         putfree(fs, *l);
 704         *l = 0;
 705 }
 706
 707 static int
 708 zeroes(int *a, int i)
 709 {
 710         while(i--)
 711                 if(*a++ != 0)
 712                         return 0;
 713         return 1;
 714 }
 715
 716 static void
 717 delindirpart(Fs *fs, FLoc *p, uvlong *l, int *a, int n)
 718 {
 719         Buf *b;
 720         int k;
 721
 722         if(*l == 0)
 723                 return;
 724         if(n == 0){
 725                 putfree(fs, *l);
 726                 *l = 0;
 727                 return;
 728         }
 729         if(zeroes(a, n)){
 730                 delindir(fs, l, n);
 731                 return;
 732         }
 733         if(chref(fs, *l, 0) > 1)
 734                 dumpblk(fs, p, l);
 735         b = getbuf(fs->d, *l, TINDIR, 0);
 736         if(b == nil)
 737                 return;
 738         delindirpart(fs, p, &b->offs[*a], a + 1, n - 1);
 739         for(k = a[0] + 1; k < OFFPERBLK; k++)
 740                 if(b->offs[k] != 0)
 741                         delindir(fs, &b->offs[k], n - 1);
 742         b->op |= BDELWRI;
 743         putbuf(b);
 744 }
 745
 746 /*
 747  * call willmodify() before and modified()
 748  * after calling this function
 749  */
 750 int
 751 trunc(Fs *fs, FLoc *ll, Buf *bd, uvlong size)
 752 {
 753         uvlong blk;
 754         Dentry *d;
 755         int a[NINDIRECT];
 756         uvlong l;
 757         int i, j;
 758
 759         d = getdent(ll, bd);
 760         if(d == nil)
 761                 return -1;
 762         if(size >= d->size)
 763                 goto done;
 764         blk = HOWMANY(size);
 765         while(blk < NDIRECT){
 766                 if(d->db[blk] != 0){
 767                         putfree(fs, d->db[blk]);
 768                         d->db[blk] = 0;
 769                         bd->op |= BDELWRI;
 770                 }
 771                 blk++;
 772         }
 773         blk -= NDIRECT;
 774         l = 1;
 775         for(i = 0; i < NINDIRECT; i++){
 776                 l *= OFFPERBLK;
 777                 if(blk < l)
 778                         break;
 779                 blk -= l;
 780         }
 781         if(blk >= l){
 782                 werrstr("phase error -- truncate");
 783                 return -1;
 784         }
 785         if(blk == 0)
 786                 goto rest;
 787         if(d->ib[i] == 0){
 788                 i++;
 789                 goto rest;
 790         }
 791         for(j = 0; j <= i; j++){
 792                 l /= OFFPERBLK;
 793                 a[j] = blk / l;
 794                 blk %= l;
 795         }
 796         delindirpart(fs, ll, &d->ib[i], a, i + 1);
 797         i++;
 798 rest:
 799         for(; i < NINDIRECT; i++)
 800                 delindir(fs, &d->ib[i], i + 1);
 801 done:
 802         d->size = size;
 803         bd->op |= BDELWRI;
 804         return 1;
 805 }
 806
 807 /*
 808  * find a direntry
 809  * name == nil allows any entry to match
 810  * rl == nil allowed
 811  * return value 1 on success, 0 on Enoent,
 812  * -1 on other errors
 813  */
 814 int
 815 findentry(Fs *fs, FLoc *l, Buf *b, char *name, FLoc *rl, int dump)
 816 {
 817         uvlong i;
 818         int j;
 819         Dentry *d;
 820         uvlong r;
 821         Buf *c;
 822
 823         d = getdent(l, b);
 824         if(d == nil)
 825                 return -1;
 826         for(i = 0; i < d->size; i++){
 827                 if(getblk(fs, l, b, i, &r, GBREAD) <= 0)
 828                         continue;
 829                 c = getbuf(fs->d, r, TDENTRY, 0);
 830                 if(c == nil)
 831                         continue;
 832                 for(j = 0; j < DEPERBLK; j++)
 833                         if((c->de[j].mode & DALLOC) != 0 &&
 834                            (name == nil || strcmp(c->de[j].name, name) == 0)){
 835                                 if(dump && (c->de[j].type & QTTMP) != 0)
 836                                         continue;
 837                                 if(rl != nil){
 838                                         rl->Qid = c->de[j].Qid;
 839                                         rl->blk = r;
 840                                         rl->deind = j;
 841                                 }
 842                                 putbuf(c);
 843                                 return 1;
 844                         }
 845                 putbuf(c);
 846         }
 847         werrstr(Enoent);
 848         return 0;
 849 }
 850
 851 void
 852 modified(Chan *ch, Dentry *d)
 853 {
 854         d->mtime = time(0);
 855         d->atime = d->mtime;
 856         d->muid = ch->uid;
 857         ch->loc->vers = ++d->vers;
 858 }
 859
 860 typedef struct Del Del;
 861
 862 struct Del {
 863         FLoc;
 864         Del *next, *prev;
 865 };
 866
 867 static int
 868 deltraverse(Fs *fs, Del *p, Buf *b, Del **last)
 869 {
 870         Buf *c;
 871         int frb;
 872         Dentry *d;
 873         uvlong i, s, r;
 874         int j, rc;
 875         Del *dd;
 876
 877         frb = b == nil;
 878         if(frb){
 879                 b = getbuf(fs->d, p->blk, TDENTRY, 0);
 880                 if(b == nil)
 881                         return -1;
 882         }
 883         d = getdent(p, b);
 884         if(d == nil){
 885                 if(frb)
 886                         putbuf(b);
 887                 return -1;
 888         }
 889         s = d->size;
 890         for(i = 0; i < s; i++){
 891                 rc = getblk(fs, p, b, i, &r, GBREAD);
 892                 if(rc <= 0)
 893                         continue;
 894                 c = getbuf(fs->d, r, TDENTRY, 0);
 895                 if(c == nil)
 896                         continue;
 897                 for(j = 0; j < DEPERBLK; j++){
 898                         d = &c->de[j];
 899                         if((d->mode & (DALLOC|DGONE)) != 0){
 900                                 if((d->type & QTDIR) == 0){
 901                                         trunc(fs, p, b, 0);
 902                                         memset(d, 0, sizeof(*d));
 903                                         c->op |= BDELWRI;
 904                                 }else{
 905                                         dd = emalloc(sizeof(Del));
 906                                         dd->blk = i;
 907                                         dd->deind = j;
 908                                         dd->Qid = d->Qid;
 909                                         dd->prev = *last;
 910                                         (*last)->next = dd;
 911                                         *last = dd;
 912                                 }
 913                         }
 914                 }
 915                 putbuf(c);
 916         }
 917         if(frb)
 918                 putbuf(b);
 919         return 0;
 920 }
 921
 922 int
 923 delete(Fs *fs, FLoc *l, Buf *b)
 924 {
 925         Dentry *d;
 926         Buf *c;
 927         Del *first, *last, *p, *q;
 928
 929         d = getdent(l, b);
 930         if(d == nil)
 931                 return -1;
 932         if((d->type & QTDIR) == 0){
 933                 trunc(fs, l, b, 0);
 934                 memset(d, 0, sizeof(*d));
 935                 b->op |= BDELWRI;
 936                 return 0;
 937         }
 938         first = last = emalloc(sizeof(Del));
 939         first->FLoc = *l;
 940         for(p = first; p != nil; p = p->next)
 941                 deltraverse(fs, p, p == first ? b : nil, &last);
 942         for(p = last; p != nil; q = p->prev, free(p), p = q){
 943                 if(p == first)
 944                         c = b;
 945                 else
 946                         c = getbuf(fs->d, p->blk, TDENTRY, 0);
 947                 if(c == nil)
 948                         continue;
 949                 d = getdent(p, c);
 950                 if(d != nil){
 951                         trunc(fs, p, c, 0);
 952                         memset(d, 0, sizeof(*d));
 953                         c->op |= BDELWRI;
 954                 }
 955                 if(p != first)
 956                         putbuf(c);
 957         }
 958         return 0;
 959 }
 960
 961 /*
 962  * newentry() looks for a free slot in the directory
 963  * and returns FLoc pointing to the slot. if no free
 964  * slot is available a new block is allocated. if
 965  * dump == 0, then the resulting blk from the FLoc
 966  * *is not* dumped, so to finally allocate the Dentry,
 967  * one has to call willmodify() on res before modyfing it.
 968  */
 969 int
 970 newentry(Fs *fs, Loc *l, Buf *b, char *name, FLoc *res, int dump)
 971 {
 972         Dentry *d, *dd;
 973         uvlong i, si, r;
 974         int j, sj;
 975         Buf *c;
 976
 977         d = getdent(l, b);
 978         if(d == nil)
 979                 return -1;
 980         si = sj = -1;
 981         for(i = 0; i < d->size; i++){
 982                 if(getblk(fs, l, b, i, &r, GBREAD) <= 0)
 983                         continue;
 984                 c = getbuf(fs->d, r, TDENTRY, 0);
 985                 if(c == nil)
 986                         continue;
 987                 for(j = 0; j < DEPERBLK; j++){
 988                         dd = &c->de[j];
 989                         if((dd->mode & DGONE) != 0)
 990                                 continue;
 991                         if((dd->mode & DALLOC) != 0){
 992                                 if(strcmp(dd->name, name) == 0){
 993                                         werrstr(Eexists);
 994                                         putbuf(c);
 995                                         return 0;
 996                                 }
 997                                 continue;
 998                         }
 999                         if(si != -1 || haveloc(fs, r, j, l))
1000                                 continue;
1001                         si = i;
1002                         sj = j;
1003                 }
1004                 putbuf(c);
1005         }
1006         if(si == -1 && i == d->size){
1007                 if(getblk(fs, l, b, i, &r, GBCREATE) >= 0){
1008                         c = getbuf(fs->d, r, TDENTRY, 1);
1009                         if(c != nil){
1010                                 si = i;
1011                                 sj = 0;
1012                                 d->size = i+1;
1013                                 b->op |= BDELWRI;
1014                                 memset(c->de, 0, sizeof(c->de));
1015                                 c->op |= BDELWRI;
1016                                 putbuf(c);
1017                         }
1018                 }
1019         }
1020         if(si == -1 || sj == -1){
1021                 werrstr("phase error -- create");
1022                 return -1;
1023         }
1024         if(getblk(fs, l, b, si, &res->blk, dump != 0 ? GBWRITE : GBREAD) <= 0)
1025                 return -1;
1026         res->deind = sj;
1027         res->Qid = (Qid){0, 0, 0};
1028         return 1;
1029 }