{"thread":{"id":"39531","subject":"Pack files, standards compliance, and efficiency","startedAt":"2015-06-05T01:41:21Z","lastAt":"2015-06-05T20:03:27Z","messageCount":10,"participants":["brian m. carlson","Jeff King","Duy Nguyen","Michael Haggerty","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"262991","messageId":"20150605014120.GE305479@vauxhall.crustytoothpaste.net","threadId":"39531","inReplyTo":null,"subject":"Pack files, standards compliance, and efficiency","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2015-06-05T01:41:21Z","receivedAt":"2015-06-05T01:41:21Z","isPatch":false,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"There was discussion sometime back about the object_id conversions and\nhandling direct offsets in pack files.  In some places in sha1_file.c,\nwe return direct pointers to the SHA-1 values in the mmap'd pack file\nand use those in other parts of the code.\n\nHowever, with the object_id conversion, we run into a problem: casting\nthose unsigned char * values into struct object_id * values is not\nallowed by the C standard.  There are two possible solutions: copying;\nand the just-do-it solution, where we cast and hope for the best.\n\nIt looks like we use the latter in nth_packed_object_offset, where we\ncast an unsigned char * value to uint32_t *, which is clearly not\nallowed.  I'm to the point where I need to make a decision on how to\nproceed, and I've included a patch with the copying conversion of\nnth_packed_object_sha1 below for comparison.  The casting solution is\nobviously more straightforward.  I haven't tested either implementation\nfor performance.\n\nPeople interested in the (still-to-change) state of the branch can see\nit at https://github.com/bk2204/git object-id-part2.\n\n------------8<------------------\nFrom 0f7a958ebbf6c25af526c5c46cc9b5f29f7caa15 Mon Sep 17 00:00:00 2001\nFrom: \"brian m. carlson\" <sandals@crustytoothpaste.net>\nDate: Thu, 4 Jun 2015 01:26:10 +0000\nSubject: [PATCH] Convert nth_packed_object_sha1 to object_id.\n\nnth_packed_object_sha1 returned a pointer directly into the mmap'd\nmemory of the pack in question, but the C standard does not allow\nconverting a pointer to unsigned char directly into a pointer to struct\nobject_id, even though the data represented is exactly the same size.\n\nRename the function nth_packed_object_oid, and make it take an\nadditional argument of type pointer to struct object_id.  Copy the data,\neven though this is less efficient, and adjust the callers to account\nfor the change in calling conventions.  Adjust get_delta_base_sha1\nsimilarly.\n\nSigned-off-by: brian m. carlson <sandals@crustytoothpaste.net>\n---\n builtin/pack-objects.c | 22 +++++++-------\n cache.h                |  8 ++---\n pack-bitmap.c          | 24 +++++++--------\n pack-check.c           | 15 +++++-----\n sha1_file.c            | 81 +++++++++++++++++++++++++++-----------------------\n sha1_name.c            | 14 ++++-----\n 6 files changed, 84 insertions(+), 80 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 870a266..9e12bd8 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1329,6 +1329,7 @@ static void check_object(struct object_entry *entry)\n \t\tstruct packed_git *p = entry->in_pack;\n \t\tstruct pack_window *w_curs = NULL;\n \t\tconst unsigned char *base_ref = NULL;\n+\t\tstruct object_id base_ref_oid;\n \t\tstruct object_entry *base_entry;\n \t\tunsigned long used, used_0;\n \t\tunsigned long avail;\n@@ -1394,7 +1395,8 @@ static void check_object(struct object_entry *entry)\n \t\t\t\trevidx = find_pack_revindex(p, ofs);\n \t\t\t\tif (!revidx)\n \t\t\t\t\tgoto give_up;\n-\t\t\t\tbase_ref = nth_packed_object_sha1(p, revidx->nr);\n+\t\t\t\tnth_packed_object_oid(p, &base_ref_oid, revidx->nr);\n+\t\t\t\tbase_ref = base_ref_oid.hash;\n \t\t\t}\n \t\t\tentry->in_pack_header_size = used + used_0;\n \t\t\tbreak;\n@@ -2350,7 +2352,7 @@ static void add_objects_in_unpacked_packs(struct rev_info *revs)\n \tmemset(&in_pack, 0, sizeof(in_pack));\n \n \tfor (p = packed_git; p; p = p->next) {\n-\t\tconst unsigned char *sha1;\n+\t\tstruct object_id oid;\n \t\tstruct object *o;\n \n \t\tif (!p->pack_local || p->pack_keep)\n@@ -2363,8 +2365,8 @@ static void add_objects_in_unpacked_packs(struct rev_info *revs)\n \t\t\t   in_pack.alloc);\n \n \t\tfor (i = 0; i < p->num_objects; i++) {\n-\t\t\tsha1 = nth_packed_object_sha1(p, i);\n-\t\t\to = lookup_unknown_object(sha1);\n+\t\t\tnth_packed_object_oid(p, &oid, i);\n+\t\t\to = lookup_unknown_object(oid.hash);\n \t\t\tif (!(o->flags & OBJECT_ADDED))\n \t\t\t\tmark_in_pack_object(o, p, &in_pack);\n \t\t\to->flags |= OBJECT_ADDED;\n@@ -2430,7 +2432,7 @@ static void loosen_unused_packed_objects(struct rev_info *revs)\n {\n \tstruct packed_git *p;\n \tuint32_t i;\n-\tconst unsigned char *sha1;\n+\tstruct object_id oid;\n \n \tfor (p = packed_git; p; p = p->next) {\n \t\tif (!p->pack_local || p->pack_keep)\n@@ -2440,11 +2442,11 @@ static void loosen_unused_packed_objects(struct rev_info *revs)\n \t\t\tdie(\"cannot open pack index\");\n \n \t\tfor (i = 0; i < p->num_objects; i++) {\n-\t\t\tsha1 = nth_packed_object_sha1(p, i);\n-\t\t\tif (!packlist_find(&to_pack, sha1, NULL) &&\n-\t\t\t    !has_sha1_pack_kept_or_nonlocal(sha1) &&\n-\t\t\t    !loosened_object_can_be_discarded(sha1, p->mtime))\n-\t\t\t\tif (force_object_loose(sha1, p->mtime))\n+\t\t\tnth_packed_object_oid(p, &oid, i);\n+\t\t\tif (!packlist_find(&to_pack, oid.hash, NULL) &&\n+\t\t\t    !has_sha1_pack_kept_or_nonlocal(oid.hash) &&\n+\t\t\t    !loosened_object_can_be_discarded(oid.hash, p->mtime))\n+\t\t\t\tif (force_object_loose(oid.hash, p->mtime))\n \t\t\t\t\tdie(\"unable to force loose object\");\n \t\t}\n \t}\ndiff --git a/cache.h b/cache.h\nindex 661ab72..4c51b08 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1281,12 +1281,10 @@ extern void clear_delta_base_cache(void);\n extern struct packed_git *add_packed_git(const char *, int, int);\n \n /*\n- * Return the SHA-1 of the nth object within the specified packfile.\n- * Open the index if it is not already open.  The return value points\n- * at the SHA-1 within the mmapped index.  Return NULL if there is an\n- * error.\n+ * Store the object ID of the nth object within the specified packfile.\n+ * Open the index if it is not already open.  Return 0 on success.\n  */\n-extern const unsigned char *nth_packed_object_sha1(struct packed_git *, uint32_t n);\n+extern int nth_packed_object_oid(struct packed_git *, struct object_id *oid, uint32_t n);\n \n /*\n  * Return the offset of the nth object within the specified packfile.\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex e49340a..e39f8c6 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -223,13 +223,13 @@ static int load_bitmap_entries_v1(struct bitmap_index *index)\n \t\tstruct ewah_bitmap *bitmap = NULL;\n \t\tstruct stored_bitmap *xor_bitmap = NULL;\n \t\tuint32_t commit_idx_pos;\n-\t\tconst unsigned char *sha1;\n+\t\tstruct object_id oid;\n \n \t\tcommit_idx_pos = read_be32(index->map, &index->map_pos);\n \t\txor_offset = read_u8(index->map, &index->map_pos);\n \t\tflags = read_u8(index->map, &index->map_pos);\n \n-\t\tsha1 = nth_packed_object_sha1(index->pack, commit_idx_pos);\n+\t\tnth_packed_object_oid(index->pack, &oid, commit_idx_pos);\n \n \t\tbitmap = read_bitmap_1(index);\n \t\tif (!bitmap)\n@@ -246,7 +246,7 @@ static int load_bitmap_entries_v1(struct bitmap_index *index)\n \t\t}\n \n \t\trecent_bitmaps[i % MAX_XOR_OFFSET] = store_bitmap(\n-\t\t\tindex, bitmap, sha1, xor_bitmap, flags);\n+\t\t\tindex, bitmap, oid.hash, xor_bitmap, flags);\n \t}\n \n \treturn 0;\n@@ -625,7 +625,7 @@ static void show_objects_for_type(\n \t\teword_t word = objects->words[i] & filter;\n \n \t\tfor (offset = 0; offset < BITS_IN_WORD; ++offset) {\n-\t\t\tconst unsigned char *sha1;\n+\t\t\tstruct object_id oid;\n \t\t\tstruct revindex_entry *entry;\n \t\t\tuint32_t hash = 0;\n \n@@ -638,12 +638,12 @@ static void show_objects_for_type(\n \t\t\t\tcontinue;\n \n \t\t\tentry = &bitmap_git.reverse_index->revindex[pos + offset];\n-\t\t\tsha1 = nth_packed_object_sha1(bitmap_git.pack, entry->nr);\n+\t\t\tnth_packed_object_oid(bitmap_git.pack, &oid, entry->nr);\n \n \t\t\tif (bitmap_git.hashes)\n \t\t\t\thash = ntohl(bitmap_git.hashes[entry->nr]);\n \n-\t\t\tshow_reach(sha1, object_type, 0, hash, bitmap_git.pack, entry->offset);\n+\t\t\tshow_reach(oid.hash, object_type, 0, hash, bitmap_git.pack, entry->offset);\n \t\t}\n \n \t\tpos += BITS_IN_WORD;\n@@ -783,15 +783,15 @@ int reuse_partial_packfile_from_bitmap(struct packed_git **packfile,\n \n #ifdef GIT_BITMAP_DEBUG\n \t{\n-\t\tconst unsigned char *sha1;\n+\t\tstruct object_id oid;\n \t\tstruct revindex_entry *entry;\n \n \t\tentry = &bitmap_git.reverse_index->revindex[reuse_objects];\n-\t\tsha1 = nth_packed_object_sha1(bitmap_git.pack, entry->nr);\n+\t\tnth_packed_object_oid(bitmap_git.pack, &oid, entry->nr);\n \n \t\tfprintf(stderr, \"Failed to reuse at %d (%016llx)\\n\",\n \t\t\treuse_objects, result->words[i]);\n-\t\tfprintf(stderr, \" %s\\n\", sha1_to_hex(sha1));\n+\t\tfprintf(stderr, \" %s\\n\", oid_to_hex(&oid));\n \t}\n #endif\n \n@@ -1041,13 +1041,13 @@ int rebuild_existing_bitmaps(struct packing_data *mapping,\n \treposition = xcalloc(num_objects, sizeof(uint32_t));\n \n \tfor (i = 0; i < num_objects; ++i) {\n-\t\tconst unsigned char *sha1;\n+\t\tstruct object_id oid;\n \t\tstruct revindex_entry *entry;\n \t\tstruct object_entry *oe;\n \n \t\tentry = &bitmap_git.reverse_index->revindex[i];\n-\t\tsha1 = nth_packed_object_sha1(bitmap_git.pack, entry->nr);\n-\t\toe = packlist_find(mapping, sha1, NULL);\n+\t\tnth_packed_object_oid(bitmap_git.pack, &oid, entry->nr);\n+\t\toe = packlist_find(mapping, oid.hash, NULL);\n \n \t\tif (oe)\n \t\t\treposition[i] = oe->in_pack_pos + 1;\ndiff --git a/pack-check.c b/pack-check.c\nindex 63a595c..f06a227 100644\n--- a/pack-check.c\n+++ b/pack-check.c\n@@ -5,7 +5,7 @@\n \n struct idx_entry {\n \toff_t                offset;\n-\tconst unsigned char *sha1;\n+\tstruct object_id oid;\n \tunsigned int nr;\n };\n \n@@ -93,8 +93,7 @@ static int verify_packfile(struct packed_git *p,\n \tentries[nr_objects].offset = pack_sig_ofs;\n \t/* first sort entries by pack offset, since unpacking them is more efficient that way */\n \tfor (i = 0; i < nr_objects; i++) {\n-\t\tentries[i].sha1 = nth_packed_object_sha1(p, i);\n-\t\tif (!entries[i].sha1)\n+\t\tif (nth_packed_object_oid(p, &entries[i].oid, i))\n \t\t\tdie(\"internal error pack-check nth-packed-object\");\n \t\tentries[i].offset = nth_packed_object_offset(p, i);\n \t\tentries[i].nr = i;\n@@ -113,20 +112,20 @@ static int verify_packfile(struct packed_git *p,\n \t\t\tif (check_pack_crc(p, w_curs, offset, len, nr))\n \t\t\t\terr = error(\"index CRC mismatch for object %s \"\n \t\t\t\t\t    \"from %s at offset %\"PRIuMAX\"\",\n-\t\t\t\t\t    sha1_to_hex(entries[i].sha1),\n+\t\t\t\t\t    oid_to_hex(&entries[i].oid),\n \t\t\t\t\t    p->pack_name, (uintmax_t)offset);\n \t\t}\n \t\tdata = unpack_entry(p, entries[i].offset, &type, &size);\n \t\tif (!data)\n \t\t\terr = error(\"cannot unpack %s from %s at offset %\"PRIuMAX\"\",\n-\t\t\t\t    sha1_to_hex(entries[i].sha1), p->pack_name,\n+\t\t\t\t    oid_to_hex(&entries[i].oid), p->pack_name,\n \t\t\t\t    (uintmax_t)entries[i].offset);\n-\t\telse if (check_sha1_signature(entries[i].sha1, data, size, typename(type)))\n+\t\telse if (check_sha1_signature(entries[i].oid.hash, data, size, typename(type)))\n \t\t\terr = error(\"packed %s from %s is corrupt\",\n-\t\t\t\t    sha1_to_hex(entries[i].sha1), p->pack_name);\n+\t\t\t\t    oid_to_hex(&entries[i].oid), p->pack_name);\n \t\telse if (fn) {\n \t\t\tint eaten = 0;\n-\t\t\tfn(entries[i].sha1, type, size, data, &eaten);\n+\t\t\tfn(entries[i].oid.hash, type, size, data, &eaten);\n \t\t\tif (eaten)\n \t\t\t\tdata = NULL;\n \t\t}\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 346f468..ff06ec5 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1810,35 +1810,39 @@ static off_t get_delta_base(struct packed_git *p,\n }\n \n /*\n- * Like get_delta_base above, but we return the sha1 instead of the pack\n- * offset. This means it is cheaper for REF deltas (we do not have to do\n- * the final object lookup), but more expensive for OFS deltas (we\n- * have to load the revidx to convert the offset back into a sha1).\n+ * Like get_delta_base above, but we store the base into base instead of the\n+ * pack offset. This means it is cheaper for REF deltas (we do not have to\n+ * do the final object lookup), but more expensive for OFS deltas (we have\n+ * to load the revidx to convert the offset back into a sha1).  Return 0 on\n+ * success.\n  */\n-static const unsigned char *get_delta_base_sha1(struct packed_git *p,\n+static int get_delta_base_oid(struct packed_git *p, struct object_id *base,\n \t\t\t\t\t\tstruct pack_window **w_curs,\n \t\t\t\t\t\toff_t curpos,\n \t\t\t\t\t\tenum object_type type,\n \t\t\t\t\t\toff_t delta_obj_offset)\n {\n \tif (type == OBJ_REF_DELTA) {\n-\t\tunsigned char *base = use_pack(p, w_curs, curpos, NULL);\n-\t\treturn base;\n+\t\tunsigned char *sha1 = use_pack(p, w_curs, curpos, NULL);\n+\t\tif (!sha1)\n+\t\t\treturn -1;\n+\t\thashcpy(base->hash, sha1);\n+\t\treturn 0;\n \t} else if (type == OBJ_OFS_DELTA) {\n \t\tstruct revindex_entry *revidx;\n \t\toff_t base_offset = get_delta_base(p, w_curs, &curpos,\n \t\t\t\t\t\t   type, delta_obj_offset);\n \n \t\tif (!base_offset)\n-\t\t\treturn NULL;\n+\t\t\treturn -1;\n \n \t\trevidx = find_pack_revindex(p, base_offset);\n \t\tif (!revidx)\n-\t\t\treturn NULL;\n+\t\t\treturn -1;\n \n-\t\treturn nth_packed_object_sha1(p, revidx->nr);\n+\t\treturn nth_packed_object_oid(p, base, revidx->nr);\n \t} else\n-\t\treturn NULL;\n+\t\treturn -1;\n }\n \n int unpack_object_header(struct packed_git *p,\n@@ -1871,13 +1875,13 @@ static int retry_bad_packed_offset(struct packed_git *p, off_t obj_offset)\n {\n \tint type;\n \tstruct revindex_entry *revidx;\n-\tconst unsigned char *sha1;\n+\tstruct object_id oid;\n \trevidx = find_pack_revindex(p, obj_offset);\n \tif (!revidx)\n \t\treturn OBJ_BAD;\n-\tsha1 = nth_packed_object_sha1(p, revidx->nr);\n-\tmark_bad_packed_object(p, sha1);\n-\ttype = sha1_object_info(sha1, NULL);\n+\tnth_packed_object_oid(p, &oid, revidx->nr);\n+\tmark_bad_packed_object(p, oid.hash);\n+\ttype = sha1_object_info(oid.hash, NULL);\n \tif (type <= OBJ_NONE)\n \t\treturn OBJ_BAD;\n \treturn type;\n@@ -2000,16 +2004,15 @@ static int packed_object_info(struct packed_git *p, off_t obj_offset,\n \n \tif (oi->delta_base_sha1) {\n \t\tif (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {\n-\t\t\tconst unsigned char *base;\n+\t\t\tstruct object_id base;\n \n-\t\t\tbase = get_delta_base_sha1(p, &w_curs, curpos,\n-\t\t\t\t\t\t   type, obj_offset);\n-\t\t\tif (!base) {\n+\t\t\tif (get_delta_base_oid(p, &base, &w_curs, curpos,\n+\t\t\t\t\t\ttype, obj_offset)) {\n \t\t\t\ttype = OBJ_BAD;\n \t\t\t\tgoto out;\n \t\t\t}\n \n-\t\t\thashcpy(oi->delta_base_sha1, base);\n+\t\t\thashcpy(oi->delta_base_sha1, base.hash);\n \t\t} else\n \t\t\thashclr(oi->delta_base_sha1);\n \t}\n@@ -2239,11 +2242,11 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,\n \t\t\tstruct revindex_entry *revidx = find_pack_revindex(p, obj_offset);\n \t\t\tunsigned long len = revidx[1].offset - obj_offset;\n \t\t\tif (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {\n-\t\t\t\tconst unsigned char *sha1 =\n-\t\t\t\t\tnth_packed_object_sha1(p, revidx->nr);\n+\t\t\t\tstruct object_id oid;\n+\t\t\t\tnth_packed_object_oid(p, &oid, revidx->nr);\n \t\t\t\terror(\"bad packed object CRC for %s\",\n-\t\t\t\t      sha1_to_hex(sha1));\n-\t\t\t\tmark_bad_packed_object(p, sha1);\n+\t\t\t\t      oid_to_hex(&oid));\n+\t\t\t\tmark_bad_packed_object(p, oid.hash);\n \t\t\t\tunuse_pack(&w_curs);\n \t\t\t\treturn NULL;\n \t\t\t}\n@@ -2325,16 +2328,17 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,\n \t\t\t * of a corrupted pack, and is better than failing outright.\n \t\t\t */\n \t\t\tstruct revindex_entry *revidx;\n-\t\t\tconst unsigned char *base_sha1;\n \t\t\trevidx = find_pack_revindex(p, obj_offset);\n \t\t\tif (revidx) {\n-\t\t\t\tbase_sha1 = nth_packed_object_sha1(p, revidx->nr);\n+\t\t\t\tstruct object_id base_oid;\n+\n+\t\t\t\tnth_packed_object_oid(p, &base_oid, revidx->nr);\n \t\t\t\terror(\"failed to read delta base object %s\"\n \t\t\t\t      \" at offset %\"PRIuMAX\" from %s\",\n-\t\t\t\t      sha1_to_hex(base_sha1), (uintmax_t)obj_offset,\n+\t\t\t\t      oid_to_hex(&base_oid), (uintmax_t)obj_offset,\n \t\t\t\t      p->pack_name);\n-\t\t\t\tmark_bad_packed_object(p, base_sha1);\n-\t\t\t\tbase = read_object(base_sha1, &type, &base_size);\n+\t\t\t\tmark_bad_packed_object(p, base_oid.hash);\n+\t\t\t\tbase = read_object(base_oid.hash, &type, &base_size);\n \t\t\t}\n \t\t}\n \n@@ -2385,24 +2389,25 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,\n \treturn data;\n }\n \n-const unsigned char *nth_packed_object_sha1(struct packed_git *p,\n-\t\t\t\t\t    uint32_t n)\n+int nth_packed_object_oid(struct packed_git *p, struct object_id *oid,\n+\t\t\t  uint32_t n)\n {\n \tconst unsigned char *index = p->index_data;\n \tif (!index) {\n \t\tif (open_pack_index(p))\n-\t\t\treturn NULL;\n+\t\t\treturn -1;\n \t\tindex = p->index_data;\n \t}\n \tif (n >= p->num_objects)\n-\t\treturn NULL;\n+\t\treturn -1;\n \tindex += 4 * 256;\n \tif (p->index_version == 1) {\n-\t\treturn index + 24 * n + 4;\n+\t\thashcpy(oid->hash, index + 24 * n + 4);\n \t} else {\n \t\tindex += 8;\n-\t\treturn index + 20 * n;\n+\t\thashcpy(oid->hash, index + 20 * n);\n \t}\n+\treturn 0;\n }\n \n off_t nth_packed_object_offset(const struct packed_git *p, uint32_t n)\n@@ -3555,13 +3560,13 @@ static int for_each_object_in_pack(struct packed_git *p, each_packed_object_fn c\n \tint r = 0;\n \n \tfor (i = 0; i < p->num_objects; i++) {\n-\t\tconst unsigned char *sha1 = nth_packed_object_sha1(p, i);\n+\t\tstruct object_id oid;\n \n-\t\tif (!sha1)\n+\t\tif (nth_packed_object_oid(p, &oid, i))\n \t\t\treturn error(\"unable to get sha1 of object %u in %s\",\n \t\t\t\t     i, p->pack_name);\n \n-\t\tr = cb(sha1, p, i, data);\n+\t\tr = cb(oid.hash, p, i, data);\n \t\tif (r)\n \t\t\tbreak;\n \t}\ndiff --git a/sha1_name.c b/sha1_name.c\nindex f542dba..680b1b9 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -140,18 +140,18 @@ static void unique_in_pack(int len,\n \t\t\t   struct disambiguate_state *ds)\n {\n \tuint32_t num, last, i, first = 0;\n-\tconst unsigned char *current = NULL;\n+\tstruct object_id current;\n \n \topen_pack_index(p);\n \tnum = p->num_objects;\n \tlast = num;\n \twhile (first < last) {\n \t\tuint32_t mid = (first + last) / 2;\n-\t\tconst unsigned char *current;\n+\t\tstruct object_id current;\n \t\tint cmp;\n \n-\t\tcurrent = nth_packed_object_sha1(p, mid);\n-\t\tcmp = hashcmp(bin_pfx, current);\n+\t\tnth_packed_object_oid(p, &current, mid);\n+\t\tcmp = hashcmp(bin_pfx, current.hash);\n \t\tif (!cmp) {\n \t\t\tfirst = mid;\n \t\t\tbreak;\n@@ -169,10 +169,10 @@ static void unique_in_pack(int len,\n \t * 0, 1 or more objects that actually match(es).\n \t */\n \tfor (i = first; i < num && !ds->ambiguous; i++) {\n-\t\tcurrent = nth_packed_object_sha1(p, i);\n-\t\tif (!match_sha(len, bin_pfx, current))\n+\t\tnth_packed_object_oid(p, &current, i);\n+\t\tif (!match_sha(len, bin_pfx, current.hash))\n \t\t\tbreak;\n-\t\tupdate_candidates(ds, current);\n+\t\tupdate_candidates(ds, current.hash);\n \t}\n }\n \n-- \nbrian m. carlson / brian with sandals: Houston, Texas, US\n+1 832 623 2791 | http://www.crustytoothpaste.net/~bmc | My opinion only\nOpenPGP: RSA v4 4096b: 88AC E9B2 9196 305B A994 7552 F1BA 225C 0223 B187\n"},{"id":"263001","messageId":"20150605094545.GB11855@peff.net","threadId":"39531","inReplyTo":"20150605014120.GE305479@vauxhall.crustytoothpaste.net","subject":"Re: Pack files, standards compliance, and efficiency","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-06-05T09:45:45Z","receivedAt":"2015-06-05T09:45:45Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jun 05, 2015 at 01:41:21AM +0000, brian m. carlson wrote:\n\n> However, with the object_id conversion, we run into a problem: casting\n> those unsigned char * values into struct object_id * values is not\n> allowed by the C standard.  There are two possible solutions: copying;\n> and the just-do-it solution, where we cast and hope for the best.\n\nI'm not sure if it does violate the standard. The address of the first\nelement of a struct is guaranteed to match the address of the struct\nitself. The object_id.hash member is an array of unsigned char, so there\nare no alignment issues. It might run afoul of rules about casting\nbetween pointer types (i.e., pointers for all types are not guaranteed\nto be the same size). The standard dictates that \"char *\" and \"void *\"\nare the same size, and big enough to hold a pointer to anything, so I\nthink it might even be OK.\n\nBut I'm not even sure that line of thinking is all that interesting.\nEven if we are violating some dark corner of the standard, this\ndefinitely falls into the \"it's useful and works on all sane machines\"\ncategory. We also do much worse things with struct-casting mmap'd data\nelsewhere (e.g., see the use of \"struct pack_header\"). It works fine in\npractice as long as you are careful about alignment and padding issues.\n\nSo my vote would be to retain the cast. This is very low-level,\nperformance-sensitive code. I did some very naive timings and didn't see\nany measurable change from your patch, but I also don't think we are\nseeing a real portability benefit to moving to the copy, so I'd prefer\nto keep the status quo.\n\n> It looks like we use the latter in nth_packed_object_offset, where we\n> cast an unsigned char * value to uint32_t *, which is clearly not\n> allowed.\n\nYes, this one is definitely dubious by the standard. However, it works\nin practice because the index format is designed to be 4-byte aligned.\nBy contrast, the .bitmap format is not, and we have to use get_be32, etc\n(which is really not the end of the world, but I do not think there is\nany real reason to change the .idx code at this point).\n\n> I'm to the point where I need to make a decision on how to\n> proceed, and I've included a patch with the copying conversion of\n> nth_packed_object_sha1 below for comparison.  The casting solution is\n> obviously more straightforward.  I haven't tested either implementation\n> for performance.\n\nThe test I did was just running \"git rev-list --use-bitmap-index --count\nHEAD\" on a bitmapped linux.git repo. That's where I'd expect it to show\nthe most, because we are not doing much other work. But I think even\nstill, the timing is dominated by loading the bitmap file.\n\n-Peff\n"},{"id":"263002","messageId":"CACsJy8CnWo=s1onqY33K+DwFmB1baQ-uwu9Fbwm+UB30kDTwQw@mail.gmail.com","threadId":"39531","inReplyTo":"20150605094545.GB11855@peff.net","subject":"Re: Pack files, standards compliance, and efficiency","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2015-06-05T10:14:25Z","receivedAt":"2015-06-05T10:14:25Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Jun 5, 2015 at 4:45 PM, Jeff King <peff@peff.net> wrote:\n> On Fri, Jun 05, 2015 at 01:41:21AM +0000, brian m. carlson wrote:\n>\n>> However, with the object_id conversion, we run into a problem: casting\n>> those unsigned char * values into struct object_id * values is not\n>> allowed by the C standard.  There are two possible solutions: copying;\n>> and the just-do-it solution, where we cast and hope for the best.\n>\n> I'm not sure if it does violate the standard. The address of the first\n> element of a struct is guaranteed to match the address of the struct\n> itself. The object_id.hash member is an array of unsigned char, so there\n> are no alignment issues. It might run afoul of rules about casting\n> between pointer types (i.e., pointers for all types are not guaranteed\n> to be the same size). The standard dictates that \"char *\" and \"void *\"\n> are the same size, and big enough to hold a pointer to anything, so I\n> think it might even be OK.\n>\n> But I'm not even sure that line of thinking is all that interesting.\n> Even if we are violating some dark corner of the standard, this\n> definitely falls into the \"it's useful and works on all sane machines\"\n> category. We also do much worse things with struct-casting mmap'd data\n> elsewhere (e.g., see the use of \"struct pack_header\"). It works fine in\n> practice as long as you are careful about alignment and padding issues.\n>\n> So my vote would be to retain the cast. This is very low-level,\n> performance-sensitive code. I did some very naive timings and didn't see\n> any measurable change from your patch, but I also don't think we are\n> seeing a real portability benefit to moving to the copy, so I'd prefer\n> to keep the status quo.\n\nI'm more concerned about breaking object_id abstraction than C\nstandard. Let's think a bit about future. I suppose we need to support\nboth sha-1 and sha-512, at least at the source code level. That might\nmake casting tricky. Maybe we should deal with it now instead of\ndelaying because if the final solution is vastly different, we may be\nredoing this conversion again. In any case, if we cast, we should make\nit grep-able (maybe hide the casting in a macro so we can grep the\nmacro's name) so we can examine them when the time comes for us to\nmove away from sha-1.\n-- \nDuy\n"},{"id":"263003","messageId":"20150605103639.GB19033@peff.net","threadId":"39531","inReplyTo":"CACsJy8CnWo=s1onqY33K+DwFmB1baQ-uwu9Fbwm+UB30kDTwQw@mail.gmail.com","subject":"Re: Pack files, standards compliance, and efficiency","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-06-05T10:36:39Z","receivedAt":"2015-06-05T10:36:39Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jun 05, 2015 at 05:14:25PM +0700, Duy Nguyen wrote:\n\n> I'm more concerned about breaking object_id abstraction than C\n> standard. Let's think a bit about future. I suppose we need to support\n> both sha-1 and sha-512, at least at the source code level.\n\nI think that's going to be a much bigger issue, because we are casting\nout of a defined, on-disk data structure here. So I'd rather defer any\ncode changes around this until we see what the new data structure (and\nthe new code) look like.\n\n> That might make casting tricky. Maybe we should deal with it now\n> instead of delaying because if the final solution is vastly different,\n> we may be redoing this conversion again. In any case, if we cast, we\n> should make it grep-able (maybe hide the casting in a macro so we can\n> grep the macro's name) so we can examine them when the time comes for\n> us to move away from sha-1.\n\nI think that is sensible. Something like:\n\n  #define SHA1_TO_OBJID(sha1) ((struct object_id *)sha1)\n\nwould probably be a good start.\n\n-Peff\n"},{"id":"263012","messageId":"CACsJy8C6E0orN1a6WbkFCiyBtfp94y4XMLS3-i=_6s4WADicCw@mail.gmail.com","threadId":"39531","inReplyTo":"20150605103639.GB19033@peff.net","subject":"Re: Pack files, standards compliance, and efficiency","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2015-06-05T13:24:55Z","receivedAt":"2015-06-05T13:24:55Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Jun 5, 2015 at 5:36 PM, Jeff King <peff@peff.net> wrote:\n> On Fri, Jun 05, 2015 at 05:14:25PM +0700, Duy Nguyen wrote:\n>\n>> I'm more concerned about breaking object_id abstraction than C\n>> standard. Let's think a bit about future. I suppose we need to support\n>> both sha-1 and sha-512, at least at the source code level.\n>\n> I think that's going to be a much bigger issue, because we are casting\n> out of a defined, on-disk data structure here. So I'd rather defer any\n> code changes around this until we see what the new data structure (and\n> the new code) look like.\n\nYeah.. I don't have a clear idea what it would look like either. What\nI didn't think of is this object_id may turn around and influence how\nnew on-disk format looks like, to make it easier to work with\nobject_id. So there's an option..\n\n>> That might make casting tricky. Maybe we should deal with it now\n>> instead of delaying because if the final solution is vastly different,\n>> we may be redoing this conversion again. In any case, if we cast, we\n>> should make it grep-able (maybe hide the casting in a macro so we can\n>> grep the macro's name) so we can examine them when the time comes for\n>> us to move away from sha-1.\n>\n> I think that is sensible. Something like:\n>\n>   #define SHA1_TO_OBJID(sha1) ((struct object_id *)sha1)\n>\n> would probably be a good start.\n\nYep.\n-- \nDuy\n"},{"id":"263020","messageId":"5571BEA0.2080305@alum.mit.edu","threadId":"39531","inReplyTo":"20150605094545.GB11855@peff.net","subject":"Re: Pack files, standards compliance, and efficiency","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2015-06-05T15:22:08Z","receivedAt":"2015-06-05T15:22:08Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 06/05/2015 11:45 AM, Jeff King wrote:\n> On Fri, Jun 05, 2015 at 01:41:21AM +0000, brian m. carlson wrote:\n> \n>> However, with the object_id conversion, we run into a problem: casting\n>> those unsigned char * values into struct object_id * values is not\n>> allowed by the C standard.  There are two possible solutions: copying;\n>> and the just-do-it solution, where we cast and hope for the best.\n> \n> [...]\n> \n> But I'm not even sure that line of thinking is all that interesting.\n> Even if we are violating some dark corner of the standard, this\n> definitely falls into the \"it's useful and works on all sane machines\"\n> category. We also do much worse things with struct-casting mmap'd data\n> elsewhere (e.g., see the use of \"struct pack_header\"). It works fine in\n> practice as long as you are careful about alignment and padding issues.\n> \n> So my vote would be to retain the cast. This is very low-level,\n> performance-sensitive code. I did some very naive timings and didn't see\n> any measurable change from your patch, but I also don't think we are\n> seeing a real portability benefit to moving to the copy, so I'd prefer\n> to keep the status quo.\n\nI don't know that there would necessarily be problems, but I would worry\nabout code involving structure assignment. For example, suppose the\nfollowing snippet:\n\n    void f(struct object_id *oid)\n    {\n        struct object_id oid_copy = *oid;\n        /* ... */\n    }\n\nThe compiler is allowed to implement the copy using instructions that\nrely on proper alignment. Such code would fail if oid is not properly\naligned.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"263035","messageId":"xmqqy4jyrtr0.fsf@gitster.dls.corp.google.com","threadId":"39531","inReplyTo":"CACsJy8CnWo=s1onqY33K+DwFmB1baQ-uwu9Fbwm+UB30kDTwQw@mail.gmail.com","subject":"Re: Pack files, standards compliance, and efficiency","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-06-05T16:43:15Z","receivedAt":"2015-06-05T16:43:15Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Duy Nguyen <pclouds@gmail.com> writes:\n\n> I'm more concerned about breaking object_id abstraction than C\n> standard. Let's think a bit about future. I suppose we need to support\n> both sha-1 and sha-512, at least at the source code level. That might\n> make casting tricky.\n\nIf we support both, the code that writes today's objects should be\naware that they are writing today's uchar[20] (or char[40]) object\nnames, no?  I do not view crusty's series as a step to change the\nhash, but more about identifying the arrays used as object names and\ndifferentiating from other char and uchar arrays, so that it will\nhelp us to identify the codepaths that needs to be updated when we\nchange the hash function.  Ideally, the result of applying his\nseries should produce the binaries identical to today's code that\nuses uchar[20] as object names.\n\nI do not see any \"breaking object-id abstraction\" involved when\nisolated low-level code that writes things to and reads things from\nthe disk or core knew that the hash we happen to use is uchar[20],\nand it is perfectly fine if casting lets us safely take advantage of\nthat knowledge.  It becomes a problem when we peek into the struct\nobject_id to find address of sha1[20] and then start passing that\nlow level address around widely, but I do not think this thread of\ndiscussion has risks to go into that direction.\n"},{"id":"263058","messageId":"20150605194200.GB356121@vauxhall.crustytoothpaste.net","threadId":"39531","inReplyTo":"5571BEA0.2080305@alum.mit.edu","subject":"Re: Pack files, standards compliance, and efficiency","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2015-06-05T19:42:00Z","receivedAt":"2015-06-05T19:42:00Z","isPatch":false,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"On Fri, Jun 05, 2015 at 05:22:08PM +0200, Michael Haggerty wrote:\n> I don't know that there would necessarily be problems, but I would worry\n> about code involving structure assignment. For example, suppose the\n> following snippet:\n> \n>     void f(struct object_id *oid)\n>     {\n>         struct object_id oid_copy = *oid;\n>         /* ... */\n>     }\n> \n> The compiler is allowed to implement the copy using instructions that\n> rely on proper alignment. Such code would fail if oid is not properly\n> aligned.\n\nWe use oidcpy which doesn't use object assignment.  I brought that up\npreviously, and Junio was opposed to doing *dest = *src.  So I don't\nthink this ends up being an issue.\n-- \nbrian m. carlson / brian with sandals: Houston, Texas, US\n+1 832 623 2791 | http://www.crustytoothpaste.net/~bmc | My opinion only\nOpenPGP: RSA v4 4096b: 88AC E9B2 9196 305B A994 7552 F1BA 225C 0223 B187\n"},{"id":"263065","messageId":"20150605195958.GC356121@vauxhall.crustytoothpaste.net","threadId":"39531","inReplyTo":"20150605103639.GB19033@peff.net","subject":"Re: Pack files, standards compliance, and efficiency","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2015-06-05T19:59:58Z","receivedAt":"2015-06-05T19:59:58Z","isPatch":false,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"On Fri, Jun 05, 2015 at 06:36:39AM -0400, Jeff King wrote:\n> On Fri, Jun 05, 2015 at 05:14:25PM +0700, Duy Nguyen wrote:\n> \n> > I'm more concerned about breaking object_id abstraction than C\n> > standard. Let's think a bit about future. I suppose we need to support\n> > both sha-1 and sha-512, at least at the source code level.\n> \n> I think that's going to be a much bigger issue, because we are casting\n> out of a defined, on-disk data structure here. So I'd rather defer any\n> code changes around this until we see what the new data structure (and\n> the new code) look like.\n\nMy plan is to change the data as little as possible.  I want to set\ncore.repositoryformatversion to 1 and create core.hashalgorithm =\nsha-256 or sha-512 or whatever.  If core.repositoryformatversion is 0,\nthen core.hashalgorithm is assumed to be sha-1.\n\nPacks will get a version number bump to 5 and acquire a 32-byte\nNUL-padded algorithm descriptor after the version field.  The network\nprotocol will acquire a capability hash=sha-256.  git init will get a\n--hash option, without which it will initialize SHA-1.\n\nI don't intend to change the contents of struct object_id any, since I\ndon't intend to allow mixed hashes in one repository (git fast-import is\nyour friend).  I plan to read the format version and hash algorithm as\nsoon as possible after startup and initialize a variable with the hash\nlength.  The length of the struct's hash member will expand to handle\nwhatever the maximum supported hash size is, but data will only be\ncompared and modified up to the hash length of the appropriate\nalgorithm.\n\nThis does lead to the possibility of increased memory usage, which is\nwhy I plan to initially only support SHA-512/256.  It's 32 bytes, like\nSHA-256, but it performs much better on 64-bit systems (SHA-1: 291\nMiB/s, SHA-256: 144 MiB/s, SHA-512/256: 242 MiB/s) for messages ≥ 55\nbytes, and most systems these days are 64 bit.\n\nThat's what I've been thinking, at least, but if people have better\nideas, I'm open to hearing them.\n-- \nbrian m. carlson / brian with sandals: Houston, Texas, US\n+1 832 623 2791 | http://www.crustytoothpaste.net/~bmc | My opinion only\nOpenPGP: RSA v4 4096b: 88AC E9B2 9196 305B A994 7552 F1BA 225C 0223 B187\n"},{"id":"263067","messageId":"5572008F.6030203@alum.mit.edu","threadId":"39531","inReplyTo":"20150605194200.GB356121@vauxhall.crustytoothpaste.net","subject":"Re: Pack files, standards compliance, and efficiency","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2015-06-05T20:03:27Z","receivedAt":"2015-06-05T20:03:27Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 06/05/2015 09:42 PM, brian m. carlson wrote:\n> On Fri, Jun 05, 2015 at 05:22:08PM +0200, Michael Haggerty wrote:\n>> I don't know that there would necessarily be problems, but I\n>> would worry about code involving structure assignment. For\n>> example, suppose the following snippet:\n>> \n>> void f(struct object_id *oid) { struct object_id oid_copy =\n>> *oid; /* ... */ }\n>> \n>> The compiler is allowed to implement the copy using instructions\n>> that rely on proper alignment. Such code would fail if oid is not\n>> properly aligned.\n> \n> We use oidcpy which doesn't use object assignment.  I brought that\n> up previously, and Junio was opposed to doing *dest = *src.  So I\n> don't think this ends up being an issue.\n\nSorry for overlooking (or forgetting :-( ) that discussion. Indeed,\nthat would allay my worry.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\n"}]}