34c80811c94f64f0f6bf0201c9b5c6d39d014877
   1#include "cache.h"
   2
   3#include <sys/types.h>
   4#include <dirent.h>
   5
   6/*
   7 * The low 16 bits of the "flags" field shows whether
   8 * a commit is part of the path to the root for that
   9 * parent.
  10 *
  11 * Bit 16 is an internal flag that we've seen the
  12 * definition for this rev, and not just seen it as
  13 * a parent target.
  14 */
  15#define MAX_COMMITS (16)
  16#define marked(rev)     ((rev)->flags & 0xffff)
  17#define SEEN 0x10000
  18#define USED 0x20000
  19#define REACHABLE 0x40000
  20
  21static int show_unreachable = 0;
  22static int head_supplied = 0;
  23static unsigned char head_sha1[20];
  24
  25struct parent {
  26        struct revision *parent;
  27        struct parent *next;
  28};
  29
  30struct revision {
  31        unsigned int flags;
  32        unsigned char sha1[20];
  33        unsigned long date;
  34        struct parent *parent;
  35};
  36
  37static struct revision **revs;
  38static int nr_revs, rev_allocs;
  39
  40static int find_rev(unsigned char *sha1)
  41{
  42        int first = 0, last = nr_revs;
  43
  44        while (first < last) {
  45                int next = (first + last) / 2;
  46                struct revision *rev = revs[next];
  47                int cmp;
  48
  49                cmp = memcmp(sha1, rev->sha1, 20);
  50                if (!cmp)
  51                        return next;
  52                if (cmp < 0) {
  53                        last = next;
  54                        continue;
  55                }
  56                first = next+1;
  57        }
  58        return -first-1;
  59}
  60
  61static struct revision *lookup_rev(unsigned char *sha1)
  62{
  63        int pos = find_rev(sha1);
  64        struct revision *n;
  65
  66        if (pos >= 0)
  67                return revs[pos];
  68        
  69        pos = -pos-1;
  70
  71        if (rev_allocs == nr_revs) {
  72                rev_allocs = alloc_nr(rev_allocs);
  73                revs = realloc(revs, rev_allocs * sizeof(struct revision *));
  74        }
  75        n = malloc(sizeof(struct revision));
  76
  77        n->flags = 0;
  78        memcpy(n->sha1, sha1, 20);
  79        n->parent = NULL;
  80
  81        /* Insert it into the right place */
  82        memmove(revs + pos + 1, revs + pos, (nr_revs - pos) * sizeof(struct revision *));
  83        revs[pos] = n;
  84        nr_revs++;
  85
  86        return n;
  87}
  88
  89static struct revision *add_relationship(struct revision *rev, unsigned char *needs)
  90{
  91        struct revision *parent_rev = lookup_rev(needs);
  92        struct parent **pp = &rev->parent, *p;
  93
  94        while ((p = *pp) != NULL) {
  95                if (p->parent == parent_rev)
  96                        return parent_rev;
  97                pp = &p->next;
  98        }
  99
 100        p = malloc(sizeof(*p));
 101        p->parent = parent_rev;
 102        p->next = NULL;
 103        *pp = p;
 104        return parent_rev;
 105}
 106
 107static void mark_reachable(struct revision *rev)
 108{
 109        struct parent *p = rev->parent;
 110
 111        /* If we've been here already, don't bother */
 112        if (rev->flags & REACHABLE)
 113                return;
 114        rev->flags |= REACHABLE | USED;
 115        while (p) {
 116                mark_reachable(p->parent);
 117                p = p->next;
 118        }
 119}
 120
 121static void check_connectivity(void)
 122{
 123        int i;
 124
 125        if (head_supplied)
 126                mark_reachable(lookup_rev(head_sha1));
 127
 128        /* Look up all the requirements, warn about missing objects.. */
 129        for (i = 0; i < nr_revs; i++) {
 130                struct revision *rev = revs[i];
 131
 132                if (show_unreachable && !(rev->flags & REACHABLE)) {
 133                        printf("unreachable %s\n", sha1_to_hex(rev->sha1));
 134                        continue;
 135                }
 136
 137                switch (rev->flags & (SEEN | USED)) {
 138                case 0:
 139                        printf("bad %s\n", sha1_to_hex(rev->sha1));
 140                        break;
 141                case USED:
 142                        printf("missing %s\n", sha1_to_hex(rev->sha1));
 143                        break;
 144                case SEEN:
 145                        printf("dangling %s\n", sha1_to_hex(rev->sha1));
 146                        break;
 147                }
 148        }
 149}
 150
 151static void mark_needs_sha1(unsigned char *parent, const char * tag, unsigned char *child)
 152{
 153        struct revision * child_rev = add_relationship(lookup_rev(parent), child);
 154        child_rev->flags |= USED;
 155}
 156
 157static int mark_sha1_seen(unsigned char *sha1, char *tag)
 158{
 159        struct revision *rev = lookup_rev(sha1);
 160
 161        rev->flags |= SEEN;
 162        return 0;
 163}
 164
 165static int fsck_tree(unsigned char *sha1, void *data, unsigned long size)
 166{
 167        int warn_old_tree = 1;
 168
 169        while (size) {
 170                int len = 1+strlen(data);
 171                unsigned char *file_sha1 = data + len;
 172                char *path = strchr(data, ' ');
 173                unsigned int mode;
 174                if (size < len + 20 || !path || sscanf(data, "%o", &mode) != 1)
 175                        return -1;
 176
 177                /* Warn about trees that don't do the recursive thing.. */
 178                if (warn_old_tree && strchr(path, '/')) {
 179                        fprintf(stderr, "warning: fsck-cache: tree %s has full pathnames in it\n", sha1_to_hex(sha1));
 180                        warn_old_tree = 0;
 181                }
 182
 183                data += len + 20;
 184                size -= len + 20;
 185                mark_needs_sha1(sha1, S_ISDIR(mode) ? "tree" : "blob", file_sha1);
 186        }
 187        return 0;
 188}
 189
 190static int fsck_commit(unsigned char *sha1, void *data, unsigned long size)
 191{
 192        int parents;
 193        unsigned char tree_sha1[20];
 194        unsigned char parent_sha1[20];
 195
 196        if (memcmp(data, "tree ", 5))
 197                return -1;
 198        if (get_sha1_hex(data + 5, tree_sha1) < 0)
 199                return -1;
 200        mark_needs_sha1(sha1, "tree", tree_sha1);
 201        data += 5 + 40 + 1;     /* "tree " + <hex sha1> + '\n' */
 202        parents = 0;
 203        while (!memcmp(data, "parent ", 7)) {
 204                if (get_sha1_hex(data + 7, parent_sha1) < 0)
 205                        return -1;
 206                mark_needs_sha1(sha1, "commit", parent_sha1);
 207                data += 7 + 40 + 1;     /* "parent " + <hex sha1> + '\n' */
 208                parents++;
 209        }
 210        if (!parents)
 211                printf("root %s\n", sha1_to_hex(sha1));
 212        return 0;
 213}
 214
 215static int fsck_entry(unsigned char *sha1, char *tag, void *data, unsigned long size)
 216{
 217        if (!strcmp(tag, "blob")) {
 218                /* Nothing to check */;
 219        } else if (!strcmp(tag, "tree")) {
 220                if (fsck_tree(sha1, data, size) < 0)
 221                        return -1;
 222        } else if (!strcmp(tag, "commit")) {
 223                if (fsck_commit(sha1, data, size) < 0)
 224                        return -1;
 225        } else
 226                return -1;
 227        return mark_sha1_seen(sha1, tag);
 228}
 229
 230static int fsck_name(char *hex)
 231{
 232        unsigned char sha1[20];
 233        if (!get_sha1_hex(hex, sha1)) {
 234                unsigned long mapsize;
 235                void *map = map_sha1_file(sha1, &mapsize);
 236                if (map) {
 237                        char type[100];
 238                        unsigned long size;
 239                        void *buffer = NULL;
 240                        if (!check_sha1_signature(sha1, map, mapsize))
 241                                buffer = unpack_sha1_file(map, mapsize, type, &size);
 242                        munmap(map, mapsize);
 243                        if (buffer && !fsck_entry(sha1, type, buffer, size))
 244                                return 0;
 245                }
 246        }
 247        return -1;
 248}
 249
 250static int fsck_dir(int i, char *path)
 251{
 252        DIR *dir = opendir(path);
 253        struct dirent *de;
 254
 255        if (!dir) {
 256                return error("missing sha1 directory '%s'", path);
 257        }
 258
 259        while ((de = readdir(dir)) != NULL) {
 260                char name[100];
 261                int len = strlen(de->d_name);
 262
 263                switch (len) {
 264                case 2:
 265                        if (de->d_name[1] != '.')
 266                                break;
 267                case 1:
 268                        if (de->d_name[0] != '.')
 269                                break;
 270                        continue;
 271                case 38:
 272                        sprintf(name, "%02x", i);
 273                        memcpy(name+2, de->d_name, len+1);
 274                        if (!fsck_name(name))
 275                                continue;
 276                }
 277                fprintf(stderr, "bad sha1 file: %s/%s\n", path, de->d_name);
 278        }
 279        closedir(dir);
 280        return 0;
 281}
 282
 283int main(int argc, char **argv)
 284{
 285        int i;
 286        char *sha1_dir;
 287
 288        for (i = 1; i < argc; i++) {
 289                if (!strcmp(argv[i], "--unreachable")) {
 290                        show_unreachable = 1;
 291                        continue;
 292                }
 293                if (!get_sha1_hex(argv[i], head_sha1)) {
 294                        head_supplied = 1;
 295                        continue;
 296                }
 297                usage("fsck-cache [[--unreachable] <head-sha1>]");
 298        }
 299        if (show_unreachable && !head_supplied)
 300                usage("unable to do reachability checks without a head");
 301
 302        sha1_dir = getenv(DB_ENVIRONMENT) ? : DEFAULT_DB_ENVIRONMENT;
 303        for (i = 0; i < 256; i++) {
 304                static char dir[4096];
 305                sprintf(dir, "%s/%02x", sha1_dir, i);
 306                fsck_dir(i, dir);
 307        }
 308        check_connectivity();
 309        return 0;
 310}