[thirdparty/git.git] / builtin-fsck.c

#include "builtin.h"
#include "cache.h"
#include "commit.h"
#include "tree.h"
#include "blob.h"
#include "tag.h"
#include "refs.h"
#include "pack.h"
#include "cache-tree.h"
#include "tree-walk.h"
#include "fsck.h"
#include "parse-options.h"
#include "dir.h"

#define REACHABLE 0x0001
#define SEEN      0x0002

static int show_root;
static int show_tags;
static int show_unreachable;
static int include_reflogs = 1;
static int check_full = 1;
static int check_strict;
static int keep_cache_objects;
static unsigned char head_sha1[20];
static const char *head_points_at;
static int errors_found;
static int write_lost_and_found;
static int verbose;
#define ERROR_OBJECT 01
#define ERROR_REACHABLE 02

#ifdef NO_D_INO_IN_DIRENT
#define SORT_DIRENT 0
#define DIRENT_SORT_HINT(de) 0
#else
#define SORT_DIRENT 1
#define DIRENT_SORT_HINT(de) ((de)->d_ino)
#endif

static void objreport(struct object *obj, const char *severity,
                      const char *err, va_list params)
{
	fprintf(stderr, "%s in %s %s: ",
	        severity, typename(obj->type), sha1_to_hex(obj->sha1));
	vfprintf(stderr, err, params);
	fputs("\n", stderr);
}

__attribute__((format (printf, 2, 3)))
static int objerror(struct object *obj, const char *err, ...)
{
	va_list params;
	va_start(params, err);
	errors_found |= ERROR_OBJECT;
	objreport(obj, "error", err, params);
	va_end(params);
	return -1;
}

__attribute__((format (printf, 3, 4)))
static int fsck_error_func(struct object *obj, int type, const char *err, ...)
{
	va_list params;
	va_start(params, err);
	objreport(obj, (type == FSCK_WARN) ? "warning" : "error", err, params);
	va_end(params);
	return (type == FSCK_WARN) ? 0 : 1;
}

static struct object_array pending;

static int mark_object(struct object *obj, int type, void *data)
{
	struct object *parent = data;

	if (!obj) {
		printf("broken link from %7s %s\n",
			   typename(parent->type), sha1_to_hex(parent->sha1));
		printf("broken link from %7s %s\n",
			   (type == OBJ_ANY ? "unknown" : typename(type)), "unknown");
		errors_found |= ERROR_REACHABLE;
		return 1;
	}

	if (type != OBJ_ANY && obj->type != type)
		objerror(parent, "wrong object type in link");

	if (obj->flags & REACHABLE)
		return 0;
	obj->flags |= REACHABLE;
	if (!obj->parsed) {
		if (parent && !has_sha1_file(obj->sha1)) {
			printf("broken link from %7s %s\n",
				 typename(parent->type), sha1_to_hex(parent->sha1));
			printf("              to %7s %s\n",
				 typename(obj->type), sha1_to_hex(obj->sha1));
			errors_found |= ERROR_REACHABLE;
		}
		return 1;
	}

	add_object_array(obj, (void *) parent, &pending);
	return 0;
}

static void mark_object_reachable(struct object *obj)
{
	mark_object(obj, OBJ_ANY, NULL);
}

static int traverse_one_object(struct object *obj, struct object *parent)
{
	int result;
	struct tree *tree = NULL;

	if (obj->type == OBJ_TREE) {
		obj->parsed = 0;
		tree = (struct tree *)obj;
		if (parse_tree(tree) < 0)
			return 1; /* error already displayed */
	}
	result = fsck_walk(obj, mark_object, obj);
	if (tree) {
		free(tree->buffer);
		tree->buffer = NULL;
	}
	return result;
}

static int traverse_reachable(void)
{
	int result = 0;
	while (pending.nr) {
		struct object_array_entry *entry;
		struct object *obj, *parent;

		entry = pending.objects + --pending.nr;
		obj = entry->item;
		parent = (struct object *) entry->name;
		result |= traverse_one_object(obj, parent);
	}
	return !!result;
}

static int mark_used(struct object *obj, int type, void *data)
{
	if (!obj)
		return 1;
	obj->used = 1;
	return 0;
}

/*
 * Check a single reachable object
 */
static void check_reachable_object(struct object *obj)
{
	/*
	 * We obviously want the object to be parsed,
	 * except if it was in a pack-file and we didn't
	 * do a full fsck
	 */
	if (!obj->parsed) {
		if (has_sha1_pack(obj->sha1))
			return; /* it is in pack - forget about it */
		printf("missing %s %s\n", typename(obj->type), sha1_to_hex(obj->sha1));
		errors_found |= ERROR_REACHABLE;
		return;
	}
}

/*
 * Check a single unreachable object
 */
static void check_unreachable_object(struct object *obj)
{
	/*
	 * Missing unreachable object? Ignore it. It's not like
	 * we miss it (since it can't be reached), nor do we want
	 * to complain about it being unreachable (since it does
	 * not exist).
	 */
	if (!obj->parsed)
		return;

	/*
	 * Unreachable object that exists? Show it if asked to,
	 * since this is something that is prunable.
	 */
	if (show_unreachable) {
		printf("unreachable %s %s\n", typename(obj->type), sha1_to_hex(obj->sha1));
		return;
	}

	/*
	 * "!used" means that nothing at all points to it, including
	 * other unreachable objects. In other words, it's the "tip"
	 * of some set of unreachable objects, usually a commit that
	 * got dropped.
	 *
	 * Such starting points are more interesting than some random
	 * set of unreachable objects, so we show them even if the user
	 * hasn't asked for _all_ unreachable objects. If you have
	 * deleted a branch by mistake, this is a prime candidate to
	 * start looking at, for example.
	 */
	if (!obj->used) {
		printf("dangling %s %s\n", typename(obj->type),
		       sha1_to_hex(obj->sha1));
		if (write_lost_and_found) {
			char *filename = git_path("lost-found/%s/%s",
				obj->type == OBJ_COMMIT ? "commit" : "other",
				sha1_to_hex(obj->sha1));
			FILE *f;

			if (safe_create_leading_directories(filename)) {
				error("Could not create lost-found");
				return;
			}
			if (!(f = fopen(filename, "w")))
				die_errno("Could not open '%s'", filename);
			if (obj->type == OBJ_BLOB) {
				enum object_type type;
				unsigned long size;
				char *buf = read_sha1_file(obj->sha1,
						&type, &size);
				if (buf) {
					if (fwrite(buf, size, 1, f) != 1)
						die_errno("Could not write '%s'",
							  filename);
					free(buf);
				}
			} else
				fprintf(f, "%s\n", sha1_to_hex(obj->sha1));
			if (fclose(f))
				die_errno("Could not finish '%s'",
					  filename);
		}
		return;
	}

	/*
	 * Otherwise? It's there, it's unreachable, and some other unreachable
	 * object points to it. Ignore it - it's not interesting, and we showed
	 * all the interesting cases above.
	 */
}

