From patchwork Thu Jun 4 07:27:57 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Abhishek Kumar X-Patchwork-Id: 11587109 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id A521914E3 for ; Thu, 4 Jun 2020 07:30:01 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 8597B20899 for ; Thu, 4 Jun 2020 07:30:01 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="tBhazdlo" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728214AbgFDH35 (ORCPT ); Thu, 4 Jun 2020 03:29:57 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:44770 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728145AbgFDH3y (ORCPT ); Thu, 4 Jun 2020 03:29:54 -0400 Received: from mail-pg1-x543.google.com (mail-pg1-x543.google.com [IPv6:2607:f8b0:4864:20::543]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8D0C1C05BD1E for ; Thu, 4 Jun 2020 00:29:53 -0700 (PDT) Received: by mail-pg1-x543.google.com with SMTP id n23so3055770pgb.12 for ; Thu, 04 Jun 2020 00:29:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=RvxBuCutDVGe4b7HkC31Y6mQZcX3z37QQdSYYPKL2GM=; b=tBhazdlodHT6vZlKrs2W9QJDbnEh6hyhiGYGcjQYPRL3SyYmg6mQMgQI6X5NBo6QdX M0RrQTiqN3TPxPSjaBHqX+31OT7wsrI8lYYdcRsq2HvCmuQD9OkBpmU4GjhUsNqdwukJ O1X4iZ+w7qoZ8OK0JCXBf+nD8qLE8+7A5x1fCzu+4jBzkEnSUy7YZ6FC+o2n6Wareq3M hNv2LWQ0Ha8ac6Wo09vMmZemYGTGIHBwrQ6Xy3BUnpHbYOzC/p3kBbnn5jBN7CccfFYL tCweVmzH25OOgA7r1D6LdRGseceGLBj2YyntKV+0mH79xT4eRfpsRPxl79UFpFoczUKb uTnw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=RvxBuCutDVGe4b7HkC31Y6mQZcX3z37QQdSYYPKL2GM=; b=HSXxabyPdDYbKftwxsTSnS2G6r7VTgp1rG00FDjtyGVxviGqpFNmrReyxnHxmJDxhh Cmp+Xz92s9NWIeTn9hWTsL0ob9G4grjzorLQkix3ESxUjKVe0LKLLF1Hf8B57svnJlCS ZBZR50w+E7UUz2mCEqNJ1U8/l9kup1iborvku1VoPmNFN14gn3Qv2ZzIZ6V6etXjOWpS kd2i1FNiVzsGqBswSDe8OvtkTyHLAdwkIfNHXPmM5bkRH3dhXrXeA6QaXXJXrtGGCfGN jbRCjKVu2IX1AMdiTTEfXQxMmKmKfh7PHb64aJr0KztkiheVhb9lRYraWW1dkbY3YnGd JSOA== X-Gm-Message-State: AOAM531NfFyoHiOz1YGMV6H3MVp5pIWGtjr5xBDkVYL5UQsOsXW5UlmH BUMvAv8Ng3b9Bz1vtKCvsq5Ivh2p X-Google-Smtp-Source: ABdhPJzVGrPk8M617zM4XJfVZHNBJEN7O8K396BFKnpCPANpg46zpAhfYWkM8Dr4XK5yu+zu3sZ8pA== X-Received: by 2002:a63:ec0c:: with SMTP id j12mr3116746pgh.255.1591255792603; Thu, 04 Jun 2020 00:29:52 -0700 (PDT) Received: from localhost.localdomain ([2409:4064:2480:9552:2003:1696:484d:e269]) by smtp.gmail.com with ESMTPSA id c12sm3335108pgt.91.2020.06.04.00.29.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 04 Jun 2020 00:29:51 -0700 (PDT) From: Abhishek Kumar To: git@vger.kernel.org Cc: stolee@gmail.com, jnareb@gmail.com Subject: [GSoC Patch 1/3] commit: introduce helpers for generation slab Date: Thu, 4 Jun 2020 12:57:57 +0530 Message-Id: <20200604072759.19142-2-abhishekkumar8222@gmail.com> X-Mailer: git-send-email 2.27.0 In-Reply-To: <20200604072759.19142-1-abhishekkumar8222@gmail.com> References: <20200604072759.19142-1-abhishekkumar8222@gmail.com> MIME-Version: 1.0 Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org The struct member generation refers to "generation number" (or more broadly, a reachablity index value) used by commit-graph to reduce time taken to walk commits. However, generation is not useful in other contexts and bloats the struct. Let's move it to a commit-slab and shrink the struct by four bytes. Signed-off-by: Abhishek Kumar --- commit-graph.c | 27 +++++++++++++++++++++++++++ commit-graph.h | 5 +++++ commit.h | 3 --- 3 files changed, 32 insertions(+), 3 deletions(-) diff --git a/commit-graph.c b/commit-graph.c index e3420ddcbf..63f419048d 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -87,6 +87,33 @@ static int commit_pos_cmp(const void *va, const void *vb) commit_pos_at(&commit_pos, b); } +define_commit_slab(generation_slab, uint32_t); +static struct generation_slab generation_slab = COMMIT_SLAB_INIT(1, generation_slab); + +uint32_t generation(const struct commit *c) +{ + uint32_t *gen = generation_slab_peek(&generation_slab, c); + + return gen ? *gen : GENERATION_NUMBER_INFINITY; +} + +static void set_generation(const struct commit *c, const uint32_t generation) +{ + unsigned int i = generation_slab.slab_count; + uint32_t *gen = generation_slab_at(&generation_slab, c); + + /* + * commit-slab initializes with zero, overwrite this with + * GENERATION_NUMBER_INFINITY + */ + for (; i < generation_slab.slab_count; ++i) { + memset(generation_slab.slab[i], GENERATION_NUMBER_INFINITY, + generation_slab.slab_size * sizeof(uint32_t)); + } + + *gen = generation; +} + static int commit_gen_cmp(const void *va, const void *vb) { const struct commit *a = *(const struct commit **)va; diff --git a/commit-graph.h b/commit-graph.h index 4212766a4f..653bd041ad 100644 --- a/commit-graph.h +++ b/commit-graph.h @@ -8,6 +8,10 @@ #include "object-store.h" #include "oidset.h" +#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF +#define GENERATION_NUMBER_MAX 0x3FFFFFFF +#define GENERATION_NUMBER_ZERO 0 + #define GIT_TEST_COMMIT_GRAPH "GIT_TEST_COMMIT_GRAPH" #define GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD "GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD" #define GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS "GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS" @@ -137,4 +141,5 @@ void free_commit_graph(struct commit_graph *); */ void disable_commit_graph(struct repository *r); +uint32_t generation(const struct commit *c); #endif diff --git a/commit.h b/commit.h index 1b2dea5d85..cc610400d5 100644 --- a/commit.h +++ b/commit.h @@ -11,9 +11,6 @@ #include "commit-slab.h" #define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF -#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF -#define GENERATION_NUMBER_MAX 0x3FFFFFFF -#define GENERATION_NUMBER_ZERO 0 struct commit_list { struct commit *item; From patchwork Thu Jun 4 07:27:58 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Abhishek Kumar X-Patchwork-Id: 11587113 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 3A75114E3 for ; Thu, 4 Jun 2020 07:30:10 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 149B92074B for ; Thu, 4 Jun 2020 07:30:10 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="l5Ecx3T4" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728234AbgFDHaD (ORCPT ); Thu, 4 Jun 2020 03:30:03 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:44786 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728187AbgFDH37 (ORCPT ); Thu, 4 Jun 2020 03:29:59 -0400 Received: from mail-pf1-x444.google.com (mail-pf1-x444.google.com [IPv6:2607:f8b0:4864:20::444]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 30675C05BD1E for ; Thu, 4 Jun 2020 00:29:59 -0700 (PDT) Received: by mail-pf1-x444.google.com with SMTP id 64so2887321pfg.8 for ; Thu, 04 Jun 2020 00:29:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=ancEd3vOSQRZq9RdwjLktYexJ9kMToKV3T19WGteVYs=; b=l5Ecx3T4QQC0jwNsq+qCo7zBg3H1xCeLQFewF0dviaRzix87YapzMGxbHMzExEhz1h w9e4nFzSPFHOok134SKbXNrPpmfEJFEzlaRqlUpcV+++UnEB+ak3R+jdFdtqROunqvyP zOroWc+yQzjKJn940QJfJ+jeYyeEiVErOf0ZA+o9JotlH3kfBykcmCnST4twWC+FzI0+ cdjVO2Ik2mGlBZoOcDmYMkD8Lh1ozhT7nRT6m+wglk6FaKV+/oc5pg/gdQ1b5/2TiM6y jp0PJv3qxxa3DPJyNLkS/5vwAd8b1aLIflHZIIWWuWvry/XAnIfi3UcWNZXFtzo5RkQc 6kNw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=ancEd3vOSQRZq9RdwjLktYexJ9kMToKV3T19WGteVYs=; b=seAwhQt8VfZOvhAKK5Y74hyPnMuYVyZrsXAewpi1x+8A/aSaC6WQ+MPqaHSNqFuvg4 J8FnuBC27DFDo34Z/Ew/6a3lt/X2OKO6D1vz6xjwHaoNUUaSsJvhEmMwqQGBi4AX0CjE tJbiFroox+mUtlanBlXRmWZYKSYkkqoq/mtYO3GIqQaE67ccr5ieOMZ2tQ+B9KKCtSLg lpLciwg3xsZWCwtH3+UEEurf0xCrqf+yn4/xCMPoM93S73MtsQS/F2o3+v7dNOdvmilo SWTjnXVkV5q5ETxVr4VrFviq1R7oBTMNAWm+nnIFkcJCQGbVyDRIxQQyRzpvu5QOFbzV 1tMw== X-Gm-Message-State: AOAM533Gka2s3zm2VnJNut0sEwx4/RJ9qpI2bBhvMr+anu+UYweXccZx vkk2IPukeXTnwsJCAgNcHQm1c0kk X-Google-Smtp-Source: ABdhPJzc3x5zRUXRI4+cupqT4CB4nOvHpLEQkf4k5O+U0th2dL3fo/4cLEwJMNcvmfNwWWGWlLHQEg== X-Received: by 2002:a05:6a00:14ce:: with SMTP id w14mr3059854pfu.121.1591255797863; Thu, 04 Jun 2020 00:29:57 -0700 (PDT) Received: from localhost.localdomain ([2409:4064:2480:9552:2003:1696:484d:e269]) by smtp.gmail.com with ESMTPSA id c12sm3335108pgt.91.2020.06.04.00.29.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 04 Jun 2020 00:29:57 -0700 (PDT) From: Abhishek Kumar To: git@vger.kernel.org Cc: stolee@gmail.com, jnareb@gmail.com Subject: [GSoC Patch 2/3] commit: convert commit->generation to a slab Date: Thu, 4 Jun 2020 12:57:58 +0530 Message-Id: <20200604072759.19142-3-abhishekkumar8222@gmail.com> X-Mailer: git-send-email 2.27.0 In-Reply-To: <20200604072759.19142-1-abhishekkumar8222@gmail.com> References: <20200604072759.19142-1-abhishekkumar8222@gmail.com> MIME-Version: 1.0 Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org In this commit, we will use the generation slab helpers introduced in last commit and replace existing uses of commit->generation using 'contrib/coccinelle/generation.cocci' Signed-off-by: Abhishek Kumar --- alloc.c | 1 - blame.c | 2 +- commit-graph.c | 39 +++++++++++----------- commit-reach.c | 50 ++++++++++++++--------------- commit.c | 4 +-- commit.h | 1 - contrib/coccinelle/generation.cocci | 12 +++++++ revision.c | 16 ++++----- 8 files changed, 68 insertions(+), 57 deletions(-) create mode 100644 contrib/coccinelle/generation.cocci diff --git a/alloc.c b/alloc.c index 1c64c4dd16..cbed187094 100644 --- a/alloc.c +++ b/alloc.c @@ -109,7 +109,6 @@ void init_commit_node(struct repository *r, struct commit *c) c->object.type = OBJ_COMMIT; c->index = alloc_commit_index(r); c->graph_pos = COMMIT_NOT_FROM_GRAPH; - c->generation = GENERATION_NUMBER_INFINITY; } void *alloc_commit_node(struct repository *r) diff --git a/blame.c b/blame.c index da7e28800e..50e6316076 100644 --- a/blame.c +++ b/blame.c @@ -1272,7 +1272,7 @@ static int maybe_changed_path(struct repository *r, if (!bd) return 1; - if (origin->commit->generation == GENERATION_NUMBER_INFINITY) + if (generation(origin->commit) == GENERATION_NUMBER_INFINITY) return 1; filter = get_bloom_filter(r, origin->commit, 0); diff --git a/commit-graph.c b/commit-graph.c index 63f419048d..9ce7d4acb1 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -120,9 +120,9 @@ static int commit_gen_cmp(const void *va, const void *vb) const struct commit *b = *(const struct commit **)vb; /* lower generation commits first */ - if (a->generation < b->generation) + if (generation(a) < generation(b)) return -1; - else if (a->generation > b->generation) + else if (generation(a) > generation(b)) return 1; /* use date as a heuristic when generations are equal */ @@ -712,7 +712,7 @@ static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, lex_index = pos - g->num_commits_in_base; commit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * lex_index; item->graph_pos = pos; - item->generation = get_be32(commit_data + g->hash_len + 8) >> 2; + set_generation(item, get_be32(commit_data + g->hash_len + 8) >> 2); } static inline void set_commit_tree(struct commit *c, struct tree *t) @@ -754,7 +754,7 @@ static int fill_commit_in_graph(struct repository *r, date_low = get_be32(commit_data + g->hash_len + 12); item->date = (timestamp_t)((date_high << 32) | date_low); - item->generation = get_be32(commit_data + g->hash_len + 8) >> 2; + set_generation(item, get_be32(commit_data + g->hash_len + 8) >> 2); pptr = &item->parents; @@ -1048,7 +1048,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len, else packedDate[0] = 0; - packedDate[0] |= htonl((*list)->generation << 2); + packedDate[0] |= htonl(generation((*list)) << 2); packedDate[1] = htonl((*list)->date); hashwrite(f, packedDate, 8); @@ -1280,8 +1280,8 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx) ctx->commits.nr); for (i = 0; i < ctx->commits.nr; i++) { display_progress(ctx->progress, i + 1); - if (ctx->commits.list[i]->generation != GENERATION_NUMBER_INFINITY && - ctx->commits.list[i]->generation != GENERATION_NUMBER_ZERO) + if (generation(ctx->commits.list[i]) != GENERATION_NUMBER_INFINITY && + generation(ctx->commits.list[i]) != GENERATION_NUMBER_ZERO) continue; commit_list_insert(ctx->commits.list[i], &list); @@ -1292,22 +1292,23 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx) uint32_t max_generation = 0; for (parent = current->parents; parent; parent = parent->next) { - if (parent->item->generation == GENERATION_NUMBER_INFINITY || - parent->item->generation == GENERATION_NUMBER_ZERO) { + if (generation(parent->item) == GENERATION_NUMBER_INFINITY || + generation(parent->item) == GENERATION_NUMBER_ZERO) { all_parents_computed = 0; commit_list_insert(parent->item, &list); break; - } else if (parent->item->generation > max_generation) { - max_generation = parent->item->generation; + } else if (generation(parent->item) > max_generation) { + max_generation = generation(parent->item); } } if (all_parents_computed) { - current->generation = max_generation + 1; + set_generation(current, max_generation + 1); pop_commit(&list); - if (current->generation > GENERATION_NUMBER_MAX) - current->generation = GENERATION_NUMBER_MAX; + if (generation(current) > GENERATION_NUMBER_MAX) + set_generation(current, + GENERATION_NUMBER_MAX); } } } @@ -2314,8 +2315,8 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags) oid_to_hex(&graph_parents->item->object.oid), oid_to_hex(&odb_parents->item->object.oid)); - if (graph_parents->item->generation > max_generation) - max_generation = graph_parents->item->generation; + if (generation(graph_parents->item) > max_generation) + max_generation = generation(graph_parents->item); graph_parents = graph_parents->next; odb_parents = odb_parents->next; @@ -2325,7 +2326,7 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags) graph_report(_("commit-graph parent list for commit %s terminates early"), oid_to_hex(&cur_oid)); - if (!graph_commit->generation) { + if (!generation(graph_commit)) { if (generation_zero == GENERATION_NUMBER_EXISTS) graph_report(_("commit-graph has generation number zero for commit %s, but non-zero elsewhere"), oid_to_hex(&cur_oid)); @@ -2345,10 +2346,10 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags) if (max_generation == GENERATION_NUMBER_MAX) max_generation--; - if (graph_commit->generation != max_generation + 1) + if (generation(graph_commit) != max_generation + 1) graph_report(_("commit-graph generation for commit %s is %u != %u"), oid_to_hex(&cur_oid), - graph_commit->generation, + generation(graph_commit), max_generation + 1); if (graph_commit->date != odb_commit->date) diff --git a/commit-reach.c b/commit-reach.c index 4ca7e706a1..77c980054a 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -59,13 +59,13 @@ static struct commit_list *paint_down_to_common(struct repository *r, struct commit_list *parents; int flags; - if (min_generation && commit->generation > last_gen) + if (min_generation && generation(commit) > last_gen) BUG("bad generation skip %8x > %8x at %s", - commit->generation, last_gen, + generation(commit), last_gen, oid_to_hex(&commit->object.oid)); - last_gen = commit->generation; + last_gen = generation(commit); - if (commit->generation < min_generation) + if (generation(commit) < min_generation) break; flags = commit->object.flags & (PARENT1 | PARENT2 | STALE); @@ -176,7 +176,7 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt repo_parse_commit(r, array[i]); for (i = 0; i < cnt; i++) { struct commit_list *common; - uint32_t min_generation = array[i]->generation; + uint32_t min_generation = generation(array[i]); if (redundant[i]) continue; @@ -186,8 +186,8 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt filled_index[filled] = j; work[filled++] = array[j]; - if (array[j]->generation < min_generation) - min_generation = array[j]->generation; + if (generation(array[j]) < min_generation) + min_generation = generation(array[j]); } common = paint_down_to_common(r, array[i], filled, work, min_generation); @@ -323,16 +323,16 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit, for (i = 0; i < nr_reference; i++) { if (repo_parse_commit(r, reference[i])) return ret; - if (reference[i]->generation < min_generation) - min_generation = reference[i]->generation; + if (generation(reference[i]) < min_generation) + min_generation = generation(reference[i]); } - if (commit->generation > min_generation) + if (generation(commit) > min_generation) return ret; bases = paint_down_to_common(r, commit, nr_reference, reference, - commit->generation); + generation(commit)); if (commit->object.flags & PARENT2) ret = 1; clear_commit_marks(commit, all_flags); @@ -467,7 +467,7 @@ static enum contains_result contains_test(struct commit *candidate, /* Otherwise, we don't know; prepare to recurse */ parse_commit_or_die(candidate); - if (candidate->generation < cutoff) + if (generation(candidate) < cutoff) return CONTAINS_NO; return CONTAINS_UNKNOWN; @@ -492,8 +492,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate, for (p = want; p; p = p->next) { struct commit *c = p->item; load_commit_graph_info(the_repository, c); - if (c->generation < cutoff) - cutoff = c->generation; + if (generation(c) < cutoff) + cutoff = generation(c); } result = contains_test(candidate, want, cache, cutoff); @@ -544,9 +544,9 @@ static int compare_commits_by_gen(const void *_a, const void *_b) const struct commit *a = *(const struct commit * const *)_a; const struct commit *b = *(const struct commit * const *)_b; - if (a->generation < b->generation) + if (generation(a) < generation(b)) return -1; - if (a->generation > b->generation) + if (generation(a) > generation(b)) return 1; return 0; } @@ -585,7 +585,7 @@ int can_all_from_reach_with_flag(struct object_array *from, list[nr_commits] = (struct commit *)from_one; if (parse_commit(list[nr_commits]) || - list[nr_commits]->generation < min_generation) { + generation(list[nr_commits]) < min_generation) { result = 0; goto cleanup; } @@ -621,7 +621,7 @@ int can_all_from_reach_with_flag(struct object_array *from, if (parse_commit(parent->item) || parent->item->date < min_commit_date || - parent->item->generation < min_generation) + generation(parent->item) < min_generation) continue; commit_list_insert(parent->item, &stack); @@ -665,8 +665,8 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to, if (from_iter->item->date < min_commit_date) min_commit_date = from_iter->item->date; - if (from_iter->item->generation < min_generation) - min_generation = from_iter->item->generation; + if (generation(from_iter->item) < min_generation) + min_generation = generation(from_iter->item); } from_iter = from_iter->next; @@ -677,8 +677,8 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to, if (to_iter->item->date < min_commit_date) min_commit_date = to_iter->item->date; - if (to_iter->item->generation < min_generation) - min_generation = to_iter->item->generation; + if (generation(to_iter->item) < min_generation) + min_generation = generation(to_iter->item); } to_iter->item->object.flags |= PARENT2; @@ -721,8 +721,8 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from, struct commit *c = *item; parse_commit(c); - if (c->generation < min_generation) - min_generation = c->generation; + if (generation(c) < min_generation) + min_generation = generation(c); if (!(c->object.flags & PARENT1)) { c->object.flags |= PARENT1; @@ -755,7 +755,7 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from, parse_commit(p); - if (p->generation < min_generation) + if (generation(p) < min_generation) continue; if (p->object.flags & PARENT2) diff --git a/commit.c b/commit.c index 87686a7055..8dad0f8446 100644 --- a/commit.c +++ b/commit.c @@ -731,9 +731,9 @@ int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void const struct commit *a = a_, *b = b_; /* newer commits first */ - if (a->generation < b->generation) + if (generation(a) < generation(b)) return 1; - else if (a->generation > b->generation) + else if (generation(a) > generation(b)) return -1; /* use date as a heuristic when generations are equal */ diff --git a/commit.h b/commit.h index cc610400d5..01e1c4c3eb 100644 --- a/commit.h +++ b/commit.h @@ -34,7 +34,6 @@ struct commit { */ struct tree *maybe_tree; uint32_t graph_pos; - uint32_t generation; unsigned int index; }; diff --git a/contrib/coccinelle/generation.cocci b/contrib/coccinelle/generation.cocci new file mode 100644 index 0000000000..da13c44856 --- /dev/null +++ b/contrib/coccinelle/generation.cocci @@ -0,0 +1,12 @@ +@@ +struct commit *c; +expression E; +@@ +- c->generation = E ++ set_generation(c, E) + +@@ +struct commit *c; +@@ +- c->generation ++ generation(c) diff --git a/revision.c b/revision.c index 60cca8c0b9..d76382007c 100644 --- a/revision.c +++ b/revision.c @@ -720,7 +720,7 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs, if (!revs->repo->objects->commit_graph) return -1; - if (commit->generation == GENERATION_NUMBER_INFINITY) + if (generation(commit) == GENERATION_NUMBER_INFINITY) return -1; filter = get_bloom_filter(revs->repo, commit, 0); @@ -3314,7 +3314,7 @@ static void explore_to_depth(struct rev_info *revs, struct topo_walk_info *info = revs->topo_walk_info; struct commit *c; while ((c = prio_queue_peek(&info->explore_queue)) && - c->generation >= gen_cutoff) + generation(c) >= gen_cutoff) explore_walk_step(revs); } @@ -3330,7 +3330,7 @@ static void indegree_walk_step(struct rev_info *revs) if (parse_commit_gently(c, 1) < 0) return; - explore_to_depth(revs, c->generation); + explore_to_depth(revs, generation(c)); for (p = c->parents; p; p = p->next) { struct commit *parent = p->item; @@ -3354,7 +3354,7 @@ static void compute_indegrees_to_depth(struct rev_info *revs, struct topo_walk_info *info = revs->topo_walk_info; struct commit *c; while ((c = prio_queue_peek(&info->indegree_queue)) && - c->generation >= gen_cutoff) + generation(c) >= gen_cutoff) indegree_walk_step(revs); } @@ -3414,8 +3414,8 @@ static void init_topo_walk(struct rev_info *revs) test_flag_and_insert(&info->explore_queue, c, TOPO_WALK_EXPLORED); test_flag_and_insert(&info->indegree_queue, c, TOPO_WALK_INDEGREE); - if (c->generation < info->min_generation) - info->min_generation = c->generation; + if (generation(c) < info->min_generation) + info->min_generation = generation(c); *(indegree_slab_at(&info->indegree, c)) = 1; @@ -3473,8 +3473,8 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit) if (parse_commit_gently(parent, 1) < 0) continue; - if (parent->generation < info->min_generation) { - info->min_generation = parent->generation; + if (generation(parent) < info->min_generation) { + info->min_generation = generation(parent); compute_indegrees_to_depth(revs, info->min_generation); } From patchwork Thu Jun 4 07:27:59 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Abhishek Kumar X-Patchwork-Id: 11587111 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 8A6D714E3 for ; Thu, 4 Jun 2020 07:30:08 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 5DFE9207F9 for ; Thu, 4 Jun 2020 07:30:08 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="m4NXdGs8" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728248AbgFDHaF (ORCPT ); Thu, 4 Jun 2020 03:30:05 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:44800 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728242AbgFDHaE (ORCPT ); Thu, 4 Jun 2020 03:30:04 -0400 Received: from mail-pl1-x642.google.com (mail-pl1-x642.google.com [IPv6:2607:f8b0:4864:20::642]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id DD5C5C05BD1E for ; Thu, 4 Jun 2020 00:30:03 -0700 (PDT) Received: by mail-pl1-x642.google.com with SMTP id t16so1861685plo.7 for ; Thu, 04 Jun 2020 00:30:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=pBFV12diVbOYQ6HJcfExL/djUWV0D75u+tb0XBmy4Do=; b=m4NXdGs8COQvLggZ5x5ybayOYNyseDkzYbJBrWaMBm6HjqsmNL/mzgdYcL7G2HipAG CPYHy1s0kN7x+mzzbD9kcbNG8jc0KUk7s/+Joh6PAkn18marTcUrIc4GeW0VKmIg0HZE exVR3s+DN27B66SipSyhehzeBK4YMEd9vrIypLxNKeiqdtqXwByGClR3E2Uak2L9osUj CMaIh/CAj9dHBA9w2bTl9W/ab4MTb/0kSGdpLL/VOclLS25IvzELeIZ2RHUrXrMYl5QN ZsQ1yHJ2Hn05HGa+cr6K99EVuy4XEgnLVanbQjWZ85UeZUtFSFu6eB+RPjZpmBBNLYxA Uqsw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=pBFV12diVbOYQ6HJcfExL/djUWV0D75u+tb0XBmy4Do=; b=cXuVlKLraCmS021rtAVMyuNfrk9m28Zk9riWD9GQQp8j8FgtftqIsUfIB7Pel/Ylxl wTw71J2BtOJJzA2Ok7TibLtqLUCriLCWKt+RbT9nwnE6JN9aZdYcbAYWbPaRkKBd+MYM sK/nr0iW2jReFyFx8AWOPWYJKutS4dm8rLLTGJbIekANiVHRS5g0hUppc9hsZO0puu5N tqdC5N1XziG6hxSShKVyH73YuUXAGOMGZ2NYE6TU/AT6H2gxV0eXVKZGNBhJa/MPAGAH qM6HoJcNSvi8tsOrUDVSMNE+zTqunt/yhXOkEFX/SH8JHhLs77y6psncJLMN7NIs1Yy5 oG9Q== X-Gm-Message-State: AOAM531538tuMR1T7ZLl9auG/MdJyGksAG0rGEATVqTkWI7iE5q+mTsS yfJ80DWEWiiHhl1ZVVMmm3j3tvnJ X-Google-Smtp-Source: ABdhPJwai10FHN8rcMYw8IGm7AbkV5UC+9VabyKH7ayWcDo/scml8Z/5HaE7WheYwYxjXlrF+8hsNQ== X-Received: by 2002:a17:902:8303:: with SMTP id bd3mr3648286plb.217.1591255802806; Thu, 04 Jun 2020 00:30:02 -0700 (PDT) Received: from localhost.localdomain ([2409:4064:2480:9552:2003:1696:484d:e269]) by smtp.gmail.com with ESMTPSA id c12sm3335108pgt.91.2020.06.04.00.29.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 04 Jun 2020 00:30:02 -0700 (PDT) From: Abhishek Kumar To: git@vger.kernel.org Cc: stolee@gmail.com, jnareb@gmail.com Subject: [GSoC Patch 3/3] commit: convert commit->graph_pos to a slab Date: Thu, 4 Jun 2020 12:57:59 +0530 Message-Id: <20200604072759.19142-4-abhishekkumar8222@gmail.com> X-Mailer: git-send-email 2.27.0 In-Reply-To: <20200604072759.19142-1-abhishekkumar8222@gmail.com> References: <20200604072759.19142-1-abhishekkumar8222@gmail.com> MIME-Version: 1.0 Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org The member graph_pos refers to the integer position used to identify a commit in commit-graph files. However, graph_pos is not useful in other contexts and bloats the struct. Let's move it to a commit-slab and shrink the struct by four bytes. Existing references to graph_pos are replaced using 'contrib/coccinelle/graph_pos.cocci'. Signed-off-by: Abhishek Kumar --- alloc.c | 1 - bloom.c | 6 ++-- commit-graph.c | 50 +++++++++++++++++++++++------- commit-graph.h | 3 ++ commit.c | 2 +- commit.h | 2 -- contrib/coccinelle/graph_pos.cocci | 12 +++++++ 7 files changed, 58 insertions(+), 18 deletions(-) create mode 100644 contrib/coccinelle/graph_pos.cocci diff --git a/alloc.c b/alloc.c index cbed187094..f37fb3b8b6 100644 --- a/alloc.c +++ b/alloc.c @@ -108,7 +108,6 @@ void init_commit_node(struct repository *r, struct commit *c) { c->object.type = OBJ_COMMIT; c->index = alloc_commit_index(r); - c->graph_pos = COMMIT_NOT_FROM_GRAPH; } void *alloc_commit_node(struct repository *r) diff --git a/bloom.c b/bloom.c index 9b86aa3f59..5bee5bb0c1 100644 --- a/bloom.c +++ b/bloom.c @@ -34,14 +34,14 @@ static int load_bloom_filter_from_graph(struct commit_graph *g, { uint32_t lex_pos, start_index, end_index; - while (c->graph_pos < g->num_commits_in_base) + while (graph_pos(c) < g->num_commits_in_base) g = g->base_graph; /* The commit graph commit 'c' lives in doesn't carry bloom filters. */ if (!g->chunk_bloom_indexes) return 0; - lex_pos = c->graph_pos - g->num_commits_in_base; + lex_pos = graph_pos(c) - g->num_commits_in_base; end_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos); @@ -188,7 +188,7 @@ struct bloom_filter *get_bloom_filter(struct repository *r, if (!filter->data) { load_commit_graph_info(r, c); - if (c->graph_pos != COMMIT_NOT_FROM_GRAPH && + if (graph_pos(c) != COMMIT_NOT_FROM_GRAPH && r->objects->commit_graph->chunk_bloom_indexes) { if (load_bloom_filter_from_graph(r->objects->commit_graph, filter, c)) return filter; diff --git a/commit-graph.c b/commit-graph.c index 9ce7d4acb1..7ff460b442 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -87,6 +87,34 @@ static int commit_pos_cmp(const void *va, const void *vb) commit_pos_at(&commit_pos, b); } +define_commit_slab(graph_pos_slab, uint32_t); +static struct graph_pos_slab graph_pos_slab = COMMIT_SLAB_INIT(1, graph_pos_slab); + +uint32_t graph_pos(const struct commit *c) +{ + uint32_t *pos = graph_pos_slab_peek(&graph_pos_slab, c); + + return pos ? *pos : COMMIT_NOT_FROM_GRAPH; +} + +static void set_graph_pos(const struct commit *c, const uint32_t position) +{ + unsigned int i = graph_pos_slab.slab_count; + uint32_t *pos = graph_pos_slab_at(&graph_pos_slab, c); + + /* + * commit-slab initializes with zero, overwrite this with + * COMMIT_NOT_FROM_GRAPH + */ + for (; i < graph_pos_slab.slab_count; ++i) + { + memset(graph_pos_slab.slab[i], COMMIT_NOT_FROM_GRAPH, + graph_pos_slab.slab_size * sizeof(uint32_t)); + } + + *pos = position; +} + define_commit_slab(generation_slab, uint32_t); static struct generation_slab generation_slab = COMMIT_SLAB_INIT(1, generation_slab); @@ -697,7 +725,7 @@ static struct commit_list **insert_parent_or_die(struct repository *r, c = lookup_commit(r, &oid); if (!c) die(_("could not find commit %s"), oid_to_hex(&oid)); - c->graph_pos = pos; + set_graph_pos(c, pos); return &commit_list_insert(c, pptr)->next; } @@ -711,7 +739,7 @@ static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, lex_index = pos - g->num_commits_in_base; commit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * lex_index; - item->graph_pos = pos; + set_graph_pos(item, pos); set_generation(item, get_be32(commit_data + g->hash_len + 8) >> 2); } @@ -741,7 +769,7 @@ static int fill_commit_in_graph(struct repository *r, * Store the "full" position, but then use the * "local" position for the rest of the calculation. */ - item->graph_pos = pos; + set_graph_pos(item, pos); lex_index = pos - g->num_commits_in_base; commit_data = g->chunk_commit_data + (g->hash_len + 16) * lex_index; @@ -786,8 +814,8 @@ static int fill_commit_in_graph(struct repository *r, static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos) { - if (item->graph_pos != COMMIT_NOT_FROM_GRAPH) { - *pos = item->graph_pos; + if (graph_pos(item) != COMMIT_NOT_FROM_GRAPH) { + *pos = graph_pos(item); return 1; } else { struct commit_graph *cur_g = g; @@ -843,11 +871,11 @@ static struct tree *load_tree_for_commit(struct repository *r, struct object_id oid; const unsigned char *commit_data; - while (c->graph_pos < g->num_commits_in_base) + while (graph_pos(c) < g->num_commits_in_base) g = g->base_graph; commit_data = g->chunk_commit_data + - GRAPH_DATA_WIDTH * (c->graph_pos - g->num_commits_in_base); + GRAPH_DATA_WIDTH * (graph_pos(c) - g->num_commits_in_base); hashcpy(oid.hash, commit_data); set_commit_tree(c, lookup_tree(r, &oid)); @@ -861,7 +889,7 @@ static struct tree *get_commit_tree_in_graph_one(struct repository *r, { if (c->maybe_tree) return c->maybe_tree; - if (c->graph_pos == COMMIT_NOT_FROM_GRAPH) + if (graph_pos(c) == COMMIT_NOT_FROM_GRAPH) BUG("get_commit_tree_in_graph_one called from non-commit-graph commit"); return load_tree_for_commit(r, g, (struct commit *)c); @@ -1247,7 +1275,7 @@ static void close_reachable(struct write_commit_graph_context *ctx) continue; if (ctx->split) { if ((!parse_commit(commit) && - commit->graph_pos == COMMIT_NOT_FROM_GRAPH) || + graph_pos(commit) == COMMIT_NOT_FROM_GRAPH) || flags == COMMIT_GRAPH_SPLIT_REPLACE) add_missing_parents(ctx, commit); } else if (!parse_commit_no_graph(commit)) @@ -1493,7 +1521,7 @@ static uint32_t count_distinct_commits(struct write_commit_graph_context *ctx) if (ctx->split) { struct commit *c = lookup_commit(ctx->r, &ctx->oids.list[i]); - if (!c || c->graph_pos != COMMIT_NOT_FROM_GRAPH) + if (!c || graph_pos(c) != COMMIT_NOT_FROM_GRAPH) continue; } @@ -1527,7 +1555,7 @@ static void copy_oids_to_commits(struct write_commit_graph_context *ctx) ctx->commits.list[ctx->commits.nr] = lookup_commit(ctx->r, &ctx->oids.list[i]); if (ctx->split && flags != COMMIT_GRAPH_SPLIT_REPLACE && - ctx->commits.list[ctx->commits.nr]->graph_pos != COMMIT_NOT_FROM_GRAPH) + graph_pos(ctx->commits.list[ctx->commits.nr]) != COMMIT_NOT_FROM_GRAPH) continue; if (ctx->split && flags == COMMIT_GRAPH_SPLIT_REPLACE) diff --git a/commit-graph.h b/commit-graph.h index 653bd041ad..3cb59ba336 100644 --- a/commit-graph.h +++ b/commit-graph.h @@ -8,6 +8,7 @@ #include "object-store.h" #include "oidset.h" +#define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF #define GENERATION_NUMBER_INFINITY 0xFFFFFFFF #define GENERATION_NUMBER_MAX 0x3FFFFFFF #define GENERATION_NUMBER_ZERO 0 @@ -142,4 +143,6 @@ void free_commit_graph(struct commit_graph *); void disable_commit_graph(struct repository *r); uint32_t generation(const struct commit *c); + +uint32_t graph_pos(const struct commit *c); #endif diff --git a/commit.c b/commit.c index 8dad0f8446..da6de08b2b 100644 --- a/commit.c +++ b/commit.c @@ -339,7 +339,7 @@ struct tree *repo_get_commit_tree(struct repository *r, if (commit->maybe_tree || !commit->object.parsed) return commit->maybe_tree; - if (commit->graph_pos != COMMIT_NOT_FROM_GRAPH) + if (graph_pos(commit) != COMMIT_NOT_FROM_GRAPH) return get_commit_tree_in_graph(r, commit); return NULL; diff --git a/commit.h b/commit.h index 01e1c4c3eb..0b10464a10 100644 --- a/commit.h +++ b/commit.h @@ -10,8 +10,6 @@ #include "pretty.h" #include "commit-slab.h" -#define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF - struct commit_list { struct commit *item; struct commit_list *next; diff --git a/contrib/coccinelle/graph_pos.cocci b/contrib/coccinelle/graph_pos.cocci new file mode 100644 index 0000000000..0929164bdf --- /dev/null +++ b/contrib/coccinelle/graph_pos.cocci @@ -0,0 +1,12 @@ +@@ +struct commit *c; +expression E; +@@ +- c->graph_pos = E ++ set_graph_pos(c, E) + +@@ +struct commit *c; +@@ +- c->graph_pos ++ graph_pos(c)