cd9ff5cdc6a3bc33f1c9072d13d74a7d5c2bcb79
[openafs.git] / 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 }