From patchwork Wed Oct 9 23:44:17 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Tan X-Patchwork-Id: 11182393 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 3F3161709 for ; Wed, 9 Oct 2019 23:44:33 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 1FEBC218DE for ; Wed, 9 Oct 2019 23:44:33 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="qXJ/qD+P" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1732476AbfJIXoc (ORCPT ); Wed, 9 Oct 2019 19:44:32 -0400 Received: from mail-pg1-f202.google.com ([209.85.215.202]:40669 "EHLO mail-pg1-f202.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1732454AbfJIXob (ORCPT ); Wed, 9 Oct 2019 19:44:31 -0400 Received: by mail-pg1-f202.google.com with SMTP id w5so2874630pgp.7 for ; Wed, 09 Oct 2019 16:44:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=date:in-reply-to:message-id:mime-version:references:subject:from:to :cc; bh=EadqpmqEO1sbalt3G0ZIdBP16QD9Yn0wEtGvxrBvS9I=; b=qXJ/qD+PL5O9hLclIKG6t1+u7hhn/cmCZs+RHwW2lCJyFSmDtMAx50K/JKCxqK7wJ2 wqdqHfhswZpqn+xjR59CiB5EvhKHmRLeZWMT9RGaG3e6Pe9sZWcCzTyEMqGw0cI1xrHi f1EkQysYGlD2QPubPB+6N+Mi8qX3BmxsHhD6gYNiTEx8A241d0hZj6J/8TPIXbov0/A7 mxGOSDnCDK7MwIbfCuajbdWQ0goAdwC1iN+LzIGIUGyVssDcr+KBAuJK6MwsMRxWy+1H CbYnVHVPU4cxlBQvWl7g/MGS4001FpXaRciXMonbo9c3wzbHtALx9EWPIR2OnS4q6dqc nd7A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=EadqpmqEO1sbalt3G0ZIdBP16QD9Yn0wEtGvxrBvS9I=; b=VV51Wd9QBnwso5lCXfDgofVdW7X3uQ4Q8hlU4fGmhDFkW+phRGY4q0r/q+DXcIXJYj LmkJ7f8T6zbw7BMOqiPgUNwFtDDsaUaOjD/tYgkTGPn/RSzDHv4oaAzz0bUigQ1WjUCE DXLoJpVkgOLdgcn39c1aSl1tU/2RVk9u0VJHOhQnOifKi05SU+enib2UG4M4qDst5lbx qgtC7uFkW9VV5eeNH/fB5dfU8jJTETT9JUkXGBuiATsgQu4KZ8Bn3bLgHfrlwQJ18jld vYg5JPaFAmP9khVaBqXUy2yEwfgVyhBdd2rEp/F+sjCZ1u7m4rMng9VMAXefJZHMyNgT J8kQ== X-Gm-Message-State: APjAAAW+/ZwxaV3qm+UyB36LzgYMonWgav05l9qAZTSqA841KaAIPeoR sDD2fBnbD5JGaUvK3PxElcGcmzeImXYjeC9NjV7FM2swSPTPF2YvsGVwwim9KjZx7ozTtl4x33Z s5ijE9Xv4JKMpj9SHcRWNCudSWkqi73qB9lYw+R3fXY5l380Pap70imR7YFbIDESrFadGYB/iQh id X-Google-Smtp-Source: APXvYqxyxXd1Kx1W9Jaem3+nVUW2cRPloAjIU8KFEBBttKp6Xf2vOR8RGo5B+57jBSRrAk+/qhy+zaQ9JQzZf8J17lD3 X-Received: by 2002:a63:1b4a:: with SMTP id b10mr7266966pgm.450.1570664670464; Wed, 09 Oct 2019 16:44:30 -0700 (PDT) Date: Wed, 9 Oct 2019 16:44:17 -0700 In-Reply-To: Message-Id: <32ef0122a55bfbdbde0595b2aad930d83b27dd6d.1570663470.git.jonathantanmy@google.com> Mime-Version: 1.0 References: X-Mailer: git-send-email 2.23.0.581.g78d2f28ef7-goog Subject: [PATCH 1/6] index-pack: unify threaded and unthreaded code From: Jonathan Tan To: git@vger.kernel.org Cc: Jonathan Tan , peff@peff.net, mh@glandium.org Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Signed-off-by: Jonathan Tan --- builtin/index-pack.c | 10 +--------- 1 file changed, 1 insertion(+), 9 deletions(-) diff --git a/builtin/index-pack.c b/builtin/index-pack.c index a23454da6e..1a2600d4b3 100644 --- a/builtin/index-pack.c +++ b/builtin/index-pack.c @@ -1210,15 +1210,7 @@ static void resolve_deltas(void) cleanup_thread(); return; } - - for (i = 0; i < nr_objects; i++) { - struct object_entry *obj = &objects[i]; - - if (is_delta_type(obj->type)) - continue; - resolve_base(obj); - display_progress(progress, nr_resolved_deltas); - } + threaded_second_pass(¬hread_data); } /* From patchwork Wed Oct 9 23:44:18 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Tan X-Patchwork-Id: 11182395 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 F0F9C76 for ; Wed, 9 Oct 2019 23:44:36 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id D0B83218AC for ; Wed, 9 Oct 2019 23:44:36 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="HYbfYV2X" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1732480AbfJIXof (ORCPT ); Wed, 9 Oct 2019 19:44:35 -0400 Received: from mail-pg1-f202.google.com ([209.85.215.202]:50495 "EHLO mail-pg1-f202.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1732453AbfJIXof (ORCPT ); Wed, 9 Oct 2019 19:44:35 -0400 Received: by mail-pg1-f202.google.com with SMTP id r24so2848719pgj.17 for ; Wed, 09 Oct 2019 16:44:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=date:in-reply-to:message-id:mime-version:references:subject:from:to :cc; bh=aAAGT4NUjKelOyrzYd7LK/IP6qzbo5FVS6y/TzQyBAI=; b=HYbfYV2XKme90/AIpKwFJpk44CCHx4r8+q8kA3jRhSK0tMw/2ZhXNaiOxStA7FScut rsN/CsHoyvZA+SBhuBnY9kk2M+3eluRkmJ1YG0ayQrBq5AZl+nOQHwsOeLHsv27fHoBi mGfWamzZkPuPt+q9WgLrM7xDW42MIgnEYQQC8R7RD1c326TyDosp4XCd0e4aeA4iq7w9 MZzZeNxAoF/ui63aG6lgZjfCA/OcOVENNZDMeoEGl9ni4Gxiw/uOg3UIi0YuWwrfj+cY bne0MoYs8Fh1DKmzJmnyRSeA2r4ibHaBGIF/KlX8j27DJAAbmXRBEQ1/PHS31vNrP/sY gHVQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=aAAGT4NUjKelOyrzYd7LK/IP6qzbo5FVS6y/TzQyBAI=; b=n0Pv1fE5J/93XCwkSAwRCTWt+4RdbCllwcnCmGTXMuRElBY8XqP/tIowr36jshqd/4 eop3wbBuV3nAM5Q1RSAspsV9DLvYXiRpO5oOexan8qKjBLPgMJiA+TvQvg3ajFyTgOCZ KTBZFVESv3aapNow0s25LIyCi3Mk8/rWssXt/lmOhG1rnP+4i+ObPva2c6ogco3TGcRi 6lIGjzfwbc4aco+oNreh910TjJuW6e1VuEXrCOS4vx/DhuzSUa71PDNZQk0fJm46M66W xWGM+xTJEY030mVD27lwtsA9iiG67fFxAevBiGIocWsk+PUZMSWDcfswAzrdvuXJR0TG gOwA== X-Gm-Message-State: APjAAAXP8tSaGhJtk4UVohFSM5qRnc1LM4P2I1GEXZcrT0+u5jno3x8U v1dikypyNPAvLzqIW301Ow3FZf+wmnTHNAIe3ozInvfqAc2/glNap45UR8OhT8KH22YzP4+BaBu kAgte/iB9fBFTX8Ep71ILQ9ml4fiKRWUbc5zhxHzBCzX4MS4ATCDwJng5Oei5R9aEsEQc3Iopho 5i X-Google-Smtp-Source: APXvYqxdjideep1pLHhT+s6QudyoLVQqy88HcnyiSNOhEZPSKLvpydHMjSMohkv88xZHRASPXIe1x4LxxGU9lVTPCKGs X-Received: by 2002:a65:5a08:: with SMTP id y8mr7151913pgs.4.1570664673042; Wed, 09 Oct 2019 16:44:33 -0700 (PDT) Date: Wed, 9 Oct 2019 16:44:18 -0700 In-Reply-To: Message-Id: Mime-Version: 1.0 References: X-Mailer: git-send-email 2.23.0.581.g78d2f28ef7-goog Subject: [PATCH 2/6] index-pack: remove redundant parameter From: Jonathan Tan To: git@vger.kernel.org Cc: Jonathan Tan , peff@peff.net, mh@glandium.org Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Signed-off-by: Jonathan Tan --- builtin/index-pack.c | 26 ++++++++++++-------------- 1 file changed, 12 insertions(+), 14 deletions(-) diff --git a/builtin/index-pack.c b/builtin/index-pack.c index 1a2600d4b3..99f6e2957f 100644 --- a/builtin/index-pack.c +++ b/builtin/index-pack.c @@ -614,7 +614,7 @@ static int compare_ofs_delta_bases(off_t offset1, off_t offset2, 0; } -static int find_ofs_delta(const off_t offset, enum object_type type) +static int find_ofs_delta(const off_t offset) { int first = 0, last = nr_ofs_deltas; @@ -624,7 +624,8 @@ static int find_ofs_delta(const off_t offset, enum object_type type) int cmp; cmp = compare_ofs_delta_bases(offset, delta->offset, - type, objects[delta->obj_no].type); + OBJ_OFS_DELTA, + objects[delta->obj_no].type); if (!cmp) return next; if (cmp < 0) { @@ -637,10 +638,9 @@ static int find_ofs_delta(const off_t offset, enum object_type type) } static void find_ofs_delta_children(off_t offset, - int *first_index, int *last_index, - enum object_type type) + int *first_index, int *last_index) { - int first = find_ofs_delta(offset, type); + int first = find_ofs_delta(offset); int last = first; int end = nr_ofs_deltas - 1; @@ -668,7 +668,7 @@ static int compare_ref_delta_bases(const struct object_id *oid1, return oidcmp(oid1, oid2); } -static int find_ref_delta(const struct object_id *oid, enum object_type type) +static int find_ref_delta(const struct object_id *oid) { int first = 0, last = nr_ref_deltas; @@ -678,7 +678,8 @@ static int find_ref_delta(const struct object_id *oid, enum object_type type) int cmp; cmp = compare_ref_delta_bases(oid, &delta->oid, - type, objects[delta->obj_no].type); + OBJ_REF_DELTA, + objects[delta->obj_no].type); if (!cmp) return next; if (cmp < 0) { @@ -691,10 +692,9 @@ static int find_ref_delta(const struct object_id *oid, enum object_type type) } static void find_ref_delta_children(const struct object_id *oid, - int *first_index, int *last_index, - enum object_type type) + int *first_index, int *last_index) { - int first = find_ref_delta(oid, type); + int first = find_ref_delta(oid); int last = first; int end = nr_ref_deltas - 1; @@ -982,12 +982,10 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base, { if (base->ref_last == -1 && base->ofs_last == -1) { find_ref_delta_children(&base->obj->idx.oid, - &base->ref_first, &base->ref_last, - OBJ_REF_DELTA); + &base->ref_first, &base->ref_last); find_ofs_delta_children(base->obj->idx.offset, - &base->ofs_first, &base->ofs_last, - OBJ_OFS_DELTA); + &base->ofs_first, &base->ofs_last); if (base->ref_last == -1 && base->ofs_last == -1) { free(base->data); From patchwork Wed Oct 9 23:44:19 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Tan X-Patchwork-Id: 11182397 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 476FA1709 for ; Wed, 9 Oct 2019 23:44:39 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 29117218DE for ; Wed, 9 Oct 2019 23:44:39 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="NMY4gDNY" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1732487AbfJIXoi (ORCPT ); Wed, 9 Oct 2019 19:44:38 -0400 Received: from mail-pg1-f201.google.com ([209.85.215.201]:53073 "EHLO mail-pg1-f201.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1732453AbfJIXoh (ORCPT ); Wed, 9 Oct 2019 19:44:37 -0400 Received: by mail-pg1-f201.google.com with SMTP id e15so2853724pgh.19 for ; Wed, 09 Oct 2019 16:44:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=date:in-reply-to:message-id:mime-version:references:subject:from:to :cc; bh=ReEftmItdZV8emeyllp25+fFy04kQopQJdOw0/ZIGCE=; b=NMY4gDNYnpFsDxON3fsyApT+8gJ6xbwbiocxHFTLq3Ry7f/Aji5krCp9DbE4SZQJlj PW0i62yjaSC/spCK0O5FztkLHxXGbZ+TwHMYgizMfrFQ/svceDx2r2qhu8L1QuvvMjZp UdZcz0tMW7RPg+/yxcpBq5KVPcoI24WuEjxs7+b+jwzBgrWxwkaWeFm8lSKLikYwx9tV EA/qUpkYNxZnx095ICNLfQxZof1nkP6QkyA3aS28gI55slcqLSXRl2iG29aBu16JGtj9 n1wajC9Fds4ox+ppgZ6yAwZY+20M0+jHTJm8AZVPqPjAcEHt5QBub0WYdYz2up0hOxiW MOCw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=ReEftmItdZV8emeyllp25+fFy04kQopQJdOw0/ZIGCE=; b=jLJUaKTY3u5Im+b/fFVaEZ4x/yJub69OR8lAhNo1NpvGIm6pNvozltrI/lhypk8Dqc jupVQr14nOeOAQm3PvpYRiQSFRxrgV3DmgalIGRPk1/t8u39KSmlVwPYnjHEG67EYuZy 9nSPYf0R+LbTS2ZsUQuPka4GBFYGNrlOjWPkX2mXnxZ7PhFyr+apT7b9RK/z+yf/vzp6 IGHmYl9z/W7MZscOiVAu97VhKCRWBA4Fi4GT7HKTkm1bM1pS9/JrLLSk/AUWUfdT8Mcr uT56dhul/+zsU3lIkbyAs3c1cyL3XF9S4TLDbt9mgqesq9ITzKPic+aryChbmCUw9q7y BBMg== X-Gm-Message-State: APjAAAWcaQE+G7Li2z8Dz5tIVj803vM3GsNxsR0qfTZX3VFo+13V/77H 2eF53muI5iE9xonsWILqnhjK89j1z9vNaPSX9A2fnXffGFSKHnskwcxCDWuGU/N1DJNJscbWEKU GYQiIpNNQPwtmjzvcHo9/oJd4PHEmGDFpaPOuPIQ+VPYRqOn9PdgaojobsHBXndTUGuakObmI3F qR X-Google-Smtp-Source: APXvYqx5uC/btFz70MSoS0v6K3gzu9HesrtNiizH4bdtQEbCd7X8HYAOrLYS/5J7b+KOOJvDAfc/7ZgunJwfWhuxDoV+ X-Received: by 2002:a63:d457:: with SMTP id i23mr7107488pgj.276.1570664675374; Wed, 09 Oct 2019 16:44:35 -0700 (PDT) Date: Wed, 9 Oct 2019 16:44:19 -0700 In-Reply-To: Message-Id: <39740c6e58bd6cb6ea33e5abb4ab8542ff6eb7b7.1570663470.git.jonathantanmy@google.com> Mime-Version: 1.0 References: X-Mailer: git-send-email 2.23.0.581.g78d2f28ef7-goog Subject: [PATCH 3/6] index-pack: remove redundant child field From: Jonathan Tan To: git@vger.kernel.org Cc: Jonathan Tan , peff@peff.net, mh@glandium.org Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Instead, recompute ancestry if we ever need to reclaim memory. Signed-off-by: Jonathan Tan --- 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 99f6e2957f..35f7f9e52b 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; + int nr = 0, alloc = 0; + int 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); } From patchwork Wed Oct 9 23:44:20 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Tan X-Patchwork-Id: 11182399 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 D9D461709 for ; Wed, 9 Oct 2019 23:44:40 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id B1B88218DE for ; Wed, 9 Oct 2019 23:44:40 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="TqX/aWsm" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1732492AbfJIXoj (ORCPT ); Wed, 9 Oct 2019 19:44:39 -0400 Received: from mail-pg1-f202.google.com ([209.85.215.202]:50496 "EHLO mail-pg1-f202.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1732453AbfJIXoj (ORCPT ); Wed, 9 Oct 2019 19:44:39 -0400 Received: by mail-pg1-f202.google.com with SMTP id r24so2848791pgj.17 for ; Wed, 09 Oct 2019 16:44:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=date:in-reply-to:message-id:mime-version:references:subject:from:to :cc; bh=vfVKLDVvz1vgelhZRwxAz5ryowrHlYdbTANJzXjWwb0=; b=TqX/aWsm4MZT/VZ/0FwAf/gzbgTYOZ39MHdiAI3tDwHEJ0aT4JwueZDVvQS2CbWtUE 4KbuRuvfsb4uM6jzHV/HtoefSg8dUVlgbJEVQUGyrBnpEVdRmz+KwHN1vL9Xjap8OEF5 ALw7OmzGQqzbQ4AWnZCwj/2IReX3BsxxmQ4UGudyZDLDOwXJlPdTVgzVTdy1xYyskgf1 u0PW9D35ep6U3YF55ux9qL0BuKCQHgkunHrngQP9kbtun1r40sUXcgRkdmwUQAAvJn5S 62lhbzrbHHPdAlLx5NnXIUX9X0w8RCJRz0tHlPbpmV5V37koS7iVlu8g31XsCz500GmJ HDow== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=vfVKLDVvz1vgelhZRwxAz5ryowrHlYdbTANJzXjWwb0=; b=X1eTvBbZ94Dqtcx0fwlvQ+kTFI2nl7NZyqehtZKApgqPjrm1nG7nQRyisU/oqAE6qF dPIGpBAXrOIce6vglPakr0naIB3ELo2OTq5O6JPjLk63HMJ2TKQllbGFZscfkYsbEWtu iv0dFqoLRUtpXDOv4SwZbmbc97w1eXuYur47nk8lOhcKsdxQ33U4qlH7S2J2KaCgcqz3 2cQ32z4T155iQXqkl8HCPu/odosPK0Ql4ZWD7t2Sil7IZxqWei4sKIxYTH83JMss65QM qFX5O/JwpZ4QGYNhvJfLaP9ysBJ2rRX4dk/4zJwlUj55ldlmF7tcELcaTBxLMdePuN6J 8sFg== X-Gm-Message-State: APjAAAV9x+jzPsCtzezpoQTeWRIOEw27q1a1PZASBiCTAjlQ3Tsu9lbR PCfNVMsJOwiGLh97Idh85+zx+yAwvyN3xxVHSnC1jEje7xoct+9GFConDNIveAgKY+RWrIwXFYY TBeUwT+Pq8MRHubqKO7K9WvyD/e01EXidXimu5ml8PpHYRtp7Qf7nbMYDecEHARAfRSAJtgUTaP 10 X-Google-Smtp-Source: APXvYqyI2Qw/FidcEcsZxhpAuZKjE1DX0bXMrQwdBLUk0egzE0ocQJJzLkT3viOadvkScBBiPcIsAwmysd1wW8ecPAxt X-Received: by 2002:a65:5302:: with SMTP id m2mr6979084pgq.336.1570664677997; Wed, 09 Oct 2019 16:44:37 -0700 (PDT) Date: Wed, 9 Oct 2019 16:44:20 -0700 In-Reply-To: Message-Id: <0f0ffe71c5df9129a04546b8e3ed13a3ece1b9b1.1570663470.git.jonathantanmy@google.com> Mime-Version: 1.0 References: X-Mailer: git-send-email 2.23.0.581.g78d2f28ef7-goog Subject: [PATCH 4/6] index-pack: calculate {ref,ofs}_{first,last} early From: Jonathan Tan To: git@vger.kernel.org Cc: Jonathan Tan , peff@peff.net, mh@glandium.org Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Whenever we make a struct base_data, immediately calculate its delta children. This eliminates confusion as to when the {ref,ofs}_{first,last} fields are initialized. Signed-off-by: Jonathan Tan --- builtin/index-pack.c | 125 +++++++++++++++++++++---------------------- 1 file changed, 61 insertions(+), 64 deletions(-) diff --git a/builtin/index-pack.c b/builtin/index-pack.c index 35f7f9e52b..17997834ec 100644 --- a/builtin/index-pack.c +++ b/builtin/index-pack.c @@ -33,12 +33,15 @@ struct object_stat { }; struct base_data { + /* Initialized by make_base(). */ struct base_data *base; struct object_entry *obj; - void *data; - unsigned long size; int ref_first, ref_last; int ofs_first, ofs_last; + + /* Not initialized by make_base(). */ + void *data; + unsigned long size; }; struct thread_local { @@ -362,14 +365,6 @@ static void set_thread_data(struct thread_local *data) pthread_setspecific(key, data); } -static struct base_data *alloc_base_data(void) -{ - struct base_data *base = xcalloc(1, sizeof(struct base_data)); - base->ref_last = -1; - base->ofs_last = -1; - return base; -} - static void free_base_data(struct base_data *c) { if (c->data) { @@ -406,19 +401,6 @@ static void prune_base_data(struct base_data *youngest_child) free(ancestry); } -static void link_base_data(struct base_data *base, struct base_data *c) -{ - c->base = base; - if (c->data) - get_thread_data()->base_cache_used += c->size; - prune_base_data(c); -} - -static void unlink_base_data(struct base_data *c) -{ - free_base_data(c); -} - static int is_delta_type(enum object_type type) { return (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA); @@ -928,10 +910,25 @@ static void *get_base_data(struct base_data *c) return c->data; } -static void resolve_delta(struct object_entry *delta_obj, - struct base_data *base, struct base_data *result) +static struct base_data *make_base(struct object_entry *obj, + struct base_data *parent) { - void *base_data, *delta_data; + struct base_data *base = xcalloc(1, sizeof(struct base_data)); + base->base = parent; + base->obj = obj; + find_ref_delta_children(&obj->idx.oid, + &base->ref_first, &base->ref_last); + find_ofs_delta_children(obj->idx.offset, + &base->ofs_first, &base->ofs_last); + return base; +} + +static struct base_data *resolve_delta(struct object_entry *delta_obj, + struct base_data *base) +{ + void *base_data, *delta_data, *result_data; + struct base_data *result; + unsigned long result_size; if (show_stat) { int i = delta_obj - objects; @@ -945,19 +942,31 @@ static void resolve_delta(struct object_entry *delta_obj, } delta_data = get_data_from_pack(delta_obj); base_data = get_base_data(base); - result->obj = delta_obj; - result->data = patch_delta(base_data, base->size, - delta_data, delta_obj->size, &result->size); + result_data = patch_delta(base_data, base->size, + delta_data, delta_obj->size, &result_size); free(delta_data); - if (!result->data) + if (!result_data) bad_object(delta_obj->idx.offset, _("failed to apply delta")); - hash_object_file(result->data, result->size, + hash_object_file(result_data, result_size, type_name(delta_obj->real_type), &delta_obj->idx.oid); - sha1_object(result->data, NULL, result->size, delta_obj->real_type, + sha1_object(result_data, NULL, result_size, delta_obj->real_type, &delta_obj->idx.oid); + + result = make_base(delta_obj, base); + if (result->ref_last == -1 && result->ofs_last == -1) { + free(result_data); + } else { + result->data = result_data; + result->size = result_size; + get_thread_data()->base_cache_used += result->size; + prune_base_data(result); + } + counter_lock(); nr_resolved_deltas++; counter_unlock(); + + return result; } /* @@ -983,30 +992,15 @@ static int compare_and_swap_type(signed char *type, static struct base_data *find_unresolved_deltas_1(struct base_data *base, struct base_data *prev_base) { - if (base->ref_last == -1 && base->ofs_last == -1) { - find_ref_delta_children(&base->obj->idx.oid, - &base->ref_first, &base->ref_last); - - find_ofs_delta_children(base->obj->idx.offset, - &base->ofs_first, &base->ofs_last); - - if (base->ref_last == -1 && base->ofs_last == -1) { - free(base->data); - return NULL; - } - - link_base_data(prev_base, base); - } - if (base->ref_first <= base->ref_last) { struct object_entry *child = objects + ref_deltas[base->ref_first].obj_no; - struct base_data *result = alloc_base_data(); + struct base_data *result; if (!compare_and_swap_type(&child->real_type, OBJ_REF_DELTA, base->obj->real_type)) BUG("child->real_type != OBJ_REF_DELTA"); - resolve_delta(child, base, result); + result = resolve_delta(child, base); if (base->ref_first == base->ref_last && base->ofs_last == -1) free_base_data(base); @@ -1016,11 +1010,11 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base, if (base->ofs_first <= base->ofs_last) { struct object_entry *child = objects + ofs_deltas[base->ofs_first].obj_no; - struct base_data *result = alloc_base_data(); + struct base_data *result; assert(child->real_type == OBJ_OFS_DELTA); child->real_type = base->obj->real_type; - resolve_delta(child, base, result); + result = resolve_delta(child, base); if (base->ofs_first == base->ofs_last) free_base_data(base); @@ -1028,7 +1022,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base, return result; } - unlink_base_data(base); + free_base_data(base); return NULL; } @@ -1071,9 +1065,8 @@ static int compare_ref_delta_entry(const void *a, const void *b) static void resolve_base(struct object_entry *obj) { - struct base_data *base_obj = alloc_base_data(); - base_obj->obj = obj; - base_obj->data = NULL; + struct base_data *base_obj = make_base(obj, NULL); + find_unresolved_deltas(base_obj); } @@ -1367,21 +1360,25 @@ static void fix_unresolved_deltas(struct hashfile *f) for (i = 0; i < nr_ref_deltas; i++) { struct ref_delta_entry *d = sorted_by_pos[i]; enum object_type type; - struct base_data *base_obj = alloc_base_data(); + struct base_data *base; + void *data; + unsigned long size; + struct object_entry *obj; if (objects[d->obj_no].real_type != OBJ_REF_DELTA) continue; - base_obj->data = read_object_file(&d->oid, &type, - &base_obj->size); - if (!base_obj->data) + data = read_object_file(&d->oid, &type, &size); + if (!data) continue; - if (check_object_signature(&d->oid, base_obj->data, - base_obj->size, type_name(type))) + if (check_object_signature(&d->oid, data, + size, type_name(type))) die(_("local object %s is corrupt"), oid_to_hex(&d->oid)); - base_obj->obj = append_obj_to_pack(f, d->oid.hash, - base_obj->data, base_obj->size, type); - find_unresolved_deltas(base_obj); + obj = append_obj_to_pack(f, d->oid.hash, data, size, type); + base = make_base(obj, NULL); + base->data = data; + base->size = size; + find_unresolved_deltas(base); display_progress(progress, nr_resolved_deltas); } free(sorted_by_pos); From patchwork Wed Oct 9 23:44:21 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Tan X-Patchwork-Id: 11182401 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 157E176 for ; Wed, 9 Oct 2019 23:44:44 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id EA8C4218AC for ; Wed, 9 Oct 2019 23:44:43 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="Rqtdr2wC" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1732504AbfJIXon (ORCPT ); Wed, 9 Oct 2019 19:44:43 -0400 Received: from mail-pf1-f202.google.com ([209.85.210.202]:42785 "EHLO mail-pf1-f202.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1732453AbfJIXom (ORCPT ); Wed, 9 Oct 2019 19:44:42 -0400 Received: by mail-pf1-f202.google.com with SMTP id w16so3139431pfj.9 for ; Wed, 09 Oct 2019 16:44:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=date:in-reply-to:message-id:mime-version:references:subject:from:to :cc; bh=oawioSwaAUmu2ZZkSqQzGwRKasmcRDzuAeebAfPR2dI=; b=Rqtdr2wCwtU5P7RNpqHG8UeHzn8+6FecGDtq6+TM4Je/tHxlZQ9WmGpZbS/7EGai8I AJXEHOAhN9rnDDYKZnlmRbnlgvfcF0GlQTzMQ8fWnuP3ig5wH0RAn4Rgg0Ii9lYkB8mF /5a3uMwBXt1YL/f38oVOkY5C8zbKNHpBalMmRn/+U7W38CFpA5ACJRO2O4oTpQCAMa4Q EyE6fBkZf3gu/hgwhPJn5H87P8dlp+hsTp9nXX9mrHb6Gh0Le4qSk65HJfOk4pCg70GQ jdtOQZjBP5Umop3xXFFLoTOwkU7hMvkplEQ6aKlBldUpqK+dWgLjHwZxcWU5nC1+YtA4 KKrA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=oawioSwaAUmu2ZZkSqQzGwRKasmcRDzuAeebAfPR2dI=; b=Z+udgg0bYXj85v3jAuaSJHDdQksGFhFcleBWcrn9gqFW5rQl6PAWn0BjBNf79Jnp3F Ri3E4ywLQir/eEffBXz3Bwj0sSEoR+KUs8G4Po8V2qtzEqAUJhSOdDXvBD3kZfygr914 6tGl+QrQFsCTQyherCo0eomjM4lReBsmoh7NF5nexrfFNwy3Ao3LWXFyIeOqU3OOVfV2 JDcca7RHuN7n2xd6FZoioOBDhPpOzbwBUGdzly1MyAzJlbiKznzhERrTDJ7lYz/oKXUg 3chgi79KP64ORUFlT3VoflpamF0uRQytq59REQmCE7lB5jvpbEPFznDPaMOImUUIjk/T RVLw== X-Gm-Message-State: APjAAAUFFvRFPwFV8yv/UKmQvqeHYj+B4agqyIJudAs8j3t1u9mw7GKE ojnGt0IsXswYgRVHIkYMnkPy7ntHB6BsUFlilF+pQhgwT1M+TrZXEzRTB533dAJ1gSBWGX3zMNp gPSLIP4BXTGDObwRVpW/CcxZysm9J2J1wHTnKJDQ4phO/e2u6j6+phm9xpdu2QivY3iaqSaCP1G Ae X-Google-Smtp-Source: APXvYqwwuJuDAQ8SfV2THRpnsDbSwF2hliv6Gl4yuUM3i1IrcWMtrzrstkryXqATZrVHTthtjIi30Z0tfkxudtjrgp5y X-Received: by 2002:a63:c045:: with SMTP id z5mr7089447pgi.69.1570664680291; Wed, 09 Oct 2019 16:44:40 -0700 (PDT) Date: Wed, 9 Oct 2019 16:44:21 -0700 In-Reply-To: Message-Id: <6fcda102acd550818536c69c41c270a8058050a7.1570663470.git.jonathantanmy@google.com> Mime-Version: 1.0 References: X-Mailer: git-send-email 2.23.0.581.g78d2f28ef7-goog Subject: [PATCH 5/6] index-pack: make resolve_delta() assume base data From: Jonathan Tan To: git@vger.kernel.org Cc: Jonathan Tan , peff@peff.net, mh@glandium.org Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org A subsequent commit will make the quantum of work smaller, necessitating more locking. This commit allows resolve_delta() to be called outside the lock. Signed-off-by: Jonathan Tan --- builtin/index-pack.c | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) diff --git a/builtin/index-pack.c b/builtin/index-pack.c index 17997834ec..3908cd3115 100644 --- a/builtin/index-pack.c +++ b/builtin/index-pack.c @@ -926,7 +926,7 @@ static struct base_data *make_base(struct object_entry *obj, static struct base_data *resolve_delta(struct object_entry *delta_obj, struct base_data *base) { - void *base_data, *delta_data, *result_data; + void *delta_data, *result_data; struct base_data *result; unsigned long result_size; @@ -941,8 +941,8 @@ static struct base_data *resolve_delta(struct object_entry *delta_obj, obj_stat[i].base_object_no = j; } delta_data = get_data_from_pack(delta_obj); - base_data = get_base_data(base); - result_data = patch_delta(base_data, base->size, + assert(base->data); + result_data = patch_delta(base->data, base->size, delta_data, delta_obj->size, &result_size); free(delta_data); if (!result_data) @@ -1000,6 +1000,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base, base->obj->real_type)) BUG("child->real_type != OBJ_REF_DELTA"); + get_base_data(base); result = resolve_delta(child, base); if (base->ref_first == base->ref_last && base->ofs_last == -1) free_base_data(base); @@ -1014,6 +1015,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base, assert(child->real_type == OBJ_OFS_DELTA); child->real_type = base->obj->real_type; + get_base_data(base); result = resolve_delta(child, base); if (base->ofs_first == base->ofs_last) free_base_data(base); From patchwork Wed Oct 9 23:44:22 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Tan X-Patchwork-Id: 11182403 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 15F6076 for ; Wed, 9 Oct 2019 23:44:45 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id CEB21218AC for ; Wed, 9 Oct 2019 23:44:44 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="FxQ06aB/" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1732508AbfJIXoo (ORCPT ); Wed, 9 Oct 2019 19:44:44 -0400 Received: from mail-pf1-f201.google.com ([209.85.210.201]:46455 "EHLO mail-pf1-f201.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1732453AbfJIXon (ORCPT ); Wed, 9 Oct 2019 19:44:43 -0400 Received: by mail-pf1-f201.google.com with SMTP id f2so3133127pfk.13 for ; Wed, 09 Oct 2019 16:44:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=date:in-reply-to:message-id:mime-version:references:subject:from:to :cc; bh=Eb+VewUU2uRym4eGRLeJWQdvDDFUKR4i2a6K8n7E1yA=; b=FxQ06aB/+lxFHIo4RsFWYG7p1CtpqwYIqqZc1ILtnhbWJdud3WMafSCFrPV8wgoxw5 5B0ldoOvg15GEjayHClKJxMRCJRF08ZihZf6EFFynxRIVUlnUhvxOVLgyJax/8A2eCfT GvXgfV5mPcHAof+m0p3GWvwHgs1UKqgW/2xay8OsuLXkQqF43nBOmPoxEtUkYEjPvaeW JfyXJF+2NlAjq2jnk94+3vEdxwuD/lALPEwW0DlfgUaX35oHcGaBCMrqZWVpb2oG8RaT 9NzFnI+GiDqopppiS113ajm5rIIUAKDafBWOb2sBR3zhJ1ivqZsH8+Hhc4KWcEgLYqHx 1hnw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=Eb+VewUU2uRym4eGRLeJWQdvDDFUKR4i2a6K8n7E1yA=; b=ZDFcpT93KSbuRl5gL1FclFBWj/nkfS5d3vwd/aZ1hrA88jQGcWSzlbtBKnreXlJSol q9TXTdVl/uRm5Et/igfVPKnL4VwWUgRKO72mUkGggOt5KyjCy8/1ihBO3v/qM4Lgrm9B oUJ2aJ6wYEmVJnu0i4oejBdPxdr0u5aKAC+XR4e7gmp8KJ2qFewZPuRs4o+WBFpQoxtj sYjK3CFRaPW8W8ECs7OgfXEqIMlEQRybJC8Oaf1NB0VkZMQiA1uYRFkH73BiQXCxk/Uf vkuM3X97EJEkPME9+Bl7C9lLxhV2DEGGFJXIALuBmYq7qx3bWl+OYyKj25qUKAh1gsI9 ramQ== X-Gm-Message-State: APjAAAVqZ5j+MLI6QQTkhBS1tc2PETmjJ35JORQAfQ/cLkxhy4NhgdBw /WthPn2DWRdGjMkJ2XW7BwSmMamuLy44JQ6lpG8Es5FGfhkxkt8n2bMuyKyciwjP4I+3bbnecfw aPBLvDJg3dtE/hVl/ZOoMjn9Po425sAWe1ymtnp/6QPSe2ZQfM5VCRryy/q8K98BAaTzm3ZPixd Xg X-Google-Smtp-Source: APXvYqzhFuTcn68bpLFr102OKfA2MHagrEOorjVCWdbp3WClOxaHeQdgMN4jFR00oejNuKB4iEqNbqBK63BmJGVazMJG X-Received: by 2002:a65:44cb:: with SMTP id g11mr7224673pgs.145.1570664682535; Wed, 09 Oct 2019 16:44:42 -0700 (PDT) Date: Wed, 9 Oct 2019 16:44:22 -0700 In-Reply-To: Message-Id: <505d8e79cd983d5b3dfd56c4f0432ad647132957.1570663470.git.jonathantanmy@google.com> Mime-Version: 1.0 References: X-Mailer: git-send-email 2.23.0.581.g78d2f28ef7-goog Subject: [PATCH 6/6] index-pack: make quantum of work smaller From: Jonathan Tan To: git@vger.kernel.org Cc: Jonathan Tan , peff@peff.net, mh@glandium.org Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Signed-off-by: Jonathan Tan --- builtin/index-pack.c | 267 ++++++++++++++++++++----------------------- 1 file changed, 127 insertions(+), 140 deletions(-) diff --git a/builtin/index-pack.c b/builtin/index-pack.c index 3908cd3115..f6318037ca 100644 --- a/builtin/index-pack.c +++ b/builtin/index-pack.c @@ -38,15 +38,22 @@ struct base_data { struct object_entry *obj; int ref_first, ref_last; int ofs_first, ofs_last; + int retain_data; + int children_remaining; /* Not initialized by make_base(). */ + struct list_head list; void *data; unsigned long size; }; +LIST_HEAD(work_head); +LIST_HEAD(done_head); +size_t base_cache_used; +size_t base_cache_limit; + struct thread_local { pthread_t thread; - size_t base_cache_used; int pack_fd; }; @@ -369,36 +376,38 @@ static void free_base_data(struct base_data *c) { if (c->data) { FREE_AND_NULL(c->data); - get_thread_data()->base_cache_used -= c->size; + base_cache_used -= c->size; } } -static void prune_base_data(struct base_data *youngest_child) +static void prune_base_data(struct base_data *retain) { - struct base_data *b; - struct thread_local *data = get_thread_data(); - struct base_data **ancestry = NULL; - int nr = 0, alloc = 0; - int i; + struct list_head *pos; - if (data->base_cache_used <= delta_base_cache_limit) + if (base_cache_used <= 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; + list_for_each_prev(pos, &done_head) { + struct base_data *b = list_entry(pos, struct base_data, list); + if (b->retain_data || b == retain) + continue; + if (b->data) { + free_base_data(b); + if (base_cache_used <= base_cache_limit) + return; + } } - for (i = nr - 1; - i >= 0 && data->base_cache_used > delta_base_cache_limit; - i--) { - if (ancestry[i]->data) - free_base_data(ancestry[i]); + + list_for_each_prev(pos, &work_head) { + struct base_data *b = list_entry(pos, struct base_data, list); + if (b->retain_data || b == retain) + continue; + if (b->data) { + free_base_data(b); + if (base_cache_used <= base_cache_limit) + return; + } } - free(ancestry); } static int is_delta_type(enum object_type type) @@ -886,7 +895,7 @@ static void *get_base_data(struct base_data *c) if (!delta_nr) { c->data = get_data_from_pack(obj); c->size = obj->size; - get_thread_data()->base_cache_used += c->size; + base_cache_used += c->size; prune_base_data(c); } for (; delta_nr > 0; delta_nr--) { @@ -902,7 +911,7 @@ static void *get_base_data(struct base_data *c) free(raw); if (!c->data) bad_object(obj->idx.offset, _("failed to apply delta")); - get_thread_data()->base_cache_used += c->size; + base_cache_used += c->size; prune_base_data(c); } free(delta); @@ -920,6 +929,8 @@ static struct base_data *make_base(struct object_entry *obj, &base->ref_first, &base->ref_last); find_ofs_delta_children(obj->idx.offset, &base->ofs_first, &base->ofs_last); + base->children_remaining = base->ref_last - base->ref_first + + base->ofs_last - base->ofs_first + 2; return base; } @@ -953,14 +964,8 @@ static struct base_data *resolve_delta(struct object_entry *delta_obj, &delta_obj->idx.oid); result = make_base(delta_obj, base); - if (result->ref_last == -1 && result->ofs_last == -1) { - free(result_data); - } else { - result->data = result_data; - result->size = result_size; - get_thread_data()->base_cache_used += result->size; - prune_base_data(result); - } + result->data = result_data; + result->size = result_size; counter_lock(); nr_resolved_deltas++; @@ -969,84 +974,6 @@ static struct base_data *resolve_delta(struct object_entry *delta_obj, return result; } -/* - * Standard boolean compare-and-swap: atomically check whether "*type" is - * "want"; if so, swap in "set" and return true. Otherwise, leave it untouched - * and return false. - */ -static int compare_and_swap_type(signed char *type, - enum object_type want, - enum object_type set) -{ - enum object_type old; - - type_cas_lock(); - old = *type; - if (old == want) - *type = set; - type_cas_unlock(); - - return old == want; -} - -static struct base_data *find_unresolved_deltas_1(struct base_data *base, - struct base_data *prev_base) -{ - if (base->ref_first <= base->ref_last) { - struct object_entry *child = objects + ref_deltas[base->ref_first].obj_no; - struct base_data *result; - - if (!compare_and_swap_type(&child->real_type, OBJ_REF_DELTA, - base->obj->real_type)) - BUG("child->real_type != OBJ_REF_DELTA"); - - get_base_data(base); - result = resolve_delta(child, base); - if (base->ref_first == base->ref_last && base->ofs_last == -1) - free_base_data(base); - - base->ref_first++; - return result; - } - - if (base->ofs_first <= base->ofs_last) { - struct object_entry *child = objects + ofs_deltas[base->ofs_first].obj_no; - struct base_data *result; - - assert(child->real_type == OBJ_OFS_DELTA); - child->real_type = base->obj->real_type; - get_base_data(base); - result = resolve_delta(child, base); - if (base->ofs_first == base->ofs_last) - free_base_data(base); - - base->ofs_first++; - return result; - } - - free_base_data(base); - return NULL; -} - -static void find_unresolved_deltas(struct base_data *base) -{ - struct base_data *new_base, *prev_base = NULL; - for (;;) { - new_base = find_unresolved_deltas_1(base, prev_base); - - if (new_base) { - prev_base = base; - base = new_base; - } else { - free(base); - base = prev_base; - if (!base) - return; - prev_base = base->base; - } - } -} - static int compare_ofs_delta_entry(const void *a, const void *b) { const struct ofs_delta_entry *delta_a = a; @@ -1065,33 +992,97 @@ static int compare_ref_delta_entry(const void *a, const void *b) return oidcmp(&delta_a->oid, &delta_b->oid); } -static void resolve_base(struct object_entry *obj) +static void *do_work(void *data) { - struct base_data *base_obj = make_base(obj, NULL); - - find_unresolved_deltas(base_obj); -} - -static void *threaded_second_pass(void *data) -{ - set_thread_data(data); + if (data) + set_thread_data(data); for (;;) { - int i; - counter_lock(); - display_progress(progress, nr_resolved_deltas); - counter_unlock(); + struct base_data *parent = NULL; + struct object_entry *child_obj; + struct base_data *child; + work_lock(); - while (nr_dispatched < nr_objects && - is_delta_type(objects[nr_dispatched].type)) - nr_dispatched++; - if (nr_dispatched >= nr_objects) { - work_unlock(); - break; + if (list_empty(&work_head)) { + while (nr_dispatched < nr_objects && + is_delta_type(objects[nr_dispatched].type)) + nr_dispatched++; + if (nr_dispatched >= nr_objects) { + work_unlock(); + break; + } + child_obj = &objects[nr_dispatched++]; + } else { + parent = list_first_entry(&work_head, struct base_data, + list); + + if (parent->ref_first <= parent->ref_last) { + child_obj = objects + + ref_deltas[parent->ref_first++].obj_no; + assert(child_obj->real_type == OBJ_REF_DELTA); + child_obj->real_type = parent->obj->real_type; + } else { + child_obj = objects + + ofs_deltas[parent->ofs_first++].obj_no; + assert(child_obj->real_type == OBJ_OFS_DELTA); + child_obj->real_type = parent->obj->real_type; + } + + if (parent->ref_first > parent->ref_last && + parent->ofs_first > parent->ofs_last) { + list_del(&parent->list); + list_add(&parent->list, &done_head); + } + + get_base_data(parent); + parent->retain_data++; } - i = nr_dispatched++; work_unlock(); - resolve_base(&objects[i]); + if (parent) { + child = resolve_delta(child_obj, parent); + if (!child->children_remaining) + FREE_AND_NULL(child->data); + } else { + child = make_base(child_obj, NULL); + if (child->children_remaining) { + /* + * Since this child has its own delta children, + * we will need this data in the future. + * Inflate now so that future iterations will + * have access to this object's data while + * outside the work mutex. + */ + child->data = get_data_from_pack(child_obj); + child->size = child_obj->size; + } + } + + work_lock(); + if (parent) + parent->retain_data--; + if (child->data) { + list_add(&child->list, &work_head); + base_cache_used += child->size; + prune_base_data(NULL); + } else { + struct base_data *p = parent; + + while (p) { + struct base_data *next_p; + + p->children_remaining--; + if (p->children_remaining) + break; + + next_p = p->base; + free_base_data(p); + list_del(&p->list); + free(p); + + p = next_p; + } + } + work_unlock(); } return NULL; } @@ -1192,11 +1183,12 @@ static void resolve_deltas(void) nr_ref_deltas + nr_ofs_deltas); nr_dispatched = 0; + base_cache_limit = delta_base_cache_limit * nr_threads; if (nr_threads > 1 || getenv("GIT_FORCE_THREADS")) { init_thread(); for (i = 0; i < nr_threads; i++) { int ret = pthread_create(&thread_data[i].thread, NULL, - threaded_second_pass, thread_data + i); + do_work, thread_data + i); if (ret) die(_("unable to create thread: %s"), strerror(ret)); @@ -1206,7 +1198,7 @@ static void resolve_deltas(void) cleanup_thread(); return; } - threaded_second_pass(¬hread_data); + do_work(¬hread_data); } /* @@ -1362,10 +1354,8 @@ static void fix_unresolved_deltas(struct hashfile *f) for (i = 0; i < nr_ref_deltas; i++) { struct ref_delta_entry *d = sorted_by_pos[i]; enum object_type type; - struct base_data *base; void *data; unsigned long size; - struct object_entry *obj; if (objects[d->obj_no].real_type != OBJ_REF_DELTA) continue; @@ -1376,11 +1366,8 @@ static void fix_unresolved_deltas(struct hashfile *f) if (check_object_signature(&d->oid, data, size, type_name(type))) die(_("local object %s is corrupt"), oid_to_hex(&d->oid)); - obj = append_obj_to_pack(f, d->oid.hash, data, size, type); - base = make_base(obj, NULL); - base->data = data; - base->size = size; - find_unresolved_deltas(base); + append_obj_to_pack(f, d->oid.hash, data, size, type); + do_work(NULL); /* will pick up new object in objects array (added by append_obj_to_pack) */ display_progress(progress, nr_resolved_deltas); } free(sorted_by_pos);