From patchwork Thu Aug 15 22:28: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: 13765232 Received: from mail-yw1-f170.google.com (mail-yw1-f170.google.com [209.85.128.170]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 808141552EE for ; Thu, 15 Aug 2024 22:28:55 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.170 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760937; cv=none; b=GoE+gGSJoxY5Pk5s3CiCuHYSWd3in7miDywOdTxroq2LPCVYyE3sx0xCCggul+k+GHKZqn0sI5eRm7ySAALbWYUfLzTh6VobeRnkpTJnN497YOoNkT50dxnBpQxHDi36ptbC0Yx6h6qtTkYhkHzMkLTUE6frLupqlFmhse+f59M= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760937; 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=ghaF2/v72tGFPPOMv01iety3XgtAsxGv/GBThYYgcRAEKaZCmhSRjTmc9/u0wGLfK10KkaKabAERAL5sp6KAmWVRQPxjYtgASrhI0Xdd9Tp7MeuG2cJlLW1Vc/WOvXjTdOdDDpT8TUD6hi42IPvk7avLW4UK2JXOn75WVmSSmKc= 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=PcAGcBd+; arc=none smtp.client-ip=209.85.128.170 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="PcAGcBd+" Received: by mail-yw1-f170.google.com with SMTP id 00721157ae682-690b6cbce11so14126487b3.2 for ; Thu, 15 Aug 2024 15:28:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723760934; x=1724365734; 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=PcAGcBd+N+uK6KYzj53v/Y8sVOyNgfuc6xLJoJM8yhKBnmcNCYyHXSkRfPQEgMbm1o MOvAe6pLgqkAkVUO2yTAlmoUjgDpQsRdUApi+uUeR4+HcmqxBVcPk8Cobl8atW0yXhPN BqydHWbN7b1OuV6zyg0JvySgCSWsLzw/iQ5ehsRDumC2EhlVcJSrv7ZEQtfFX9kS+ykR FXE8ypXL9peAGMvqaVojvUdyjNIBt/A7bcmT6MWDkVQu+jeM4BZCS+JIanywoQonYLLI MI0BYOu/OJA4HRZjA9wiVygYFWadFg7+h6dDSNN0/S1vRRTgglQGCqBseq2ACn1exWzx tclA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723760934; x=1724365734; 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=YdS8SrHdPqT6mG+G83T6rjsL31ONZgw2zXfMYav33QViosESTq3rIrsDCHHHs1ssgs 7gJWNdm2775uQUxHeEKJCtO/ovkRqC4cWhsR8NezMYEAmtPXwDuPHbZKB3xJ4oGukBwf TIYvNkjcjFf56FR/1FjQz5Ny6Ly0tCQpuGPmko+76HBft0U41lMGVfDojsUj/RLzy3TG wPTo/4l9Ms6rw3BtCpx+fK97wF/5ezLMibLxn7tsosRsUKQrHsrTXnZRugdxgFRqdfJD ClcFXH6jYUtER6bvloN1SsX3QmBTZBv9a5sjN6QE09xiJUH7XnPujRQjhYPo1umbuoKY 8t9A== X-Gm-Message-State: AOJu0Yw0wodQ9iSo4FdwJvSZhBDYGSX6NaEzKsDFZyPhOaW5y0m7r7+e U8sYG5M1Lv1a0Dwxo7Yo+B19EszQMh9uXx9TjPn24DJfi9CMO6T5UnwMhpWjIL9Omh1KW8r17C/ 2 X-Google-Smtp-Source: AGHT+IH/qIjqmoR7HGb1KNpDEiKVXem3+ofn9tRW+GF2gnDG7XNuXI7v9qN7cgWjJF9V2DUEzaUL6g== X-Received: by 2002:a05:690c:dce:b0:64b:2f31:296b with SMTP id 00721157ae682-6b1b7597f8emr14400267b3.4.1723760934218; Thu, 15 Aug 2024 15:28:54 -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-6af9e1db793sm4127197b3.135.2024.08.15.15.28.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 15:28:53 -0700 (PDT) Date: Thu, 15 Aug 2024 18:28:52 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH v2 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 22:28: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: 13765233 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 B424E1552EE for ; Thu, 15 Aug 2024 22:28:58 +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=1723760940; cv=none; b=UBvk/yl4A3EhEnLA6/c7KBdrE0OLmxqEsmSsN9dMb6cXtDK84OY+vDDOa748BMn1iHXpj9eAclI446Br4+sMKDzS7Zm5uvj7ApLJEJZq1L9tbFyXgBNvl8UoeoALcxO9DAFc63cCozWsFO5LfeJUbC96ZGAqkLt7Tros0o4Xzsk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760940; 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=JtKtnQrDZN5Tr9nxaudG2mhAenvFWFngxEPORqsF3UlpUN4tinctssq8YkQJOxaUQM4wSG8uFwn7TK8su2jWE5jud362xLpF+ecBWo9cze4P1+D3ve85A6nrmb8zfqwbN8NUqm5XXLwQnHpDjmc9mENyKqfirgkw0rdl/Lf5qmE= 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=iO2MT6kL; 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="iO2MT6kL" Received: by mail-yw1-f182.google.com with SMTP id 00721157ae682-68518bc1407so15652497b3.2 for ; Thu, 15 Aug 2024 15:28:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723760937; x=1724365737; 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=iO2MT6kL4i8z+4ZT9FNqV24T/i5sTAhI5BIGiOwmKcuWHPXZ1D/MQ/3Irx+XtoiX2f CZZHGgxDuOIFX8jg00RnIRKQdF1LtId7JQKdZOKSPnRafmfvbQoJZkyru/gySQzkIuwq xzVmJYHhh5JCDhA2OcB2DAP2/Cl16wZFgkG5nXpd5UVjrDecWxOM7g+dwcSttOSrKy2j OrDYd8uboV+mIw664qShCy1W97A3JUjN+w2K8OKePWcyahjq6Hq1ZqYgm+a1BJpS2p2h e3xH9mTyGxaPhHxibylr9OZXu0OIYVOzjl89IwZzCx46Gf6jEQBCBl1b1d1AE50ZzWse GO7g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723760937; x=1724365737; 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=SCUwZd5adg2VOFw2nUypeDzJhE7TyGAvboxNMV0+nQsTdXkJIT81DmuuIT7dPymY3K HfiT1Xa4krlLtMxazQH3Wd87cycbAUZ3QAlTf1tlmfqu9Z7nwl2w85vzs5Hvxs8LhhCZ 8KiR7S5gVYyBkMbC3xZs35YHmACLL8E56FlA+vMpvEy4cjjwmus+eCfFFR2fz0h/yun1 /kRcSEpIa3ET1333cQb42KzY1gwiWL+RZ9he7vOppwYoSNc4jjuIWRzapJMHV/xfIcI3 Bti4xvXkU94Asr/UtONlgej1Ha7K1VtwpluIO/ziSdlQUQ9eEKa7pEcCIAmoATl1z2cV fRsQ== X-Gm-Message-State: AOJu0YxR+r93TbLDr4tJ9Q0pENjR0FwsaTZrSsepkU/HVJE9/MOGmmi3 ob6eoN7POFKetmr98uklQEU50HTrUD8pI3AsGaZ1GuLIs8VNUh+5oLTcIYFJJBykIgCRyqQQyCq L X-Google-Smtp-Source: AGHT+IFtWA19eS9SzFCGMGOQivlPwbcaTkidplfeftPqOK1E+y7Nh6wpP35Pqd9VZErb0X7VK+Fktg== X-Received: by 2002:a05:690c:c8c:b0:6ad:f6ae:768b with SMTP id 00721157ae682-6b1bdb2193bmr13097887b3.31.1723760937219; Thu, 15 Aug 2024 15:28:57 -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-6af9950713dsm4128847b3.26.2024.08.15.15.28.56 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 15:28:56 -0700 (PDT) Date: Thu, 15 Aug 2024 18:28:55 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH v2 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 22:28: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: 13765234 Received: from mail-yb1-f170.google.com (mail-yb1-f170.google.com [209.85.219.170]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 546F915573B for ; Thu, 15 Aug 2024 22:29:01 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.170 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760942; cv=none; b=Q+rCJILxQEJA5DsEzn5Gdkh/LBNBwOnHat+eKgHb6Pu9G94+Lfa9hubl9VzfWkScJ4O/RpDcl0NvTaWT0JfNL5Nn/Esm6QoBn5rgGTl7+Ur1BWC87dChfM8gD6DUOOPvz32kv+lxendSyrLnuRLQyN3KeexyMrh6NH3F4u8nAkc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760942; c=relaxed/simple; bh=0c1BLveCC0VTuedQ7gjhMnuviv9khlUd8jJuVt6QJGc=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=RAPRWhiKkX8tU85zyKYvGBtVY4cstlpO1gPselpbOhMwi/9wn4ZIR3dJSwfnU7QSozLCGW/4VQHIWpJwA8iNnsRYsZrj2SLCA7zRoQrW8G+uajYcHIitvNAf9CfkX9ntjXc58UBwdDmgX8kuUBQnjIzjkuyiauHwGtUXepteqsg= 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=WfrrBx/Y; arc=none smtp.client-ip=209.85.219.170 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="WfrrBx/Y" Received: by mail-yb1-f170.google.com with SMTP id 3f1490d57ef6-e124cdea21bso181038276.2 for ; Thu, 15 Aug 2024 15:29:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723760940; x=1724365740; 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=WfrrBx/Y27V8m0pEcVB6Hd8dYO27wow9jDXetcqxgs3CUB1/JnfE6sVuBCKctwxrWf XFp+k8BcQz1M24K33pnrlh6wy0CIpbQTWXcwQz+GAQXMS5wdywdqOV3SUdXXKI8UcKir xMBtnMSH/GNC5yoqhbnCXcIekpxb48heOosAXc+TyqlY1/M11NNoc1XMP+1wC+xDQGag ivsG5e1nyUjKhOXlm7vgs1a8NVjdsolJvAudLk5b5BTgmHzoXJomIHkQ68UkZBKM6z+6 d77CGVGwzxpJam6ap1uTwPY1zCB19gNOzmPMwVNzRAMLf9DCYudEBnj8TQVAElwnZXP/ 32dA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723760940; x=1724365740; 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=iAkSlpVAv+u/HHpDynO8I6CvHY3YMEj9RtsauNpMsAOX+OuR6CkqaS/jju0dRZrkzQ AhEz+nYhesacmvDExvbUgN6AY5+wSiHoemMk+n6f2SOke/1C8dCLmgJSHOnza78jEJIr iv97zGIN4lYTDuLrPPFr2khKusRpB+gHdmiQdOs/iZTHuOZEkCdZVTRlWH6ldhw6aU05 xSpHD7sb757inID7MDPaVBOcE2rE/zc6b0UQRuibJE8tf5Oy9/Yad+nmUGv9CIgPwX7m uhlL8+Lkeph81juQAU9ZOafGNkj/A4s3n519XlgucnfskJ2BXbsi9+50/Vh2BYJyNFdC 0BtA== X-Gm-Message-State: AOJu0Yw8Xa5MEjqWvh/STKWL7GT0FCmurSeM1yIaOl+UGMtEMebqBNIz JgRQs3XJiWdXsCBQXFAD9SJ1NEJzWC7lsDdwQ35I8W94pN1yTAK3TcDfq/ogxRczhTyKwvxAqxp z X-Google-Smtp-Source: AGHT+IHoCCOTLyXYBaTcgVq0FoJJzoPRDpUb4FnWnQVKKeFzPokqRNKz+kkEHQEzF/y44hjSkGydWA== X-Received: by 2002:a05:690c:3244:b0:64b:8b8f:7770 with SMTP id 00721157ae682-6b1bb95f379mr10432347b3.23.1723760940140; Thu, 15 Aug 2024 15:29:00 -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-6af9e0de828sm4086867b3.130.2024.08.15.15.28.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 15:28:59 -0700 (PDT) Date: Thu, 15 Aug 2024 18:28:58 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH v2 03/13] pack-bitmap.c: open and store incremental bitmap layers Message-ID: <43444efc21415b8817522cbd7b590e1ce38636d5.1723760847.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 22:29:01 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13765235 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 0670615574A for ; Thu, 15 Aug 2024 22:29:04 +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=1723760945; cv=none; b=t+cOd03Z0F+UXm4g9kBYmScvjxQCZm4Eo28n+yaeeHce7BUG+DhahhtMHZxCrcPqiK9YZ/H8NdAInvBMDq0aj5VATfJVPOIZkgbxwnaxEfR5DYwKodHWqD9b9yyFxYLmZUniM8fgUZESTs86b8XEp7q1EKeTSwbbIApSbpYuhL8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760945; 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=KuBvg5eE/AQT2nzr7z6Ez+LiETbRpsfPEdjKu3i+CW1Y0buvWE5IKSYV+z03XnJ3UsGYy0vpxyiUzn9sF9LdrmDSUdtWUkMiy7zUp3jVXrIC7ZIS6ii8kUxuqzxKqJW7CEofHYxGwQnLMnUoFQgypznUEYO8HcWQ9fgdXd77OpE= 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=AF8RVELH; 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="AF8RVELH" Received: by mail-yw1-f169.google.com with SMTP id 00721157ae682-691bb56eb65so14886257b3.0 for ; Thu, 15 Aug 2024 15:29:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723760943; x=1724365743; 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=AF8RVELHqV5gSJxjXIWriuxLPpQsq80ET8TSM1s0kQA8CJcifAU9robUMoJZp4ruPX 9MVzuCj3rhIqNZGTwH/ImQtpGQqgKW3BnZJqwLJdAo70vpmB17I+rf32IXtRAX44RfcE lIo+qhT858xDI67DE2X5YcQuJwtIMZ8uXSBxQW0iiSo2nbEF5ZHjJphyNaRApj7mYSwq XpN5T10JLvpQnoAudiwk55qgminstIBDivS4vu/7CzIITZBp5XX5SB47RkmE2kFvCqQn 5X1gM8T6trwN/Upr1nBdykbXO+YujalDz9yX1URWo9vYp5QQhnDYhVEsAkQ4RzlSCZ8b 4P+w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723760943; x=1724365743; 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=ZEDW69WjrGggQ7g136yJW39avj5TpyCP+cB3MdAy7X7hbLl/nfqPtZ+RXBI7THQxPd u3p6mNPIgeFl6CcJ5N1g/zS1KEin8FNwGZvDergQ5l1dMLxuwurxNok+3fW+xPBpcs3t t4yDq1RDEoakUoaIr0tIJA1WALgSA9nhG/ISuhvQCwVfXHj8w1XKiKHsxZHPl6ztBMU3 O7B8pSry8oHjZ+QgQkNtqdEwGdxQ6cy1ROn2aP6EFu0YTvoxjOzb7K+GwtQGpC9IQ3FW IP6uhj39knSg1C1D/ThuKfrNF1L6LZ5hXnXG9Z1Rky8VTZD44Zc7qYiinIgCd17fR6f7 Ic9Q== X-Gm-Message-State: AOJu0YxM05igV0rDWGjFNo5SJIQO4Ib+FBHL1bm3+Tka3V5ICeFIgr43 zeXLToGP6DnVemeNtNpjrqMFuVuuJfBmeRjpiM5h5r345eU5FEbpiwoEa/Jko+7GlKeYyjGuVxA G X-Google-Smtp-Source: AGHT+IGttVIcHU1Bp3jOUoib0kfj7fMMjnz2JCURlB+d7qIUMyiYQS9OKGodOrbglM1BSBl8RjZIiQ== X-Received: by 2002:a05:690c:6a08:b0:6ae:59e5:5f37 with SMTP id 00721157ae682-6b1b823f19amr14180597b3.13.1723760943005; Thu, 15 Aug 2024 15:29:03 -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-6af9cd7a4b7sm4114517b3.85.2024.08.15.15.29.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 15:29:02 -0700 (PDT) Date: Thu, 15 Aug 2024 18:29:01 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH v2 04/13] pack-bitmap.c: teach `bitmap_for_commit()` about incremental MIDXs Message-ID: <44871306487e5c4c93f619b3c81b651cab3099d6.1723760847.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 22:29:04 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13765236 Received: from mail-yw1-f170.google.com (mail-yw1-f170.google.com [209.85.128.170]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id CB5F915531A for ; Thu, 15 Aug 2024 22:29:06 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.170 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760948; cv=none; b=URH0JY/qZHTpOQBDHdvnMYhJSRJJTACFesRfxoR1bqLaamwCfNt41iIXYkDFeDzenrybachSmUEADnEQTUR2ZI8DNSHE8YQmCNS8zCTEbBLZrjEcJI+lwPEkbbPr2u94/1UQnAbynWvZUARiEGgOfxHR+0oGXz1+OYHc1xEn5k8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760948; c=relaxed/simple; bh=0UuXiDa6CtY6HXjJk3BitUxubH6xt4gi2qL6O8WFYb0=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=EB4jN328CewGnQjEE2IH4kOqODM6Hvd6xeTfX1L+U27MaNIA0DKNPUWnS5lsoC/76fc76GpgSgfSYCVpCgRCYP9eT/7t07HUpGYTCjPatEGKf1jKi9lYmgr5ve62nRqNp0linU8K3ZQq0cBKv/0ejtNIeSR9vuIg82IcamTOrKA= 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=gmCxA6HI; arc=none smtp.client-ip=209.85.128.170 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="gmCxA6HI" Received: by mail-yw1-f170.google.com with SMTP id 00721157ae682-685cc5415e8so14821357b3.3 for ; Thu, 15 Aug 2024 15:29:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723760946; x=1724365746; 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=3fSrcpNaCpuMN/HRO28htMCvmfWZZBMcAta7SD0QG+Q=; b=gmCxA6HIeekN3UTWIUF7zFKUNXS6ySPiM7gIjtWKEI4Swni4nJL2zW5sV6b74csBvQ 0LTHz7FZjg6z0JwjpxOa+zpWnF6ADHoTd+toDhH4SS4v+FlQje0zBCp4zkT9+mUDad+m FIabMu2t1COPsQccQENLPxvASJS5ZgUPHsQvmIqzepWuUi29Kj6HbFOdYKPusieT/A53 +c4lK6D/QDiIh0Wq3KhBPn0zH1CJgv3tZqnUibx8P5ojxJ0BB7SuwbDuz9vLfv999JQi UTmtptRdmXzYSK6fKdDT3xU/yf6ioUd5Azikd+cTV4w6ZDfAXQV6PXQ5jZvRjSu0nq9m bWdw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723760946; x=1724365746; 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=3fSrcpNaCpuMN/HRO28htMCvmfWZZBMcAta7SD0QG+Q=; b=WJX74yBpV8YrNzf+oWDswRkEWzDM5U6V7rT1r4msjfKamjOCpZfbfRJ0KKAzD+6ha8 LTmKowBm9U3shpoDYU8e/SsbV0skD7Q5dQckWxTorEBxKqAD1rVDXdCv13G5+TpYL4+R I8DXfwWclj3O/mhQ3VBn9S+KeW5e9hnN/hy89bT03zMJvB8xb4xqdAaXfjBxbT/URXQe T74wmIBnXKMh6p5BlPT7ohhCL1CHcFMtsv0BFTeKCDDjanqKrWTVjthcNyJ1wlaiWwRQ LKYjY8/Y5hIvl9mR/Dps869IwKDe43QbqfCTbE6cslqjh1VlOtPJDjMjYn0MisQkbOwB 8zxg== X-Gm-Message-State: AOJu0YyV28S1WWhrgCGaQ04Htr8URXVgIhjb3bC8KxohwY7uX0U6msfp DjOJh228nZ0HqvY5fxMImD0vJdqq2e14hy8Gs93SDo84v51SfDsCxY0DgfxdaLMOOUqIrWUdpBt Q X-Google-Smtp-Source: AGHT+IFi11SJEkAIUbWgK0FTiq6CI3aflkkkvuH+/IQdpB5hZNDCgdJpqmrX+kLPspSuZJphCzlebg== X-Received: by 2002:a05:690c:404a:b0:6b0:2031:6414 with SMTP id 00721157ae682-6b1b9592c0dmr11213037b3.24.1723760945820; Thu, 15 Aug 2024 15:29:05 -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-6af9da111f6sm4148157b3.105.2024.08.15.15.29.05 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 15:29:05 -0700 (PDT) Date: Thu, 15 Aug 2024 18:29:04 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH v2 05/13] pack-bitmap.c: teach `show_objects_for_type()` about incremental MIDXs Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Since we may ask for a pack_id that is in an earlier MIDX layer relative to the one corresponding to our bitmap, use nth_midxed_pack() instead of accessing the ->packs array directly. Signed-off-by: Taylor Blau --- pack-bitmap.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 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 22:29:07 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13765237 Received: from mail-yb1-f174.google.com (mail-yb1-f174.google.com [209.85.219.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 3752415531A for ; Thu, 15 Aug 2024 22:29:10 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.174 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760951; cv=none; b=F1XdL/v8UwgRacuvaz25ma1IRdGIerWZ+ZPGDMcaNQQ+ESeL4M+Q2qpmey5hqg81V8dyHnW3i8yiWqLGrSe9ys2Awr/9cIaYT4T118XL7mAfnDxUjfh8UTGo6wQG2EWx+lxM3x18t1qXNkxMRhnJc51WnxvKV3sk24U0LoirZk8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760951; c=relaxed/simple; bh=9Puj252JCV+0q7nJxCgFKrPXVpStAKFjh04Ubmwpwfo=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=HZvV/3Gg8Q1ZmxGhH3qW4dzlk76iiFc1pZQvFQN88l2iD+Ysh8iZ1MKVCoSJyXHuky1ugENQWN71UHfZ0ShCmX59jrzIn/XY73zxeNjCFQKgO9zyioFyNYFkjBs+Eb/7ZCaPEnoNW3JuHatx21qCz3GxCV3PihJARJmLEUKQgC0= 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=tEfMkE/w; arc=none smtp.client-ip=209.85.219.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="tEfMkE/w" Received: by mail-yb1-f174.google.com with SMTP id 3f1490d57ef6-dfef5980a69so1402644276.3 for ; Thu, 15 Aug 2024 15:29:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723760949; x=1724365749; 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=+PkomJj2aPqY5XbmAPT9lA21lSx7aPQei2ZpLNKbdI0=; b=tEfMkE/wNqSz1dMlTczKg5QseNyGM198cX8ty3/0L3pCg6D9Retc9DEC9bUFPjO3gV TSqnKoio+akgBcqHm5xFwWI5KufF6OQm4yUZ4eX0u1d2Vn3j1uTp8rk+yOXpynn9UjoM 0w8Ukp9590//ghSPS6wsjU8tDVxMNChrNeoQtpOYuP6vIe6JQvtzmjuDgRIAvjCr7CW4 5KcIreHMutVW1JnSYDqjal7k03sx2Jo7jOJGflpZFURq235HBgJK5NA9MiYets2nzLhy EVEKMWk+QkOBt8cWkF+O/5BbP8wX6lQUDOHN7rghJ9YqSPp6ViWVQ0lw4kN76B01iuUj ci5w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723760949; x=1724365749; 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=+PkomJj2aPqY5XbmAPT9lA21lSx7aPQei2ZpLNKbdI0=; b=Qd4dHYUPh5QSFh0PmQ5J0xYGgD87uz4vrNYjUruUf4r5oxscTtqJwkIxJTmrZy7Mf0 fXoD5NzBkDTmce46SivMr6NMAQq9l9iRxym9IrlypAkef/+Y2whyfyLR+Hok9HTVUdc6 Tr7x9CsXAOnRQbNXPH/79a0Ql9bjnFfmqbiYBH1bk3P7W6EVZ4FKA3FZuWGVnb3zBcAH QBrDkIIXJBrJyVbaA7o5WK8lBhYDWNcA3JCtMZLuMTFxGsYfOZYJlAHWavbxAbQw2FL5 Se32pxQM69xsDqKrB4avUvJk5aF0J5icqEbhJFg9oE+QLyJVkfzhzT7Z8Ow12+kMG9+0 Uwdw== X-Gm-Message-State: AOJu0YzrNnzNSXK7SPJFZoDjPzxWP/ZdJ84S0p66aV00jTGfcuh9kIVB 9oCEqx9TBC6UvfX2TAcnLl0lgvyTIInRYQQoHqvQge8/X7eXULgt8uPM/iNjkT+lrgsn9ChuKcj U X-Google-Smtp-Source: AGHT+IHrUAj2tv2y7Nnm2TaLM3cicn3uqMR9GDDB3yoX87wSH90nDYPwQ3FSeRLk1WBGjtn9zWQHUw== X-Received: by 2002:a05:6902:2b91:b0:e11:5a47:eb9d with SMTP id 3f1490d57ef6-e1180e96b10mr1524200276.6.1723760948762; Thu, 15 Aug 2024 15:29:08 -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-e1171e3ddc1sm498664276.21.2024.08.15.15.29.08 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 15:29:08 -0700 (PDT) Date: Thu, 15 Aug 2024 18:29:07 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH v2 06/13] pack-bitmap.c: support bitmap pack-reuse with incremental MIDXs Message-ID: <9716d022e0b7a6992dd4630f9719079652b7de35.1723760847.git.me@ttaylorr.com> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: In a similar fashion as previous commits in the first phase of incremental MIDXs, enumerate not just the packs in the current incremental MIDX layer, but previous ones as well. Likewise, in reuse_partial_packfile_from_bitmap(), when reusing only a single pack from a MIDX, use the oldest layer's preferred pack as it is likely to contain the most amount of reusable sections. Signed-off-by: Taylor Blau --- pack-bitmap.c | 11 ++++++++--- 1 file changed, 8 insertions(+), 3 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 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 22:29:10 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13765238 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 1B53815531A for ; Thu, 15 Aug 2024 22:29:12 +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=1723760954; cv=none; b=fevVQ8wiSsbc/+6mqRK98YGR9r4P9HyqUZYwD6dJJq4kV/axFMEolPVQsYjNvIDF7Yq916wvvPlPlDWuIEtbq2s0RPg9F2F6HEgwGYXYBZIzfqKPQhtpWCYh7JDO5BHTr3e6eQbJLaDzbp6mYhub5KEXkYmnQpr0C00JzKm+N4Y= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760954; c=relaxed/simple; bh=Diw2OP53BjtYbKzltDoOm+95IBJ5g3vodhUljHD7fsY=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=pB2G2bEXK/WBhaE3OqYOMdndS5aNDeI9AKKT5KirzmpzAfhUMXY7Ae+mv554o8fmoIP4jqJ8B/LQrF5ABGxtcArOKV6Fh1vnOqp6urmSajjvrxViMZ++1+vFlz/6cI8BjF+hZ5kaWk+qyuKA+fU19fbwNRg6fjwS0rx/qi1gkh8= 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=gAlGGbes; 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="gAlGGbes" Received: by mail-yb1-f179.google.com with SMTP id 3f1490d57ef6-e116e2727dcso1291716276.0 for ; Thu, 15 Aug 2024 15:29:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723760952; x=1724365752; 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=itJ+RhRFSycZejgewS480eUDQpt1Pgfchs0s5vJxBUc=; b=gAlGGbesHAi2IkZvi5Gm9ubYdKIDugmyrbJBH5xBjsZIZ8f9q4/S/sFf0stOadNadq 0PatTJ5Y+CYw9PunJsvaNxPO8zlj0WiYB3S9ypF03VLBaqufB22EOE1kLMYrd1CK2u9O xCQqvGwUm2MSzUmX3/zSjYR4TyztetrzXDROTn25EbKTpoxnZiCSb367S0fUNCLkozPe OL7ebOQxr+MMn1mAWGZIJ39uv+MF/JItgiNvbw8LbKoCF5gewVkwxFlgW8nxHG32FjOR /+QqOOFctLw25QPKQ4W1/7BdS/cQUayCn1/OFEMGIL5B8qvVoU78DcU3e3H+OR4+awKw yBvw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723760952; x=1724365752; 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=itJ+RhRFSycZejgewS480eUDQpt1Pgfchs0s5vJxBUc=; b=NGbhOgws0eJO86frYfBYDWhdS7mnbsw3Nxai2H8I9Nuphl5UNQWSZS5fngHBaRvCus J6KVwBqFvh4eSgDo6IuwjiXkhsO9/93/kjj25MFj94ABiBoNA+x3LxJv1DWg3p6N1zlZ WPFgnji1KqUI2Dzu2AutNUTMTYUgwpRZl8+ReA5UhCBZhDmGUWZsBH6ctkhNwcH5whIx 5S8WmJf9VWTzbgdSjaBgcZpFL4Aa8o1wvj04ozAo1/xkLWwl70KErGA48mclF9RWLjyN iI9P11BgdI205SeB447o0Jc01l9BYvmF6h0EagUWnkx3o9ODaBJYEVYutUwVYKZxAKbm /QcA== X-Gm-Message-State: AOJu0YxbGoyEH7TYS59NXGyMkN+64SuYI0zMemqo2oBFvNH+QI0jDl+N 2QpjLKHyOkP2mwcm1tXo7hcDF6YTZhEc3dHZruazQL8h1Oek4OTWcUc9V4AHP1y+9WeP3Tv/Cca R X-Google-Smtp-Source: AGHT+IGSD8RzCKH12otdsKU6Lvg3YN5fRbI5d2KYCuMSt9J/IDHSlSkoFm5QCYvGRMEBxAOO0asryw== X-Received: by 2002:a05:6902:2004:b0:e11:6cc0:3a94 with SMTP id 3f1490d57ef6-e1180eef11cmr1050851276.27.1723760951660; Thu, 15 Aug 2024 15:29:11 -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-e1171e09d9esm502999276.13.2024.08.15.15.29.11 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 15:29:11 -0700 (PDT) Date: Thu, 15 Aug 2024 18:29:10 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH v2 07/13] pack-bitmap.c: teach `rev-list --test-bitmap` about incremental MIDXs Message-ID: <6baece31750b889a189cf81f6121af162db91354.1723760847.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: Implement support for the special `--test-bitmap` mode of `git rev-list` when using incremental MIDXs. The bitmap_test_data structure is extended to contain a "base" pointer that mirrors the structure of the bitmap chain that it is being used to test. When we find a commit to test, we first chase down the ->base pointer to find the appropriate bitmap_test_data for the bitmap layer that the given commit is contained within, and then perform the test on that bitmap. In order to implement this, light modifications are made to bitmap_for_commit() to reimplement it in terms of a new function, find_bitmap_for_commit(), which fills out a pointer which indicates the bitmap layer which contains the given commit. Signed-off-by: Taylor Blau --- pack-bitmap.c | 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 22:29:13 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13765239 Received: from mail-yw1-f173.google.com (mail-yw1-f173.google.com [209.85.128.173]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 1B110155732 for ; Thu, 15 Aug 2024 22:29:15 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.173 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760957; cv=none; b=FOkMgLBV9DnpWMHgJHp23YYjtHrH/5Uu7pFPvvfgp3bs8qv0gGq9E9vaUWhR5amOJ8KLICvCRKf3/H1c2xuQaN1zYP7Ow6vN/4V4/mhRohef3WPZKXMyaPj0IfoO0KdGpjPMeiQwH+I5/sVY6erY5xEZK21DHCM0xjguXYPXNys= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760957; c=relaxed/simple; bh=aVJTg+WQTBfnWbKVhrLnlAbnIXS5sQnM+pLBvDomHKE=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=uqOiybAJhu3uxuyxwZgkng7QuGlc2Hgqug+MAOfROvxcy3uBCGUJnTgpwMKH0rL5NVX9Y+ioCHypIj3JM1IGiBr4pmsF1P4mToUdm5BCd2WBkM127gJhKOte8m4RVyCQkPm1bFP8tk3crZwshWSw4J2d8LCVCsKhTOQxJBDVmR4= 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=Fzt1Xdrj; arc=none smtp.client-ip=209.85.128.173 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="Fzt1Xdrj" Received: by mail-yw1-f173.google.com with SMTP id 00721157ae682-690af536546so14415727b3.3 for ; Thu, 15 Aug 2024 15:29:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723760955; x=1724365755; 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=zJJjjljJmJjzh5CXSIPmQlY53lAKEdTONAOuWTAY+d0=; b=Fzt1Xdrj4NmgvrMh1aK9qLtZNNsVXCQoudRH0Jte3J5aYhWPf3UWMzB+6+BqTlvRQA 7tmDcIOPkEp3AR/++OM6ZyVQlHvLvAGMEVfPAkl0Bhj8DGVsUXIZtjOLgdislksjBuIf vuai2UG/vzvJ5cgO3yBS9yKaPKbGYnNS65oxC0291jeKhabQCEIWOe/q2MmQG4iRlUCs 9c3/rSTID2vV/sjtlx1FEIrpPCdudtK2PxrE8Wz22WVjYuLExnh1PP62Q9nxN7squ9u0 9ThJFe0ndR3Xy6NN+7U27FndZGigPdLJkAzi9tMcBZeAPD5dLiUIGtkurjuCBwus7TcJ 4evA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723760955; x=1724365755; 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=zJJjjljJmJjzh5CXSIPmQlY53lAKEdTONAOuWTAY+d0=; b=m1SAD2vgOih3gzbsFUaIYzk3K4wZi+jSw9qLQMNXUirGyOs7+J5b9ERe98L3ZtLFTg VXN06IFk2tMEft4+sIgE6WpC9eLimvy2ztjXh7iuPiZPNCP1U3+emkT6c31UxyGqQ0hH X+UgMZdUf1odd0FZCVOzswOFRmWidRhuCz+3Z5JPmrMS9CcZqHsaAb79nDSEiMqqHs0O TZssTs9f3NtQg0cb29FaA9/n4EOPJqUk/FfHhOjZfr+aJFr7rXeuGb/KS9arwd9Fiduq 47snXWcm2oSaugMhl6lNbqUOxsqK+m21SmIxbTl/BbUU5OVC7N+Y6mEaUCksEr3LlDnz 20Jw== X-Gm-Message-State: AOJu0Yz6nVWJkQqpsIqc8MBuU6SSO3/qRQCjW4oSLd2Ef+TV/C2uqzSe sWMNwV2yHdFz+4SVbXta/JBUwk9ZaQPAhGytrMiABsGWtHXfsfxNIYSKuv2nnHA9mF8XTPFMAGZ m X-Google-Smtp-Source: AGHT+IHkChuESEKuudymzHso7qMOOfILEkP99krNxwNuaCq6mWEH5hEYuoMyJrGmY4qS1+MfJ7E0tg== X-Received: by 2002:a05:690c:f94:b0:63b:f919:2e89 with SMTP id 00721157ae682-6b1b7a6ac54mr12629467b3.2.1723760954711; Thu, 15 Aug 2024 15:29:14 -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-6af9cd7aab2sm4148017b3.77.2024.08.15.15.29.14 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 15:29:14 -0700 (PDT) Date: Thu, 15 Aug 2024 18:29:13 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH v2 08/13] pack-bitmap.c: compute disk-usage with incremental MIDXs Message-ID: <5c909df38ad86eb09ca92eda609cd8cda81edca9.1723760847.git.me@ttaylorr.com> References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: In a similar fashion as previous commits, use nth_midxed_pack() instead of accessing the MIDX's ->packs array directly to support incremental MIDXs. Signed-off-by: Taylor Blau --- pack-bitmap.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 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 22:29:16 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13765240 Received: from mail-yw1-f177.google.com (mail-yw1-f177.google.com [209.85.128.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 E3F50155732 for ; Thu, 15 Aug 2024 22:29:18 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.177 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760960; cv=none; b=WIskv6iaUGRKf5wN0gHZ5mSmzWRGnLs8zwNewoLQA2olhQ+y6CwnAYlNQw9C8/PWLu38HnC6YcxFDNsNGVOy/rCkp88JPpyrhYIghtlo8FdUb9XRQ12Szzq6yvx2xyCsraB9uOlvfKA9VUVljPQgfOQH2z+dtX+30B4mQc5XK9c= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760960; 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=qITV34YAGD9Ej8OpwoyPuQi8nCL4xBVj/Djmpfrr5+/esS0urpFNXFscd79MgfxbZUexJwq4iCxVTuZPJX7LRFfcRRG44OJAqiWgStNIgrS7znIZUYW/fpUCbFttD5xx0mYcC64KMogpHDqCW6Fx00aHKDliLoRJuyQET1ShdR0= 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=T+s/HJl3; arc=none smtp.client-ip=209.85.128.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="T+s/HJl3" Received: by mail-yw1-f177.google.com with SMTP id 00721157ae682-690af536546so14416387b3.3 for ; Thu, 15 Aug 2024 15:29:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723760957; x=1724365757; 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=T+s/HJl3ArfnJU09GtfJLmzs/iiQdcvePZ1h4fKlvMtsqT2GN0VxqLWRaLLxxFuc5M DCzbjXYzW9NLYPBZvFdPbeMY/Dp3NhrVfz0nh0VARZXcL/hc/IPtiZ6Olb6HSCYK4lD0 hZiUOqtT1Ts+0M8ofgEnxai2vLEksnfCRfmu7kfBG2j0JMrj11O6q2Tjg7H/B8/pOvs1 /r78lvrTVufmYnzHPiuknTd0fzDwy1d7zi+5SnauTKHXR3UZsimeQ28HSw9IcvMpQcix KJwEW/wvD3v4dTT5wj4sJJFpHUjBJK3WfiTAuRHHFbAS6foPopwNIRoGuehfr7jBOWfT 6EtA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723760957; x=1724365757; 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=DMHHoU/W6i0Q7gnHfDZnzuhEH+sja9Hw2SWyhDUrIvKY26PenRT2mx9Hh1ag4iDbhT wMDgilx4KEYumgN13kc+zhKF+3kTU6zW52sWa/pz5Bipn/MZ1BHB/oAUNdul6PoPMUQ5 +vV4TP3P3yZV8FONc9LQEPy+wYsySq2okZ/D66vM9wN440UDoEkSlyVw01xot8f5ZOhv LBW7ZecwwsS2YlggWOdDp2hcOyD7Rq2slopBfb2JCECSxnWl67iMpBO9yMwpFFj/uozH 2n1czFWw8E5i5u7U3DXmHFnC4JkUW/ja2c3+KOwT2iWVSYdimGSCoQmKGcLhDqF6EmvJ 3C7w== X-Gm-Message-State: AOJu0YxT8d1xMzrlPPPT3bTpUVKF8wtCyUefBr/EpO3BqC3MpQByPLMr BzcoDtMz+HydqCewVvIX22RGjINru8L+s9gEALIs3Pkm3TVZQrtCOnH1GVJerYUsW4M4D2oz0gd K X-Google-Smtp-Source: AGHT+IG0aLy9pgm50kQWPMf/8/G5S6ZtszAjsTBqrzUmhCzx6+myfTXvXR4tyUGhio8qSggihSAm8g== X-Received: by 2002:a05:690c:f94:b0:63b:f919:2e89 with SMTP id 00721157ae682-6b1b7a6ac54mr12630457b3.2.1723760957576; Thu, 15 Aug 2024 15:29:17 -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-6af9e0e0e1fsm4192877b3.133.2024.08.15.15.29.17 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 15:29:17 -0700 (PDT) Date: Thu, 15 Aug 2024 18:29:16 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH v2 09/13] pack-bitmap.c: apply pseudo-merge commits with incremental MIDXs Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: 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 22:29:19 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13765241 Received: from mail-yb1-f181.google.com (mail-yb1-f181.google.com [209.85.219.181]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 19FF01552EE for ; Thu, 15 Aug 2024 22:29:21 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.181 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760963; cv=none; b=QMciYliUkgIJx8MnsnptjkqcNLIEvfEE9LvuVeCkDO8EB++hh8ArtSel52VW60e39YOk1tM5wPQ2eNcToICFYSSqtrjmM3JZXobqdq1rT8fhmwzd4Jyqrj9K3rEnNRsw0OjBD7OeWUPgusK3d49S85hgorITRXKWSxGv2jBGmjE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760963; c=relaxed/simple; bh=e0pUdkypE5N8JOR0223KnhXy7yYCfVdq0REDUuVeAMU=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=bdlneSWkXWMccC+DhUCgC/ipB60ypDymE/EX3UtFZBu8z2kMRVbAMYJEv0Cw0WRB3esqCRd8V7YmN25KGbuiGNuqIqQBwlQjRoB4GV8KpdoxyRt+SSeKfAMGNDbNk+A/rswiu8j+yVtypQJ8tRk/u2vslTnBOUd2/aGEu9ZMnPg= 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=ADK5V+H7; arc=none smtp.client-ip=209.85.219.181 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="ADK5V+H7" Received: by mail-yb1-f181.google.com with SMTP id 3f1490d57ef6-e05f25fb96eso1442706276.1 for ; Thu, 15 Aug 2024 15:29:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723760961; x=1724365761; 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=ADK5V+H7IfoBLAdfLgIsX7hj/3GBxj7qjTNvTmAg+tnMh0XeQyC8ZrxN0BBM3i3aMU p2zmG5UhBucFn0IZ5OqEhObT0eC0wuGE4s0YimzqO5XmRIg29/MUNuc/P5CYQrsrgFi/ HZ60hfMvIg2js2gZxdwiNq50iRtKJySF2LZ28kyfGtCxAc7rozwdcL0gLPNnhnuMyQ+p cOXLovQjKXSP1D0tHramGsEud27NoigypGzPDezQTshwetprk1uGkM9aVXqGmf2nchxO udpJN1m2Bid5yGoNWVPPrfrbD7gtpf6glW0ybT7G0s7MTpoZuS8iC0DltJ3HospQYNP/ yiWw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723760961; x=1724365761; 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=iNntljlVL22oTn7b2uTiaXtkWabl9jD5a54fd/PIA7+/K7zzczzo/zU2+VqsxOwX8N +bA9yZZzM4gPhb9V2uScanrMcZOY4NreIU3+FH77JzCJHdtVVx05tvYyxr8L+JsWzV0e fHU7mY4X+xIWmnizuo/8/W/gpGgX+9aQDPJf62FscNY/2cvctBDwMBkfOQTYGdMmuKZf ni2unV/2XUXM/hhtAghN3pznvYSluf7KT0S2e2iZ1pCXKGQ4KSPqpMRaZE1pqKOSqqdM moal6HPsr5IoVvyA5x/mpatNGLdXD+fJILZorDfuw297vRtl3kwyoPnNNiF6esmE+npB XCDg== X-Gm-Message-State: AOJu0YyzWWLBRTZhJ4oFC6CUsbD7cJhFEt5QFdCtXE3q/hvPMtDwQSay Eei+gEvSQUKbeDDC0Vu1PrlqU67jnbUHwexfphktNNBsLG2mezqtrEuzXcebcrTtY1B7L5B2N97 W X-Google-Smtp-Source: AGHT+IELJjF5axX7xn6DhiCySXYwPkSJRbodbp7jzHXFkpq0uuK70TW+0UN56vJbrkQxnf/3TwPUAg== X-Received: by 2002:a05:690c:2706:b0:64a:4728:ef8 with SMTP id 00721157ae682-6b1be8b6fbbmr10247397b3.44.1723760960789; Thu, 15 Aug 2024 15:29:20 -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-6af99410b80sm4179047b3.10.2024.08.15.15.29.19 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 15:29:20 -0700 (PDT) Date: Thu, 15 Aug 2024 18:29:19 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH v2 10/13] ewah: implement `struct ewah_or_iterator` Message-ID: <04042981c1ad0edb6ab768516cdff341ee278786.1723760847.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 22:29:22 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13765242 Received: from mail-yb1-f182.google.com (mail-yb1-f182.google.com [209.85.219.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 2F568156C5F for ; Thu, 15 Aug 2024 22:29:25 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760966; cv=none; b=kEVbJ1wBJvSHd3RQco3M8P06IyKXIWGOq3AOrvwXecC5Fbbvfg9an8QqF3AC5HC+X4/twbkvq9DgTIp2fdIlr4LjNEK0g2hs+BLIzyErp2XTAqehUB3ZFOvswc+334Eq9awDjVKVuMYhdsA4cgN3Qry+Uj+XiuklSLOOJFC7kw4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760966; c=relaxed/simple; bh=Kbhib89U0y8ygjQysH9AhiuC1dwlrxVvPwUU7EhTViE=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=qe0ahTtXwfcokaX7gMIE+L0OlEh2LAzvHBoKgpflgyLJ06P59uV3iiVE7H+ELNh3DFyn+7tKu+uW4rpWB2n5IAI/0b1sHoLKQwKMt/jng+/c5ANkkTa/aBQMiHYJWIhxlMydkBWtfUY4MEbMTW6eKSM6Alwbho15G385SoiS8cU= 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=tapXi6fw; arc=none smtp.client-ip=209.85.219.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="tapXi6fw" Received: by mail-yb1-f182.google.com with SMTP id 3f1490d57ef6-e11693fbebaso1693236276.3 for ; Thu, 15 Aug 2024 15:29:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723760964; x=1724365764; 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=tapXi6fwxVa5DWejW8dWVommg6NG58Yt2nEPu/dz0HQRYt74F7H5Y8VdMlK3KhAGtQ p2+Ux8xWSO1xqGC5eZNOrcKOaLlsSKdkNBGXjUqlOGCZEuxtVcZLWwtOLSk/foRDqPuc tFnxxlWI7JSNqNEF6Zqdxm6IuEPwZNrYj9IovJzl9L2fNNzS2Bk1G0dziI8mlW4nHhTB 4XkPbh4Jpa0GFdI1B38PbIlsXVJ1c4ppK/Jr5FC+mXBzTf0aPSkAjrqAj+V7r3kKm3/0 XMiWN3oP/Mgt9FndPDYoVuZ62+vdkLtgMI/VaX63PbKo92cAQ+Fkw9LxOsOvMo/XYQNH kmtQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723760964; x=1724365764; 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=NmWNlyJfewhxdWW3rrqtcHIEjznztMZZfGf/wggw491B1tw7HxIlu6gopLa14SRW00 bO2iFbIoJtclvrxt2OLU0tT7aDgXz19od048JlicGI8KQfXJEBB0ld56uAKUzeOM/+GN SGzqT/FXJ8ya/tZwbDoBbJy/TUkqDOpJ9AnL5hctUnAx28739XyTHOgSS5BpmRlIiTWw EBtMkjWjQbMMmsj0NykZZ7B8i/bCJKO5O3opQ4dIbK2xkG7/anm4bg3bND8/lwP9S1Gu hI9JthKgnyjTdulu+qlcHrnrTd8Lzepdiz1SjJr/nO5c/lS4rY5r1eOWnbSkW7lKFNXe UA7g== X-Gm-Message-State: AOJu0YxuVcZeSJmJD0VjZgPIi6d0+xXKd4J2xKA3azm9psFfj383alW5 S6Evbyb7LyTfWAQIhqoFoJbNwVkQ5d/nc7HnV2k28Tpprubp8F3tZB/5XXiEXgaiOcnwb80GWoo j X-Google-Smtp-Source: AGHT+IH4sHjRHWvxC4846j0bQ8NSIWU0+rXIl7l2JnBy/5YMcmbIAeNXW+kVRsGFRSQdmRlHew6TKQ== X-Received: by 2002:a05:690c:4c8e:b0:6b2:6cd4:7fa5 with SMTP id 00721157ae682-6b26cd4802amr381477b3.32.1723760963992; Thu, 15 Aug 2024 15:29: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 00721157ae682-6af9cd7a4a5sm4164317b3.99.2024.08.15.15.29.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 15:29:23 -0700 (PDT) Date: Thu, 15 Aug 2024 18:29:22 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH v2 11/13] pack-bitmap.c: keep track of each layer's type bitmaps Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Prepare for reading the type-level bitmaps from previous bitmap layers by maintaining an array for each type, where each element in that type's array corresponds to one layer's bitmap for that type. These fields will be used in a later commit to instantiate the 'struct ewah_or_iterator' for each type. Signed-off-by: Taylor Blau --- pack-bitmap.c | 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 22:29: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: 13765243 Received: from mail-yb1-f172.google.com (mail-yb1-f172.google.com [209.85.219.172]) (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 0E6E2156F3C for ; Thu, 15 Aug 2024 22:29:27 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.172 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760969; cv=none; b=UTpu8nYkH2pVJ/7etTjZYKj4MoUzO9/kZSpEtJkCzziMn5SL/yIM93jNDgKyZLEehZa1RoTVFthgtcCC6jQ0F/MCY2ZQQrPSqcJLw+i62QTVp4VSv8aDD/g7laAd11nfY/oTlpEowN84PasMztt7Sf5LLdH/SxCPzhE8mCGSsyQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760969; 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=UV0Oxg+meo1UxWwB+VvKldjJLy2BZjzPe6d5km7cN56mP71u8GIGXBqXIi03KCwQmEfkZsRzjm6QjnoI6rvhWM9M+ja1cwSXmXFwtpqcSuJAkN2+KBnHvTb7nl1GBxPw+8sQ1Igba2elokkDuYZxGKq3vMo+muEF/zCAn0kAVlo= 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=w73kfPOs; arc=none smtp.client-ip=209.85.219.172 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="w73kfPOs" Received: by mail-yb1-f172.google.com with SMTP id 3f1490d57ef6-e115ea1b919so1341169276.0 for ; Thu, 15 Aug 2024 15:29:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723760967; x=1724365767; 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=w73kfPOsL3jix4V50NsYX345YdTtMm+DaJ8QSA1iDbX1KLTUVq3amj8VMZ1hc/vR/9 4UEN4sfePtQuzkOztQ/sfO4SGDgucYygRRM7b/S7dcXXqNYnzEP6PwIiG0ub8eaiA4qP WpKeSfgWEgl9FfsObo9YwLXs3TMkCLpS6mWLm+YsENwn8EqacLyKxUwkKY1Zc/P0ystr 7zXStNgxmctbnY7MPONIUmdOo+C53HiON7stsz2hsMLkdiHHdGMa5nF5vgKQzRsyZ2A3 m/ysBaJJyiOV4o26x96MX+q4B4rB/KvcjxYuDGEmGaHj0eamMTxgb5W2qWgMjObhL+CL UMig== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723760967; x=1724365767; 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=E2H7RzaonDUOMiy2eLbzLBT7IJAb8A1m6wKFv01dwULb7zhvgnX9s8fVVny8r6rfoU 75OFm0e24/sPQSZOtjbLqLDCriwyFYIuIeM5n1eQ1+2cn1zSA/fICKuChzftnJZ/lWjR dNODxsoAl7JkJlEU85MyvXaks6x7Y/yF0Yr1nWf9Wogpv3fCRuY5yhaE0Rh7VURHTC7G JFuxxktDGjNHZa326gVcjvdxyfY5Szeybju+T+I7LHrxsCzexm3aiz3q7z3fx6wzeat5 1++tBNPxecFl1bKURYBGGbuGZ7ClrYvHZHYMYSgSzRkRjqyIh4g2YjTmkCLzcpqnqb41 K2bw== X-Gm-Message-State: AOJu0YzNrMmVb9SaUJJMmnv/epV1Cs/+st0tUmS4DOlyqrhtxH2BnP+F a4JFww0BOi8Tjy3LacJAhclLAnZ8JIgq4T7FCZnn4Pff/KniQVfZt4DTifRTmxpSfZgYCRLGjSJ a X-Google-Smtp-Source: AGHT+IGQSU70y4KJBwdpOHJdg9EHZhWff4mzinfsTG8EHyyfNbpNgWz6PGiD/F28f+4IgY/9twLsVg== X-Received: by 2002:a05:6902:18cd:b0:e11:6c6d:8bff with SMTP id 3f1490d57ef6-e1180f152dfmr1466883276.4.1723760966896; Thu, 15 Aug 2024 15:29: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 3f1490d57ef6-e1171e715edsm485476276.35.2024.08.15.15.29.26 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 15:29:26 -0700 (PDT) Date: Thu, 15 Aug 2024 18:29:25 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH v2 12/13] pack-bitmap.c: use `ewah_or_iterator` for type bitmap iterators Message-ID: References: Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Now that we have initialized arrays for each bitmap layer's type bitmaps in the previous commit, adjust existing callers to use them in preparation for multi-layered bitmaps. Signed-off-by: Taylor Blau --- pack-bitmap.c | 42 +++++++++++++++++++++++++++--------------- 1 file changed, 27 insertions(+), 15 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 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 22:29: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: 13765244 Received: from mail-yb1-f172.google.com (mail-yb1-f172.google.com [209.85.219.172]) (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 3480F15575D for ; Thu, 15 Aug 2024 22:29:30 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.172 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760973; cv=none; b=eZErxbqRf+p/JfQGfCQx9CisCwUYxt03YqJOFQJFzQNcRhFNyfccXCXMhE14WfgBvrObYpXQXozYH1P5TfkMD+zBQtHZYECM9ppgMMMMWZKsN74zgM4q5HmILC3VawRtEv0ws6OTWAUUACemOZ7AicqGyCUXB2QKomtlHymwzgE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723760973; 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=fNYVMPnK6ZUd2lIE2kMldxp687E05HquzBRJA5aOxwf4ZBXL0E6f15k+6eJT3rjLIveIMy7I03A6f1ba6t3OsS2IkdSmxcuy6dvKArGeJMw1aYBwreeRHA81R7aIBsPy6Pdm8i2zcIDN41S8g2abhjzM+gLGNv3YNPOOwcJInTs= 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=gFmD0NqL; arc=none smtp.client-ip=209.85.219.172 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="gFmD0NqL" Received: by mail-yb1-f172.google.com with SMTP id 3f1490d57ef6-e0bf9b821e8so1486507276.3 for ; Thu, 15 Aug 2024 15:29:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20230601.gappssmtp.com; s=20230601; t=1723760970; x=1724365770; 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=gFmD0NqLL4rBYE5FZvN/mYUHwcXwT6uvjWcL0tAS011cyjU885Royr6pwOByGtehaf p6i817zaqd7yNIAnyn/iPAAHEFpoucQ3WHKV1LOLzVuOTPUYqKAKkgvFUSPrJ4x1z040 6iJ2R1ZeyLpz48wSo1o4kgGhB59o07jDxtXKHTJOgjVqBSuD4pkkGXcE2zdNMZcWuR/L /swxnmyNfqarDu1ZF5zuUmeZFZcdSjCeXCzA5+Ekzp5/Te+UJE+5bu0WQAsCFm8BH7MZ s/Ul0Q2btqx0Rusg3s6vlAhduIGIfZkOX4cKZipCbss0hm0H5KdOoWBu9AQMdv7ocQC9 WPjg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723760970; x=1724365770; 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=XQxhYwSiuZmGfgPVaCSJmA+HsNZyO0eM+gFkc3pHS2Kffvng5CICH6agtq0HpORrkO kHvT8dCx7qG+EkI7aow8weR4q8SUOEha2ZL+p/0Fc6zG322Q6Y6WbCX8oFPwX/YrgOYd 6qqfiGSSqS8xUCxKlh29WyofvjjmNb93eYerqA8o3BbBqkWBxnmkk+24ULy+ef6O5w5w /UxDY8Q8LTlSPBKl+P5Gf4iY+yEcP0ket1UbySCuEUBtgB5hOVor9zUqwphhD0OC582S jO0tVPPurecI/HrQa/nuL9EGVQC7vziYVeuISkzU0RlDT8RvVGkkf/fKpaYQeCrXqGBm ErFg== X-Gm-Message-State: AOJu0YzcdQ99VYtA688eowFqicuEs2n2SWwOEAYGa55LuNykF9s6GVbr fibVUHv6Kz5G2lbvvPZmD1ciwQseFaScWYyb64s2Bv9td3OYosFdtk/uThZX7Vqb+OV0FMKkxFb / X-Google-Smtp-Source: AGHT+IH5NGvlvIb5FYTexlDC3XwQb9xTpaf9azjhekLEGSoTPpnKKYVhD6jJc+nRsVBSgJXKpsQSJg== X-Received: by 2002:a05:6902:908:b0:e11:5e69:3791 with SMTP id 3f1490d57ef6-e1180ef2c9emr1530978276.34.1723760969796; Thu, 15 Aug 2024 15:29: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 3f1490d57ef6-e11720385bfsm479683276.60.2024.08.15.15.29.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 15 Aug 2024 15:29:29 -0700 (PDT) Date: Thu, 15 Aug 2024 18:29:28 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Junio C Hamano Subject: [PATCH v2 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