static void check_object(struct object *obj)
{
	if (verbose)
		fprintf(stderr, "Checking %s\n", sha1_to_hex(obj->sha1));

	if (obj->flags & REACHABLE)
		check_reachable_object(obj);
	else
		check_unreachable_object(obj);
}

static void check_connectivity(void)
{
	int i, max;

	/* Traverse the pending reachable objects */
	traverse_reachable();

	/* Look up all the requirements, warn about missing objects.. */
	max = get_max_object_index();
	if (verbose)
		fprintf(stderr, "Checking connectivity (%d objects)\n", max);

	for (i = 0; i < max; i++) {
		struct object *obj = get_indexed_object(i);

		if (obj)
			check_object(obj);
	}
}

static int fsck_sha1(const unsigned char *sha1)
{
	struct object *obj = parse_object(sha1);
	if (!obj) {
		errors_found |= ERROR_OBJECT;
		return error("%s: object corrupt or missing",
			     sha1_to_hex(sha1));
	}
	if (obj->flags & SEEN)
		return 0;
	obj->flags |= SEEN;

	if (verbose)
		fprintf(stderr, "Checking %s %s\n",
			typename(obj->type), sha1_to_hex(obj->sha1));

	if (fsck_walk(obj, mark_used, NULL))
		objerror(obj, "broken links");
	if (fsck_object(obj, check_strict, fsck_error_func))
		return -1;

	if (obj->type == OBJ_TREE) {
		struct tree *item = (struct tree *) obj;

		free(item->buffer);
		item->buffer = NULL;
	}

	if (obj->type == OBJ_COMMIT) {
		struct commit *commit = (struct commit *) obj;

		free(commit->buffer);
		commit->buffer = NULL;

		if (!commit->parents && show_root)
			printf("root %s\n", sha1_to_hex(commit->object.sha1));
	}

	if (obj->type == OBJ_TAG) {
		struct tag *tag = (struct tag *) obj;

		if (show_tags && tag->tagged) {
			printf("tagged %s %s", typename(tag->tagged->type), sha1_to_hex(tag->tagged->sha1));
			printf(" (%s) in %s\n", tag->tag, sha1_to_hex(tag->object.sha1));
		}
	}

	return 0;
}

/*
 * This is the sorting chunk size: make it reasonably
 * big so that we can sort well..
 */
#define MAX_SHA1_ENTRIES (1024)

struct sha1_entry {
	unsigned long ino;
	unsigned char sha1[20];
};

static struct {
	unsigned long nr;
	struct sha1_entry *entry[MAX_SHA1_ENTRIES];
} sha1_list;

static int ino_compare(const void *_a, const void *_b)
{
	const struct sha1_entry *a = _a, *b = _b;
	unsigned long ino1 = a->ino, ino2 = b->ino;
	return ino1 < ino2 ? -1 : ino1 > ino2 ? 1 : 0;
}

static void fsck_sha1_list(void)
{
	int i, nr = sha1_list.nr;

	if (SORT_DIRENT)
		qsort(sha1_list.entry, nr,
		      sizeof(struct sha1_entry *), ino_compare);
	for (i = 0; i < nr; i++) {
		struct sha1_entry *entry = sha1_list.entry[i];
		unsigned char *sha1 = entry->sha1;

		sha1_list.entry[i] = NULL;
		fsck_sha1(sha1);
		free(entry);
	}
	sha1_list.nr = 0;
}

static void add_sha1_list(unsigned char *sha1, unsigned long ino)
{
	struct sha1_entry *entry = xmalloc(sizeof(*entry));
	int nr;

	entry->ino = ino;
	hashcpy(entry->sha1, sha1);
	nr = sha1_list.nr;
	if (nr == MAX_SHA1_ENTRIES) {
		fsck_sha1_list();
		nr = 0;
	}
	sha1_list.entry[nr] = entry;
	sha1_list.nr = ++nr;
}

static void fsck_dir(int i, char *path)
{
	DIR *dir = opendir(path);
	struct dirent *de;

	if (!dir)
		return;

	if (verbose)
		fprintf(stderr, "Checking directory %s\n", path);

	while ((de = readdir(dir)) != NULL) {
		char name[100];
		unsigned char sha1[20];

		if (is_dot_or_dotdot(de->d_name))
			continue;
		if (strlen(de->d_name) == 38) {
			sprintf(name, "%02x", i);
			memcpy(name+2, de->d_name, 39);
			if (get_sha1_hex(name, sha1) < 0)
				break;
			add_sha1_list(sha1, DIRENT_SORT_HINT(de));
			continue;
		}
		if (!prefixcmp(de->d_name, "tmp_obj_"))
			continue;
		fprintf(stderr, "bad sha1 file: %s/%s\n", path, de->d_name);
	}
	closedir(dir);
}

static int default_refs;

