From patchwork Thu Aug 15 21:01:21 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13765155 Received: from mail-yb1-f169.google.com (mail-yb1-f169.google.com [209.85.219.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 CA34C14C5AF for ; Thu, 15 Aug 2024 21:01:24 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.169 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755686; cv=none; b=rn9UrdXBU8wEtF89a1grQxXV4UV3DbzLGn/OhS1wVmXeOqk26tUOr1Uh34cSi6D/hgUMR2gGMN60lABrwC+K8WTsyw4hyJmg+phg2eRenK92lUFU8GreLv2NMnhiGBHJThpmOWNoMGR1nq55OKGBuCh/KBvFcCcGiGvjXBHiF/o= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755686; c=relaxed/simple; bh=9gI9tFmb5lm+kC+z3qm2I4abJzeJzffegyYeKYhwSHg=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=Jh6RnFIAuUCVvnPjcceQ9tkiPL/R43MZZM2pdUe64VgdqNaDY5Ypoq6cF6ITv4gUnnDCWwKgl5FLd6rpfj6vuaxpFXdamj27LfWEKBQ7g0/M/XfmD87c5cZK8XIak8MX/rgaJqV3QGniUazX0h5OBsUDF9qHS/mleHd/OunWRZE= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none 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=bfn5iRqY; arc=none smtp.client-ip=209.85.219.169 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none 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="bfn5iRqY" Received: by mail-yb1-f169.google.com with SMTP id 3f1490d57ef6-e0875f1e9edso1324315276.1 for ; Thu, 15 Aug 2024 14:01:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723755683; x=1724360483; 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=NqThN4qbfvU+1vWMgiwXaIfvuShsSgAKF1gC3+o4HU4=; b=bfn5iRqYaQ97n0rpRHLoS1PdzV413YCP2njkj8xESGjLMLfwCgS5mzdT9nCB14NT3Y 8zW2d+hnXNLke1l2Us+dyPFrk+FORIlitf9sp7m2KnXZFzVw420upv+Rhak4p8AUjJ7P /pjMYKAc8Qz7/8bhp194h1++vrLRVPxzqr+ZZxi2o7DCW34oZSFhhNah3cod4MqJ54WF Serxut2lhLnl/cWB18FdoV4WT7lxhOpDrTZTfRl/smi9W/LFUr98QmUQEdbYiGYRTfFT 3G6m39XE3sAQkzXHsfuUSDeI2jgKhune9cEl6cSk3rpQ0lfL/eopqDw473xDVZiSMnde VOFg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723755683; x=1724360483; 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=NqThN4qbfvU+1vWMgiwXaIfvuShsSgAKF1gC3+o4HU4=; b=opGugF3fvzuWX08mfA/ABkO07s/UPrkiFkC0JrMssMlBi8lSVDJJ0nvS+gaI9X9+Re FWVHPLhKd5dBJSk0WyvCfDuRAeRmQTb2o/9GvqunZntr3Pl9YBJHwGMZMS9aUTEtCxBq 3SrG5lC5+k3Usv159RRCVVg9Jj+oL1RS2SVo4vhU72XDei5XWfV7g12nWDo+sqdAlTaM PtX77Et4x3+1JlcNuFOoOs9/dxehXx59QKqnCjSiHtwc5MQFs0rk21mLCnP5I+sZydia OaphTcC9SYraZEVkaa2TNYynlOLnLKQzxXrFXXSpQrff4feKH4Ibvbszlx5mBNb5xVKi 6IvQ== X-Gm-Message-State: AOJu0YxIfhsGmnzjsdU42ebNkEBnH6r3y5oLBNv7iazC/sNw7/FX1ZD7 I6WNhl0Cy1ny++xrROZV5rNFPaNzdhD8mcUGzhTaedpD+xsAQ6EVBBXi2CHI1B7BJk+rg32Tykw A X-Google-Smtp-Source: AGHT+IF4Qr3lCNO/3KlL1oX/bDjo8ZAABb3h65S+IkKlLg3QdMTHXpP6s36Z/oDAxfzcMtxOaV4xew== X-Received: by 2002:a05:6902:2382:b0:e11:3f5d:9e3d with SMTP id 3f1490d57ef6-e1180f72076mr988298276.37.1723755683277; Thu, 15 Aug 2024 14:01:23 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id 3f1490d57ef6-e1171e6ffb6sm467859276.32.2024.08.15.14.01.22 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 14:01:22 -0700 (PDT) Date: Thu, 15 Aug 2024 17:01:21 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH 01/13] Documentation: describe incremental MIDX bitmaps Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Prepare to implement support for reachability bitmaps for the new incremental multi-pack index (MIDX) feature over the following commits. This commit begins by first describing the relevant format and usage details for incremental MIDX bitmaps. Signed-off-by: Taylor Blau --- Documentation/technical/multi-pack-index.txt | 64 ++++++++++++++++++++ 1 file changed, 64 insertions(+) diff --git a/Documentation/technical/multi-pack-index.txt b/Documentation/technical/multi-pack-index.txt index cc063b30be..a063262c36 100644 --- a/Documentation/technical/multi-pack-index.txt +++ b/Documentation/technical/multi-pack-index.txt @@ -164,6 +164,70 @@ objects_nr($H2) + objects_nr($H1) + i (in the C implementation, this is often computed as `i + m->num_objects_in_base`). +=== Pseudo-pack order for incremental MIDXs + +The original implementation of multi-pack reachability bitmaps defined +the pseudo-pack order in linkgit:gitformat-pack[5] (see the section +titled "multi-pack-index reverse indexes") roughly as follows: + +____ +In short, a MIDX's pseudo-pack is the de-duplicated concatenation of +objects in packs stored by the MIDX, laid out in pack order, and the +packs arranged in MIDX order (with the preferred pack coming first). +____ + +In the incremental MIDX design, we extend this definition to include +objects from multiple layers of the MIDX chain. The pseudo-pack order +for incremental MIDXs is determined by concatenating the pseudo-pack +ordering for each layer of the MIDX chain in order. Formally two objects +`o1` and `o2` are compared as follows: + +1. If `o1` appears in an earlier layer of the MIDX chain than `o2`, then + `o1` is considered less than `o2`. +2. Otherwise, if `o1` and `o2` appear in the same MIDX layer, and that + MIDX layer has no base, then If one of `pack(o1)` and `pack(o2)` is + preferred and the other is not, then the preferred one sorts first. If + there is a base layer (i.e. the MIDX layer is not the first layer in + the chain), then if `pack(o1)` appears earlier in that MIDX layer's + pack order, than `o1` is less than `o2`. Likewise if `pack(o2)` + appears earlier, than the opposite is true. +3. Otherwise, `o1` and `o2` appear in the same pack, and thus in the + same MIDX layer. Sort `o1` and `o2` by their offset within their + containing packfile. + +=== Reachability bitmaps and incremental MIDXs + +Each layer of an incremental MIDX chain may have its objects (and the +objects from any previous layer in the same MIDX chain) represented in +its own `*.bitmap` file. + +The structure of a `*.bitmap` file belonging to an incremental MIDX +chain is identical to that of a non-incremental MIDX bitmap, or a +classic single-pack bitmap. Since objects are added to the end of the +incremental MIDX's pseudo-pack order (see: above), it is possible to +extend a bitmap when appending to the end of a MIDX chain. + +(Note: it is possible likewise to compress a contiguous sequence of MIDX +incremental layers, and their `*.bitmap`(s) into a single layer and +`*.bitmap`, but this is not yet implemented.) + +The object positions used are global within the pseudo-pack order, so +subsequent layers will have, for example, `m->num_objects_in_base` +number of `0` bits in each of their four type bitmaps. This follows from +the fact that we only write type bitmap entries for objects present in +the layer immediately corresponding to the bitmap). + +Note also that only the bitmap pertaining to the most recent layer in an +incremental MIDX chain is used to store reachability information about +the interesting and uninteresting objects in a reachability query. +Earlier bitmap layers are only used to look up commit and pseudo-merge +bitmaps from that layer, as well as the type-level bitmaps for objects +in that layer. + +To simplify the implementation, type-level bitmaps are iterated +simultaneously, and their results are OR'd together to avoid recursively +calling internal bitmap functions. + Future Work ----------- From patchwork Thu Aug 15 21:01:25 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13765156 Received: from mail-ot1-f46.google.com (mail-ot1-f46.google.com [209.85.210.46]) (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 C05E614E2DF for ; Thu, 15 Aug 2024 21:01:27 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.46 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755689; cv=none; b=IvyF1tYT04bnt6TXO84FYIL8PlQ2vUH97gaNIT3mw+Iwpx2BgmU0RCn1Fb+aFiX/WUZZVfXa1fulf5eYlNH13NPV2SvwwlTsieOdf4NfEBkh+BvbPXQ+ex3JVosx+fzkVNm599a24yiqi1U6UB/c8/c3vO2z0UCNNX2m6qI0ZTY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755689; c=relaxed/simple; bh=ilh/z9+rVIxGj/lPNfJG41yrKZe1FjE1tzFQ0hjWiEU=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=eEXMtort38CKmqolXg+MdQlNBlelsY35mILUhm3O3mbAF9wtFeyY/5XrC/QyP/Jdp2d5avGBamCIULTPP09JppQnPNf2NddZ7Egy0VsMKyB34Rx5Pq3MFCZ2AY1mECFN6efwoXFu1EHca8w2HPRpccMhAed5Y3bylWC3lQGjILs= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none 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=nHWUM5Af; arc=none smtp.client-ip=209.85.210.46 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none 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="nHWUM5Af" Received: by mail-ot1-f46.google.com with SMTP id 46e09a7af769-7093705c708so1348393a34.1 for ; Thu, 15 Aug 2024 14:01:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723755686; x=1724360486; 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=YdO5rpfaE/UAjBShy8CXkYYFcFh8jX1HTqxdCfoZyPI=; b=nHWUM5AfSo9VesOnjvfZmm04u91WdRVgzo9TNUXgbPVTUn9E5700/Imi4TNy0n3w0R 1j4wclokwHDfdgxMmGxzmZ9rrTQAJrlvpncVN2hLrOIgfvcl7ufKE6J8JYeehp2AMgxJ idcCBriiePVYKdtT3GXSpcfSLUq6YtoBgtDYwax9sp4rzk9BdBwJG0Vk1HynvWKx7yQG 2OdHGU9cgw8avGsz2ze0ny9D+3OBlbP+rU1gjVWwQtNtxnDi/yTrfkaNqD2m+kxC2R7Y R6HyNKQqUAyVUqtvMWlDqkptqNDijFT/kBa0ldNHVnX9KWspGYbbL+TEWRYdCFAUQ0ha 5YCw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723755686; x=1724360486; 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=YdO5rpfaE/UAjBShy8CXkYYFcFh8jX1HTqxdCfoZyPI=; b=CpTDUnmSfItZZVqw05ZGJ24rJ0Yu/TiWTYju2CJgO8AwwHo+65cJAY0zOSVdiliFje G1MR+QpY2KQTfMbtGh5VREu8hey1OCyIRgAgjaLKUyRgsE3L3O2Rn76irODeVlDf23ve UfpGwpJXU0d2ZXZ7ox5kRxZnFw6u6zD3FpKA2ZOWPgIk5F+joKaizsDfmtI1wCyzcmgB OFqvD+UgW+JEM7bxHJKjpm77t3ICXRH71ul6Cw9Dctea2kIHAL2guy+r612v7+PeVMWT eyvYqoUg0kz8tfnIwrdURLZVAZ+TrHPMkTnfUYS579F7oUuEBfaZ2ldUW86RwSPBJvKJ UN6g== X-Gm-Message-State: AOJu0YyCPgUzCWI5o65eOyIJVbSQ7ZOKPKSF1tbsNhDS7ebz7pKcDWwh 78eo9CQgpIvTh5zFhYHGXApJCsLXuZtQo8irTG86ujmtu+irM/Y5RgS9os5V3C8otgKzRhQj7+r 1 X-Google-Smtp-Source: AGHT+IHTRwfjufHhry/tu/syn7NBJcZZqJgW+Agn7BFCMVgZ1tTHUcgxcYBDfJ7P4tLJdPQ2byQmHA== X-Received: by 2002:a05:6830:6610:b0:709:409e:528b with SMTP id 46e09a7af769-70cac85db7amr1018934a34.15.1723755686603; Thu, 15 Aug 2024 14:01:26 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id 00721157ae682-6af9940fec6sm3931337b3.14.2024.08.15.14.01.26 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 14:01:26 -0700 (PDT) Date: Thu, 15 Aug 2024 17:01:25 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH 02/13] pack-revindex: prepare for incremental MIDX bitmaps Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Prepare the reverse index machinery to handle object lookups in an incremental MIDX bitmap. These changes are broken out across a few functions: - load_midx_revindex() learns to use the appropriate MIDX filename depending on whether the given 'struct multi_pack_index *' is incremental or not. - pack_pos_to_midx() and midx_to_pack_pos() now both take in a global object position in the MIDX pseudo-pack order, and finds the earliest containing MIDX (similar to midx.c::midx_for_object(). - midx_pack_order_cmp() adjusts its call to pack_pos_to_midx() by the number of objects in the base (since 'vb - midx->revindx_data' is relative to the containing MIDX, and pack_pos_to_midx() expects a global position). Likewise, this function adjusts its output by adding m->num_objects_in_base to return a global position out through the `*pos` pointer. Together, these changes are sufficient to use the multi-pack index's reverse index format for incremental multi-pack reachability bitmaps. Signed-off-by: Taylor Blau --- pack-bitmap.c | 30 ++++++++++++++++++++---------- pack-revindex.c | 32 +++++++++++++++++++++++--------- 2 files changed, 43 insertions(+), 19 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 2e657a2aa4..0a7039d955 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -170,6 +170,15 @@ static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *index) return read_bitmap(index->map, index->map_size, &index->map_pos); } +static uint32_t bitmap_non_extended_bits(struct bitmap_index *index) +{ + if (index->midx) { + struct multi_pack_index *m = index->midx; + return m->num_objects + m->num_objects_in_base; + } + return index->pack->num_objects; +} + static uint32_t bitmap_num_objects(struct bitmap_index *index) { if (index->midx) @@ -925,7 +934,7 @@ static inline int bitmap_position_extended(struct bitmap_index *bitmap_git, if (pos < kh_end(positions)) { int bitmap_pos = kh_value(positions, pos); - return bitmap_pos + bitmap_num_objects(bitmap_git); + return bitmap_pos + bitmap_non_extended_bits(bitmap_git); } return -1; @@ -993,7 +1002,7 @@ static int ext_index_add_object(struct bitmap_index *bitmap_git, bitmap_pos = kh_value(eindex->positions, hash_pos); } - return bitmap_pos + bitmap_num_objects(bitmap_git); + return bitmap_pos + bitmap_non_extended_bits(bitmap_git); } struct bitmap_show_data { @@ -1498,7 +1507,8 @@ static void show_extended_objects(struct bitmap_index *bitmap_git, for (i = 0; i < eindex->count; ++i) { struct object *obj; - if (!bitmap_get(objects, st_add(bitmap_num_objects(bitmap_git), i))) + if (!bitmap_get(objects, + st_add(bitmap_non_extended_bits(bitmap_git), i))) continue; obj = eindex->objects[i]; @@ -1677,7 +1687,7 @@ static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git, * them individually. */ for (i = 0; i < eindex->count; i++) { - size_t pos = st_add(i, bitmap_num_objects(bitmap_git)); + size_t pos = st_add(i, bitmap_non_extended_bits(bitmap_git)); if (eindex->objects[i]->type == type && bitmap_get(to_filter, pos) && !bitmap_get(tips, pos)) @@ -1703,7 +1713,7 @@ static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git, oi.sizep = &size; - if (pos < bitmap_num_objects(bitmap_git)) { + if (pos < bitmap_non_extended_bits(bitmap_git)) { struct packed_git *pack; off_t ofs; @@ -1726,7 +1736,7 @@ static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git, } } else { struct eindex *eindex = &bitmap_git->ext_index; - struct object *obj = eindex->objects[pos - bitmap_num_objects(bitmap_git)]; + struct object *obj = eindex->objects[pos - bitmap_non_extended_bits(bitmap_git)]; if (oid_object_info_extended(the_repository, &obj->oid, &oi, 0) < 0) die(_("unable to get size of %s"), oid_to_hex(&obj->oid)); } @@ -1878,7 +1888,7 @@ static void filter_packed_objects_from_bitmap(struct bitmap_index *bitmap_git, uint32_t objects_nr; size_t i, pos; - objects_nr = bitmap_num_objects(bitmap_git); + objects_nr = bitmap_non_extended_bits(bitmap_git); pos = objects_nr / BITS_IN_EWORD; if (pos > result->word_alloc) @@ -2399,7 +2409,7 @@ static uint32_t count_object_type(struct bitmap_index *bitmap_git, for (i = 0; i < eindex->count; ++i) { if (eindex->objects[i]->type == type && bitmap_get(objects, - st_add(bitmap_num_objects(bitmap_git), i))) + st_add(bitmap_non_extended_bits(bitmap_git), i))) count++; } @@ -2798,7 +2808,7 @@ uint32_t *create_bitmap_mapping(struct bitmap_index *bitmap_git, BUG("rebuild_existing_bitmaps: missing required rev-cache " "extension"); - num_objects = bitmap_num_objects(bitmap_git); + num_objects = bitmap_non_extended_bits(bitmap_git); CALLOC_ARRAY(reposition, num_objects); for (i = 0; i < num_objects; ++i) { @@ -2941,7 +2951,7 @@ static off_t get_disk_usage_for_extended(struct bitmap_index *bitmap_git) struct object *obj = eindex->objects[i]; if (!bitmap_get(result, - st_add(bitmap_num_objects(bitmap_git), i))) + st_add(bitmap_non_extended_bits(bitmap_git), i))) continue; if (oid_object_info_extended(the_repository, &obj->oid, &oi, 0) < 0) diff --git a/pack-revindex.c b/pack-revindex.c index 22d3c23464..ce3f7ae214 100644 --- a/pack-revindex.c +++ b/pack-revindex.c @@ -383,8 +383,12 @@ int load_midx_revindex(struct multi_pack_index *m) trace2_data_string("load_midx_revindex", the_repository, "source", "rev"); - get_midx_filename_ext(&revindex_name, m->object_dir, - get_midx_checksum(m), MIDX_EXT_REV); + if (m->has_chain) + get_split_midx_filename_ext(&revindex_name, m->object_dir, + get_midx_checksum(m), MIDX_EXT_REV); + else + get_midx_filename_ext(&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 +475,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 +499,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 +538,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 +560,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 +569,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 Aug 15 21:01:28 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13765157 Received: from mail-yw1-f169.google.com (mail-yw1-f169.google.com [209.85.128.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 EF8EE14E2DF for ; Thu, 15 Aug 2024 21:01:30 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.169 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755692; cv=none; b=FFzS416G9rFyaowV4/AN1gcPjNXN+zevEPZe22f4mOjUSkyFk7YfboidvYBGFrzhNXFXJQb+DDSOx0No4eDDsy/1E2qdjubWNon2p5ebKqwPdjwa9/NU5lSKb368WLEp0e9GVzqEdHE8LGD+FhQtraUo/VkfsqSMqvloIBFy16o= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755692; c=relaxed/simple; bh=0c1BLveCC0VTuedQ7gjhMnuviv9khlUd8jJuVt6QJGc=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=X7U83VLiZyszOu4uEs/RAAa3by15TLvEowwnkNOlL7tUS6Y0DnjAS6sXa0Ny+joddd/MeA/N9ZeepF8+B7S/JjS9Z9U0CW7XTAxmrBjJ72op95uYdZ+uDzl8diG7FWFqMaiftZ8WUxW+k8ugziKO4b+JMHuXWH+fcpPVbUTLqI0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none 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=xklMKWIC; arc=none smtp.client-ip=209.85.128.169 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none 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="xklMKWIC" Received: by mail-yw1-f169.google.com with SMTP id 00721157ae682-699ac6dbf24so13061837b3.3 for ; Thu, 15 Aug 2024 14:01:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723755689; x=1724360489; 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=DYNYWrfBb9brsbTpEoKkvZqrdyZOZli6q8goV7oYNrU=; b=xklMKWICPlUuES3lizVAMBtlT004GIgrmPOk4vW+/kMlLgwVH68sVYjIs2iCBOHlhN IN+CiozRCrPg3GchiR7W2iE2bQn56LLUM36qo1/eNP/AcXOduay3JwyqBkBkDuKQKyu9 AKllCaMACzXdT5Fq5h76vUp45pMoe0ytonM97iQ03oJ1Ocj7DzdRdyy3P0NADed8Wg/Q 89My9XgKXL+RWVUFJ2k5Mv1+SzhqgsgOiq7fBYCQn4SKJ/0juKA7pSXcccCyQLvHuFMz tL7J5TYOoT+kHwY3TzKaSrqpqddXxEy4OuilsiLW4Kr0tNmy6v7ZDj5FT29ILDP6Imp5 LU+A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723755689; x=1724360489; 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=DYNYWrfBb9brsbTpEoKkvZqrdyZOZli6q8goV7oYNrU=; b=QrCsludjHA+9azTNVZU43Af+WVUVsBKfrhNu69BxW0U/HLDaKHsULnADfmItg07vFJ keBEzW8mYtvCtYgUs3deuPDkepjlcj47wO2pVtBLCMJJttjQgYNZelA1OsSK/3DafaDi U/+Ia7KpyG1ZMX5P/fnZD2unBaY+Z3vPRLjqTBlJHdB7SZYiHxGlW1psRcm+bs8xn096 hlfgIyqzWscx8+kO2VeAqabQXf2AG4El7ESqGAJiyaiqv2jOHICYhBJ73f9XiGrpSFBI w9m8S7qtifs8fDkUeBfOnuMbe64F04Vwa/+q75btWUXLIKREPZdc+PNb2meQYLgCjLmj 0/Tw== X-Gm-Message-State: AOJu0YxjY5QGQ1PJ/noerO4LK1A963R4RMTTFrbYv6Os8w/5o/jA2gVn aHCkkaq37//0+hjTqgZKajAej6obdwq32+tqTOIi4zBlwsl68tBN+1fYL0Wo9cv3OKJrnY4Gk7s W X-Google-Smtp-Source: AGHT+IHNXMxEzNGjL7N+ikicRhvqNC882VUkDeX7+9htt+VT51/62EusABcNVzZOoGQBFt/6Sbi+ZA== X-Received: by 2002:a05:690c:2905:b0:6ad:feb0:e6c9 with SMTP id 00721157ae682-6b1b8906da8mr8707057b3.23.1723755689648; Thu, 15 Aug 2024 14:01:29 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id 00721157ae682-6af9a28cd46sm3902497b3.36.2024.08.15.14.01.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 14:01:29 -0700 (PDT) Date: Thu, 15 Aug 2024 17:01:28 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH 03/13] pack-bitmap.c: open and store incremental bitmap layers Message-ID: <43444efc21415b8817522cbd7b590e1ce38636d5.1723755667.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 bitmap layers along the "base" pointer, ensures that the correct packs and their reverse indexes are loaded across MIDX layers, etc. While we're at it, keep track of a base_nr field to indicate how many bitmap layers (including the current bitmap) exist. This will be used in a future commit to allocate an array of 'struct ewah_bitmap' pointers to collect all of the respective type bitmaps among all layers to initialize a multi-EWAH iterator. Subsequent commits will teach the functions within the pack-bitmap machinery how to interact with these new fields. Signed-off-by: Taylor Blau --- pack-bitmap.c | 63 ++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 50 insertions(+), 13 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 0a7039d955..c27383c027 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -54,6 +54,13 @@ 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. + */ + 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 */ @@ -377,8 +384,13 @@ 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(&buf, midx->object_dir, get_midx_checksum(midx), - MIDX_EXT_BITMAP); + if (midx->has_chain) + get_split_midx_filename_ext(&buf, midx->object_dir, + get_midx_checksum(midx), + MIDX_EXT_BITMAP); + else + get_midx_filename_ext(&buf, midx->object_dir, + get_midx_checksum(midx), MIDX_EXT_BITMAP); return strbuf_detach(&buf, NULL); } @@ -397,10 +409,17 @@ static int open_midx_bitmap_1(struct bitmap_index *bitmap_git, { struct stat st; char *bitmap_name = midx_bitmap_filename(midx); - int fd = git_open(bitmap_name); + int fd; uint32_t i, preferred_pack; struct packed_git *preferred; + fd = git_open(bitmap_name); + if (fd < 0 && errno == ENOENT) { + FREE_AND_NULL(bitmap_name); + bitmap_name = midx_bitmap_filename(midx); + fd = git_open(bitmap_name); + } + if (fd < 0) { if (errno != ENOENT) warning_errno("cannot open '%s'", bitmap_name); @@ -446,7 +465,7 @@ static int open_midx_bitmap_1(struct bitmap_index *bitmap_git, goto cleanup; } - for (i = 0; i < bitmap_git->midx->num_packs; i++) { + for (i = 0; i < bitmap_git->midx->num_packs + bitmap_git->midx->num_packs_in_base; i++) { if (prepare_midx_pack(the_repository, bitmap_git->midx, i)) { warning(_("could not open pack %s"), bitmap_git->midx->pack_names[i]); @@ -459,13 +478,20 @@ static int open_midx_bitmap_1(struct bitmap_index *bitmap_git, goto cleanup; } - preferred = bitmap_git->midx->packs[preferred_pack]; + preferred = nth_midxed_pack(bitmap_git->midx, preferred_pack); if (!is_pack_valid(preferred)) { warning(_("preferred pack (%s) is invalid"), preferred->pack_name); 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 = 1; + } + return 0; cleanup: @@ -516,6 +542,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 = 1; close(fd); if (load_bitmap_header(bitmap_git) < 0) { @@ -535,8 +562,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 @@ -545,10 +571,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; } @@ -574,6 +605,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: @@ -658,10 +696,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 = the_repository; 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); From patchwork Thu Aug 15 21:01:31 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13765158 Received: from mail-yw1-f174.google.com (mail-yw1-f174.google.com [209.85.128.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 D66A614F100 for ; Thu, 15 Aug 2024 21:01:33 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.174 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755695; cv=none; b=f5pBw+f9kK3SNAbV9Mrd9G78h/pr0qRI6YfylRKasgdlrExqVpqbxnbUGOLRSxjXAm9l9W4ZcFSbCva3exAazgyGDOd4JOheK0LctO4xWv43fMe10QS57jY2SSfVXv/nD/L01yA8XbdTbSG3ymbWkIsdHEqw+czsvvveidX6TnM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755695; c=relaxed/simple; bh=xzI/Uud9Z0WlQdTf+8ebH6i9bjeXNBU0aFD7QhFZigQ=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=aZ389Fh/+pvDhGzyR1HB+j4Nijn7HDYiTkm4AAfFXnbWM566W/miiTidFL7cuAM6yHyHVcrLqlnKLViACKDE+QcKCm9QHRTyp1RuNpo4ZTnaETlto3pvvpXv2uwPIR8vnPRIrwfVEdTf+QPwzkJcyuH7uJP1vIiHdQr2u1j5PFg= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none 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=jx07P7E7; arc=none smtp.client-ip=209.85.128.174 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none 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="jx07P7E7" Received: by mail-yw1-f174.google.com with SMTP id 00721157ae682-64b417e1511so13487047b3.3 for ; Thu, 15 Aug 2024 14:01:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723755692; x=1724360492; 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=cUlApPl07OkhfjwTTTVSsr4uQ1Aev+3QtfB5OTDai5E=; b=jx07P7E75W2qAChStNzqGKyUubclp1zNDFMCvYxosKGQJrHcHkvc6/4BfjbezZc+2A IOETORTCOv7YP1Drdy5vGz1GgWfR6wjHwxx4Awy/2IXDSBJuHpFq7c2LmsPTIqB5NPY2 srSlWGh4u+k0D1X72NDWJW62qdgMYvND9tMOLASHrn1Bq94RjYanAyKWg68e+OoeYe8o NRFUvt/MJiMiLHUOyy2qz311BWiiNuqNsiBoCuaFgDanjbbT9TkKa7C1Kz5GtZVrB/Pe d2u2OOXAQtbVFRZO+DlHltEPTVbNG/1xiDiDgavYYxoKpsNYr91NZ4091RgnMkMCMDtA LJQQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723755692; x=1724360492; 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=cUlApPl07OkhfjwTTTVSsr4uQ1Aev+3QtfB5OTDai5E=; b=h+aSWzLbUM47Gz9vXxP2ZqHUkCt/8JVE/hoUZ2DGT1POZ5HoH+Xmr4aZnFpgUmdxTF JSD0b/0d6w6+6ce4zGqrh2P6lueTZ2wlXbJjrQnysr5IRk9J4+iZXaYSKC7WVG6zPbn+ MbRz/D9xYdO0tc0WFtEqVL1rcg3JEO+mR9rVfz0LnTF0e96kolTDCySkCG0kgu5sFP3g gy9IMw2REqsOB2IrCixCRrqexITz65laTJzQwCGxLtHZa6WvXdBmExGIexn7Mck4nH/2 pAAFwgXISIh5GLJbBlT9J+qBmO/Wl2aBWpmgjhyn5V2CIQxVsJa6gfuGZ6zYfY8F3z4p n2Og== X-Gm-Message-State: AOJu0YxnjK6W0auMVuK5phb2LZ3pSdWpbGT9aNP2nkHRyWZHVDIN89K8 EI65WhgTznJO83PtKRHeCHKr2n+uwul044hVohVA75qP05yHus/UbH1yPtkK8MZ3l42zUXDu1In d X-Google-Smtp-Source: AGHT+IEhDkwFKQrDR/sHZbQhOKfwNprkTH/HdNhVR0hT7rzzOMWeONaUyxg2NuVTLg1TEqCBln9E8Q== X-Received: by 2002:a05:690c:4606:b0:6b0:9be1:ecde with SMTP id 00721157ae682-6b1bbf24f09mr7555387b3.27.1723755692543; Thu, 15 Aug 2024 14:01:32 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id 00721157ae682-6af9e1d9607sm3808007b3.140.2024.08.15.14.01.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 14:01:32 -0700 (PDT) Date: Thu, 15 Aug 2024 17:01:31 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH 04/13] pack-bitmap.c: teach `bitmap_for_commit()` about incremental MIDXs Message-ID: <44871306487e5c4c93f619b3c81b651cab3099d6.1723755667.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 c27383c027..88623d9e06 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -946,18 +946,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 Aug 15 21:01:34 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13765159 Received: from mail-yb1-f177.google.com (mail-yb1-f177.google.com [209.85.219.177]) (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 DD7B37E0F4 for ; Thu, 15 Aug 2024 21:01:36 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.177 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755698; cv=none; b=hJLDsYqdow/8LRsSo/KJn5vgFRcFt2GkC7cT8YOQTBp/6X6nMLEjkgGd//jiUuRTNGj3fsyXzUwQ64POWYgr4/ihoLBp3jFP8GPZNY2WYOLxSCU+cTlPN6t0dIdr7HCfj9IH+lgUlY/DjGbJdqN+vqPjZsHkS/0jZy7qCNzUq6Y= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755698; c=relaxed/simple; bh=P4nLtaax4xZUgAoO01Y3Be2O/COrRVLoiZ/UDwWNLeM=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=p1s59n4XCBOhP6NdJbJfJ/tZgWP4xJNlTUP/byRH68lgkiWMGwttWa0kVWgK2dbn2n/gyY5EiP8hoA5HnW3WZGSiHon53yenVFhhhrLoD8aX4ARX/F2PkdZUQetNKnPu3Ck1zqdwrqMr1879gAyHA5Z070wOVrn1l2IdeuIEyc4= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none 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=zrxefS7L; arc=none smtp.client-ip=209.85.219.177 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none 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="zrxefS7L" Received: by mail-yb1-f177.google.com with SMTP id 3f1490d57ef6-e0ea24477f0so1444380276.2 for ; Thu, 15 Aug 2024 14:01:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723755695; x=1724360495; 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=vnXoms/JZKpsIummwddL7fQgERMHOCeXotpuHp5HbFU=; b=zrxefS7L016YaWGgkvw0KSChGyGTjd2GT9agr/xv3A+ryikgYFSkukLRO68fP3DKBa H5uDWS03cp3c9wo4pYUIZI0FBiPfH/P4AGQwAWVjGtkhxh82wpwKQftWqABj2BJYsxEb lkXNyPax7Gbrew/HK/D2GhPOO9OIodg7Zszb8x4UrZw+dRcH6KVPOYaY/Thc0qsta5mH 6G/+x4ZYUF6BLdrpct2+bYVHXIAp1S084B500xast2yKvPDvkbAsSspDenDgS78VWvQ6 o2rg01lKeX5Qrq80OrZFvnsmqtZQGUbEZRleFMekJ2IbzgmLzdC3lwGIYyIWUDzUB+Hc +Vtg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723755695; x=1724360495; 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=vnXoms/JZKpsIummwddL7fQgERMHOCeXotpuHp5HbFU=; b=aYAKfflak+1paPKG1dnUEnfcLdEpXUY+FkFLDOv7mYgUI3O0saJoALOmTY7yTwGsP8 1iyh1x6xEj1LJ0SVVG9VqSe13HA4isy46d2hHXZMq1RIZlzZbBxkyqry3J9C+c1205Is y5XgTMNk9cFc0GlBxLCFRnqjJ6iq74zDjCKLNMAfP5fRLGfLNJK4lIE4cvKX0ZEx3dZ/ yVJ8WliiHte6J3CMW9EXfjt8m97U+AmdPLBIMb3C6cLFjh7uh0wniUcgORnSPv+BxE7C N0hYk9Uk4OEmjyj6Ynl1WCBO7KK64w1MUXzjaLHm+IU51e8GvgKTkBmiP4xkU9Fj1r+d NjLQ== X-Gm-Message-State: AOJu0YyhjeSN5AoPBpjDXhgi89NxFjLLOkr+ZKjyjDA4nvCf2pBUdwyR q35HB1p6a3KGX4yxtTnVuyl8kjzURQMcFbOejbcDRWGk8KdR/PjvmMORQbjfKjhXos7zf+tlWE9 1 X-Google-Smtp-Source: AGHT+IHhiLOep9HKr6QApb5ZkWdF+pH2BWzflfokhHVcoOzgRoaw9drv4AdDqTubEYaT3m4/TWH8Xg== X-Received: by 2002:a25:8204:0:b0:e11:7ecc:3b0b with SMTP id 3f1490d57ef6-e1180f45d93mr1121089276.14.1723755695560; Thu, 15 Aug 2024 14:01:35 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id 3f1490d57ef6-e1171e3ff58sm451727276.18.2024.08.15.14.01.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 14:01:35 -0700 (PDT) Date: Thu, 15 Aug 2024 17:01:34 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH 05/13] pack-bitmap.c: teach `show_objects_for_type()` about incremental MIDXs Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: 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 88623d9e06..f91ab1b572 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -1631,7 +1631,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 Aug 15 21:01:37 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13765160 Received: from mail-yb1-f179.google.com (mail-yb1-f179.google.com [209.85.219.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 A841814F9EB for ; Thu, 15 Aug 2024 21:01:39 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.179 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755701; cv=none; b=CtqLW5vMn3WlxInAQvieIrvxIlXkGk22iB6Uw+jYSvhjU24jNpocDwhfl6YPB7iTsyhoIUWOuXOa23RoRfnquaYZoTGIvTRH60dxHe7XjTqCGoLhdzLE0SetorYM6PSTtX6v2voc9XLfq/gCE6DV/iz2fs54fMr2hojyzoZqFow= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755701; c=relaxed/simple; bh=6m0KXRcKiFTeCqXkVLH4B7gp29jjiELQPt7qeCoTVfU=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=S6ja8Cwm1P09Jx/Dx+/Ha7phk3xEIbbQFBLi+Uhrg4kt3QrfBpXpIjux4cLtinClTbvzfDZQoYjlceMrB0FbqEVQwoJmPELkU2VMt1tTnkti/5DMZ+j5Jgbm64C+t+YDH7fOcsGWM/BdTiuy4BlsejZnqkDFg+8bVsR+2YqH/U4= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none 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=vtdYTR/t; arc=none smtp.client-ip=209.85.219.179 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none 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="vtdYTR/t" Received: by mail-yb1-f179.google.com with SMTP id 3f1490d57ef6-dfe43dca3bfso1474118276.0 for ; Thu, 15 Aug 2024 14:01:39 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723755698; x=1724360498; 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=g3Oql4sXviHrCmOI1UoNB7tUbznuL5clvipDPDVw6Fs=; b=vtdYTR/tY8dKBRE+6JnSqtcCcLmzayMpwrQ8h6Eox2/DIXfEW1zx34UCTD0p/6jHwe xBTtliFADygn2BVAeclpL1h+ZaDJ3grDgxefQFKLbv1pTIvdm+8GwNF9S0RLKvEQstOe AHkCSaPXfqvrdTMhwUTmvl7bYC19q+vM9DQ4b/pDRdJSQEfswsp+QODnwCKX0Gb+ZLmX T2OcrpUZctUGeUOyeGTwyFzLLijJwmmA3VhZWyheh7JeRCKvdjkSwXpmGhhP0fc8Xz9t TPBEzlB91T1GiNTsP2U68Fh2a/WNfG0g5+DSr/QeyVsnPZElka84zLS3EiiM3hjpUU4v HhXQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723755698; x=1724360498; 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=g3Oql4sXviHrCmOI1UoNB7tUbznuL5clvipDPDVw6Fs=; b=jn7ouDh83+zwxjOkr3SVrvkpeyLLPwkrGOQHIHhgO4/QtWEEqQwSTBjXPRWeE6kAhl VAbvxbSHdsKmK2daoXBk9BKiNEqKFmoRCYcvZzLeYYvX13IUiSNbjTdwvIXlsAN8UFCi D2dongRXXuCfhWiGtiowD5KLcTKj0gUTJ45AxM8HXc28iBGjkaDDZDxULtj9Mq6nbKEK /Rb6XYWZbWMuiZHQ3a7Smumi1eafskQ3yz16XL9vwVzzfwEcy2Lg9m+JaPcXne6h2KGe fBgAgwpuW+TvPGWxGm7zJ3NaNGKQY7gGmbSR74McXtx9+u1Zwif2dov+B2lcWWe+mZTX k+TQ== X-Gm-Message-State: AOJu0YwvPDsPo0u4eMo+8O400VrsArynwoxzxXApKP2y25To6U0z1TlI QXmoHD6wpuByNCahS1Sl8wbaHDi1WnZLeBL14zE3wu8ihAzwsdTq4LuEPVM3RV/ZnaakY3txMP1 u X-Google-Smtp-Source: AGHT+IGyc7prTUXLp15StunBpDxQwy5Axbhci9Cc+SLNayWn6dd/DMg9xVOvtmxbRUfN5okYm/buMQ== X-Received: by 2002:a05:6902:118d:b0:e0b:a4b6:670f with SMTP id 3f1490d57ef6-e118100496fmr1287552276.51.1723755698413; Thu, 15 Aug 2024 14:01:38 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id 3f1490d57ef6-e1171e6a848sm453771276.31.2024.08.15.14.01.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 14:01:38 -0700 (PDT) Date: Thu, 15 Aug 2024 17:01:37 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH 06/13] pack-bitmap.c: support bitmap pack-reuse with incremental MIDXs Message-ID: <01b8bd22cd9a6486cb79500558bd1eb2da832856.1723755667.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: 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 f91ab1b572..2b3c53d882 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -2320,7 +2320,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"), @@ -2344,14 +2345,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 Aug 15 21:01:40 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13765161 Received: from mail-yb1-f169.google.com (mail-yb1-f169.google.com [209.85.219.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 B958D149DE3 for ; Thu, 15 Aug 2024 21:01:42 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.169 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755704; cv=none; b=sL89NbcB/+IxgTL2uDSPKV6pqZE7IgiKJr+4eFLteGtMoVr6x/5CxHvJ2m54Rehc6ur9pI/4LOUnWgZpdbDX8JaYEwBzDcKkI1kj9mYP2amjIUUJZ6g3SyDHIzJ+XlU5ooiagParGD6qrvlltg08H6AtkAXNJYJubMM4L2Y4HUA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755704; c=relaxed/simple; bh=a3kgtv/MMf4WCWdp4KzOSOjY0Cd6rX/09v6y4OiCmzg=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=iQWVAQuRIWw2mhAcZmEhj7ME477AQX6eIXMj3kkQL/+gZYfvc2CwB7kEqkH9e9izkBRWtK5z6rPLw7hNfzCrbHikKCs4o5I4xczIaHEIp4mVLtaiAN6yZHLnQJawUjo8vHxOd7J8zt0BF2GfE8yqjxS3dDB36GkLe0eeFdlzvPk= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none 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=Ee6e5q8l; arc=none smtp.client-ip=209.85.219.169 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none 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="Ee6e5q8l" Received: by mail-yb1-f169.google.com with SMTP id 3f1490d57ef6-e02c4983bfaso1432284276.2 for ; Thu, 15 Aug 2024 14:01:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723755701; x=1724360501; 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=6aPkBe+rAAR0WgzphauuzcOxRQIV1mAnmFFkXYP6HoY=; b=Ee6e5q8lFnHH9G3tIaQv8oNXw91hBbJ24SQVyelMuaMu6fx7LmEF7ViemJlpcwDn5l gWJ/x//lXNehRVPcv3Dq5Cb4ijbVPq0yAyA2Q+usEx4KPGwR9afY5xdb1NKcegLbF/5l PY37MT/2y7LqgcpwfBf/nC2Bco3QGSO5w1t4RvuOYK4dzOc/TMkTWojFhxlsZ4QKCl6n YdNmfiKamYf+3almRdkT4L7dLuqFQrqNQiGS7TDVt2jJKSccsvSxeiYNUK6CmwBPCAA9 GQPzSAU7U00vqHo8N60EKu+O03hivhpxfbTyzrtvm0fTNvQ11EygduxIc6LPoJ8lTnEG Evdw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723755701; x=1724360501; 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=6aPkBe+rAAR0WgzphauuzcOxRQIV1mAnmFFkXYP6HoY=; b=Xy+k4xBFb9PkntOhvKk0I1SGe1FH6lTX1kYMK1X79AI3eqTM7K7HP66sYcgaLa7bMZ MB6Cpc1WImGUeqp2vVvqnbWVveMWg8NCBDCd4yWkUC7e5Gc42/eKtgRi6UyQN5QClUuY QTLuYjnnXspckyJo7pQtzHnSVjvVh72UUTTkrYPqj7Pt74yYby/kyZIiDX5Q+tvJt0C5 1VR1VhgVF8QoMA2xrdGtwrAVwTEC6uK/PHzJV5mcSp15HPmlP5Z/L8QRgRPS1Ky0Kbj3 /dVwzLSA8z6MN6FBWtqvu6culLxjc2wwSLSDKvCyKsuc8PYKrbWImPXPa2uu9du73GZP VydA== X-Gm-Message-State: AOJu0YwT/kg0wOFSajvUtGJABSsn9YGrmv+4Jw8qLEORlzW1x26pCE0o PdFMo9CJ1neQBLXL+fGG45ybvR4+fNQzkURjlpY7E0NE9S3qjLNR6I0JWh/btdh4MWCFymCZQrJ Y X-Google-Smtp-Source: AGHT+IEs3Iq96E4vYsBMkxOhB/E7EHZBB/G0g2AbZzpOtUSjC2SguWZz3rWk02CGB/Li4nJF2LYbIw== X-Received: by 2002:a05:6902:2589:b0:e11:7744:e55b with SMTP id 3f1490d57ef6-e1180fa4b36mr1131013276.37.1723755701354; Thu, 15 Aug 2024 14:01:41 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id 3f1490d57ef6-e1172008d19sm451540276.44.2024.08.15.14.01.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 14:01:41 -0700 (PDT) Date: Thu, 15 Aug 2024 17:01:40 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH 07/13] pack-bitmap.c: teach `rev-list --test-bitmap` about incremental MIDXs Message-ID: <928a4eabc8b305f7608c082dcb61cd25f2387d3d.1723755667.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: Signed-off-by: Taylor Blau --- pack-bitmap.c | 105 ++++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 84 insertions(+), 21 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 2b3c53d882..5fea2714c1 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -943,8 +943,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) @@ -954,18 +955,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) { @@ -2489,6 +2502,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, @@ -2497,6 +2512,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++; @@ -2560,13 +2580,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 prepare_bitmap_test_data(struct bitmap_test_data *tdata, + struct bitmap_index *bitmap_git) +{ + memset(tdata, 0, sizeof(struct bitmap_test_data)); + + tdata->bitmap_git = bitmap_git; + tdata->base = bitmap_new(); + tdata->commits = ewah_to_bitmap(bitmap_git->commits); + tdata->trees = ewah_to_bitmap(bitmap_git->trees); + tdata->blobs = ewah_to_bitmap(bitmap_git->blobs); + tdata->tags = ewah_to_bitmap(bitmap_git->tags); + + if (bitmap_git->base) { + CALLOC_ARRAY(tdata->base_tdata, 1); + prepare_bitmap_test_data(tdata->base_tdata, bitmap_git->base); + } +} + +static void free_bitmap_test_data(struct bitmap_test_data *tdata) +{ + if (!tdata) + return; + + free_bitmap_test_data(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))) @@ -2575,17 +2639,26 @@ 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(get_midx_checksum(found->midx))); + else + fprintf_ln(stderr, "Located via pack '%s'.", + hash_to_hex(found->pack->hash)); result = ewah_to_bitmap(bm); } @@ -2602,14 +2675,8 @@ 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); + prepare_bitmap_test_data(&tdata, bitmap_git); tdata.prg = start_progress("Verifying bitmap entries", result_popcnt); - tdata.seen = 0; traverse_commit_list(revs, &test_show_commit, &test_show_object, &tdata); @@ -2621,11 +2688,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); + free_bitmap_test_data(&tdata); free_bitmap_index(bitmap_git); } From patchwork Thu Aug 15 21:01:42 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13765162 Received: from mail-yb1-f178.google.com (mail-yb1-f178.google.com [209.85.219.178]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id AAE3814EC56 for ; Thu, 15 Aug 2024 21:01:45 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.178 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755707; cv=none; b=VlNAWbplwS2pOnogu3mmn7NprF7Txtk/C2CvOi59+ipeMB0+SlEVpoUu6wk72MbSAAxibQ3+BtbS1gYsvCK6obSj+6oZnPpDRbYB+NdJTGuCE3HVxqDXYJUkbIvBPcIKUNtM1g4pX7Z87xuBsFKWoSnVVQmmKmuXZf+wkRI6P/k= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755707; c=relaxed/simple; bh=eM/0xgFO5YXXzInVeE/M5c426U62d6+/sgZyUs+2dGU=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=p5J8tWowVdO/8rp3BCftXURhDOBeBg6RPbHQGwWrKa8rOhZHsobt62e9kzFxsf3RPGNa8y7iIZq2KFqX9mOcvn1se27xix00drETNK/MsQEtxLuCGkngvgZbh6q8Vxx3ElS7HbXs2tdMQL9x3GKeMp4fe26z8WddFyqmmaX67SI= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none 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=gKbPNIRi; arc=none smtp.client-ip=209.85.219.178 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none 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="gKbPNIRi" Received: by mail-yb1-f178.google.com with SMTP id 3f1490d57ef6-e116b591e15so1425717276.3 for ; Thu, 15 Aug 2024 14:01:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723755704; x=1724360504; 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=PxIWN2Etecy85LgKdYbI2nyq1L25mosO1gBq/FfF1q0=; b=gKbPNIRiF+FmL/kaGRK6y5AMuuxbh25n9fAQ7SlylRJ8hLqaFzCcqqr8uwADuZkFPg Ey8ExTFAyx/455+xrLi42bsahWGlfpf8QypCntJjUAPnriwwgm8SX+RAmRxTbJMvDqmV dYXLB1Ehm7eIr3BgXV71z9ebgUVGk8IYq1HM9AllzGMSkTF/I8OnFCTDfNXUjSrJfs0s ej6ZbvniWi5lvLQagl4rDB+R93YSxndUV+fy+sYetWikj84vJRzkckH1RU+CMaeS1/nk sUPI0S1pEKifrtUDcfYYvv7eQBCN9vbjmQa0m040mzkmACspriHPsyqDbPvocnkfK8ze bgdg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723755704; x=1724360504; 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=PxIWN2Etecy85LgKdYbI2nyq1L25mosO1gBq/FfF1q0=; b=uk4OpUzYIdeG3pi/PTRY2SGaU/+JEH6XoqxRpkSvj7Tj/zQMbda7ylVj9rEmLGdW5/ p1qSHXROcnWMXGHpzh64dqxSX9Q+BWZ5Al1xDbRh4I4VoTbFhda/jiNYWQkB0amnyQKe IZ3aaFEr6B4nrMLybTFvVyiV2hhY+6+jmSqf5/5NL7IT7Zh4JMGyVIHCbmGoK/dqSEZs N36R47PTATpQ4bFOVTpJ/nqRX6eBg0MTohCGuByKdpPZ/HWr0izjXRXuWE8UcPKLObnQ vxT3OEJkJ2caosBRXpXQsenv7rw44jwtAREmvpM9WUrlWmXhYkpoekiwJKtxBVp/mZum xNCw== X-Gm-Message-State: AOJu0Yw5uJ2DMR8tXRqcwjGulkzLSEihuYRMP0hpuJbmmOdYTOlvGXzy Iwnl0pl04kPfJZTh8Rja2/GERVGIRBbtXHhP6yW1+FSb3Ahs9cOpm6Mcm8biDZ4I65MwAG4hXPw 8 X-Google-Smtp-Source: AGHT+IHt457loWs1ur7MfU6ORZxKYXrD+YvwbunGyB/luwJ6EuI4XxdAVXSospbgfcKXthOBgMYp4g== X-Received: by 2002:a05:6902:160f:b0:e11:7b5b:18d4 with SMTP id 3f1490d57ef6-e1180ec4d76mr1266108276.13.1723755704307; Thu, 15 Aug 2024 14:01:44 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id 3f1490d57ef6-e1171e6fee1sm470446276.33.2024.08.15.14.01.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 14:01:44 -0700 (PDT) Date: Thu, 15 Aug 2024 17:01:42 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH 08/13] pack-bitmap.c: compute disk-usage with incremental MIDXs Message-ID: <129f55ac285de29b9dc84aa67a58600dcf2ce41c.1723755667.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: 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 5fea2714c1..d3bb78237e 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -1774,7 +1774,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; @@ -3020,7 +3020,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 Aug 15 21:01:45 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13765163 Received: from mail-yb1-f171.google.com (mail-yb1-f171.google.com [209.85.219.171]) (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 9851D14EC56 for ; Thu, 15 Aug 2024 21:01:48 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.171 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755710; cv=none; b=oPcccQeTNLqhSBPS/0fDOY4+yvugUcsNOuy/6zlDtqwc9te5PaXNwBvZ8QbISe7pY60IJUHIkHa6vgDWMgPEYpsldD9W9Tkjbrk3NNxLfO4CF3RJmMFicj8hWIz4gJGGdNrmnqBYC0+OMHkirCIewKSNehXJeSLpfwaLyCt4rAk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755710; c=relaxed/simple; bh=xbAiuQVR2y0u+YecTIG0A9Ny9UIZNKKG2WfRFXFmB4s=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=is3ZlhukxRl+liQLjrposHsoh8QXpwkfr4VlrIuUAcute6pdyBCMa2M3hS5t3L/Z3MtzRVmEbrfEUWIT4yZzXXOZ4FSL9lJ4lXYLtWva1/38Fw95eBHTZjYxuxeRCzYwNjYhLCOdOncR+BTVJiQX5AzQLvwDeqMgDEB4APENI7Y= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none 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=c9jJQNz9; arc=none smtp.client-ip=209.85.219.171 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none 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="c9jJQNz9" Received: by mail-yb1-f171.google.com with SMTP id 3f1490d57ef6-e0875f1e9edso1324531276.1 for ; Thu, 15 Aug 2024 14:01:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723755707; x=1724360507; 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=PDRQ3hj8CqCqfbToN7r6VpfC6iQIyqXSQfZOlsjQc/M=; b=c9jJQNz98m08UalK2YlrJVK4SoYaQ0Evzo4X4bMZ45GZ8NeCrBMFQp0FSWOZoIx/bb nJTrXtmguV6UbpGrQPTnVzOoDVIhixujF0oHP7GXTvs9Kp/+6aokby1Gb13/6HEcNFiQ 1dPWg++L9E7z7xY2kBgAgCy/qlL9dQRdp6HVa5gKuSeRvaIXgkCelbXl/YoOwuAiabQl Zl7k9qB6znpZ5Lsn0W+EBYQfutvD/BeWfwgD79aiKCvA267gc3LK/0qW8ircpgDO+TcC xby5s+7kfpmfnI2420HtXvzYPXUXt02xJp3XAJWeFcYMx4M7RsudBgfU9h1VCZSHecML xYWw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723755707; x=1724360507; 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=PDRQ3hj8CqCqfbToN7r6VpfC6iQIyqXSQfZOlsjQc/M=; b=Fr6ww9rblrpdYe/bNiwVEzDBxb3CTpZps05X0iQSvXVkfx9sR7S3aiLEtkOIFA+BhO ZyqZX2L/usSLww82qz8gmp8iHnlVcySjEHIVGzP6Y6JNeC/GnsEd2YWmv85Iq1rW8U9Q EE9+FomP2zUDbFkJz26p/S5U1h7OJNRWWp07Dc5QjqaWRUWp3B6/Ti39ikrfewfrJEp8 IFtlIa5WBdSj9mLZyMRV4mli1togDbsuO5L/wyvbheg3kVNGzymze1JdJOfu7rToJFay O35G0WeLQNpanHItnArQGAfRdYYD3Nto52AIO12XoKdNMsOD/g3mPuvNH/hHAHnS6Q9R l6yw== X-Gm-Message-State: AOJu0YwcQNY9AQIU9XFK/9BFPS78A24p5g+YVJKihIBae4u4YSpTti4/ PApr70hwvBdS4N04lfpqOtU7/uGDe0D5RvX7HH/8VzF6mb1I5JL9obMM+D/+MoHp0fV2cWGNlLv U X-Google-Smtp-Source: AGHT+IHtdaDfg8eXPN8bR6pAVcamYBwhLMFaxERNPahGKHQh7gMmBBgJ01wsZrbXVlXYCCbO9WC5/g== X-Received: by 2002:a05:6902:150e:b0:e0b:d8ae:caca with SMTP id 3f1490d57ef6-e1180ef21f7mr1470340276.29.1723755707255; Thu, 15 Aug 2024 14:01:47 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id 3f1490d57ef6-e1182fac3acsm92400276.9.2024.08.15.14.01.46 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 14:01:46 -0700 (PDT) Date: Thu, 15 Aug 2024 17:01:45 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH 09/13] pack-bitmap.c: apply pseudo-merge commits with incremental MIDXs Message-ID: <81839fc1d1a60b467b7de61222795a3a0a7423aa.1723755667.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 d3bb78237e..1fa101bb33 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -1087,10 +1087,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 Aug 15 21:01:48 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13765164 Received: from mail-yb1-f178.google.com (mail-yb1-f178.google.com [209.85.219.178]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id B48A614EC56 for ; Thu, 15 Aug 2024 21:01:51 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.178 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755713; cv=none; b=WmKoCu7JVfdtBDiSsEtc5km0COktVBiUXF7feEYfYYAIJTIQi3J/ZFyY3TlDTLq7N9xeO6Tl+5sr9kaJDej0A/GRwlAFJYUpl2zXvPXXmY8ptW54WYCjyLb4pALb1KCIITpISiN2E/mRBM0qGKECyb8/5j3Bp4JibkRw1htHD1g= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755713; c=relaxed/simple; bh=e0pUdkypE5N8JOR0223KnhXy7yYCfVdq0REDUuVeAMU=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=uGYcRr88vrR3V9YzArOQhr40z4XED7MB1ddwt4lI9fiAv7MahB6Az8M5IcEP4laRfeG/LgUsy6GQtl8k7NN/KW5J0+TZrMmsuEfdM9x5TGy8wHXITYYJV4Ek4vbZgBtf5dqgCtw86VcshiY5897XgdpO3L5l0fJxYqk8fTn4M0E= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none 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=wgf0ZXfJ; arc=none smtp.client-ip=209.85.219.178 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none 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="wgf0ZXfJ" Received: by mail-yb1-f178.google.com with SMTP id 3f1490d57ef6-dfe43dca3bfso1474312276.0 for ; Thu, 15 Aug 2024 14:01:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723755710; x=1724360510; 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=hk7olCEw+V+2tKC2Zlgs33ebK2vFPcs6qBfEtV08lR4=; b=wgf0ZXfJCOTb/VB13sI9z+Olwna2qDTMLPGerReoVLuYfyNi/j27KfEu/mjxyk60E9 tYr9r1zqJPFMBWDAVF4FZ8jksTZjqtnnBrSfk49p5AH2k1hRKrYCspNngOIjo6t6YKMn iDkytc3DjkUwZtuRCec3TKmVLrMjAkOPJ+kTtDWHcpBDO9HMAXb3FPRowFyScrBFPE0O Ush/8p/NNirfaIYutfeIuEudO2KI/sGg1V+mk3OwX1yTGlOlNj1XVO++TMBc9DS9zc0u OXFPmovh13u+tbwplPyxBZxXETAD6GjllbY1Mw9HhPdDjr7mY2UXTCq+Oo29U0980q9r Woxg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723755710; x=1724360510; 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=hk7olCEw+V+2tKC2Zlgs33ebK2vFPcs6qBfEtV08lR4=; b=cr9vc4OYpcoU2F5kEe69UV2+lpJUFoWXzR3FxxqrBwjPI9FMOgfqXLfuBxsLXPT5cF QbEMFMVeaheHG7J3WdAaprunROQvad/4rZ8kOhdcd0s1ooh0/bqm19PeuuZVUbsf5P3l a/8YUlQU/Xt0UYDb7qendL7e5BGPtK2m34ZuW+6h9v1S5cuk/jBzOIdvyirGYAYi83Ks nBfvKKyIrW4HNzGSZXP7lLhtk0jZnVlp+WXhgu6w9NOguy/ffgoySm/IJgM92pthhABm evflFGsO9fLA+Cy9QUhJOqWJST+ldQXBQD44n/vSFedi/6MM6ar6N4aRw625Rtn5okyJ 5cCg== X-Gm-Message-State: AOJu0Yw7UHFfh2240RscQ/5YEmc4uxIadyp7srGdoOHqfzXXF9D9A8Kv dS2zyonNi0hQBZ+hN1YuXIYMEv9zwYhRKAop3J5Cs4ecNAvrbQOXSAn+RkpfoY7w9UaNjgm0Ogm p X-Google-Smtp-Source: AGHT+IFjhFHlMTgwgXeNrFv9BaVG8R88Jnb6cJrEwyh1GGmicSPgbVzWTdVlwS0BLSj508BCCpH8QA== X-Received: by 2002:a05:6902:150a:b0:e03:227c:cf98 with SMTP id 3f1490d57ef6-e1180fd8b58mr1213359276.37.1723755710456; Thu, 15 Aug 2024 14:01:50 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id 3f1490d57ef6-e11720385bfsm447673276.60.2024.08.15.14.01.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 14:01:50 -0700 (PDT) Date: Thu, 15 Aug 2024 17:01:48 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH 10/13] ewah: implement `struct ewah_or_iterator` Message-ID: <63019e952abfd70865466019cbc38bfdb8841301.1723755667.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 8785cbc54a..b3a7ada071 100644 --- a/ewah/ewah_bitmap.c +++ b/ewah/ewah_bitmap.c @@ -372,6 +372,39 @@ void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent) read_new_rlw(it); } +void ewah_or_iterator_init(struct ewah_or_iterator *it, + struct ewah_bitmap **parents, size_t nr) +{ + size_t i; + + memset(it, 0, sizeof(*it)); + + ALLOC_ARRAY(it->its, nr); + for (i = 0; i < nr; i++) + ewah_iterator_init(&it->its[it->nr++], parents[i]); +} + +int ewah_or_iterator_next(eword_t *next, struct ewah_or_iterator *it) +{ + eword_t buf, out = 0; + size_t i; + int ret = 0; + + for (i = 0; i < it->nr; i++) + if (ewah_iterator_next(&buf, &it->its[i])) { + out |= buf; + ret = 1; + } + + *next = out; + return ret; +} + +void ewah_or_iterator_free(struct ewah_or_iterator *it) +{ + free(it->its); +} + void ewah_xor( struct ewah_bitmap *ewah_i, struct ewah_bitmap *ewah_j, diff --git a/ewah/ewok.h b/ewah/ewok.h index 5e357e2493..4b70641045 100644 --- a/ewah/ewok.h +++ b/ewah/ewok.h @@ -148,6 +148,18 @@ void ewah_iterator_init(struct ewah_iterator *it, struct ewah_bitmap *parent); */ int ewah_iterator_next(eword_t *next, struct ewah_iterator *it); +struct ewah_or_iterator { + struct ewah_iterator *its; + size_t nr; +}; + +void ewah_or_iterator_init(struct ewah_or_iterator *it, + struct ewah_bitmap **parents, size_t nr); + +int ewah_or_iterator_next(eword_t *next, struct ewah_or_iterator *it); + +void ewah_or_iterator_free(struct ewah_or_iterator *it); + void ewah_xor( struct ewah_bitmap *ewah_i, struct ewah_bitmap *ewah_j, From patchwork Thu Aug 15 21:01:52 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13765165 Received: from mail-ot1-f50.google.com (mail-ot1-f50.google.com [209.85.210.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 AB3B214E2D8 for ; Thu, 15 Aug 2024 21:01:54 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.50 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755716; cv=none; b=Z4YICtIWOUvD7F0qxXgofop69B5m5h10d7YtX72C5DEIuZEOtTDOWAMEw9GU00OgeD07rhtcm2CHcJZO/psgm5OrqYCQjuBlPDgWVlzSxWhhrehYjIQF7e7LAIax3NbunRA+UiLR0eD7vfS5ZkzMXBzJNJFkZbaMGkOCJeOH3os= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755716; c=relaxed/simple; bh=Kbhib89U0y8ygjQysH9AhiuC1dwlrxVvPwUU7EhTViE=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=h6/JdJwsCAVIn2rvyRp7HMvlUqtxl+GPeFtTp3YKiAJZEXMEQW8FlyDD2AxJJ78EzrYQlS5bFPDwh9P3bkW27RCO3JWtTD72GL+znfmg2qiFb3LUkqsc3JpgdnJGzybf0mSq3r0b5Zg9cqSE9/mVkZF5mp+SYMAAweiqkzhukzg= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none 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=Fu80ZfOB; arc=none smtp.client-ip=209.85.210.50 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none 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="Fu80ZfOB" Received: by mail-ot1-f50.google.com with SMTP id 46e09a7af769-70945a007f0so810764a34.2 for ; Thu, 15 Aug 2024 14:01:54 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723755713; x=1724360513; 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=k9ldVvuZshyODGMuDow6l9/6JrqjZzTJb49kzfy3z6M=; b=Fu80ZfOB/tDXDnKUf4fcGQeHqy+yu2ftgZk3BuNt1NSGVJbljG6bXuHAo+RRXgoPhx O0Uao/5U5DeLiycFlrKyq90WcTn5Dkd5gT/CLKLEWXOcdYAaOlb/uV45TPstrNyQ8KIM v05excDRR9ryNdqiIgYreC5FocCgWs8eM2fBJKqaIFJagNBnArhvGD5gTjj3xAlHiulf xipW7ER8ytvsNcGAAzmA5gm0LFoTXy5o1VfIGpPta/QhqABDdZaZYuLZ+NxRwRiS+9CK FzZzo8m9OgvXsSkl9jc0gIHFxeTRVrOSK+p3bkA65KzL2IqpL6ws6PJRpYA4Vru7uJYc Tc+g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723755713; x=1724360513; 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=k9ldVvuZshyODGMuDow6l9/6JrqjZzTJb49kzfy3z6M=; b=PDcloYV1J7xEqazt7DHIGVmsaQiwI1ynrkNnc9bf1n4gxo8pspPRywOqGu/p9bCXxT dpJHFEh1+naF8uYXR94HKjLbaLTOADaJ9jK+nsHpgc60b2KCXrMd+bSyGH8kCimmLAkI GiYvmCpZM7IPNUXJid4fYTacX4hOmL2/8RN2ywEDGEwSXoOt0wYJCQ4bgDCN0FujCpG/ kUNlUaoDeJbbqLVNyR4rVN/mKX8Z5yRW7T+YxPOw7Y9Zl7Qrhw9+uT4b5iXBj9LyZrhy pNM3UVspFwniU0zMVrSV44n7DvuVoV9VjiB/3Uksma6nKteLOFZkuNEmi09OnK4+Hlnf w2FA== X-Gm-Message-State: AOJu0YwL4EQ2zJjLYn5YD2j70uB2u+SAIofjKNWJMIC9xpA8o2+N8OUK aUMTsiT3lb2cGjqhq8sA0k5ZDdaIEZmUvWVukK7YZasi1HL6EWVfAK7XG3uAHZVTXru7+Eyp6nw s X-Google-Smtp-Source: AGHT+IEL/bZNlfR8PS7f3d/qcDuSb+DX9CW/TbBMdCy1fqxEDqUXeOs3tzhdAY1xs2srZHbHQ7kaPA== X-Received: by 2002:a05:6830:3788:b0:708:b344:fed8 with SMTP id 46e09a7af769-70cac8d53b0mr939144a34.33.1723755713413; Thu, 15 Aug 2024 14:01:53 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id 00721157ae682-6af9d82757esm3897807b3.104.2024.08.15.14.01.52 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 14:01:53 -0700 (PDT) Date: Thu, 15 Aug 2024 17:01:52 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH 11/13] pack-bitmap.c: keep track of each layer's type bitmaps Message-ID: <01508e4ff56531a271beca95b5a8e64bf842fa58.1723755667.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 | 55 +++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 51 insertions(+), 4 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 1fa101bb33..e1badc7887 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -78,6 +78,24 @@ struct bitmap_index { struct ewah_bitmap *blobs; struct ewah_bitmap *tags; + /* + * Type index arrays when this bitmap is associated with an + * incremental multi-pack index chain. + * + * If n is the number of unique layers in the MIDX chain, then + * commits_all[n-1] is this structs 'commits' field, + * commits_all[n-2] is the commits field of this bitmap's + * 'base', and so on. + * + * When either associated either with a non-incremental MIDX, or + * a single packfile, these arrays each contain a single + * element. + */ + struct ewah_bitmap **commits_all; + struct ewah_bitmap **trees_all; + struct ewah_bitmap **blobs_all; + struct ewah_bitmap **tags_all; + /* Map from object ID -> `stored_bitmap` for all the bitmapped commits */ kh_oid_map_t *bitmaps; @@ -586,7 +604,29 @@ 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 - 1; + + ALLOC_ARRAY(bitmap_git->commits_all, bitmap_git->base_nr); + ALLOC_ARRAY(bitmap_git->trees_all, bitmap_git->base_nr); + ALLOC_ARRAY(bitmap_git->blobs_all, bitmap_git->base_nr); + ALLOC_ARRAY(bitmap_git->tags_all, bitmap_git->base_nr); + + 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; + i -= 1; + } +} + +static int load_bitmap(struct repository *r, struct bitmap_index *bitmap_git, + int recursing) { assert(bitmap_git->map); @@ -608,10 +648,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: @@ -687,7 +730,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); @@ -2042,7 +2085,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) @@ -2957,6 +3000,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 Aug 15 21:01:55 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13765166 Received: from mail-yw1-f182.google.com (mail-yw1-f182.google.com [209.85.128.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 9B78414E2D8 for ; Thu, 15 Aug 2024 21:01:57 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755719; cv=none; b=XqhwIAjdWRNIv56e4m6M1D0iOGmD9OYyQah8p/tkQ8bgbolx4IXzuYwuvWhSxfcY82GB1//JXeLAebJ1tZHHKj5ACtIVLMrEYHTJzrG7S9kn2TujMO3ohaN8z05Y55pq5NOUJt9lL1WXZ32+g/hwoV8VQXKh+KkcEmpX3pBd5ok= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755719; c=relaxed/simple; bh=L/kx2bVz2U8MLc2sJPAacU3PrkSp0Ga/+8N5iUelGfA=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=W3olOf1YWe+sI2wig34X0tFzuER9LX7+ZdklflqBiCyoe4bNX67krcPhmrIFkc757L2kI8igb07mSDHFBVn6xsPWSvEYIBudxX6orI+cjs9IHxiboiTrX2r1OKEt6KwEak7Ke6yiqp/om6NsalbqvYdo5kwex/nWye7OpCtaMjQ= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none 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=idil5nhz; arc=none smtp.client-ip=209.85.128.182 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none 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="idil5nhz" Received: by mail-yw1-f182.google.com with SMTP id 00721157ae682-69df49d92b8so13094187b3.3 for ; Thu, 15 Aug 2024 14:01:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723755716; x=1724360516; 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=BP9XtWEMOUHY4a+xwD5V4Twc3Akc76s2qr/cq3q+gvY=; b=idil5nhzRhwIO+3ZqCny7IrjbAPz2w45eDYzXX1N+i46Ceg3VVFhzAmJkVkZn2CpQf vFENZnO/7zgNEEEigPNTab27Hct2YeQZGmJBrpTjCUyO7rkbbwqttl4iYAiDn53h1hXV lkAnpyHygqNKr7BcyKAKLpd9jXLC0kVpGvrNSfTItcOcTI0U9Ap4Q71EyxVIjjhXUEQi RPD4Ky13qXBoU2qr5UKkJjthipoxkCA6SuOXxWpIr/fkujRrrIltodBXE0HsIErHw3ru rFpsAgqqKAdmtjLKnbJwQrZz17SU4clwjgogtbKUNUBcab0SLVEqTAOfiDxxxF5+5hYh fsLg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723755716; x=1724360516; 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=BP9XtWEMOUHY4a+xwD5V4Twc3Akc76s2qr/cq3q+gvY=; b=nblJh0Md8hANYsDY4NzZQsK8aIqr10V0VDWDsk153gWgFSPMva97tmrAs9rBALVxrB LbuhUIQMBMKyUeW86sm7+6boyPeLrs1zOOLjQXu6KRGsTF/GjVFi8/VR9AadlqLdi4FC uNm2zx1esDmbdLkNJ0n7r/CeqVHzW/MMZjGgB8kUG63nRiJUP3PEJzpFjHHMZrmgua8G pqHZic0u+tCix0tXID15SHURa61RBdqmU2Vi7G5UQ/rQd8nCVJqNKFGJOn7krWhv3Wd7 2/rd641KaI1JgSbZiNxvYa2+WOmfcw0ITMwYXV7VJqlpHEjIYwo9f24mdz1CpbMKPI6A e/fA== X-Gm-Message-State: AOJu0YwC4Y6tI5N71q5bZKIaNC8a0RX9rntz/avpBGrVQTxrWyJ1u57x Y9sS3uJ3ejwr78BZ9ko7vdK8t9qB6TB2zbo4601JaZojuz0W4GJdX02ns/GjDnZBXzrUMzE9GHb V X-Google-Smtp-Source: AGHT+IEElagtaxsxzGVI5ZGRd5RlG5y1KvNrucBxERT8rUxGDdmFbKA5qxqPIO1KkDTwf/0j/zLOKg== X-Received: by 2002:a05:690c:6a08:b0:6ae:59e5:5f37 with SMTP id 00721157ae682-6b1b823f19amr11541127b3.13.1723755716321; Thu, 15 Aug 2024 14:01:56 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id 00721157ae682-6af9e0e0e1fsm3931687b3.133.2024.08.15.14.01.55 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 14:01:56 -0700 (PDT) Date: Thu, 15 Aug 2024 17:01:55 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH 12/13] pack-bitmap.c: use `ewah_or_iterator` for type bitmap iterators Message-ID: <59a50a2ea24312eb5b643927aac3fa7143b838f5.1723755667.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 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 e1badc7887..9fac43749c 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -1622,25 +1622,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); break; case OBJ_TREE: - ewah_iterator_init(it, bitmap_git->trees); + ewah_or_iterator_init(it, bitmap_git->trees_all, + bitmap_git->base_nr); break; case OBJ_BLOB: - ewah_iterator_init(it, bitmap_git->blobs); + ewah_or_iterator_init(it, bitmap_git->blobs_all, + bitmap_git->base_nr); break; case OBJ_TAG: - ewah_iterator_init(it, bitmap_git->tags); + ewah_or_iterator_init(it, bitmap_git->tags_all, + bitmap_git->base_nr); break; default: @@ -1657,7 +1661,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; @@ -1665,7 +1669,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); @@ -1707,6 +1711,8 @@ static void show_objects_for_type( show_reach(&oid, object_type, 0, hash, pack, ofs); } } + + ewah_or_iterator_free(&it); } static int in_bitmapped_pack(struct bitmap_index *bitmap_git, @@ -1758,7 +1764,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; @@ -1775,7 +1781,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]; @@ -1795,6 +1801,7 @@ static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git, bitmap_unset(to_filter, pos); } + ewah_or_iterator_free(&it); bitmap_free(tips); } @@ -1852,14 +1859,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; @@ -1887,6 +1894,7 @@ static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git, bitmap_unset(to_filter, pos); } + ewah_or_iterator_free(&it); bitmap_free(tips); } @@ -2502,12 +2510,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); } @@ -2519,6 +2527,8 @@ static uint32_t count_object_type(struct bitmap_index *bitmap_git, count++; } + ewah_or_iterator_free(&it); + return count; } @@ -3046,13 +3056,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; @@ -3093,6 +3103,8 @@ static off_t get_disk_usage_for_type(struct bitmap_index *bitmap_git, } } + ewah_or_iterator_free(&it); + return total; } From patchwork Thu Aug 15 21:01:58 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13765167 Received: from mail-ot1-f49.google.com (mail-ot1-f49.google.com [209.85.210.49]) (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 B85E614E2D8 for ; Thu, 15 Aug 2024 21:02:00 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.49 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755722; cv=none; b=kFrFwhSaWhOam8ycce9CSl/JMhIloCviWrq59QgVy3yReFMfn7WunEOkEowMhNgUV4w9pRN8S7NPJBmcCu5K+Bc8aqnLioHNhmB+InmgtPGxKsS9GEEQ8EuqECIDDAycy8o+HY/2/gv2XRICAva0/wI3W1+BYQsxkwE+ZJxCbF8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723755722; c=relaxed/simple; bh=2EN5w4WRwqubDhsghx1+U2Q57zYOP9x8OzM5kZNhqjA=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=UVtARU9SkgQsqmCTJPlP03l0urf6MTNjubvkGNnHPZwZFnZjEOqJ5g0yE80ZBn4dI1BUwGpIdwA85tcH/TXy/InrZKsK2XwPnSg5oSWR2btf8hz7ExTOKAp66LCEf3teWcY2UBE13mkgKeNmBIKvFb7kFpkRddmB5sUzdOJr/Rc= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com; spf=none 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=2efi+TLO; arc=none smtp.client-ip=209.85.210.49 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=ttaylorr.com Authentication-Results: smtp.subspace.kernel.org; spf=none 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="2efi+TLO" Received: by mail-ot1-f49.google.com with SMTP id 46e09a7af769-70936061d0dso919030a34.2 for ; Thu, 15 Aug 2024 14:02:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723755719; x=1724360519; 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=ghC4BXI7kqs9bsSqUTWFosomIzwkFW9zkMobzORZmXI=; b=2efi+TLOmLpw8jyEnOj2MbSK7IJqaX2zCOKj3gKOFw8h0VigTzwKUUSof9+PnLTD1C yQQw+zxMU5XZMIryyVRwukHUrfnuR9NTW2GQhlsHqQw0UnU49JonHfzbGvFviRd0diqu DD/t2SDVrdaZC9GNNWhZu96AkdSHRLAShxE22TJHPxaMnIhzErynzanoHU0QA/j9oFUQ X0TVs+rYCecNqAxEULbckNuNJMMcfJjy7bmjQ19Ttvm+ct9pTBWY2DrqB2G9AAOAlDIn HmQh055Q+Gh01P60vDnnWEIrvzc4pmUC+t6n1xr44jCzK0GGhNiAMufymocUwu6FlP/W K/Ww== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723755719; x=1724360519; 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=ghC4BXI7kqs9bsSqUTWFosomIzwkFW9zkMobzORZmXI=; b=pedryKKSapfmP81zp0ycHgEUMCxt2U8KcfTWKuUZlsJgNuT27CVa5J26KfvFIBjwsm 5y8EH7w9p9/O64wIpvwv9q7/S6vCbAGfvo9E0VULS2CgvCo+Kb8O9mDRPyxvNYn6oS/t qVKLzKX5dT1O8CeTDR1dGK7cyh/fAOaKD5Ge5o7A1b6IcB4Gn3RmFuFqHYZJkwfolyUY dc/AI4Fn+dW/NF710YT/4cycze1KsOkVAdu7kGcSiyJtaStgHt11sC3LZBtPTUVSGJpf fGxhV/Ek9/zbaIXOaSdIXip3MOsZvXbXjlHlQmXih4mRR9hxxN9a4HlkwjLWdFSNIpMf YLeQ== X-Gm-Message-State: AOJu0YxRMsaLPC4Ye/QHkIkIS3DW7aIBb5wROw51G5ENBsy/3SZy1hRg S/Im5hFWXmzpMpSgSzz439TINP4rlPayHWpulUQqXA/sU1u2CwtAYQGMOPmr9675dpmnFgwVy/h d X-Google-Smtp-Source: AGHT+IGTIcCzoIpw3IXxXtc3tic9+wl3N9xZttzqoCqXKW9kwgB3PgZu3jf0S57X++qmhLKcIqrOQg== X-Received: by 2002:a05:6830:a90:b0:703:7a77:d7d7 with SMTP id 46e09a7af769-70cac89dca2mr1092096a34.28.1723755719449; Thu, 15 Aug 2024 14:01:59 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id 00721157ae682-6b0ebd8a85bsm2106057b3.66.2024.08.15.14.01.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 14:01:59 -0700 (PDT) Date: Thu, 15 Aug 2024 17:01:58 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH 13/13] midx: implement writing incremental MIDX bitmaps Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Now that the pack-bitmap machinery has learned how to read and interact with an incremental MIDX bitmap, teach the pack-bitmap-write.c machinery (and relevant callers from within the MIDX machinery) to write such bitmaps. The details for doing so are mostly straightforward. The main changes are as follows: - find_object_pos() now makes use of an extra MIDX parameter which is used to locate the bit positions of objects which are from previous layers (and thus do not exist in the current layer's pack_order field). (Note also that the pack_order field is moved into struct write_midx_context to further simplify the callers for write_midx_bitmap()). - bitmap_writer_build_type_index() first determines how many objects precede the current bitmap layer and offsets the bits it sets in each respective type-level bitmap by that amount so they can be OR'd together. Signed-off-by: Taylor Blau --- builtin/pack-objects.c | 3 +- midx-write.c | 35 +++++++---- pack-bitmap-write.c | 65 ++++++++++++++----- pack-bitmap.h | 4 +- t/t5334-incremental-multi-pack-index.sh | 84 +++++++++++++++++++++++++ 5 files changed, 161 insertions(+), 30 deletions(-) diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c index e23c4950ed..9e61ff7ca3 100644 --- a/builtin/pack-objects.c +++ b/builtin/pack-objects.c @@ -1342,7 +1342,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 81501efdda..bac3b0589a 100644 --- a/midx-write.c +++ b/midx-write.c @@ -826,20 +826,26 @@ static struct commit **find_commits_for_midx_bitmap(uint32_t *indexed_commits_nr return cb.commits; } -static int write_midx_bitmap(const char *midx_name, +static int write_midx_bitmap(struct write_midx_context *ctx, + const char *object_dir, const char *midx_name, 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(midx_hash)); + struct strbuf bitmap_name = STRBUF_INIT; + + if (ctx->incremental) + get_split_midx_filename_ext(&bitmap_name, object_dir, midx_hash, + MIDX_EXT_BITMAP); + else + get_midx_filename_ext(&bitmap_name, object_dir, midx_hash, + MIDX_EXT_BITMAP); trace2_region_enter("midx", "write_midx_bitmap", the_repository); @@ -858,7 +864,8 @@ static int write_midx_bitmap(const char *midx_name, for (i = 0; i < pdata->nr_objects; i++) index[i] = &pdata->objects[i].idx; - bitmap_writer_init(&writer, the_repository, pdata); + bitmap_writer_init(&writer, the_repository, pdata, + ctx->incremental ? ctx->base_midx : NULL); bitmap_writer_show_progress(&writer, flags & MIDX_PROGRESS); bitmap_writer_build_type_index(&writer, index); @@ -876,7 +883,7 @@ static int write_midx_bitmap(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); @@ -884,11 +891,11 @@ static int write_midx_bitmap(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", the_repository); @@ -1072,8 +1079,6 @@ static int write_midx_internal(const char *object_dir, trace2_region_enter("midx", "write_midx_internal", the_repository); 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, @@ -1115,6 +1120,12 @@ static int write_midx_internal(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(get_midx_checksum(m))); + result = 1; + goto cleanup; + } ctx.num_multi_pack_indexes_before++; m = m->base_midx; } @@ -1404,8 +1415,8 @@ static int write_midx_internal(const char *object_dir, FREE_AND_NULL(ctx.entries); ctx.entries_nr = 0; - if (write_midx_bitmap(midx_name.buf, midx_hash, &pdata, - commits, commits_nr, ctx.pack_order, + if (write_midx_bitmap(&ctx, object_dir, midx_name.buf, + 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 923f793cec..8fc979cbc9 100644 --- a/pack-bitmap-write.c +++ b/pack-bitmap-write.c @@ -25,6 +25,8 @@ #include "alloc.h" #include "refs.h" #include "strmap.h" +#include "midx.h" +#include "pack-revindex.h" struct bitmapped_commit { struct commit *commit; @@ -42,7 +44,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) @@ -50,6 +53,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); @@ -104,6 +108,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(); @@ -133,19 +142,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: @@ -198,19 +207,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) @@ -577,7 +604,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) @@ -1010,7 +1037,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; @@ -1036,6 +1063,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, @@ -1044,7 +1077,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 ff0fd815b8..4242458198 100644 --- a/pack-bitmap.h +++ b/pack-bitmap.h @@ -110,6 +110,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; @@ -124,7 +125,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 c3b08acc73..0b6d45c8fd 100755 --- a/t/t5334-incremental-multi-pack-index.sh +++ b/t/t5334-incremental-multi-pack-index.sh @@ -43,4 +43,88 @@ test_expect_success 'convert incremental to non-incremental' ' compare_results_with_midx 'non-incremental MIDX conversion' +write_midx_layer () { + n=1 + if test -f $midx_chain + then + n="$(($(wc -l <$midx_chain) + 1))" + fi + + for i in 1 2 + do + test_commit $n.$i && + git repack -d || return 1 + done && + git multi-pack-index write --bitmap --incremental +} + +test_expect_success 'write initial MIDX layer' ' + git repack -ad && + write_midx_layer +' + +test_expect_success 'read bitmap from first MIDX layer' ' + git rev-list --test-bitmap 1.2 +' + +test_expect_success 'write another MIDX layer' ' + write_midx_layer +' + +test_expect_success 'midx verify with multiple layers' ' + git multi-pack-index verify +' + +test_expect_success 'read bitmap from second MIDX layer' ' + git rev-list --test-bitmap 2.2 +' + +test_expect_success 'read earlier bitmap from second MIDX layer' ' + git rev-list --test-bitmap 1.2 +' + +test_expect_success 'show object from first pack' ' + git cat-file -p 1.1 +' + +test_expect_success 'show object from second pack' ' + git cat-file -p 2.2 +' + +for reuse in false single multi +do + test_expect_success "full clone (pack.allowPackReuse=$reuse)" ' + rm -fr clone.git && + + git config pack.allowPackReuse $reuse && + git clone --no-local --bare . clone.git + ' +done + +test_expect_success 'relink existing MIDX layer' ' + rm -fr "$midxdir" && + + GIT_TEST_MIDX_WRITE_REV=1 git multi-pack-index write --bitmap && + + midx_hash="$(test-tool read-midx --checksum $objdir)" && + + test_path_is_file "$packdir/multi-pack-index" && + test_path_is_file "$packdir/multi-pack-index-$midx_hash.bitmap" && + test_path_is_file "$packdir/multi-pack-index-$midx_hash.rev" && + + test_commit another && + git repack -d && + git multi-pack-index write --bitmap --incremental && + + test_path_is_missing "$packdir/multi-pack-index" && + test_path_is_missing "$packdir/multi-pack-index-$midx_hash.bitmap" && + test_path_is_missing "$packdir/multi-pack-index-$midx_hash.rev" && + + test_path_is_file "$midxdir/multi-pack-index-$midx_hash.midx" && + test_path_is_file "$midxdir/multi-pack-index-$midx_hash.bitmap" && + test_path_is_file "$midxdir/multi-pack-index-$midx_hash.rev" && + test_line_count = 2 "$midx_chain" + +' + test_done