{"thread":{"id":"53131","subject":"[PATCH 0/7] oid_array cleanups","startedAt":"2020-03-30T14:02:50Z","lastAt":"2020-04-15T00:35:54Z","messageCount":12,"participants":["Jeff King","Taylor Blau"],"isPatch":true,"patchVersion":1,"patchTotal":7},"messages":[{"id":"394355","messageId":"20200330140247.GA476088@coredump.intra.peff.net","threadId":"53131","inReplyTo":null,"subject":"[PATCH 0/7] oid_array cleanups","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-30T14:02:47Z","receivedAt":"2020-03-30T14:02:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"I recently encountered a repo in the wild that had over 2^31 objects,\nand found that cat-file barfed:\n\n  $ git cat-file --batch-all-objects --batch-check\n  fatal: size_t overflow: 32 * 18446744071562067968\n\nThe issue is that we use an \"int\" to store the count and the allocation.\nFortunately our st_mult() protection kicks in before we end up with an\nundersized buffer, so this shouldn't be dangerous. And while I'd argue\nthat having that many objects is probably silly and likely to cause\nother problems, I'd just as soon we kept our allocating code as robust\nas possible.\n\nThe first patch is the actual fix, followed by some related type\ncleanup. The rest of it is just leftovers from the\ns/sha1_array/oid_array/ transition a few years back.\n\n  [1/7]: oid_array: use size_t for count and allocation\n  [2/7]: oid_array: use size_t for iteration\n  [3/7]: oid_array: rename source file from sha1-array\n  [4/7]: test-tool: rename sha1-array to oid-array\n  [5/7]: bisect: stop referring to sha1_array\n  [6/7]: ref-filter: stop referring to \"sha1 array\"\n  [7/7]: oidset: stop referring to sha1-array\n\n Makefile                                         |  4 ++--\n bisect.c                                         |  8 ++++----\n builtin/cat-file.c                               |  2 +-\n builtin/diff.c                                   |  2 +-\n builtin/fetch-pack.c                             |  2 +-\n builtin/pack-objects.c                           |  2 +-\n builtin/pull.c                                   |  2 +-\n builtin/receive-pack.c                           |  2 +-\n builtin/send-pack.c                              |  2 +-\n builtin/tag.c                                    |  2 +-\n cache.h                                          |  2 +-\n combine-diff.c                                   |  2 +-\n connect.c                                        |  2 +-\n delta-islands.c                                  |  2 +-\n fetch-pack.c                                     |  2 +-\n object-store.h                                   |  2 +-\n sha1-array.c => oid-array.c                      | 10 +++++-----\n sha1-array.h => oid-array.h                      |  6 +++---\n oidset.h                                         |  2 +-\n parse-options-cb.c                               |  2 +-\n ref-filter.c                                     |  7 +++----\n ref-filter.h                                     |  2 +-\n remote-curl.c                                    |  2 +-\n send-pack.c                                      |  2 +-\n sha1-name.c                                      |  2 +-\n shallow.c                                        |  2 +-\n submodule.c                                      |  2 +-\n t/helper/{test-sha1-array.c => test-oid-array.c} |  8 ++++----\n t/helper/test-tool.c                             |  2 +-\n t/helper/test-tool.h                             |  2 +-\n t/t0064-sha1-array.sh                            | 16 ++++++++--------\n transport.c                                      |  2 +-\n 32 files changed, 54 insertions(+), 55 deletions(-)\n rename sha1-array.c => oid-array.c (93%)\n rename sha1-array.h => oid-array.h (97%)\n rename t/helper/{test-sha1-array.c => test-oid-array.c} (83%)\n\n"},{"id":"394356","messageId":"20200330140309.GA2456038@coredump.intra.peff.net","threadId":"53131","inReplyTo":"20200330140247.GA476088@coredump.intra.peff.net","subject":"[PATCH 1/7] oid_array: use size_t for count and allocation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-30T14:03:09Z","receivedAt":"2020-03-30T14:03:12Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The oid_array object uses an \"int\" to store the number of items and the\nallocated size. It's rather unlikely for somebody to have more than 2^31\nobjects in a repository (the sha1's alone would be 40GB!), but if they\ndo, we'd overflow our alloc variable.\n\nYou can reproduce this case with something like:\n\n  git init repo\n  cd repo\n\n  # make a pack with 2^24 objects\n  perl -e '\n    my $nr = 2**24;\n\n    for (my $i = 0; $i < $nr; $i++) {\n\t    print \"blob\\n\";\n\t    print \"data 4\\n\";\n\t    print pack(\"N\", $i);\n    }\n  ' | git fast-import\n\n  # now make 256 copies of it; most of these objects will be duplicates,\n  # but oid_array doesn't de-dup until all values are read and it can\n  # sort the result.\n  cd .git/objects/pack/\n  pack=$(echo *.pack)\n  idx=$(echo *.idx)\n  for i in $(seq 0 255); do\n    # no need to waste disk space\n    ln \"$pack\" \"pack-extra-$i.pack\"\n    ln \"$idx\" \"pack-extra-$i.idx\"\n  done\n\n  # and now force an oid_array to store all of it\n  git cat-file --batch-all-objects --batch-check\n\nwhich results in:\n\n  fatal: size_t overflow: 32 * 18446744071562067968\n\nSo the good news is that st_mult() sees the problem (the large number is\nbecause our int wraps negative, and then that gets cast to a size_t),\ndoing the job it was meant to: bailing in crazy situations rather than\ncausing an undersized buffer.\n\nBut we should avoid hitting this case at all, and instead limit\nourselves based on what malloc() is willing to give us. We can easily do\nthat by switching to size_t.\n\nThe cat-file process above made it to ~120GB virtual set size before the\ninteger overflow (our internal hash storage is 32-bytes now in\npreparation for sha256, so we'd expect ~128GB total needed, plus\npotentially more to copy from one realloc'd block to another)). After\nthis patch (and about 130GB of RAM+swap), it does eventually read in the\nwhole set. No test for obvious reasons.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n sha1-array.h | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/sha1-array.h b/sha1-array.h\nindex dc1bca9c9a..c5e4b9324f 100644\n--- a/sha1-array.h\n+++ b/sha1-array.h\n@@ -49,8 +49,8 @@\n  */\n struct oid_array {\n \tstruct object_id *oid;\n-\tint nr;\n-\tint alloc;\n+\tsize_t nr;\n+\tsize_t alloc;\n \tint sorted;\n };\n \n-- \n2.26.0.597.g7e08ed78ff\n\n"},{"id":"394357","messageId":"20200330140320.GB2456038@coredump.intra.peff.net","threadId":"53131","inReplyTo":"20200330140247.GA476088@coredump.intra.peff.net","subject":"[PATCH 2/7] oid_array: use size_t for iteration","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-30T14:03:20Z","receivedAt":"2020-03-30T14:03:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The previous commit started using size_t for our allocations. There are\nsome iterations that use int or unsigned, though. These aren't dangerous\nwith respect to memory, but they could produce incorrect results.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n sha1-array.c | 6 +++---\n 1 file changed, 3 insertions(+), 3 deletions(-)\n\ndiff --git a/sha1-array.c b/sha1-array.c\nindex 3eeadfede9..bada0c4353 100644\n--- a/sha1-array.c\n+++ b/sha1-array.c\n@@ -46,7 +46,7 @@ int oid_array_for_each(struct oid_array *array,\n \t\t       for_each_oid_fn fn,\n \t\t       void *data)\n {\n-\tint i;\n+\tsize_t i;\n \n \t/* No oid_array_sort() here! See sha1-array.h */\n \n@@ -62,7 +62,7 @@ int oid_array_for_each_unique(struct oid_array *array,\n \t\t\t      for_each_oid_fn fn,\n \t\t\t      void *data)\n {\n-\tint i;\n+\tsize_t i;\n \n \tif (!array->sorted)\n \t\toid_array_sort(array);\n@@ -82,7 +82,7 @@ void oid_array_filter(struct oid_array *array,\n \t\t      for_each_oid_fn want,\n \t\t      void *cb_data)\n {\n-\tunsigned nr = array->nr, src, dst;\n+\tsize_t nr = array->nr, src, dst;\n \tstruct object_id *oids = array->oid;\n \n \tfor (src = dst = 0; src < nr; src++) {\n-- \n2.26.0.597.g7e08ed78ff\n\n"},{"id":"394358","messageId":"20200330140346.GC2456038@coredump.intra.peff.net","threadId":"53131","inReplyTo":"20200330140247.GA476088@coredump.intra.peff.net","subject":"[PATCH 3/7] oid_array: rename source file from sha1-array","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-30T14:03:46Z","receivedAt":"2020-03-30T14:03:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We renamed the actual data structure in 910650d2f8 (Rename sha1_array to\noid_array, 2017-03-31), but the file is still called sha1-array. Besides\nbeing slightly confusing, it makes it more annoying to grep for leftover\noccurrences of \"sha1\" in various files, because the header is included\nin so many places.\n\nLet's complete the transition by renaming the source and header files\n(and fixing up a few comment references).\n\nI kept the \"-\" in the name, as that seems to be our style; cf.\nfc1395f4a4 (sha1_file.c: rename to use dash in file name, 2018-04-10).\nWe also have oidmap.h and oidset.h without any punctuation, but those\nare \"struct oidmap\" and \"struct oidset\" in the code. We _could_ make\nthis \"oidarray\" to match, but somehow it looks uglier to me because of\nthe length of \"array\" (plus it would be a very invasive patch for little\ngain).\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n Makefile                    | 2 +-\n bisect.c                    | 2 +-\n builtin/cat-file.c          | 2 +-\n builtin/diff.c              | 2 +-\n builtin/fetch-pack.c        | 2 +-\n builtin/pack-objects.c      | 2 +-\n builtin/pull.c              | 2 +-\n builtin/receive-pack.c      | 2 +-\n builtin/send-pack.c         | 2 +-\n builtin/tag.c               | 2 +-\n cache.h                     | 2 +-\n combine-diff.c              | 2 +-\n connect.c                   | 2 +-\n delta-islands.c             | 2 +-\n fetch-pack.c                | 2 +-\n object-store.h              | 2 +-\n sha1-array.c => oid-array.c | 4 ++--\n sha1-array.h => oid-array.h | 2 +-\n parse-options-cb.c          | 2 +-\n ref-filter.h                | 2 +-\n remote-curl.c               | 2 +-\n send-pack.c                 | 2 +-\n sha1-name.c                 | 2 +-\n shallow.c                   | 2 +-\n submodule.c                 | 2 +-\n t/helper/test-sha1-array.c  | 2 +-\n transport.c                 | 2 +-\n 27 files changed, 28 insertions(+), 28 deletions(-)\n rename sha1-array.c => oid-array.c (96%)\n rename sha1-array.h => oid-array.h (98%)\n\ndiff --git a/Makefile b/Makefile\nindex ef1ff2228f..abfe5cc29b 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -929,6 +929,7 @@ LIB_OBJS += notes-utils.o\n LIB_OBJS += object.o\n LIB_OBJS += oidmap.o\n LIB_OBJS += oidset.o\n+LIB_OBJS += oid-array.o\n LIB_OBJS += packfile.o\n LIB_OBJS += pack-bitmap.o\n LIB_OBJS += pack-bitmap-write.o\n@@ -978,7 +979,6 @@ LIB_OBJS += sequencer.o\n LIB_OBJS += serve.o\n LIB_OBJS += server-info.o\n LIB_OBJS += setup.o\n-LIB_OBJS += sha1-array.o\n LIB_OBJS += sha1-lookup.o\n LIB_OBJS += sha1-file.o\n LIB_OBJS += sha1-name.o\ndiff --git a/bisect.c b/bisect.c\nindex 9154f810f7..64b579b6ea 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -10,7 +10,7 @@\n #include \"run-command.h\"\n #include \"log-tree.h\"\n #include \"bisect.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"argv-array.h\"\n #include \"commit-slab.h\"\n #include \"commit-reach.h\"\ndiff --git a/builtin/cat-file.c b/builtin/cat-file.c\nindex 6ecc8ee6dc..0d03fdac6e 100644\n--- a/builtin/cat-file.c\n+++ b/builtin/cat-file.c\n@@ -12,7 +12,7 @@\n #include \"userdiff.h\"\n #include \"streaming.h\"\n #include \"tree-walk.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"packfile.h\"\n #include \"object-store.h\"\n #include \"promisor-remote.h\"\ndiff --git a/builtin/diff.c b/builtin/diff.c\nindex 42ac803091..8537b17bd5 100644\n--- a/builtin/diff.c\n+++ b/builtin/diff.c\n@@ -17,7 +17,7 @@\n #include \"log-tree.h\"\n #include \"builtin.h\"\n #include \"submodule.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n \n #define DIFF_NO_INDEX_EXPLICIT 1\n #define DIFF_NO_INDEX_IMPLICIT 2\ndiff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c\nindex dc1485c8aa..4771100072 100644\n--- a/builtin/fetch-pack.c\n+++ b/builtin/fetch-pack.c\n@@ -3,7 +3,7 @@\n #include \"fetch-pack.h\"\n #include \"remote.h\"\n #include \"connect.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"protocol.h\"\n \n static const char fetch_pack_usage[] =\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex dc7c58ce3f..fdd18c7ccb 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -26,7 +26,7 @@\n #include \"pack-bitmap.h\"\n #include \"delta-islands.h\"\n #include \"reachable.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"argv-array.h\"\n #include \"list.h\"\n #include \"packfile.h\"\ndiff --git a/builtin/pull.c b/builtin/pull.c\nindex e42665b681..9429786604 100644\n--- a/builtin/pull.c\n+++ b/builtin/pull.c\n@@ -12,7 +12,7 @@\n #include \"parse-options.h\"\n #include \"exec-cmd.h\"\n #include \"run-command.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"remote.h\"\n #include \"dir.h\"\n #include \"rebase.h\"\ndiff --git a/builtin/receive-pack.c b/builtin/receive-pack.c\nindex 2cc18bbffd..d46147f709 100644\n--- a/builtin/receive-pack.c\n+++ b/builtin/receive-pack.c\n@@ -13,7 +13,7 @@\n #include \"remote.h\"\n #include \"connect.h\"\n #include \"string-list.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"connected.h\"\n #include \"argv-array.h\"\n #include \"version.h\"\ndiff --git a/builtin/send-pack.c b/builtin/send-pack.c\nindex 098ebf22d0..f2c5a34402 100644\n--- a/builtin/send-pack.c\n+++ b/builtin/send-pack.c\n@@ -11,7 +11,7 @@\n #include \"quote.h\"\n #include \"transport.h\"\n #include \"version.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"gpg-interface.h\"\n #include \"gettext.h\"\n #include \"protocol.h\"\ndiff --git a/builtin/tag.c b/builtin/tag.c\nindex cc30d346f5..dd160b49c7 100644\n--- a/builtin/tag.c\n+++ b/builtin/tag.c\n@@ -17,7 +17,7 @@\n #include \"diff.h\"\n #include \"revision.h\"\n #include \"gpg-interface.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"column.h\"\n #include \"ref-filter.h\"\n \ndiff --git a/cache.h b/cache.h\nindex c77b95870a..0f0485ecfe 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -14,7 +14,7 @@\n #include \"pack-revindex.h\"\n #include \"hash.h\"\n #include \"path.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"repository.h\"\n #include \"mem-pool.h\"\n \ndiff --git a/combine-diff.c b/combine-diff.c\nindex d5c4d839dc..002e0e5438 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -10,7 +10,7 @@\n #include \"log-tree.h\"\n #include \"refs.h\"\n #include \"userdiff.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"revision.h\"\n \n static int compare_paths(const struct combine_diff_path *one,\ndiff --git a/connect.c b/connect.c\nindex b6451ab5e8..23013c6344 100644\n--- a/connect.c\n+++ b/connect.c\n@@ -9,7 +9,7 @@\n #include \"connect.h\"\n #include \"url.h\"\n #include \"string-list.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"transport.h\"\n #include \"strbuf.h\"\n #include \"version.h\"\ndiff --git a/delta-islands.c b/delta-islands.c\nindex 09dbd3cf72..aa98b2e541 100644\n--- a/delta-islands.c\n+++ b/delta-islands.c\n@@ -17,7 +17,7 @@\n #include \"pack-bitmap.h\"\n #include \"pack-objects.h\"\n #include \"delta-islands.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"config.h\"\n \n KHASH_INIT(str, const char *, void *, 1, kh_str_hash_func, kh_str_hash_equal)\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 1734a573b0..0b07b3ee73 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -15,7 +15,7 @@\n #include \"connect.h\"\n #include \"transport.h\"\n #include \"version.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"oidset.h\"\n #include \"packfile.h\"\n #include \"object-store.h\"\ndiff --git a/object-store.h b/object-store.h\nindex be72fee7d5..d1e490f203 100644\n--- a/object-store.h\n+++ b/object-store.h\n@@ -4,7 +4,7 @@\n #include \"cache.h\"\n #include \"oidmap.h\"\n #include \"list.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"strbuf.h\"\n #include \"thread-utils.h\"\n \ndiff --git a/sha1-array.c b/oid-array.c\nsimilarity index 96%\nrename from sha1-array.c\nrename to oid-array.c\nindex bada0c4353..8657a5cedf 100644\n--- a/sha1-array.c\n+++ b/oid-array.c\n@@ -1,5 +1,5 @@\n #include \"cache.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"sha1-lookup.h\"\n \n void oid_array_append(struct oid_array *array, const struct object_id *oid)\n@@ -48,7 +48,7 @@ int oid_array_for_each(struct oid_array *array,\n {\n \tsize_t i;\n \n-\t/* No oid_array_sort() here! See sha1-array.h */\n+\t/* No oid_array_sort() here! See oid-array.h */\n \n \tfor (i = 0; i < array->nr; i++) {\n \t\tint ret = fn(array->oid + i, data);\ndiff --git a/sha1-array.h b/oid-array.h\nsimilarity index 98%\nrename from sha1-array.h\nrename to oid-array.h\nindex c5e4b9324f..f28d322c90 100644\n--- a/sha1-array.h\n+++ b/oid-array.h\n@@ -19,7 +19,7 @@\n  *\n  * void some_func(void)\n  * {\n- *     struct sha1_array hashes = OID_ARRAY_INIT;\n+ *     struct oid_array hashes = OID_ARRAY_INIT;\n  *     struct object_id oid;\n  *\n  *     // Read objects into our set\ndiff --git a/parse-options-cb.c b/parse-options-cb.c\nindex a28b55be48..86cd393013 100644\n--- a/parse-options-cb.c\n+++ b/parse-options-cb.c\n@@ -5,7 +5,7 @@\n #include \"color.h\"\n #include \"string-list.h\"\n #include \"argv-array.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n \n /*----- some often used options -----*/\n \ndiff --git a/ref-filter.h b/ref-filter.h\nindex f1dcff4c6e..64330e9601 100644\n--- a/ref-filter.h\n+++ b/ref-filter.h\n@@ -1,7 +1,7 @@\n #ifndef REF_FILTER_H\n #define REF_FILTER_H\n \n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"refs.h\"\n #include \"commit.h\"\n #include \"parse-options.h\"\ndiff --git a/remote-curl.c b/remote-curl.c\nindex e4cd321844..1c9aa3d0ab 100644\n--- a/remote-curl.c\n+++ b/remote-curl.c\n@@ -12,7 +12,7 @@\n #include \"sideband.h\"\n #include \"argv-array.h\"\n #include \"credential.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"send-pack.h\"\n #include \"protocol.h\"\n #include \"quote.h\"\ndiff --git a/send-pack.c b/send-pack.c\nindex 0407841ae8..da4741ce4a 100644\n--- a/send-pack.c\n+++ b/send-pack.c\n@@ -12,7 +12,7 @@\n #include \"quote.h\"\n #include \"transport.h\"\n #include \"version.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"gpg-interface.h\"\n #include \"cache.h\"\n \ndiff --git a/sha1-name.c b/sha1-name.c\nindex 5bb006e5a9..6561cd9097 100644\n--- a/sha1-name.c\n+++ b/sha1-name.c\n@@ -8,7 +8,7 @@\n #include \"refs.h\"\n #include \"remote.h\"\n #include \"dir.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"packfile.h\"\n #include \"object-store.h\"\n #include \"repository.h\"\ndiff --git a/shallow.c b/shallow.c\nindex 7fd04afed1..14f7fa6e27 100644\n--- a/shallow.c\n+++ b/shallow.c\n@@ -8,7 +8,7 @@\n #include \"pkt-line.h\"\n #include \"remote.h\"\n #include \"refs.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"diff.h\"\n #include \"revision.h\"\n #include \"commit-slab.h\"\ndiff --git a/submodule.c b/submodule.c\nindex c3aadf3fff..e2ef5698c8 100644\n--- a/submodule.c\n+++ b/submodule.c\n@@ -12,7 +12,7 @@\n #include \"diffcore.h\"\n #include \"refs.h\"\n #include \"string-list.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"argv-array.h\"\n #include \"blob.h\"\n #include \"thread-utils.h\"\ndiff --git a/t/helper/test-sha1-array.c b/t/helper/test-sha1-array.c\nindex ad5e69f9d3..6f7d3b939e 100644\n--- a/t/helper/test-sha1-array.c\n+++ b/t/helper/test-sha1-array.c\n@@ -1,6 +1,6 @@\n #include \"test-tool.h\"\n #include \"cache.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n \n static int print_oid(const struct object_id *oid, void *data)\n {\ndiff --git a/transport.c b/transport.c\nindex 1fdc7dac1a..471c5bd339 100644\n--- a/transport.c\n+++ b/transport.c\n@@ -16,7 +16,7 @@\n #include \"url.h\"\n #include \"submodule.h\"\n #include \"string-list.h\"\n-#include \"sha1-array.h\"\n+#include \"oid-array.h\"\n #include \"sigchain.h\"\n #include \"transport-internal.h\"\n #include \"protocol.h\"\n-- \n2.26.0.597.g7e08ed78ff\n\n"},{"id":"394359","messageId":"20200330140403.GD2456038@coredump.intra.peff.net","threadId":"53131","inReplyTo":"20200330140247.GA476088@coredump.intra.peff.net","subject":"[PATCH 4/7] test-tool: rename sha1-array to oid-array","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-30T14:04:03Z","receivedAt":"2020-03-30T14:04:06Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This matches the actual data structure name, as well as the source file\nthat contains the code we're testing. The test scripts need updating to\nuse the new name, as well.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n Makefile                                         |  2 +-\n t/helper/{test-sha1-array.c => test-oid-array.c} |  6 +++---\n t/helper/test-tool.c                             |  2 +-\n t/helper/test-tool.h                             |  2 +-\n t/t0064-sha1-array.sh                            | 16 ++++++++--------\n 5 files changed, 14 insertions(+), 14 deletions(-)\n rename t/helper/{test-sha1-array.c => test-oid-array.c} (85%)\n\ndiff --git a/Makefile b/Makefile\nindex abfe5cc29b..dc356ce4dd 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -738,7 +738,7 @@ TEST_BUILTINS_OBJS += test-run-command.o\n TEST_BUILTINS_OBJS += test-scrap-cache-tree.o\n TEST_BUILTINS_OBJS += test-serve-v2.o\n TEST_BUILTINS_OBJS += test-sha1.o\n-TEST_BUILTINS_OBJS += test-sha1-array.o\n+TEST_BUILTINS_OBJS += test-oid-array.o\n TEST_BUILTINS_OBJS += test-sha256.o\n TEST_BUILTINS_OBJS += test-sigchain.o\n TEST_BUILTINS_OBJS += test-strcmp-offset.o\ndiff --git a/t/helper/test-sha1-array.c b/t/helper/test-oid-array.c\nsimilarity index 85%\nrename from t/helper/test-sha1-array.c\nrename to t/helper/test-oid-array.c\nindex 6f7d3b939e..ce9fd5f091 100644\n--- a/t/helper/test-sha1-array.c\n+++ b/t/helper/test-oid-array.c\n@@ -8,7 +8,7 @@ static int print_oid(const struct object_id *oid, void *data)\n \treturn 0;\n }\n \n-int cmd__sha1_array(int argc, const char **argv)\n+int cmd__oid_array(int argc, const char **argv)\n {\n \tstruct oid_array array = OID_ARRAY_INIT;\n \tstruct strbuf line = STRBUF_INIT;\n@@ -19,11 +19,11 @@ int cmd__sha1_array(int argc, const char **argv)\n \n \t\tif (skip_prefix(line.buf, \"append \", &arg)) {\n \t\t\tif (get_oid_hex(arg, &oid))\n-\t\t\t\tdie(\"not a hexadecimal SHA1: %s\", arg);\n+\t\t\t\tdie(\"not a hexadecimal oid: %s\", arg);\n \t\t\toid_array_append(&array, &oid);\n \t\t} else if (skip_prefix(line.buf, \"lookup \", &arg)) {\n \t\t\tif (get_oid_hex(arg, &oid))\n-\t\t\t\tdie(\"not a hexadecimal SHA1: %s\", arg);\n+\t\t\t\tdie(\"not a hexadecimal oid: %s\", arg);\n \t\t\tprintf(\"%d\\n\", oid_array_lookup(&array, &oid));\n \t\t} else if (!strcmp(line.buf, \"clear\"))\n \t\t\toid_array_clear(&array);\ndiff --git a/t/helper/test-tool.c b/t/helper/test-tool.c\nindex 31eedcd241..c1b320c24c 100644\n--- a/t/helper/test-tool.c\n+++ b/t/helper/test-tool.c\n@@ -37,6 +37,7 @@ static struct test_cmd cmds[] = {\n \t{ \"match-trees\", cmd__match_trees },\n \t{ \"mergesort\", cmd__mergesort },\n \t{ \"mktemp\", cmd__mktemp },\n+\t{ \"oid-array\", cmd__oid_array },\n \t{ \"oidmap\", cmd__oidmap },\n \t{ \"online-cpus\", cmd__online_cpus },\n \t{ \"parse-options\", cmd__parse_options },\n@@ -57,7 +58,6 @@ static struct test_cmd cmds[] = {\n \t{ \"scrap-cache-tree\", cmd__scrap_cache_tree },\n \t{ \"serve-v2\", cmd__serve_v2 },\n \t{ \"sha1\", cmd__sha1 },\n-\t{ \"sha1-array\", cmd__sha1_array },\n \t{ \"sha256\", cmd__sha256 },\n \t{ \"sigchain\", cmd__sigchain },\n \t{ \"strcmp-offset\", cmd__strcmp_offset },\ndiff --git a/t/helper/test-tool.h b/t/helper/test-tool.h\nindex 4eb5e6609e..1cbaec02f3 100644\n--- a/t/helper/test-tool.h\n+++ b/t/helper/test-tool.h\n@@ -47,7 +47,7 @@ int cmd__run_command(int argc, const char **argv);\n int cmd__scrap_cache_tree(int argc, const char **argv);\n int cmd__serve_v2(int argc, const char **argv);\n int cmd__sha1(int argc, const char **argv);\n-int cmd__sha1_array(int argc, const char **argv);\n+int cmd__oid_array(int argc, const char **argv);\n int cmd__sha256(int argc, const char **argv);\n int cmd__sigchain(int argc, const char **argv);\n int cmd__strcmp_offset(int argc, const char **argv);\ndiff --git a/t/t0064-sha1-array.sh b/t/t0064-sha1-array.sh\nindex 5dda570b9a..45685af2fd 100755\n--- a/t/t0064-sha1-array.sh\n+++ b/t/t0064-sha1-array.sh\n@@ -18,7 +18,7 @@ test_expect_success 'ordered enumeration' '\n \t{\n \t\techoid append 88 44 aa 55 &&\n \t\techo for_each_unique\n-\t} | test-tool sha1-array >actual &&\n+\t} | test-tool oid-array >actual &&\n \ttest_cmp expect actual\n '\n \n@@ -28,15 +28,15 @@ test_expect_success 'ordered enumeration with duplicate suppression' '\n \t\techoid append 88 44 aa 55 &&\n \t\techoid append 88 44 aa 55 &&\n \t\techo for_each_unique\n-\t} | test-tool sha1-array >actual &&\n+\t} | test-tool oid-array >actual &&\n \ttest_cmp expect actual\n '\n \n test_expect_success 'lookup' '\n \t{\n \t\techoid append 88 44 aa 55 &&\n \t\techoid lookup 55\n-\t} | test-tool sha1-array >actual &&\n+\t} | test-tool oid-array >actual &&\n \tn=$(cat actual) &&\n \ttest \"$n\" -eq 1\n '\n@@ -45,7 +45,7 @@ test_expect_success 'lookup non-existing entry' '\n \t{\n \t\techoid append 88 44 aa 55 &&\n \t\techoid lookup 33\n-\t} | test-tool sha1-array >actual &&\n+\t} | test-tool oid-array >actual &&\n \tn=$(cat actual) &&\n \ttest \"$n\" -lt 0\n '\n@@ -55,7 +55,7 @@ test_expect_success 'lookup with duplicates' '\n \t\techoid append 88 44 aa 55 &&\n \t\techoid append 88 44 aa 55 &&\n \t\techoid lookup 55\n-\t} | test-tool sha1-array >actual &&\n+\t} | test-tool oid-array >actual &&\n \tn=$(cat actual) &&\n \ttest \"$n\" -ge 2 &&\n \ttest \"$n\" -le 3\n@@ -66,7 +66,7 @@ test_expect_success 'lookup non-existing entry with duplicates' '\n \t\techoid append 88 44 aa 55 &&\n \t\techoid append 88 44 aa 55 &&\n \t\techoid lookup 66\n-\t} | test-tool sha1-array >actual &&\n+\t} | test-tool oid-array >actual &&\n \tn=$(cat actual) &&\n \ttest \"$n\" -lt 0\n '\n@@ -81,7 +81,7 @@ test_expect_success 'lookup with almost duplicate values' '\n \t\techo \"append $id1\" &&\n \t\techo \"append $id2\" &&\n \t\techoid lookup 55\n-\t} | test-tool sha1-array >actual &&\n+\t} | test-tool oid-array >actual &&\n \tn=$(cat actual) &&\n \ttest \"$n\" -eq 0\n '\n@@ -90,7 +90,7 @@ test_expect_success 'lookup with single duplicate value' '\n \t{\n \t\techoid append 55 55 &&\n \t\techoid lookup 55\n-\t} | test-tool sha1-array >actual &&\n+\t} | test-tool oid-array >actual &&\n \tn=$(cat actual) &&\n \ttest \"$n\" -ge 0 &&\n \ttest \"$n\" -le 1\n-- \n2.26.0.597.g7e08ed78ff\n\n"},{"id":"394360","messageId":"20200330140406.GE2456038@coredump.intra.peff.net","threadId":"53131","inReplyTo":"20200330140247.GA476088@coredump.intra.peff.net","subject":"[PATCH 5/7] bisect: stop referring to sha1_array","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-30T14:04:06Z","receivedAt":"2020-03-30T14:04:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Our join_sha1_array_hex() function long ago switched to using an\noid_array; let's change the name to match.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n bisect.c | 6 +++---\n 1 file changed, 3 insertions(+), 3 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 64b579b6ea..d5e830410f 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -473,7 +473,7 @@ static void read_bisect_paths(struct argv_array *array)\n \tfclose(fp);\n }\n \n-static char *join_sha1_array_hex(struct oid_array *array, char delim)\n+static char *join_oid_array_hex(struct oid_array *array, char delim)\n {\n \tstruct strbuf joined_hexs = STRBUF_INIT;\n \tint i;\n@@ -765,7 +765,7 @@ static enum bisect_error handle_bad_merge_base(void)\n {\n \tif (is_expected_rev(current_bad_oid)) {\n \t\tchar *bad_hex = oid_to_hex(current_bad_oid);\n-\t\tchar *good_hex = join_sha1_array_hex(&good_revs, ' ');\n+\t\tchar *good_hex = join_oid_array_hex(&good_revs, ' ');\n \t\tif (!strcmp(term_bad, \"bad\") && !strcmp(term_good, \"good\")) {\n \t\t\tfprintf(stderr, _(\"The merge base %s is bad.\\n\"\n \t\t\t\t\"This means the bug has been fixed \"\n@@ -796,7 +796,7 @@ static void handle_skipped_merge_base(const struct object_id *mb)\n {\n \tchar *mb_hex = oid_to_hex(mb);\n \tchar *bad_hex = oid_to_hex(current_bad_oid);\n-\tchar *good_hex = join_sha1_array_hex(&good_revs, ' ');\n+\tchar *good_hex = join_oid_array_hex(&good_revs, ' ');\n \n \twarning(_(\"the merge base between %s and [%s] \"\n \t\t\"must be skipped.\\n\"\n-- \n2.26.0.597.g7e08ed78ff\n\n"},{"id":"394361","messageId":"20200330140411.GF2456038@coredump.intra.peff.net","threadId":"53131","inReplyTo":"20200330140247.GA476088@coredump.intra.peff.net","subject":"[PATCH 6/7] ref-filter: stop referring to \"sha1 array\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-30T14:04:11Z","receivedAt":"2020-03-30T14:04:13Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"A comment refers to the \"sha1s in the given sha1 array\". But this became\nan oid_array along with everywhere else in 910650d2f8 (Rename sha1_array\nto oid_array, 2017-03-31). Plus there's an extra line of leftover\nediting cruft we can drop.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n ref-filter.c | 7 +++----\n 1 file changed, 3 insertions(+), 4 deletions(-)\n\ndiff --git a/ref-filter.c b/ref-filter.c\nindex b1812cb69a..35776838f4 100644\n--- a/ref-filter.c\n+++ b/ref-filter.c\n@@ -1976,10 +1976,9 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter,\n }\n \n /*\n- * Given a ref (sha1, refname), check if the ref belongs to the array\n- * of sha1s. If the given ref is a tag, check if the given tag points\n- * at one of the sha1s in the given sha1 array.\n- * the given sha1_array.\n+ * Given a ref (oid, refname), check if the ref belongs to the array\n+ * of oids. If the given ref is a tag, check if the given tag points\n+ * at one of the oids in the given oid array.\n  * NEEDSWORK:\n  * 1. Only a single level of inderection is obtained, we might want to\n  * change this to account for multiple levels (e.g. annotated tags\n-- \n2.26.0.597.g7e08ed78ff\n\n"},{"id":"394362","messageId":"20200330140413.GG2456038@coredump.intra.peff.net","threadId":"53131","inReplyTo":"20200330140247.GA476088@coredump.intra.peff.net","subject":"[PATCH 7/7] oidset: stop referring to sha1-array","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-30T14:04:13Z","receivedAt":"2020-03-30T14:04:16Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Ths has been oid_array for some time, though the source only recently\nmoved from sha1-array.[ch] to oid-array.[ch]. In either case, we should\nsay \"oid-array\" here.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n oidset.h | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/oidset.h b/oidset.h\nindex d8a106b127..3a2d9d1115 100644\n--- a/oidset.h\n+++ b/oidset.h\n@@ -4,7 +4,7 @@\n #include \"khash.h\"\n \n /**\n- * This API is similar to sha1-array, in that it maintains a set of object ids\n+ * This API is similar to oid-array, in that it maintains a set of object ids\n  * in a memory-efficient way. The major differences are:\n  *\n  *   1. It uses a hash, so we can do online duplicate removal, rather than\n-- \n2.26.0.597.g7e08ed78ff\n"},{"id":"394363","messageId":"20200330140930.GA2456104@coredump.intra.peff.net","threadId":"53131","inReplyTo":"20200330140309.GA2456038@coredump.intra.peff.net","subject":"Re: [PATCH 1/7] oid_array: use size_t for count and allocation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-03-30T14:09:30Z","receivedAt":"2020-03-30T14:09:34Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Mar 30, 2020 at 10:03:10AM -0400, Jeff King wrote:\n\n> The oid_array object uses an \"int\" to store the number of items and the\n> allocated size. It's rather unlikely for somebody to have more than 2^31\n> objects in a repository (the sha1's alone would be 40GB!), but if they\n> do, we'd overflow our alloc variable.\n> \n> You can reproduce this case with something like:\n> \n>   git init repo\n>   cd repo\n> \n>   # make a pack with 2^24 objects\n>   perl -e '\n>     my $nr = 2**24;\n> \n>     for (my $i = 0; $i < $nr; $i++) {\n> \t    print \"blob\\n\";\n> \t    print \"data 4\\n\";\n> \t    print pack(\"N\", $i);\n>     }\n>   ' | git fast-import\n\nI briefly tried to create a packfile manually that had a ton of objects\nin it, thinking it would be faster. Conceptually it's pretty simple to\nwrite a pack header, and then a series of pack-object headers (which are\nthe same single-byte each time) and then a 4-byte body. But you have to\nzlib compress the body, which created a bunch of headaches.\n\nSo I arrived at this fast-import solution, which was...not super fast.\nProfiling showed that we were spending 80% of the time inserting into\nour custom hashtable, which is fixed at 2^16 entries and then chains\nbeyond that. Swapping it out for a khash proved much faster, but I'm not\nsure if the memory games are too gross (see the comment in find_object\nbelow).\n\nI also didn't look into whether we could get rid of the extra allocating\npool (and store the structs right in the hash), or if it's necessary for\ntheir pointers to be stable.\n\n---\ndiff --git a/fast-import.c b/fast-import.c\nindex 202dda11a6..427dd73d26 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -39,12 +39,25 @@\n \n struct object_entry {\n \tstruct pack_idx_entry idx;\n-\tstruct object_entry *next;\n \tuint32_t type : TYPE_BITS,\n \t\tpack_id : PACK_ID_BITS,\n \t\tdepth : DEPTH_BITS;\n };\n \n+static inline unsigned int object_entry_hash(struct object_entry *oe)\n+{\n+\treturn oidhash(&oe->idx.oid);\n+}\n+\n+static inline int object_entry_equal(struct object_entry *a,\n+\t\t\t\t     struct object_entry *b)\n+{\n+\treturn oideq(&a->idx.oid, &b->idx.oid);\n+}\n+\n+KHASH_INIT(object_entry_set, struct object_entry *, int, 0,\n+\t   object_entry_hash, object_entry_equal);\n+\n struct object_entry_pool {\n \tstruct object_entry_pool *next_pool;\n \tstruct object_entry *next_free;\n@@ -178,7 +191,7 @@ static off_t pack_size;\n /* Table of objects we've written. */\n static unsigned int object_entry_alloc = 5000;\n static struct object_entry_pool *blocks;\n-static struct object_entry *object_table[1 << 16];\n+static kh_object_entry_set_t object_table;\n static struct mark_set *marks;\n static const char *export_marks_file;\n static const char *import_marks_file;\n@@ -455,44 +468,40 @@ static struct object_entry *new_object(struct object_id *oid)\n \n static struct object_entry *find_object(struct object_id *oid)\n {\n-\tunsigned int h = oid->hash[0] << 8 | oid->hash[1];\n-\tstruct object_entry *e;\n-\tfor (e = object_table[h]; e; e = e->next)\n-\t\tif (oideq(oid, &e->idx.oid))\n-\t\t\treturn e;\n+\t/*\n+\t * this cast works because we only look at the oid part of the entry,\n+\t * and it comes first in the struct\n+\t */\n+\tkhiter_t pos = kh_get_object_entry_set(&object_table,\n+\t\t\t\t\t       (struct object_entry *)oid);\n+\tif (pos != kh_end(&object_table))\n+\t\treturn kh_key(&object_table, pos);\n \treturn NULL;\n }\n \n static struct object_entry *insert_object(struct object_id *oid)\n {\n-\tunsigned int h = oid->hash[0] << 8 | oid->hash[1];\n-\tstruct object_entry *e = object_table[h];\n-\n-\twhile (e) {\n-\t\tif (oideq(oid, &e->idx.oid))\n-\t\t\treturn e;\n-\t\te = e->next;\n-\t}\n+\tstruct object_entry *e;\n+\tint redundant;\n \n \te = new_object(oid);\n-\te->next = object_table[h];\n \te->idx.offset = 0;\n-\tobject_table[h] = e;\n+\tkh_put_object_entry_set(&object_table, e, &redundant);\n \treturn e;\n }\n \n static void invalidate_pack_id(unsigned int id)\n {\n-\tunsigned int h;\n \tunsigned long lu;\n \tstruct tag *t;\n+\tkhiter_t iter;\n \n-\tfor (h = 0; h < ARRAY_SIZE(object_table); h++) {\n-\t\tstruct object_entry *e;\n-\n-\t\tfor (e = object_table[h]; e; e = e->next)\n+\tfor (iter = kh_begin(&object_table); iter != kh_end(&object_table); iter++) {\n+\t\tif (kh_exist(&object_table, iter)) {\n+\t\t\tstruct object_entry *e = kh_key(&object_table, iter);\n \t\t\tif (e->pack_id == id)\n \t\t\t\te->pack_id = MAX_PACK_ID;\n+\t\t}\n \t}\n \n \tfor (lu = 0; lu < branch_table_sz; lu++) {\n"},{"id":"395460","messageId":"20200415002758.GC7457@syl.local","threadId":"53131","inReplyTo":"20200330140309.GA2456038@coredump.intra.peff.net","subject":"Re: [PATCH 1/7] oid_array: use size_t for count and allocation","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-04-15T00:27:58Z","receivedAt":"2020-04-15T00:28:05Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, Mar 30, 2020 at 10:03:09AM -0400, Jeff King wrote:\n> The oid_array object uses an \"int\" to store the number of items and the\n> allocated size. It's rather unlikely for somebody to have more than 2^31\n> objects in a repository (the sha1's alone would be 40GB!), but if they\n> do, we'd overflow our alloc variable.\n>\n> You can reproduce this case with something like:\n>\n>   git init repo\n>   cd repo\n>\n>   # make a pack with 2^24 objects\n>   perl -e '\n>     my $nr = 2**24;\n>\n>     for (my $i = 0; $i < $nr; $i++) {\n> \t    print \"blob\\n\";\n> \t    print \"data 4\\n\";\n> \t    print pack(\"N\", $i);\n>     }\n>   ' | git fast-import\n>\n>   # now make 256 copies of it; most of these objects will be duplicates,\n>   # but oid_array doesn't de-dup until all values are read and it can\n>   # sort the result.\n>   cd .git/objects/pack/\n>   pack=$(echo *.pack)\n>   idx=$(echo *.idx)\n>   for i in $(seq 0 255); do\n>     # no need to waste disk space\n>     ln \"$pack\" \"pack-extra-$i.pack\"\n>     ln \"$idx\" \"pack-extra-$i.idx\"\n>   done\n>\n>   # and now force an oid_array to store all of it\n>   git cat-file --batch-all-objects --batch-check\n>\n> which results in:\n>\n>   fatal: size_t overflow: 32 * 18446744071562067968\n>\n> So the good news is that st_mult() sees the problem (the large number is\n> because our int wraps negative, and then that gets cast to a size_t),\n> doing the job it was meant to: bailing in crazy situations rather than\n> causing an undersized buffer.\n>\n> But we should avoid hitting this case at all, and instead limit\n> ourselves based on what malloc() is willing to give us. We can easily do\n> that by switching to size_t.\n>\n> The cat-file process above made it to ~120GB virtual set size before the\n> integer overflow (our internal hash storage is 32-bytes now in\n> preparation for sha256, so we'd expect ~128GB total needed, plus\n> potentially more to copy from one realloc'd block to another)). After\n> this patch (and about 130GB of RAM+swap), it does eventually read in the\n> whole set. No test for obvious reasons.\n\n;). This patch looks good, and makes immediate sense given your\nexplanation.\n\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n>  sha1-array.h | 4 ++--\n>  1 file changed, 2 insertions(+), 2 deletions(-)\n>\n> diff --git a/sha1-array.h b/sha1-array.h\n> index dc1bca9c9a..c5e4b9324f 100644\n> --- a/sha1-array.h\n> +++ b/sha1-array.h\n> @@ -49,8 +49,8 @@\n>   */\n>  struct oid_array {\n>  \tstruct object_id *oid;\n> -\tint nr;\n> -\tint alloc;\n> +\tsize_t nr;\n> +\tsize_t alloc;\n>  \tint sorted;\n>  };\n>\n> --\n> 2.26.0.597.g7e08ed78ff\n\nThanks,\nTaylor\n"},{"id":"395461","messageId":"20200415003404.GD7457@syl.local","threadId":"53131","inReplyTo":"20200330140346.GC2456038@coredump.intra.peff.net","subject":"Re: [PATCH 3/7] oid_array: rename source file from sha1-array","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-04-15T00:34:04Z","receivedAt":"2020-04-15T00:34:20Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, Mar 30, 2020 at 10:03:46AM -0400, Jeff King wrote:\n> We renamed the actual data structure in 910650d2f8 (Rename sha1_array to\n> oid_array, 2017-03-31), but the file is still called sha1-array. Besides\n> being slightly confusing, it makes it more annoying to grep for leftover\n> occurrences of \"sha1\" in various files, because the header is included\n> in so many places.\n>\n> Let's complete the transition by renaming the source and header files\n> (and fixing up a few comment references).\n>\n> I kept the \"-\" in the name, as that seems to be our style; cf.\n> fc1395f4a4 (sha1_file.c: rename to use dash in file name, 2018-04-10).\n> We also have oidmap.h and oidset.h without any punctuation, but those\n> are \"struct oidmap\" and \"struct oidset\" in the code. We _could_ make\n> this \"oidarray\" to match, but somehow it looks uglier to me because of\n> the length of \"array\" (plus it would be a very invasive patch for little\n> gain).\n\nI was wondering what you were planning to do about that. But I think\nthat what you did is the right move. Sure, perhaps it'd be more\nconsistent to call this \"oidarray\", or rename everything else to\n\"oid_map\" and \"oid_set\".\n\nI prefer what you did here to that, I think because I also find the\n\"oidarray\" spelling to be weird.\n\n>\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n\nThanks,\nTaylor\n"},{"id":"395462","messageId":"20200415003546.GE7457@syl.local","threadId":"53131","inReplyTo":"20200330140247.GA476088@coredump.intra.peff.net","subject":"Re: [PATCH 0/7] oid_array cleanups","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-04-15T00:35:46Z","receivedAt":"2020-04-15T00:35:54Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Hi Peff,\n\nOn Mon, Mar 30, 2020 at 10:02:47AM -0400, Jeff King wrote:\n> I recently encountered a repo in the wild that had over 2^31 objects,\n> and found that cat-file barfed:\n>\n>   $ git cat-file --batch-all-objects --batch-check\n>   fatal: size_t overflow: 32 * 18446744071562067968\n>\n> The issue is that we use an \"int\" to store the count and the allocation.\n> Fortunately our st_mult() protection kicks in before we end up with an\n> undersized buffer, so this shouldn't be dangerous. And while I'd argue\n> that having that many objects is probably silly and likely to cause\n> other problems, I'd just as soon we kept our allocating code as robust\n> as possible.\n>\n> The first patch is the actual fix, followed by some related type\n> cleanup. The rest of it is just leftovers from the\n> s/sha1_array/oid_array/ transition a few years back.\n>\n>   [1/7]: oid_array: use size_t for count and allocation\n>   [2/7]: oid_array: use size_t for iteration\n>   [3/7]: oid_array: rename source file from sha1-array\n>   [4/7]: test-tool: rename sha1-array to oid-array\n>   [5/7]: bisect: stop referring to sha1_array\n>   [6/7]: ref-filter: stop referring to \"sha1 array\"\n>   [7/7]: oidset: stop referring to sha1-array\n\nThanks for this. I reviewed the patch, which was a breeze thanks to how\nyou broke it out. I don't think that I said anything useful in my actual\nreview, which is to say that this looks good from my perspective.\n\nSorry that I let it sit in my inbox for a few days. Trying to get better\nabout that :).\n\n  Reviewed-by: Taylor Blau <me@ttaylorr.com>\n\nThanks,\nTaylor\n"}]}