src/vlserver/vlutils.c

   1 /*
   2  * Copyright 2000, International Business Machines Corporation and others.
   3  * All Rights Reserved.
   4  *
   5  * This software has been released under the terms of the IBM Public
   6  * License.  For details, see the LICENSE file in the top-level source
   7  * directory or online at http://www.openafs.org/dl/license10.html
   8  */
   9
  10 #include <afsconfig.h>
  11 #include <afs/param.h>
  12
  13
  14 #include <sys/types.h>
  15 #include <string.h>
  16 #ifdef AFS_NT40_ENV
  17 #include <winsock2.h>
  18 #else
  19 #include <netinet/in.h>
  20 #endif
  21
  22 #include <lock.h>
  23 #include <rx/xdr.h>
  24 #include <ubik.h>
  25 #include "vlserver.h"
  26 #include "vlserver_internal.h"
  27
  28 extern struct vlheader cheader;
  29 struct vlheader xheader;
  30 extern afs_uint32 HostAddress[];
  31 extern int maxnservers;
  32 struct extentaddr extentaddr;
  33 extern struct extentaddr *ex_addr[];
  34 int vldbversion = 0;
  35
  36 static int index_OK(struct ubik_trans *trans, afs_int32 blockindex);
  37
  38 #define ERROR_EXIT(code) {error=(code); goto error_exit;}
  39
  40 /* Hashing algorithm based on the volume id; HASHSIZE must be prime */
  41 afs_int32
  42 IDHash(afs_int32 volumeid)
  43 {
  44     return ((abs(volumeid)) % HASHSIZE);
  45 }
  46
  47
  48 /* Hashing algorithm based on the volume name; name's size is implicit (64 chars) and if changed it should be reflected here. */
  49 afs_int32
  50 NameHash(register char *volumename)
  51 {
  52     register unsigned int hash;
  53     register int i;
  54
  55     hash = 0;
  56     for (i = strlen(volumename), volumename += i - 1; i--; volumename--)
  57         hash = (hash * 63) + (*((unsigned char *)volumename) - 63);
  58     return (hash % HASHSIZE);
  59 }
  60
  61
  62 /* package up seek and write into one procedure for ease of use */
  63 afs_int32
  64 vlwrite(struct ubik_trans *trans, afs_int32 offset, void *buffer,
  65         afs_int32 length)
  66 {
  67     afs_int32 errorcode;
  68
  69     if ((errorcode = ubik_Seek(trans, 0, offset)))
  70         return errorcode;
  71     return (ubik_Write(trans, buffer, length));
  72 }
  73
  74
  75 /* Package up seek and read into one procedure for ease of use */
  76 afs_int32
  77 vlread(struct ubik_trans *trans, afs_int32 offset, char *buffer,
  78        afs_int32 length)
  79 {
  80     afs_int32 errorcode;
  81
  82     if ((errorcode = ubik_Seek(trans, 0, offset)))
  83         return errorcode;
  84     return (ubik_Read(trans, buffer, length));
  85 }
  86
  87
  88 /* take entry and convert to network order and write to disk */
  89 afs_int32
  90 vlentrywrite(struct ubik_trans *trans, afs_int32 offset, void *buffer,
  91              afs_int32 length)
  92 {
  93     struct vlentry oentry;
  94     struct nvlentry nentry, *nep;
  95     char *bufp;
  96     register afs_int32 i;
  97
  98     if (length != sizeof(oentry))
  99         return -1;
 100     if (maxnservers == 13) {
 101         nep = (struct nvlentry *)buffer;
 102         for (i = 0; i < MAXTYPES; i++)
 103             nentry.volumeId[i] = htonl(nep->volumeId[i]);
 104         nentry.flags = htonl(nep->flags);
 105         nentry.LockAfsId = htonl(nep->LockAfsId);
 106         nentry.LockTimestamp = htonl(nep->LockTimestamp);
 107         nentry.cloneId = htonl(nep->cloneId);
 108         for (i = 0; i < MAXTYPES; i++)
 109             nentry.nextIdHash[i] = htonl(nep->nextIdHash[i]);
 110         nentry.nextNameHash = htonl(nep->nextNameHash);
 111         memcpy(nentry.name, nep->name, VL_MAXNAMELEN);
 112         memcpy(nentry.serverNumber, nep->serverNumber, NMAXNSERVERS);
 113         memcpy(nentry.serverPartition, nep->serverPartition, NMAXNSERVERS);
 114         memcpy(nentry.serverFlags, nep->serverFlags, NMAXNSERVERS);
 115         bufp = (char *)&nentry;
 116     } else {
 117         memset(&oentry, 0, sizeof(struct vlentry));
 118         nep = (struct nvlentry *)buffer;
 119         for (i = 0; i < MAXTYPES; i++)
 120             oentry.volumeId[i] = htonl(nep->volumeId[i]);
 121         oentry.flags = htonl(nep->flags);
 122         oentry.LockAfsId = htonl(nep->LockAfsId);
 123         oentry.LockTimestamp = htonl(nep->LockTimestamp);
 124         oentry.cloneId = htonl(nep->cloneId);
 125         for (i = 0; i < MAXTYPES; i++)
 126             oentry.nextIdHash[i] = htonl(nep->nextIdHash[i]);
 127         oentry.nextNameHash = htonl(nep->nextNameHash);
 128         memcpy(oentry.name, nep->name, VL_MAXNAMELEN);
 129         memcpy(oentry.serverNumber, nep->serverNumber, OMAXNSERVERS);
 130         memcpy(oentry.serverPartition, nep->serverPartition, OMAXNSERVERS);
 131         memcpy(oentry.serverFlags, nep->serverFlags, OMAXNSERVERS);
 132         bufp = (char *)&oentry;
 133     }
 134     return vlwrite(trans, offset, bufp, length);
 135 }
 136
 137 /* read entry and convert to host order and write to disk */
 138 afs_int32
 139 vlentryread(struct ubik_trans *trans, afs_int32 offset, char *buffer,
 140             afs_int32 length)
 141 {
 142     struct vlentry *oep, tentry;
 143     struct nvlentry *nep, *nbufp;
 144     char *bufp = (char *)&tentry;
 145     register afs_int32 i;
 146
 147     if (length != sizeof(vlentry))
 148         return -1;
 149     i = vlread(trans, offset, bufp, length);
 150     if (i)
 151         return i;
 152     if (maxnservers == 13) {
 153         nep = (struct nvlentry *)bufp;
 154         nbufp = (struct nvlentry *)buffer;
 155         for (i = 0; i < MAXTYPES; i++)
 156             nbufp->volumeId[i] = ntohl(nep->volumeId[i]);
 157         nbufp->flags = ntohl(nep->flags);
 158         nbufp->LockAfsId = ntohl(nep->LockAfsId);
 159         nbufp->LockTimestamp = ntohl(nep->LockTimestamp);
 160         nbufp->cloneId = ntohl(nep->cloneId);
 161         for (i = 0; i < MAXTYPES; i++)
 162             nbufp->nextIdHash[i] = ntohl(nep->nextIdHash[i]);
 163         nbufp->nextNameHash = ntohl(nep->nextNameHash);
 164         memcpy(nbufp->name, nep->name, VL_MAXNAMELEN);
 165         memcpy(nbufp->serverNumber, nep->serverNumber, NMAXNSERVERS);
 166         memcpy(nbufp->serverPartition, nep->serverPartition, NMAXNSERVERS);
 167         memcpy(nbufp->serverFlags, nep->serverFlags, NMAXNSERVERS);
 168     } else {
 169         oep = (struct vlentry *)bufp;
 170         nbufp = (struct nvlentry *)buffer;
 171         memset(nbufp, 0, sizeof(struct nvlentry));
 172         for (i = 0; i < MAXTYPES; i++)
 173             nbufp->volumeId[i] = ntohl(oep->volumeId[i]);
 174         nbufp->flags = ntohl(oep->flags);
 175         nbufp->LockAfsId = ntohl(oep->LockAfsId);
 176         nbufp->LockTimestamp = ntohl(oep->LockTimestamp);
 177         nbufp->cloneId = ntohl(oep->cloneId);
 178         for (i = 0; i < MAXTYPES; i++)
 179             nbufp->nextIdHash[i] = ntohl(oep->nextIdHash[i]);
 180         nbufp->nextNameHash = ntohl(oep->nextNameHash);
 181         memcpy(nbufp->name, oep->name, VL_MAXNAMELEN);
 182         memcpy(nbufp->serverNumber, oep->serverNumber, NMAXNSERVERS);
 183         memcpy(nbufp->serverPartition, oep->serverPartition, NMAXNSERVERS);
 184         memcpy(nbufp->serverFlags, oep->serverFlags, NMAXNSERVERS);
 185     }
 186     return 0;
 187 }
 188
 189 /* Convenient write of small critical vldb header info to the database. */
 190 int
 191 write_vital_vlheader(register struct ubik_trans *trans)
 192 {
 193     if (vlwrite
 194         (trans, 0, (char *)&cheader.vital_header, sizeof(vital_vlheader)))
 195         return VL_IO;
 196     return 0;
 197 }
 198
 199
 200 int extent_mod = 0;
 201
 202 /* This routine reads in the extent blocks for multi-homed servers.
 203  * There used to be an initialization bug that would cause the contaddrs
 204  * pointers in the first extent block to be bad. Here we will check the
 205  * pointers and zero them in the in-memory copy if we find them bad. We
 206  * also try to write the extent blocks back out. If we can't, then we
 207  * will wait until the next write transaction to write them out
 208  * (extent_mod tells us the on-disk copy is bad).
 209  */
 210 afs_int32
 211 readExtents(struct ubik_trans *trans)
 212 {
 213     afs_uint32 extentAddr;
 214     afs_int32 error = 0, code;
 215     int i;
 216
 217     extent_mod = 0;
 218     extentAddr = ntohl(cheader.SIT);
 219     if (!extentAddr)
 220         return 0;
 221
 222     /* Read the first extension block */
 223     if (!ex_addr[0]) {
 224         ex_addr[0] = (struct extentaddr *)malloc(VL_ADDREXTBLK_SIZE);
 225         if (!ex_addr[0])
 226             ERROR_EXIT(VL_NOMEM);
 227     }
 228     code = vlread(trans, extentAddr, (char *)ex_addr[0], VL_ADDREXTBLK_SIZE);
 229     if (code) {
 230         free(ex_addr[0]);       /* Not the place to create it */
 231         ex_addr[0] = 0;
 232         ERROR_EXIT(VL_IO);
 233     }
 234
 235     /* In case more that 64 mh servers are in use they're kept in these
 236      * continuation blocks
 237      */
 238     for (i = 1; i < VL_MAX_ADDREXTBLKS; i++) {
 239         if (!ex_addr[0]->ex_contaddrs[i])
 240             continue;
 241
 242         /* Before reading it in, check to see if the address is good */
 243         if ((ntohl(ex_addr[0]->ex_contaddrs[i]) <
 244              ntohl(ex_addr[0]->ex_contaddrs[i - 1]) + VL_ADDREXTBLK_SIZE)
 245             || (ntohl(ex_addr[0]->ex_contaddrs[i]) >
 246                 ntohl(cheader.vital_header.eofPtr) - VL_ADDREXTBLK_SIZE)) {
 247             extent_mod = 1;
 248             ex_addr[0]->ex_contaddrs[i] = 0;
 249             continue;
 250         }
 251
 252
 253         /* Read the continuation block */
 254         if (!ex_addr[i]) {
 255             ex_addr[i] = (struct extentaddr *)malloc(VL_ADDREXTBLK_SIZE);
 256             if (!ex_addr[i])
 257                 ERROR_EXIT(VL_NOMEM);
 258         }
 259         code =
 260             vlread(trans, ntohl(ex_addr[0]->ex_contaddrs[i]),
 261                    (char *)ex_addr[i], VL_ADDREXTBLK_SIZE);
 262         if (code) {
 263             free(ex_addr[i]);   /* Not the place to create it */
 264             ex_addr[i] = 0;
 265             ERROR_EXIT(VL_IO);
 266         }
 267
 268         /* After reading it in, check to see if its a real continuation block */
 269         if (ntohl(ex_addr[i]->ex_flags) != VLCONTBLOCK) {
 270             extent_mod = 1;
 271             ex_addr[0]->ex_contaddrs[i] = 0;
 272             free(ex_addr[i]);   /* Not the place to create it */
 273             ex_addr[i] = 0;
 274             continue;
 275         }
 276     }
 277
 278     if (extent_mod) {
 279         code = vlwrite(trans, extentAddr, ex_addr[0], VL_ADDREXTBLK_SIZE);
 280         if (!code) {
 281             VLog(0, ("Multihome server support modification\n"));
 282         }
 283         /* Keep extent_mod true in-case the transaction aborts */
 284         /* Don't return error so we don't abort transaction */
 285     }
 286
 287   error_exit:
 288     return error;
 289 }
 290
 291 /* Check that the database has been initialized.  Be careful to fail in a safe
 292    manner, to avoid bogusly reinitializing the db.  */
 293 /**
 294  * reads in db cache from ubik.
 295  *
 296  * @param[in] ut ubik transaction
 297  * @param[in] rock  opaque pointer to an int*; if 1, we should rebuild the db
 298  *                  if it appears empty, if 0 we should return an error if the
 299  *                  db appears empty
 300  *
 301  * @return operation status
 302  *   @retval 0 success
 303  */
 304 static afs_int32
 305 UpdateCache(struct ubik_trans *trans, void *rock)
 306 {
 307     int *builddb_rock = rock;
 308     int builddb = *builddb_rock;
 309     afs_int32 error = 0, i, code, ubcode;
 310
 311     /* if version changed (or first call), read the header */
 312     ubcode = vlread(trans, 0, (char *)&cheader, sizeof(cheader));
 313     vldbversion = ntohl(cheader.vital_header.vldbversion);
 314
 315     if (!ubcode && (vldbversion != 0)) {
 316         memcpy(HostAddress, cheader.IpMappedAddr, sizeof(cheader.IpMappedAddr));
 317         for (i = 0; i < MAXSERVERID + 1; i++) { /* cvt HostAddress to host order */
 318             HostAddress[i] = ntohl(HostAddress[i]);
 319         }
 320
 321         code = readExtents(trans);
 322         if (code)
 323             ERROR_EXIT(code);
 324     }
 325
 326     /* now, if can't read, or header is wrong, write a new header */
 327     if (ubcode || vldbversion == 0) {
 328         if (builddb) {
 329             printf("Can't read VLDB header, re-initialising...\n");
 330
 331             /* try to write a good header */
 332             memset(&cheader, 0, sizeof(cheader));
 333             cheader.vital_header.vldbversion = htonl(VLDBVERSION);
 334             cheader.vital_header.headersize = htonl(sizeof(cheader));
 335             /* DANGER: Must get this from a master place!! */
 336             cheader.vital_header.MaxVolumeId = htonl(0x20000000);
 337             cheader.vital_header.eofPtr = htonl(sizeof(cheader));
 338             for (i = 0; i < MAXSERVERID + 1; i++) {
 339                 cheader.IpMappedAddr[i] = 0;
 340                 HostAddress[i] = 0;
 341             }
 342             code = vlwrite(trans, 0, (char *)&cheader, sizeof(cheader));
 343             if (code) {
 344                 printf("Can't write VLDB header (error = %d)\n", code);
 345                 ERROR_EXIT(VL_IO);
 346             }
 347             vldbversion = ntohl(cheader.vital_header.vldbversion);
 348         } else {
 349             ERROR_EXIT(VL_EMPTY);
 350         }
 351     }
 352
 353     if ((vldbversion != VLDBVERSION) && (vldbversion != OVLDBVERSION)
 354         && (vldbversion != VLDBVERSION_4)) {
 355         printf
 356             ("VLDB version %d doesn't match this software version(%d, %d or %d), quitting!\n",
 357              vldbversion, VLDBVERSION_4, VLDBVERSION, OVLDBVERSION);
 358         return VL_BADVERSION;
 359     }
 360
 361     maxnservers = ((vldbversion == 3 || vldbversion == 4) ? 13 : 8);
 362
 363   error_exit:
 364     /* all done */
 365     return error;
 366 }
 367
 368 afs_int32
 369 CheckInit(struct ubik_trans *trans, int builddb)
 370 {
 371     afs_int32 code;
 372
 373     code = ubik_CheckCache(trans, UpdateCache, &builddb);
 374     if (code) {
 375         return code;
 376     }
 377
 378     /* these next two cases shouldn't happen (UpdateCache should either
 379      * rebuild the db or return an error if these cases occur), but just to
 380      * be on the safe side... */
 381     if (vldbversion == 0) {
 382         return VL_EMPTY;
 383     }
 384     if ((vldbversion != VLDBVERSION) && (vldbversion != OVLDBVERSION)
 385         && (vldbversion != VLDBVERSION_4)) {
 386         return VL_BADVERSION;
 387     }
 388
 389     return 0;
 390 }
 391
 392
 393 afs_int32
 394 GetExtentBlock(register struct ubik_trans *trans, register afs_int32 base)
 395 {
 396     afs_int32 blockindex, code, error = 0;
 397
 398     /* Base 0 must exist before any other can be created */
 399     if ((base != 0) && !ex_addr[0])
 400         ERROR_EXIT(VL_CREATEFAIL);      /* internal error */
 401
 402     if (!ex_addr[0] || !ex_addr[0]->ex_contaddrs[base]) {
 403         /* Create a new extension block */
 404         if (!ex_addr[base]) {
 405             ex_addr[base] = (struct extentaddr *)malloc(VL_ADDREXTBLK_SIZE);
 406             if (!ex_addr[base])
 407                 ERROR_EXIT(VL_NOMEM);
 408         }
 409         memset(ex_addr[base], 0, VL_ADDREXTBLK_SIZE);
 410
 411         /* Write the full extension block at end of vldb */
 412         ex_addr[base]->ex_flags = htonl(VLCONTBLOCK);
 413         blockindex = ntohl(cheader.vital_header.eofPtr);
 414         code =
 415             vlwrite(trans, blockindex, (char *)ex_addr[base],
 416                     VL_ADDREXTBLK_SIZE);
 417         if (code)
 418             ERROR_EXIT(VL_IO);
 419
 420         /* Update the cheader.vitalheader structure on disk */
 421         cheader.vital_header.eofPtr = blockindex + VL_ADDREXTBLK_SIZE;
 422         cheader.vital_header.eofPtr = htonl(cheader.vital_header.eofPtr);
 423         code = write_vital_vlheader(trans);
 424         if (code)
 425             ERROR_EXIT(VL_IO);
 426
 427         /* Write the address of the base extension block in the vldb header */
 428         if (base == 0) {
 429             cheader.SIT = htonl(blockindex);
 430             code =
 431                 vlwrite(trans, DOFFSET(0, &cheader, &cheader.SIT),
 432                         (char *)&cheader.SIT, sizeof(cheader.SIT));
 433             if (code)
 434                 ERROR_EXIT(VL_IO);
 435         }
 436
 437         /* Write the address of this extension block into the base extension block */
 438         ex_addr[0]->ex_contaddrs[base] = htonl(blockindex);
 439         code =
 440             vlwrite(trans, ntohl(cheader.SIT), ex_addr[0],
 441                     sizeof(struct extentaddr));
 442         if (code)
 443             ERROR_EXIT(VL_IO);
 444     }
 445
 446   error_exit:
 447     return error;
 448 }
 449
 450
 451 afs_int32
 452 FindExtentBlock(register struct ubik_trans *trans, afsUUID *uuidp,
 453                 afs_int32 createit, afs_int32 hostslot,
 454                 struct extentaddr **expp, afs_int32 *basep)
 455 {
 456     afsUUID tuuid;
 457     struct extentaddr *exp;
 458     register afs_int32 i, j, code, base, index, error = 0;
 459
 460     *expp = NULL;
 461     *basep = 0;
 462
 463     /* Create the first extension block if it does not exist */
 464     if (!cheader.SIT) {
 465         code = GetExtentBlock(trans, 0);
 466         if (code)
 467             ERROR_EXIT(code);
 468     }
 469
 470     for (i = 0; i < MAXSERVERID + 1; i++) {
 471         if ((HostAddress[i] & 0xff000000) == 0xff000000) {
 472             if ((base = (HostAddress[i] >> 16) & 0xff) > VL_MAX_ADDREXTBLKS) {
 473                 ERROR_EXIT(VL_INDEXERANGE);
 474             }
 475             if ((index = HostAddress[i] & 0x0000ffff) > VL_MHSRV_PERBLK) {
 476                 ERROR_EXIT(VL_INDEXERANGE);
 477             }
 478             exp = &ex_addr[base][index];
 479             tuuid = exp->ex_hostuuid;
 480             afs_ntohuuid(&tuuid);
 481             if (afs_uuid_equal(uuidp, &tuuid)) {
 482                 *expp = exp;
 483                 *basep = base;
 484                 ERROR_EXIT(0);
 485             }
 486         }
 487     }
 488
 489     if (createit) {
 490         if (hostslot == -1) {
 491             for (i = 0; i < MAXSERVERID + 1; i++) {
 492                 if (!HostAddress[i])
 493                     break;
 494             }
 495             if (i > MAXSERVERID)
 496                 ERROR_EXIT(VL_REPSFULL);
 497         } else {
 498             i = hostslot;
 499         }
 500
 501         for (base = 0; base < VL_MAX_ADDREXTBLKS; base++) {
 502             if (!ex_addr[0]->ex_contaddrs[base]) {
 503                 code = GetExtentBlock(trans, base);
 504                 if (code)
 505                     ERROR_EXIT(code);
 506             }
 507             for (j = 1; j < VL_MHSRV_PERBLK; j++) {
 508                 exp = &ex_addr[base][j];
 509                 tuuid = exp->ex_hostuuid;
 510                 afs_ntohuuid(&tuuid);
 511                 if (afs_uuid_is_nil(&tuuid)) {
 512                     tuuid = *uuidp;
 513                     afs_htonuuid(&tuuid);
 514                     exp->ex_hostuuid = tuuid;
 515                     code =
 516                         vlwrite(trans,
 517                                 DOFFSET(ntohl(ex_addr[0]->ex_contaddrs[base]),
 518                                         (char *)ex_addr[base], (char *)exp),
 519                                 (char *)&tuuid, sizeof(tuuid));
 520                     if (code)
 521                         ERROR_EXIT(VL_IO);
 522                     HostAddress[i] =
 523                         0xff000000 | ((base << 16) & 0xff0000) | (j & 0xffff);
 524                     *expp = exp;
 525                     *basep = base;
 526                     if (vldbversion != VLDBVERSION_4) {
 527                         cheader.vital_header.vldbversion =
 528                             htonl(VLDBVERSION_4);
 529                         code = write_vital_vlheader(trans);
 530                         if (code)
 531                             ERROR_EXIT(VL_IO);
 532                     }
 533                     cheader.IpMappedAddr[i] = htonl(HostAddress[i]);
 534                     code =
 535                         vlwrite(trans,
 536                                 DOFFSET(0, &cheader,
 537                                         &cheader.IpMappedAddr[i]),
 538                                 (char *)&cheader.IpMappedAddr[i],
 539                                 sizeof(afs_int32));
 540                     if (code)
 541                         ERROR_EXIT(VL_IO);
 542                     ERROR_EXIT(0);
 543                 }
 544             }
 545         }
 546         ERROR_EXIT(VL_REPSFULL);        /* No reason to utilize a new error code */
 547     }
 548
 549   error_exit:
 550     return error;
 551 }
 552
 553 /* Allocate a free block of storage for entry, returning address of a new
 554    zeroed entry (or zero if something is wrong).  */
 555 afs_int32
 556 AllocBlock(register struct ubik_trans *trans, struct nvlentry *tentry)
 557 {
 558     register afs_int32 blockindex;
 559
 560     if (cheader.vital_header.freePtr) {
 561         /* allocate this dude */
 562         blockindex = ntohl(cheader.vital_header.freePtr);
 563         if (vlentryread(trans, blockindex, (char *)tentry, sizeof(vlentry)))
 564             return 0;
 565         cheader.vital_header.freePtr = htonl(tentry->nextIdHash[0]);
 566     } else {
 567         /* hosed, nothing on free list, grow file */
 568         blockindex = ntohl(cheader.vital_header.eofPtr);        /* remember this guy */
 569         cheader.vital_header.eofPtr = htonl(blockindex + sizeof(vlentry));
 570     }
 571     cheader.vital_header.allocs++;
 572     if (write_vital_vlheader(trans))
 573         return 0;
 574     memset(tentry, 0, sizeof(nvlentry));        /* zero new entry */
 575     return blockindex;
 576 }
 577
 578
 579 /* Free a block given its index.  It must already have been unthreaded. Returns zero for success or an error code on failure. */
 580 int
 581 FreeBlock(struct ubik_trans *trans, afs_int32 blockindex)
 582 {
 583     struct nvlentry tentry;
 584
 585     /* check validity of blockindex just to be on the safe side */
 586     if (!index_OK(trans, blockindex))
 587         return VL_BADINDEX;
 588     memset(&tentry, 0, sizeof(nvlentry));
 589     tentry.nextIdHash[0] = cheader.vital_header.freePtr;        /* already in network order */
 590     tentry.flags = htonl(VLFREE);
 591     cheader.vital_header.freePtr = htonl(blockindex);
 592     if (vlwrite(trans, blockindex, (char *)&tentry, sizeof(nvlentry)))
 593         return VL_IO;
 594     cheader.vital_header.frees++;
 595     if (write_vital_vlheader(trans))
 596         return VL_IO;
 597     return 0;
 598 }
 599
 600
 601 /* Look for a block by volid and voltype (if not known use -1 which searches
 602  * all 3 volid hash lists. Note that the linked lists are read in first from
 603  * the database header.  If found read the block's contents into the area
 604  * pointed to by tentry and return the block's index.  If not found return 0.
 605  */
 606 afs_int32
 607 FindByID(struct ubik_trans *trans, afs_uint32 volid, afs_int32 voltype,
 608          struct nvlentry *tentry, afs_int32 *error)
 609 {
 610     register afs_int32 typeindex, hashindex, blockindex;
 611
 612     *error = 0;
 613     hashindex = IDHash(volid);
 614     if (voltype == -1) {
 615 /* Should we have one big hash table for volids as opposed to the three ones? */
 616         for (typeindex = 0; typeindex < MAXTYPES; typeindex++) {
 617             for (blockindex = ntohl(cheader.VolidHash[typeindex][hashindex]);
 618                  blockindex != NULLO;
 619                  blockindex = tentry->nextIdHash[typeindex]) {
 620                 if (vlentryread
 621                     (trans, blockindex, (char *)tentry, sizeof(nvlentry))) {
 622                     *error = VL_IO;
 623                     return 0;
 624                 }
 625                 if (volid == tentry->volumeId[typeindex])
 626                     return blockindex;
 627             }
 628         }
 629     } else {
 630         for (blockindex = ntohl(cheader.VolidHash[voltype][hashindex]);
 631              blockindex != NULLO; blockindex = tentry->nextIdHash[voltype]) {
 632             if (vlentryread
 633                 (trans, blockindex, (char *)tentry, sizeof(nvlentry))) {
 634                 *error = VL_IO;
 635                 return 0;
 636             }
 637             if (volid == tentry->volumeId[voltype])
 638                 return blockindex;
 639         }
 640     }
 641     return 0;                   /* no such entry */
 642 }
 643
 644
 645 /* Look for a block by volume name. If found read the block's contents into
 646  * the area pointed to by tentry and return the block's index.  If not
 647  * found return 0.
 648  */
 649 afs_int32
 650 FindByName(struct ubik_trans *trans, char *volname, struct nvlentry *tentry,
 651            afs_int32 *error)
 652 {
 653     register afs_int32 hashindex;
 654     register afs_int32 blockindex;
 655     char tname[VL_MAXNAMELEN];
 656
 657     /* remove .backup or .readonly extensions for stupid backwards
 658      * compatibility
 659      */
 660     hashindex = strlen(volname);        /* really string length */
 661     if (hashindex >= 8 && strcmp(volname + hashindex - 7, ".backup") == 0) {
 662         /* this is a backup volume */
 663         strcpy(tname, volname);
 664         tname[hashindex - 7] = 0;       /* zap extension */
 665     } else if (hashindex >= 10
 666                && strcmp(volname + hashindex - 9, ".readonly") == 0) {
 667         /* this is a readonly volume */
 668         strcpy(tname, volname);
 669         tname[hashindex - 9] = 0;       /* zap extension */
 670     } else
 671         strcpy(tname, volname);
 672
 673     *error = 0;
 674     hashindex = NameHash(tname);
 675     for (blockindex = ntohl(cheader.VolnameHash[hashindex]);
 676          blockindex != NULLO; blockindex = tentry->nextNameHash) {
 677         if (vlentryread(trans, blockindex, (char *)tentry, sizeof(nvlentry))) {
 678             *error = VL_IO;
 679             return 0;
 680         }
 681         if (!strcmp(tname, tentry->name))
 682             return blockindex;
 683     }
 684     return 0;                   /* no such entry */
 685 }
 686
 687 /**
 688  * Returns whether or not any of the supplied volume IDs already exist
 689  * in the vldb.
 690  *
 691  * @param trans    the ubik transaction
 692  * @param ids      an array of volume IDs
 693  * @param ids_len  the number of elements in the 'ids' array
 694  * @param error    filled in with an error code in case of error
 695  *
 696  * @return whether any of the volume IDs are already used
 697  *  @retval 1  at least one of the volume IDs is already used
 698  *  @retval 0  none of the volume IDs are used, or an error occurred
 699  */
 700 int
 701 EntryIDExists(struct ubik_trans *trans, const afs_uint32 *ids,
 702               afs_int32 ids_len, afs_int32 *error)
 703 {
 704     afs_int32 typeindex;
 705     struct nvlentry tentry;
 706
 707     *error = 0;
 708
 709     for (typeindex = 0; typeindex < ids_len; typeindex++) {
 710         if (ids[typeindex]
 711             && FindByID(trans, ids[typeindex], -1, &tentry, error)) {
 712
 713             return 1;
 714         } else if (*error) {
 715             return 0;
 716         }
 717     }
 718
 719     return 0;
 720 }
 721
 722 /**
 723  * Finds the next range of unused volume IDs in the vldb.
 724  *
 725  * @param trans     the ubik transaction
 726  * @param maxvolid  the current max vol ID, and where to start looking
 727  *                  for an unused volume ID range
 728  * @param bump      how many volume IDs we need to be unused
 729  * @param error     filled in with an error code in case of error
 730  *
 731  * @return the next volume ID 'volid' such that the range
 732  *         [volid, volid+bump) of volume IDs is unused, or 0 if there's
 733  *         an error
 734  */
 735 afs_uint32
 736 NextUnusedID(struct ubik_trans *trans, afs_uint32 maxvolid, afs_uint32 bump,
 737              afs_int32 *error)
 738 {
 739     struct nvlentry tentry;
 740     afs_uint32 id;
 741     afs_uint32 nfree;
 742
 743     *error = 0;
 744
 745      /* we simply start at the given maxvolid, keep a running tally of
 746       * how many free volume IDs we've seen in a row, and return when
 747       * we've seen 'bump' unused IDs in a row */
 748     for (id = maxvolid, nfree = 0; nfree < bump; ++id) {
 749         if (FindByID(trans, id, -1, &tentry, error)) {
 750             nfree = 0;
 751         } else if (*error) {
 752             return 0;
 753         } else {
 754             ++nfree;
 755         }
 756     }
 757
 758     /* 'id' is now at the end of the [maxvolid,maxvolid+bump) range,
 759      * but we need to return the first unused id, so subtract the
 760      * number of current running free IDs to get the beginning */
 761     return id - nfree;
 762 }
 763
 764 int
 765 HashNDump(struct ubik_trans *trans, int hashindex)
 766 {
 767     register int i = 0;
 768     register int blockindex;
 769     struct nvlentry tentry;
 770
 771     for (blockindex = ntohl(cheader.VolnameHash[hashindex]);
 772          blockindex != NULLO; blockindex = tentry.nextNameHash) {
 773         if (vlentryread(trans, blockindex, (char *)&tentry, sizeof(nvlentry)))
 774             return 0;
 775         i++;
 776         VLog(0,
 777              ("[%d]#%d: %10d %d %d (%s)\n", hashindex, i, tentry.volumeId[0],
 778               tentry.nextIdHash[0], tentry.nextNameHash, tentry.name));
 779     }
 780     return 0;
 781 }
 782
 783
 784 int
 785 HashIdDump(struct ubik_trans *trans, int hashindex)
 786 {
 787     register int i = 0;
 788     register int blockindex;
 789     struct nvlentry tentry;
 790
 791     for (blockindex = ntohl(cheader.VolidHash[0][hashindex]);
 792          blockindex != NULLO; blockindex = tentry.nextIdHash[0]) {
 793         if (vlentryread(trans, blockindex, (char *)&tentry, sizeof(nvlentry)))
 794             return 0;
 795         i++;
 796         VLog(0,
 797              ("[%d]#%d: %10d %d %d (%s)\n", hashindex, i, tentry.volumeId[0],
 798               tentry.nextIdHash[0], tentry.nextNameHash, tentry.name));
 799     }
 800     return 0;
 801 }
 802
 803
 804 /* Add a block to the hash table given a pointer to the block and its index.
 805  * The block is threaded onto both hash tables and written to disk.  The
 806  * routine returns zero if there were no errors.
 807  */
 808 int
 809 ThreadVLentry(struct ubik_trans *trans, afs_int32 blockindex,
 810               struct nvlentry *tentry)
 811 {
 812     int errorcode;
 813
 814     if (!index_OK(trans, blockindex))
 815         return VL_BADINDEX;
 816     /* Insert into volid's hash linked list */
 817     if ((errorcode = HashVolid(trans, RWVOL, blockindex, tentry)))
 818         return errorcode;
 819
 820     /* For rw entries we also enter the RO and BACK volume ids (if they
 821      * exist) in the hash tables; note all there volids (RW, RO, BACK)
 822      * should not be hashed yet! */
 823     if (tentry->volumeId[ROVOL]) {
 824         if ((errorcode = HashVolid(trans, ROVOL, blockindex, tentry)))
 825             return errorcode;
 826     }
 827     if (tentry->volumeId[BACKVOL]) {
 828         if ((errorcode = HashVolid(trans, BACKVOL, blockindex, tentry)))
 829             return errorcode;
 830     }
 831
 832     /* Insert into volname's hash linked list */
 833     HashVolname(trans, blockindex, tentry);
 834
 835     /* Update cheader entry */
 836     if (write_vital_vlheader(trans))
 837         return VL_IO;
 838
 839     /* Update hash list pointers in the entry itself */
 840     if (vlentrywrite(trans, blockindex, (char *)tentry, sizeof(nvlentry)))
 841         return VL_IO;
 842     return 0;
 843 }
 844
 845
 846 /* Remove a block from both the hash tables.  If success return 0, else
 847  * return an error code. */
 848 int
 849 UnthreadVLentry(struct ubik_trans *trans, afs_int32 blockindex,
 850                 struct nvlentry *aentry)
 851 {
 852     register afs_int32 errorcode, typeindex;
 853
 854     if (!index_OK(trans, blockindex))
 855         return VL_BADINDEX;
 856     if ((errorcode = UnhashVolid(trans, RWVOL, blockindex, aentry)))
 857         return errorcode;
 858
 859     /* Take the RO/RW entries of their respective hash linked lists. */
 860     for (typeindex = ROVOL; typeindex <= BACKVOL; typeindex++) {
 861         if ((errorcode = UnhashVolid(trans, typeindex, blockindex, aentry)))
 862             return errorcode;
 863     }
 864
 865     /* Take it out of the Volname hash list */
 866     if ((errorcode = UnhashVolname(trans, blockindex, aentry)))
 867         return errorcode;
 868
 869     /* Update cheader entry */
 870     write_vital_vlheader(trans);
 871
 872     return 0;
 873 }
 874
 875 /* cheader must have be read before this routine is called. */
 876 int
 877 HashVolid(struct ubik_trans *trans, afs_int32 voltype, afs_int32 blockindex,
 878           struct nvlentry *tentry)
 879 {
 880     afs_int32 hashindex, errorcode;
 881     struct nvlentry ventry;
 882
 883     if (FindByID
 884         (trans, tentry->volumeId[voltype], voltype, &ventry, &errorcode))
 885         return VL_IDALREADYHASHED;
 886     else if (errorcode)
 887         return errorcode;
 888     hashindex = IDHash(tentry->volumeId[voltype]);
 889     tentry->nextIdHash[voltype] =
 890         ntohl(cheader.VolidHash[voltype][hashindex]);
 891     cheader.VolidHash[voltype][hashindex] = htonl(blockindex);
 892     if (vlwrite
 893         (trans, DOFFSET(0, &cheader, &cheader.VolidHash[voltype][hashindex]),
 894          (char *)&cheader.VolidHash[voltype][hashindex], sizeof(afs_int32)))
 895         return VL_IO;
 896     return 0;
 897 }
 898
 899
 900 /* cheader must have be read before this routine is called. */
 901 int
 902 UnhashVolid(struct ubik_trans *trans, afs_int32 voltype, afs_int32 blockindex,
 903             struct nvlentry *aentry)
 904 {
 905     int hashindex, nextblockindex, prevblockindex;
 906     struct nvlentry tentry;
 907     afs_int32 code;
 908     afs_int32 temp;
 909
 910     if (aentry->volumeId[voltype] == NULLO)     /* Assume no volume id */
 911         return 0;
 912     /* Take it out of the VolId[voltype] hash list */
 913     hashindex = IDHash(aentry->volumeId[voltype]);
 914     nextblockindex = ntohl(cheader.VolidHash[voltype][hashindex]);
 915     if (nextblockindex == blockindex) {
 916         /* First on the hash list; just adjust pointers */
 917         cheader.VolidHash[voltype][hashindex] =
 918             htonl(aentry->nextIdHash[voltype]);
 919         code =
 920             vlwrite(trans,
 921                     DOFFSET(0, &cheader,
 922                             &cheader.VolidHash[voltype][hashindex]),
 923                     (char *)&cheader.VolidHash[voltype][hashindex],
 924                     sizeof(afs_int32));
 925         if (code)
 926             return VL_IO;
 927     } else {
 928         while (nextblockindex != blockindex) {
 929             prevblockindex = nextblockindex;    /* always done once */
 930             if (vlentryread
 931                 (trans, nextblockindex, (char *)&tentry, sizeof(nvlentry)))
 932                 return VL_IO;
 933             if ((nextblockindex = tentry.nextIdHash[voltype]) == NULLO)
 934                 return VL_NOENT;
 935         }
 936         temp = tentry.nextIdHash[voltype] = aentry->nextIdHash[voltype];
 937         temp = htonl(temp);     /* convert to network byte order before writing */
 938         if (vlwrite
 939             (trans,
 940              DOFFSET(prevblockindex, &tentry, &tentry.nextIdHash[voltype]),
 941              (char *)&temp, sizeof(afs_int32)))
 942             return VL_IO;
 943     }
 944     aentry->nextIdHash[voltype] = 0;
 945     return 0;
 946 }
 947
 948
 949 int
 950 HashVolname(struct ubik_trans *trans, afs_int32 blockindex,
 951             struct nvlentry *aentry)
 952 {
 953     register afs_int32 hashindex;
 954     register afs_int32 code;
 955
 956     /* Insert into volname's hash linked list */
 957     hashindex = NameHash(aentry->name);
 958     aentry->nextNameHash = ntohl(cheader.VolnameHash[hashindex]);
 959     cheader.VolnameHash[hashindex] = htonl(blockindex);
 960     code =
 961         vlwrite(trans, DOFFSET(0, &cheader, &cheader.VolnameHash[hashindex]),
 962                 (char *)&cheader.VolnameHash[hashindex], sizeof(afs_int32));
 963     if (code)
 964         return VL_IO;
 965     return 0;
 966 }
 967
 968
 969 int
 970 UnhashVolname(struct ubik_trans *trans, afs_int32 blockindex,
 971               struct nvlentry *aentry)
 972 {
 973     register afs_int32 hashindex, nextblockindex, prevblockindex;
 974     struct nvlentry tentry;
 975     afs_int32 temp;
 976
 977     /* Take it out of the Volname hash list */
 978     hashindex = NameHash(aentry->name);
 979     nextblockindex = ntohl(cheader.VolnameHash[hashindex]);
 980     if (nextblockindex == blockindex) {
 981         /* First on the hash list; just adjust pointers */
 982         cheader.VolnameHash[hashindex] = htonl(aentry->nextNameHash);
 983         if (vlwrite
 984             (trans, DOFFSET(0, &cheader, &cheader.VolnameHash[hashindex]),
 985              (char *)&cheader.VolnameHash[hashindex], sizeof(afs_int32)))
 986             return VL_IO;
 987     } else {
 988         while (nextblockindex != blockindex) {
 989             prevblockindex = nextblockindex;    /* always done at least once */
 990             if (vlentryread
 991                 (trans, nextblockindex, (char *)&tentry, sizeof(nvlentry)))
 992                 return VL_IO;
 993             if ((nextblockindex = tentry.nextNameHash) == NULLO)
 994                 return VL_NOENT;
 995         }
 996         tentry.nextNameHash = aentry->nextNameHash;
 997         temp = htonl(tentry.nextNameHash);
 998         if (vlwrite
 999             (trans, DOFFSET(prevblockindex, &tentry, &tentry.nextNameHash),
1000              (char *)&temp, sizeof(afs_int32)))
1001             return VL_IO;
1002     }
1003     aentry->nextNameHash = 0;
1004     return 0;
1005 }
1006
1007
1008 /* Returns the vldb entry tentry at offset index; remaining is the number of
1009  * entries left; the routine also returns the index of the next sequential
1010  * entry in the vldb
1011  */
1012
1013 afs_int32
1014 NextEntry(struct ubik_trans *trans, afs_int32 blockindex,
1015           struct nvlentry *tentry, afs_int32 *remaining)
1016 {
1017     register afs_int32 lastblockindex;
1018
1019     if (blockindex == 0)        /* get first one */
1020         blockindex = sizeof(cheader);
1021     else {
1022         if (!index_OK(trans, blockindex)) {
1023             *remaining = -1;    /* error */
1024             return 0;
1025         }
1026         blockindex += sizeof(nvlentry);
1027     }
1028     /* now search for the first entry that isn't free */
1029     for (lastblockindex = ntohl(cheader.vital_header.eofPtr);
1030          blockindex < lastblockindex;) {
1031         if (vlentryread(trans, blockindex, (char *)tentry, sizeof(nvlentry))) {
1032             *remaining = -1;
1033             return 0;
1034         }
1035         if (tentry->flags == VLCONTBLOCK) {
1036             /*
1037              * This is a special mh extension block just simply skip over it
1038              */
1039             blockindex += VL_ADDREXTBLK_SIZE;
1040         } else {
1041             if (tentry->flags != VLFREE) {
1042                 /* estimate remaining number of entries, not including this one */
1043                 *remaining =
1044                     (lastblockindex - blockindex) / sizeof(nvlentry) - 1;
1045                 return blockindex;
1046             }
1047             blockindex += sizeof(nvlentry);
1048         }
1049     }
1050     *remaining = 0;             /* no more entries */
1051     return 0;
1052 }
1053
1054
1055 /* Routine to verify that index is a legal offset to a vldb entry in the
1056  * table
1057  */
1058 static int
1059 index_OK(struct ubik_trans *trans, afs_int32 blockindex)
1060 {
1061     if ((blockindex < sizeof(cheader))
1062         || (blockindex >= ntohl(cheader.vital_header.eofPtr)))
1063         return 0;
1064     return 1;
1065 }