Andrew's git - gitweb.git/blob

   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        rev->flags |= REACHABLE | USED;
 112        while (p) {
 113                mark_reachable(p->parent);
 114                p = p->next;
 115        }
 116}
 117
 118static void check_connectivity(void)
 119{
 120        int i;
 121
 122        if (head_supplied)
 123                mark_reachable(lookup_rev(head_sha1));
 124
 125        /* Look up all the requirements, warn about missing objects.. */
 126        for (i = 0; i < nr_revs; i++) {
 127                struct revision *rev = revs[i];
 128
 129                if (show_unreachable && !(rev->flags & REACHABLE)) {
 130                        printf("unreachable %s\n", sha1_to_hex(rev->sha1));
 131                        continue;
 132                }
 133
 134                switch (rev->flags & (SEEN | USED)) {
 135                case 0:
 136                        printf("bad %s\n", sha1_to_hex(rev->sha1));
 137                        break;
 138                case USED:
 139                        printf("missing %s\n", sha1_to_hex(rev->sha1));
 140                        break;
 141                case SEEN:
 142                        printf("dangling %s\n", sha1_to_hex(rev->sha1));
 143                        break;
 144                }
 145        }
 146}
 147
 148static void mark_needs_sha1(unsigned char *parent, const char * tag, unsigned char *child)
 149{
 150        struct revision * child_rev = add_relationship(lookup_rev(parent), child);
 151        child_rev->flags |= USED;
 152}
 153
 154static int mark_sha1_seen(unsigned char *sha1, char *tag)
 155{
 156        struct revision *rev = lookup_rev(sha1);
 157
 158        rev->flags |= SEEN;
 159        return 0;
 160}
 161
 162static int fsck_tree(unsigned char *sha1, void *data, unsigned long size)
 163{
 164        int warn_old_tree = 1;
 165
 166        while (size) {
 167                int len = 1+strlen(data);
 168                unsigned char *file_sha1 = data + len;
 169                char *path = strchr(data, ' ');
 170                unsigned int mode;
 171                if (size < len + 20 || !path || sscanf(data, "%o", &mode) != 1)
 172                        return -1;
 173
 174                /* Warn about trees that don't do the recursive thing.. */
 175                if (warn_old_tree && strchr(path, '/')) {
 176                        fprintf(stderr, "warning: fsck-cache: tree %s has full pathnames in it\n", sha1_to_hex(sha1));
 177                        warn_old_tree = 0;
 178                }
 179
 180                data += len + 20;
 181                size -= len + 20;
 182                mark_needs_sha1(sha1, S_ISDIR(mode) ? "tree" : "blob", file_sha1);
 183        }
 184        return 0;
 185}
 186
 187static int fsck_commit(unsigned char *sha1, void *data, unsigned long size)
 188{
 189        int parents;
 190        unsigned char tree_sha1[20];
 191        unsigned char parent_sha1[20];
 192
 193        if (memcmp(data, "tree ", 5))
 194                return -1;
 195        if (get_sha1_hex(data + 5, tree_sha1) < 0)
 196                return -1;
 197        mark_needs_sha1(sha1, "tree", tree_sha1);
 198        data += 5 + 40 + 1;     /* "tree " + <hex sha1> + '\n' */
 199        parents = 0;
 200        while (!memcmp(data, "parent ", 7)) {
 201                if (get_sha1_hex(data + 7, parent_sha1) < 0)
 202                        return -1;
 203                mark_needs_sha1(sha1, "commit", parent_sha1);
 204                data += 7 + 40 + 1;     /* "parent " + <hex sha1> + '\n' */
 205                parents++;
 206        }
 207        if (!parents)
 208                printf("root %s\n", sha1_to_hex(sha1));
 209        return 0;
 210}
 211
 212static int fsck_entry(unsigned char *sha1, char *tag, void *data, unsigned long size)
 213{
 214        if (!strcmp(tag, "blob")) {
 215                /* Nothing to check */;
 216        } else if (!strcmp(tag, "tree")) {
 217                if (fsck_tree(sha1, data, size) < 0)
 218                        return -1;
 219        } else if (!strcmp(tag, "commit")) {
 220                if (fsck_commit(sha1, data, size) < 0)
 221                        return -1;
 222        } else
 223                return -1;
 224        return mark_sha1_seen(sha1, tag);
 225}
 226
 227static int fsck_name(char *hex)
 228{
 229        unsigned char sha1[20];
 230        if (!get_sha1_hex(hex, sha1)) {
 231                unsigned long mapsize;
 232                void *map = map_sha1_file(sha1, &mapsize);
 233                if (map) {
 234                        char type[100];
 235                        unsigned long size;
 236                        void *buffer = NULL;
 237                        if (!check_sha1_signature(sha1, map, mapsize))
 238                                buffer = unpack_sha1_file(map, mapsize, type, &size);
 239                        munmap(map, mapsize);
 240                        if (buffer && !fsck_entry(sha1, type, buffer, size))
 241                                return 0;
 242                }
 243        }
 244        return -1;
 245}
 246
 247static int fsck_dir(int i, char *path)
 248{
 249        DIR *dir = opendir(path);
 250        struct dirent *de;
 251
 252        if (!dir) {
 253                return error("missing sha1 directory '%s'", path);
 254        }
 255
 256        while ((de = readdir(dir)) != NULL) {
 257                char name[100];
 258                int len = strlen(de->d_name);
 259
 260                switch (len) {
 261                case 2:
 262                        if (de->d_name[1] != '.')
 263                                break;
 264                case 1:
 265                        if (de->d_name[0] != '.')
 266                                break;
 267                        continue;
 268                case 38:
 269                        sprintf(name, "%02x", i);
 270                        memcpy(name+2, de->d_name, len+1);
 271                        if (!fsck_name(name))
 272                                continue;
 273                }
 274                fprintf(stderr, "bad sha1 file: %s/%s\n", path, de->d_name);
 275        }
 276        closedir(dir);
 277        return 0;
 278}
 279
 280int main(int argc, char **argv)
 281{
 282        int i;
 283        char *sha1_dir;
 284
 285        for (i = 1; i < argc; i++) {
 286                if (!strcmp(argv[i], "--unreachable")) {
 287                        show_unreachable = 1;
 288                        continue;
 289                }
 290                if (!get_sha1_hex(argv[i], head_sha1)) {
 291                        head_supplied = 1;
 292                        continue;
 293                }
 294                usage("fsck-cache [[--unreachable] <head-sha1>]");
 295        }
 296        if (show_unreachable && !head_supplied)
 297                usage("unable to do reachability checks without a head");
 298
 299        sha1_dir = getenv(DB_ENVIRONMENT) ? : DEFAULT_DB_ENVIRONMENT;
 300        for (i = 0; i < 256; i++) {
 301                static char dir[4096];
 302                sprintf(dir, "%s/%02x", sha1_dir, i);
 303                fsck_dir(i, dir);
 304        }
 305        check_connectivity();
 306        return 0;
 307}