From: Junio C Hamano Date: Thu, 27 Oct 2016 21:58:47 +0000 (-0700) Subject: Merge branch 'jk/abbrev-auto' X-Git-Tag: v2.11.0-rc0~23 X-Git-Url: https://git.lorimer.id.au/gitweb.git/diff_plain/d7ae013a3173c621a3556be6834d459ece60e130?ds=inline;hp=-c Merge branch 'jk/abbrev-auto' Updates the way approximate count of total objects is computed while attempting to come up with a unique abbreviated object name, which in turn needs to estimate how many hexdigits are necessary to ensure uniqueness. * jk/abbrev-auto: find_unique_abbrev: move logic out of get_short_sha1() --- d7ae013a3173c621a3556be6834d459ece60e130 diff --combined cache.h index 446d4cb632,f22ace5079..b7f34b4ae6 --- a/cache.h +++ b/cache.h @@@ -367,9 -367,8 +367,9 @@@ extern void free_name_hash(struct index #define rename_cache_entry_at(pos, new_name) rename_index_entry_at(&the_index, (pos), (new_name)) #define remove_cache_entry_at(pos) remove_index_entry_at(&the_index, (pos)) #define remove_file_from_cache(path) remove_file_from_index(&the_index, (path)) -#define add_to_cache(path, st, flags) add_to_index(&the_index, (path), (st), (flags), 0) -#define add_file_to_cache(path, flags) add_file_to_index(&the_index, (path), (flags), 0) +#define add_to_cache(path, st, flags) add_to_index(&the_index, (path), (st), (flags)) +#define add_file_to_cache(path, flags) add_file_to_index(&the_index, (path), (flags)) +#define chmod_cache_entry(ce, flip) chmod_index_entry(&the_index, (ce), (flip)) #define refresh_cache(flags) refresh_index(&the_index, (flags), NULL, NULL, NULL) #define ce_match_stat(ce, st, options) ie_match_stat(&the_index, (ce), (st), (options)) #define ce_modified(ce, st, options) ie_modified(&the_index, (ce), (st), (options)) @@@ -409,7 -408,6 +409,7 @@@ static inline enum object_type object_t #define GIT_NAMESPACE_ENVIRONMENT "GIT_NAMESPACE" #define GIT_WORK_TREE_ENVIRONMENT "GIT_WORK_TREE" #define GIT_PREFIX_ENVIRONMENT "GIT_PREFIX" +#define GIT_SUPER_PREFIX_ENVIRONMENT "GIT_INTERNAL_SUPER_PREFIX" #define DEFAULT_GIT_DIR_ENVIRONMENT ".git" #define DB_ENVIRONMENT "GIT_OBJECT_DIRECTORY" #define INDEX_ENVIRONMENT "GIT_INDEX_FILE" @@@ -434,7 -432,6 +434,7 @@@ #define GIT_GLOB_PATHSPECS_ENVIRONMENT "GIT_GLOB_PATHSPECS" #define GIT_NOGLOB_PATHSPECS_ENVIRONMENT "GIT_NOGLOB_PATHSPECS" #define GIT_ICASE_PATHSPECS_ENVIRONMENT "GIT_ICASE_PATHSPECS" +#define GIT_QUARANTINE_ENVIRONMENT "GIT_QUARANTINE_PATH" /* * This environment variable is expected to contain a boolean indicating @@@ -477,7 -474,6 +477,7 @@@ extern int get_common_dir_noenv(struct extern int get_common_dir(struct strbuf *sb, const char *gitdir); extern const char *get_git_namespace(void); extern const char *strip_namespace(const char *namespaced_ref); +extern const char *get_super_prefix(void); extern const char *get_git_work_tree(void); /* @@@ -529,10 -525,9 +529,10 @@@ extern void verify_non_filename(const c extern int path_inside_repo(const char *prefix, const char *path); #define INIT_DB_QUIET 0x0001 +#define INIT_DB_EXIST_OK 0x0002 -extern int set_git_dir_init(const char *git_dir, const char *real_git_dir, int); -extern int init_db(const char *template_dir, unsigned int flags); +extern int init_db(const char *git_dir, const char *real_git_dir, + const char *template_dir, unsigned int flags); extern void sanitize_stdfds(void); extern int daemonize(void); @@@ -592,10 -587,9 +592,10 @@@ extern int remove_file_from_index(struc #define ADD_CACHE_IGNORE_ERRORS 4 #define ADD_CACHE_IGNORE_REMOVAL 8 #define ADD_CACHE_INTENT 16 -extern int add_to_index(struct index_state *, const char *path, struct stat *, int flags, int force_mode); -extern int add_file_to_index(struct index_state *, const char *path, int flags, int force_mode); +extern int add_to_index(struct index_state *, const char *path, struct stat *, int flags); +extern int add_file_to_index(struct index_state *, const char *path, int flags); extern struct cache_entry *make_cache_entry(unsigned int mode, const unsigned char *sha1, const char *path, int stage, unsigned int refresh_options); +extern int chmod_index_entry(struct index_state *, struct cache_entry *ce, char flip); extern int ce_same_name(const struct cache_entry *a, const struct cache_entry *b); extern void set_object_name_for_intent_to_add_entry(struct cache_entry *ce); extern int index_name_is_other(const struct index_state *, const char *, int); @@@ -1157,7 -1151,6 +1157,7 @@@ static inline int has_sha1_file(const u /* Same as the above, except for struct object_id. */ extern int has_object_file(const struct object_id *oid); +extern int has_object_file_with_flags(const struct object_id *oid, int flags); /* * Return true iff an alternate object database has a loose object @@@ -1211,7 -1204,6 +1211,6 @@@ struct object_context #define GET_SHA1_TREEISH 020 #define GET_SHA1_BLOB 040 #define GET_SHA1_FOLLOW_SYMLINKS 0100 - #define GET_SHA1_AUTOMATIC 0200 #define GET_SHA1_ONLY_TO_DIE 04000 #define GET_SHA1_DISAMBIGUATORS \ @@@ -1372,7 -1364,6 +1371,7 @@@ struct checkout not_new:1, refresh_cache:1; }; +#define CHECKOUT_INIT { NULL, "" } #define TEMPORARY_FILENAME_LENGTH 25 extern int checkout_entry(struct cache_entry *ce, const struct checkout *state, char *topath); @@@ -1398,46 -1389,16 +1397,46 @@@ extern void remove_scheduled_dirs(void) extern struct alternate_object_database { struct alternate_object_database *next; - char *name; - char base[FLEX_ARRAY]; /* more */ + + /* see alt_scratch_buf() */ + struct strbuf scratch; + size_t base_len; + + char path[FLEX_ARRAY]; } *alt_odb_list; extern void prepare_alt_odb(void); extern void read_info_alternates(const char * relative_base, int depth); extern char *compute_alternate_path(const char *path, struct strbuf *err); -extern void add_to_alternates_file(const char *reference); typedef int alt_odb_fn(struct alternate_object_database *, void *); extern int foreach_alt_odb(alt_odb_fn, void*); +/* + * Allocate a "struct alternate_object_database" but do _not_ actually + * add it to the list of alternates. + */ +struct alternate_object_database *alloc_alt_odb(const char *dir); + +/* + * Add the directory to the on-disk alternates file; the new entry will also + * take effect in the current process. + */ +extern void add_to_alternates_file(const char *dir); + +/* + * Add the directory to the in-memory list of alternates (along with any + * recursive alternates it points to), but do not modify the on-disk alternates + * file. + */ +extern void add_to_alternates_memory(const char *dir); + +/* + * Returns a scratch strbuf pre-filled with the alternate object directory, + * including a trailing slash, which can be used to access paths in the + * alternate. Always use this over direct access to alt->scratch, as it + * cleans up any previous use of the scratch buffer. + */ +extern struct strbuf *alt_scratch_buf(struct alternate_object_database *alt); + struct pack_window { struct pack_window *next; unsigned char *base; @@@ -1494,6 -1455,12 +1493,12 @@@ extern void prepare_packed_git(void) extern void reprepare_packed_git(void); extern void install_packed_git(struct packed_git *pack); + /* + * Give a rough count of objects in the repository. This sacrifices accuracy + * for speed. + */ + unsigned long approximate_object_count(void); + extern struct packed_git *find_sha1_pack(const unsigned char *sha1, struct packed_git *packs); @@@ -1640,15 -1607,7 +1645,15 @@@ struct object_info } packed; } u; }; + +/* + * Initializer for a "struct object_info" that wants no items. You may + * also memset() the memory to all-zeroes. + */ +#define OBJECT_INFO_INIT {NULL} + extern int sha1_object_info_extended(const unsigned char *, struct object_info *, unsigned flags); +extern int packed_object_info(struct packed_git *pack, off_t offset, struct object_info *); /* Dumb servers support */ extern int update_server_info(int); @@@ -1915,7 -1874,7 +1920,7 @@@ void packet_trace_identity(const char * * return 0 if success, 1 - if addition of a file failed and * ADD_FILES_IGNORE_ERRORS was specified in flags */ -int add_files_to_cache(const char *prefix, const struct pathspec *pathspec, int flags, int force_mode); +int add_files_to_cache(const char *prefix, const struct pathspec *pathspec, int flags); /* diff.c */ extern int diff_auto_refresh_index; diff --combined sha1_file.c index 2eda9291ee,48824407aa..1e41954a84 --- a/sha1_file.c +++ b/sha1_file.c @@@ -172,42 -172,36 +172,42 @@@ enum scld_error safe_create_leading_dir return result; } -static void fill_sha1_path(char *pathbuf, const unsigned char *sha1) +static void fill_sha1_path(struct strbuf *buf, const unsigned char *sha1) { int i; for (i = 0; i < 20; i++) { static char hex[] = "0123456789abcdef"; unsigned int val = sha1[i]; - char *pos = pathbuf + i*2 + (i > 0); - *pos++ = hex[val >> 4]; - *pos = hex[val & 0xf]; + strbuf_addch(buf, hex[val >> 4]); + strbuf_addch(buf, hex[val & 0xf]); + if (!i) + strbuf_addch(buf, '/'); } } const char *sha1_file_name(const unsigned char *sha1) { - static char buf[PATH_MAX]; - const char *objdir; - int len; + static struct strbuf buf = STRBUF_INIT; + + strbuf_reset(&buf); + strbuf_addf(&buf, "%s/", get_object_directory()); - objdir = get_object_directory(); - len = strlen(objdir); + fill_sha1_path(&buf, sha1); + return buf.buf; +} + +struct strbuf *alt_scratch_buf(struct alternate_object_database *alt) +{ + strbuf_setlen(&alt->scratch, alt->base_len); + return &alt->scratch; +} - /* '/' + sha1(2) + '/' + sha1(38) + '\0' */ - if (len + 43 > PATH_MAX) - die("insanely long object directory %s", objdir); - memcpy(buf, objdir, len); - buf[len] = '/'; - buf[len+3] = '/'; - buf[len+42] = '\0'; - fill_sha1_path(buf + len + 1, sha1); - return buf; +static const char *alt_sha1_path(struct alternate_object_database *alt, + const unsigned char *sha1) +{ + struct strbuf *buf = alt_scratch_buf(alt); + fill_sha1_path(buf, sha1); + return buf->buf; } /* @@@ -240,35 -234,6 +240,35 @@@ char *sha1_pack_index_name(const unsign struct alternate_object_database *alt_odb_list; static struct alternate_object_database **alt_odb_tail; +/* + * Return non-zero iff the path is usable as an alternate object database. + */ +static int alt_odb_usable(struct strbuf *path, const char *normalized_objdir) +{ + struct alternate_object_database *alt; + + /* Detect cases where alternate disappeared */ + if (!is_directory(path->buf)) { + error("object directory %s does not exist; " + "check .git/objects/info/alternates.", + path->buf); + return 0; + } + + /* + * Prevent the common mistake of listing the same + * thing twice, or object directory itself. + */ + for (alt = alt_odb_list; alt; alt = alt->next) { + if (!fspathcmp(path->buf, alt->path)) + return 0; + } + if (!fspathcmp(path->buf, normalized_objdir)) + return 0; + + return 1; +} + /* * Prepare alternate object database registry. * @@@ -288,6 -253,8 +288,6 @@@ static int link_alt_odb_entry(const cha int depth, const char *normalized_objdir) { struct alternate_object_database *ent; - struct alternate_object_database *alt; - size_t pfxlen, entlen; struct strbuf pathbuf = STRBUF_INIT; if (!is_absolute_path(entry) && relative_base) { @@@ -296,26 -263,49 +296,26 @@@ } strbuf_addstr(&pathbuf, entry); - normalize_path_copy(pathbuf.buf, pathbuf.buf); - - pfxlen = strlen(pathbuf.buf); + if (strbuf_normalize_path(&pathbuf) < 0) { + error("unable to normalize alternate object path: %s", + pathbuf.buf); + strbuf_release(&pathbuf); + return -1; + } /* * The trailing slash after the directory name is given by * this function at the end. Remove duplicates. */ - while (pfxlen && pathbuf.buf[pfxlen-1] == '/') - pfxlen -= 1; - - entlen = st_add(pfxlen, 43); /* '/' + 2 hex + '/' + 38 hex + NUL */ - ent = xmalloc(st_add(sizeof(*ent), entlen)); - memcpy(ent->base, pathbuf.buf, pfxlen); - strbuf_release(&pathbuf); - - ent->name = ent->base + pfxlen + 1; - ent->base[pfxlen + 3] = '/'; - ent->base[pfxlen] = ent->base[entlen-1] = 0; + while (pathbuf.len && pathbuf.buf[pathbuf.len - 1] == '/') + strbuf_setlen(&pathbuf, pathbuf.len - 1); - /* Detect cases where alternate disappeared */ - if (!is_directory(ent->base)) { - error("object directory %s does not exist; " - "check .git/objects/info/alternates.", - ent->base); - free(ent); + if (!alt_odb_usable(&pathbuf, normalized_objdir)) { + strbuf_release(&pathbuf); return -1; } - /* Prevent the common mistake of listing the same - * thing twice, or object directory itself. - */ - for (alt = alt_odb_list; alt; alt = alt->next) { - if (pfxlen == alt->name - alt->base - 1 && - !memcmp(ent->base, alt->base, pfxlen)) { - free(ent); - return -1; - } - } - if (!fspathcmp(ent->base, normalized_objdir)) { - free(ent); - return -1; - } + ent = alloc_alt_odb(pathbuf.buf); /* add the alternate entry */ *alt_odb_tail = ent; @@@ -323,9 -313,10 +323,9 @@@ ent->next = NULL; /* recursively add alternates */ - read_info_alternates(ent->base, depth + 1); - - ent->base[pfxlen] = '/'; + read_info_alternates(pathbuf.buf, depth + 1); + strbuf_release(&pathbuf); return 0; } @@@ -344,9 -335,7 +344,9 @@@ static void link_alt_odb_entries(const } strbuf_add_absolute_path(&objdirbuf, get_object_directory()); - normalize_path_copy(objdirbuf.buf, objdirbuf.buf); + if (strbuf_normalize_path(&objdirbuf) < 0) + die("unable to normalize object directory: %s", + objdirbuf.buf); alt_copy = xmemdupz(alt, len); string_list_split_in_place(&entries, alt_copy, sep, -1); @@@ -354,7 -343,12 +354,7 @@@ const char *entry = entries.items[i].string; if (entry[0] == '\0' || entry[0] == '#') continue; - if (!is_absolute_path(entry) && depth) { - error("%s: ignoring relative alternate object store %s", - relative_base, entry); - } else { - link_alt_odb_entry(entry, relative_base, depth, objdirbuf.buf); - } + link_alt_odb_entry(entry, relative_base, depth, objdirbuf.buf); } string_list_clear(&entries, 0); free(alt_copy); @@@ -387,18 -381,6 +387,18 @@@ void read_info_alternates(const char * munmap(map, mapsz); } +struct alternate_object_database *alloc_alt_odb(const char *dir) +{ + struct alternate_object_database *ent; + + FLEX_ALLOC_STR(ent, path, dir); + strbuf_init(&ent->scratch, 0); + strbuf_addf(&ent->scratch, "%s/", dir); + ent->base_len = ent->scratch.len; + + return ent; +} + void add_to_alternates_file(const char *reference) { struct lock_file *lock = xcalloc(1, sizeof(struct lock_file)); @@@ -444,17 -426,6 +444,17 @@@ free(alts); } +void add_to_alternates_memory(const char *reference) +{ + /* + * Make sure alternates are initialized, or else our entry may be + * overwritten when they are. + */ + prepare_alt_odb(); + + link_alt_odb_entries(reference, strlen(reference), '\n', NULL, 0); +} + /* * Compute the exact path an alternate is at and returns it. In case of * error NULL is returned and the human readable error is added to `err` @@@ -595,8 -566,8 +595,8 @@@ static int check_and_freshen_nonlocal(c struct alternate_object_database *alt; prepare_alt_odb(); for (alt = alt_odb_list; alt; alt = alt->next) { - fill_sha1_path(alt->name, sha1); - if (check_and_freshen_file(alt->base, freshen)) + const char *path = alt_sha1_path(alt, sha1); + if (check_and_freshen_file(path, freshen)) return 1; } return 0; @@@ -1410,6 -1381,32 +1410,32 @@@ static void prepare_packed_git_one(cha strbuf_release(&path); } + static int approximate_object_count_valid; + + /* + * Give a fast, rough count of the number of objects in the repository. This + * ignores loose objects completely. If you have a lot of them, then either + * you should repack because your performance will be awful, or they are + * all unreachable objects about to be pruned, in which case they're not really + * interesting as a measure of repo size in the first place. + */ + unsigned long approximate_object_count(void) + { + static unsigned long count; + if (!approximate_object_count_valid) { + struct packed_git *p; + + prepare_packed_git(); + count = 0; + for (p = packed_git; p; p = p->next) { + if (open_pack_index(p)) + continue; + count += p->num_objects; + } + } + return count; + } + static void *get_next_packed_git(const void *p) { return ((const struct packed_git *)p)->next; @@@ -1472,8 -1469,11 +1498,8 @@@ void prepare_packed_git(void return; prepare_packed_git_one(get_object_directory(), 1); prepare_alt_odb(); - for (alt = alt_odb_list; alt; alt = alt->next) { - alt->name[-1] = 0; - prepare_packed_git_one(alt->base, 0); - alt->name[-1] = '/'; - } + for (alt = alt_odb_list; alt; alt = alt->next) + prepare_packed_git_one(alt->path, 0); rearrange_packed_git(); prepare_packed_git_mru(); prepare_packed_git_run_once = 1; @@@ -1481,6 -1481,7 +1507,7 @@@ void reprepare_packed_git(void) { + approximate_object_count_valid = 0; prepare_packed_git_run_once = 0; prepare_packed_git(); } @@@ -1591,8 -1592,8 +1618,8 @@@ static int stat_sha1_file(const unsigne prepare_alt_odb(); errno = ENOENT; for (alt = alt_odb_list; alt; alt = alt->next) { - fill_sha1_path(alt->name, sha1); - if (!lstat(alt->base, st)) + const char *path = alt_sha1_path(alt, sha1); + if (!lstat(path, st)) return 0; } @@@ -1612,8 -1613,8 +1639,8 @@@ static int open_sha1_file(const unsigne prepare_alt_odb(); for (alt = alt_odb_list; alt; alt = alt->next) { - fill_sha1_path(alt->name, sha1); - fd = git_open_noatime(alt->base); + const char *path = alt_sha1_path(alt, sha1); + fd = git_open_noatime(path); if (fd >= 0) return fd; if (most_interesting_errno == ENOENT) @@@ -1672,9 -1673,7 +1699,9 @@@ unsigned long unpack_object_header_buff return used; } -int unpack_sha1_header(git_zstream *stream, unsigned char *map, unsigned long mapsize, void *buffer, unsigned long bufsiz) +static int unpack_sha1_short_header(git_zstream *stream, + unsigned char *map, unsigned long mapsize, + void *buffer, unsigned long bufsiz) { /* Get the data stream */ memset(stream, 0, sizeof(*stream)); @@@ -1687,31 -1686,13 +1714,31 @@@ return git_inflate(stream, 0); } +int unpack_sha1_header(git_zstream *stream, + unsigned char *map, unsigned long mapsize, + void *buffer, unsigned long bufsiz) +{ + int status = unpack_sha1_short_header(stream, map, mapsize, + buffer, bufsiz); + + if (status < Z_OK) + return status; + + /* Make sure we have the terminating NUL */ + if (!memchr(buffer, '\0', stream->next_out - (unsigned char *)buffer)) + return -1; + return 0; +} + static int unpack_sha1_header_to_strbuf(git_zstream *stream, unsigned char *map, unsigned long mapsize, void *buffer, unsigned long bufsiz, struct strbuf *header) { int status; - status = unpack_sha1_header(stream, map, mapsize, buffer, bufsiz); + status = unpack_sha1_short_header(stream, map, mapsize, buffer, bufsiz); + if (status < Z_OK) + return -1; /* * Check if entire header is unpacked in the first iteration. @@@ -1802,8 -1783,6 +1829,8 @@@ static int parse_sha1_header_extended(c */ for (;;) { char c = *hdr++; + if (!c) + return -1; if (c == ' ') break; type_len++; @@@ -1852,9 -1831,11 +1879,9 @@@ int parse_sha1_header(const char *hdr, unsigned long *sizep) { - struct object_info oi; + struct object_info oi = OBJECT_INFO_INIT; oi.sizep = sizep; - oi.typename = NULL; - oi.typep = NULL; return parse_sha1_header_extended(hdr, &oi, LOOKUP_REPLACE_OBJECT); } @@@ -2092,8 -2073,8 +2119,8 @@@ unwind goto out; } -static int packed_object_info(struct packed_git *p, off_t obj_offset, - struct object_info *oi) +int packed_object_info(struct packed_git *p, off_t obj_offset, + struct object_info *oi) { struct pack_window *w_curs = NULL; unsigned long size; @@@ -2864,7 -2845,7 +2891,7 @@@ int sha1_object_info_extended(const uns int sha1_object_info(const unsigned char *sha1, unsigned long *sizep) { enum object_type type; - struct object_info oi = {NULL}; + struct object_info oi = OBJECT_INFO_INIT; oi.typep = &type; oi.sizep = sizep; @@@ -3335,11 -3316,6 +3362,11 @@@ int has_object_file(const struct object return has_sha1_file(oid->hash); } +int has_object_file_with_flags(const struct object_id *oid, int flags) +{ + return has_sha1_file_with_flags(oid->hash, flags); +} + static void check_tree(const void *buf, size_t size) { struct tree_desc desc; @@@ -3679,7 -3655,8 +3706,7 @@@ static int loose_from_alt_odb(struct al struct strbuf buf = STRBUF_INIT; int r; - /* copy base not including trailing '/' */ - strbuf_add(&buf, alt->base, alt->name - alt->base - 1); + strbuf_addstr(&buf, alt->path); r = for_each_loose_file_in_objdir_buf(&buf, data->cb, NULL, NULL, data->data); diff --combined sha1_name.c index 84662a6804,4a6f842692..c71fc172f5 --- a/sha1_name.c +++ b/sha1_name.c @@@ -15,7 -15,6 +15,6 @@@ typedef int (*disambiguate_hint_fn)(con struct disambiguate_state { int len; /* length of prefix in hex chars */ - unsigned int nrobjects; char hex_pfx[GIT_SHA1_HEXSZ + 1]; unsigned char bin_pfx[GIT_SHA1_RAWSZ]; @@@ -92,18 -91,25 +91,18 @@@ static void find_short_object_filename( * alt->name/alt->base while iterating over the * object databases including our own. */ - const char *objdir = get_object_directory(); - size_t objdir_len = strlen(objdir); - fakeent = xmalloc(st_add3(sizeof(*fakeent), objdir_len, 43)); - memcpy(fakeent->base, objdir, objdir_len); - fakeent->name = fakeent->base + objdir_len + 1; - fakeent->name[-1] = '/'; + fakeent = alloc_alt_odb(get_object_directory()); } fakeent->next = alt_odb_list; xsnprintf(hex, sizeof(hex), "%.2s", ds->hex_pfx); for (alt = fakeent; alt && !ds->ambiguous; alt = alt->next) { + struct strbuf *buf = alt_scratch_buf(alt); struct dirent *de; DIR *dir; - /* - * every alt_odb struct has 42 extra bytes after the base - * for exactly this purpose - */ - xsnprintf(alt->name, 42, "%.2s/", ds->hex_pfx); - dir = opendir(alt->base); + + strbuf_addf(buf, "%.2s/", ds->hex_pfx); + dir = opendir(buf->buf); if (!dir) continue; @@@ -112,14 -118,6 +111,6 @@@ if (strlen(de->d_name) != 38) continue; - - /* - * We only look at the one subdirectory, and we assume - * each subdirectory is roughly similar, so each - * object we find probably has 255 other objects in - * the other fan-out directories. - */ - ds->nrobjects += 256; if (memcmp(de->d_name, ds->hex_pfx + 2, ds->len - 2)) continue; memcpy(hex + 2, de->d_name, 38); @@@ -153,7 -151,6 +144,6 @@@ static void unique_in_pack(struct packe open_pack_index(p); num = p->num_objects; - ds->nrobjects += num; last = num; while (first < last) { uint32_t mid = (first + last) / 2; @@@ -383,9 -380,6 +373,6 @@@ static int show_ambiguous_object(const return 0; } - /* start from our historical default before the automatic abbreviation */ - static int default_automatic_abbrev = FALLBACK_DEFAULT_ABBREV; - static int get_short_sha1(const char *name, int len, unsigned char *sha1, unsigned flags) { @@@ -432,14 -426,6 +419,6 @@@ for_each_abbrev(ds.hex_pfx, show_ambiguous_object, &ds); } - if (len < 16 && !status && (flags & GET_SHA1_AUTOMATIC)) { - unsigned int expect_collision = 1 << (len * 2); - if (ds.nrobjects > expect_collision) { - default_automatic_abbrev = len+1; - return SHORT_NAME_AMBIGUOUS; - } - } - return status; } @@@ -469,22 -455,53 +448,53 @@@ int for_each_abbrev(const char *prefix return ret; } + /* + * Return the slot of the most-significant bit set in "val". There are various + * ways to do this quickly with fls() or __builtin_clzl(), but speed is + * probably not a big deal here. + */ + static unsigned msb(unsigned long val) + { + unsigned r = 0; + while (val >>= 1) + r++; + return r; + } + int find_unique_abbrev_r(char *hex, const unsigned char *sha1, int len) { int status, exists; - int flags = GET_SHA1_QUIETLY; if (len < 0) { - flags |= GET_SHA1_AUTOMATIC; - len = default_automatic_abbrev; + unsigned long count = approximate_object_count(); + /* + * Add one because the MSB only tells us the highest bit set, + * not including the value of all the _other_ bits (so "15" + * is only one off of 2^4, but the MSB is the 3rd bit. + */ + len = msb(count) + 1; + /* + * We now know we have on the order of 2^len objects, which + * expects a collision at 2^(len/2). But we also care about hex + * chars, not bits, and there are 4 bits per hex. So all + * together we need to divide by 2; but we also want to round + * odd numbers up, hence adding one before dividing. + */ + len = (len + 1) / 2; + /* + * For very small repos, we stick with our regular fallback. + */ + if (len < FALLBACK_DEFAULT_ABBREV) + len = FALLBACK_DEFAULT_ABBREV; } + sha1_to_hex_r(hex, sha1); if (len == 40 || !len) return 40; exists = has_sha1_file(sha1); while (len < 40) { unsigned char sha1_ret[20]; - status = get_short_sha1(hex, len, sha1_ret, flags); + status = get_short_sha1(hex, len, sha1_ret, GET_SHA1_QUIETLY); if (exists ? !status : status == SHORT_NAME_NOT_FOUND) {