Rewrite vldb_check -fix
authorRod Widdowson <rdw@steadingsoftware.com>
Thu, 20 May 2010 17:27:11 +0000 (18:27 +0100)
committerRuss Allbery <rra@stanford.edu>
Sun, 30 May 2010 20:11:12 +0000 (13:11 -0700)
vldb_check -fix was very 'topical' in nature.  It showed signs that
each sucessive corruption had been treated as a one off needing a
specific fix.  This made the code difficult to understand and
incomplete: for instance a single volume on the wrong hash only was
not corrected.  Further there was some rather unfortunately code which
would under certain circumstances stamp the last volume at various
places across the file.

This checkin removes all the old code and replaces it with a
'systematic' fix.  During the last scan across all the volumes, all
four of the hash chains are rebuild from the ground up.  We can then
get rid of the outer 'Mung Until Now Good' iteration and further we
benefit from a linear run time.

Tested by building several different forms of broken-ness in all three
chains and then fixing it.

Now with improved logging and correct non insertion of nonexistant elements
and clean compiled with extra warning.

Change-Id: Id39d806c9c90f67c6967bd99460ba9842a043158
Reviewed-on: http://gerrit.openafs.org/1991
Reviewed-by: Russ Allbery <rra@stanford.edu>
Tested-by: Russ Allbery <rra@stanford.edu>

src/vlserver/vldb_check.c

index 166ae6e..fa9c8d8 100644 (file)
@@ -75,7 +75,6 @@ int fd;
 int listentries, listservers, listheader, listuheader, verbose, quiet;
 
 int fix = 0;
-int fixed = 0;
 int passes = 0;
 /* if quiet, don't send anything to stdout */
 int quiet = 0; 
@@ -463,7 +462,6 @@ writeentry(afs_int32 addr, struct nvlentry *vlentryp)
     int i;
 
     if (verbose) quiet_println("Writing back entry at addr %u\n", addr);
-    fixed++;
     for (i = 0; i < MAXTYPES; i++)
        vlentryp->volumeId[i] = htonl(vlentryp->volumeId[i]);
     vlentryp->flags = htonl(vlentryp->flags);
@@ -637,57 +635,6 @@ ReadAllEntries(struct vlheader *header)
             header->vital_header.MaxVolumeId, maxvolid);
 }
 