static int fsck_handle_reflog_ent(unsigned char *osha1, unsigned char *nsha1,
		const char *email, unsigned long timestamp, int tz,
		const char *message, void *cb_data)
{
	struct object *obj;

	if (verbose)
		fprintf(stderr, "Checking reflog %s->%s\n",
			sha1_to_hex(osha1), sha1_to_hex(nsha1));

	if (!is_null_sha1(osha1)) {
		obj = lookup_object(osha1);
		if (obj) {
			obj->used = 1;
			mark_object_reachable(obj);
		}
	}
	obj = lookup_object(nsha1);
	if (obj) {
		obj->used = 1;
		mark_object_reachable(obj);
	}
	return 0;
}

static int fsck_handle_reflog(const char *logname, const unsigned char *sha1, int flag, void *cb_data)
{
	for_each_reflog_ent(logname, fsck_handle_reflog_ent, NULL);
	return 0;
}

static int is_branch(const char *refname)
{
	return !strcmp(refname, "HEAD") || !prefixcmp(refname, "refs/heads/");
}

static int fsck_handle_ref(const char *refname, const unsigned char *sha1, int flag, void *cb_data)
{
	struct object *obj;

	obj = parse_object(sha1);
	if (!obj) {
		error("%s: invalid sha1 pointer %s", refname, sha1_to_hex(sha1));
		/* We'll continue with the rest despite the error.. */
		return 0;
	}
	if (obj->type != OBJ_COMMIT && is_branch(refname))
		error("%s: not a commit", refname);
	default_refs++;
	obj->used = 1;
	mark_object_reachable(obj);

	return 0;
}

static void get_default_heads(void)
{
	if (head_points_at && !is_null_sha1(head_sha1))
		fsck_handle_ref("HEAD", head_sha1, 0, NULL);
	for_each_ref(fsck_handle_ref, NULL);
	if (include_reflogs)
		for_each_reflog(fsck_handle_reflog, NULL);

	/*
	 * Not having any default heads isn't really fatal, but
	 * it does mean that "--unreachable" no longer makes any
	 * sense (since in this case everything will obviously
	 * be unreachable by definition.
	 *
	 * Showing dangling objects is valid, though (as those
	 * dangling objects are likely lost heads).
	 *
	 * So we just print a warning about it, and clear the
	 * "show_unreachable" flag.
	 */
	if (!default_refs) {
		fprintf(stderr, "notice: No default references\n");
		show_unreachable = 0;
	}
}

static void fsck_object_dir(const char *path)
{
	int i;

	if (verbose)
		fprintf(stderr, "Checking object directory\n");

	for (i = 0; i < 256; i++) {
		static char dir[4096];
		sprintf(dir, "%s/%02x", path, i);
		fsck_dir(i, dir);
	}
	fsck_sha1_list();
}

static int fsck_head_link(void)
{
	int flag;
	int null_is_error = 0;

	if (verbose)
		fprintf(stderr, "Checking HEAD link\n");

	head_points_at = resolve_ref("HEAD", head_sha1, 0, &flag);
	if (!head_points_at)
		return error("Invalid HEAD");
	if (!strcmp(head_points_at, "HEAD"))
		/* detached HEAD */
		null_is_error = 1;
	else if (prefixcmp(head_points_at, "refs/heads/"))
		return error("HEAD points to something strange (%s)",
			     head_points_at);
	if (is_null_sha1(head_sha1)) {
		if (null_is_error)
			return error("HEAD: detached HEAD points at nothing");
		fprintf(stderr, "notice: HEAD points to an unborn branch (%s)\n",
			head_points_at + 11);
	}
	return 0;
}

static int fsck_cache_tree(struct cache_tree *it)
{
	int i;
	int err = 0;

	if (verbose)
		fprintf(stderr, "Checking cache tree\n");

	if (0 <= it->entry_count) {
		struct object *obj = parse_object(it->sha1);
		if (!obj) {
			error("%s: invalid sha1 pointer in cache-tree",
			      sha1_to_hex(it->sha1));
			return 1;
		}
		mark_object_reachable(obj);
		obj->used = 1;
		if (obj->type != OBJ_TREE)
			err |= objerror(obj, "non-tree in cache-tree");
	}
	for (i = 0; i < it->subtree_nr; i++)
		err |= fsck_cache_tree(it->down[i]->cache_tree);
	return err;
}

static char const * const fsck_usage[] = {
	"git fsck [options] [<object>...]",
	NULL
};

static struct option fsck_opts[] = {
	OPT__VERBOSE(&verbose),
	OPT_BOOLEAN(0, "unreachable", &show_unreachable, "show unreachable objects"),
	OPT_BOOLEAN(0, "tags", &show_tags, "report tags"),
	OPT_BOOLEAN(0, "root", &show_root, "report root nodes"),
	OPT_BOOLEAN(0, "cache", &keep_cache_objects, "make index objects head nodes"),
	OPT_BOOLEAN(0, "reflogs", &include_reflogs, "make reflogs head nodes (default)"),
	OPT_BOOLEAN(0, "full", &check_full, "also consider packs and alternate objects"),
	OPT_BOOLEAN(0, "strict", &check_strict, "enable more strict checking"),
	OPT_BOOLEAN(0, "lost-found", &write_lost_and_found,
				"write dangling objects in .git/lost-found"),
	OPT_END(),
};

