From patchwork Fri Mar 14 20:18:20 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14017389 Received: from mail-qt1-f179.google.com (mail-qt1-f179.google.com [209.85.160.179]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id E31D92046BE for ; Fri, 14 Mar 2025 20:18:23 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.160.179 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983505; cv=none; b=DoA4QbXK2jZ5JmYg34ZsXvr3iyiM7e4CEX6b+KZojcBwUJMAsy5AeVYjxDW+yubd/26svX+YfGKickcd964ROLBXrhwDzEKoWp4icW3ON1sP7xjJWKttCndEfdD276Na8H3k6H9twx5mUnFo2DtI0MXiWP3WlFmPTognbOGL24U= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983505; c=relaxed/simple; bh=ccGhW+7vzD/TmdLOHMpdGUnkrtzVYOWB7wnQ3KraAIA=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=Yh7OazhGxfithScNRjKYlOpIpU4UIJleUuZDxhRmcEez0gm07l6MdNC1whXYEWsVU44GXI2+8yk7Tfx6LWQbameyIcZqaVTR4rkxoG7f0Ss3JBRFqSUSIt2XZUZ3SAF315RcX+g3qtxaR+RSKYPwBWhwK3JlssBYxaM8OoDlA+o= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=pass smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=XbrAGuPV; arc=none smtp.client-ip=209.85.160.179 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="XbrAGuPV" Received: by mail-qt1-f179.google.com with SMTP id d75a77b69052e-476af5479feso25183021cf.2 for ; Fri, 14 Mar 2025 13:18:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1741983502; x=1742588302; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=hn0FV7RzxfiyXbO1m3w7A6qXi6kVkTwOVXrDzIJAeX8=; b=XbrAGuPVEpuZKWSEuHlNThIukEbugj+xhPwFsqBpFGtK8iauUVRWCLkrslt7JgbsK8 2QACKrLSfrMtN0U+kFHuSKlhfpNmgKRzG1qJTAbkttgdzohzY0NDoKx8ociGcLxyuGhN PyDm/EFngEV8g7xy+CxtcePduEOAt903aDn2CtcNzR2LkasIb43ylJ9BIJ7HoBIRdsPl nB71/fyY+mWChXEanii6Mee9hz+JXHUllP9LSFBl0plKwKMZ4yEM7CyiO8rTPHq/p2hn WDDVaYtQaz1+z/7+9me+23PyFOY6gUEQ6LxrdjnjpgM/WX5O06KqaZpryNiPzd95W5v2 0/Fw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741983502; x=1742588302; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=hn0FV7RzxfiyXbO1m3w7A6qXi6kVkTwOVXrDzIJAeX8=; b=kBBkineSrGsZMNYfb3KswJkK1XTIf36smjz9aUkvHKsdJ61xMCG8YuoPVuc11B3o19 Q9HzoYXlqWmm8XfsyfgmwYEDT727utMoFt46QwomhTrgXj7UvZXsfYUt085dNb3cS90t b3jFV8XpBF4u80oc7GFvSlUxNH1z+lSiqmgeHuuXZncv+qK0E8PJj02VxmScHZgPrWcY oOROAwl6oleAhhekUZ0b16IpubFCbBwozizB1S3VYCY4SDlGic1s5GGzecMcg6vIou5B WTUxRnbspbGKttwQpY1hMYUqZkTC1t2PyGm3lqZrTYSg/x27apuRVtm17zpCtnja7N5U xPtQ== X-Gm-Message-State: AOJu0YwDGJRXNkJTllcXvKr0dhLZ5wrdVVC5LfO1DHTPs4Bb2SfZGzMr QiMNgxG0C1RbXJBlLiY2VyONkxQ1B/PQp9a95NQmgMVug77v/oo+hktm2OxMsHzy5RFZYObYSRY VL8A= X-Gm-Gg: ASbGncv7NEOuxxDLvLLN/uh8NdP0fspEg5rS8LrYkfQ4U51u5w3LkFeB2e9cBMxhzHH CXQjEuPUPP67ZTm1oDVWOk0e7a9ZONUVYhcXbPgaLcb398zGgUqCdvmeecOt18S5H1lpZwbvi6f aJnQVXviSBmeJBa3JUK1GGeqQqQQOMy7/0o/LZoOlQgfpPWJ1h4f4aziNK9Q33jrrUhXl9ceh8C SkAkSTZQQmJR8yV/dVYIyHpo0IvZBhkL27ZbYNzpA+l0UDSHga0C5/rTbbnOHcFRliu6vON2M3E DFrbgxxeek+n4oKHn0DC19WJ+O/fyngPmcx7gNnDgR0HGXXllDpGPnQTKqg7wAIruYPqulUlry3 JDNF1F1g8DKgwUAcr X-Google-Smtp-Source: AGHT+IHL6ZcrrJf75hCK5S+AUN1tw3rLGaXuTK4yUIoi6o7M1nYE5a6FlgGAeFlS8MfTem3fwDaW5Q== X-Received: by 2002:a05:622a:438a:b0:476:8c58:4f69 with SMTP id d75a77b69052e-476c81330e9mr53114281cf.1.1741983502375; Fri, 14 Mar 2025 13:18:22 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with UTF8SMTPSA id d75a77b69052e-476bb82c170sm26627901cf.77.2025.03.14.13.18.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 14 Mar 2025 13:18:21 -0700 (PDT) Date: Fri, 14 Mar 2025 16:18:20 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v4 01/13] Documentation: describe incremental MIDX bitmaps Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Prepare to implement support for reachability bitmaps for the new incremental multi-pack index (MIDX) feature over the following commits. This commit begins by first describing the relevant format and usage details for incremental MIDX bitmaps. Signed-off-by: Taylor Blau --- Documentation/technical/multi-pack-index.adoc | 71 +++++++++++++++++++ 1 file changed, 71 insertions(+) diff --git a/Documentation/technical/multi-pack-index.adoc b/Documentation/technical/multi-pack-index.adoc index cc063b30be..ab98ecfeb9 100644 --- a/Documentation/technical/multi-pack-index.adoc +++ b/Documentation/technical/multi-pack-index.adoc @@ -164,6 +164,77 @@ objects_nr($H2) + objects_nr($H1) + i (in the C implementation, this is often computed as `i + m->num_objects_in_base`). +=== Pseudo-pack order for incremental MIDXs + +The original implementation of multi-pack reachability bitmaps defined +the pseudo-pack order in linkgit:gitformat-pack[5] (see the section +titled "multi-pack-index reverse indexes") roughly as follows: + +____ +In short, a MIDX's pseudo-pack is the de-duplicated concatenation of +objects in packs stored by the MIDX, laid out in pack order, and the +packs arranged in MIDX order (with the preferred pack coming first). +____ + +In the incremental MIDX design, we extend this definition to include +objects from multiple layers of the MIDX chain. The pseudo-pack order +for incremental MIDXs is determined by concatenating the pseudo-pack +ordering for each layer of the MIDX chain in order. Formally two objects +`o1` and `o2` are compared as follows: + +1. If `o1` appears in an earlier layer of the MIDX chain than `o2`, then + `o1` is considered less than `o2`. + +2. Otherwise, if `o1` and `o2` appear in the same MIDX layer, and that + MIDX layer has no base, then if one of `pack(o1)` and `pack(o2)` is + preferred and the other is not, then the preferred one sorts first. If + there is a base layer (i.e. the MIDX layer is not the first layer in + the chain), then if `pack(o1)` appears earlier in that MIDX layer's + pack order, than `o1` is less than `o2`. Likewise if `pack(o2)` + appears earlier, than the opposite is true. + +3. Otherwise, `o1` and `o2` appear in the same pack, and thus in the + same MIDX layer. Sort `o1` and `o2` by their offset within their + containing packfile. + +Note that the preferred pack is a property of the MIDX chain, not the +individual layers themselves. Fundamentally we could introduce a +per-layer preferred pack, but this is less relevant now that we can +perform multi-pack reuse across the set of packs in a MIDX. + +=== Reachability bitmaps and incremental MIDXs + +Each layer of an incremental MIDX chain may have its objects (and the +objects from any previous layer in the same MIDX chain) represented in +its own `*.bitmap` file. + +The structure of a `*.bitmap` file belonging to an incremental MIDX +chain is identical to that of a non-incremental MIDX bitmap, or a +classic single-pack bitmap. Since objects are added to the end of the +incremental MIDX's pseudo-pack order (see: above), it is possible to +extend a bitmap when appending to the end of a MIDX chain. + +(Note: it is possible likewise to compress a contiguous sequence of MIDX +incremental layers, and their `*.bitmap`(s) into a single layer and +`*.bitmap`, but this is not yet implemented.) + +The object positions used are global within the pseudo-pack order, so +subsequent layers will have, for example, `m->num_objects_in_base` +number of `0` bits in each of their four type bitmaps. This follows from +the fact that we only write type bitmap entries for objects present in +the layer immediately corresponding to the bitmap). + +Note also that only the bitmap pertaining to the most recent layer in an +incremental MIDX chain is used to store reachability information about +the interesting and uninteresting objects in a reachability query. +Earlier bitmap layers are only used to look up commit and pseudo-merge +bitmaps from that layer, as well as the type-level bitmaps for objects +in that layer. + +To simplify the implementation, type-level bitmaps are iterated +simultaneously, and their results are OR'd together to avoid recursively +calling internal bitmap functions. + Future Work ----------- From patchwork Fri Mar 14 20:18:24 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14017390 Received: from mail-qt1-f182.google.com (mail-qt1-f182.google.com [209.85.160.182]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 18A5E205E17 for ; Fri, 14 Mar 2025 20:18:26 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.160.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983509; cv=none; b=EgwpFyycc9NH6XuHgsezyRGrFcDjdoSXlPIevrEOxp2C9ub3Z0bVmw7b/V5jnxVVwghV3tT8+K/tBXzVluaAUevBa4Lyo/qMoEFld0iOyNnFNql8Cz7TOkXJApgQIeJUxEZ2M9xIq3x9aGgaArsVdPfmIbDE0tuNRCG+axcr1Zk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983509; c=relaxed/simple; bh=6N1CTIKrsKC5cvhYIaqm4sSYdzqklDeMxdf3KW46VIY=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=JCqsQYAQ7x8HC9Rjpg+BBgyEX7sc6p53eXNyyCO5VdXLt5/dGkdZjDk+2T4m0KkmSUhhWqVycNYGTVu+g3zWuBetbSaUNiaIpu5rV3v1gDX/2qRDMTTpruFcO/p7Q+46kBLKSP3Mdgg1ExNHwisoGTP2tHdnzrSz868kQML1knk= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=pass smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=tvDZnZbT; arc=none smtp.client-ip=209.85.160.182 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="tvDZnZbT" Received: by mail-qt1-f182.google.com with SMTP id d75a77b69052e-46fcbb96ba9so34271711cf.0 for ; Fri, 14 Mar 2025 13:18:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1741983506; x=1742588306; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=8nsJ9+y6/1BFnZefRuXSAAvlsgqb00kumJyoESlQw1s=; b=tvDZnZbTER6fqmugabXHGMAwh3453rTyWTdZ8HCKFstP1szxrJV5e8YiCYB25g36LW VADtgh4xqkI3QW2zx9l2Hj//XGqIW7xGlaKRY2aZK4EYqRnj02l/Ve25R3PwtAB8ATkW Da4av4FQPGaRovqvG2eMEDsfzQ7vQADAmUIVBhpAVMcXQkXOhe3RduvRx1ktaXdtXOUm /KjoQt/eDsafBwSQTySmjOLMZB6Y0dbgObgoxZ2WcrMp1u3uAb35DKKvE4gGl4aIFZfX sB3jd8x7FSnymR1z1F92+UP2ruBBZbeoGt3XnD8yz99DFoIQx4v5PfpFzmo0NLN/wdpp GcdQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741983506; x=1742588306; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=8nsJ9+y6/1BFnZefRuXSAAvlsgqb00kumJyoESlQw1s=; b=ixFMF2A6j76OnTWAAYZMQsjZyvJhIT0lAPQhm/fhT+qA7e7dGOj5uCLNICbNWoDjfP 6+ifCXAr5Q3mKImV+e9YqaGM3QTVlePFT6er0rxlclND0SGs+nqhLdRsLpkj4iBWnofI opIFCMmiGWL0bwv4YvmUHesQpgchRTRVesZDf2BI8RAVJ9hQbCWQpZLhckZ9FznqCNc4 i9mork7G6QhBNPUCCFG5o7MDlLfEn5XV2tIzD1HvG2HCbXjUWdjWkEWZoSDNQ6x3NDFN vaO5FnD4/OJPjME+8X4GMHJ+sQQtY6XIVtBlcLQM9thpKfv1bqh1U8jqYEwNWSGHU/8n 2Nng== X-Gm-Message-State: AOJu0YxsN6dVY6Rkr6e7gUyaPF3icV0KG8UA5EX0xZHRBknVUWLNAjrw UzPmDexBzNZnd/OOi4uxcV7RbRFpua8YRlhuAxps5hRDYoEv4AXzPk/5YmLCePsAz4xXwu3R1se hi+k= X-Gm-Gg: ASbGncvXPSNeGinXASQIg2MEKzp3GjpA/Ei+duEUaN4u4oXv37dWabUW4GabDxJZ5WJ aSAoT+89X8r3YV2XF6GnXBIRfD7yFAtp7lnkduOtwEEntWr/cjZqgWaVFF/0rDnNB6NOOoJgI+v oMqp5xgU1ypXzvo4vYGboYqDYEDX1igIeMMy944RTehcSG+DpLiOplXh+bwQl/9ZRp/kzK0crM0 uJxQP6TLSnV1KW4Zkx34AdfhKuMoiB3vuv/ox1Ecp9NyeGoZKSnU7lOuMWZp5LSFcX6MGgeb83A 1eYemXg4kGhCnPVAwXnhV38XAAN1RSS/2iDfrIW+ef7MyvKmKm/7G4QvWQP21DS7DnB8LRYCsz5 BSd7h+mmTCeOlQpI2 X-Google-Smtp-Source: AGHT+IGLMNsDlFRQpB/UIX4ZWEL90qRvJicTSza/iV6GP8i2BAYPpETqA2FVVKnwqNJ/XPI/mY9DvA== X-Received: by 2002:a05:6214:dab:b0:6e2:4859:f062 with SMTP id 6a1803df08f44-6eaeaa4cf43mr61112086d6.21.1741983505658; Fri, 14 Mar 2025 13:18:25 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with UTF8SMTPSA id 6a1803df08f44-6eade34c5d6sm27683056d6.111.2025.03.14.13.18.25 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 14 Mar 2025 13:18:25 -0700 (PDT) Date: Fri, 14 Mar 2025 16:18:24 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v4 02/13] pack-revindex: prepare for incremental MIDX bitmaps Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Prepare the reverse index machinery to handle object lookups in an incremental MIDX bitmap. These changes are broken out across a few functions: - load_midx_revindex() learns to use the appropriate MIDX filename depending on whether the given 'struct multi_pack_index *' is incremental or not. - pack_pos_to_midx() and midx_to_pack_pos() now both take in a global object position in the MIDX pseudo-pack order, and finds the earliest containing MIDX (similar to midx.c::midx_for_object(). - midx_pack_order_cmp() adjusts its call to pack_pos_to_midx() by the number of objects in the base (since 'vb - midx->revindx_data' is relative to the containing MIDX, and pack_pos_to_midx() expects a global position). Likewise, this function adjusts its output by adding m->num_objects_in_base to return a global position out through the `*pos` pointer. Together, these changes are sufficient to use the multi-pack index's reverse index format for incremental multi-pack reachability bitmaps. Signed-off-by: Taylor Blau --- pack-bitmap.c | 40 ++++++++++++++++++++++++++++------------ pack-revindex.c | 34 +++++++++++++++++++++++++--------- 2 files changed, 53 insertions(+), 21 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 6406953d32..c26d85b5db 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -170,6 +170,15 @@ static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *index) return read_bitmap(index->map, index->map_size, &index->map_pos); } +static uint32_t bitmap_non_extended_bits(struct bitmap_index *index) +{ + if (index->midx) { + struct multi_pack_index *m = index->midx; + return m->num_objects + m->num_objects_in_base; + } + return index->pack->num_objects; +} + static uint32_t bitmap_num_objects(struct bitmap_index *index) { if (index->midx) @@ -924,7 +933,7 @@ static inline int bitmap_position_extended(struct bitmap_index *bitmap_git, if (pos < kh_end(positions)) { int bitmap_pos = kh_value(positions, pos); - return bitmap_pos + bitmap_num_objects(bitmap_git); + return bitmap_pos + bitmap_non_extended_bits(bitmap_git); } return -1; @@ -992,7 +1001,7 @@ static int ext_index_add_object(struct bitmap_index *bitmap_git, bitmap_pos = kh_value(eindex->positions, hash_pos); } - return bitmap_pos + bitmap_num_objects(bitmap_git); + return bitmap_pos + bitmap_non_extended_bits(bitmap_git); } struct bitmap_show_data { @@ -1342,11 +1351,17 @@ struct ewah_bitmap *pseudo_merge_bitmap_for_commit(struct bitmap_index *bitmap_g if (pos < 0 || pos >= bitmap_num_objects(bitmap_git)) goto done; + /* + * Use bitmap-relative positions instead of offsetting + * by bitmap_git->num_objects_in_base because we use + * this to find a match in pseudo_merge_for_parents(), + * and pseudo-merge groups cannot span multiple bitmap + * layers. + */ bitmap_set(parents, pos); } - match = pseudo_merge_for_parents(&bitmap_git->pseudo_merges, - parents); + match = pseudo_merge_for_parents(&bitmap_git->pseudo_merges, parents); done: bitmap_free(parents); @@ -1500,7 +1515,8 @@ static void show_extended_objects(struct bitmap_index *bitmap_git, for (i = 0; i < eindex->count; ++i) { struct object *obj; - if (!bitmap_get(objects, st_add(bitmap_num_objects(bitmap_git), i))) + if (!bitmap_get(objects, + st_add(bitmap_non_extended_bits(bitmap_git), i))) continue; obj = eindex->objects[i]; @@ -1679,7 +1695,7 @@ static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git, * them individually. */ for (i = 0; i < eindex->count; i++) { - size_t pos = st_add(i, bitmap_num_objects(bitmap_git)); + size_t pos = st_add(i, bitmap_non_extended_bits(bitmap_git)); if (eindex->objects[i]->type == type && bitmap_get(to_filter, pos) && !bitmap_get(tips, pos)) @@ -1705,7 +1721,7 @@ static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git, oi.sizep = &size; - if (pos < bitmap_num_objects(bitmap_git)) { + if (pos < bitmap_non_extended_bits(bitmap_git)) { struct packed_git *pack; off_t ofs; @@ -1729,7 +1745,7 @@ static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git, } } else { struct eindex *eindex = &bitmap_git->ext_index; - struct object *obj = eindex->objects[pos - bitmap_num_objects(bitmap_git)]; + struct object *obj = eindex->objects[pos - bitmap_non_extended_bits(bitmap_git)]; if (oid_object_info_extended(bitmap_repo(bitmap_git), &obj->oid, &oi, 0) < 0) die(_("unable to get size of %s"), oid_to_hex(&obj->oid)); @@ -1882,7 +1898,7 @@ static void filter_packed_objects_from_bitmap(struct bitmap_index *bitmap_git, uint32_t objects_nr; size_t i, pos; - objects_nr = bitmap_num_objects(bitmap_git); + objects_nr = bitmap_non_extended_bits(bitmap_git); pos = objects_nr / BITS_IN_EWORD; if (pos > result->word_alloc) @@ -2419,7 +2435,7 @@ static uint32_t count_object_type(struct bitmap_index *bitmap_git, for (i = 0; i < eindex->count; ++i) { if (eindex->objects[i]->type == type && bitmap_get(objects, - st_add(bitmap_num_objects(bitmap_git), i))) + st_add(bitmap_non_extended_bits(bitmap_git), i))) count++; } @@ -2820,7 +2836,7 @@ uint32_t *create_bitmap_mapping(struct bitmap_index *bitmap_git, BUG("rebuild_existing_bitmaps: missing required rev-cache " "extension"); - num_objects = bitmap_num_objects(bitmap_git); + num_objects = bitmap_non_extended_bits(bitmap_git); CALLOC_ARRAY(reposition, num_objects); for (i = 0; i < num_objects; ++i) { @@ -2963,7 +2979,7 @@ static off_t get_disk_usage_for_extended(struct bitmap_index *bitmap_git) struct object *obj = eindex->objects[i]; if (!bitmap_get(result, - st_add(bitmap_num_objects(bitmap_git), i))) + st_add(bitmap_non_extended_bits(bitmap_git), i))) continue; if (oid_object_info_extended(bitmap_repo(bitmap_git), &obj->oid, diff --git a/pack-revindex.c b/pack-revindex.c index d3832478d9..d3faab6a37 100644 --- a/pack-revindex.c +++ b/pack-revindex.c @@ -383,8 +383,14 @@ int load_midx_revindex(struct multi_pack_index *m) trace2_data_string("load_midx_revindex", the_repository, "source", "rev"); - get_midx_filename_ext(m->repo->hash_algo, &revindex_name, m->object_dir, - get_midx_checksum(m), MIDX_EXT_REV); + if (m->has_chain) + get_split_midx_filename_ext(m->repo->hash_algo, &revindex_name, + m->object_dir, get_midx_checksum(m), + MIDX_EXT_REV); + else + get_midx_filename_ext(m->repo->hash_algo, &revindex_name, + m->object_dir, get_midx_checksum(m), + MIDX_EXT_REV); ret = load_revindex_from_disk(revindex_name.buf, m->num_objects, @@ -471,11 +477,15 @@ off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos) uint32_t pack_pos_to_midx(struct multi_pack_index *m, uint32_t pos) { + while (m && pos < m->num_objects_in_base) + m = m->base_midx; + if (!m) + BUG("NULL multi-pack-index for object position: %"PRIu32, pos); if (!m->revindex_data) BUG("pack_pos_to_midx: reverse index not yet loaded"); - if (m->num_objects <= pos) + if (m->num_objects + m->num_objects_in_base <= pos) BUG("pack_pos_to_midx: out-of-bounds object at %"PRIu32, pos); - return get_be32(m->revindex_data + pos); + return get_be32(m->revindex_data + pos - m->num_objects_in_base); } struct midx_pack_key { @@ -491,7 +501,8 @@ static int midx_pack_order_cmp(const void *va, const void *vb) const struct midx_pack_key *key = va; struct multi_pack_index *midx = key->midx; - uint32_t versus = pack_pos_to_midx(midx, (uint32_t*)vb - (const uint32_t *)midx->revindex_data); + size_t pos = (uint32_t *)vb - (const uint32_t *)midx->revindex_data; + uint32_t versus = pack_pos_to_midx(midx, pos + midx->num_objects_in_base); uint32_t versus_pack = nth_midxed_pack_int_id(midx, versus); off_t versus_offset; @@ -529,9 +540,9 @@ static int midx_key_to_pack_pos(struct multi_pack_index *m, { uint32_t *found; - if (key->pack >= m->num_packs) + if (key->pack >= m->num_packs + m->num_packs_in_base) BUG("MIDX pack lookup out of bounds (%"PRIu32" >= %"PRIu32")", - key->pack, m->num_packs); + key->pack, m->num_packs + m->num_packs_in_base); /* * The preferred pack sorts first, so determine its identifier by * looking at the first object in pseudo-pack order. @@ -551,7 +562,8 @@ static int midx_key_to_pack_pos(struct multi_pack_index *m, if (!found) return -1; - *pos = found - m->revindex_data; + *pos = (found - m->revindex_data) + m->num_objects_in_base; + return 0; } @@ -559,9 +571,13 @@ int midx_to_pack_pos(struct multi_pack_index *m, uint32_t at, uint32_t *pos) { struct midx_pack_key key; + while (m && at < m->num_objects_in_base) + m = m->base_midx; + if (!m) + BUG("NULL multi-pack-index for object position: %"PRIu32, at); if (!m->revindex_data) BUG("midx_to_pack_pos: reverse index not yet loaded"); - if (m->num_objects <= at) + if (m->num_objects + m->num_objects_in_base <= at) BUG("midx_to_pack_pos: out-of-bounds object at %"PRIu32, at); key.pack = nth_midxed_pack_int_id(m, at); From patchwork Fri Mar 14 20:18:27 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14017391 Received: from mail-qv1-f53.google.com (mail-qv1-f53.google.com [209.85.219.53]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 02D26204C3F for ; Fri, 14 Mar 2025 20:18:30 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.53 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983512; cv=none; b=TRFXrXGgDmrnfsbVMMBWPjxULX0FilI3iTV79S5HZFs2K8De1d+S9hE9zJGrRWk5MMRuw1Np2csvGqbbGoNeUzHhmK7Qmh5MGIe9r6b0NfUUMcXs0fvlKhdoUWunNrpEqyNV6+xbCQB4m8R+cmR2BhCugeYiDidkGR0kltdD89w= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983512; c=relaxed/simple; bh=WcvUsjHqHLWDYm52ixOxJNFAPhG570Fyc1VHoyxp97o=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=LlLG6cxsaN3KBkyF4dYvq7v4VmXE37A5pkvN5xKKylqr6JkzNWXyzgfO+Gfn7S8S2Hw8gQ7J3vGuJbirFSL0Bv+jeVFBxS8u79SGEJrCoQN4puECRTdSDg5ClofVyUxyjDtmc1vY60iu+vaJDehigCqtAXtbpuceWZhfQzXYV6U= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=pass smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=s2AnIWCb; arc=none smtp.client-ip=209.85.219.53 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="s2AnIWCb" Received: by mail-qv1-f53.google.com with SMTP id 6a1803df08f44-6e8fd49b85eso36628576d6.0 for ; Fri, 14 Mar 2025 13:18:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1741983509; x=1742588309; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=U5aN3ETzCXA6ruGv8x4ecQltwFZc7pmljK7qcMx67U8=; b=s2AnIWCbXHhmqCkHQXve8o2jbzeVGwZiJ6+Pj9hsX4mM343RRiKsezJ7l3VdEm4Cgq K9pU6IG/Scaiho0dc4SIlAKnWW7YrAKLs7tUXKHni8bygiWLuh82R3xf3LvXMhpkFcjf 6Y+imAQaPtAT+VkQq195RQ7MxHKxk7uO0KzhWiVuHCVGDqcFAavctz1aXdFc8N1JJXtP hmHje/XPGxuyM2ykrwq8K7CLHj0t/eSN8681KRyPfhQCkjshLw0aS626U4vew6mlGlDY G438EmvCvXrchU3hZQbGoVSXJXEoVdpm7M/I+n1Mt16PqMxqVjlz+5ntD0DeM6uzSy9V GeSA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741983509; x=1742588309; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=U5aN3ETzCXA6ruGv8x4ecQltwFZc7pmljK7qcMx67U8=; b=SF2iOWJNN8gXqFSkGgf7rnel3tHGa1XnSCSknHpcyHs5u0Rf6+Z10sZ8QTwmjatBnZ SIl6qMOi+JDNGLSoPOX/PQIsmIPP9kDk/e5dDJFg4Lhs3a/FzYNIMKt5IgL0eGcTlT1K vORBCJt9kenryJZvr1+LjmORTQBvjrem778KB4A4SfZ2xFTy6w7YFx83PTjvs9Ip8LVO CD56dtXI1wrdSUJezITKbKLXdKvcnqeUpQDJYL8LxC3loOFHHMUbPf7vfZtwKW5V+cY8 ZVSrtgbd0+vzRNluOMjscSVmM0qkTQlQ2xCS+yzfeiejqSWJrKuBJI2ZurO2zCEhMHqs +tRQ== X-Gm-Message-State: AOJu0YyYYD0L3bkwdwNN/P26VPZYae/FYc1mU3zdbQYFy3a39Zq2ifN8 ajpuUrM5wM6Wc9qcxJv4hk8Kh/TNymzLjUE+/7Fo2agNWHBi+NWil/KiW8QkGH21IJF+qU00liu 7GlQ= X-Gm-Gg: ASbGnculeNK8/JSn3y/NWSFlF9fK4ckvg0eqsu4A372RSSyN/1pAUfgVXvkLS1Tg8cJ 6MkWPSamOJZzhwKmbpRF1wpUjfTYsCxiiUPcfB5htO/jzqdp0l2TkYb2hnfulLYU1g6Lw37iU1F bTxoG5QljnxRstZwW4/ol7CeXPH4bOpccuqhG4kQtQjJhHSc0u9DOmBcpjlbHFPkb1eKb8Puhcg aLqqvUm1/b1a7ZjyLQhxJmW+QbevpdEA+sqq/nc1npfyWotFrHM8ATMiDpJaJO5V857sLVtjTfU Q/xNBkYzBGlfjgUfJ6cn2+tBAin+jQx1IwcvkQWucqUyogUIZ/Gemb7Sb6i9RPT8gccMwx3k9+J SXk/kH+PsI0W7N8B4 X-Google-Smtp-Source: AGHT+IEudqxgrL65+LT2yPoO360wE+49452o4KnApGRSpJ/lt+Y+s1mocOBTAlBF1iBoQ6kJf42ueg== X-Received: by 2002:a05:6214:19c5:b0:6e8:9b26:8c5 with SMTP id 6a1803df08f44-6eaeaa047c7mr46221496d6.10.1741983509670; Fri, 14 Mar 2025 13:18:29 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with UTF8SMTPSA id 6a1803df08f44-6eade35c90fsm27634736d6.120.2025.03.14.13.18.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 14 Mar 2025 13:18:29 -0700 (PDT) Date: Fri, 14 Mar 2025 16:18:27 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v4 03/13] pack-bitmap.c: open and store incremental bitmap layers Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Prepare the pack-bitmap machinery to work with incremental MIDXs by adding a new "base" field to keep track of the bitmap index associated with the previous MIDX layer. The changes in this commit are mostly boilerplate to open the correct bitmap(s), add them to the chain bitmap layers along the "base" pointer, ensures that the correct packs and their reverse indexes are loaded across MIDX layers, etc. While we're at it, keep track of a base_nr field to indicate how many bitmap layers (including the current bitmap) exist. This will be used in a future commit to allocate an array of 'struct ewah_bitmap' pointers to collect all of the respective type bitmaps among all layers to initialize a multi-EWAH iterator. Subsequent commits will teach the functions within the pack-bitmap machinery how to interact with these new fields. Signed-off-by: Taylor Blau --- pack-bitmap.c | 62 +++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 48 insertions(+), 14 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index c26d85b5db..72fb11d014 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -54,6 +54,16 @@ struct bitmap_index { struct packed_git *pack; struct multi_pack_index *midx; + /* + * If using a multi-pack index chain, 'base' points to the + * bitmap index corresponding to this bitmap's midx->base_midx. + * + * base_nr indicates how many layers precede this one, and is + * zero when base is NULL. + */ + struct bitmap_index *base; + uint32_t base_nr; + /* mmapped buffer of the whole bitmap index */ unsigned char *map; size_t map_size; /* size of the mmaped buffer */ @@ -386,8 +396,15 @@ static int load_bitmap_entries_v1(struct bitmap_index *index) char *midx_bitmap_filename(struct multi_pack_index *midx) { struct strbuf buf = STRBUF_INIT; - get_midx_filename_ext(midx->repo->hash_algo, &buf, midx->object_dir, - get_midx_checksum(midx), MIDX_EXT_BITMAP); + if (midx->has_chain) + get_split_midx_filename_ext(midx->repo->hash_algo, &buf, + midx->object_dir, + get_midx_checksum(midx), + MIDX_EXT_BITMAP); + else + get_midx_filename_ext(midx->repo->hash_algo, &buf, + midx->object_dir, get_midx_checksum(midx), + MIDX_EXT_BITMAP); return strbuf_detach(&buf, NULL); } @@ -454,16 +471,21 @@ static int open_midx_bitmap_1(struct bitmap_index *bitmap_git, goto cleanup; } - for (i = 0; i < bitmap_git->midx->num_packs; i++) { - if (prepare_midx_pack(bitmap_repo(bitmap_git), - bitmap_git->midx, - i)) { + for (i = 0; i < bitmap_git->midx->num_packs + bitmap_git->midx->num_packs_in_base; i++) { + if (prepare_midx_pack(bitmap_repo(bitmap_git), bitmap_git->midx, i)) { warning(_("could not open pack %s"), bitmap_git->midx->pack_names[i]); goto cleanup; } } + if (midx->base_midx) { + bitmap_git->base = prepare_midx_bitmap_git(midx->base_midx); + bitmap_git->base_nr = bitmap_git->base->base_nr + 1; + } else { + bitmap_git->base_nr = 0; + } + return 0; cleanup: @@ -515,6 +537,7 @@ static int open_pack_bitmap_1(struct bitmap_index *bitmap_git, struct packed_git bitmap_git->map_size = xsize_t(st.st_size); bitmap_git->map = xmmap(NULL, bitmap_git->map_size, PROT_READ, MAP_PRIVATE, fd, 0); bitmap_git->map_pos = 0; + bitmap_git->base_nr = 0; close(fd); if (load_bitmap_header(bitmap_git) < 0) { @@ -534,8 +557,7 @@ static int open_pack_bitmap_1(struct bitmap_index *bitmap_git, struct packed_git static int load_reverse_index(struct repository *r, struct bitmap_index *bitmap_git) { if (bitmap_is_midx(bitmap_git)) { - uint32_t i; - int ret; + struct multi_pack_index *m; /* * The multi-pack-index's .rev file is already loaded via @@ -544,10 +566,15 @@ static int load_reverse_index(struct repository *r, struct bitmap_index *bitmap_ * But we still need to open the individual pack .rev files, * since we will need to make use of them in pack-objects. */ - for (i = 0; i < bitmap_git->midx->num_packs; i++) { - ret = load_pack_revindex(r, bitmap_git->midx->packs[i]); - if (ret) - return ret; + for (m = bitmap_git->midx; m; m = m->base_midx) { + uint32_t i; + int ret; + + for (i = 0; i < m->num_packs; i++) { + ret = load_pack_revindex(r, m->packs[i]); + if (ret) + return ret; + } } return 0; } @@ -573,6 +600,13 @@ static int load_bitmap(struct repository *r, struct bitmap_index *bitmap_git) if (!bitmap_git->table_lookup && load_bitmap_entries_v1(bitmap_git) < 0) goto failed; + if (bitmap_git->base) { + if (!bitmap_is_midx(bitmap_git)) + BUG("non-MIDX bitmap has non-NULL base bitmap index"); + if (load_bitmap(r, bitmap_git->base) < 0) + goto failed; + } + return 0; failed: @@ -657,10 +691,9 @@ struct bitmap_index *prepare_bitmap_git(struct repository *r) struct bitmap_index *prepare_midx_bitmap_git(struct multi_pack_index *midx) { - struct repository *r = midx->repo; struct bitmap_index *bitmap_git = xcalloc(1, sizeof(*bitmap_git)); - if (!open_midx_bitmap_1(bitmap_git, midx) && !load_bitmap(r, bitmap_git)) + if (!open_midx_bitmap_1(bitmap_git, midx)) return bitmap_git; free_bitmap_index(bitmap_git); @@ -2899,6 +2932,7 @@ void free_bitmap_index(struct bitmap_index *b) close_midx_revindex(b->midx); } free_pseudo_merge_map(&b->pseudo_merges); + free_bitmap_index(b->base); free(b); } From patchwork Fri Mar 14 20:18:31 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14017392 Received: from mail-qv1-f41.google.com (mail-qv1-f41.google.com [209.85.219.41]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 0D2912063DF for ; Fri, 14 Mar 2025 20:18:33 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.41 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983515; cv=none; b=LavtWZqXmLCGEuh/jCst/zzchMnqH99aD+ZZrnPqe0M6exohLyE+AW2AOUvUjtkqBGCxTcGlnFmrxQ4M+29znwSU7vwID4uKUpkiZFfSON1/UsXrwggfFrrrTnDjarjh9zx5ppZH7goNUUF7p8dJy58gmvq12st3VpTm8ncsQ4o= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983515; c=relaxed/simple; bh=7sc2VSCzxXbXT6QmOm74NwQsLWnqG2atM0MFXsJUaEw=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=Is73EcHN8odFhuXciCucF9RV+1eBVW/gXBTeuaeQiCrUQx9I05EpUQMjSUSya3hO9+ulfiGhiIt8LZfDtoyfBqadrQrGvo0Q0zA/T6KQbxf2yhzCTyyo2ZcG8Ca3O8x3zjUQbgBCFJEw60HC+dR/4QkQGx0w73wQ89tqluEgN7Y= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=pass smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=ICQZHTU5; arc=none smtp.client-ip=209.85.219.41 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="ICQZHTU5" Received: by mail-qv1-f41.google.com with SMTP id 6a1803df08f44-6eaddbfcbc9so35576766d6.2 for ; Fri, 14 Mar 2025 13:18:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1741983513; x=1742588313; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=YszKF+95vQrFZZnSop7aU9GmTIFgsPqtQnZGrY/czpk=; b=ICQZHTU56c7MguRpzyxRy+h98VXfhLn3J5WxfrLU9aODUghir+pJs5cmKZNMBLaea/ ZBynLBrijlLESdeg69qXDqo8+wCA7aGNSyC85nts0Ebb8L8wAW7hjoQ5/pC8x97MoHrA egObIo5Hq/UTCoidN9zwV3AVCJqSj1koLTCypGw4mwYUGvAdR77syqhdORgVgDth0FEH buDvKkv2xagHdS5SXvzUpfZq3NnQdmsStxwrRonumzsnmMdYvRnHV/+snY3kmgkGHPRb rgIDCfpOr9Aqa0cluIyu+kpldCvZi11IbQQlwEkm/wtzJALTIGKO71M+wnPGM0OBQZgf mQ8A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741983513; x=1742588313; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=YszKF+95vQrFZZnSop7aU9GmTIFgsPqtQnZGrY/czpk=; b=R1LFzhc0hLsxjlD3Twr+bspFHZ945OLaSPBMVawu/2RpnPURIv+cF/h5nAYl5qvYG9 BKr26DbX/ahgsh4SklvDS4LE4mpGi0PUly303roNBW4XKduTWzVeYxgg0HJiJ+hTDPs0 TFFIE+qoSY1sU9Ulc7f79B2AhgMw1zioOtVI6TcLkrlPn5Lx0QMmTJwa/G5DaqPGEXge BfLPSlsbNS/by05fXamYcT4Xa7DY4UHdDATx9y7WPfgwj5vE8/+GicLZMW8u7ef4i/Qq rE71nYHw0tY2V47iHGnLUy5zbFUXO0KHc9CI4J2/GrIk49g/c9BYf48dfQy4yKITvpC5 OAuQ== X-Gm-Message-State: AOJu0YxvxUFFiuB5C+Gu17QwytARWG7zH3LOnxSEBJU5IqPz/IASPMOt JupMzVSb56ak+UNGhZeerbVo9DZY36NQhRfmeY9twUNlf/oBx/OHu08pPVeyM1NqEFHvB6X+I+s VL4c= X-Gm-Gg: ASbGncv6vIm2RhKgbfPgkxejVTrh89G2jsMWaOQJ8umUcObId9emusrvZvN+GR+tpXt Ux+mHjnEt0Kd7gu6clkB6DkE8FCmRBsgzNDQD6+W/A/8n+0vUOkXGlqmSkQq2DZxDMLxSL0BQlt TvWr0AWY0sD5iP7DMEvEh5sVMv/Q7UkhVm67GZ3QD8Sro9ZZ/+BTAiIqd16LWQEjMfFxHQ3IyXd Dpkg2+mGiNNT0TNUW63W7WYbYQxVHF3DCPIAaxYeRPT5Y/F96NVmtc0uAJwKRNuLIEwJjdY6qOd U5PYpIGjWdNMAa0KASyfzMHLU2bgOkEkfSL5GPwsN0E0R+ulTkrAz1EXlzcJ4tQPuVZ22PV0+LD 3eedr2iUqQVGATQhg X-Google-Smtp-Source: AGHT+IFPzikp+5vyue8enY8067dXbNuVpGcRxzuSytrLMjH8xk+PM3GmUcJy+btVzPgrVbNXWC+8Lg== X-Received: by 2002:ad4:5aaf:0:b0:6d4:25c4:e775 with SMTP id 6a1803df08f44-6eaeaa0646emr55717466d6.15.1741983512809; Fri, 14 Mar 2025 13:18:32 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with UTF8SMTPSA id 6a1803df08f44-6eade23190csm27727826d6.31.2025.03.14.13.18.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 14 Mar 2025 13:18:32 -0700 (PDT) Date: Fri, 14 Mar 2025 16:18:31 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v4 04/13] pack-bitmap.c: teach `bitmap_for_commit()` about incremental MIDXs Message-ID: <832fd0e8dc3a37e36b3d59085e448f8de84ce4b4.1741983492.git.me@ttaylorr.com> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: The pack-bitmap machinery uses `bitmap_for_commit()` to locate the EWAH-compressed bitmap corresponding to some given commit object. Teach this function about incremental MIDX bitmaps by teaching it to recur on earlier bitmap layers when it fails to find a given commit in the current layer. The changes to do so are as follows: - Avoid initializing hash_pos at its declaration, since bitmap_for_commit() is now a recursive function and may receive a NULL bitmap_index pointer as its first argument. - In cases where we would previously return NULL (to indicate that a lookup failed and the given bitmap_index does not contain an entry corresponding to the given commit), recursively call the function on the previous bitmap layer. Signed-off-by: Taylor Blau --- pack-bitmap.c | 11 +++++++---- 1 file changed, 7 insertions(+), 4 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 72fb11d014..615d5de85e 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -941,18 +941,21 @@ static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_ struct ewah_bitmap *bitmap_for_commit(struct bitmap_index *bitmap_git, struct commit *commit) { - khiter_t hash_pos = kh_get_oid_map(bitmap_git->bitmaps, - commit->object.oid); + khiter_t hash_pos; + if (!bitmap_git) + return NULL; + + hash_pos = kh_get_oid_map(bitmap_git->bitmaps, commit->object.oid); if (hash_pos >= kh_end(bitmap_git->bitmaps)) { struct stored_bitmap *bitmap = NULL; if (!bitmap_git->table_lookup) - return NULL; + return bitmap_for_commit(bitmap_git->base, commit); /* this is a fairly hot codepath - no trace2_region please */ /* NEEDSWORK: cache misses aren't recorded */ bitmap = lazy_bitmap_for_commit(bitmap_git, commit); if (!bitmap) - return NULL; + return bitmap_for_commit(bitmap_git->base, commit); return lookup_stored_bitmap(bitmap); } return lookup_stored_bitmap(kh_value(bitmap_git->bitmaps, hash_pos)); From patchwork Fri Mar 14 20:18:34 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14017393 Received: from mail-qk1-f178.google.com (mail-qk1-f178.google.com [209.85.222.178]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 3DE3D2063DF for ; Fri, 14 Mar 2025 20:18:36 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.222.178 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983518; cv=none; b=BiszIJqOzdWLiSF8nLRFuYZLCJOcRXJHPNbKuVgqI9XlSjxSFlsgOHmdR/Y6tvCsNgAaAKg4wLM2JZiEKiBCON7lPCs2Mnn4tyQtLOlLDs+3SejleXhQfZrsrtNr+HAdqzeB9jbQPtIclkAKBcJBDutDPTYbQT1/Z1T2fZRee9U= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983518; c=relaxed/simple; bh=lIwvvQmVXJ0GbYL4ALqpDZLu/R97BKM8Z72m+yyE1Fc=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=LaJhjM5elGBegG2mBpJLC+SUfbvD0RXrRPxjk5bEdyZ/j4eScUF8vs/9JF/S2zzBfBWOnY0QwQrXBe1W3cr/SZ1tN1BWaAIELZOgbw9a5Nu3ADWhcP9MItFkHnJhOlIT7n8rgquvz436iZc2Gr1ZUDC9aAleoLQ+YRRnSFGq1QY= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=pass smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=NyH+CeSt; arc=none smtp.client-ip=209.85.222.178 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="NyH+CeSt" Received: by mail-qk1-f178.google.com with SMTP id af79cd13be357-7c24ae82de4so284518285a.1 for ; Fri, 14 Mar 2025 13:18:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1741983516; x=1742588316; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=5VEmdPrpEdUmpvGFdaIDqrXWYbn4QIFeQ0SZ8NgIwwg=; b=NyH+CeStX8/cZDsnaPJxP6CB9p/fwDz14/sjD5gCsXMyBo8jBdZanQLh/nuvad0X4p 6wpq2AB7rbtuWWq09EHi1y75pqPn06M922ZEHGcPd//fFea8NG6uxY5A6EA3zh7YF5nw 6Q/NazfWo6ne6S2AEyZt2yAVTubhXePqRiZcZjQ4nFLExNM6ApM4vLnkFMFhjHgHtHUO p6xOECfDRARbsj4QCozf73DLeitTk3weUBhTsy6o0GKp/ZwnQVPhzkYkuI1gNgNXw3sT qQDNqX4feBHSGGHpnqb+Na4lZRdHjCQnKtlnFTAwvHlIHL7kVq6bpNM3+4Pi65PxbLBB qHRA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741983516; x=1742588316; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=5VEmdPrpEdUmpvGFdaIDqrXWYbn4QIFeQ0SZ8NgIwwg=; b=kVhFF9rQDQgMNP2CBUdpr7QiP0BXUcI7HlUt9DyzSpgnfu3U86sAH6y+F1hL/hw9Ve 89GFQnd2rKuryXJ1C3CjBOA2jgxXKivHvZu/GnOmAJuu2RB+XUwwRcu7WwfIhevPhIVi h+wQvUnLRjoFCYfrF9SmjU5NE+pWO++wCQcagtB8JLQAu18T6HcRxEJoWSsFXpm3qzbJ 8Xpz8MJmlvQ/gSJ42PQDkwVfCY3ugPEEnquITw+nhxske7E7uTOfsiLsMPEtsoTx3+pC Ox8wyB37v6IG4R/GL1zoyW5cA3ALePdKPYbmXoH98OgSRPD6wkKfXjl1N3QO2s9wILc/ oGjw== X-Gm-Message-State: AOJu0YywVNow5Q+K87v64F/R6xhqcyaBF9mfrNKauf9DKXkw7sB51Oj1 zdm1D2ApUZOKRpvRQ95KQo7R/x7pVJW8xc5si9gD/EhtvGuHUPU+cobzErLq9g4gclGE+HqRV8a lr9s= X-Gm-Gg: ASbGnctpe4C682DQd7mjG6iYqYS3LDIQtaYNxQxiszbOAG1xn27jggu3/mL7OokYnRZ 1DhDgyyRspgDs0pBUF3ZoHD3CuRhYF0eBbJdos8lvG50/LsRAHT2/8vvAXKLXXNuqFi31j+zvWb u/4gaF2s+U9+Q9JOc2M0x53IYrQbulgplUQTfMw0JYPuhYWIi/yE6uPru6SSdZe5A15TlUlhhsr luFXMIMFUvfJaanCCYLtO3KCc5UONKFp3q4QutMfQ9WPkzAedih3ez2m0L6vpoc0j79dlYzq8O9 h9AxC3spKFc14QwgfWMGlm2EGg++/0ag0pqXHYWRXMf65Kper8QptAmENTEI4e3q5X7QkEDdkR/ vAdz890WFIs7YrJrw X-Google-Smtp-Source: AGHT+IHCAvJKhCBNn3T7rvvdBSJQDk6WKAXlLQ8JLB2LL97qazUA356CWjh6wGmJNSLx7+LK2g6lmQ== X-Received: by 2002:a05:620a:450c:b0:7c5:4c44:db9a with SMTP id af79cd13be357-7c57c8f8c5bmr573720185a.37.1741983515930; Fri, 14 Mar 2025 13:18:35 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with UTF8SMTPSA id af79cd13be357-7c573d6fcf4sm294387985a.75.2025.03.14.13.18.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 14 Mar 2025 13:18:35 -0700 (PDT) Date: Fri, 14 Mar 2025 16:18:34 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v4 05/13] pack-bitmap.c: teach `show_objects_for_type()` about incremental MIDXs Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Since we may ask for a pack_id that is in an earlier MIDX layer relative to the one corresponding to our bitmap, use nth_midxed_pack() instead of accessing the ->packs array directly. Signed-off-by: Taylor Blau --- pack-bitmap.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 615d5de85e..1b4fec0033 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -1635,7 +1635,7 @@ static void show_objects_for_type( nth_midxed_object_oid(&oid, m, index_pos); pack_id = nth_midxed_pack_int_id(m, index_pos); - pack = bitmap_git->midx->packs[pack_id]; + pack = nth_midxed_pack(bitmap_git->midx, pack_id); } else { index_pos = pack_pos_to_index(bitmap_git->pack, pos + offset); ofs = pack_pos_to_offset(bitmap_git->pack, pos + offset); From patchwork Fri Mar 14 20:18:37 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14017394 Received: from mail-qv1-f43.google.com (mail-qv1-f43.google.com [209.85.219.43]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 0ADFA2054F3 for ; Fri, 14 Mar 2025 20:18:40 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.43 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983522; cv=none; b=XdrEE9XJ++muyr7CIyU+/IoLdUQAXI6mH/rY2y/Soa7ALI0x5Y/vnz9sYRLQt8DrFpHn7Hlrd8DzyKJuCVw6bbm5aGn7bOElhRT/EG2LO5iFpTAVcpPxxIG5o/MXH3fYP2MM5GMSy2uepUACZ6rTk1d79f5TaUq08ApIIQRye+M= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983522; c=relaxed/simple; bh=KM2bJA0MViNUnwdYT0Bz58VxPzDp7jMGau/ps4mS4+U=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=lQ3epPiWvZxrYxEyxM3GeX4uBbrupY01FBLiyLFbdDaVtsB6yPK4w8Xr56ilRnFoFsT1hYogemt1aEVL+2JeQ4i3hxAfEWtJfytNqEH0WeI18TgO/8A5wN1gwoc8452EfI33frmJfM+71b/If9RdFsBgclYx6oXTQ9l1Ko8KXsM= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=pass smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=1F+5CEzS; arc=none smtp.client-ip=209.85.219.43 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="1F+5CEzS" Received: by mail-qv1-f43.google.com with SMTP id 6a1803df08f44-6e91d323346so26834656d6.1 for ; Fri, 14 Mar 2025 13:18:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1741983520; x=1742588320; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=kP2Cp4/Wu0NP1Cmz9gq1/23FRXWJPZdjWHo2ATLqG3Q=; b=1F+5CEzSg15IulRDEuA16DSU0A/Ix7CPVmker9Bv821bAr5YHJZH7ZwWWqbNgi9hQ8 wyDWhvRCCLGO476UpG5LNzbbS7mNC7jlMRnCfcRThqlrVB2kafSGwG6eoKZKYzRiNHNO qpw0N1eqbbdO69evaN0T0Sfr6qtpi8DrihyHOGwr+gMU52/spY4Iu7xqEmevcNbJ54N4 EITIvEyC9x8xw7TQPCvEZrDwDUpHx1LJhtW13HTANcOd/w62gfoWc2VNGX0PFLnT13pI GjSlvP454gTNt2g+WvwnBIQKjqm6RAFYls20H4SsQSxhjkfzEQC0mGVAqzT8VaMWsu3/ im7w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741983520; x=1742588320; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=kP2Cp4/Wu0NP1Cmz9gq1/23FRXWJPZdjWHo2ATLqG3Q=; b=DLOqhRIyV8/0u0zML6mnBnkta9RXPZ1sG5WAmjUqIcsYekmgMCAl3WbDTbWJmT+bzz DLNd+JIyZxhQd8IrlHeII5nZZjSidmXtiWgVwEDRxjK+oIsftXoiXnWiFkkzCoXxgGC0 ZRR7uj8LR4fnwYIYjsDrQUBPO/LHZKHRsjpvt7eOZS5gWV3jMw4E4xbzaAdmLx1qjgcd rfpi+SufQ7r48ZcDQHVXIqha0ztbbIPG9dzl7jWPIaEGegavwQrdS72s/wLCJcYA92zI gg1ms3Cw2g2tJV8mV7UsTdHziKu4Yo8dz+D9D2vFmV7KWiJmYfmarJFv+7fCOtLVimXv U+4g== X-Gm-Message-State: AOJu0YxwPzSeHVfUslH7BZRjj2UKK5Yz/yiDsXJ5Zu9iouBL7BBUa+01 KF+Mth7akQOuLA2Ylf/A66H1/B+py3nyjrdieQSJVWuIoMLvunU+u2clxi1NjIPm1Px+J/BE5rT BDe4= X-Gm-Gg: ASbGncvMKSgHcn5e1kTOkkwIlgVC8rdOY5TdJXRDv0gxiD9UFbFjbuOJcKaOeusgUp0 mJ/g0dn3YbRh0/5hn+iyFVO65qsa/6t5sjBkWpiRqItDmU76M4QxzJvNsbJwe0fps1lA5hp8x3o ev4i4OoVgRk2pZ7iPX+bCuPPhpoyHyl1EH7VqOZ/GaJO8GX5zUAS3P94/LFkERvYkDAeIdkaa6w VrGQx7/oV87xh3QRzcGY3Kl5uW61f+bG9TG/YiOamx7s3jH06JROYOhOZhX7fwZ6cTCr6sp2AT9 Kpf8l5QEatOvJ8rve+QT1kr440nzismQPQJf4kTEob+pWVhlVjmiFgp6eD5N/FGKYzUbN7XHDI8 PYy2BJGpiepaMx7h7 X-Google-Smtp-Source: AGHT+IGBQJCpYZ5N4TQlhEu+xSIy20+lq30heDAmGZezrBxqeZeWhkoTtZSDUu2Aso5lKhd/kpq5cQ== X-Received: by 2002:ad4:5c49:0:b0:6e2:4da9:4e2d with SMTP id 6a1803df08f44-6eaeac211b7mr51370116d6.9.1741983519053; Fri, 14 Mar 2025 13:18:39 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with UTF8SMTPSA id 6a1803df08f44-6eade209bcdsm28018196d6.24.2025.03.14.13.18.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 14 Mar 2025 13:18:38 -0700 (PDT) Date: Fri, 14 Mar 2025 16:18:37 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v4 06/13] pack-bitmap.c: support bitmap pack-reuse with incremental MIDXs Message-ID: <14d3d80c3d301233048004fe9de18154aa597782.1741983492.git.me@ttaylorr.com> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: In a similar fashion as previous commits in the first phase of incremental MIDXs, enumerate not just the packs in the current incremental MIDX layer, but previous ones as well. Likewise, in reuse_partial_packfile_from_bitmap(), when reusing only a single pack from a MIDX, use the oldest layer's preferred pack as it is likely to contain the most amount of reusable sections. Signed-off-by: Taylor Blau --- pack-bitmap.c | 11 ++++++++--- 1 file changed, 8 insertions(+), 3 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 1b4fec0033..7a41535425 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -2333,7 +2333,8 @@ void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git, multi_pack_reuse = 0; if (multi_pack_reuse) { - for (i = 0; i < bitmap_git->midx->num_packs; i++) { + struct multi_pack_index *m = bitmap_git->midx; + for (i = 0; i < m->num_packs + m->num_packs_in_base; i++) { struct bitmapped_pack pack; if (nth_bitmapped_pack(r, bitmap_git->midx, &pack, i) < 0) { warning(_("unable to load pack: '%s', disabling pack-reuse"), @@ -2359,14 +2360,18 @@ void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git, uint32_t pack_int_id; if (bitmap_is_midx(bitmap_git)) { + struct multi_pack_index *m = bitmap_git->midx; uint32_t preferred_pack_pos; - if (midx_preferred_pack(bitmap_git->midx, &preferred_pack_pos) < 0) { + while (m->base_midx) + m = m->base_midx; + + if (midx_preferred_pack(m, &preferred_pack_pos) < 0) { warning(_("unable to compute preferred pack, disabling pack-reuse")); return; } - pack = bitmap_git->midx->packs[preferred_pack_pos]; + pack = nth_midxed_pack(m, preferred_pack_pos); pack_int_id = preferred_pack_pos; } else { pack = bitmap_git->pack; From patchwork Fri Mar 14 20:18:41 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14017395 Received: from mail-qk1-f173.google.com (mail-qk1-f173.google.com [209.85.222.173]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 223082054F3 for ; Fri, 14 Mar 2025 20:18:43 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.222.173 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983526; cv=none; b=EhifaAnjr22h52MBROo1FKmbMDSvPDPK7SNQbNcNWGm2qnZ+JYMMbxP+Oj8ESr5irGdd3Gmy04sGaBMTDKzQJ7LTGJlHDCY+OMYp9QylU9R4kCUOMAe9pnmlXHojRxghlHjC7Tf3zhi+sFkTnW8hnnH73RKz5sOGF24gvTkAcw0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983526; c=relaxed/simple; bh=wwH0XQaRbqNlb+WxfwmWe7VSWT+4MMMeQm70uzZAzoA=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=IWuWT/+fnTF9/vSPIw6q/gL6cBrQB8mBhwWrtBLszgsgjfMqRFpV29bDXMk+UW6uE44M90yYcvWAGsqtWTVBnzEVE8dUyTEyINNt0W8Ggrq/2lE/gPAYKtilTGOnxOIeskN2lhLeIfrk+HjqSYWXeN0gx+pz1fefM0UT8iNiV5M= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=pass smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=MoaDpiR6; arc=none smtp.client-ip=209.85.222.173 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="MoaDpiR6" Received: by mail-qk1-f173.google.com with SMTP id af79cd13be357-7c55500cf80so196115885a.1 for ; Fri, 14 Mar 2025 13:18:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1741983523; x=1742588323; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=nUi1fV5CbQ0P51wBkNONPREMhlgs8lPVXE/LfhfBuNg=; b=MoaDpiR6C3E9fI5/L582jrufoS1vKGZOSZK1+mHuay+v+ZR6bPWss6APQkjGufFDNY z9Pwia4jqgDuuRZOYR0gZo18/17YcTRUlvaugjlaR9IBe9O3yeohzWp9DO/gnRcgcARl Q54kFJYHiv3o7u+AQ7jnox11I/MdfvTXQmsv6Inc3Uget0EzCltIMqHdJ/R24Bp4eYU1 tRCGtOH3Lo9Sdmoh9e2HqEBz5JtF4cX56tEwGgzUBRw8K3UKtJy4tlpQUG55sN9z3nvy 4DGwF7DBKfrHZGLiCSxGqvVQnyn1v0QJz0xB71+BE3HDZuZFRo/cgW2etZ0t7TMnpkqW 7cQA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741983523; x=1742588323; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=nUi1fV5CbQ0P51wBkNONPREMhlgs8lPVXE/LfhfBuNg=; b=qZObTlWlbeBSO9iBog3qYpWIcePyqbov6qWINQ1vRRzOguIYtf7PymMNoawEuMkQRq h+8NEH5nHkobRaCjVT2dDqqpqWkg17gLTOx8oJf/5GFBOf9sXOX5w8TvpFWEZk1lsWJH hXVnOumDmVLqh62IcIFwYxSA4UqQEKvc3orhVaGV/8Gxd6TaGk9SnHkcykDBJpXadlNO DfpxHXXjsPSkDLEv/aLjdAK69+6W7OC7ASAZ8V/bYWrLoKjAJAb3Tn888BQPBpRn6ZJi 2dZJvhtRTbbzMmJZPiOpazCYVUTzNAFm6Q+MrSsrJVE+xpQ6ONE47SqcxfxQJ062/N5G nThw== X-Gm-Message-State: AOJu0YyEmhRfo7YKxLFQ9GKG85Wv8QqGijogyPpcaEeulYW/9yq/ng+I aUIlfVPSckv/PpInLm/e6bcVILz0rNplkt6OrHrZDlxLO0vV7beLomWPBb6mhVavwDiT4yrBZaF W1ds= X-Gm-Gg: ASbGnctZUI3QWfIjWSYQMabjhxWwIM570u81b3h7HVmErnp2FjOtajJTW5GsmcfyIig BDOivkBOzkq2fMJlm+FX+jYLqVe8h7ZcP8p52Eb6LaQx9vopVgp3I+kp1t0kpK5BC7GPv2uebS8 kusWaBLRgWlPOxe78vu8Q0oldEoOEiAS1WgQPJsEnRjsse8PnqSt9aKeAVU+Vzsvqwela2jG+dE DSxbHpdp9xcgzpGsweWo6luL0sifBtBdq3m/W9wFuoQh9kWw7kbnFZWYNYooZqzcQIjyyvhcWsY YTkq8ggj1r5UVzjje0LqGxi2GCCztBMZ6bvt9LNLcYIq0AUav9iGWdUPIvVEgWRqwNhCnCA5dfw UennGwiAFdYaNC2TC X-Google-Smtp-Source: AGHT+IECe4CHLsc6BKmFACyDXxT8B7939TGaNHbwaUVfZLC9PGag3dFgY6ryRoDfPWR0jQL3hH/CgQ== X-Received: by 2002:a05:620a:4550:b0:7c5:49b7:237a with SMTP id af79cd13be357-7c57c7e22d5mr415952185a.19.1741983522739; Fri, 14 Mar 2025 13:18:42 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with UTF8SMTPSA id af79cd13be357-7c573c4db57sm297931485a.8.2025.03.14.13.18.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 14 Mar 2025 13:18:42 -0700 (PDT) Date: Fri, 14 Mar 2025 16:18:41 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v4 07/13] pack-bitmap.c: teach `rev-list --test-bitmap` about incremental MIDXs Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Implement support for the special `--test-bitmap` mode of `git rev-list` when using incremental MIDXs. The bitmap_test_data structure is extended to contain a "base" pointer that mirrors the structure of the bitmap chain that it is being used to test. When we find a commit to test, we first chase down the ->base pointer to find the appropriate bitmap_test_data for the bitmap layer that the given commit is contained within, and then perform the test on that bitmap. In order to implement this, light modifications are made to bitmap_for_commit() to reimplement it in terms of a new function, find_bitmap_for_commit(), which fills out a pointer which indicates the bitmap layer which contains the given commit. Signed-off-by: Taylor Blau --- pack-bitmap.c | 107 ++++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 86 insertions(+), 21 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 7a41535425..bb09ce3cf5 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -938,8 +938,9 @@ static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_ return NULL; } -struct ewah_bitmap *bitmap_for_commit(struct bitmap_index *bitmap_git, - struct commit *commit) +static struct ewah_bitmap *find_bitmap_for_commit(struct bitmap_index *bitmap_git, + struct commit *commit, + struct bitmap_index **found) { khiter_t hash_pos; if (!bitmap_git) @@ -949,18 +950,30 @@ struct ewah_bitmap *bitmap_for_commit(struct bitmap_index *bitmap_git, if (hash_pos >= kh_end(bitmap_git->bitmaps)) { struct stored_bitmap *bitmap = NULL; if (!bitmap_git->table_lookup) - return bitmap_for_commit(bitmap_git->base, commit); + return find_bitmap_for_commit(bitmap_git->base, commit, + found); /* this is a fairly hot codepath - no trace2_region please */ /* NEEDSWORK: cache misses aren't recorded */ bitmap = lazy_bitmap_for_commit(bitmap_git, commit); if (!bitmap) - return bitmap_for_commit(bitmap_git->base, commit); + return find_bitmap_for_commit(bitmap_git->base, commit, + found); + if (found) + *found = bitmap_git; return lookup_stored_bitmap(bitmap); } + if (found) + *found = bitmap_git; return lookup_stored_bitmap(kh_value(bitmap_git->bitmaps, hash_pos)); } +struct ewah_bitmap *bitmap_for_commit(struct bitmap_index *bitmap_git, + struct commit *commit) +{ + return find_bitmap_for_commit(bitmap_git, commit, NULL); +} + static inline int bitmap_position_extended(struct bitmap_index *bitmap_git, const struct object_id *oid) { @@ -2511,6 +2524,8 @@ struct bitmap_test_data { struct bitmap *tags; struct progress *prg; size_t seen; + + struct bitmap_test_data *base_tdata; }; static void test_bitmap_type(struct bitmap_test_data *tdata, @@ -2519,6 +2534,11 @@ static void test_bitmap_type(struct bitmap_test_data *tdata, enum object_type bitmap_type = OBJ_NONE; int bitmaps_nr = 0; + if (bitmap_is_midx(tdata->bitmap_git)) { + while (pos < tdata->bitmap_git->midx->num_objects_in_base) + tdata = tdata->base_tdata; + } + if (bitmap_get(tdata->commits, pos)) { bitmap_type = OBJ_COMMIT; bitmaps_nr++; @@ -2582,13 +2602,57 @@ static void test_show_commit(struct commit *commit, void *data) display_progress(tdata->prg, ++tdata->seen); } +static uint32_t bitmap_total_entry_count(struct bitmap_index *bitmap_git) +{ + uint32_t total = 0; + do { + total = st_add(total, bitmap_git->entry_count); + bitmap_git = bitmap_git->base; + } while (bitmap_git); + + return total; +} + +static void bitmap_test_data_prepare(struct bitmap_test_data *tdata, + struct bitmap_index *bitmap_git) +{ + memset(tdata, 0, sizeof(struct bitmap_test_data)); + + tdata->bitmap_git = bitmap_git; + tdata->base = bitmap_new(); + tdata->commits = ewah_to_bitmap(bitmap_git->commits); + tdata->trees = ewah_to_bitmap(bitmap_git->trees); + tdata->blobs = ewah_to_bitmap(bitmap_git->blobs); + tdata->tags = ewah_to_bitmap(bitmap_git->tags); + + if (bitmap_git->base) { + CALLOC_ARRAY(tdata->base_tdata, 1); + bitmap_test_data_prepare(tdata->base_tdata, bitmap_git->base); + } +} + +static void bitmap_test_data_release(struct bitmap_test_data *tdata) +{ + if (!tdata) + return; + + bitmap_test_data_release(tdata->base_tdata); + free(tdata->base_tdata); + + bitmap_free(tdata->base); + bitmap_free(tdata->commits); + bitmap_free(tdata->trees); + bitmap_free(tdata->blobs); + bitmap_free(tdata->tags); +} + void test_bitmap_walk(struct rev_info *revs) { struct object *root; struct bitmap *result = NULL; size_t result_popcnt; struct bitmap_test_data tdata; - struct bitmap_index *bitmap_git; + struct bitmap_index *bitmap_git, *found; struct ewah_bitmap *bm; if (!(bitmap_git = prepare_bitmap_git(revs->repo))) @@ -2597,17 +2661,28 @@ void test_bitmap_walk(struct rev_info *revs) if (revs->pending.nr != 1) die(_("you must specify exactly one commit to test")); - fprintf_ln(stderr, "Bitmap v%d test (%d entries%s)", + fprintf_ln(stderr, "Bitmap v%d test (%d entries%s, %d total)", bitmap_git->version, bitmap_git->entry_count, - bitmap_git->table_lookup ? "" : " loaded"); + bitmap_git->table_lookup ? "" : " loaded", + bitmap_total_entry_count(bitmap_git)); root = revs->pending.objects[0].item; - bm = bitmap_for_commit(bitmap_git, (struct commit *)root); + bm = find_bitmap_for_commit(bitmap_git, (struct commit *)root, &found); if (bm) { fprintf_ln(stderr, "Found bitmap for '%s'. %d bits / %08x checksum", - oid_to_hex(&root->oid), (int)bm->bit_size, ewah_checksum(bm)); + oid_to_hex(&root->oid), + (int)bm->bit_size, ewah_checksum(bm)); + + if (bitmap_is_midx(found)) + fprintf_ln(stderr, "Located via MIDX '%s'.", + hash_to_hex_algop(get_midx_checksum(found->midx), + revs->repo->hash_algo)); + else + fprintf_ln(stderr, "Located via pack '%s'.", + hash_to_hex_algop(found->pack->hash, + revs->repo->hash_algo)); result = ewah_to_bitmap(bm); } @@ -2624,16 +2699,10 @@ void test_bitmap_walk(struct rev_info *revs) if (prepare_revision_walk(revs)) die(_("revision walk setup failed")); - tdata.bitmap_git = bitmap_git; - tdata.base = bitmap_new(); - tdata.commits = ewah_to_bitmap(bitmap_git->commits); - tdata.trees = ewah_to_bitmap(bitmap_git->trees); - tdata.blobs = ewah_to_bitmap(bitmap_git->blobs); - tdata.tags = ewah_to_bitmap(bitmap_git->tags); + bitmap_test_data_prepare(&tdata, bitmap_git); tdata.prg = start_progress(revs->repo, "Verifying bitmap entries", result_popcnt); - tdata.seen = 0; traverse_commit_list(revs, &test_show_commit, &test_show_object, &tdata); @@ -2645,11 +2714,7 @@ void test_bitmap_walk(struct rev_info *revs) die(_("mismatch in bitmap results")); bitmap_free(result); - bitmap_free(tdata.base); - bitmap_free(tdata.commits); - bitmap_free(tdata.trees); - bitmap_free(tdata.blobs); - bitmap_free(tdata.tags); + bitmap_test_data_release(&tdata); free_bitmap_index(bitmap_git); } From patchwork Fri Mar 14 20:18:44 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14017396 Received: from mail-qv1-f43.google.com (mail-qv1-f43.google.com [209.85.219.43]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 3D0082066C6 for ; Fri, 14 Mar 2025 20:18:46 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.43 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983528; cv=none; b=UeQHEa50Cddq4GcZzokAlqaL2VkOJmEnFDy6PWVkC9Piyzepuc+yvpsOxNYh/15UPrqmsqOEJzZn4c+AvL5fJ7DhmL47y2FfDcz/Cnr15xapXuYXCap8GbiAxzr4D+StsQSmcTw5aAM/ZZGur3XOZr5D1GMH1AVKROZ8/R36eOI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983528; c=relaxed/simple; bh=1vQrmlJMOKmMotEtkcskNoJ0KE6x8lYNw5gNtttKdBM=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=TsOxf9DbVmqHA12ZrnAf+uvxTDXRL5MO4P1rBiZBhWazfa8JEL7YxOT5QOI2YMuHE8DKN3w1+W6lvxJOMTsq3asXoyIsJyQCl0W4T25ToW5b4Av6OBAWMma88xJzgIb9bz17PSTDlRGPu9Yh2I+tYxJGJya50FuiFK2Q6xAT2NM= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=pass smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=CsGUmGTy; arc=none smtp.client-ip=209.85.219.43 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="CsGUmGTy" Received: by mail-qv1-f43.google.com with SMTP id 6a1803df08f44-6e8ec399427so20224586d6.2 for ; Fri, 14 Mar 2025 13:18:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1741983526; x=1742588326; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=ODHPTAPMWIatEvoJRULe6xD/J8KK9pnjKVoT3acMt+c=; b=CsGUmGTyKfU9VLjstETqoUQlZpisvLNR5y+LtE+mt2yiLzuGZvOTR9c1H1SefxPCRD bqWHs2rRgDYrx8J2k4erXV8VkB7HRH39ybcpK5/R/TleaYeRIX+n8XYTcLg9mS31hMmK fhX9xOhBl1F4fYSr/kh8EjBbNY19w02GAqMZ7CdQ7/043FNp56cv19u/trxvLZndzRsB ApbFbQh7x6OW/TYZHv5+acpDKtPtAAD1VUChtky0RdcyglSCfWuC9/WhelzHJiD0YrjU 5kMYr8CxrZ0aUM0OWiVxwenVukGp0moysFF/aenSz3lrLnwod6a2DFrmbBrQAGEYSMfi 9KtQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741983526; x=1742588326; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=ODHPTAPMWIatEvoJRULe6xD/J8KK9pnjKVoT3acMt+c=; b=hlKWqRky+WQ/Kcy3KrXwMoU+k2isodiv174/Z6qx0sGRMfRvLBuVLgEJ3VtxEwAnZS npJrupeelO4OJEL3JL5ofQN1kxuesIkjwbxrFhkaHuMWwndNcCLwCntEPDZY4PT77m36 TGTicx9V9JBrsQ1Wbdswnnee3K/zXbx8wteqXpALj9AQv5KjsRSR3Xt0/YzCnKyYcemv 9EfofCMW8DA70Lr6Py6Uogw/Ct6CfQuQ0phVyOQirYeY3KD6EVN0fCcqOjrqTSJWYOhp PKSRoXkB8VzZ6J49u9ouDb30xuFeKxJGaxJKqUIE22zBOgoilN2EDOvyYFQVVvPv5wQB Ddsg== X-Gm-Message-State: AOJu0Yz79Gt/3WDCxSfCfdmwRvA9K0OG1HJLI8f7TXXqGeut/0juWYph 4SNL7LVvpTJzRoyHkDLgJOzThajQaZ2N0PGcvObi8aGqIEupxGbC1Ek5LG35wvHfmo5ViFJ4ha5 G6+A= X-Gm-Gg: ASbGnctBELHDmyRhHl2GZXrNo8iknHASFW4GIlHuLmCoeUCfVIJ58cPPLCjDaleq+rf Kx32mrQLyaH60z4kka+bn+4LA6lOEdI/ZeNeR2Hj4TbOHzUOnSd95vE8YrJvUslbE9vo9UiKsi1 Rv7gXQfUW1H0lxdvPCEm1J1D5DicJoGaSvtg0WbOS89gmCfhKWTkfHa1nS4P7oJqiM5PE0PUmq0 39Sqmqmt1oAT8sXaUAIc6Tj+yDDlfEoSxwKdeOdDhk8PJ7vyarI5uQfSapkt++To4FwmFPP6boo 6KDMid2FcwbjLOuYD4H9CU6S6WDb6/PYZZgNeYPFX3mgpQwWb9Kb86EYRlYJFCQPfPdjSkpVl6r W0+w1/t496Jme7sCj X-Google-Smtp-Source: AGHT+IGo+0YZ4hzdoR/RTwNrey3GUcXKusEaMDZ9zWF4CtS+e7NvuJyLL94luCiRaIdEPRaEploMZA== X-Received: by 2002:a05:6214:5289:b0:6e4:2dd7:5c88 with SMTP id 6a1803df08f44-6eaeab04210mr43265606d6.38.1741983525851; Fri, 14 Mar 2025 13:18:45 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with UTF8SMTPSA id 6a1803df08f44-6eade2342eesm27669716d6.38.2025.03.14.13.18.45 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 14 Mar 2025 13:18:45 -0700 (PDT) Date: Fri, 14 Mar 2025 16:18:44 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v4 08/13] pack-bitmap.c: compute disk-usage with incremental MIDXs Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: In a similar fashion as previous commits, use nth_midxed_pack() instead of accessing the MIDX's ->packs array directly to support incremental MIDXs. Signed-off-by: Taylor Blau --- pack-bitmap.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index bb09ce3cf5..8442f8e55f 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -1778,7 +1778,7 @@ static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git, uint32_t midx_pos = pack_pos_to_midx(bitmap_git->midx, pos); uint32_t pack_id = nth_midxed_pack_int_id(bitmap_git->midx, midx_pos); - pack = bitmap_git->midx->packs[pack_id]; + pack = nth_midxed_pack(bitmap_git->midx, pack_id); ofs = nth_midxed_offset(bitmap_git->midx, midx_pos); } else { pack = bitmap_git->pack; @@ -3047,7 +3047,7 @@ static off_t get_disk_usage_for_type(struct bitmap_index *bitmap_git, off_t offset = nth_midxed_offset(bitmap_git->midx, midx_pos); uint32_t pack_id = nth_midxed_pack_int_id(bitmap_git->midx, midx_pos); - struct packed_git *pack = bitmap_git->midx->packs[pack_id]; + struct packed_git *pack = nth_midxed_pack(bitmap_git->midx, pack_id); if (offset_to_pack_pos(pack, offset, &pack_pos) < 0) { struct object_id oid; From patchwork Fri Mar 14 20:18:47 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14017397 Received: from mail-qt1-f182.google.com (mail-qt1-f182.google.com [209.85.160.182]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 09917205AAC for ; Fri, 14 Mar 2025 20:18:51 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.160.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983533; cv=none; b=GAEznQDJ33RZnmXT7fQSg3TzcekLEwTdnP5bA1sjrTjEl+tmwd2P1B0ek366sju2sovplgwjMfBoK9b5rERbqQuinEdTmIZ5rxW2dSaGINzMwdZdcUieA4smf2f4iJG6eH/hIGRTVd8g/RPzx48Nw1E+palpZNBkipjEmKiMRz8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983533; c=relaxed/simple; bh=DpEef1SFAUj38hnMk2L6f3CdLpeF+pREdzrvrmnS0H8=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=lQEPXsTTDJQ55E4wnrpmtB9aBwVi+CzAc2/i+3reSkVp7gObJUiw/zp8Koh4ytt57qT3oxNF0p38fegH7QsW5FmrzCq7AUJeVG60EOxiFMTaT3btaIFailxqzjOKK83mBv9a7i6oqP55qA6uSyWtO4JpAhHd4qQUzCUq3j1w50I= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=pass smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=PD6djAyR; arc=none smtp.client-ip=209.85.160.182 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="PD6djAyR" Received: by mail-qt1-f182.google.com with SMTP id d75a77b69052e-47692b9d059so32906341cf.3 for ; Fri, 14 Mar 2025 13:18:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1741983531; x=1742588331; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=mOZPC0WvQ/l8NPBTO2JSUl2Uyr8+A2TaVt3ZAh4ccL8=; b=PD6djAyROwGDvpUEg0IEwUffY1jaIitbdJVSkGqdKbkawLQ3MWhmYsR8taZN/BqcMW 7DotW6oX4Tw6vIC/2SYWcEz4Z+bBCFVwzL3eoGeDb5lYrDxWD9fEkmIJH+/zgHj8+7Kp YvLiWzY6tvirtAaUOL8G71CH4hN4EjVxjJw876Ukh78/AZ2ug0549Ph4WrvkHQmHSNdo iUnd+3LIIb4ojqOJpKuOvtUpxhT+HT3njpePQ0jM2WBFht+XEVjTg2tK2HvXC5oLv6EO H5CKcFd0Kl/4xaCMQr8tesjCI94uOWHMwdPXrvJ4xSG2zuevZ67261DvN3LTcuWI95PY nwgA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741983531; x=1742588331; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=mOZPC0WvQ/l8NPBTO2JSUl2Uyr8+A2TaVt3ZAh4ccL8=; b=GrokQG66SysZO4UzBYOZ02dqXkXtr/MdRb9oOZ8ZjN3k+fPVKm9raIzTi4c+cYDkF7 sEfhzpZu2nDZ8ZTruJRooPJWqk3mM1TLd/Q5jVcHiXAh6PMnUPCJmwYdlNn3SQq2qYOb tE8Km3kFeHEsPZSXu87WVMG8Xgg9KAeS0K5VXyzYzlLhQtcMMp5D3RmMbpX5sjcC17nd lg4PyoIYJGk/ciIjKM+mbm9pOoaPqCOMt+ysR2m2aenyv0HyFNWIwum+Z5yauruOd7UY 0X48oDm+63/61/rU7429N29rx4CoSgeyclRlPBZ7DE1PxMZoz3vIINolwmGdboIwYA/K WXBQ== X-Gm-Message-State: AOJu0YyGhHBZjdUSQr78lNp+DmzbeVDnUCsISZrHSqEsbLWFjHaEERiY XWhfeQcMFCLI7tIp0cg+bP1EX0VCchcWhZk1L/igeQxDGVXcdXXeUaspZp1WOquiawPrQUi4HMQ YJeg= X-Gm-Gg: ASbGncuJIl2olfK+/lPpDEVU0E/jyQruzbCoF4acJMu/daMx9XPHVw0MJwVLmDhSSyP 1QPb24ifDnpicy2dIdrHGI7Ox6XL3OSVcL5x1P9R/7c8q42lrD7WmCVlychm7pvnVIWZGaR0N7p y8r3Ye9A3RQuKGz2Q9I18/ZtxEbDqCTS9kj4lx4Qdoe9QNC7zmMGu7Gc5QcUAr11PCxbueMC5h/ j9XCjagKHUCek3hei1m+HZ6W5HS3ayHPOodAZ1coxfW1qSC7nQ3Dh5Z7iiFksP9f8ZPp00NcfVw eHdn5D/mZtaErR3BTld3X+80cUu5WIpgh1DbqT5rb7bHmzc99wdLMAIBxELpr2dD0RTpmlr6Aaq URID7P+D5005u7z+5WpDFj4NCuso= X-Google-Smtp-Source: AGHT+IFkFk/XITloGIoVg6+Rp5tptkCKLNHbSnxTx1cV0ReHI4X8uP/szD+3NsJT4NOSgFiEKQTMBQ== X-Received: by 2002:a05:6214:5084:b0:6e4:42c2:dd91 with SMTP id 6a1803df08f44-6eaeaabadbcmr67564486d6.37.1741983528886; Fri, 14 Mar 2025 13:18:48 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with UTF8SMTPSA id 6a1803df08f44-6eade34be7dsm27577136d6.104.2025.03.14.13.18.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 14 Mar 2025 13:18:48 -0700 (PDT) Date: Fri, 14 Mar 2025 16:18:47 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v4 09/13] pack-bitmap.c: apply pseudo-merge commits with incremental MIDXs Message-ID: <11c4b7b9491c9b34a441b941902a6c29fde912dc.1741983492.git.me@ttaylorr.com> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Prepare for using pseudo-merges with incremental MIDX bitmaps by attempting to apply pseudo-merges from each layer when encountering a given commit during a walk. Signed-off-by: Taylor Blau --- pack-bitmap.c | 11 ++++++++--- 1 file changed, 8 insertions(+), 3 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 8442f8e55f..00acf5ec73 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -1082,10 +1082,15 @@ static unsigned apply_pseudo_merges_for_commit_1(struct bitmap_index *bitmap_git struct commit *commit, uint32_t commit_pos) { - int ret; + struct bitmap_index *curr = bitmap_git; + int ret = 0; - ret = apply_pseudo_merges_for_commit(&bitmap_git->pseudo_merges, - result, commit, commit_pos); + while (curr) { + ret += apply_pseudo_merges_for_commit(&curr->pseudo_merges, + result, commit, + commit_pos); + curr = curr->base; + } if (ret) pseudo_merges_satisfied_nr += ret; From patchwork Fri Mar 14 20:18:50 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14017398 Received: from mail-qk1-f175.google.com (mail-qk1-f175.google.com [209.85.222.175]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 7D0A3183CA6 for ; Fri, 14 Mar 2025 20:18:53 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.222.175 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983535; cv=none; b=XZyFZhzrhzy6ak96UM980wT4+PhYvl/qblsbM44aVBncgPMrYfFcAQS7HjPstbjOk5ypDx4rNdRzaqNl56rsqVNjOI2/0aqannGrWttOo6kpobvPTpNDKG4GimyWBjJEu1dwPWCcGMo6Ui/Uxn2OgcXYafUc323nzqxSDcAVsHI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983535; c=relaxed/simple; bh=2GNzc709su22S17XvlV5TXqrW9utlBwDgZFC+SGNZUU=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=DmXDqtqo4T4YeGTBC9/AqjxhL6b50kdYYDYwNpYdE1ix3A/RdZyFGIWHGlyhH1ay2hmpvqd8vVpsm7RxcOCGPcNxa3ky87wkePQ3hqILzJrziCndhLyMzsWnTaYTzZG7/gqRvo8F8YfY8DIwiFS34JO3mWo9SL/pffvPSF384uU= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=pass smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=iFrOngTt; arc=none smtp.client-ip=209.85.222.175 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="iFrOngTt" Received: by mail-qk1-f175.google.com with SMTP id af79cd13be357-7c0818add57so270794585a.3 for ; Fri, 14 Mar 2025 13:18:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1741983532; x=1742588332; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=KshCsw9BYsb+Zoj5mw5r3bskLU+1QkHFPw59rvGBRbg=; b=iFrOngTtHIw3G3dfPfFzGEl2rvnYDH3wVvjsYUtVVDDMW9dqh9bkQWlglcfMNKcNon E3gL9ZDtgM0KW6TgausqLpwsc1I3yXyaOU2LLl2mh5BvBxlUoEgEFyAmG+1m1eyAIygE flCEUrtkx3VsgUyheRVOnyGMwuwryJBZey0gxdoBG/ZPBVXlsxRjKx3AFMjs8kzh5cMw UubJnx/S/P/y52UiTeBEUqQFGhCEcgC6Qf6ao31oPKhPHA2bioF/HPj+SEPffiFdtfXR 1Kwizq+Z1TGrasKuG4XN/9yUfpbqOlmELeIeH1dMO6TdcduxssH78IDYZxP7f8K9lALG vcRg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741983532; x=1742588332; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=KshCsw9BYsb+Zoj5mw5r3bskLU+1QkHFPw59rvGBRbg=; b=mG18d5vYmykj++d9EB13fThvulK6n1kLVLWUdlqRGGylzsZoC7hL71sksu/yIQ4FsQ bV1jl+Spu3c0xaoziq0O3UiHH022A8GhInlOcmwJxG3XIcSMmWhjqNkg5grO9GI3Kc0v lZKIA95QlGX1fH3E0Rmtgj1z6eivx6FCNLX3C9MenlNuc00RfVdSK8lVi63EdEBJYxn8 JaZtimpt3m+FTibnxprntP2vKJYhLJ4hYx/f0Qsy9jHY6f1trwv0C8bWC0bKbscZM5aO xtUWXv48/ATPTt8rH/bTbwD91sqyRVkmrdoOS+aMLDLQpDg2auPKL5+4fakhtFgK0CNn q6/A== X-Gm-Message-State: AOJu0YwaaYXctrgauL8LN0x1WIUUqyuFZ27TbzNEsu/bvnNtWtp8+W09 rWYHxh2KgKi0sVAbuDWN2mseWEJclz8Xd2lj6AUYCvQkZHx04gos4fKEEKx/Fd1IhM4M9jhmZsm qGxU= X-Gm-Gg: ASbGncsbvOQ3ue60KCsr5keipBXRoINIwGqkgZsVSRGREq58MEUQpIAlFYMH0B9wNhR hxzdzuOnCz8aTsBgQx9DpuUMCAnJvcSJTDj8xFusgEbgVJ8bWYWXeFOg1szyUdij/5RK0Kj1HL4 PU9eNM9FrlqnqM/rip0RzW4TdsFG2P+ZYm/28H/g9q6ofvjynK8dJqIV5wxuIYFH4CTBdWShjEe R5rywDk64JRybN53Z/aZ4rzCwoqtQ0YM+9WB3wv8Zvd2rJO0ylxDXqX9FRDJZZe22GhRtPP/iPl OhNCy+wClvHBWHtCNHpFnsDNkNfRqw3HBVh7OXM7/ligd70i3glVcQuahWmBereA4WpRtGYmwFO agqfQaAm5KnCshPUl X-Google-Smtp-Source: AGHT+IHHhzSJKbyAYFAFi4GVap+ADbRDu048EAh1c+tP4EQqYjHfGJ9dhxzldLyQ248WXeKvWqlKAQ== X-Received: by 2002:a05:620a:4726:b0:7c3:c695:156 with SMTP id af79cd13be357-7c57c7d29a3mr428971985a.16.1741983532125; Fri, 14 Mar 2025 13:18:52 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with UTF8SMTPSA id af79cd13be357-7c573c4f50fsm294636085a.12.2025.03.14.13.18.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 14 Mar 2025 13:18:51 -0700 (PDT) Date: Fri, 14 Mar 2025 16:18:50 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v4 10/13] ewah: implement `struct ewah_or_iterator` Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: While individual bitmap layers store different commit, type-level, and pseudo-merge bitmaps, only the top-most layer is used to compute reachability traversals. Many functions which implement the aforementioned traversal rely on enumerating the results according to the type-level bitmaps, and so would benefit from a conceptual type-level bitmap that spans multiple layers. Implement `struct ewah_or_iterator` which is capable of enumerating multiple EWAH bitmaps at once, and OR-ing the results together. When initialized with, for example, all of the commit type bitmaps from each layer, callers can pretend as if they are enumerating a large type-level bitmap which contains the commits from *all* bitmap layers. There are a couple of alternative approaches which were considered: - Decompress each EWAH bitmap and OR them together, enumerating a single (non-EWAH) bitmap. This would work, but has the disadvantage of decompressing a potentially large bitmap, which may not be necessary if the caller does not wish to read all of it. - Recursively call bitmap internal functions, reusing the "result" and "haves" bitmap from the top-most layer. This approach resembles the original implementation of this feature, but is inefficient in that it both (a) requires significant refactoring to implement, and (b) enumerates large sections of later bitmaps which are all zeros (as they pertain to objects in earlier layers). (b) is not so bad in and of itself, but can cause significant slow-downs when combined with expensive loop bodies. This approach (enumerating an OR'd together version of all of the type-level bitmaps from each layer) produces a significantly more straightforward implementation with significantly less refactoring required in order to make it work. Signed-off-by: Taylor Blau --- ewah/ewah_bitmap.c | 33 +++++++++++++++++++++++++++++++++ ewah/ewok.h | 12 ++++++++++++ 2 files changed, 45 insertions(+) diff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c index 67f8f588e0..e92341b8fa 100644 --- a/ewah/ewah_bitmap.c +++ b/ewah/ewah_bitmap.c @@ -371,6 +371,39 @@ void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent) read_new_rlw(it); } +void ewah_or_iterator_init(struct ewah_or_iterator *it, + struct ewah_bitmap **parents, size_t nr) +{ + size_t i; + + memset(it, 0, sizeof(*it)); + + ALLOC_ARRAY(it->its, nr); + for (i = 0; i < nr; i++) + ewah_iterator_init(&it->its[it->nr++], parents[i]); +} + +int ewah_or_iterator_next(eword_t *next, struct ewah_or_iterator *it) +{ + eword_t buf, out = 0; + size_t i; + int ret = 0; + + for (i = 0; i < it->nr; i++) + if (ewah_iterator_next(&buf, &it->its[i])) { + out |= buf; + ret = 1; + } + + *next = out; + return ret; +} + +void ewah_or_iterator_free(struct ewah_or_iterator *it) +{ + free(it->its); +} + void ewah_xor( struct ewah_bitmap *ewah_i, struct ewah_bitmap *ewah_j, diff --git a/ewah/ewok.h b/ewah/ewok.h index 5e357e2493..4b70641045 100644 --- a/ewah/ewok.h +++ b/ewah/ewok.h @@ -148,6 +148,18 @@ void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent); */ int ewah_iterator_next(eword_t *next, struct ewah_iterator *it); +struct ewah_or_iterator { + struct ewah_iterator *its; + size_t nr; +}; + +void ewah_or_iterator_init(struct ewah_or_iterator *it, + struct ewah_bitmap **parents, size_t nr); + +int ewah_or_iterator_next(eword_t *next, struct ewah_or_iterator *it); + +void ewah_or_iterator_free(struct ewah_or_iterator *it); + void ewah_xor( struct ewah_bitmap *ewah_i, struct ewah_bitmap *ewah_j, From patchwork Fri Mar 14 20:18:53 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14017399 Received: from mail-qk1-f170.google.com (mail-qk1-f170.google.com [209.85.222.170]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 798862066DB for ; Fri, 14 Mar 2025 20:18:56 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.222.170 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983538; cv=none; b=lBWuaptWzBTEBZIaiRxffARWdcFlf2BVb+KB7bhw0Pl+lc6LCjlw1PgwCrjxhLn5f5nIPuV2GO5q2g7vofDFX9c4zOqSJzEtC07imh3kINa7PWJMzCByLSdXAL1EJGD7QujeXR0pKQ6IoNFSruczicXrIo6LW1PvUxPGFjqMydQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983538; c=relaxed/simple; bh=J0/YefXaYWBkw+PcGEkx1pOjFrjKfBDFigogdDtW2Tc=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=cMm752bqqpLAG54WTiEPhZ+/ww5iFXyJX4JyBH9Ps4VmiNjXIpADOyIkiTg9maGBaBw6q4adMVabXZlxAfn+XgD6zrPqGdJztXKvpSQUvyKVfrpGgEAVt4+fL+FlxtGY7fe3YblUWwrV5+RftXnLQxNS8vQ9Fom9t64pINRPZMY= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=pass smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=TV82YcU/; arc=none smtp.client-ip=209.85.222.170 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="TV82YcU/" Received: by mail-qk1-f170.google.com with SMTP id af79cd13be357-7c542ffec37so255012285a.2 for ; Fri, 14 Mar 2025 13:18:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1741983535; x=1742588335; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=EmzxNlob+PFgER2n2B7XGmwg5I58P/R5fpgwzx815nc=; b=TV82YcU/GiNGu6Czsuft2ztRRchw9ZGNbFCyf+G9Lly5h+trM+BYwE2OS3HlWaJAfK H2zDblJnkt2J6ap4yv2WOMZo4BZHhHVllUc6zIqzeesIIgPAXow/afJfrRLQno2xLIns /YzXB8iFSvoEDOupAdF0oLOB+wsyCluwQ61reDOIq3J7KUj5nyRcKGA8qbDM7NEgHPWn dWmlj4VXXQYkujUPk1txliUpxjch7ABoKEWRMMHIjsQomRQUBFdwcB6jcMcpEFIIerjl t7upxaUelvoxByToaHWpgBJRRp04roZHKFADNwVf5C2aRPgQvHVHdDwrb1wIQnZF35Pi 876w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741983535; x=1742588335; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=EmzxNlob+PFgER2n2B7XGmwg5I58P/R5fpgwzx815nc=; b=Ub9kfSwW6xS5z1gwblYb5uhSJA0Y+rFzMqM8rWAoWafCzROqn1FJWD+2wAiuneqWbe 2XOguwm1ztQk7YRiBjOQT1U8RaEhUFOo6G6KUUKSIRo9Hhve2fN96aIJ6vPShEpEcLZJ utNoAaeuCJvoFhiaBQTHKBMrtoK0o+oRNa18fH6QKhyPnLHpn9OYO2g8W7eSkgXdVyYA Rgk/XYd0nv4x3Cqxbb1QJ08Dv3+y2vW/1UBxnn5UJ04BJn2m97w7UFAfRXWrGT/OU3Jr HuMKQp66ZlvPaZs4t5bBHCq0yF2jzM/HvnNWOaKlY92CLqT7aQX80NCcPCFjzzMk8wcJ 6cEw== X-Gm-Message-State: AOJu0YyF6FQSEkC6/bHUaI3sQ+Y3tL8QcspkCZQZzNV6MHsVNKKllS9U 7lZva7IH0jcVVxA8NmAhvdLHBjBiNbgcNzfJJj6jqDreS2Y72cefeq5gA4yTLPIU+Bam5jEVAD2 qFAs= X-Gm-Gg: ASbGncsXNTi+HjwkKKuN2wvfV8j2say/5ueNADcSR45Be4LclJDZv67DydaZMJSdNvb E0uDoHlgW1sNUgTErWTUBVt3k13Jgmh4YlhEAhLdmApIy1kraVc4eM41oT2xbC2eMQ9UzGzX/eS B+UnCdm8cwDmyABBXo7Hm9C39UOz1shlr+sp68zFm5u++dsrmSiypfIbcgQ4MeqoV0uGLSWTpDa wnMow+IaA5UvKGzlZBJTwYPKyQN3u51c8UjVkhEcfofcxZu1rjAijh+FyHxUYHfGfM+2YcbyNDe QWQWl9UZZifBxNGGD3pPRU1Kh3Q+9vsV2AmP/3qznHw3YQxdg21uzSwa43zn3nprUZcjL5AFaua UpokEhD8ZhajEcoh1 X-Google-Smtp-Source: AGHT+IEO1Bslg/4xqUehbqWx+b7xclr4RNYylN+dRjL/aGGAsJZZttK2Sy4WILD5QMXWzivB5bBRwA== X-Received: by 2002:a05:620a:1a88:b0:7c5:4788:a152 with SMTP id af79cd13be357-7c57c9191d0mr651156285a.49.1741983535129; Fri, 14 Mar 2025 13:18:55 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with UTF8SMTPSA id af79cd13be357-7c573c7853fsm294471485a.43.2025.03.14.13.18.54 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 14 Mar 2025 13:18:54 -0700 (PDT) Date: Fri, 14 Mar 2025 16:18:53 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v4 11/13] pack-bitmap.c: keep track of each layer's type bitmaps Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Prepare for reading the type-level bitmaps from previous bitmap layers by maintaining an array for each type, where each element in that type's array corresponds to one layer's bitmap for that type. These fields will be used in a later commit to instantiate the 'struct ewah_or_iterator' for each type. Signed-off-by: Taylor Blau --- pack-bitmap.c | 58 +++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 54 insertions(+), 4 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 00acf5ec73..3517972892 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -81,6 +81,24 @@ struct bitmap_index { struct ewah_bitmap *blobs; struct ewah_bitmap *tags; + /* + * Type index arrays when this bitmap is associated with an + * incremental multi-pack index chain. + * + * If n is the number of unique layers in the MIDX chain, then + * commits_all[n-1] is this structs 'commits' field, + * commits_all[n-2] is the commits field of this bitmap's + * 'base', and so on. + * + * When either associated either with a non-incremental MIDX, or + * a single packfile, these arrays each contain a single + * element. + */ + struct ewah_bitmap **commits_all; + struct ewah_bitmap **trees_all; + struct ewah_bitmap **blobs_all; + struct ewah_bitmap **tags_all; + /* Map from object ID -> `stored_bitmap` for all the bitmapped commits */ kh_oid_map_t *bitmaps; @@ -581,7 +599,32 @@ static int load_reverse_index(struct repository *r, struct bitmap_index *bitmap_ return load_pack_revindex(r, bitmap_git->pack); } -static int load_bitmap(struct repository *r, struct bitmap_index *bitmap_git) +static void load_all_type_bitmaps(struct bitmap_index *bitmap_git) +{ + struct bitmap_index *curr = bitmap_git; + size_t i = bitmap_git->base_nr; + + ALLOC_ARRAY(bitmap_git->commits_all, bitmap_git->base_nr + 1); + ALLOC_ARRAY(bitmap_git->trees_all, bitmap_git->base_nr + 1); + ALLOC_ARRAY(bitmap_git->blobs_all, bitmap_git->base_nr + 1); + ALLOC_ARRAY(bitmap_git->tags_all, bitmap_git->base_nr + 1); + + while (curr) { + bitmap_git->commits_all[i] = curr->commits; + bitmap_git->trees_all[i] = curr->trees; + bitmap_git->blobs_all[i] = curr->blobs; + bitmap_git->tags_all[i] = curr->tags; + + curr = curr->base; + if (curr && !i) + BUG("unexpected number of bitmap layers, expected %"PRIu32, + bitmap_git->base_nr + 1); + i -= 1; + } +} + +static int load_bitmap(struct repository *r, struct bitmap_index *bitmap_git, + int recursing) { assert(bitmap_git->map); @@ -603,10 +646,13 @@ static int load_bitmap(struct repository *r, struct bitmap_index *bitmap_git) if (bitmap_git->base) { if (!bitmap_is_midx(bitmap_git)) BUG("non-MIDX bitmap has non-NULL base bitmap index"); - if (load_bitmap(r, bitmap_git->base) < 0) + if (load_bitmap(r, bitmap_git->base, 1) < 0) goto failed; } + if (!recursing) + load_all_type_bitmaps(bitmap_git); + return 0; failed: @@ -682,7 +728,7 @@ struct bitmap_index *prepare_bitmap_git(struct repository *r) { struct bitmap_index *bitmap_git = xcalloc(1, sizeof(*bitmap_git)); - if (!open_bitmap(r, bitmap_git) && !load_bitmap(r, bitmap_git)) + if (!open_bitmap(r, bitmap_git) && !load_bitmap(r, bitmap_git, 0)) return bitmap_git; free_bitmap_index(bitmap_git); @@ -2050,7 +2096,7 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs, * from disk. this is the point of no return; after this the rev_list * becomes invalidated and we must perform the revwalk through bitmaps */ - if (load_bitmap(revs->repo, bitmap_git) < 0) + if (load_bitmap(revs->repo, bitmap_git, 0) < 0) goto cleanup; if (!use_boundary_traversal) @@ -2983,6 +3029,10 @@ void free_bitmap_index(struct bitmap_index *b) ewah_pool_free(b->trees); ewah_pool_free(b->blobs); ewah_pool_free(b->tags); + free(b->commits_all); + free(b->trees_all); + free(b->blobs_all); + free(b->tags_all); if (b->bitmaps) { struct stored_bitmap *sb; kh_foreach_value(b->bitmaps, sb, { From patchwork Fri Mar 14 20:18:56 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14017400 Received: from mail-qt1-f182.google.com (mail-qt1-f182.google.com [209.85.160.182]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 9430D2066E5 for ; Fri, 14 Mar 2025 20:18:59 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.160.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983541; cv=none; b=QbQZPrMGZussW81gyz9GPCZrY9iRt+dKyXoyLdy/IhiQ55pyK0H9/XJ24pAvmrheulNnsMGEt4QQ0cKhncnca3RszLmVTHg7y6ezHFj9HztaqydJxaeCVyRi+0zS25BfGMNqZ5JHbS6duD9clarI2p9mxq3WNB8ggmyucECbsY8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983541; c=relaxed/simple; bh=/bu6KGzgR8fHXsbbS4P3fTttwzBY9K58GIjhsPqtaU0=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=jPLWlAtVhbE7eVTRg+fD7fEbQEzZt7J0GPv9sNyFQCH85uYX/df5ftNUywpbog+VZJAFh81bOCsmu8zCHcmQ2HKqF/s2cDNcmqRyK2bM8VlZtgh0jhpR3c1fPOHI6DnZ4NRUsCPDVSXAvXk1WOV4YzPM1f6CEHSkSNJewU+GX+Q= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=pass smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=iVmVQMTo; arc=none smtp.client-ip=209.85.160.182 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="iVmVQMTo" Received: by mail-qt1-f182.google.com with SMTP id d75a77b69052e-476a720e806so22307841cf.0 for ; Fri, 14 Mar 2025 13:18:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1741983538; x=1742588338; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=aQyAqbdmyme6Qp/tL9FNrqeA6P9nUXQjtQWkQCnZUsQ=; b=iVmVQMTo5Rur2qTTTRq/mReq97AS4guifHcP/qY685redzIXDNd5Kk6xdcgx6+V9bx 9WcAhkavFl2ePlEznGVKbtuWJGwtnO7IQ22xQ7mjRkJ9bZryuLo0eCx9DHa3LbVQupVZ xdi+hRwB/MYBHJjvh84JyP33lalPjNL85BmxD2A6LeCHUkd+Lhc+1IY7oKO45DL1DBAY TimLaLe7BmA/NPwKWKGBTuyJoB9vFOS2lpUug2nPmK9zOGxo5W6NJIp1SpdkXwKxn5Ss /86fpqy2rs2N5g7ZY03aq4gguyjq9LEMG8lFwS9ppiPGFJnri41uyiJEG25AYAQG80E4 Tx/A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741983538; x=1742588338; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=aQyAqbdmyme6Qp/tL9FNrqeA6P9nUXQjtQWkQCnZUsQ=; b=hrMKSta8dmGM3ujBtfRSnqQPqwM7Q2p7C0VHS8vyL5k4VWozgCQpDTWRknTXv7GgRO WugOkhfWdvveaNAU37EZvD/LeClwQoU0rZzUar2130pOUHqWFSNiMV677VyETymzobMU Ww0VhN6OK785XfUF1okGV2Rf9f9b/k2ZVU4Rgz5ULcS7+B7GETie7ozEr3eFxM97p3+M +gwIm1iKAzprSl4u26Wol9sBrbYjicgd6EELHypWN74ibTliip/nCmBo6zVfRm7oY7RY AosiE+rMaTrOueJikLYCHvVq4V3DjtxUIEJEPcqJAvVea8RvDc2hlxUD6rFRV+IywPC1 FVpQ== X-Gm-Message-State: AOJu0Yyg5Nj5AeSOtT7MSWiAEmpQBic59buzO4A7fofZB03ciQbrBoVU TvzwiJAdThvxymdLU61ofiI8j1O4Iwp2sOFHg4srMLIC4MCalFIGzqk6Wvt0poC9ogBfKpgK9vH ld7Q= X-Gm-Gg: ASbGncvRDG+YjPHLpeOrVpjBvjJVTXe+q8HbghAsxik8Uc5/Uz/sCvHz1F6sIS2T7Rn kV+hTUfMNd6hapEX8vdvJ/ufGklKQz33ktNwPVB06wPuHq0Ae8uJclpNY58BIaxnajT5FY+/6NY sNnPVrxbBGOMp6oAQe7+k9C+6xgg9YbpIEoGrKLC1QCD/Vf0BSR2AFODIirQvl7jm/y9fRpSgtk foslIa6cWtBGbJ5B7y0tLpXJVTyBCN5op5pt+IFTlD8Grm6rRz9loySWxV7FkbltyrYBlJI4SNJ H4GLQVv38uGgQyWByHSSBVy7C6+zhWaTAX2XfANTAzDQjruBhelm546U5QquCyQYXpzc5Vce8Ot E/iC3lKPqryHEmJCIn5/6Eo0DfIU= X-Google-Smtp-Source: AGHT+IHvCrSQO307EtKOR/giHS5+84aUWBZOggS+lxuQ6LXNdU1CsbCLSuiGG+f7VE7npxuYP8G2yQ== X-Received: by 2002:a05:622a:178c:b0:476:790c:73a7 with SMTP id d75a77b69052e-476c81c3807mr50601361cf.40.1741983538277; Fri, 14 Mar 2025 13:18:58 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with UTF8SMTPSA id d75a77b69052e-476bb6370aasm27057511cf.20.2025.03.14.13.18.57 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 14 Mar 2025 13:18:58 -0700 (PDT) Date: Fri, 14 Mar 2025 16:18:56 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v4 12/13] pack-bitmap.c: use `ewah_or_iterator` for type bitmap iterators Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Now that we have initialized arrays for each bitmap layer's type bitmaps in the previous commit, adjust existing callers to use them in preparation for multi-layered bitmaps. Signed-off-by: Taylor Blau --- pack-bitmap.c | 42 +++++++++++++++++++++++++++--------------- 1 file changed, 27 insertions(+), 15 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 3517972892..5e6d4ace58 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -1629,25 +1629,29 @@ static void show_extended_objects(struct bitmap_index *bitmap_git, } } -static void init_type_iterator(struct ewah_iterator *it, +static void init_type_iterator(struct ewah_or_iterator *it, struct bitmap_index *bitmap_git, enum object_type type) { switch (type) { case OBJ_COMMIT: - ewah_iterator_init(it, bitmap_git->commits); + ewah_or_iterator_init(it, bitmap_git->commits_all, + bitmap_git->base_nr + 1); break; case OBJ_TREE: - ewah_iterator_init(it, bitmap_git->trees); + ewah_or_iterator_init(it, bitmap_git->trees_all, + bitmap_git->base_nr + 1); break; case OBJ_BLOB: - ewah_iterator_init(it, bitmap_git->blobs); + ewah_or_iterator_init(it, bitmap_git->blobs_all, + bitmap_git->base_nr + 1); break; case OBJ_TAG: - ewah_iterator_init(it, bitmap_git->tags); + ewah_or_iterator_init(it, bitmap_git->tags_all, + bitmap_git->base_nr + 1); break; default: @@ -1664,7 +1668,7 @@ static void show_objects_for_type( size_t i = 0; uint32_t offset; - struct ewah_iterator it; + struct ewah_or_iterator it; eword_t filter; struct bitmap *objects = bitmap_git->result; @@ -1672,7 +1676,7 @@ static void show_objects_for_type( init_type_iterator(&it, bitmap_git, object_type); for (i = 0; i < objects->word_alloc && - ewah_iterator_next(&filter, &it); i++) { + ewah_or_iterator_next(&filter, &it); i++) { eword_t word = objects->words[i] & filter; size_t pos = (i * BITS_IN_EWORD); @@ -1714,6 +1718,8 @@ static void show_objects_for_type( show_reach(&oid, object_type, 0, hash, pack, ofs); } } + + ewah_or_iterator_free(&it); } static int in_bitmapped_pack(struct bitmap_index *bitmap_git, @@ -1765,7 +1771,7 @@ static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git, { struct eindex *eindex = &bitmap_git->ext_index; struct bitmap *tips; - struct ewah_iterator it; + struct ewah_or_iterator it; eword_t mask; uint32_t i; @@ -1782,7 +1788,7 @@ static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git, * packfile. */ for (i = 0, init_type_iterator(&it, bitmap_git, type); - i < to_filter->word_alloc && ewah_iterator_next(&mask, &it); + i < to_filter->word_alloc && ewah_or_iterator_next(&mask, &it); i++) { if (i < tips->word_alloc) mask &= ~tips->words[i]; @@ -1802,6 +1808,7 @@ static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git, bitmap_unset(to_filter, pos); } + ewah_or_iterator_free(&it); bitmap_free(tips); } @@ -1861,14 +1868,14 @@ static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git, { struct eindex *eindex = &bitmap_git->ext_index; struct bitmap *tips; - struct ewah_iterator it; + struct ewah_or_iterator it; eword_t mask; uint32_t i; tips = find_tip_objects(bitmap_git, tip_objects, OBJ_BLOB); for (i = 0, init_type_iterator(&it, bitmap_git, OBJ_BLOB); - i < to_filter->word_alloc && ewah_iterator_next(&mask, &it); + i < to_filter->word_alloc && ewah_or_iterator_next(&mask, &it); i++) { eword_t word = to_filter->words[i] & mask; unsigned offset; @@ -1896,6 +1903,7 @@ static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git, bitmap_unset(to_filter, pos); } + ewah_or_iterator_free(&it); bitmap_free(tips); } @@ -2527,12 +2535,12 @@ static uint32_t count_object_type(struct bitmap_index *bitmap_git, struct eindex *eindex = &bitmap_git->ext_index; uint32_t i = 0, count = 0; - struct ewah_iterator it; + struct ewah_or_iterator it; eword_t filter; init_type_iterator(&it, bitmap_git, type); - while (i < objects->word_alloc && ewah_iterator_next(&filter, &it)) { + while (i < objects->word_alloc && ewah_or_iterator_next(&filter, &it)) { eword_t word = objects->words[i++] & filter; count += ewah_bit_popcount64(word); } @@ -2544,6 +2552,8 @@ static uint32_t count_object_type(struct bitmap_index *bitmap_git, count++; } + ewah_or_iterator_free(&it); + return count; } @@ -3076,13 +3086,13 @@ static off_t get_disk_usage_for_type(struct bitmap_index *bitmap_git, { struct bitmap *result = bitmap_git->result; off_t total = 0; - struct ewah_iterator it; + struct ewah_or_iterator it; eword_t filter; size_t i; init_type_iterator(&it, bitmap_git, object_type); for (i = 0; i < result->word_alloc && - ewah_iterator_next(&filter, &it); i++) { + ewah_or_iterator_next(&filter, &it); i++) { eword_t word = result->words[i] & filter; size_t base = (i * BITS_IN_EWORD); unsigned offset; @@ -3123,6 +3133,8 @@ static off_t get_disk_usage_for_type(struct bitmap_index *bitmap_git, } } + ewah_or_iterator_free(&it); + return total; } From patchwork Fri Mar 14 20:19:00 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14017401 Received: from mail-qv1-f53.google.com (mail-qv1-f53.google.com [209.85.219.53]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id EE1FA2066F3 for ; Fri, 14 Mar 2025 20:19:02 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.53 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983545; cv=none; b=ZZcJltJ4MEpD55L3004afh1N312IoPKqR4DCpTbLRhjg21h2phqDI8Za2xx8RlkI99opn+KGPlKtarNWMer6zF+0hl5UWFmk2y89uDos80f1hPb/a2xnPyA65Mg+KV284VxOZ1Eu8mfksQKW+/yPJyvL/OrsStK7vl9m05MVGz0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741983545; c=relaxed/simple; bh=ZYx2gByTblTw+dsIsojZeBW7tU40aII3gaiJu9Xgy3E=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=VPTDlXLN58x/nnPaB7R3hwApWVCIye4jt0ah5HGzpbyqfXxkBmnZrQuoA+1SglxPOdIl4RT3QC9CL43f6j4WnIZGmjsmJNeRYpHk7FjoK/lfGH097s7NGaEHFY5KVklC+Kz3mQ5elMTdhXJ5GPIeIMu/Rvq0VyfWsTEsXCyh1MA= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=pass smtp.mailfrom=ttaylorr.com; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b=zECCoToT; arc=none smtp.client-ip=209.85.219.53 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20230601.gappssmtp.com header.i=@ttaylorr-com.20230601.gappssmtp.com header.b="zECCoToT" Received: by mail-qv1-f53.google.com with SMTP id 6a1803df08f44-6e8f4c50a8fso22122636d6.1 for ; Fri, 14 Mar 2025 13:19:02 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1741983541; x=1742588341; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=Yrdhz+xcjCDmVtdwxSkwlSAeLnoIXiDdRTu+0Lr7nvw=; b=zECCoToTIR/aNETSdye7Yuz5cnXPIWWzm0dVhZhnRfNmeTg5eW3lqC8riDt8EXdVe9 oH3pqW6kMahY1Z9SlTCX34g275gw/DY9iPv16XosUkC9+/CCw4HjfwtRSykRbWs7gys6 9JoF61oCArpoyMmx2q1SdmehCr5yRm8tDpV+3ZNsJ+ZEorE0CKECOecGRFgQ+SuINq1E Mabfxp8OhiHZ3qfLKzW1GiaGXA5PqlfqUh2lNYjuwnr39+llpASUk2yTkVPhmJdLSKgW vkw3Nk9mcG8LqS60GiCx2wrZYmpdkeQRtzaQ5XV4SxeL2Zaq9lW2BVpHLGIJl/XFUrqa MpJQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1741983541; x=1742588341; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=Yrdhz+xcjCDmVtdwxSkwlSAeLnoIXiDdRTu+0Lr7nvw=; b=HWpUvclrkuVi+9piJ6ThauA1axKALMvO8CIYL4XmklPx9dcbsShGOpvT+ebOwdVcbv 0yRP+eS2Ct1mxXaJCBEodHFRk7H7/gmqupUpGkMGOUkPdO+f7hTB3qrMJfPetgIz23vp pnFkLlJNhafPR/O+TRUkBbVWmV2LjsVCRPMzg67qd2pKgTq2EIFEIe9J5gek7qaKonSg ebbgnqB74wiRNj7P6EUcpNFN1fYB+VvX3K/XJkFf8fCT7fkSgMb1UufJc3pekwoQ4oOC eybjoKxZFgTTVL1Qxip8V3U/OC8jlsrgxX+xj4MuI4A3Uwmm/EnPPQCxDZ3HiUlnLXei 3aBA== X-Gm-Message-State: AOJu0YxMhoT6ZH7SKsS2WGgVXB3A0Go5LLYVJhqR8uBD68ojkwuu0Guc 6NmymnmN5lWkigFaXFJ3hOhu++keTYaJ1dqdlaIZ+zMdKM0N765TGvSQOelUPTXaqEO02ApAfwf 1HEg= X-Gm-Gg: ASbGncv7T1dyV3D7i0/zVQ067Co+eXRzAbDBYxcSKKw5alTSM4pi2xTLbflAmq6svyC RVak5vOfGNByo2nJUxFckZO1XIeaTwtzWdrNLysFS3MkeB8dslzaCCSm9sJS/Pbgg93MMOi2kfJ JFRufKZsfrKXlwt2tHSx4X/V7JeXUE4YDS1LuITUVIoowkWlFGMuqKoo82hTRMS3O+p+5Ab/55g uAzpBmZvRgX2U9/M9xJHC0vybANvk5dWXuhM6p1P76Oarf8HJ1qHCc7f5uMAvOke93LZbeZD4XA n3KjhxCUKWOAiWQWza54q2XKWrAp47jKQjAr0I35PVY6L4IpwXweDUVMtCqvFKxGv2tVP0g13m9 XceXCC7BjIXwkpX6G X-Google-Smtp-Source: AGHT+IGifYAGE9z++QOmRYHQEg5j/DqSTIH3PdTSiJs1YaDPAHNCNLjFqCtvU5nSJoxYUhpJxDAfvQ== X-Received: by 2002:ad4:5f4f:0:b0:6e8:9d00:3d71 with SMTP id 6a1803df08f44-6eaeaa2389fmr56486156d6.21.1741983541411; Fri, 14 Mar 2025 13:19:01 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with UTF8SMTPSA id 6a1803df08f44-6eade209369sm27880036d6.2.2025.03.14.13.19.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 14 Mar 2025 13:19:01 -0700 (PDT) Date: Fri, 14 Mar 2025 16:19:00 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v4 13/13] midx: implement writing incremental MIDX bitmaps Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Now that the pack-bitmap machinery has learned how to read and interact with an incremental MIDX bitmap, teach the pack-bitmap-write.c machinery (and relevant callers from within the MIDX machinery) to write such bitmaps. The details for doing so are mostly straightforward. The main changes are as follows: - find_object_pos() now makes use of an extra MIDX parameter which is used to locate the bit positions of objects which are from previous layers (and thus do not exist in the current layer's pack_order field). (Note also that the pack_order field is moved into struct write_midx_context to further simplify the callers for write_midx_bitmap()). - bitmap_writer_build_type_index() first determines how many objects precede the current bitmap layer and offsets the bits it sets in each respective type-level bitmap by that amount so they can be OR'd together. Signed-off-by: Taylor Blau --- builtin/pack-objects.c | 3 +- ewah/ewah_bitmap.c | 2 +- ewah/ewok.h | 2 +- midx-write.c | 57 +++++++++++------ pack-bitmap-write.c | 65 ++++++++++++++----- pack-bitmap.c | 10 +-- pack-bitmap.h | 4 +- t/t5334-incremental-multi-pack-index.sh | 84 +++++++++++++++++++++++++ 8 files changed, 183 insertions(+), 44 deletions(-) diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c index 58a9b16126..a7e4bb7904 100644 --- a/builtin/pack-objects.c +++ b/builtin/pack-objects.c @@ -1397,7 +1397,8 @@ static void write_pack_file(void) if (write_bitmap_index) { bitmap_writer_init(&bitmap_writer, - the_repository, &to_pack); + the_repository, &to_pack, + NULL); bitmap_writer_set_checksum(&bitmap_writer, hash); bitmap_writer_build_type_index(&bitmap_writer, written_list); diff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c index e92341b8fa..056c410efb 100644 --- a/ewah/ewah_bitmap.c +++ b/ewah/ewah_bitmap.c @@ -399,7 +399,7 @@ int ewah_or_iterator_next(eword_t *next, struct ewah_or_iterator *it) return ret; } -void ewah_or_iterator_free(struct ewah_or_iterator *it) +void ewah_or_iterator_release(struct ewah_or_iterator *it) { free(it->its); } diff --git a/ewah/ewok.h b/ewah/ewok.h index 4b70641045..c29d354236 100644 --- a/ewah/ewok.h +++ b/ewah/ewok.h @@ -158,7 +158,7 @@ void ewah_or_iterator_init(struct ewah_or_iterator *it, int ewah_or_iterator_next(eword_t *next, struct ewah_or_iterator *it); -void ewah_or_iterator_free(struct ewah_or_iterator *it); +void ewah_or_iterator_release(struct ewah_or_iterator *it); void ewah_xor( struct ewah_bitmap *ewah_i, diff --git a/midx-write.c b/midx-write.c index 48d6558253..0897cbd829 100644 --- a/midx-write.c +++ b/midx-write.c @@ -647,16 +647,22 @@ static uint32_t *midx_pack_order(struct write_midx_context *ctx) return pack_order; } -static void write_midx_reverse_index(char *midx_name, unsigned char *midx_hash, - struct write_midx_context *ctx) +static void write_midx_reverse_index(struct write_midx_context *ctx, + const char *object_dir, + unsigned char *midx_hash) { struct strbuf buf = STRBUF_INIT; char *tmp_file; trace2_region_enter("midx", "write_midx_reverse_index", ctx->repo); - strbuf_addf(&buf, "%s-%s.rev", midx_name, hash_to_hex_algop(midx_hash, - ctx->repo->hash_algo)); + if (ctx->incremental) + get_split_midx_filename_ext(ctx->repo->hash_algo, &buf, + object_dir, midx_hash, + MIDX_EXT_REV); + else + get_midx_filename_ext(ctx->repo->hash_algo, &buf, object_dir, + midx_hash, MIDX_EXT_REV); tmp_file = write_rev_file_order(ctx->repo->hash_algo, NULL, ctx->pack_order, ctx->entries_nr, midx_hash, WRITE_REV); @@ -829,22 +835,29 @@ static struct commit **find_commits_for_midx_bitmap(uint32_t *indexed_commits_nr return cb.commits; } -static int write_midx_bitmap(struct repository *r, const char *midx_name, +static int write_midx_bitmap(struct write_midx_context *ctx, + const char *object_dir, const unsigned char *midx_hash, struct packing_data *pdata, struct commit **commits, uint32_t commits_nr, - uint32_t *pack_order, unsigned flags) { int ret, i; uint16_t options = 0; struct bitmap_writer writer; struct pack_idx_entry **index; - char *bitmap_name = xstrfmt("%s-%s.bitmap", midx_name, - hash_to_hex_algop(midx_hash, r->hash_algo)); + struct strbuf bitmap_name = STRBUF_INIT; - trace2_region_enter("midx", "write_midx_bitmap", r); + trace2_region_enter("midx", "write_midx_bitmap", ctx->repo); + + if (ctx->incremental) + get_split_midx_filename_ext(ctx->repo->hash_algo, &bitmap_name, + object_dir, midx_hash, + MIDX_EXT_BITMAP); + else + get_midx_filename_ext(ctx->repo->hash_algo, &bitmap_name, + object_dir, midx_hash, MIDX_EXT_BITMAP); if (flags & MIDX_WRITE_BITMAP_HASH_CACHE) options |= BITMAP_OPT_HASH_CACHE; @@ -861,7 +874,8 @@ static int write_midx_bitmap(struct repository *r, const char *midx_name, for (i = 0; i < pdata->nr_objects; i++) index[i] = &pdata->objects[i].idx; - bitmap_writer_init(&writer, r, pdata); + bitmap_writer_init(&writer, ctx->repo, pdata, + ctx->incremental ? ctx->base_midx : NULL); bitmap_writer_show_progress(&writer, flags & MIDX_PROGRESS); bitmap_writer_build_type_index(&writer, index); @@ -879,7 +893,7 @@ static int write_midx_bitmap(struct repository *r, const char *midx_name, * bitmap_writer_finish(). */ for (i = 0; i < pdata->nr_objects; i++) - index[pack_order[i]] = &pdata->objects[i].idx; + index[ctx->pack_order[i]] = &pdata->objects[i].idx; bitmap_writer_select_commits(&writer, commits, commits_nr); ret = bitmap_writer_build(&writer); @@ -887,14 +901,14 @@ static int write_midx_bitmap(struct repository *r, const char *midx_name, goto cleanup; bitmap_writer_set_checksum(&writer, midx_hash); - bitmap_writer_finish(&writer, index, bitmap_name, options); + bitmap_writer_finish(&writer, index, bitmap_name.buf, options); cleanup: free(index); - free(bitmap_name); + strbuf_release(&bitmap_name); bitmap_writer_free(&writer); - trace2_region_leave("midx", "write_midx_bitmap", r); + trace2_region_leave("midx", "write_midx_bitmap", ctx->repo); return ret; } @@ -1077,8 +1091,6 @@ static int write_midx_internal(struct repository *r, const char *object_dir, ctx.repo = r; ctx.incremental = !!(flags & MIDX_WRITE_INCREMENTAL); - if (ctx.incremental && (flags & MIDX_WRITE_BITMAP)) - die(_("cannot write incremental MIDX with bitmap")); if (ctx.incremental) strbuf_addf(&midx_name, @@ -1119,6 +1131,13 @@ static int write_midx_internal(struct repository *r, const char *object_dir, if (ctx.incremental) { struct multi_pack_index *m = ctx.base_midx; while (m) { + if (flags & MIDX_WRITE_BITMAP && load_midx_revindex(m)) { + error(_("could not load reverse index for MIDX %s"), + hash_to_hex_algop(get_midx_checksum(m), + m->repo->hash_algo)); + result = 1; + goto cleanup; + } ctx.num_multi_pack_indexes_before++; m = m->base_midx; } @@ -1387,7 +1406,7 @@ static int write_midx_internal(struct repository *r, const char *object_dir, if (flags & MIDX_WRITE_REV_INDEX && git_env_bool("GIT_TEST_MIDX_WRITE_REV", 0)) - write_midx_reverse_index(midx_name.buf, midx_hash, &ctx); + write_midx_reverse_index(&ctx, object_dir, midx_hash); if (flags & MIDX_WRITE_BITMAP) { struct packing_data pdata; @@ -1410,8 +1429,8 @@ static int write_midx_internal(struct repository *r, const char *object_dir, FREE_AND_NULL(ctx.entries); ctx.entries_nr = 0; - if (write_midx_bitmap(r, midx_name.buf, midx_hash, &pdata, - commits, commits_nr, ctx.pack_order, + if (write_midx_bitmap(&ctx, object_dir, + midx_hash, &pdata, commits, commits_nr, flags) < 0) { error(_("could not write multi-pack bitmap")); result = 1; diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c index 34e86d4994..8a30853d2e 100644 --- a/pack-bitmap-write.c +++ b/pack-bitmap-write.c @@ -26,6 +26,8 @@ #include "alloc.h" #include "refs.h" #include "strmap.h" +#include "midx.h" +#include "pack-revindex.h" struct bitmapped_commit { struct commit *commit; @@ -43,7 +45,8 @@ static inline int bitmap_writer_nr_selected_commits(struct bitmap_writer *writer } void bitmap_writer_init(struct bitmap_writer *writer, struct repository *r, - struct packing_data *pdata) + struct packing_data *pdata, + struct multi_pack_index *midx) { memset(writer, 0, sizeof(struct bitmap_writer)); if (writer->bitmaps) @@ -51,6 +54,7 @@ void bitmap_writer_init(struct bitmap_writer *writer, struct repository *r, writer->bitmaps = kh_init_oid_map(); writer->pseudo_merge_commits = kh_init_oid_map(); writer->to_pack = pdata; + writer->midx = midx; string_list_init_dup(&writer->pseudo_merge_groups); @@ -113,6 +117,11 @@ void bitmap_writer_build_type_index(struct bitmap_writer *writer, struct pack_idx_entry **index) { uint32_t i; + uint32_t base_objects = 0; + + if (writer->midx) + base_objects = writer->midx->num_objects + + writer->midx->num_objects_in_base; writer->commits = ewah_new(); writer->trees = ewah_new(); @@ -142,19 +151,19 @@ void bitmap_writer_build_type_index(struct bitmap_writer *writer, switch (real_type) { case OBJ_COMMIT: - ewah_set(writer->commits, i); + ewah_set(writer->commits, i + base_objects); break; case OBJ_TREE: - ewah_set(writer->trees, i); + ewah_set(writer->trees, i + base_objects); break; case OBJ_BLOB: - ewah_set(writer->blobs, i); + ewah_set(writer->blobs, i + base_objects); break; case OBJ_TAG: - ewah_set(writer->tags, i); + ewah_set(writer->tags, i + base_objects); break; default: @@ -207,19 +216,37 @@ void bitmap_writer_push_commit(struct bitmap_writer *writer, static uint32_t find_object_pos(struct bitmap_writer *writer, const struct object_id *oid, int *found) { - struct object_entry *entry = packlist_find(writer->to_pack, oid); + struct object_entry *entry; + + entry = packlist_find(writer->to_pack, oid); + if (entry) { + uint32_t base_objects = 0; + if (writer->midx) + base_objects = writer->midx->num_objects + + writer->midx->num_objects_in_base; + + if (found) + *found = 1; + return oe_in_pack_pos(writer->to_pack, entry) + base_objects; + } else if (writer->midx) { + uint32_t at, pos; + + if (!bsearch_midx(oid, writer->midx, &at)) + goto missing; + if (midx_to_pack_pos(writer->midx, at, &pos) < 0) + goto missing; - if (!entry) { if (found) - *found = 0; - warning("Failed to write bitmap index. Packfile doesn't have full closure " - "(object %s is missing)", oid_to_hex(oid)); - return 0; + *found = 1; + return pos; } +missing: if (found) - *found = 1; - return oe_in_pack_pos(writer->to_pack, entry); + *found = 0; + warning("Failed to write bitmap index. Packfile doesn't have full closure " + "(object %s is missing)", oid_to_hex(oid)); + return 0; } static void compute_xor_offsets(struct bitmap_writer *writer) @@ -586,7 +613,7 @@ int bitmap_writer_build(struct bitmap_writer *writer) struct prio_queue queue = { compare_commits_by_gen_then_commit_date }; struct prio_queue tree_queue = { NULL }; struct bitmap_index *old_bitmap; - uint32_t *mapping; + uint32_t *mapping = NULL; int closed = 1; /* until proven otherwise */ if (writer->show_progress) @@ -1021,7 +1048,7 @@ void bitmap_writer_finish(struct bitmap_writer *writer, struct strbuf tmp_file = STRBUF_INIT; struct hashfile *f; off_t *offsets = NULL; - uint32_t i; + uint32_t i, base_objects; struct bitmap_disk_header header; @@ -1047,6 +1074,12 @@ void bitmap_writer_finish(struct bitmap_writer *writer, if (options & BITMAP_OPT_LOOKUP_TABLE) CALLOC_ARRAY(offsets, writer->to_pack->nr_objects); + if (writer->midx) + base_objects = writer->midx->num_objects + + writer->midx->num_objects_in_base; + else + base_objects = 0; + for (i = 0; i < bitmap_writer_nr_selected_commits(writer); i++) { struct bitmapped_commit *stored = &writer->selected[i]; int commit_pos = oid_pos(&stored->commit->object.oid, index, @@ -1055,7 +1088,7 @@ void bitmap_writer_finish(struct bitmap_writer *writer, if (commit_pos < 0) BUG(_("trying to write commit not in index")); - stored->commit_pos = commit_pos; + stored->commit_pos = commit_pos + base_objects; } write_selected_commits_v1(writer, f, offsets); diff --git a/pack-bitmap.c b/pack-bitmap.c index 5e6d4ace58..94d1e8474a 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -1719,7 +1719,7 @@ static void show_objects_for_type( } } - ewah_or_iterator_free(&it); + ewah_or_iterator_release(&it); } static int in_bitmapped_pack(struct bitmap_index *bitmap_git, @@ -1808,7 +1808,7 @@ static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git, bitmap_unset(to_filter, pos); } - ewah_or_iterator_free(&it); + ewah_or_iterator_release(&it); bitmap_free(tips); } @@ -1903,7 +1903,7 @@ static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git, bitmap_unset(to_filter, pos); } - ewah_or_iterator_free(&it); + ewah_or_iterator_release(&it); bitmap_free(tips); } @@ -2552,7 +2552,7 @@ static uint32_t count_object_type(struct bitmap_index *bitmap_git, count++; } - ewah_or_iterator_free(&it); + ewah_or_iterator_release(&it); return count; } @@ -3133,7 +3133,7 @@ static off_t get_disk_usage_for_type(struct bitmap_index *bitmap_git, } } - ewah_or_iterator_free(&it); + ewah_or_iterator_release(&it); return total; } diff --git a/pack-bitmap.h b/pack-bitmap.h index d7f4b8b8e9..dd0951088f 100644 --- a/pack-bitmap.h +++ b/pack-bitmap.h @@ -111,6 +111,7 @@ struct bitmap_writer { kh_oid_map_t *bitmaps; struct packing_data *to_pack; + struct multi_pack_index *midx; /* if appending to a MIDX chain */ struct bitmapped_commit *selected; unsigned int selected_nr, selected_alloc; @@ -125,7 +126,8 @@ struct bitmap_writer { }; void bitmap_writer_init(struct bitmap_writer *writer, struct repository *r, - struct packing_data *pdata); + struct packing_data *pdata, + struct multi_pack_index *midx); void bitmap_writer_show_progress(struct bitmap_writer *writer, int show); void bitmap_writer_set_checksum(struct bitmap_writer *writer, const unsigned char *sha1); diff --git a/t/t5334-incremental-multi-pack-index.sh b/t/t5334-incremental-multi-pack-index.sh index 26257e5660..46d1f0b864 100755 --- a/t/t5334-incremental-multi-pack-index.sh +++ b/t/t5334-incremental-multi-pack-index.sh @@ -44,4 +44,88 @@ test_expect_success 'convert incremental to non-incremental' ' compare_results_with_midx 'non-incremental MIDX conversion' +write_midx_layer () { + n=1 + if test -f $midx_chain + then + n="$(($(wc -l <$midx_chain) + 1))" + fi + + for i in 1 2 + do + test_commit $n.$i && + git repack -d || return 1 + done && + git multi-pack-index write --bitmap --incremental +} + +test_expect_success 'write initial MIDX layer' ' + git repack -ad && + write_midx_layer +' + +test_expect_success 'read bitmap from first MIDX layer' ' + git rev-list --test-bitmap 1.2 +' + +test_expect_success 'write another MIDX layer' ' + write_midx_layer +' + +test_expect_success 'midx verify with multiple layers' ' + git multi-pack-index verify +' + +test_expect_success 'read bitmap from second MIDX layer' ' + git rev-list --test-bitmap 2.2 +' + +test_expect_success 'read earlier bitmap from second MIDX layer' ' + git rev-list --test-bitmap 1.2 +' + +test_expect_success 'show object from first pack' ' + git cat-file -p 1.1 +' + +test_expect_success 'show object from second pack' ' + git cat-file -p 2.2 +' + +for reuse in false single multi +do + test_expect_success "full clone (pack.allowPackReuse=$reuse)" ' + rm -fr clone.git && + + git config pack.allowPackReuse $reuse && + git clone --no-local --bare . clone.git + ' +done + +test_expect_success 'relink existing MIDX layer' ' + rm -fr "$midxdir" && + + GIT_TEST_MIDX_WRITE_REV=1 git multi-pack-index write --bitmap && + + midx_hash="$(test-tool read-midx --checksum $objdir)" && + + test_path_is_file "$packdir/multi-pack-index" && + test_path_is_file "$packdir/multi-pack-index-$midx_hash.bitmap" && + test_path_is_file "$packdir/multi-pack-index-$midx_hash.rev" && + + test_commit another && + git repack -d && + git multi-pack-index write --bitmap --incremental && + + test_path_is_missing "$packdir/multi-pack-index" && + test_path_is_missing "$packdir/multi-pack-index-$midx_hash.bitmap" && + test_path_is_missing "$packdir/multi-pack-index-$midx_hash.rev" && + + test_path_is_file "$midxdir/multi-pack-index-$midx_hash.midx" && + test_path_is_file "$midxdir/multi-pack-index-$midx_hash.bitmap" && + test_path_is_file "$midxdir/multi-pack-index-$midx_hash.rev" && + test_line_count = 2 "$midx_chain" + +' + test_done