git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
From: Jonathan Tan <jonathantanmy@google.com>
To: git@vger.kernel.org
Cc: Jonathan Tan <jonathantanmy@google.com>,
	peff@peff.net, steadmon@google.com
Subject: [PATCH 4/7] index-pack: remove redundant child field
Date: Mon, 24 Aug 2020 12:16:35 -0700	[thread overview]
Message-ID: <6fe6ede5ff2dabed0d7633bc2a385d9047b13cb3.1598296530.git.jonathantanmy@google.com> (raw)
In-Reply-To: <cover.1598296530.git.jonathantanmy@google.com>

This is refactoring 1 of 2 to simplify struct base_data.

In index-pack, each thread maintains a doubly-linked list of the delta
chain that it is currently processing (the "base" and "child" pointers
in struct base_data). When a thread exceeds the delta base cache limit
and needs to reclaim memory, it uses the "child" pointers to traverse
the lineage, reclaiming the memory of the eldest delta bases first.

A subsequent patch will perform memory reclaiming in a different way and
will thus no longer need the "child" pointer. Because the "child"
pointer is redundant even now, remove it so that the aforementioned
subsequent patch will be clearer. In the meantime, reclaim memory in the
reverse order of the "base" pointers.

Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
---
 builtin/index-pack.c | 41 ++++++++++++++++++++++-------------------
 1 file changed, 22 insertions(+), 19 deletions(-)

diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index 357e03b5aa..032716553c 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c
@@ -34,7 +34,6 @@ struct object_stat {
 
 struct base_data {
 	struct base_data *base;
-	struct base_data *child;
 	struct object_entry *obj;
 	void *data;
 	unsigned long size;
@@ -44,7 +43,6 @@ struct base_data {
 
 struct thread_local {
 	pthread_t thread;
-	struct base_data *base_cache;
 	size_t base_cache_used;
 	int pack_fd;
 };
@@ -380,27 +378,37 @@ static void free_base_data(struct base_data *c)
 	}
 }
 
-static void prune_base_data(struct base_data *retain)
+static void prune_base_data(struct base_data *youngest_child)
 {
 	struct base_data *b;
 	struct thread_local *data = get_thread_data();
-	for (b = data->base_cache;
-	     data->base_cache_used > delta_base_cache_limit && b;
-	     b = b->child) {
-		if (b->data && b != retain)
-			free_base_data(b);
+	struct base_data **ancestry = NULL;
+	size_t nr = 0, alloc = 0;
+	ssize_t i;
+
+	if (data->base_cache_used <= delta_base_cache_limit)
+		return;
+
+	/*
+	 * Free all ancestors of youngest_child until we have enough space,
+	 * starting with the oldest. (We cannot free youngest_child itself.)
+	 */
+	for (b = youngest_child->base; b != NULL; b = b->base) {
+		ALLOC_GROW(ancestry, nr + 1, alloc);
+		ancestry[nr++] = b;
 	}
+	for (i = nr - 1;
+	     i >= 0 && data->base_cache_used > delta_base_cache_limit;
+	     i--) {
+		if (ancestry[i]->data)
+			free_base_data(ancestry[i]);
+	}
+	free(ancestry);
 }
 
 static void link_base_data(struct base_data *base, struct base_data *c)
 {
-	if (base)
-		base->child = c;
-	else
-		get_thread_data()->base_cache = c;
-
 	c->base = base;
-	c->child = NULL;
 	if (c->data)
 		get_thread_data()->base_cache_used += c->size;
 	prune_base_data(c);
@@ -408,11 +416,6 @@ static void link_base_data(struct base_data *base, struct base_data *c)
 
 static void unlink_base_data(struct base_data *c)
 {
-	struct base_data *base = c->base;
-	if (base)
-		base->child = NULL;
-	else
-		get_thread_data()->base_cache = NULL;
 	free_base_data(c);
 }
 
-- 
2.28.0.297.g1956fa8f8d-goog


  parent reply	other threads:[~2020-08-24 19:17 UTC|newest]

Thread overview: 28+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-08-24 19:16 [PATCH 0/7] Better threaded delta resolution in index-pack (another try) Jonathan Tan
2020-08-24 19:16 ` [PATCH 1/7] Documentation: deltaBaseCacheLimit is per-thread Jonathan Tan
2020-08-24 19:16 ` [PATCH] fetch-pack: in partial clone, pass --promisor Jonathan Tan
2020-08-24 19:36   ` Jonathan Tan
2020-08-24 19:16 ` [PATCH 2/7] index-pack: remove redundant parameter Jonathan Tan
2020-08-24 21:01   ` Junio C Hamano
2020-08-24 19:16 ` [PATCH 3/7] index-pack: unify threaded and unthreaded code Jonathan Tan
2020-08-24 21:11   ` Junio C Hamano
2020-08-24 19:16 ` Jonathan Tan [this message]
2020-08-24 19:16 ` [PATCH 5/7] index-pack: calculate {ref,ofs}_{first,last} early Jonathan Tan
2020-08-24 19:16 ` [PATCH 6/7] index-pack: make resolve_delta() assume base data Jonathan Tan
2020-08-24 19:16 ` [PATCH 7/7] index-pack: make quantum of work smaller Jonathan Tan
2020-08-24 21:19   ` Junio C Hamano
2020-08-24 20:47 ` [PATCH 0/7] Better threaded delta resolution in index-pack (another try) Junio C Hamano
2020-08-24 21:27 ` [PATCH] fixup! index-pack: make quantum of work smaller Jonathan Tan
2020-08-24 22:08 ` [PATCH 0/7] Better threaded delta resolution in index-pack (another try) Jeff King
2020-08-25 18:11   ` Jonathan Tan
2020-08-25 21:18     ` Jeff King
2020-08-25 21:46       ` Jeff King
2020-09-08 19:48 ` [PATCH v2 " Jonathan Tan
2020-09-08 19:48   ` [PATCH v2 1/7] Documentation: deltaBaseCacheLimit is per-thread Jonathan Tan
2020-09-08 19:48   ` [PATCH v2 2/7] index-pack: remove redundant parameter Jonathan Tan
2020-09-08 19:48   ` [PATCH v2 3/7] index-pack: unify threaded and unthreaded code Jonathan Tan
2020-09-08 19:48   ` [PATCH v2 4/7] index-pack: remove redundant child field Jonathan Tan
2020-09-08 19:48   ` [PATCH v2 5/7] index-pack: calculate {ref,ofs}_{first,last} early Jonathan Tan
2020-09-08 19:48   ` [PATCH v2 6/7] index-pack: make resolve_delta() assume base data Jonathan Tan
2020-09-08 19:48   ` [PATCH v2 7/7] index-pack: make quantum of work smaller Jonathan Tan
2020-09-08 22:53   ` [PATCH v2 0/7] Better threaded delta resolution in index-pack (another try) Junio C Hamano

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=6fe6ede5ff2dabed0d7633bc2a385d9047b13cb3.1598296530.git.jonathantanmy@google.com \
    --to=jonathantanmy@google.com \
    --cc=git@vger.kernel.org \
    --cc=peff@peff.net \
    --cc=steadmon@google.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).