int cmd_fsck(int argc, const char **argv, const char *prefix)
{
	int i, heads;
	struct alternate_object_database *alt;

	errors_found = 0;
	read_replace_refs = 0;

	argc = parse_options(argc, argv, prefix, fsck_opts, fsck_usage, 0);
	if (write_lost_and_found) {
		check_full = 1;
		include_reflogs = 0;
	}

	fsck_head_link();
	fsck_object_dir(get_object_directory());

	prepare_alt_odb();
	for (alt = alt_odb_list; alt; alt = alt->next) {
		char namebuf[PATH_MAX];
		int namelen = alt->name - alt->base;
		memcpy(namebuf, alt->base, namelen);
		namebuf[namelen - 1] = 0;
		fsck_object_dir(namebuf);
	}

	if (check_full) {
		struct packed_git *p;

		prepare_packed_git();
		for (p = packed_git; p; p = p->next)
			/* verify gives error messages itself */
			verify_pack(p);

		for (p = packed_git; p; p = p->next) {
			uint32_t j, num;
			if (open_pack_index(p))
				continue;
			num = p->num_objects;
			for (j = 0; j < num; j++)
				fsck_sha1(nth_packed_object_sha1(p, j));
		}
	}

	heads = 0;
	for (i = 0; i < argc; i++) {
		const char *arg = argv[i];
		unsigned char sha1[20];
		if (!get_sha1(arg, sha1)) {
			struct object *obj = lookup_object(sha1);

			/* Error is printed by lookup_object(). */
			if (!obj)
				continue;

			obj->used = 1;
			mark_object_reachable(obj);
			heads++;
			continue;
		}
		error("invalid parameter: expected sha1, got '%s'", arg);
	}

	/*
	 * If we've not been given any explicit head information, do the
	 * default ones from .git/refs. We also consider the index file
	 * in this case (ie this implies --cache).
	 */
	if (!heads) {
		get_default_heads();
		keep_cache_objects = 1;
	}

	if (keep_cache_objects) {
		read_cache();
		for (i = 0; i < active_nr; i++) {
			unsigned int mode;
			struct blob *blob;
			struct object *obj;

			mode = active_cache[i]->ce_mode;
			if (S_ISGITLINK(mode))
				continue;
			blob = lookup_blob(active_cache[i]->sha1);
			if (!blob)
				continue;
			obj = &blob->object;
			obj->used = 1;
			mark_object_reachable(obj);
		}
		if (active_cache_tree)
			fsck_cache_tree(active_cache_tree);
	}

	check_connectivity();
	return errors_found;
}
Commit	Line	Data
baffc0e7	1	#include "builtin.h"
4b182421	2	#include "cache.h"
ff5ebe39 DB	3	#include "commit.h"
	4	#include "tree.h"
	5	#include "blob.h"
c418eda4	6	#include "tag.h"
944d8589	7	#include "refs.h"
f9253394	8	#include "pack.h"
53dc3f3e	9	#include "cache-tree.h"
e9a95bef	10	#include "tree-walk.h"
271b8d25	11	#include "fsck.h"
5ac0a206	12	#include "parse-options.h"
8ca12c0d	13	#include "dir.h"
ff5ebe39 DB	14
ff5ebe39 DB	15	#define REACHABLE 0x0001
2d9c58c6	16	#define SEEN 0x0002
d9839e03	17
96f1e58f DR	18	static int show_root;
	19	static int show_tags;
	20	static int show_unreachable;
566842f6	21	static int include_reflogs = 1;
f29cd393	22	static int check_full = 1;
96f1e58f DR	23	static int check_strict;
96f1e58f DR	24	static int keep_cache_objects;
d9839e03	25	static unsigned char head_sha1[20];
469e2ebf	26	static const char *head_points_at;
e2b4f635	27	static int errors_found;
68f6c019	28	static int write_lost_and_found;
20f1eb6b	29	static int verbose;
e2b4f635 JH	30	#define ERROR_OBJECT 01
e2b4f635 JH	31	#define ERROR_REACHABLE 02
d9839e03	32
962554c6	33	#ifdef NO_D_INO_IN_DIRENT
35a730f0 JH	34	#define SORT_DIRENT 0
	35	#define DIRENT_SORT_HINT(de) 0
	36	#else
	37	#define SORT_DIRENT 1
	38	#define DIRENT_SORT_HINT(de) ((de)->d_ino)
	39	#endif
f1f0d088 PB	40
	41	static void objreport(struct object obj, const char severity,
	42	const char *err, va_list params)
	43	{
	44	fprintf(stderr, "%s in %s %s: ",
885a86ab	45	severity, typename(obj->type), sha1_to_hex(obj->sha1));
f1f0d088 PB	46	vfprintf(stderr, err, params);
	47	fputs("\n", stderr);
	48	}
	49
28bea9e5	50	__attribute__((format (printf, 2, 3)))
a7928f8e	51	static int objerror(struct object obj, const char err, ...)
f1f0d088 PB	52	{
	53	va_list params;
	54	va_start(params, err);
e2b4f635	55	errors_found \|= ERROR_OBJECT;
f1f0d088 PB	56	objreport(obj, "error", err, params);
	57	va_end(params);
	58	return -1;
	59	}
	60
28bea9e5	61	__attribute__((format (printf, 3, 4)))
ba002f3b	62	static int fsck_error_func(struct object obj, int type, const char err, ...)
f1f0d088 PB	63	{
	64	va_list params;
	65	va_start(params, err);
ba002f3b	66	objreport(obj, (type == FSCK_WARN) ? "warning" : "error", err, params);
f1f0d088	67	va_end(params);
ba002f3b	68	return (type == FSCK_WARN) ? 0 : 1;
f1f0d088 PB	69	}
f1f0d088 PB	70
04d39759 LT	71	static struct object_array pending;
04d39759 LT	72
271b8d25 MK	73	static int mark_object(struct object obj, int type, void data)
271b8d25 MK	74	{
271b8d25	75	struct object *parent = data;
271b8d25 MK	76
	77	if (!obj) {
	78	printf("broken link from %7s %s\n",
	79	typename(parent->type), sha1_to_hex(parent->sha1));
	80	printf("broken link from %7s %s\n",
	81	(type == OBJ_ANY ? "unknown" : typename(type)), "unknown");
	82	errors_found \|= ERROR_REACHABLE;
	83	return 1;
	84	}
	85
	86	if (type != OBJ_ANY && obj->type != type)
	87	objerror(parent, "wrong object type in link");
	88
	89	if (obj->flags & REACHABLE)
	90	return 0;
	91	obj->flags \|= REACHABLE;
	92	if (!obj->parsed) {
	93	if (parent && !has_sha1_file(obj->sha1)) {
	94	printf("broken link from %7s %s\n",
	95	typename(parent->type), sha1_to_hex(parent->sha1));
	96	printf(" to %7s %s\n",
	97	typename(obj->type), sha1_to_hex(obj->sha1));
	98	errors_found \|= ERROR_REACHABLE;
	99	}
	100	return 1;
	101	}
	102
04d39759 LT	103	add_object_array(obj, (void *) parent, &pending);
	104	return 0;
	105	}
	106
	107	static void mark_object_reachable(struct object *obj)
	108	{
2af202be	109	mark_object(obj, OBJ_ANY, NULL);
04d39759 LT	110	}
	111
	112	static int traverse_one_object(struct object obj, struct object parent)
	113	{
	114	int result;
	115	struct tree *tree = NULL;
	116
271b8d25 MK	117	if (obj->type == OBJ_TREE) {
	118	obj->parsed = 0;
	119	tree = (struct tree *)obj;
	120	if (parse_tree(tree) < 0)
	121	return 1; /* error already displayed */
	122	}
	123	result = fsck_walk(obj, mark_object, obj);
	124	if (tree) {
	125	free(tree->buffer);
	126	tree->buffer = NULL;
	127	}
271b8d25 MK	128	return result;
	129	}
	130