-
-void
-SetHashEnd(long addr, int type, long new)
-{
-    struct nvlentry vlentry;
-    afs_int32 type2, next = -1;
-
-    for (; addr; addr = next) {
-       readentry(addr, &vlentry, &type2);
-       switch(type & 0xf0) {
-       case RWH:
-           next = vlentry.nextIdHash[0];
-           break;
-       case ROH:
-           next = vlentry.nextIdHash[1];
-           break;
-       case BKH:
-           next = vlentry.nextIdHash[2];
-           break;
-       case NH:
-           next = vlentry.nextNameHash;
-           break;
-       default:
-           next = -1;
-       }
-
-       if (next < 1) {
-           switch(type & 0xf0) {
-           case RWH:
-             if (vlentry.nextIdHash[0] != 0) {quiet_println("bwoop\n");}
-               vlentry.nextIdHash[0] = new;
-               break;
-           case ROH:
-             if (vlentry.nextIdHash[1] != 0) {quiet_println("bwoop\n");}
-               vlentry.nextIdHash[1] = new;
-               break;
-           case BKH:
-             if (vlentry.nextIdHash[2] != 0) {quiet_println("bwoop\n");}
-               vlentry.nextIdHash[2] = new;
-               break;
-           case NH:
-             if (vlentry.nextNameHash != 0) {quiet_println("bwoop\n");}
-               vlentry.nextNameHash = new;
-               break;
-           }
-           writeentry(addr, &vlentry);
-           return;
-       }
-    }
-}
-
 /*
  * Follow each Name hash bucket marking it as read in the record array.
  * Record we found it in the name hash within the record array.
@@ -1120,12 +1067,72 @@ CheckIpAddrs(struct vlheader *header)
     return;
 }
 
-void 
-FixBad(afs_uint32 idx, afs_uint32 addr, afs_uint32 type, afs_uint32 tmp, 
-       struct nvlentry *vlentry, afs_uint32 hash) {
-    SetHashEnd(addr, type, tmp);
-    quiet_println("linked unlinked chain %u (index %lu) to end of chain %d for %s hash\n", 
-          tmp, ADDR(tmp), hash, type==NH?"Name":(type==RWH?"RW":(type==ROH?"RO":"BK")));
+char *
+nameForAddr(afs_uint32 addr, int hashtype, afs_uint32 *hash, char *buffer)
+{
+    /*
+     * We need to simplify the reporting, while retaining
+     * legible messages.  This is a helper function.  The return address
+     * is either a fixed char or the provided buffer - so don't use the
+     * name after the valid lifetime of the buffer.
+     */
+    afs_int32 type;
+    struct nvlentry entry;
+    if (!addr) {
+       /* Distinguished, invalid, hash */
+       *hash = 0xFFFFFFFF;
+       return "empty";
+    } else if (!validVolumeAddr(addr)) {
+       /* Different, invalid, hash */
+       *hash = 0XFFFFFFFE;
+       return "invalid";
+    }
+    readentry(addr, &entry, &type);
+    if (VL != type) {
+       *hash = 0XFFFFFFFE;
+       return "invalid";
+    }
+    if (hashtype >= MAXTYPES) {
+       *hash = NameHash(entry.name);
+    } else {
+       *hash = IdHash(entry.volumeId[hashtype]);
+    }
+    sprintf(buffer, "for '%s'", entry.name);
+    return buffer;
+}
+
+void
+reportHashChanges(struct vlheader *header, afs_uint32 oldnamehash[HASHSIZE], afs_uint32 oldidhash[MAXTYPES][HASHSIZE])
+{
+    int i, j;
+    afs_uint32 oldhash, newhash;
+    char oldNameBuffer[10 + VL_MAXNAMELEN];
+    char newNameBuffer[10 + VL_MAXNAMELEN];
+    char *oldname, *newname;
+    /*
+     * report hash changes
+     */
+
+    for (i = 0; i < HASHSIZE; i++) {
+       if (oldnamehash[i] != header->VolnameHash[i]) {
+
+           oldname = nameForAddr(oldnamehash[i], MAXTYPES, &oldhash, oldNameBuffer);
+           newname = nameForAddr(header->VolnameHash[i], MAXTYPES, &newhash, newNameBuffer);
+           if (verbose || (oldhash != newhash)) {
+               quiet_println("FIX: Name hash header at %d was %s, is now %s\n", i, oldname, newname);
+           }
+       }
+       for (j = 0; j < MAXTYPES; j++) {
+           if (oldidhash[j][i] != header->VolidHash[j][i]) {
+
+               oldname = nameForAddr(oldidhash[j][i], j, &oldhash, oldNameBuffer);
+               newname = nameForAddr(header->VolidHash[j][i], j, &newhash, newNameBuffer);
+               if (verbose || (oldhash != newhash)) {
+                   quiet_println("FIX: %s hash header at %d was %s, is now %s\n", vtype(j), i, oldname, newname);
+               }
+           }
+       }
+    }
 }
 
 int
@@ -1136,6 +1143,8 @@ WorkerBee(struct cmd_syndesc *as, void *arock)
     struct vlheader header;
     struct nvlentry vlentry, vlentry2;
     int i, j;
+    afs_uint32 oldnamehash[HASHSIZE];
+    afs_uint32 oldidhash[MAXTYPES][HASHSIZE];
 
     error_level = 0;  /*  start clean with no error status */
     dbfile = as->parms[0].items->data; /* -database */
@@ -1154,7 +1163,7 @@ WorkerBee(struct cmd_syndesc *as, void *arock)
         return VLDB_CHECK_FATAL;
     }
 
