From patchwork Thu Mar 20 17:56: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: 14024270 Received: from mail-qk1-f174.google.com (mail-qk1-f174.google.com [209.85.222.174]) (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 BBB5822652E for ; Thu, 20 Mar 2025 17:56:27 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.222.174 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493389; cv=none; b=d5qLF2GLfQWlV7QXSLYhEHkMJtOrG+g+zi132dli5QNsJgB4zM3BNohttxkoDfPn4fV0sXYH4ms1K+kQY9n9eJ0s+aBA5c2AAaPfIwgF+xNElhszoOLtplUHEBkMyQpBrLpFRuOZKbKoP5h/RRT9vcDRSq/dq/acbysjWVyJDyQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493389; c=relaxed/simple; bh=KxLTthee5U4Y3fUySNU+8z1ecvU775a+xOYJpNHF8aM=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=gcltoDyAJZgpMSfKi3w6nxJsTjri050OzB/5zdGKBMZXXhK+NUMOowHF1QItMHpNxYox7jGY6jxcKHP3c9gwjKkbiAYXGVmGP+emQM5TYUiPCz3a4Y0ABLwUiQ/bg3Q0PKvaeg4NM6gPy+8XS8Gg7DerJMFQ9Ebp3QNxTbTWjoU= 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=k5lRnyT9; arc=none smtp.client-ip=209.85.222.174 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="k5lRnyT9" Received: by mail-qk1-f174.google.com with SMTP id af79cd13be357-7c559b3eb0bso56101385a.1 for ; Thu, 20 Mar 2025 10:56:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1742493386; x=1743098186; 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=4WkR0UuCZVk9W5hpkFegbCPqNJJHGLYVMhyEm/nPffo=; b=k5lRnyT9wq18DHJ2KDm7YEvIKE2NcJWX0ktbi8z0pZNZCC8K8AUGRBtoMOT4nr1Ymb yltpwNI3eSsittDrbJpyj8Tb5UO2TPsnJ2IbZlssmqZL5UrEQR5S6fdjlQNoyszx0hSe 7epKZ1sCupaATNggLhhr7smzsC1gwbdWOX2p4taaqtMyuWEVulmWcb81ZwRr/R9v2RKf DDXruXC0NdVkgSIPS7nRT0Y/kby3qO1BnLJbDtwAl/fkeZJnxjz+18hFnzOHRouPQ4KR WFFO6iDVkSnuNbA+dLIJcGCBmNvbcHwAINVrHI99VJ9DKR/wT6MtjWjCbkqTSQLyl7QB 7h6g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1742493386; x=1743098186; 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=4WkR0UuCZVk9W5hpkFegbCPqNJJHGLYVMhyEm/nPffo=; b=mEGOE50uel0GrM7N38eJekRjq5pyGddo0vFoe6ITGhMv+565OgC2971wXLiwfc9HdF AGwst7ZkbcGXS03d6zGc4XxFV41D4tBm9tPT4GUGyimlsZMx6uqiH0RjqFyW+LCsFzvn IqXki4VsOQG8I98OJkd7eTTMXldmFB1qrqJPBTQDkcDF2AJBJV9AOhQDlO4TMnAKw+B2 tZ3daKWlOBXxE2/CuJspb2Bo6nG5ap3l9hMMdpuk49Y6Gxu7MuyoHEwk3ZTihn26eVdb AvPtfRa19FI+1MEdKrFHEH0AfCc3CQneNqu4JzW3V8+9XWBJQpkdbuBuYMdqYtGbuUgS WHxg== X-Gm-Message-State: AOJu0YxBQ6WcLJaCJCd1JtqUasSxAPMYGReZKvFSZ/GV83Xw2KJTrScX kpWVocvr2JmWGHjxi731MNnhVgh1t7Q7ts5BU47BUA1x7I4ywIu9SxgzvJ9CneU5FRDYUd5WIbj ZXE0= X-Gm-Gg: ASbGncsUsENWb984SwkwKzqpt9WkcHOqS7xW2aGflYioiQkIz2cD1YQEuHhqCzy19Tf M1lmNaWA9o/gA9/NMD62/wg55WWoMMAc7tzExMUiI1LyDnY1TKAS8fz8ql5dk2d+9A8GTQWBnFs qaEU4VLtoTTqLBZm0Se2xqYTpFRXKY6h/I2p0r56LjO9btCRG2hCL0/x35WU3rJWaQ0bomsLH5T Gt5+lqt8ONaFcfeQfCNNfj3pOEhDA2jPf0yKVibDj/734zdNrwHDUK5p35BVNjcg7zs1ii+qZuG 3ZG5yzyrm3jyibMT8RRXkwQm4YI1Ws9DqR/cpjhM09SFxkU8qhUlgVGz3dmRMHnjzF9J0y9FLn0 IvGkGfsguBK7KJsRO X-Google-Smtp-Source: AGHT+IGNh15It4Y6fif5Doy9B1gAaEA4GZuELr/aDdAu3Nxqpf5ars5iU3H5TdEiYBaVmPu4sSeFsA== X-Received: by 2002:a05:620a:45aa:b0:7c5:55f9:4bcb with SMTP id af79cd13be357-7c5ba190bf1mr15396685a.31.1742493386463; Thu, 20 Mar 2025 10:56:26 -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-7c5b92b3f97sm16477485a.13.2025.03.20.10.56.26 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 20 Mar 2025 10:56:26 -0700 (PDT) Date: Thu, 20 Mar 2025 13:56:24 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v5 01/14] Documentation: remove a "future work" item from the MIDX docs Message-ID: <6af65fdaacd5e50cc2e3cc0611d1cf08ef3aa452.1742493373.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: One of the items listed as "future work" in the MIDX's technical documentation is to extend the format to allow MIDXs to be written incrementally across multiple layers. This was suggested all the way back in ceab693d1f (multi-pack-index: add design document, 2018-07-12), and implemented in b9497848df (Merge branch 'tb/incremental-midx-part-1', 2024-08-19). Let's remove it accordingly. Signed-off-by: Taylor Blau --- Documentation/technical/multi-pack-index.adoc | 10 ---------- 1 file changed, 10 deletions(-) diff --git a/Documentation/technical/multi-pack-index.adoc b/Documentation/technical/multi-pack-index.adoc index cc063b30be..dea6486f88 100644 --- a/Documentation/technical/multi-pack-index.adoc +++ b/Documentation/technical/multi-pack-index.adoc @@ -167,16 +167,6 @@ m->num_objects_in_base`). Future Work ----------- -- The multi-pack-index allows many packfiles, especially in a context - where repacking is expensive (such as a very large repo), or - unexpected maintenance time is unacceptable (such as a high-demand - build machine). However, the multi-pack-index needs to be rewritten - in full every time. We can extend the format to be incremental, so - writes are fast. By storing a small "tip" multi-pack-index that - points to large "base" MIDX files, we can keep writes fast while - still reducing the number of binary searches required for object - lookups. - - If the multi-pack-index is extended to store a "stable object order" (a function Order(hash) = integer that is constant for a given hash, even as the multi-pack-index is updated) then MIDX bitmaps could be From patchwork Thu Mar 20 17:56:28 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14024271 Received: from mail-qt1-f181.google.com (mail-qt1-f181.google.com [209.85.160.181]) (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 E47DE226D07 for ; Thu, 20 Mar 2025 17:56:30 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.160.181 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493392; cv=none; b=tY+slP6L0MAJYECjBf4kIrXDfh9eq2jVYyVybUA3Ngk3pCsInlDROoZZwVhMgXBA3JoYXtdtuvSv8OSdkOUP4b6mbPVlKojimaRk2KkpyBrwBkrhpnOxCz2DDnsZnQOoPDmReFgVudk+mAmstg2OaHkH8xcaH/8nWLT3I1SPEm4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493392; c=relaxed/simple; bh=f3AV+8otO5hbjxB/NdrYS7Ir6wA65aLzOGBbJaQrjPk=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=XFxNWPCBVUMbWZqM9ifHdfI8xNguSKHMy6FL1GPmNNlDTyDhGfo2IY4aIvi6WYIjG/y7ep6bO/yLWfYepnWkQ4gfzRWhJrdKjaGevZIjjrcJJ/mfEqG0n1WYozpTCw3SOxMfXwi2bh6Fkl6oid1UL1cLdDow9U0K0gwuiJm/ArM= 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=wwwWuRbT; arc=none smtp.client-ip=209.85.160.181 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="wwwWuRbT" Received: by mail-qt1-f181.google.com with SMTP id d75a77b69052e-46c8474d8daso10038511cf.3 for ; Thu, 20 Mar 2025 10:56:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1742493389; x=1743098189; 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=NpfHGMLFzmBBNjIAqUnwos+XwPk7NDi9WzmE3kCQHn0=; b=wwwWuRbT2/yDQueE7RchcPS/0Jwhm44OrBnra9vo2O6D8xThNDVdgw3dLRJm0tL5b+ aBR8m1Vbif7oGPeVkS2rAY12G11oafXSzsGSJInH7AAuSJdX2rBgurKyOg8zBliEfsJi cakSqg3V5bxRw9B5O4Nnc7icNU7OO2o9ePorIWEVoyFb8EeKs0LQG3GSS6vw8soczhS+ ONdRmIIPJiKiAXMzcUiWsHQWtvOU+N+KwmurqgtKbLc1cLt74BKd7QRshA5uMjjoV3du wpWWnBY5h2PXLasRuUBSE5/jd6ZnKhoz+YMlZQeDMdLejSmaiPQQ/O0hDWnjEInlNZtu 9qag== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1742493389; x=1743098189; 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=NpfHGMLFzmBBNjIAqUnwos+XwPk7NDi9WzmE3kCQHn0=; b=uEZ/qOVmT7VkcnV0XVef4WeQQnF3uMX5FrndXabUaUTsx3f4eG6QZ+6zRIhI4Ig5zX ao0ll3X4aX3SMvNlbLIpT1knAy2s6l7Vp0Nv9v7GPOdr1rG8nErKI7Tvn2YfQ6Wkkpth VEzhFgZ1KB3LiQxdJjRtz05I7QGkBitGi9Ca2DsAnWeyuqAdOUCMRLPu8BeVhp21hGgP ownJGkoZPi/4nc4uMPtW3lxxNqEX3vLAZ/9U9yzw1cGYcuBvPE9ajaC2N1SudakmBzm1 2yipu4QXjVMZbEZwdfKgDNNftYNfjHBw9+g7L2mDxq7RGwxjmPJH0XW1Ds+ikUsS5Zby 8Kdg== X-Gm-Message-State: AOJu0YyRamjeDd9AEaviLnJYXUSOBz6zXtv+RT1RU+sp+I4ffZSHDN1b qvWO4XUDhb0fg/IxlMnjzA3eXYBFZcH1yMAmy8sOYv41wlZjxPHJCCLJrAhStiyvQv59eEdHiaq Qbis= X-Gm-Gg: ASbGncuteWHCLZ8cs0AiKrq8tbEHsCKVSh6AYli1DCipGzuQTrVRWwsf8Zz2m+/Ricd Tyv2Gk1yiAhNe8X4yHLWb8SVgcBHjoEsfINIFFwmmN05Jtm4g9RAqihArQaXyZ1RZMxjOAC8KEH dRl2iIoWC0dyFeT651TfEHiutS/8D9o7i8DVHhr3O1XNbjk8vrEFx1awOylzZCT4A30aXVhXF+3 UQMmlExMsmWZAGk1HVtCGN1QvGzc8L3dx3bAHU8bP0Q/CK0TnIqvwY+WcT8JRbGti4yHrUpNZrP RZkCADINkg35wA3dC5Zhfqr9o0xrPyoR80t589VjMammRCjvGLUHdswY8zW31WLWjTcWSe8rrIw Lt+uZpGtrCimInYNa X-Google-Smtp-Source: AGHT+IFeePsiH4nbS6Ked9Kfp3bYcKP50HgQPjVpKLWr/gcuBUvyDwACWi6xwvDaNCIWlvn75sjPIA== X-Received: by 2002:a05:622a:22a5:b0:476:aa7a:2f78 with SMTP id d75a77b69052e-4771de5b160mr3130441cf.49.1742493389658; Thu, 20 Mar 2025 10:56: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 af79cd13be357-7c5b92d6883sm16219385a.45.2025.03.20.10.56.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 20 Mar 2025 10:56:29 -0700 (PDT) Date: Thu, 20 Mar 2025 13:56:28 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v5 02/14] Documentation: describe incremental MIDX bitmaps Message-ID: <0897359506211b407c173e50007555e7de083342.1742493373.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 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 | 72 +++++++++++++++++++ 1 file changed, 72 insertions(+) diff --git a/Documentation/technical/multi-pack-index.adoc b/Documentation/technical/multi-pack-index.adoc index dea6486f88..ffda70aa13 100644 --- a/Documentation/technical/multi-pack-index.adoc +++ b/Documentation/technical/multi-pack-index.adoc @@ -164,6 +164,78 @@ 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` sorts ahead of `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 ahead of + the non-preferred one. 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, then `o1` sorts ahead of + `o2`. Likewise if `pack(o2)` appears earlier, then 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` files 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 Thu Mar 20 17:56: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: 14024272 Received: from mail-qt1-f181.google.com (mail-qt1-f181.google.com [209.85.160.181]) (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 D4F1E226D14 for ; Thu, 20 Mar 2025 17:56:33 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.160.181 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493395; cv=none; b=rWu9KM3cP7bngrZbHrDRIWZJUQ8VwUnTYsnB+y7tZOUY/uQOmlsliI/83BLMqj+oJHy5Ytzj7P2fITij4ZJYOTBnYGBPzEbCuA6IGT4oF3MDTM+p/OLyJMp7LN0UlKgblqW/KK10SotnWKf49UTJ+6jj5Ask8fEm5vaa2CIWLk0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493395; c=relaxed/simple; bh=/iu2sLQgyJEc7KczN4fg/h+T5UJVmCh3HJ7VrCGQU0k=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=Oc2ZcQREoa/zT6bDUzZEdAK9tikarOT1XauStvJxe0HNYAuQR5c1mVn9ATPkMgba30UVzUwRe951w+aefQTMXi8nuC/ikeLOLUR2fL6BrMU1JLvZNxd/1qslduN5u3O9ea8ZuVBL8TseCI8uc2/5RsHwYWXqtAjGb/d5TfD5774= 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=vTA2PsSC; arc=none smtp.client-ip=209.85.160.181 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="vTA2PsSC" Received: by mail-qt1-f181.google.com with SMTP id d75a77b69052e-47692b9d059so15341461cf.3 for ; Thu, 20 Mar 2025 10:56:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1742493393; x=1743098193; 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=okeut1hGQOfrMJhKwahTjs3IcdAeJwbz5BeZIM/0gqg=; b=vTA2PsSCpA48FmxAErwsIZiMDampg2/1p/7Utwhbg34MPfHHv3sD2I9FyIagUpPOJZ cggaZSBeWwHfIsR7el1G6A4QQPyb6uItv6YlfFXqjK9qTGYoocBN9eskiQp5UFEoaYrn lyNJN+yHpi+BOZWRDoBJJkzjnz0o6Bw0GgkrPxAbzbJ16wdAYy/+/WU09qn6cb4g656X tNOAnWynNYkT9Oj2vhxis+iAWe8Q3Rq+DwNbMNwpVS2BbcqssDmsCoKnd1VAiZGjXy6d dqzPnxWrtMObjd/uzYGyuFdYr6J/mqFzQkdkx3nBk8laDCo/l3yhrzUKr3LsoIh5GOD8 WEag== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1742493393; x=1743098193; 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=okeut1hGQOfrMJhKwahTjs3IcdAeJwbz5BeZIM/0gqg=; b=pFdpkBVLldkEJ8q3hr607essjfRsXVYsRpoIS75g8eOLNpZwGDgIF5SmXkj3dRTop6 9cYVOcqd6vM0kmig3qF8tChw3PHv/gJHuWZWw2gcMttV7NpptHCAvpCSGBoVj/J/NAGZ 4XSj4Fqe38GCbKIJ7Z0XNJPCLSpUmxngAMoG/eircPIvAcOckerwhYx4crpySemDspwO B/XCBJJfc+TwZFEfC/UqAt3Y0ciF7482Bkj/m4jIpnA/2+WcvKUiIGk+gj+KgWD9Gfyk MlndY/FrGJ1o5ftArJjyHIU023LzgMA39CoHek3JJqLsYoMsafwHQtJybmP+onfIpAGy f+Gg== X-Gm-Message-State: AOJu0YyKkl6BhtkYDC60kC6ti74OEoscPgBR1j/aZUlMyv5eRA7rt8+j JsN8lYu2m8I5z5k4Vft3nDScfa6lw+g/wrR3CDBVGlkbGcZhKfLcz17W3240lGfZL2y2vBPHn5t bl3Q= X-Gm-Gg: ASbGncsx+ZrCbHHxmmCMvBGLe57dywMdzocFp07i6sdwYsewa3gcpr4uQ05ZOfJzWoi +MpCDMRffFZ1zWB0uy5Ed79LoM4KJqA2b6p7VgMQSV5Qp03Ia9qVx0gKKonYjUiht7GwpHrssjT 7w1eNw3U32nMs1WOFYOOZBtFMmjXaqzKIZ7SeJiVL59o35NXClTHaBhCkzOLZQn8sjcTxadXReM Y7vg7j3bAW0TgHAgl3IWFyWiJvqqOfpMJk5H0d4FvHPdec+BFMPQBc0+PKJO0sxCQtpGHSlRIpU Aa3dqyKY7lEw8YqaS0C0eZHPOzD5YgwtikW6Drfq094dYNjNHB5ecJZzetPruFMcuQsCDRhwl26 Fm8iSls5APEukJOWE X-Google-Smtp-Source: AGHT+IFMehXMs8yRuNtaY5HdvqW4NHAqrl2n/Rqby0TY8Rk+KtdiG+thEbuzOMUGSpsdq5PGtk6lJQ== X-Received: by 2002:a05:622a:5509:b0:476:6e2e:58b with SMTP id d75a77b69052e-4771de8e1a0mr3592181cf.49.1742493392715; Thu, 20 Mar 2025 10:56: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 d75a77b69052e-4771d15a081sm1541211cf.9.2025.03.20.10.56.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 20 Mar 2025 10:56:32 -0700 (PDT) Date: Thu, 20 Mar 2025 13:56:31 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v5 03/14] pack-revindex: prepare for incremental MIDX bitmaps Message-ID: <5eac0d1485019179cde4f8b010ac64ee7eb3cd3f.1742493373.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 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 find 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 | 43 +++++++++++++++++++++++++++++++------------ pack-revindex.c | 34 +++++++++++++++++++++++++--------- 2 files changed, 56 insertions(+), 21 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 6406953d32..87f3b5cf4d 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_num_objects_total(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_num_objects_total(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_num_objects_total(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,9 @@ 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_num_objects_total(bitmap_git), + i))) continue; obj = eindex->objects[i]; @@ -1679,7 +1696,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_num_objects_total(bitmap_git)); if (eindex->objects[i]->type == type && bitmap_get(to_filter, pos) && !bitmap_get(tips, pos)) @@ -1705,7 +1722,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_num_objects_total(bitmap_git)) { struct packed_git *pack; off_t ofs; @@ -1728,8 +1745,9 @@ static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git, die(_("unable to get size of %s"), oid_to_hex(&oid)); } } else { + size_t eindex_pos = pos - bitmap_num_objects_total(bitmap_git); struct eindex *eindex = &bitmap_git->ext_index; - struct object *obj = eindex->objects[pos - bitmap_num_objects(bitmap_git)]; + struct object *obj = eindex->objects[eindex_pos]; 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 +1900,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_num_objects_total(bitmap_git); pos = objects_nr / BITS_IN_EWORD; if (pos > result->word_alloc) @@ -2419,7 +2437,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_num_objects_total(bitmap_git), i))) count++; } @@ -2820,7 +2838,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_num_objects_total(bitmap_git); CALLOC_ARRAY(reposition, num_objects); for (i = 0; i < num_objects; ++i) { @@ -2963,7 +2981,8 @@ 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_num_objects_total(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 Thu Mar 20 17:56: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: 14024273 Received: from mail-qk1-f169.google.com (mail-qk1-f169.google.com [209.85.222.169]) (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 3468F227563 for ; Thu, 20 Mar 2025 17:56:36 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.222.169 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493398; cv=none; b=Hi9foCWD5aA0tTNrFryWy4UOpDvGitNDzIfmuHjVnsZV8QS6mS0WH7USiJzrc3BH2HCNHTofhl/qs8A+j8f4lrK6+XuuksewSzzAbtc67nUMhUZ60WsBPqGW78e1T8Ba9ULPSvJ5tR5yCj3jUaKiKauK+O+Gu97dko2jektwBhw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493398; c=relaxed/simple; bh=WnVeB1hbVLcyjXSQUbTbZCThBQSh0ip1ULFqeTh1Io0=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=s0s97h8WIdcDvEilVN75ms6DAVK3IDLe6QZgk6FdUsNbr+GeWj7eGLqJ2G8IgyLVZqJzD0hKc1jeS3c5my2TAAZcCeNI7Jrw7rjuufD/eSxuG499i8xETOwr8skxEmSFQjAhY8JFRRazb/1Ce++Je6rAc3FxrdkCrStzXYazuWk= 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=NgF0xOR/; arc=none smtp.client-ip=209.85.222.169 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="NgF0xOR/" Received: by mail-qk1-f169.google.com with SMTP id af79cd13be357-7c5a88b34a6so114278285a.3 for ; Thu, 20 Mar 2025 10:56:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1742493396; x=1743098196; 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=J8BumMeL9zYKjokSFg9jhQgkRk22D7RUsejzgnvQcvU=; b=NgF0xOR/GOm9f5Pb5DcEsXqiEn+2DlcHPrUW7eX8THzwRhpyEi0hp0Fs6F87NbGPZ8 zY0awV04bWAKOiN+4914Nis+y3fCFMrA8xFXcQRHbkDND7buKmurNVvxITPAnWurerLG F1IY5eZiA3fWrCqCGzqJbCw9v6eLGTtWBp6gT+GZYM3YjmRs8zR74cqonN/8iWWAvqLL LKmhHGNLLwni0jBzMyMXgRjuj0eBE+rIb2E5fZ5AQ/JGkOtx8fZV+6DbMfDcSO6FzYay 55EyKx7yw2RG2B6l+rWnCs0BzP8cNX9hVGs3ztxlqkDxuE47qxO0BLA+fzKHXHhYdqY1 evaQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1742493396; x=1743098196; 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=J8BumMeL9zYKjokSFg9jhQgkRk22D7RUsejzgnvQcvU=; b=OBUAI8feK2Dui3sttwsYzYaarA5gnzsyJM6TiuFGtO4FoUNKAbwGBuJ2Vu/f9cfXqU KfpTmIzLfZ/LjJlbs6eoKz3czoL/KIcucPGf/bEDKM+zyidD33zcgMvAnb22zyGVdmVb 3y4hgoBkSmT2B/W/GvzetxYfWQQ5DIUrkq06Bq8Vm8ExLQz2VXAoO2QgZbz28t5S3ckw fLHVM8yL+mUmVHNh5ncoSAon+V6UwcFCNZAW6QyKkcjp6BW5JF6c8KXiVTW5lIgANoQ5 h17pc723be8XZvYFFrNi2ehBSTL/3uIa23X41PDMsWUK4vtn/+wpbF4IPqm6qWwJgqMH WPDw== X-Gm-Message-State: AOJu0YznzDZo2gdWB6fiCkG2hnr8FzazQHCgqnlJaF7nr4GbGvA9xWWo vEYAEAhe2rUwUQ26YbBq5gfBKoice0Nxu47LceAkt3xhwU94hrv5pcHfAmuobKJueyZIUPw8Xbr 2cr0= X-Gm-Gg: ASbGncuyxO2EBfpoaATGbwUc3aGrHthZ1ZOtvrAIgJdugf8JQ9XpR4R8mzgySbsWQxU fQWFj4lW2c6yR5MEfnsbosFSDYZp+9obxOEo2/MVEimlz4lQ71oc7TdfxVFDbsSqILQf53u7S+t IcFiJn7tMzUw3kx6rqhWoJachD82qyhxHroQqIrZKAKORUsOLkUgAxkNYDJL/mdjg92HpQ50eWs 8u9CmR03Rq8hlaknpqZHEOT5B52YYW3dDYtDhZ4YCfggPqcgr3egWLFk5QUtBGDC1UuCndOOIOf K70qHbcVUltQpgVCa6bBEEYEnf8S5lvcTEECy/ryVWHuHq2iZXaRcW47+/WXYYo5czwVdHYbpXN v8f/qiUWJACK/OK+LjkPo9RXfIrM= X-Google-Smtp-Source: AGHT+IHCF4r7d26tDjcEyrgKo6pBpc96SI6SdQxpwbAJynuJdWiVoBmUk3Ddfpy0JJQ5PBEgpPdIwg== X-Received: by 2002:a05:620a:3908:b0:7c3:c329:792f with SMTP id af79cd13be357-7c5ba135bd1mr17030785a.3.1742493395831; Thu, 20 Mar 2025 10:56: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-7c5b92b8609sm16451185a.18.2025.03.20.10.56.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 20 Mar 2025 10:56:35 -0700 (PDT) Date: Thu, 20 Mar 2025 13:56:34 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v5 04/14] pack-bitmap.c: open and store incremental bitmap layers Message-ID: <922ea2f6075b47419a07e881efb2557ac73ba0c9.1742493373.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 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 of bitmap layers along the "base" pointer, ensure 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 87f3b5cf4d..e84211de15 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); @@ -2901,6 +2934,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 Thu Mar 20 17:56: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: 14024274 Received: from mail-qv1-f47.google.com (mail-qv1-f47.google.com [209.85.219.47]) (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 1B928226D15 for ; Thu, 20 Mar 2025 17:56:39 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.47 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493401; cv=none; b=F4KHwgLBsHilAGoMQUqyyGoWXGLC1AgUrpU3ap81YIm65Sca6UaOzMBDJNUm/3q9i4aVDjDf3pZ0kYMZd0MTvXyLxYZ3OZCZZ6OoRsKB/UZBwz8Sfrnc2TEgUMoDqqxDLZVcE/R09Gxm5fpLmAEVYTwCO10ihGpomXk1S+Tr8GQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493401; c=relaxed/simple; bh=vkWXuI5XQwptlWXD8LJXY5ETixKyybnQCmQNn9+ccUg=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=XHHqclzrOcIFp33LOl9+G3rwCeuBZzYffp9+ar2BAyJwrMXzA21nNykoYSfpDKAQ/CJE1B/0UAtIm4tzKdfu/NA6xG4efYx66A0FmNhk37gLLYYfxoVWoEDkvQKVtBBbfNzpoj97CJsUZZNvxOy4DgFWYC0fuRju84AP6vWirJc= 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=m2NIzx7f; arc=none smtp.client-ip=209.85.219.47 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="m2NIzx7f" Received: by mail-qv1-f47.google.com with SMTP id 6a1803df08f44-6dd1962a75bso8392156d6.3 for ; Thu, 20 Mar 2025 10:56:39 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1742493399; x=1743098199; 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=iuJYfc2WVdHkQ1d4xMSLkhVlfdAMjk3b4MIrQVtjuRg=; b=m2NIzx7fPpU68es8kdPTGliLyMO2adwKzOseEduv4p0e1XKBTwea3ksmCPYFlS20Px SGjwq0L+UibiXXmNDCaN4rMmcznKAjjd4AXMQUVkflPKXttHVln+c72rY/fdcpIZviRk occ9Le/g2XYzc4ggyvY5EpEUcPJTqhCTWWkR05LDypMBVQIb3Bs0lq9bmZ2EHv0zop+c dWDbS4bqqKzLyqTqaH5ERrei3pjmJm3XXZ5Urb71DvykG/HPA6/Ms1UQUZWq07QLS+2I 4iv54reQxEkwyAebjxh7/EqjvYfr8kMNWcVuM2f3L+ECWeN9ElH4peUnQvp94g5Yb7b/ Rijg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1742493399; x=1743098199; 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=iuJYfc2WVdHkQ1d4xMSLkhVlfdAMjk3b4MIrQVtjuRg=; b=BIKwFDzwqbbIaQFNCv2kSOa7D1hio/Ly/cFh09+m1kmc2Qe1nhh9U/5jCnY4+G6+lH nBmOlp7v9Q73wA8Ne1ggHcwVBtRzPTrYhKTaGE6JPYUX5GFrzvfwZ4lJKvWJQpTKlKhs NXWT5iTICChmoq9iH56p5Q31hgZWQjVl6hwS+5kdSm3sM/rriZ857+pOJY4/wWk6uPlb V45vtKKeDjBe83h7XfGOQRyp3DyHxjJM0Qy3OKM4q3NWy0WzOZ0B5E7ehsRsxJCMx3GW O1/xwmcfe6xJ0kITS8rECSXGnFfUK8sF6YJS4REbx8Spk/mkO+vQdBfYLhF+xpGDGa4M BZUA== X-Gm-Message-State: AOJu0YylhX4xoAAlce6/jBwHfso3LAmYUt3EAKgvxwQTb8gH2m2MqySC oe4QELMTNTe+LCXb6y4FuZYw46ASR6boQwbWeEfdrXCPHxGeG5zVnrSt/QcJRHTetqare1ZdSzj Keks= X-Gm-Gg: ASbGncvrIPsGT7Qa8Rma7ZSwvJFWce2nbAghhLCrrClvGXamog58TBKxyGVYGvQrZOk c7rvlNgt48fb4hK6wWhLDengpRreODQk/YUKnIL7xe5FeLM6eusPAF+/dn/W98tAe9IITppejUg JOFeQfDXuiv0jKhJ/C2wHuiox2uFTBbG8Z3ni/oNAYDu388ZdyFPgklrjcAVs227IwLjaj/aR+W 3FXAXH2KSpDneyLWgMt9a5/j7tYlQhuf2rvLZAQMFGdYuPc1djsihswiAwQZj1TYfxf0ak//kH9 OBmDf+EKigogtCpTzo17mi1IhkoLLcS6ADJVKW4MjZzTfEIU2QwEtHaQvKSha5FSDYmZF61nEBT 1VGweZw1aw4eX8+j+ X-Google-Smtp-Source: AGHT+IFnIa5Vzkwp+NrCLiYHECs6dxK4Z03yCu8TjtIilL3N/llIwh4nOfWXwaWGVB5ZRK5uRNfWyg== X-Received: by 2002:ad4:5beb:0:b0:6e8:ffb6:2f90 with SMTP id 6a1803df08f44-6eb3f2c84a7mr3911886d6.11.1742493398805; Thu, 20 Mar 2025 10:56:38 -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-6eb3ef1f82asm1132856d6.32.2025.03.20.10.56.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 20 Mar 2025 10:56:38 -0700 (PDT) Date: Thu, 20 Mar 2025 13:56:37 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v5 05/14] pack-bitmap.c: teach `bitmap_for_commit()` about incremental MIDXs Message-ID: <8fedd9661497c4f74f061f55438014f2726d199d.1742493373.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 e84211de15..17f1087fba 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 Thu Mar 20 17:56:40 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14024275 Received: from mail-qv1-f50.google.com (mail-qv1-f50.google.com [209.85.219.50]) (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 429FE226D15 for ; Thu, 20 Mar 2025 17:56:42 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.50 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493404; cv=none; b=iyzzku/dhm83eH8viwubGm0LyircWsi6hK1wwnOPkVVcjxAYcRA7U7/J0ZL1fRWWjc6CY5BrnZvM/GsU2B8GyOU/ucM2OJCgE2Jay8Kib+8RJk3qkpRokKpoLdMlmcobOUxTv1C95FXgVfpu0kmcjw5zR/O3XzgeQB/+lnFkB9s= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493404; c=relaxed/simple; bh=vF4WlOV9bawcZjc0vNeIB+6OF3dMVBLiaRXb514GCPo=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=TEwqA2O3I8bL+MgTQwyfDfxvA+du7CcYAqA7z4KUCNvw2efwf6UvZHX0OOZghpF7Hc+OGFuvm/ZtpRF+ggaq+V+UJKP0oz/bVwkIJ82kI8kjcA+v4X5PIPaEhK77bNgibOcRYBG63GBtJos7AXHqaWHtPc9nfGiBovnsNCEi8nE= 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=adUQA28Y; arc=none smtp.client-ip=209.85.219.50 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="adUQA28Y" Received: by mail-qv1-f50.google.com with SMTP id 6a1803df08f44-6eafac1f047so18338606d6.2 for ; Thu, 20 Mar 2025 10:56:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1742493402; x=1743098202; 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=FtPKtDait40Au1zUqhsov8C0sfX8Zx4r0DqaogDLTBQ=; b=adUQA28Y6FDmIor8bIperg/adm++B4jH3URBcxiYClaVtgcmqV9QjhpUNCt2jCnNgc o5xftQPiRg3ZQ+6qpGRbm2xuCyUFy3ae40N0McxBgLt5PsHxpX+fQVjbb1QYy4+Q15lY J/Si1xU1sUyu0WVuPdBnlNQhWbCvgF9BPKrjVVO21RCUS6lvO5oubjPEBsmVGxOGzbyF G5hUlZl6dXrhZCU5UsRg1qTw+uJZkAfvwN8oQTMgKljLPRclf1ItHbtxzuh0g/V3r73W R2umETxSvEJtDzINI+A7VAHztPq+kPzAELqQ6c1SqKkki/PxJJLsaV4WYMsomkbwbqRc YG4A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1742493402; x=1743098202; 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=FtPKtDait40Au1zUqhsov8C0sfX8Zx4r0DqaogDLTBQ=; b=jcIk7RPlmDm4DWYQoKnMoFEhKhNJ1GJWy7b6RmapfiYz2M831L39zzZ8s/+EamJsqT 6//9w7qiSr63C6zOIbJrdUgUMT5SLXPikXylN8pmfQh//bt5dANdaLDxEzK33l4X409k +gTpMyyzSH81IQh6MMCIhdN8+MwIv1ouW/Hk+RXVIIVuYkJXsZ5pGIgcE+fa6NSGdUSs it0Q8M3K2xWnSuXd2bbywkDskAzfqKlPUHv2aYwaEaCQPy6K7PoZphQUF5cC7/Bez9lY nZ4udBes1wI1wsAc3/6ap+g+03C4BWbIjnCEQu3oujRqbuJgNPZHqi75aij23vxfT5bh sZeA== X-Gm-Message-State: AOJu0Yw1m4PfWcipMmgisQCLfbrUK+qtzLKMPFHvkSeTTnvaLdaBCGTa KybqwNscsd5BjlyVCoiMah7ws604KC4rQGvRTWxGxOtDgld4uERj/+oQht4De3TmCYnvBlJiC9i sF2Y= X-Gm-Gg: ASbGncsNBtbccOiDOXHyS3oPUMtj0HoOgOi6K3l4YasGwZvJTCj93x9wFsN2/YcO2wJ cKZFNQi/lwlZeDT1OVczCqiUzVY/Qkmmvpr6+Kgsv3yJvWOnCL/9Xy1EjiJrpIgBaBHZKRXgA3o 9t/GycBplGIWvFAtE55ZdgiYWmVwk3ya0WEjHA5z4gs8qZ68bn2y6V2hhEjtJfvPMnVCvwEjgG+ Y9d2JWOd27QjTAa31vQQnihkzPSMqj5ZcMaFpiJJl01vSz65fc9aO3oi4mFr06DLSlV5iAFOzxV ERDZfSpI58qSClpn0tde4dWnd5POoYyWPn1P/ZMxLZuP8KLkXY9H31U8DkHJj1+FCCbxfduoBLL A+BYNJ8FtTG1xw/SG X-Google-Smtp-Source: AGHT+IF4Z5t8VgXEv5gwyO1d/SBbgci5YUQkGTpMVE2heJE0oRJohjHHVBBSjGRO3P3RI29UpSq+UQ== X-Received: by 2002:a05:6214:2a83:b0:6e8:fbe2:2db0 with SMTP id 6a1803df08f44-6eb3f36c234mr3962456d6.30.1742493401953; Thu, 20 Mar 2025 10:56:41 -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-6eb3ef344eesm1122456d6.59.2025.03.20.10.56.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 20 Mar 2025 10:56:41 -0700 (PDT) Date: Thu, 20 Mar 2025 13:56:40 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v5 06/14] 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 17f1087fba..f3ef9e43ef 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -1636,7 +1636,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 Thu Mar 20 17:56:43 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14024276 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 28EED227B94 for ; Thu, 20 Mar 2025 17:56:45 +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=1742493407; cv=none; b=MjqSTSOY6Ho/NE1WvCJUhnsFFgwX5l2aCuQoVd169jVe9Sevun8IsESwmJqvjn3wHoqJuAw8+onNaATFoU1vtTGjLhyyJRH0wVKbKRKIt7zD+7KHoZeyXS4d4aQBneavu/dLU9GGRZXySGRSlUs1h5QCU4+7Ojna6DpD4KHuqa0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493407; c=relaxed/simple; bh=w+FWzi+d79JHyFNvK19jyyUreyXv9q5+YLkSlVuvIb8=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=YAS2Df6Hj0Fjyo+H3dksanZxohYfsHOAxy/mmDW6TaTTlmgWhbBskD3HzhVieKYXlCTA2di9Jtnc74LjUfk30ksZ4rbBq2ULdtpJMGmEaO+w6YoXbZ7NcYnT/P0bOVV4NZC+YSYClxb4vdTJYum9tB0pi3C3NW6LoSP6fkLT0E4= 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=LnJGrlaS; 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="LnJGrlaS" Received: by mail-qk1-f170.google.com with SMTP id af79cd13be357-7c54a9d3fcaso114009885a.2 for ; Thu, 20 Mar 2025 10:56:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1742493405; x=1743098205; 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=uHXdBU51oj8/+AmU79u/pG8c0vM4ZJxhjUALWOOkKUA=; b=LnJGrlaStlDMXRnxz1xsPO1khZKh5iKW17jLE6cD5L0uFRGJ7eXxxc8ldg6HqyKl2a 2WvBFb04fT6Vjlg6hLjzcp0+sp8i4ZZhXgKAQ3vTdBMmpR6AflJ4BZQch5dyPGqmpoe3 PHldPhU1qaRqjB5k6CqkRqjX+HOB3N4bCbpP4wozYvad9e1zHdEEDo1sn7ratMjASG0I 3qEvpJvX7EnlDaKkdhXEV9BMLWOKYBZxoG9hM/XO1MPYO5k3jA4jMe5zq7+sbF2RccM1 XL0y4MQKfacVoo4oaxGBWIJoSsrnao2M32CcaNSPen9srfnyhOBBKmvu/1YM69JFDEsM L+fA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1742493405; x=1743098205; 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=uHXdBU51oj8/+AmU79u/pG8c0vM4ZJxhjUALWOOkKUA=; b=FHJFpH/B++RFgYIDSqcoXvfuLbYvyFYT+bhmVkTCcSQjjhiGAf1gYotCWDsVNiBqCj 3MzjpqfkZ7z67+lBpJsnjtZpluQUGVaJK6MLjqFOfvIgnAQYC58fZPLpovAsZeqf/Kt7 Al1lCJ28WFWT01qCo16CIyaT71bOLvIjJjZf1Qi7wgzxKezBvoFODVVxKeiNzpQ2hdo5 Fa5QrYt+ydAdEXn9ZM+9H1PNnwFP1RozlIl26paYEmyRijTKf9dmV6VBUPdHSVcXxj7M J2Ou1U3CdSQp/8ZFABqdPV+BAUE7gwm52xvHkiC4KGqtXTCGlR3fpMUxZEINCn5xRIC+ 298A== X-Gm-Message-State: AOJu0YyYU47YEoSxo0CvINB1YS10R143LhEhmnfiWcPJPtDugMY1LDGz uJqZyn6vG/PsysvxH3MzpNb6I8we3/jRtSw2aitH7g0JnVA+iPp09FeL4T1ZWaIUWoAr8W7rHcs MonU= X-Gm-Gg: ASbGnctV5pCJ7CiVXmVNg2FPZzs9reL7edqN7PY0Klx21qbt+BrXlxo5qhOcjpechZG m7m/66HGAreEL9RUt8R2BP13uL7z8v+Pdbn9v9BKX5oZEzrTLrcLXAY7kPApBQGshW9K3+qBiKy IoMS5cyIL7BavpqPd+Kl9TaDeHJuvXNcrwjJhuKr77fuVpOs7ChqtzhugTjyJrmNz7WoS0h4Imp 1YePAwTT0tjCJxWHF48YuzADxfEA9P6abo/S+Jnp0zroHcAO0oJiQZcjD+Sv7I/HU0uNd62h4+x 1LtrkA43/MynJEmfEN+18Od3ClZM+ZRCv/1G9RyWLCr68d71ZB4Dlxk6+dx8S2McfGf6NLAIU1n LFdBZ0bM5SbtC8dOK X-Google-Smtp-Source: AGHT+IEHRZouOC3s6ZA//vtuALdzFCyDz5fnCkAl+SdCLwbhfrDg8MdN/vbUV8qawwdwq9OVXn2ihg== X-Received: by 2002:a05:620a:6089:b0:7c5:43c2:a904 with SMTP id af79cd13be357-7c5ba12cc3amr19180085a.10.1742493404924; Thu, 20 Mar 2025 10:56:44 -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-7c5b9355b19sm15177185a.109.2025.03.20.10.56.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 20 Mar 2025 10:56:44 -0700 (PDT) Date: Thu, 20 Mar 2025 13:56:43 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v5 07/14] pack-bitmap.c: support bitmap pack-reuse 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 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 largest number 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 f3ef9e43ef..5ff1bbfd54 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -2335,7 +2335,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"), @@ -2361,14 +2362,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 Thu Mar 20 17:56:46 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14024277 Received: from mail-qv1-f52.google.com (mail-qv1-f52.google.com [209.85.219.52]) (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 61818226D15 for ; Thu, 20 Mar 2025 17:56:49 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.52 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493411; cv=none; b=Obfp+bxGj1FTQBkzekv2JCgmutH78JLGdxx6i8ooYMB1JEAYWiMfV3RySchIaq4Rs4eUhl4ianRxoHqSczYY/XcnFGWCAbDcv/IfJgu6l5fjqquxoUDmA8mmRl0lynaiWdvhYuipeDaZzFWvPTIxjRlczXkYFzhitbly3f2UxA4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493411; c=relaxed/simple; bh=e/swQyaGBSuYBv/vUkxE0VVD96fVnK7K874+NJc1u0s=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=U3Jcnx3J3LUoACdJ2PnJvGJoVFKAWhreTCzj33Jx1ma91wGaEBCufIfApSD69cJ29gIgNnIAs1yXAPV+pkrLoEkZVywyXwHpAKcmFL/6eSsENvGOvmIdtlvU0shlUgUXAYInAk81+6P+opL+Vd20kO+s2qACkr3leAJ9NgHe1hA= 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=V4t7xFTr; arc=none smtp.client-ip=209.85.219.52 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="V4t7xFTr" Received: by mail-qv1-f52.google.com with SMTP id 6a1803df08f44-6dd15d03eacso10849926d6.0 for ; Thu, 20 Mar 2025 10:56:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1742493408; x=1743098208; 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=ZO5Yoa/oX4fnHaQ0thRBTiNtX94aLzclbBWwjOYbegM=; b=V4t7xFTrxDWckSyMqvEkB/EcMKZRfCCXDy/fYKutN/lGUNN80OnvEAK2QS3wxTyxsF 5F3WKuKcMFQ7KooHDBMo8FBJZynRcg1DQAKQlQjoBxxhAmnbqmYhbJLEsdyDDskyWSVn O79hdCpqIPl3g8YK/91VRhXj3SuvddWLXmu3eLA1HVNHYwlsNxQPx6cQuNYOdHrJ9YsO X925aUqzMhkhmG0AMsg62gdmG+DcdNkXQYlm+qN1K37T2lETyWMQV6k9h0//aVSqipRh FobkUj6rPYeImCfBr79N+hBdxs3ILsKKS89V6Wh//CUoo5B2jiIEdsTD2MvFCtVzPx1z FrkA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1742493408; x=1743098208; 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=ZO5Yoa/oX4fnHaQ0thRBTiNtX94aLzclbBWwjOYbegM=; b=dcLbqkppnHiDrWK7T3O1ugrVn548ymKutpP9rq8OIjGFWyXjdELK2WI8fGcaOdJmKD FubXHYHcYZQi1E558is7IWm5vDqMNHiImWIBp40CdGX/ZLaRhC+vw2dXLE/gWfCH07Bb DjQ1jcVN6mLcbTIdnGQ3Ei5lKUSvf6HqRp2019L04Mc5VEoD62gJMx7obe/LOtvvjWmr HV72nn6DQsBokAxHFrA76c6fZ01Iok52pcTwWLp842i+ppnMmS51ljEmkadH50kLej02 3GKLsmTm2jZeWV55XuukxGUfYN3ZqnYA/pSJK2aQb51Sxi4zfJ6MewJ3rnxmfC7TVG2T /cqg== X-Gm-Message-State: AOJu0Yz++coiY7PDtWhCRwu/AqYB/7lBHg9iQBgpL4SF6mKWYZPXCKxO jNqSGXBWKg3ZOcFVIWNXWTLAgRgHBVT1IDYiTs++OCRBTXYocH+tUmLnUS/XuE3gdXtnVvC36xk BtK4= X-Gm-Gg: ASbGncvIlYTSe0xK6eYV3QGdYhYWGpc4o7SM+ifVnoPj0rD3HOREDp2f2WW8FkmCaKP txOblXdimBqAvNhPZ+CO2Q+c+b40SgTorxV5ep86xYlOQVK0rAScw38rfpZf1ig8cZhn+1v9y6E VtGPC9oShtQn9Uyf8IYvadi6rzMKNG0oDlLcEB9zAs6h4xFEFlGbSdN0jJCQNwvmvaIZLPGdGVk 7oIaeP7742YJiSEKdD4abg+RM9N0l3nGFMGZqI+Tivya0ihAFpM6DOklvHi7trELaSQqF5dBVnq sp0fuipeDrcEISLuzwHdlT+1Ccgj/dVGO0dmB9lrG3nIcdDCndkip7NH/tv8EoeoGPGACKQ+QiX 0hVlKQNWZ0ykBlDSXW18Z5TfKnsM= X-Google-Smtp-Source: AGHT+IEp8tkTOlot+a5uiFNBKG2u6vWaVTDggJs2Nu5MN3AfwTjhhne1BmtjLZNs2taR0Mk054pezw== X-Received: by 2002:a05:6214:29e7:b0:6e8:ec18:a1be with SMTP id 6a1803df08f44-6eb349305d5mr57095796d6.7.1742493408122; Thu, 20 Mar 2025 10:56: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-6eb3efc5aa4sm1055756d6.71.2025.03.20.10.56.47 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 20 Mar 2025 10:56:47 -0700 (PDT) Date: Thu, 20 Mar 2025 13:56:46 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v5 08/14] 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 5ff1bbfd54..65ad631ce1 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) { @@ -2513,6 +2526,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, @@ -2521,6 +2536,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++; @@ -2584,13 +2604,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) { + tdata->base_tdata = xmalloc(sizeof(struct bitmap_test_data)); + 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))) @@ -2599,17 +2663,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); } @@ -2626,16 +2701,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); @@ -2647,11 +2716,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 Thu Mar 20 17:56:49 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14024278 Received: from mail-qv1-f42.google.com (mail-qv1-f42.google.com [209.85.219.42]) (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 5C0E7227BA4 for ; Thu, 20 Mar 2025 17:56:52 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.42 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493413; cv=none; b=ESQfUIlhKug4N/CcmHwEX/YNGjW+Cctw0AnHIIMqyLZWnUHPSgKWw68xmXwBX/pirNDjD/5MA95p1lzfJEygylH87+RtEh8y4WGVIKVLMS1CbgzaZU3/WPVKZ4GpoJu9ysL8E+IqhAmA7kPMe1gDizrRScXwU/HIjerINJmGvWI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493413; c=relaxed/simple; bh=eHl+tUd0SY8aMC9cemyOrg5u0gYKk01mG3U8a5l/Uts=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=gUMCq60qTT1aFbfBOTFDZP9PvCoYHMbF5tBpRW95ppa7/FqpG/MgLeUqaObCTPyhfq52n2fRs+jZvrX3PZlSEYQrR1XEfwlqFMfHZJeeOOPT2QacJgSxyc7ywl5ZI21eA72ycaBjLp5B3MuqoKyQA0uOG27sfEFDEXRtEKW8bYQ= 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=xKSVVFis; arc=none smtp.client-ip=209.85.219.42 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="xKSVVFis" Received: by mail-qv1-f42.google.com with SMTP id 6a1803df08f44-6e8f05acc13so11955996d6.2 for ; Thu, 20 Mar 2025 10:56:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1742493411; x=1743098211; 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=tpast4GBJZkw6YoFfZudb25tTY1DGiStVgtvFabup4Q=; b=xKSVVFisIks8STVygS32xoEll4DF7Xc9kEvy5g/wZL15y7yXkNwJslpNwFZ3MPOJ0Z 9iKOQo/8/k5NKNOXxmLMDsp1MpGJzTxad2Q3s8i+mcT0AuTOh+ycIL1IiiIizQL+Tkg1 rImKs2EonXP7QoEzPUQT9XCWevQkibxETd1SiAs1rB/1FF4XGPGE9teOXtIHU1gNTJki EviG7U2sQmFxo1kLoYEwl7yXEyi2VEup/Xy5tleL+KRFuTGLD+oTDIiOzUMcUL/xkjrO aITRd/07gCFhv2KYspwQoKTYelJ1aalCZliuOTuFDn3NpGXra9kLI/BGaP4lGoegvOvR C2Xw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1742493411; x=1743098211; 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=tpast4GBJZkw6YoFfZudb25tTY1DGiStVgtvFabup4Q=; b=gY2F9rGsTuH2IUWt2r9MzbqD4yMvAQuYxD2Ysx986PjVy6UqOZKdM3b1wlcMtrD31u HGA/AbvrwIRE3PS7K8TiFcJMrwaljqEJ3r/unx1XpQCtAdFRpw/saZL+EeLQ3vSUosJK QMbSiwjC6FSUT5CgA0fcNAfcjk/PdxzT2kWRhZWtvfA8X8Jla/ou47S982mlBvOd4auG zpNplV7/p88JKI/L4h5GxgL1PoTaro2e32MhVrIz4Zs9Sitc1VThOCDYcaMuj+Z4h7vp khaOMmURGsfZc1Ewi91bJCnUPbN/3s0V+wFx01W6Uu/wN+/sHdvio4v2D3K8nYGIMgzb /kBw== X-Gm-Message-State: AOJu0YyLummUD6TPM628dyGJ6XEhkFyCZgXtPzDq3IAfmQ5pVJvWf9wO CZcaQ+2QagPVBry8VQfSdKwlwfJFB2PIKjv4hgM6TI4PtxJGn6gMoF3IBQ9tr9RI6muxUNJY6E7 ldyg= X-Gm-Gg: ASbGncvbKRWJ+Uyv2sU1Gg6WZBVtHV/CBdKZo0OuuhhA8pUEByHoPbdq7YG3ePYZjHT ogATExYsf37LY0ZOsP3+lgPkC+Ty6qMUfIjedp9ej4p7L2Ejt32ZC+Uy/WJnzUWeX46pfmsyn60 zH5kwBFB+70kS1n0Jj7c+W6yF6Ffibb1JQ7FlULewyI59x5l3YgiaeG6r6KemDfifNWnEeh2Kye K7MJq5Q7zbeYbbh5ZLkfACzIs/NE/XuV7jpIbF/N77bjleEhef5ss2JnUxi+w09XUNHCu9L527T ZvJEhwpJEwfek67ZTI3ixd+CCMJ7WVf1thQ8hqfER/ycNZ/Q8iJ/i4dSlyj7/FO2CFKZ1atRi8D ZUI0k9P5TIhY4L/nLFkB9/6C53gE= X-Google-Smtp-Source: AGHT+IGSXhSREY4oKrydLB8wPk38yGzAQau6U94xVxx/r9DnX6hwDiFEWmarcCmZdHr1nKZsyHcQ7g== X-Received: by 2002:a05:6214:1249:b0:6e6:6a82:4989 with SMTP id 6a1803df08f44-6eb3f39353emr4695636d6.44.1742493411087; Thu, 20 Mar 2025 10:56:51 -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-6eb3ef33e4bsm1121006d6.53.2025.03.20.10.56.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 20 Mar 2025 10:56:50 -0700 (PDT) Date: Thu, 20 Mar 2025 13:56:49 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v5 09/14] 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 65ad631ce1..4086277de8 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -1779,7 +1779,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; @@ -3049,7 +3049,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 Thu Mar 20 17:56: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: 14024279 Received: from mail-qk1-f181.google.com (mail-qk1-f181.google.com [209.85.222.181]) (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 C5008227BA4 for ; Thu, 20 Mar 2025 17:56:58 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.222.181 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493420; cv=none; b=dffJbTGk2U9H6ZddfqDOZidah88pTrG4eszGoSih8T1hn3lliDTc1u4U3EuY1OuuGMn4Cb3fvriChQJohyADBPavqmymtZdPYtTkq1Agmb2Q9m+yIu6ToMZw6nMlUZI8Qdj4oO7fCJ+5P6Kh/IZdbaPdYoSXzV98rqGLqeR2F44= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493420; c=relaxed/simple; bh=YlLB7/xYkhjl7q+m4k6TmRGshg2jAEQ8u6Df3LLcGp4=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=ixpjOd35MTnthgxn8YmW7eSP3tJtEgbaMe2m+IKwP+gvVA/6GsgvqRai6rpk3vMutogq9uAPTObgmjdMmrLlZ5aT1KRGRMPi30+yIa4huQMcRu2aRVaH/x/Ru4M6h9+ogaBChcADe65itAxYuK+SPFJvobul2N0gKjmW2zZ+8mM= 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=mb+DBpM/; arc=none smtp.client-ip=209.85.222.181 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="mb+DBpM/" Received: by mail-qk1-f181.google.com with SMTP id af79cd13be357-7c546334bdeso86893185a.2 for ; Thu, 20 Mar 2025 10:56:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1742493417; x=1743098217; 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=JDQIoLoAUgXTqiT5jBUIoin5F22MGC/vCDB/rmDZyLQ=; b=mb+DBpM/zY1av52vkeEMjIKcryCyRD6zKWo2HcLgQln3CwGaIycdxslozq/S5QQ5i5 VDKEjFxOgGf7OJbrwdN7S/udSRZc4PQfaMZtRdK1Aa9WuhrKc7EditoNHJAv3ZKsfM42 S6VRc4HrhVYcJpHxQ0JINCVWQUViKsk/mEFUHbju0azFcH0PhAXy684MNHw0NVrQ3gn7 r3PVk2lojIt3Sh9/vj9A2NudnGfo50LnvMapLOKA5DPBOgjrCDT9mA5BSqAvqKhBlYW5 Xhg/P2s+pMPc8CR7G+5bDwXO3ifzMlcmxxutf8lQBz4wWXsTh1PhjVdIqZXbtseQBM/i y/Sw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1742493417; x=1743098217; 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=JDQIoLoAUgXTqiT5jBUIoin5F22MGC/vCDB/rmDZyLQ=; b=gdFGwS2iedpX12C2uyc+SsSSClhO/wGAitadRwUAdVFyfi2ZmtrWmyynU+zDDHoIZP OPy7dF7WBAoOMOiyaOGVRPU3x7RJQXXe55s5CMYJZtFOOwLkUkJDPdR8TWzO8gykMkdv QzpdRVpCw2ALnvcZUJLUglo2cAljJPedOXJHt1ZuJa3+Zx7plANoYRC62+PeGDMxHH1I 20ogVVquErLB3bkwCWj/JiyFZbDZWnqzGsQraz/cIEH6qok1xH4/faJs+YzNm1VnaPl9 AbBw/+vupd5eSPuKWdqM7F85KNiVP71x88/BDZ/U+sGHczz67RQxt98EuYquikgoF1Cs fd8g== X-Gm-Message-State: AOJu0YwNquKPcnPUMX8py2H7ZiY+clmzs5fqPrwn0zSY8I8zdXI9y77Y HE7T41y+TuKRxWQwOaWMlJG0cuAB0U5hxENyS7IA8zca8n8ZmstJBTa3BlK8MPfOUo/7FsPDA63 mkM8= X-Gm-Gg: ASbGncu/B1AV2SZ4atJW/CRpotjEePRzcLRZ8eJWvND8ZIqcHUS+uKkW8KAWmqs4bhc 0+51YEMSlWajp30RatfVN6JcyKCPQnrZ+anuTn/mRMyG6Y+rvFWx9tTqQDsfkF2QYAO0526IRgM UvDPkxgGW1KLA8UXhbYBsUXqBLIOPkJ+abXKIkhZYPFDc989S9orBEjSKEvuA7an/Kxx4aMH6w4 IYcqryV6Zvbv22P9S4fjKVHbrWK+agmmQVLfFNjhq5K4/o+q9nI2NDesRuIwti30GlCXrp8I7XY tH8IlHdEQ25dO2rX4ImuVo2hCP0pAqPUI52rhA14rDS+7HNQS5n41m+n3n6CqMDD2Hir21xTxzl xiGpBrYEEoULflFGx X-Google-Smtp-Source: AGHT+IFTndx6RUr2DePd1XoRyUNZF8StSHm+Fy/t2fDB0cC8rMcd6fckJx7zHo2YvSJnBMj5j4bimQ== X-Received: by 2002:a05:620a:8019:b0:7c5:3b8d:9f29 with SMTP id af79cd13be357-7c5ba15ee0amr18715885a.21.1742493417674; Thu, 20 Mar 2025 10:56:57 -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-7c5b92ed0a9sm16158985a.65.2025.03.20.10.56.57 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 20 Mar 2025 10:56:57 -0700 (PDT) Date: Thu, 20 Mar 2025 13:56:56 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v5 10/14] pack-bitmap.c: apply pseudo-merge commits with incremental MIDXs Message-ID: <7477a8ac03737afcb42c54739931311539eaaf8e.1742493373.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 4086277de8..1d1e1a65ca 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 Thu Mar 20 17:56:59 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14024280 Received: from mail-qk1-f182.google.com (mail-qk1-f182.google.com [209.85.222.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 57A20226520 for ; Thu, 20 Mar 2025 17:57:02 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.222.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493423; cv=none; b=Lwki1GUzRKfotg+Myid9UfU/nrvjkqUEhiKYhNffYtdNuKueOl0ByPgVIFGsHg8kTIRyJFoiYu6ey0O8Y38Qu238IbErc/MgpzUt4L5kXcUZ6uI8AWd8HIcVZNeip97swFklunI2VHm2/oY5VQC3lIyyQz91c1a38GhUCLAR8SI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493423; c=relaxed/simple; bh=vU+seeiUhq6+boGZW9tWtB1TL6/CqI1cewhnjEAMIPA=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=o8Zd8Dp8vR8XDhU0sjBLuM4xkbhMIfxLqcL7hARQWRMdC7alqxA9jLfWXZhtPYlguP9DxcIrgz8w2kkiXqbuI7FIEd+YyxA3z3JHlmqpf0GkckwhzAuNXRWhVkYaHcUBcTrgH8amXsh5vhj+MNYv9HcSScBHG7lvn1YC7z9+Ql4= 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=BbUZbxhW; arc=none smtp.client-ip=209.85.222.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="BbUZbxhW" Received: by mail-qk1-f182.google.com with SMTP id af79cd13be357-7be8f281714so141851185a.1 for ; Thu, 20 Mar 2025 10:57:02 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1742493421; x=1743098221; 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=nZqE9BGm06SVb8mpErQU75JgleTZK1unD+cCdMUkCTU=; b=BbUZbxhWExr83pcPTuy6+isIMKsglqwtMiYnc272+ApG+qXn4aK5fkxy76WKWuN1uq zqC9C2sE2HuGTYzIsFSGJGV55UjaXP4UBDrnuXlNbdmz88O8gnQziVlQRMCfgdQUem8u czZFBRaKpRn5DM99IjXuKya/Cgh5JR2jwLjzxaXQwTIEETN4t9mHjBL9Mn9TPi7mjjlL CR4ZmRJELnUglhMkZhoY1cEMNU6OeXRVl2fJGKJGi0Vj5mxswWNdV8SKAhIsdtZv1N6X qvzZ8rvt6eCB3G6PH/j6TJwor5IzFml6Sj4F/bneZvISF8D0IfoL0flU8/vcaoZhb4rw BYdA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1742493421; x=1743098221; 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=nZqE9BGm06SVb8mpErQU75JgleTZK1unD+cCdMUkCTU=; b=oSXQuF9xSA2gGlAq488jYfH0Xmz+3z3sK3ZXSlUh1Usvz8LyHZtHbDxlv7ho6qNSAB rE6D0kuiuH9dVb+lw40or3V7uWZIO/r03taFRCpO5lIqufHVLNjIYCZhm4/dUil7tr+G k9744xckN5EM3TYEg9zwgozgFE2dLDGAx17RzoJpJoc4jEK9Ph9ex0NxnlIjPwazkt9z POTKFDNY8LVwl8EYpZuJznLei7r9Ci+bPtJjVZWbjO3C/NUl8IPO34n+7WTI83VBI5RH jNIIWGhMaTyxQwjPN5u83TI4Vx6Aped7N4ZDlmKk+SLWuUWMOgwd4H/VrfsFTJ/GtW9J GcnQ== X-Gm-Message-State: AOJu0YwdHTkichX5DuqcmxafC17HemMTrLsbAvqnwdC6jOTTkilwoyKo 4zdHtyMsWVgDC1BtPgRfG+RyRlTJ25BTmfzb6AgbFQKKLXHIrqd3kv7PfvlJtkp17QoEFVDJRSd Gj/k= X-Gm-Gg: ASbGncvCfz+cPqTZUxzBSDRhWlKhno1H1mdV/UKw0/eKHj6YjddagwHX2M3cjqOvprL h3WWmjeUkCP6Eqw0ygq6MqBX6Sm9ZkHFUJOyx1CMjycsR6Ya/H4j5BM0c1EMXznurfp6+jDFnKF xRjduNtAFnl3jIwmDA5LYVzoWKRxF41gz6mINhwFu2qAHcbznn3A15kw8/tFS45xQEXAdgj3Vn8 O2gr8j1KeBHkzDB7a6In1JKnnJNoWobzmaWc0VGyLqcPBk9/TJ4oNP4dPeQ0ceSH41rCoZQct3E nrGa31pxcR1zqI/X5a9aNcLT7f2d3uAmPDc+nigeQ77z9zhKy4neVogXCGTobpT4cbtCpAAuuPN Tqo6BxwGAdrXIJKjGtQWMb9+Tx5k= X-Google-Smtp-Source: AGHT+IGn3/A4SgarqXW9pdmqUGVacEB+verODEBwrWFK5smvDhw1E1u1LoDl6C/oSZWiKA5GMfwAAg== X-Received: by 2002:a05:620a:394a:b0:7c5:4a6c:eb8d with SMTP id af79cd13be357-7c5ba200eb2mr9988485a.58.1742493421008; Thu, 20 Mar 2025 10:57: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 af79cd13be357-7c5b92bc0e3sm16599385a.8.2025.03.20.10.57.00 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 20 Mar 2025 10:57:00 -0700 (PDT) Date: Thu, 20 Mar 2025 13:56:59 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v5 11/14] ewah: implement `struct ewah_or_iterator` Message-ID: <0fbef17acc7fbf49fdb8b61efa2320bab94e3499.1742493373.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: 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..056c410efb 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_release(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..c29d354236 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_release(struct ewah_or_iterator *it); + void ewah_xor( struct ewah_bitmap *ewah_i, struct ewah_bitmap *ewah_j, From patchwork Thu Mar 20 17:57:02 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14024281 Received: from mail-qt1-f173.google.com (mail-qt1-f173.google.com [209.85.160.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 997B5227E8B for ; Thu, 20 Mar 2025 17:57:05 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.160.173 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493427; cv=none; b=g964bFZRjI9d7mhbDmWd+DTt7uySW42Lyx6RFM4Xd3HddlMR+6UVFZWkifDrVV3jUApPHOMk9nUT1j5t3+aqinV9Uzr+R9lBqf9U3tzcfjJEIY4+bwBSqRggn++4Uvd0lUmxAaEObzKgAevemfSzGAOydCvw6AV7DlywusSksFY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493427; c=relaxed/simple; bh=8W/VW8WknwNEss3wDjHN7e32EAhgKCTsEBkUpjRBHIo=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=Kv75udvTFrGa627m3y4NBy+r1DztXi+DKxYs0XyT9BWKZS9CU4dQwuUdX7NkG9lARfh6Vm3/6315MLF947ZaANkbPWDHEI5KcZQr/OHVOL+I8coTqZ27F3ODP6nxJlKK58yP4q36D//Cc9bTWaHvWDh44O0cREKAi1JMRrQcvU0= 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=HESJa/UL; arc=none smtp.client-ip=209.85.160.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="HESJa/UL" Received: by mail-qt1-f173.google.com with SMTP id d75a77b69052e-46fcbb96ba9so2941341cf.0 for ; Thu, 20 Mar 2025 10:57:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1742493424; x=1743098224; 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=AVhFct6OQmEeFxN9x+GgMtP3qbGV7vjamGAjlpSqNQ8=; b=HESJa/ULAQCbDUOo2ns9X2d6LVTYLBsDRtnScy89SUtSHTDgvPmkOYvIj+D+3hs8ca aDUzhFhjgAVoxgBYtZ2txmWzx0xSOIYy5tVw27Pbzzr5xEH2tOSBkV8Ft1mzarZeyVyE cfASqy69Gg/MieUwZGgLF0R2+DgjFSJIvD0ysJAhwi9RyvsorwgrlXJWmu4gXM8AYaD+ jJBiikSrwLqWs4ktVhjQlcWQVeJ1I9xrzqQHqr5FbfbICvPrOyY0wiZcCOGEDrz0mOES rYzhKg1Q4UrzuW7KcPBji5XR/toT5NUWl0BQgJHjAxIYug65JAPvrXzwd5+MTz39VMgx XOYw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1742493424; x=1743098224; 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=AVhFct6OQmEeFxN9x+GgMtP3qbGV7vjamGAjlpSqNQ8=; b=EOhrPPKgmgNZo+k/CQ5xyRq14XpmfAAWRxX407TfE3IAsK+DcMnDCegRBSL2siidWp qxHgDKc86a42z6SHY7M2XJV2hElhunGEeO4UPT+68P6ib1fQJjkP9SpHN8o5mKc9HJIB NHwxAoik1y12+1u2IKHXr5P+tzHZHc0g5vfw2iDLGg47g25gIyFVGeUrR1mIUacS3rsu Qsc/MC5Syy0sZjckTXdqv4eonFD3hhP1CkD3ZRbk9dDCFtCfmuyCE2393gVGWZJwoYs3 MgDT9L38eCb9RG3Bv09GdXZcTIEDI3pBQLUxoM0tjGo5VNNl2JzBbJlVgX1PkTBuHwsj eLvQ== X-Gm-Message-State: AOJu0YxrG4NB/AZa/u0WA1EKM6u8b3oYdtSJvCRErmWdTgL54SS99YtJ xOpm+Af3JMQ9iVcCZDI1hh+U7OOJps0B0aGN7F1sTDAE1ZHQZVxp9R860PDyYTRwmlqjNxo09JN P1EQ= X-Gm-Gg: ASbGncvtD3IxDORHymJ4/U5eqlfmzxDOcPGriStutTBXyus6Dddkj45q9DcLHUa4cQ+ VexhA/6Hp590HJpWDG0ZgQC85YloLr1XSTi4Ya4iuCxklmoaLO1YET60BROr0GTz6w74S+fbooM 2ny2ruuRJg7NgM9PXk9//cujAgcWK1sewh425V9Jzmo8IEQV103yVRrraG6RgKn60M2jn+p0scc 9EAaZrUSYtiZbwBR7dioEvGVWggKv6YaLd+29t/39bLN9m15Ox94oOWhl80Iv8cXUovjk2Smakv wCfWjChA65nTFmFIib02AfL8OFFA7n7+S58DOu7mT/etYoaoK/x0M6mG3PbCnAd5tZUzSXDChus uWEVUwx7lCtkPXj1U X-Google-Smtp-Source: AGHT+IGZ9Qel95/MXn+JGCZ6HsrRQnuS+kFWMwMf+bt3Sk791dYEyj94JdUp6Ub47EwdVRG0nTyHVw== X-Received: by 2002:a05:622a:4c0d:b0:476:739a:5cf3 with SMTP id d75a77b69052e-4771dd607edmr3699361cf.1.1742493424283; Thu, 20 Mar 2025 10:57:04 -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-4771d18f7d4sm1516381cf.37.2025.03.20.10.57.03 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 20 Mar 2025 10:57:03 -0700 (PDT) Date: Thu, 20 Mar 2025 13:57:02 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v5 12/14] pack-bitmap.c: keep track of each layer's type bitmaps Message-ID: <439e743fd52e2023a2a215ce00703f6de1dea856.1742493373.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 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 | 57 +++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 53 insertions(+), 4 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 1d1e1a65ca..5721fa7a0f 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -81,6 +81,23 @@ 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 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 +598,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 +645,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 +727,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); @@ -2052,7 +2097,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) @@ -2985,6 +3030,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 Thu Mar 20 17:57:05 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14024282 Received: from mail-qt1-f175.google.com (mail-qt1-f175.google.com [209.85.160.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 8E482226520 for ; Thu, 20 Mar 2025 17:57:08 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.160.175 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493430; cv=none; b=kyGjVWEBA3DnL6sk5gnFK4vFngqOOmXaXIa0wHyCj4mEFnYy9LPDaVWQjfi3l9rFVx8xr2axcv8Exa47kncWnnIimLJ3LUdedMTjpt4jSp1ns4f8/5nTCoGg984vzz+9xZ3t+cz8KwULb0SGVsZTL3MuojSNxv9wuboFctwnDJE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493430; c=relaxed/simple; bh=/eYVYhOP5/zVzPfFH3gx2cn4AGkw7a1jcIUMvZVu6TA=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=gNwohfLKE7Qmo7amH5Frrw/PHXVvI3NG31Nc2BDASVgVYaaLvVdWkckg1GTxX1e7+mjhV7HGyzioKNeomM7Frf7T9nt/Jw21G5ih9jaOTtv0duOS/H2T5t8CCbgByur1BYwPwqtlWaeCDD1sl7YMIIpe/Eg1PqRfkTm/+lZ9glw= 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=P415jyBJ; arc=none smtp.client-ip=209.85.160.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="P415jyBJ" Received: by mail-qt1-f175.google.com with SMTP id d75a77b69052e-4769b16d4fbso5905171cf.2 for ; Thu, 20 Mar 2025 10:57:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1742493427; x=1743098227; 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=mHMLeW8dR6WFJWNufB4KeIXEno4jvN0jJc04K5IivGI=; b=P415jyBJOErdmSjA1xGA96a9spENH4bFMqlrgNBitGQMHWEyPtlboN9t32ZUZCEgZ4 gD2E9Pvl/VXWUKyHZ5VDAN/ZXWEKOqzYNK1jhWegZzHth5yypGTTJZZhcmGucbpso2dP i2ZFsznpvfv2oy8vA7QGyQbgeWKc2dQiMXN2fUz2uy7AZV83/jb9h6FTWQkZ1iqNiSED myrvKXe4u0cqqeBg67v8iC36KSWhaYBxJH8gM5JIBs1wiuoic8z1kjpsWun7HQFcNaGy Ln3/VIMWalNXQj0TDHHcCoQ4svVSFGQk/EHaScnsygKp114UMqYTrH4j4teIBixXo8K2 xk0w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1742493427; x=1743098227; 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=mHMLeW8dR6WFJWNufB4KeIXEno4jvN0jJc04K5IivGI=; b=WyhrUE+H55siT9hco3XdOr3I3woB4HsLm/Uc0/B7Sac061SBTRQVc8wtVeg2ikkHV5 Ci9R9g5bvOyH1w87kUPqipYRTHYvZbb9c4qz2SDAPynivKFzNvU73bNdR6fAQGJ2RAbW /YgiqWOm3/3Dyd/4dwaifC2QtinIKcxjjBYzaBrX2g5aqqnII5UTGrWhg7WgF8hNjt5G vwoJXz+Z9xVa8WFzpYFpJvyj0YMUkX9WhiYh8iVB1Jzm5dqo4SLAlMEq7/HrgbEYGkTv DEo2JrMbwtSG/LVTKjdcPc9YfimE8gPejIguFnOaeoN/NwFaqgEmkwmphkSbNkl9L2zb dVpw== X-Gm-Message-State: AOJu0Yx/oZinZRcype0nP2hzQ9Zx86CLa5RWth4TxCx3KkexwhJQVZKI +cypEts3Y0jGQc2p8CzzXhLdyVSyHCWxu7si9JmLbZWdFtN4o712MuxKPO3Nqd/eiYgELul1dMk CLEs= X-Gm-Gg: ASbGncvxDUl/nWNAbRkUil81AXrqAShrzbhopc7axvaoW0Qo1yuQ3EcuYnxUQIEIXlt tcG6MuaPZOguv+31aRKWMDs2pITeWa8AGGIdc/Tik+7qs51iLKj86JY6WfMz9XdGjACxO64ZksH xxsJPGJlsfl5Ef2z0hLEqV8O2kEwjGpfB3k0KGrTj2C+c/4FqldRP5KEUEwn2z4uPFukcBz+gab XGSy+leL5InOzKmk1Oh861/W6esx/3guG2XjZnh96wZJYpLiuGs6KfIbaD9i0Q4XFsbehlbzLQw V0EpTMVhm/a+bykWw/5zZPxZLxhtRxogTqNUgo3A+aM77HWaPk2lbAUV4rE6oHj9JY+x8G/0d7D Y2Js00j3spOzQbRb+ X-Google-Smtp-Source: AGHT+IEb1VBw0y+XOrLOfbCCYW405H6znJkxWQZSBERbTE5I8zS4tULVeP3+LHTC88YVshuEE4Bh6Q== X-Received: by 2002:a05:622a:5912:b0:476:889b:ac08 with SMTP id d75a77b69052e-4771dd6234amr4290511cf.3.1742493427331; Thu, 20 Mar 2025 10:57:07 -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-4771d0ad87esm1647871cf.0.2025.03.20.10.57.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 20 Mar 2025 10:57:07 -0700 (PDT) Date: Thu, 20 Mar 2025 13:57:05 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v5 13/14] 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 5721fa7a0f..6f7fd94c36 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_release(&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_release(&it); bitmap_free(tips); } @@ -1862,14 +1869,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; @@ -1897,6 +1904,7 @@ static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git, bitmap_unset(to_filter, pos); } + ewah_or_iterator_release(&it); bitmap_free(tips); } @@ -2528,12 +2536,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); } @@ -2545,6 +2553,8 @@ static uint32_t count_object_type(struct bitmap_index *bitmap_git, count++; } + ewah_or_iterator_release(&it); + return count; } @@ -3077,13 +3087,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; @@ -3124,6 +3134,8 @@ static off_t get_disk_usage_for_type(struct bitmap_index *bitmap_git, } } + ewah_or_iterator_release(&it); + return total; } From patchwork Thu Mar 20 17:57:08 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 14024283 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 AB7A3226520 for ; Thu, 20 Mar 2025 17:57:11 +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=1742493433; cv=none; b=aeJW1vGfAs48cCLizinkPNZ8eaZJACbCvTetqbh0gDC/wa4AUqxWlUWg+/wtHxt6GC9oeoC/5Uy6UJLYaMeUFJvPqucuXIaq+NKOPa6SOsYsn0oRHdXkan4LOc7T2QbCAr/pgwve2A9I/k2PyTlRItjkiXEBa0zg/C92Qn7yx04= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1742493433; c=relaxed/simple; bh=o9+BGg2BAJZkLhPc7UJDkCHZHAzJ1pd4jTBqQObC6iQ=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=i3E3ez4MTcJH8seC1S1H2grandx+O9eccK31Rrb9kBeHDQO69ufdNVFntx7RqD3j9SbZCLEwu5U6ISAeyb/vITFQLLvk3PWV7Z9TWFcWjW0ewHahYH0MiU9gROkcaNq4IJNbP9flODRpj8M3qH5I2vdvMTJT1S5nG+cis7Cp494= 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=ZfrrLeqY; 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="ZfrrLeqY" Received: by mail-qt1-f179.google.com with SMTP id d75a77b69052e-4769f3e19a9so6990321cf.0 for ; Thu, 20 Mar 2025 10:57:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1742493430; x=1743098230; 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=gk2WS6Ej0HV1rs0jz/nxfhLNsT+AmIuwPbZcCf3QfOg=; b=ZfrrLeqYfqznT8f74D0gcMW3YNxSfZajRmmB1931cFL4MFfCs2N1n2hrRfjpfU7MrY x6c91+VLpZ/llY6XxBfjlji/0vYgNxTF7ndgda9E0eheUjBI7c+dx9uyT2fZCgUcmPzJ MeOTujTMS/UZdVOXaHo2XAzBsLlX9Zx0byROEsUQm64y7BRtB5BzpLAVgXRWjsl3SAmg yHe7ZqXCtORVaOjgJkY0Obv71tNM/1YX38a6bywI0azOwqiNasmi6NFtAKlMBXdzTNLJ CH6FIXz1GP4NB+l5D4yl0FQirbWsuPZRkqO19rqx21phHp6H4eguvdUtg0wrc20zo/9u yElA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1742493430; x=1743098230; 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=gk2WS6Ej0HV1rs0jz/nxfhLNsT+AmIuwPbZcCf3QfOg=; b=HLqQtRv2gLQccuH30jHTCDIV9ca3PI80khRqiKx/xoynSmusQeqa3oeNxSmfUXWsTg XnSb2rhWJKNDi1/yyA11rywVgE7v4ieiESuBYEwqReWQrZ49gJyJl6TV71OKa6t8x1Z2 SsiUBjg+9kC7Fw9t8SmQP7n83zwUpUoSUjaaKJqZrT/etY3U2YNvpxoeIQDeNrIxvH8d hosBCfNjQItm3+DlFKRgsQLQcOT4qG75jslRIA75Y8MZu8rkFkUu2BDt77URgeIef2R6 UX5MvmtkZtb6Wyzwm7+jSEf3fxaXWQKxH8BMhGQGB50hNfejFbICrFAEZJbYX/3nAQyt guzA== X-Gm-Message-State: AOJu0YzzzkxSRoQ0vdUAjQYBS/YdmqAqpYYJx7qmj2+NMvTP99D2tAg9 qmSUhaCHq/EoQl8qVNAnuXK1wUPkVhY9nNkuw8rdOZix+2aKrut51oAl9dnAveiip1kKsaCx/bE 4UIo= X-Gm-Gg: ASbGncvfEchZQGRNis9FGOxUssoG3+71K4CSyglIEDyV5lHxXAyNGn19myX7Ku0fgwV 0tV606uqh8F5sb9OBnfSf+5/5kId5Hjk/ElGmWRn4kn5SbqYe4enyWplBYT5MwhcF4TYDuLYtSo +BIo2Pt5RSBeGDgVa3hSNipmd0zDTqxLmozoof1YL5Fjdpxt5dcd4WOI/ZyjIWnZ9p4ma6/s6L0 U3PclYoaQDawSh/23Ds+GH1CFzYphm/+rhSZVmz5hLYDVLq7uI6FKllcRsUrk7Gu9AAL/84tev0 aZd4mr2WFWyoOspMLQ82Oh2YxVHkNNo6wYE5ivI6Wq5UioALkrkjHhqS2E5yYLiWcKfuTtB7Y9/ lNj4AxCuR8YJHoOKTPJInNSsaFgM= X-Google-Smtp-Source: AGHT+IGR1b0d8LLhM8Xjd89Zv+Y901Ge3ZQz3NOukwE2Pp6h49HJ5oHs/UDh5X4oppu0bEYUEj+DTg== X-Received: by 2002:a05:622a:4a19:b0:476:76bc:cfb8 with SMTP id d75a77b69052e-4771dddea0bmr4161271cf.31.1742493430404; Thu, 20 Mar 2025 10:57:10 -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-4771d63597dsm1420581cf.71.2025.03.20.10.57.09 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 20 Mar 2025 10:57:10 -0700 (PDT) Date: Thu, 20 Mar 2025 13:57:08 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Elijah Newren , Jeff King , Junio C Hamano , Patrick Steinhardt Subject: [PATCH v5 14/14] midx: implement writing incremental MIDX bitmaps Message-ID: <13568cfa3b8a9efcc9238d08b9f940e7c0650681.1742493373.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: 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 +- midx-write.c | 57 ++++++++++------ pack-bitmap-write.c | 65 +++++++++++++----- pack-bitmap.h | 4 +- t/t5334-incremental-multi-pack-index.sh | 87 +++++++++++++++++++++++++ 5 files changed, 179 insertions(+), 37 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/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.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..d30d7253d6 100755 --- a/t/t5334-incremental-multi-pack-index.sh +++ b/t/t5334-incremental-multi-pack-index.sh @@ -44,4 +44,91 @@ 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' ' + test_path_is_file "$midx_chain" && + test_line_count = 2 "$midx_chain" && + + 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