04d39759	131	static int traverse_reachable(void)
271b8d25	132	{
04d39759 LT	133	int result = 0;
	134	while (pending.nr) {
	135	struct object_array_entry *entry;
	136	struct object obj, parent;
	137
	138	entry = pending.objects + --pending.nr;
	139	obj = entry->item;
	140	parent = (struct object *) entry->name;
	141	result \|= traverse_one_object(obj, parent);
	142	}
	143	return !!result;
271b8d25 MK	144	}
	145
	146	static int mark_used(struct object obj, int type, void data)
	147	{
	148	if (!obj)
	149	return 1;
	150	obj->used = 1;
	151	return 0;
f1f0d088 PB	152	}
f1f0d088 PB	153
18af29f2 LT	154	/*
	155	* Check a single reachable object
	156	*/
	157	static void check_reachable_object(struct object *obj)
	158	{
18af29f2 LT	159	/*
	160	* We obviously want the object to be parsed,
	161	* except if it was in a pack-file and we didn't
	162	* do a full fsck
	163	*/
	164	if (!obj->parsed) {
cd673c1f	165	if (has_sha1_pack(obj->sha1))
18af29f2 LT	166	return; /* it is in pack - forget about it */
18af29f2 LT	167	printf("missing %s %s\n", typename(obj->type), sha1_to_hex(obj->sha1));
e2b4f635	168	errors_found \|= ERROR_REACHABLE;
18af29f2 LT	169	return;
18af29f2 LT	170	}
18af29f2 LT	171	}
	172
	173	/*
	174	* Check a single unreachable object
	175	*/
	176	static void check_unreachable_object(struct object *obj)
	177	{
	178	/*
	179	* Missing unreachable object? Ignore it. It's not like
	180	* we miss it (since it can't be reached), nor do we want
	181	* to complain about it being unreachable (since it does
	182	* not exist).
	183	*/
	184	if (!obj->parsed)
	185	return;
	186
	187	/*
	188	* Unreachable object that exists? Show it if asked to,
	189	* since this is something that is prunable.
	190	*/
	191	if (show_unreachable) {
	192	printf("unreachable %s %s\n", typename(obj->type), sha1_to_hex(obj->sha1));
	193	return;
	194	}
	195
	196	/*
	197	* "!used" means that nothing at all points to it, including
3dff5379	198	* other unreachable objects. In other words, it's the "tip"
18af29f2 LT	199	* of some set of unreachable objects, usually a commit that
	200	* got dropped.
	201	*
	202	* Such starting points are more interesting than some random
	203	* set of unreachable objects, so we show them even if the user
	204	* hasn't asked for _all_ unreachable objects. If you have
	205	* deleted a branch by mistake, this is a prime candidate to
	206	* start looking at, for example.
	207	*/
	208	if (!obj->used) {
	209	printf("dangling %s %s\n", typename(obj->type),
	210	sha1_to_hex(obj->sha1));
68f6c019 JS	211	if (write_lost_and_found) {
	212	char *filename = git_path("lost-found/%s/%s",
	213	obj->type == OBJ_COMMIT ? "commit" : "other",
	214	sha1_to_hex(obj->sha1));
	215	FILE *f;
	216
	217	if (safe_create_leading_directories(filename)) {
	218	error("Could not create lost-found");
	219	return;
	220	}
	221	if (!(f = fopen(filename, "w")))
0721c314	222	die_errno("Could not open '%s'", filename);
16a7fcfe JS	223	if (obj->type == OBJ_BLOB) {
	224	enum object_type type;
	225	unsigned long size;
	226	char *buf = read_sha1_file(obj->sha1,
	227	&type, &size);
	228	if (buf) {
47d32af2	229	if (fwrite(buf, size, 1, f) != 1)
d824cbba TR	230	die_errno("Could not write '%s'",
d824cbba TR	231	filename);
16a7fcfe JS	232	free(buf);
	233	}
	234	} else
	235	fprintf(f, "%s\n", sha1_to_hex(obj->sha1));
47d32af2	236	if (fclose(f))
d824cbba TR	237	die_errno("Could not finish '%s'",
d824cbba TR	238	filename);
68f6c019	239	}
18af29f2 LT	240	return;
	241	}
	242
	243	/*
	244	* Otherwise? It's there, it's unreachable, and some other unreachable
	245	* object points to it. Ignore it - it's not interesting, and we showed
	246	* all the interesting cases above.
	247	*/
	248	}
	249
	250	static void check_object(struct object *obj)
	251	{
20f1eb6b JS	252	if (verbose)
	253	fprintf(stderr, "Checking %s\n", sha1_to_hex(obj->sha1));
	254
18af29f2 LT	255	if (obj->flags & REACHABLE)
	256	check_reachable_object(obj);
	257	else
	258	check_unreachable_object(obj);
	259	}
f1f0d088	260
8ba0bbb2 LT	261	static void check_connectivity(void)
8ba0bbb2 LT	262	{
fc046a75	263	int i, max;
8ba0bbb2	264
04d39759 LT	265	/* Traverse the pending reachable objects */
	266	traverse_reachable();
	267
8ba0bbb2	268	/* Look up all the requirements, warn about missing objects.. */
fc046a75	269	max = get_max_object_index();
20f1eb6b JS	270	if (verbose)
	271	fprintf(stderr, "Checking connectivity (%d objects)\n", max);
	272
fc046a75	273	for (i = 0; i < max; i++) {
fc046a75	274	struct object *obj = get_indexed_object(i);
8ba0bbb2	275
18af29f2 LT	276	if (obj)
18af29f2 LT	277	check_object(obj);
8ba0bbb2 LT	278	}
	279	}
	280
