7 * The low 16 bits of the "flags" field shows whether
8 * a commit is part of the path to the root for that
11 * Bit 16 is an internal flag that we've seen the
12 * definition for this rev, and not just seen it as
15 #define MAX_COMMITS (16)
16 #define marked(rev) ((rev)->flags & 0xffff)
19 #define REACHABLE 0x40000
21 static int show_unreachable
= 0;
22 static int head_supplied
= 0;
23 static unsigned char head_sha1
[20];
26 struct revision
*parent
;
32 unsigned char sha1
[20];
34 struct parent
*parent
;
37 static struct revision
**revs
;
38 static int nr_revs
, rev_allocs
;
40 static int find_rev(unsigned char *sha1
)
42 int first
= 0, last
= nr_revs
;
44 while (first
< last
) {
45 int next
= (first
+ last
) / 2;
46 struct revision
*rev
= revs
[next
];
49 cmp
= memcmp(sha1
, rev
->sha1
, 20);
61 static struct revision
*lookup_rev(unsigned char *sha1
)
63 int pos
= find_rev(sha1
);
71 if (rev_allocs
== nr_revs
) {
72 rev_allocs
= alloc_nr(rev_allocs
);
73 revs
= realloc(revs
, rev_allocs
* sizeof(struct revision
*));
75 n
= malloc(sizeof(struct revision
));
78 memcpy(n
->sha1
, sha1
, 20);
81 /* Insert it into the right place */
82 memmove(revs
+ pos
+ 1, revs
+ pos
, (nr_revs
- pos
) * sizeof(struct revision
*));
89 static struct revision
*add_relationship(struct revision
*rev
, unsigned char *needs
)
91 struct revision
*parent_rev
= lookup_rev(needs
);
92 struct parent
**pp
= &rev
->parent
, *p
;
94 while ((p
= *pp
) != NULL
) {
95 if (p
->parent
== parent_rev
)
100 p
= malloc(sizeof(*p
));
101 p
->parent
= parent_rev
;
107 static void mark_reachable(struct revision
*rev
)
109 struct parent
*p
= rev
->parent
;
111 /* If we've been here already, don't bother */
112 if (rev
->flags
& REACHABLE
)
114 rev
->flags
|= REACHABLE
| USED
;
116 mark_reachable(p
->parent
);
121 static void check_connectivity(void)
126 mark_reachable(lookup_rev(head_sha1
));
128 /* Look up all the requirements, warn about missing objects.. */
129 for (i
= 0; i
< nr_revs
; i
++) {
130 struct revision
*rev
= revs
[i
];
132 if (show_unreachable
&& !(rev
->flags
& REACHABLE
)) {
133 printf("unreachable %s\n", sha1_to_hex(rev
->sha1
));
137 switch (rev
->flags
& (SEEN
| USED
)) {
139 printf("bad %s\n", sha1_to_hex(rev
->sha1
));
142 printf("missing %s\n", sha1_to_hex(rev
->sha1
));
145 printf("dangling %s\n", sha1_to_hex(rev
->sha1
));
151 static void mark_needs_sha1(unsigned char *parent
, const char * tag
, unsigned char *child
)
153 struct revision
* child_rev
= add_relationship(lookup_rev(parent
), child
);
154 child_rev
->flags
|= USED
;
157 static int mark_sha1_seen(unsigned char *sha1
, char *tag
)
159 struct revision
*rev
= lookup_rev(sha1
);
165 static int fsck_tree(unsigned char *sha1
, void *data
, unsigned long size
)
167 int warn_old_tree
= 1;
170 int len
= 1+strlen(data
);
171 unsigned char *file_sha1
= data
+ len
;
172 char *path
= strchr(data
, ' ');
174 if (size
< len
+ 20 || !path
|| sscanf(data
, "%o", &mode
) != 1)
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
));
185 mark_needs_sha1(sha1
, S_ISDIR(mode
) ? "tree" : "blob", file_sha1
);
190 static int fsck_commit(unsigned char *sha1
, void *data
, unsigned long size
)
193 unsigned char tree_sha1
[20];
194 unsigned char parent_sha1
[20];
196 if (memcmp(data
, "tree ", 5))
198 if (get_sha1_hex(data
+ 5, tree_sha1
) < 0)
200 mark_needs_sha1(sha1
, "tree", tree_sha1
);
201 data
+= 5 + 40 + 1; /* "tree " + <hex sha1> + '\n' */
203 while (!memcmp(data
, "parent ", 7)) {
204 if (get_sha1_hex(data
+ 7, parent_sha1
) < 0)
206 mark_needs_sha1(sha1
, "commit", parent_sha1
);
207 data
+= 7 + 40 + 1; /* "parent " + <hex sha1> + '\n' */
211 printf("root %s\n", sha1_to_hex(sha1
));
215 static int fsck_entry(unsigned char *sha1
, char *tag
, void *data
, unsigned long size
)
217 if (!strcmp(tag
, "blob")) {
218 /* Nothing to check */;
219 } else if (!strcmp(tag
, "tree")) {
220 if (fsck_tree(sha1
, data
, size
) < 0)
222 } else if (!strcmp(tag
, "commit")) {
223 if (fsck_commit(sha1
, data
, size
) < 0)
227 return mark_sha1_seen(sha1
, tag
);
230 static int fsck_name(char *hex
)
232 unsigned char sha1
[20];
233 if (!get_sha1_hex(hex
, sha1
)) {
234 unsigned long mapsize
;
235 void *map
= map_sha1_file(sha1
, &mapsize
);
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
))
250 static int fsck_dir(int i
, char *path
)
252 DIR *dir
= opendir(path
);
256 return error("missing sha1 directory '%s'", path
);
259 while ((de
= readdir(dir
)) != NULL
) {
261 int len
= strlen(de
->d_name
);
265 if (de
->d_name
[1] != '.')
268 if (de
->d_name
[0] != '.')
272 sprintf(name
, "%02x", i
);
273 memcpy(name
+2, de
->d_name
, len
+1);
274 if (!fsck_name(name
))
277 fprintf(stderr
, "bad sha1 file: %s/%s\n", path
, de
->d_name
);
283 int main(int argc
, char **argv
)
288 for (i
= 1; i
< argc
; i
++) {
289 if (!strcmp(argv
[i
], "--unreachable")) {
290 show_unreachable
= 1;
293 if (!get_sha1_hex(argv
[i
], head_sha1
)) {
297 usage("fsck-cache [[--unreachable] <head-sha1>]");
299 if (show_unreachable
&& !head_supplied
)
300 usage("unable to do reachability checks without a head");
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
);
308 check_connectivity();