- restart:
+
     /* open the vldb database file */
     fd = open(dbfile, (fix > 0)?O_RDWR:O_RDONLY, 0);
     if (fd < 0) {
@@ -1335,24 +1344,13 @@ WorkerBee(struct cmd_syndesc *as, void *arock)
            }
 
            if (foundbroken) {
-               log_error(VLDB_CHECK_ERROR, "%d: Volume '%s' %s forward link in %s hash chain is broken (hash %d != %d)", i,
+               log_error(VLDB_CHECK_ERROR, "%d: Volume '%s' %s forward link in %s hash chain is broken (hash %d != %d)\n", i,
                          vlentry.name, volidbuf, which, hash, nexthash);
            } else if (foundbad) {
-               log_error(VLDB_CHECK_ERROR, "%d: Volume '%s' %snot found in %s hash %d", i,
+               log_error(VLDB_CHECK_ERROR, "%d: Volume '%s' %snot found in %s hash %d\n", i,
                       vlentry.name, volidbuf, which, hash);
            }
 
-           if (foundbad || foundbroken) {
-               if (nextp && fix) {
-                   log_error(VLDB_CHECK_ERROR, ", unchaining next (%d)\n", nextp);
-                   *nextpp = 0;
-                   writeentry(record[i].addr, &vlentry);
-               } else {
-                   log_error(VLDB_CHECK_ERROR, "\n");
-               }
-               
-           }
-
            for (j = 0; j < NMAXNSERVERS; j++) {
                if ((vlentry.serverNumber[j] != 255)
                    && (serveraddrs[vlentry.serverNumber[j]] == 0)) {
@@ -1395,136 +1393,104 @@ WorkerBee(struct cmd_syndesc *as, void *arock)
        }
     }
 
-    if (verbose)  quiet_println("Verify each chain head\n");
-    {
-       afs_uint32 addr;
-       int hash;
-
-       for (j = 0; j < HASHSIZE; j++) {
-           for (addr = header.VolnameHash[j]; j < HASHSIZE; j++) {
-               if (record[ADDR(addr)].type & MULTN) {
-                   hash = NameHash(vlentry.name);
-                   if (hash != j) {
-                       header.VolnameHash[j] = vlentry.nextNameHash;
-                       vlentry.nextNameHash = 0;
-                       if (fix)
-                           writeentry(record[i].addr, &vlentry);
-                   }
-               }
-           }
-       }
-       for (i = 0; i <= 2; i++) {
-         for (j = 0, addr = header.VolidHash[i][j]; j < HASHSIZE; j++) {
-        if (verbose) quiet_println("got %d %d %d\n", i, j, ADDR(addr));
-               if (i == 0 && (record[ADDR(addr)].type & MULTRW)) {
-                   hash = IdHash(vlentry.volumeId[i]);
-                   if (hash != j) {
-                       header.VolidHash[i][j] = vlentry.nextIdHash[i];
-                       vlentry.nextIdHash[i] = 0;
-                       if (fix) {
-                         quiet_println("fix %d %d %d\n", i, j, ADDR(addr));
-                           writeentry(record[i].addr, &vlentry);
-                   }
-               }
-               }
-
-               if (i == 1 && (record[ADDR(addr)].type & MULTRO)) {
-                   hash = IdHash(vlentry.volumeId[i]);
-                   if (hash != j) {
-                       header.VolidHash[i][j] = vlentry.nextIdHash[i];
-                       vlentry.nextIdHash[i] = 0;
-                       if (fix) {
-                         quiet_println("fix %d %d %d\n", i, j, addr);
-                           writeentry(record[i].addr, &vlentry);
-                   }
-               }
-               }
+    if (fix) {
+       /*
+        * If we are fixing we will rebuild all the hash lists from the ground up
+        */
+       memcpy(oldnamehash, header.VolnameHash, sizeof(oldnamehash));
+       memset(header.VolnameHash, 0, sizeof(header.VolnameHash));
 
-               if (i == 2 && (record[ADDR(addr)].type & MULTBK)) {
-                   hash = IdHash(vlentry.volumeId[i]);
-                   if (hash != j) {
-                       header.VolidHash[i][j] = vlentry.nextIdHash[i];
-                       vlentry.nextIdHash[i] = 0;
-                       if (fix) {
-                         quiet_println("fix %d %d %d\n", i, j, addr);
-                           writeentry(record[i].addr, &vlentry);
-                   }
-               }
-           }
-       }
-    }
+       memcpy(oldidhash, header.VolidHash, sizeof(oldidhash));
+       memset(header.VolidHash, 0, sizeof(header.VolidHash));
+       quiet_println("Rebuilding %u entries\n", maxentries);
+    } else {
+       quiet_println("Scanning %u entries for possible repairs\n", maxentries);
     }
-    /* By the time we get here, unchained entries are really unchained */
-    quiet_println("Scanning %u entries for possible repairs\n", maxentries);
     for (i = 0; i < maxentries; i++) {
-       int *nextpp;
+       afs_uint32 hash;
        if (record[i].type & VL) {
            readentry(record[i].addr, &vlentry, &type);
            if (!(record[i].type & REFN)) {
                log_error(VLDB_CHECK_ERROR,"%d: Record %ld (type 0x%x) not in a name chain\n", i, 
                       record[i].addr, record[i].type);
-               if (strlen(vlentry.name)>0) {
-                   if (fix) {
-                       if (header.VolnameHash[NameHash(vlentry.name)] == 0)
-                           header.VolnameHash[NameHash(vlentry.name)] = record[i].addr;
-                       else
-                           FixBad(i, header.VolnameHash[NameHash(vlentry.name)], NH, record[i].addr, &vlentry, NameHash(vlentry.name));
-                   }
-               } else {
-                   nextpp = &vlentry.nextNameHash;
-                   if (fix && *nextpp) {
-                       printf(", unchaining");
-                       *nextpp = 0;
-                       writeentry(record[i].addr, &vlentry);
-                   }
-               }
            }
            if (vlentry.volumeId[0] && !(record[i].type & REFRW)) {
                log_error(VLDB_CHECK_ERROR,"%d: Record %ld (type 0x%x) not in a RW chain\n", i,
                       record[i].addr, record[i].type);
-               if (fix) {
-                   if (header.VolidHash[0][IdHash(vlentry.volumeId[0])] == 0)
-                       header.VolidHash[0][IdHash(vlentry.volumeId[0])] = record[i].addr;
-                   else
-                       FixBad(i, header.VolidHash[0][IdHash(vlentry.volumeId[0])], RWH, record[i].addr, &vlentry, IdHash(vlentry.volumeId[0]));
-               }
            }
            if (vlentry.volumeId[1] && !(record[i].type & REFRO)) {
                log_error(VLDB_CHECK_ERROR,"%d: Record %ld (type 0x%x) not in a RO chain\n", i, 
                       record[i].addr, record[i].type);
-               if (fix) {
-                   if (header.VolidHash[1][IdHash(vlentry.volumeId[1])] == 0)
-                       header.VolidHash[1][IdHash(vlentry.volumeId[1])] = record[i].addr;
-                   else
-                       FixBad(i, header.VolidHash[1][IdHash(vlentry.volumeId[1])], ROH, record[i].addr, &vlentry, IdHash(vlentry.volumeId[1]));
-               }
            }
            if (vlentry.volumeId[2] && !(record[i].type & REFBK)) {
                log_error(VLDB_CHECK_ERROR,"%d: Record %ld (type 0x%x) not in a BK chain\n", i, 
                       record[i].addr, record[i].type);
-               if (fix) {
-                   if (header.VolidHash[2][IdHash(vlentry.volumeId[2])] == 0)
-                       header.VolidHash[2][IdHash(vlentry.volumeId[2])] = record[i].addr;
-                   else
-                       FixBad(i, header.VolidHash[2][IdHash(vlentry.volumeId[2])], BKH, record[i].addr, &vlentry, IdHash(vlentry.volumeId[2]));
+           }
+           if (fix) {
+               afs_uint32 oldhash, newhash;
+               char oldNameBuffer[10 + VL_MAXNAMELEN];
+               char newNameBuffer[10 + VL_MAXNAMELEN];
+               char *oldname, *newname;
+
+               /*
+                * Put the current hash table contexts into our 'next'
+                * and our address into the hash table.
+                */
+               hash = NameHash(vlentry.name);
+
+               if (vlentry.nextNameHash != header.VolnameHash[hash]) {
+                   oldname = nameForAddr(vlentry.nextNameHash, MAXTYPES, &oldhash, oldNameBuffer);
+                   newname = nameForAddr(header.VolnameHash[hash], MAXTYPES, &newhash, newNameBuffer);
+                   if (verbose || ((oldhash != newhash) &&
+                                    (0 != vlentry.nextNameHash) &&
+                                    (0 != header.VolnameHash[hash]))) {
+                       /*
+                        * That is, only report if we are verbose
+                        * or the hash is changing (and one side wasn't NULL
+                        */
+                       quiet_println("FIX: Name hash link for '%s' was %s, is now %s\n",
+                              vlentry.name, oldname, newname);
+                   }
                }
 
+               vlentry.nextNameHash = header.VolnameHash[hash];
+               header.VolnameHash[hash] = record[i].addr;
+
+               for (j = 0; j < MAXTYPES; j++) {
+
+                   if (0 == vlentry.volumeId[j]) {
+                       /*
+                        * No volume of that type.  Continue
+                        */
+                       continue;
+                   }
+                   hash = IdHash(vlentry.volumeId[j]);
+
+                   if (vlentry.nextIdHash[j] != header.VolidHash[j][hash]) {
+                       oldname = nameForAddr(vlentry.nextIdHash[j], j, &oldhash, oldNameBuffer);
+                       newname = nameForAddr(header.VolidHash[j][hash], j, &newhash, newNameBuffer);
+                       if (verbose || ((oldhash != newhash) &&
+                                       (0 != vlentry.nextIdHash[j]) &&
+                                       (0 != header.VolidHash[j][hash]))) {
+                           quiet_println("FIX: %s hash link for '%s' was %s, is now %s\n",
+                                         vtype(j), vlentry.name, oldname, newname);
+                       }
+                   }
+
+                   vlentry.nextIdHash[j] = header.VolidHash[j][hash];
+                   header.VolidHash[j][hash] = record[i].addr;
+               }
+               writeentry(record[i].addr, &vlentry);
            }
        }
     }
-    if (fix) 
+    if (fix) {
+       reportHashChanges(&header, oldnamehash, oldidhash);
        writeheader(&header);
+    }
 
     close(fd);
 
-    if (fixed) {
-      fixed=0;
-      passes++;
-      if (passes < 20)
-       goto restart;
-      else
-       return 1;
-    }
     return error_level;
 }