ba002f3b	281	static int fsck_sha1(const unsigned char *sha1)
85003492	282	{
ba002f3b MK	283	struct object *obj = parse_object(sha1);
	284	if (!obj) {
	285	errors_found \|= ERROR_OBJECT;
	286	return error("%s: object corrupt or missing",
	287	sha1_to_hex(sha1));
	288	}
	289	if (obj->flags & SEEN)
85003492	290	return 0;
ba002f3b	291	obj->flags \|= SEEN;
85003492	292
20f1eb6b	293	if (verbose)
ba002f3b MK	294	fprintf(stderr, "Checking %s %s\n",
ba002f3b MK	295	typename(obj->type), sha1_to_hex(obj->sha1));
42ea9cb2	296
2af202be	297	if (fsck_walk(obj, mark_used, NULL))
ba002f3b MK	298	objerror(obj, "broken links");
	299	if (fsck_object(obj, check_strict, fsck_error_func))
	300	return -1;
85003492	301
ba002f3b MK	302	if (obj->type == OBJ_TREE) {
ba002f3b MK	303	struct tree item = (struct tree ) obj;
85003492	304
ba002f3b MK	305	free(item->buffer);
ba002f3b MK	306	item->buffer = NULL;
1ea34e36	307	}
1ea34e36	308
ba002f3b MK	309	if (obj->type == OBJ_COMMIT) {
ba002f3b MK	310	struct commit commit = (struct commit ) obj;
de2eb7f6	311
ba002f3b MK	312	free(commit->buffer);
ba002f3b MK	313	commit->buffer = NULL;
4728b861	314
ba002f3b MK	315	if (!commit->parents && show_root)
	316	printf("root %s\n", sha1_to_hex(commit->object.sha1));
	317	}
92d4c85d	318
ba002f3b MK	319	if (obj->type == OBJ_TAG) {
ba002f3b MK	320	struct tag tag = (struct tag ) obj;
20f1eb6b	321
ba002f3b MK	322	if (show_tags && tag->tagged) {
	323	printf("tagged %s %s", typename(tag->tagged->type), sha1_to_hex(tag->tagged->sha1));
	324	printf(" (%s) in %s\n", tag->tag, sha1_to_hex(tag->object.sha1));
	325	}
92d4c85d	326	}
889262ea	327
ff5ebe39	328	return 0;
20222118 LT	329	}
20222118 LT	330
7e8c174a LT	331	/*
	332	* This is the sorting chunk size: make it reasonably
	333	* big so that we can sort well..
	334	*/
	335	#define MAX_SHA1_ENTRIES (1024)
	336
	337	struct sha1_entry {
	338	unsigned long ino;
20222118	339	unsigned char sha1[20];
7e8c174a LT	340	};
	341
	342	static struct {
	343	unsigned long nr;
	344	struct sha1_entry *entry[MAX_SHA1_ENTRIES];
	345	} sha1_list;
	346
	347	static int ino_compare(const void _a, const void _b)
	348	{
	349	const struct sha1_entry a = _a, b = _b;
	350	unsigned long ino1 = a->ino, ino2 = b->ino;
	351	return ino1 < ino2 ? -1 : ino1 > ino2 ? 1 : 0;
	352	}
	353
	354	static void fsck_sha1_list(void)
	355	{
	356	int i, nr = sha1_list.nr;
	357
35a730f0 JH	358	if (SORT_DIRENT)
	359	qsort(sha1_list.entry, nr,
	360	sizeof(struct sha1_entry *), ino_compare);
7e8c174a LT	361	for (i = 0; i < nr; i++) {
	362	struct sha1_entry *entry = sha1_list.entry[i];
	363	unsigned char *sha1 = entry->sha1;
	364
	365	sha1_list.entry[i] = NULL;
f1f0d088	366	fsck_sha1(sha1);
7e8c174a	367	free(entry);
20222118	368	}
7e8c174a LT	369	sha1_list.nr = 0;
	370	}
	371
	372	static void add_sha1_list(unsigned char *sha1, unsigned long ino)
	373	{
	374	struct sha1_entry entry = xmalloc(sizeof(entry));
	375	int nr;
	376
	377	entry->ino = ino;
e702496e	378	hashcpy(entry->sha1, sha1);
7e8c174a LT	379	nr = sha1_list.nr;
	380	if (nr == MAX_SHA1_ENTRIES) {
	381	fsck_sha1_list();
	382	nr = 0;
	383	}
	384	sha1_list.entry[nr] = entry;
	385	sha1_list.nr = ++nr;
20222118 LT	386	}
20222118 LT	387
b5524c82	388	static void fsck_dir(int i, char *path)
20222118 LT	389	{
	390	DIR *dir = opendir(path);
	391	struct dirent *de;
	392
230f1322	393	if (!dir)
b5524c82	394	return;
20222118	395
20f1eb6b JS	396	if (verbose)
	397	fprintf(stderr, "Checking directory %s\n", path);
	398
20222118 LT	399	while ((de = readdir(dir)) != NULL) {
20222118 LT	400	char name[100];
7e8c174a	401	unsigned char sha1[20];
20222118	402
8ca12c0d	403	if (is_dot_or_dotdot(de->d_name))
20222118	404	continue;
8ca12c0d	405	if (strlen(de->d_name) == 38) {
20222118	406	sprintf(name, "%02x", i);
8ca12c0d	407	memcpy(name+2, de->d_name, 39);
7e8c174a LT	408	if (get_sha1_hex(name, sha1) < 0)
7e8c174a LT	409	break;
35a730f0	410	add_sha1_list(sha1, DIRENT_SORT_HINT(de));
7e8c174a	411	continue;
20222118	412	}
3d32a46b	413	if (!prefixcmp(de->d_name, "tmp_obj_"))
a08c53a1	414	continue;
20222118 LT	415	fprintf(stderr, "bad sha1 file: %s/%s\n", path, de->d_name);
	416	}
	417	closedir(dir);
20222118 LT	418	}
20222118 LT	419
96f1e58f	420	static int default_refs;
944d8589	421
883d60fa JS	422	static int fsck_handle_reflog_ent(unsigned char osha1, unsigned char nsha1,
	423	const char *email, unsigned long timestamp, int tz,
	424	const char message, void cb_data)
