diff options
| -rw-r--r-- | README.md | 6 | ||||
| -rw-r--r-- | fuzzers/commit_graph_fuzzer.c | 5 | ||||
| -rw-r--r-- | src/blame.c | 25 | ||||
| -rw-r--r-- | src/commit_graph.c | 171 | ||||
| -rw-r--r-- | src/commit_graph.h | 49 | ||||
| -rw-r--r-- | src/merge.c | 7 | ||||
| -rw-r--r-- | tests/graph/commit_graph.c | 70 | ||||
| -rw-r--r-- | tests/resources/merge-recursive/.gitted/objects/info/commit-graph | bin | 0 -> 4624 bytes |
8 files changed, 318 insertions, 15 deletions
@@ -3,7 +3,7 @@ libgit2 - the Git linkable library | Build Status | | | ------------ | - | -| **master** branch CI builds | [](https://github.com/libgit2/libgit2/actions?query=workflow%3A%22CI+Build%22+event%3Apush) | +| **main** branch CI builds | [](https://github.com/libgit2/libgit2/actions?query=workflow%3A%22CI+Build%22+event%3Apush) | | **v1.1 branch** CI builds | [](https://github.com/libgit2/libgit2/actions?query=workflow%3A%22CI+Build%22+event%3Apush+branch%3Amaint%2Fv1.1) | | **v1.0 branch** CI builds | [](https://dev.azure.com/libgit2/libgit2/_build/latest?definitionId=7&branchName=maint/v1.0) | | **Nightly** builds | [](https://github.com/libgit2/libgit2/actions?query=workflow%3A%22Nightly+Build%22) [](https://scan.coverity.com/projects/639) | @@ -242,7 +242,7 @@ run the index tests: $ ./libgit2_clar -sindex To run a single test named `index::racy::diff`, which corresponds to the test -function [`test_index_racy__diff`](https://github.com/libgit2/libgit2/blob/master/tests/index/racy.c#L23): +function [`test_index_racy__diff`](https://github.com/libgit2/libgit2/blob/main/tests/index/racy.c#L23): $ ./libgit2_clar -sindex::racy::diff @@ -252,7 +252,7 @@ applicable to your platform or is particularly expensive. **Note:** There should be _no_ failing tests when you build an unmodified source tree from a [release](https://github.com/libgit2/libgit2/releases), -or from the [master branch](https://github.com/libgit2/libgit2/tree/master). +or from the [main branch](https://github.com/libgit2/libgit2/tree/main). Please contact us or [open an issue](https://github.com/libgit2/libgit2/issues) if you see test failures. diff --git a/fuzzers/commit_graph_fuzzer.c b/fuzzers/commit_graph_fuzzer.c index f5b9c8988..eb2c38258 100644 --- a/fuzzers/commit_graph_fuzzer.c +++ b/fuzzers/commit_graph_fuzzer.c @@ -32,6 +32,7 @@ int LLVMFuzzerInitialize(int *argc, char ***argv) int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { git_commit_graph_file cgraph = {{0}}; + git_commit_graph_entry e; git_buf commit_graph_buf = GIT_BUF_INIT; git_oid oid = {{0}}; bool append_hash = false; @@ -68,6 +69,10 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) < 0) goto cleanup; + /* Search for any oid, just to exercise that codepath. */ + if (git_commit_graph_entry_find(&e, &cgraph, &oid, GIT_OID_HEXSZ) < 0) + goto cleanup; + cleanup: git_commit_graph_close(&cgraph); git_buf_dispose(&commit_graph_buf); diff --git a/src/blame.c b/src/blame.c index 651b7a003..10e311aee 100644 --- a/src/blame.c +++ b/src/blame.c @@ -76,6 +76,14 @@ static git_blame_hunk* new_hunk( return hunk; } +static void free_hunk(git_blame_hunk *hunk) +{ + git__free((void*)hunk->orig_path); + git_signature_free(hunk->final_signature); + git_signature_free(hunk->orig_signature); + git__free(hunk); +} + static git_blame_hunk* dup_hunk(git_blame_hunk *hunk) { git_blame_hunk *newhunk = new_hunk( @@ -90,17 +98,14 @@ static git_blame_hunk* dup_hunk(git_blame_hunk *hunk) git_oid_cpy(&newhunk->orig_commit_id, &hunk->orig_commit_id); git_oid_cpy(&newhunk->final_commit_id, &hunk->final_commit_id); newhunk->boundary = hunk->boundary; - git_signature_dup(&newhunk->final_signature, hunk->final_signature); - git_signature_dup(&newhunk->orig_signature, hunk->orig_signature); - return newhunk; -} -static void free_hunk(git_blame_hunk *hunk) -{ - git__free((void*)hunk->orig_path); - git_signature_free(hunk->final_signature); - git_signature_free(hunk->orig_signature); - git__free(hunk); + if (git_signature_dup(&newhunk->final_signature, hunk->final_signature) < 0 || + git_signature_dup(&newhunk->orig_signature, hunk->orig_signature) < 0) { + free_hunk(newhunk); + return NULL; + } + + return newhunk; } /* Starting with the hunk that includes start_line, shift all following hunks' diff --git a/src/commit_graph.c b/src/commit_graph.c index 71a56e3da..b301d3d49 100644 --- a/src/commit_graph.c +++ b/src/commit_graph.c @@ -9,6 +9,7 @@ #include "futils.h" #include "hash.h" +#include "pack.h" #define GIT_COMMIT_GRAPH_MISSING_PARENT 0x70000000 @@ -278,6 +279,176 @@ int git_commit_graph_open(git_commit_graph_file **cgraph_out, const char *path) return 0; } +static int git_commit_graph_entry_get_byindex( + git_commit_graph_entry *e, + const git_commit_graph_file *cgraph, + size_t pos) +{ + const unsigned char *commit_data; + + GIT_ASSERT_ARG(e); + GIT_ASSERT_ARG(cgraph); + + if (pos >= cgraph->num_commits) { + git_error_set(GIT_ERROR_INVALID, "commit index %zu does not exist", pos); + return GIT_ENOTFOUND; + } + + commit_data = cgraph->commit_data + pos * (GIT_OID_RAWSZ + 4 * sizeof(uint32_t)); + git_oid_cpy(&e->tree_oid, (const git_oid *)commit_data); + e->parent_indices[0] = ntohl(*((uint32_t *)(commit_data + GIT_OID_RAWSZ))); + e->parent_indices[1] + = ntohl(*((uint32_t *)(commit_data + GIT_OID_RAWSZ + sizeof(uint32_t)))); + e->parent_count = (e->parent_indices[0] != GIT_COMMIT_GRAPH_MISSING_PARENT) + + (e->parent_indices[1] != GIT_COMMIT_GRAPH_MISSING_PARENT); + e->generation = ntohl(*((uint32_t *)(commit_data + GIT_OID_RAWSZ + 2 * sizeof(uint32_t)))); + e->commit_time = ntohl(*((uint32_t *)(commit_data + GIT_OID_RAWSZ + 3 * sizeof(uint32_t)))); + + e->commit_time |= (e->generation & 0x3ull) << 32ull; + e->generation >>= 2u; + if (e->parent_indices[1] & 0x80000000u) { + uint32_t extra_edge_list_pos = e->parent_indices[1] & 0x7fffffff; + + /* Make sure we're not being sent out of bounds */ + if (extra_edge_list_pos >= cgraph->num_extra_edge_list) { + git_error_set(GIT_ERROR_INVALID, + "commit %u does not exist", + extra_edge_list_pos); + return GIT_ENOTFOUND; + } + + e->extra_parents_index = extra_edge_list_pos; + while (extra_edge_list_pos < cgraph->num_extra_edge_list + && (ntohl(*( + (uint32_t *)(cgraph->extra_edge_list + + extra_edge_list_pos * sizeof(uint32_t)))) + & 0x80000000u) + == 0) { + extra_edge_list_pos++; + e->parent_count++; + } + + } + git_oid_cpy(&e->sha1, &cgraph->oid_lookup[pos]); + return 0; +} + +bool git_commit_graph_needs_refresh(const git_commit_graph_file *cgraph, const char *path) +{ + git_file fd = -1; + struct stat st; + ssize_t bytes_read; + git_oid cgraph_checksum = {{0}}; + + if (path == NULL) + path = git_buf_cstr(&cgraph->filename); + + /* TODO: properly open the file without access time using O_NOATIME */ + fd = git_futils_open_ro(path); + if (fd < 0) + return true; + + if (p_fstat(fd, &st) < 0) { + p_close(fd); + return true; + } + + if (!S_ISREG(st.st_mode) || !git__is_sizet(st.st_size) + || (size_t)st.st_size != cgraph->graph_map.len) { + p_close(fd); + return true; + } + + bytes_read = p_pread(fd, cgraph_checksum.id, GIT_OID_RAWSZ, st.st_size - GIT_OID_RAWSZ); + p_close(fd); + if (bytes_read != GIT_OID_RAWSZ) + return true; + + return !git_oid_equal(&cgraph_checksum, &cgraph->checksum); +} + +int git_commit_graph_entry_find( + git_commit_graph_entry *e, + const git_commit_graph_file *cgraph, + const git_oid *short_oid, + size_t len) +{ + int pos, found = 0; + uint32_t hi, lo; + const git_oid *current = NULL; + + GIT_ASSERT_ARG(e); + GIT_ASSERT_ARG(cgraph); + GIT_ASSERT_ARG(short_oid); + + hi = ntohl(cgraph->oid_fanout[(int)short_oid->id[0]]); + lo = ((short_oid->id[0] == 0x0) ? 0 : ntohl(cgraph->oid_fanout[(int)short_oid->id[0] - 1])); + + pos = git_pack__lookup_sha1(cgraph->oid_lookup, GIT_OID_RAWSZ, lo, hi, short_oid->id); + + if (pos >= 0) { + /* An object matching exactly the oid was found */ + found = 1; + current = cgraph->oid_lookup + pos; + } else { + /* No object was found */ + /* pos refers to the object with the "closest" oid to short_oid */ + pos = -1 - pos; + if (pos < (int)cgraph->num_commits) { + current = cgraph->oid_lookup + pos; + + if (!git_oid_ncmp(short_oid, current, len)) + found = 1; + } + } + + if (found && len != GIT_OID_HEXSZ && pos + 1 < (int)cgraph->num_commits) { + /* Check for ambiguousity */ + const git_oid *next = current + 1; + + if (!git_oid_ncmp(short_oid, next, len)) { + found = 2; + } + } + + if (!found) + return git_odb__error_notfound( + "failed to find offset for multi-pack index entry", short_oid, len); + if (found > 1) + return git_odb__error_ambiguous( + "found multiple offsets for multi-pack index entry"); + + return git_commit_graph_entry_get_byindex(e, cgraph, pos); +} + +int git_commit_graph_entry_parent( + git_commit_graph_entry *parent, + const git_commit_graph_file *cgraph, + const git_commit_graph_entry *entry, + size_t n) +{ + GIT_ASSERT_ARG(parent); + GIT_ASSERT_ARG(cgraph); + + if (n >= entry->parent_count) { + git_error_set(GIT_ERROR_INVALID, "parent index %zu does not exist", n); + return GIT_ENOTFOUND; + } + + if (n == 0 || (n == 1 && entry->parent_count == 2)) + return git_commit_graph_entry_get_byindex(parent, cgraph, entry->parent_indices[n]); + + return git_commit_graph_entry_get_byindex( + parent, + cgraph, + ntohl( + *(uint32_t *)(cgraph->extra_edge_list + + (entry->extra_parents_index + n - 1) + * sizeof(uint32_t))) + & 0x7fffffff); +} + + int git_commit_graph_close(git_commit_graph_file *cgraph) { GIT_ASSERT_ARG(cgraph); diff --git a/src/commit_graph.h b/src/commit_graph.h index 01512d76f..f21a03769 100644 --- a/src/commit_graph.h +++ b/src/commit_graph.h @@ -57,7 +57,56 @@ typedef struct git_commit_graph_file { git_buf filename; } git_commit_graph_file; +/** + * An entry in the commit-graph file. Provides a subset of the information that + * can be obtained from the commit header. + */ +typedef struct git_commit_graph_entry { + /* The generation number of the commit within the graph */ + size_t generation; + + /* Time in seconds from UNIX epoch. */ + git_time_t commit_time; + + /* The number of parents of the commit. */ + size_t parent_count; + + /* + * The indices of the parent commits within the Commit Data table. The value + * of `GIT_COMMIT_GRAPH_MISSING_PARENT` indicates that no parent is in that + * position. + */ + size_t parent_indices[2]; + + /* The index within the Extra Edge List of any parent after the first two. */ + size_t extra_parents_index; + + /* The SHA-1 hash of the root tree of the commit. */ + git_oid tree_oid; + + /* The SHA-1 hash of the requested commit. */ + git_oid sha1; +} git_commit_graph_entry; + int git_commit_graph_open(git_commit_graph_file **cgraph_out, const char *path); + +/* + * Returns whether the commit_graph_file needs to be reloaded since the + * contents of the commit-graph file have changed on disk. If `path` is NULL, + * the filename stored in `cgraph` will be used. + */ +bool git_commit_graph_needs_refresh(const git_commit_graph_file *cgraph, const char *path); + +int git_commit_graph_entry_find( + git_commit_graph_entry *e, + const git_commit_graph_file *cgraph, + const git_oid *short_oid, + size_t len); +int git_commit_graph_entry_parent( + git_commit_graph_entry *parent, + const git_commit_graph_file *cgraph, + const git_commit_graph_entry *entry, + size_t n); int git_commit_graph_close(git_commit_graph_file *cgraph); void git_commit_graph_free(git_commit_graph_file *cgraph); diff --git a/src/merge.c b/src/merge.c index e02ea9169..82b028b4a 100644 --- a/src/merge.c +++ b/src/merge.c @@ -2277,8 +2277,11 @@ static int create_virtual_base( result->type = GIT_ANNOTATED_COMMIT_VIRTUAL; result->index = index; - insert_head_ids(&result->parents, one); - insert_head_ids(&result->parents, two); + if (insert_head_ids(&result->parents, one) < 0 || + insert_head_ids(&result->parents, two) < 0) { + git_annotated_commit_free(result); + return -1; + } *out = result; return 0; diff --git a/tests/graph/commit_graph.c b/tests/graph/commit_graph.c index 329aa5b00..4c7c5a726 100644 --- a/tests/graph/commit_graph.c +++ b/tests/graph/commit_graph.c @@ -8,11 +8,81 @@ void test_graph_commit_graph__parse(void) { git_repository *repo; struct git_commit_graph_file *cgraph; + struct git_commit_graph_entry e, parent; + git_oid id; git_buf commit_graph_path = GIT_BUF_INIT; cl_git_pass(git_repository_open(&repo, cl_fixture("testrepo.git"))); cl_git_pass(git_buf_joinpath(&commit_graph_path, git_repository_path(repo), "objects/info/commit-graph")); cl_git_pass(git_commit_graph_open(&cgraph, git_buf_cstr(&commit_graph_path))); + cl_assert_equal_i(git_commit_graph_needs_refresh(cgraph, git_buf_cstr(&commit_graph_path)), 0); + + cl_git_pass(git_oid_fromstr(&id, "5001298e0c09ad9c34e4249bc5801c75e9754fa5")); + cl_git_pass(git_commit_graph_entry_find(&e, cgraph, &id, GIT_OID_HEXSZ)); + cl_assert_equal_oid(&e.sha1, &id); + cl_git_pass(git_oid_fromstr(&id, "418382dff1ffb8bdfba833f4d8bbcde58b1e7f47")); + cl_assert_equal_oid(&e.tree_oid, &id); + cl_assert_equal_i(e.generation, 1); + cl_assert_equal_i(e.commit_time, 1273610423ull); + cl_assert_equal_i(e.parent_count, 0); + + cl_git_pass(git_oid_fromstr(&id, "be3563ae3f795b2b4353bcce3a527ad0a4f7f644")); + cl_git_pass(git_commit_graph_entry_find(&e, cgraph, &id, GIT_OID_HEXSZ)); + cl_assert_equal_oid(&e.sha1, &id); + cl_assert_equal_i(e.generation, 5); + cl_assert_equal_i(e.commit_time, 1274813907ull); + cl_assert_equal_i(e.parent_count, 2); + + cl_git_pass(git_oid_fromstr(&id, "9fd738e8f7967c078dceed8190330fc8648ee56a")); + cl_git_pass(git_commit_graph_entry_parent(&parent, cgraph, &e, 0)); + cl_assert_equal_oid(&parent.sha1, &id); + cl_assert_equal_i(parent.generation, 4); + + cl_git_pass(git_oid_fromstr(&id, "c47800c7266a2be04c571c04d5a6614691ea99bd")); + cl_git_pass(git_commit_graph_entry_parent(&parent, cgraph, &e, 1)); + cl_assert_equal_oid(&parent.sha1, &id); + cl_assert_equal_i(parent.generation, 3); + + git_commit_graph_free(cgraph); + git_repository_free(repo); + git_buf_dispose(&commit_graph_path); +} + +void test_graph_commit_graph__parse_octopus_merge(void) +{ + git_repository *repo; + struct git_commit_graph_file *cgraph; + struct git_commit_graph_entry e, parent; + git_oid id; + git_buf commit_graph_path = GIT_BUF_INIT; + + cl_git_pass(git_repository_open(&repo, cl_fixture("merge-recursive/.gitted"))); + cl_git_pass(git_buf_joinpath(&commit_graph_path, git_repository_path(repo), "objects/info/commit-graph")); + cl_git_pass(git_commit_graph_open(&cgraph, git_buf_cstr(&commit_graph_path))); + + cl_git_pass(git_oid_fromstr(&id, "d71c24b3b113fd1d1909998c5bfe33b86a65ee03")); + cl_git_pass(git_commit_graph_entry_find(&e, cgraph, &id, GIT_OID_HEXSZ)); + cl_assert_equal_oid(&e.sha1, &id); + cl_git_pass(git_oid_fromstr(&id, "348f16ffaeb73f319a75cec5b16a0a47d2d5e27c")); + cl_assert_equal_oid(&e.tree_oid, &id); + cl_assert_equal_i(e.generation, 7); + cl_assert_equal_i(e.commit_time, 1447083009ull); + cl_assert_equal_i(e.parent_count, 3); + + cl_git_pass(git_oid_fromstr(&id, "ad2ace9e15f66b3d1138922e6ffdc3ea3f967fa6")); + cl_git_pass(git_commit_graph_entry_parent(&parent, cgraph, &e, 0)); + cl_assert_equal_oid(&parent.sha1, &id); + cl_assert_equal_i(parent.generation, 6); + + cl_git_pass(git_oid_fromstr(&id, "483065df53c0f4a02cdc6b2910b05d388fc17ffb")); + cl_git_pass(git_commit_graph_entry_parent(&parent, cgraph, &e, 1)); + cl_assert_equal_oid(&parent.sha1, &id); + cl_assert_equal_i(parent.generation, 2); + + cl_git_pass(git_oid_fromstr(&id, "815b5a1c80ca749d705c7aa0cb294a00cbedd340")); + cl_git_pass(git_commit_graph_entry_parent(&parent, cgraph, &e, 2)); + cl_assert_equal_oid(&parent.sha1, &id); + cl_assert_equal_i(parent.generation, 6); git_commit_graph_free(cgraph); git_repository_free(repo); diff --git a/tests/resources/merge-recursive/.gitted/objects/info/commit-graph b/tests/resources/merge-recursive/.gitted/objects/info/commit-graph Binary files differnew file mode 100644 index 000000000..da055f180 --- /dev/null +++ b/tests/resources/merge-recursive/.gitted/objects/info/commit-graph |