55dd5526 JH	425	{
	426	struct object *obj;
	427
20f1eb6b JS	428	if (verbose)
	429	fprintf(stderr, "Checking reflog %s->%s\n",
	430	sha1_to_hex(osha1), sha1_to_hex(nsha1));
	431
55dd5526 JH	432	if (!is_null_sha1(osha1)) {
	433	obj = lookup_object(osha1);
	434	if (obj) {
	435	obj->used = 1;
271b8d25	436	mark_object_reachable(obj);
55dd5526 JH	437	}
	438	}
	439	obj = lookup_object(nsha1);
	440	if (obj) {
	441	obj->used = 1;
271b8d25	442	mark_object_reachable(obj);
55dd5526 JH	443	}
	444	return 0;
	445	}
	446
eb8381c8 NP	447	static int fsck_handle_reflog(const char logname, const unsigned char sha1, int flag, void *cb_data)
	448	{
	449	for_each_reflog_ent(logname, fsck_handle_reflog_ent, NULL);
	450	return 0;
	451	}
	452
6232f62b LT	453	static int is_branch(const char *refname)
	454	{
	455	return !strcmp(refname, "HEAD") \|\| !prefixcmp(refname, "refs/heads/");
	456	}
	457
8da19775	458	static int fsck_handle_ref(const char refname, const unsigned char sha1, int flag, void *cb_data)
1024932f	459	{
1024932f LT	460	struct object *obj;
1024932f LT	461
6232f62b	462	obj = parse_object(sha1);
8a498a05	463	if (!obj) {
944d8589 LT	464	error("%s: invalid sha1 pointer %s", refname, sha1_to_hex(sha1));
	465	/* We'll continue with the rest despite the error.. */
	466	return 0;
8a498a05	467	}
6232f62b LT	468	if (obj->type != OBJ_COMMIT && is_branch(refname))
6232f62b LT	469	error("%s: not a commit", refname);
944d8589	470	default_refs++;
1024932f	471	obj->used = 1;
271b8d25	472	mark_object_reachable(obj);
55dd5526	473
7c4d07c7	474	return 0;
1024932f LT	475	}
1024932f LT	476
1024932f LT	477	static void get_default_heads(void)
1024932f LT	478	{
469e2ebf JH	479	if (head_points_at && !is_null_sha1(head_sha1))
469e2ebf JH	480	fsck_handle_ref("HEAD", head_sha1, 0, NULL);
cb5d709f	481	for_each_ref(fsck_handle_ref, NULL);
566842f6 SP	482	if (include_reflogs)
566842f6 SP	483	for_each_reflog(fsck_handle_reflog, NULL);
071fa89e LT	484
	485	/*
	486	* Not having any default heads isn't really fatal, but
	487	* it does mean that "--unreachable" no longer makes any
	488	* sense (since in this case everything will obviously
	489	* be unreachable by definition.
	490	*
	491	* Showing dangling objects is valid, though (as those
	492	* dangling objects are likely lost heads).
	493	*
	494	* So we just print a warning about it, and clear the
	495	* "show_unreachable" flag.
	496	*/
	497	if (!default_refs) {
8eb2d0be	498	fprintf(stderr, "notice: No default references\n");
071fa89e LT	499	show_unreachable = 0;
071fa89e LT	500	}
1024932f LT	501	}
1024932f LT	502
8a498a05 JH	503	static void fsck_object_dir(const char *path)
	504	{
	505	int i;
20f1eb6b JS	506
	507	if (verbose)
	508	fprintf(stderr, "Checking object directory\n");
	509
8a498a05 JH	510	for (i = 0; i < 256; i++) {
	511	static char dir[4096];
	512	sprintf(dir, "%s/%02x", path, i);
	513	fsck_dir(i, dir);
	514	}
	515	fsck_sha1_list();
	516	}
	517
c3330383 LT	518	static int fsck_head_link(void)
c3330383 LT	519	{
8da19775	520	int flag;
8eb2d0be	521	int null_is_error = 0;
8eb2d0be	522
20f1eb6b JS	523	if (verbose)
	524	fprintf(stderr, "Checking HEAD link\n");
	525
469e2ebf	526	head_points_at = resolve_ref("HEAD", head_sha1, 0, &flag);
8eb2d0be JH	527	if (!head_points_at)
	528	return error("Invalid HEAD");
	529	if (!strcmp(head_points_at, "HEAD"))
	530	/* detached HEAD */
	531	null_is_error = 1;
	532	else if (prefixcmp(head_points_at, "refs/heads/"))
8098a178	533	return error("HEAD points to something strange (%s)",
5b10b091	534	head_points_at);
469e2ebf	535	if (is_null_sha1(head_sha1)) {
8eb2d0be JH	536	if (null_is_error)
	537	return error("HEAD: detached HEAD points at nothing");
	538	fprintf(stderr, "notice: HEAD points to an unborn branch (%s)\n",
	539	head_points_at + 11);
	540	}
c3330383 LT	541	return 0;
	542	}
	543
53dc3f3e JH	544	static int fsck_cache_tree(struct cache_tree *it)
	545	{
	546	int i;
	547	int err = 0;
	548
20f1eb6b JS	549	if (verbose)
	550	fprintf(stderr, "Checking cache tree\n");
	551
53dc3f3e JH	552	if (0 <= it->entry_count) {
53dc3f3e JH	553	struct object *obj = parse_object(it->sha1);
6d60bbef JH	554	if (!obj) {
	555	error("%s: invalid sha1 pointer in cache-tree",
	556	sha1_to_hex(it->sha1));
	557	return 1;
	558	}
271b8d25	559	mark_object_reachable(obj);
cdc08b33	560	obj->used = 1;
1974632c	561	if (obj->type != OBJ_TREE)
53dc3f3e JH	562	err \|= objerror(obj, "non-tree in cache-tree");
	563	}
	564	for (i = 0; i < it->subtree_nr; i++)
	565	err \|= fsck_cache_tree(it->down[i]->cache_tree);
	566	return err;
	567	}
	568
5ac0a206	569	static char const * const fsck_usage[] = {
1b1dd23f	570	"git fsck [options] [<object>...]",
5ac0a206 PH	571	NULL
	572	};
	573
	574	static struct option fsck_opts[] = {
	575	OPT__VERBOSE(&verbose),
	576	OPT_BOOLEAN(0, "unreachable", &show_unreachable, "show unreachable objects"),
	577	OPT_BOOLEAN(0, "tags", &show_tags, "report tags"),
	578	OPT_BOOLEAN(0, "root", &show_root, "report root nodes"),
	579	OPT_BOOLEAN(0, "cache", &keep_cache_objects, "make index objects head nodes"),
	580	OPT_BOOLEAN(0, "reflogs", &include_reflogs, "make reflogs head nodes (default)"),
2b26e0e1	581	OPT_BOOLEAN(0, "full", &check_full, "also consider packs and alternate objects"),
dd46b9b9	582	OPT_BOOLEAN(0, "strict", &check_strict, "enable more strict checking"),
5ac0a206 PH	583	OPT_BOOLEAN(0, "lost-found", &write_lost_and_found,
	584	"write dangling objects in .git/lost-found"),
	585	OPT_END(),
	586	};
e2b4f635	587
baffc0e7	588	int cmd_fsck(int argc, const char *argv, const char prefix)
20222118	589	{
bcee6fd8	590	int i, heads;
e15ef669	591	struct alternate_object_database *alt;
20222118	592
e2b4f635	593	errors_found = 0;
dae556bd	594	read_replace_refs = 0;
61e2b015	595
37782920	596	argc = parse_options(argc, argv, prefix, fsck_opts, fsck_usage, 0);
5ac0a206 PH	597	if (write_lost_and_found) {
	598	check_full = 1;
	599	include_reflogs = 0;
889262ea LT	600	}
889262ea LT	601
c3330383	602	fsck_head_link();
8a498a05	603	fsck_object_dir(get_object_directory());
e15ef669 JH	604
	605	prepare_alt_odb();
	606	for (alt = alt_odb_list; alt; alt = alt->next) {
	607	char namebuf[PATH_MAX];
	608	int namelen = alt->name - alt->base;
	609	memcpy(namebuf, alt->base, namelen);
	610	namebuf[namelen - 1] = 0;
	611	fsck_object_dir(namebuf);
	612	}
	613
8a498a05	614	if (check_full) {
8a498a05	615	struct packed_git *p;
e15ef669	616
8a498a05	617	prepare_packed_git();
f9253394 JH	618	for (p = packed_git; p; p = p->next)
f9253394 JH	619	/* verify gives error messages itself */
77d3ecee	620	verify_pack(p);
f9253394	621
8a498a05	622	for (p = packed_git; p; p = p->next) {
5ac0a206	623	uint32_t j, num;
b77ffe8a SP	624	if (open_pack_index(p))
	625	continue;
	626	num = p->num_objects;
5ac0a206 PH	627	for (j = 0; j < num; j++)
5ac0a206 PH	628	fsck_sha1(nth_packed_object_sha1(p, j));
8a498a05	629	}
bcee6fd8 LT	630	}
	631
	632	heads = 0;
3aed2fda	633	for (i = 0; i < argc; i++) {
a6080a0a	634	const char *arg = argv[i];
469e2ebf JH	635	unsigned char sha1[20];
	636	if (!get_sha1(arg, sha1)) {
	637	struct object *obj = lookup_object(sha1);
e1a1388d	638
770896e5 LT	639	/* Error is printed by lookup_object(). */
770896e5 LT	640	if (!obj)
e1a1388d JF	641	continue;
e1a1388d JF	642
ff5ebe39	643	obj->used = 1;
271b8d25	644	mark_object_reachable(obj);
bcee6fd8	645	heads++;
d9839e03 LT	646	continue;
d9839e03 LT	647	}
f1f0d088	648	error("invalid parameter: expected sha1, got '%s'", arg);
d9839e03	649	}
d9839e03	650
1024932f	651	/*
d1af002d	652	* If we've not been given any explicit head information, do the
e7bd907d LT	653	* default ones from .git/refs. We also consider the index file
e7bd907d LT	654	* in this case (ie this implies --cache).
1024932f	655	*/
e7bd907d	656	if (!heads) {
1024932f LT	657	get_default_heads();
	658	keep_cache_objects = 1;
	659	}
	660
ae7c0c92	661	if (keep_cache_objects) {
ae7c0c92 JH	662	read_cache();
ae7c0c92 JH	663	for (i = 0; i < active_nr; i++) {
8d9721c8 LT	664	unsigned int mode;
8d9721c8 LT	665	struct blob *blob;
ae7c0c92	666	struct object *obj;
8d9721c8	667
7a51ed66	668	mode = active_cache[i]->ce_mode;
302b9282	669	if (S_ISGITLINK(mode))
8d9721c8 LT	670	continue;
8d9721c8 LT	671	blob = lookup_blob(active_cache[i]->sha1);
ae7c0c92 JH	672	if (!blob)
	673	continue;
	674	obj = &blob->object;
	675	obj->used = 1;
271b8d25	676	mark_object_reachable(obj);
ae7c0c92	677	}
53dc3f3e JH	678	if (active_cache_tree)
53dc3f3e JH	679	fsck_cache_tree(active_cache_tree);
ae7c0c92 JH	680	}
ae7c0c92 JH	681
8ba0bbb2	682	check_connectivity();
e2b4f635	683	return errors_found;
20222118	684	}