From patchwork Wed Apr 22 23:13:24 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 11504695 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 7936714B4 for ; Wed, 22 Apr 2020 23:13:28 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 6184C2076E for ; Wed, 22 Apr 2020 23:13:28 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20150623.gappssmtp.com header.i=@ttaylorr-com.20150623.gappssmtp.com header.b="uSUzIrJl" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726164AbgDVXN1 (ORCPT ); Wed, 22 Apr 2020 19:13:27 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:42494 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-FAIL-OK-FAIL) by vger.kernel.org with ESMTP id S1725839AbgDVXN1 (ORCPT ); Wed, 22 Apr 2020 19:13:27 -0400 Received: from mail-pg1-x543.google.com (mail-pg1-x543.google.com [IPv6:2607:f8b0:4864:20::543]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 13BFBC03C1AA for ; Wed, 22 Apr 2020 16:13:27 -0700 (PDT) Received: by mail-pg1-x543.google.com with SMTP id t11so1897581pgg.2 for ; Wed, 22 Apr 2020 16:13:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to; bh=VS6zc4Di/do5IxU/khW4eZxYKw3AXDshI80+WQY1iEQ=; b=uSUzIrJlZmNWA9TGLfW8C9KxoJDWGzB9uzgm1e4mfYix1NPLLDWE+zJB0L81E5fkMF LoBE7sx8zJcj1srg1IQ0ruVplqtttsBlE7FjVYTdGOqLtjB4KNSoFlTP+3CNKA2udAWM S7HCGezlNWCSoxWoKv3MOV7RSyHSF5x2hA6+6Ev3sRgMjaOswNeSdOkiWu2xZ/bq12HL 4uy7Rr8unbF5K6gsarCPiOsES2SMgS9aQcgGUSFGEI2AkTdk2Qv/+rSO7IzwqVKgkA1A yv95eVsq0fsf6epRqYu8u17kCHyECCh4BWDU+C7FKMDAsgb96GuYgGCNuZICnUxCnQyV 2sLg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to; bh=VS6zc4Di/do5IxU/khW4eZxYKw3AXDshI80+WQY1iEQ=; b=BCC5MSIRraUILhcVX0zSCa5JwxZLJE9U+gTWQ4siDCr1GxShVkJ8UoL4Fpj5crBnFr erN2xft+WpDn81ktFxdFQRurDWSkY/IXInMJ29Yf+6ND9oAWzkEKpIzl99JR8P5koYRm QoQbNW1RjQ6xUfObxS7lrgTybx7mDHhRlTCi2J7IrgdAtaxKkXkMmLK2xqr2aiszTb4Q aBL5fK8Y4+Hxge+gyrkBgyxq31rb05BEfnlUb03zIg/nRYtoJy6RXORYHLudkmUCfrNW FHkydvdxHS+Fooiw/5c3tEI+36MTfk8TmbyFriWCy9w9tcRFU7EK+uHOiAZaljkDgNOX 6fMQ== X-Gm-Message-State: AGi0PuZjNmmcIQ06YtEEo1xiMSWU453Ps9sALAThE4Tf5bCkzuPYN8aa juIt0D3Korr957jR1uV0FPHKoEDRFcu/cA== X-Google-Smtp-Source: APiQypINX7EUdIPI/kG2Sfq6ZT5vVvxYXmvfhksKTyQVZM66L16ODUg/xBLfPtlZqgs73H9jGTKnBw== X-Received: by 2002:a63:615:: with SMTP id 21mr1334375pgg.22.1587597206174; Wed, 22 Apr 2020 16:13:26 -0700 (PDT) Received: from localhost ([8.44.146.30]) by smtp.gmail.com with ESMTPSA id d203sm571931pfd.79.2020.04.22.16.13.25 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Apr 2020 16:13:25 -0700 (PDT) Date: Wed, 22 Apr 2020 17:13:24 -0600 From: Taylor Blau To: git@vger.kernel.org Cc: peff@peff.net, chriscool@tuxfamily.org Subject: [PATCH 1/4] list-objects-filter: treat NULL filter_options as "disabled" Message-ID: References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Jeff King In most callers, we have an actual list_objects_filter_options struct, and if no filtering is desired its "choice" element will be LOFC_DISABLED. However, some code may have only a pointer to such a struct which may be NULL (because _their_ callers didn't care about filtering, either). Rather than forcing them to handle this explicitly like: if (filter_options) traverse_commit_list_filtered(filter_options, revs, show_commit, show_object, show_data, NULL); else traverse_commit_list(revs, show_commit, show_object, show_data); let's just treat a NULL filter_options the same as LOFC_DISABLED. We only need a small change, since that option struct is converted into a real filter only in the "init" function. Signed-off-by: Jeff King Signed-off-by: Taylor Blau --- list-objects-filter.c | 3 +++ 1 file changed, 3 insertions(+) diff --git a/list-objects-filter.c b/list-objects-filter.c index 1e8d4e763d..0a3ef3cab3 100644 --- a/list-objects-filter.c +++ b/list-objects-filter.c @@ -663,6 +663,9 @@ struct filter *list_objects_filter__init( assert((sizeof(s_filters) / sizeof(s_filters[0])) == LOFC__COUNT); + if (!filter_options) + return NULL; + if (filter_options->choice >= LOFC__COUNT) BUG("invalid list-objects filter choice: %d", filter_options->choice); From patchwork Wed Apr 22 23:13:29 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 11504697 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 24865112C for ; Wed, 22 Apr 2020 23:13:34 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 0CDC22074F for ; Wed, 22 Apr 2020 23:13:34 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20150623.gappssmtp.com header.i=@ttaylorr-com.20150623.gappssmtp.com header.b="d+0YJhLk" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726234AbgDVXNd (ORCPT ); Wed, 22 Apr 2020 19:13:33 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:42506 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-FAIL-OK-FAIL) by vger.kernel.org with ESMTP id S1725839AbgDVXNc (ORCPT ); Wed, 22 Apr 2020 19:13:32 -0400 Received: from mail-pj1-x1041.google.com (mail-pj1-x1041.google.com [IPv6:2607:f8b0:4864:20::1041]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 6ED73C03C1AA for ; Wed, 22 Apr 2020 16:13:31 -0700 (PDT) Received: by mail-pj1-x1041.google.com with SMTP id 7so2946199pjo.0 for ; Wed, 22 Apr 2020 16:13:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to; bh=ReCoUBhA6DuS6qYAUTxKUmQY/vAN9JfYI6V6uyzE6G4=; b=d+0YJhLkUUlkwDUMr9LcBZl49ADqeqmK121qebFUNzwn4EiJnsXTa0VTAhJ1vOQgAn 0VnLrHjTyuS+hR8wi9jUiU8viF0bJNrBbo+Wf2x9rMdtvmXl9kOY4H8jv+SsUhkiRFqh ppHG3Fv3Mz2U+jKTCFZF3kGULYYrD64RRjbkuGm+PNnbFvslDkzfxvs8K3cYpF3bUbOc k/wvFT7YS8qOdcwqbt/m6w6RzjfulOMm37q/MTrSyaqTT49Q6uN1Bin3faLrC3H1ksGo voq0K34wT/02cw9zbpUrfP7FOZ2/IQIXSzx7GGHgCyMVQy1Nt1s4N4oj14AoEJvjt/qd NI1A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to; bh=ReCoUBhA6DuS6qYAUTxKUmQY/vAN9JfYI6V6uyzE6G4=; b=ejKvJi7xBS0OMkrDNSq4ZQENQ3DJtxCwSRfetrnjPni8JWZw0RUxMaNQA+AVFJauP4 lLV5OlMbcm2braEYelTY9csB2gR+Q6mCspqtShbvnRB1UclFFvA90GttCZaNbRxJKWV8 6C+UIk3lo6HMILlNILsKQucWQvs0LOY4Osfsz9IeF3vEAPKTAPrrUxMjLuS00XHgQRSW 8PicGg626+OcFrJgfwWffdwP8pR2rwtXMpJzm4Jo6O0r+Sc+XOCPJjrJ7jj3EUoJM85+ AvGTAKRU+Qe5yrBx8qu2pM8SYDPSjzDgm1FZcQk/6htdFfvzsF1jkX4FvwFA4wxf7HRG PjmA== X-Gm-Message-State: AGi0PuYqzp6Wb59eIH+scPLDhGHeNJO5F5cUfuzo02xjNXicGKPFXbKG LwNK81ig+Gnb/wDEZ7MIV6yn94umIHpTqA== X-Google-Smtp-Source: APiQypLzlTXS4ltpyPZxKVgmjX29JvY1Qo7lcHCgjN/pMFKL2dXtB5l6047qCX/ilrpGzYSe3xFLdw== X-Received: by 2002:a17:902:d201:: with SMTP id t1mr1063791ply.328.1587597210568; Wed, 22 Apr 2020 16:13:30 -0700 (PDT) Received: from localhost ([8.44.146.30]) by smtp.gmail.com with ESMTPSA id u15sm291441pjm.47.2020.04.22.16.13.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Apr 2020 16:13:29 -0700 (PDT) Date: Wed, 22 Apr 2020 17:13:29 -0600 From: Taylor Blau To: git@vger.kernel.org Cc: peff@peff.net, chriscool@tuxfamily.org Subject: [PATCH 2/4] pack-bitmap.c: make object filtering functions generic Message-ID: References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org In 4f3bd5606a (pack-bitmap: implement BLOB_NONE filtering, 2020-02-14), filtering support for bitmaps was added for the 'LOFC_BLOB_NONE' filter. In the future, we would like to add support for filters that behave as if they exclude a certain type of object, for e.g., the tree depth filter with depth 0. To prepare for this, make some of the functions used for filtering more generic, such as 'find_tip_blobs' and 'filter_bitmap_blob_none' so that they can work over arbitrary object types. To that end, create 'find_tip_objects' and 'filter_bitmap_exclude_type', and redefine the aforementioned functions in terms of those. Signed-off-by: Taylor Blau --- pack-bitmap.c | 35 ++++++++++++++++++++++++----------- 1 file changed, 24 insertions(+), 11 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 49a8d10d0c..3693c9e62f 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -715,8 +715,9 @@ static int in_bitmapped_pack(struct bitmap_index *bitmap_git, return 0; } -static struct bitmap *find_tip_blobs(struct bitmap_index *bitmap_git, - struct object_list *tip_objects) +static struct bitmap *find_tip_objects(struct bitmap_index *bitmap_git, + struct object_list *tip_objects, + enum object_type type) { struct bitmap *result = bitmap_new(); struct object_list *p; @@ -724,7 +725,7 @@ static struct bitmap *find_tip_blobs(struct bitmap_index *bitmap_git, for (p = tip_objects; p; p = p->next) { int pos; - if (p->item->type != OBJ_BLOB) + if (p->item->type != type) continue; pos = bitmap_position(bitmap_git, &p->item->oid); @@ -737,9 +738,10 @@ static struct bitmap *find_tip_blobs(struct bitmap_index *bitmap_git, return result; } -static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git, - struct object_list *tip_objects, - struct bitmap *to_filter) +static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git, + struct object_list *tip_objects, + struct bitmap *to_filter, + enum object_type type) { struct eindex *eindex = &bitmap_git->ext_index; struct bitmap *tips; @@ -747,18 +749,21 @@ static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git, eword_t mask; uint32_t i; + if (type != OBJ_BLOB) + BUG("filter_bitmap_exclude_type: unsupported type '%d'", type); + /* * The non-bitmap version of this filter never removes - * blobs which the other side specifically asked for, + * objects which the other side specifically asked for, * so we must match that behavior. */ - tips = find_tip_blobs(bitmap_git, tip_objects); + tips = find_tip_objects(bitmap_git, tip_objects, type); /* * We can use the blob type-bitmap to work in whole words * for the objects that are actually in the bitmapped packfile. */ - for (i = 0, init_type_iterator(&it, bitmap_git, OBJ_BLOB); + for (i = 0, init_type_iterator(&it, bitmap_git, type); i < to_filter->word_alloc && ewah_iterator_next(&mask, &it); i++) { if (i < tips->word_alloc) @@ -773,7 +778,7 @@ static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git, */ for (i = 0; i < eindex->count; i++) { uint32_t pos = i + bitmap_git->pack->num_objects; - if (eindex->objects[i]->type == OBJ_BLOB && + if (eindex->objects[i]->type == type && bitmap_get(to_filter, pos) && !bitmap_get(tips, pos)) bitmap_unset(to_filter, pos); @@ -782,6 +787,14 @@ static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git, bitmap_free(tips); } +static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git, + struct object_list *tip_objects, + struct bitmap *to_filter) +{ + filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter, + OBJ_BLOB); +} + static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git, uint32_t pos) { @@ -820,7 +833,7 @@ static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git, eword_t mask; uint32_t i; - tips = find_tip_blobs(bitmap_git, tip_objects); + 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); From patchwork Wed Apr 22 23:13:32 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 11504699 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id D5C39112C for ; Wed, 22 Apr 2020 23:13:38 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id B9EB32076E for ; Wed, 22 Apr 2020 23:13:38 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20150623.gappssmtp.com header.i=@ttaylorr-com.20150623.gappssmtp.com header.b="Hjhe0WXL" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726456AbgDVXNh (ORCPT ); Wed, 22 Apr 2020 19:13:37 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:42518 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-FAIL-OK-FAIL) by vger.kernel.org with ESMTP id S1725839AbgDVXNg (ORCPT ); Wed, 22 Apr 2020 19:13:36 -0400 Received: from mail-pj1-x1041.google.com (mail-pj1-x1041.google.com [IPv6:2607:f8b0:4864:20::1041]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 49B6FC03C1AA for ; Wed, 22 Apr 2020 16:13:35 -0700 (PDT) Received: by mail-pj1-x1041.google.com with SMTP id e6so1646510pjt.4 for ; Wed, 22 Apr 2020 16:13:35 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to; bh=Y1TkIm0sEdPUmBG+UMdtDWlyV9EMXbiFLUMQTeN9rpo=; b=Hjhe0WXLiZ/0wxGZPygamELF83gZohAwTJrSJMvn3aFQ9Atuskxd+kXD8m7z5DLLR3 3OPu1Z5tXuXuAhEGgz7m9DUc3cEja9AOvC7K9JsVNPkS0Yh55EEYEU1Pi2oH8Ecg0vf9 OQZvBdoqYtUmLqGwWh8+mx71ecvRPdZv5trv5/g03IfxsjvL+FTSkgkMzqMoysK9FGFA UpR3aV7ZsSKPreJeRcQBPkM5YxEeFKMT0T9aGpcE5/0sE2oVvN7qAC7b00qFiqtvLQrq /9vpLsYRmiCVlfhh41Oip/32bcwMOPQsijrlREfszVyM+eZSOfQJerbkXGOrPHbTkqKn AcJQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to; bh=Y1TkIm0sEdPUmBG+UMdtDWlyV9EMXbiFLUMQTeN9rpo=; b=gcjpq6hvrxyMACvezK7wr/53WLN63mZYZMVKjxORgKUsdPhKRF0lyAC5yAy8t0rThW A87XcFG2d/q8r0GrPvi9gfCLNGO0Upjo9EYitO41DBi6FawhPx4nOaG4ltJdPmGo8AWM WX1fq9UzU3VRmbl20I7n3tYS1hNoID1s4xGzLNB+Z4nUMhLGJv2yoU8CjRQPXpLyqIKl YN5cdycXgA37PZUuK2Ltlo2Be9nP+Vm84Kn5ZJ75uwkKQgPO5OPaRQSIoWra64vBsE20 VWpmlC8pAOsl/hP4WoJd+QOZHAtuR7KZEoHY5Xt0XMcdO8ucirR8jOq9oLj6ffh+yZ3l uXtw== X-Gm-Message-State: AGi0PuYE4EQ1QAV9DI2o42+FK7zUxKK8Zkde7Z7xRk3jJgr07v/lbzs9 CWbqcKuz3xsFXzr9bQsB0QWmsTpOBldSKQ== X-Google-Smtp-Source: APiQypItxI0vvzIux74i2t35YOxtGxFIOkHc4CCJtLYIO3JKhm/l81ARt1dyP9FWelPpXhG6EpQCKg== X-Received: by 2002:a17:90a:cb0b:: with SMTP id z11mr1163094pjt.62.1587597214212; Wed, 22 Apr 2020 16:13:34 -0700 (PDT) Received: from localhost ([8.44.146.30]) by smtp.gmail.com with ESMTPSA id g22sm312205pju.21.2020.04.22.16.13.33 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Apr 2020 16:13:33 -0700 (PDT) Date: Wed, 22 Apr 2020 17:13:32 -0600 From: Taylor Blau To: git@vger.kernel.org Cc: peff@peff.net, chriscool@tuxfamily.org Subject: [PATCH 3/4] pack-bitmap.c: support 'tree:0' filtering Message-ID: References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org In the previous patch, we made it easy to define other filters that exclude all objects of a certain type. Use that in order to implement bitmap-level filtering for the '--filter=tree:' filter when 'n' is equal to 0. The general case is not helped by bitmaps, since for values of 'n > 0', the object filtering machinery requires a full-blown tree traversal in order to determine the depth of a given tree. Caching this is non-obvious, too, since the same tree object can have a different depth depending on the context (e.g., a tree was moved up in the directory hierarchy between two commits). But, the 'n = 0' case can be helped, and this patch does so. Running p5310.11 in this tree and on master with the kernel, we can see that this case is helped substantially: Test master this tree -------------------------------------------------------------------------------- 5310.11: rev-list count with tree:0 10.68(10.39+0.27) 0.06(0.04+0.01) -99.4% Signed-off-by: Taylor Blau --- pack-bitmap.c | 25 ++++++++++++++++++++++++- t/perf/p5310-pack-bitmaps.sh | 5 +++++ t/t6113-rev-list-bitmap-filters.sh | 21 +++++++++++++++++++++ 3 files changed, 50 insertions(+), 1 deletion(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 3693c9e62f..195ee8cad0 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -749,7 +749,7 @@ static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git, eword_t mask; uint32_t i; - if (type != OBJ_BLOB) + if (type != OBJ_BLOB && type != OBJ_TREE) BUG("filter_bitmap_exclude_type: unsupported type '%d'", type); /* @@ -867,6 +867,20 @@ static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git, bitmap_free(tips); } +static void filter_bitmap_tree_depth(struct bitmap_index *bitmap_git, + struct object_list *tip_objects, + struct bitmap *to_filter, + unsigned long limit) +{ + if (limit) + BUG("filter_bitmap_tree_depth given non-zero limit"); + + filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter, + OBJ_TREE); + filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter, + OBJ_BLOB); +} + static int filter_bitmap(struct bitmap_index *bitmap_git, struct object_list *tip_objects, struct bitmap *to_filter, @@ -890,6 +904,15 @@ static int filter_bitmap(struct bitmap_index *bitmap_git, return 0; } + if (filter->choice == LOFC_TREE_DEPTH && + filter->tree_exclude_depth == 0) { + if (bitmap_git) + filter_bitmap_tree_depth(bitmap_git, tip_objects, + to_filter, + filter->tree_exclude_depth); + return 0; + } + /* filter choice not handled */ return -1; } diff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh index 7743f4f4c9..b629a211f9 100755 --- a/t/perf/p5310-pack-bitmaps.sh +++ b/t/perf/p5310-pack-bitmaps.sh @@ -57,6 +57,11 @@ test_perf 'rev-list count with blob:limit=1k' ' --filter=blob:limit=1k >/dev/null ' +test_perf 'rev-list count with tree:0' ' + git rev-list --use-bitmap-index --count --objects --all \ + --filter=tree:0 >/dev/null +' + test_perf 'simulated partial clone' ' git pack-objects --stdout --all --filter=blob:none /dev/null ' diff --git a/t/t6113-rev-list-bitmap-filters.sh b/t/t6113-rev-list-bitmap-filters.sh index 145603f124..2b551e6fd0 100755 --- a/t/t6113-rev-list-bitmap-filters.sh +++ b/t/t6113-rev-list-bitmap-filters.sh @@ -53,4 +53,25 @@ test_expect_success 'blob:limit filter with specified blob' ' test_bitmap_traversal expect actual ' +test_expect_success 'tree:0 filter' ' + git rev-list --objects --filter=tree:0 HEAD >expect && + git rev-list --use-bitmap-index \ + --objects --filter=tree:0 HEAD >actual && + test_bitmap_traversal expect actual +' + +test_expect_success 'tree:0 filter with specified blob, tree' ' + git rev-list --objects --filter=tree:0 HEAD HEAD:two.t >expect && + git rev-list --use-bitmap-index \ + --objects --filter=tree:0 HEAD HEAD:two.t >actual && + test_bitmap_traversal expect actual +' + +test_expect_success 'tree:1 filter' ' + git rev-list --objects --filter=tree:1 HEAD >expect && + git rev-list --use-bitmap-index \ + --objects --filter=tree:1 HEAD >actual && + test_cmp expect actual +' + test_done From patchwork Wed Apr 22 23:13:35 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 11504701 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 1656114B4 for ; Wed, 22 Apr 2020 23:13:42 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id EFE5A20776 for ; Wed, 22 Apr 2020 23:13:41 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20150623.gappssmtp.com header.i=@ttaylorr-com.20150623.gappssmtp.com header.b="bC1fmTdv" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726448AbgDVXNk (ORCPT ); Wed, 22 Apr 2020 19:13:40 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:42530 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-FAIL-OK-FAIL) by vger.kernel.org with ESMTP id S1725839AbgDVXNj (ORCPT ); Wed, 22 Apr 2020 19:13:39 -0400 Received: from mail-pj1-x1042.google.com (mail-pj1-x1042.google.com [IPv6:2607:f8b0:4864:20::1042]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C3C1EC03C1AA for ; Wed, 22 Apr 2020 16:13:38 -0700 (PDT) Received: by mail-pj1-x1042.google.com with SMTP id e6so1646561pjt.4 for ; Wed, 22 Apr 2020 16:13:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to; bh=Jn1rNT7YWZIH2z0oO6A1dqXvoIOrx2rvWO0vbd1gErY=; b=bC1fmTdv56iQqpgh5dUGoCZzw311YmKyU0hnz9r5uQto4KZ/Vy3Yqh/KQPAkJGYqT7 S+YZVCfzz7swXbTz/DxTye23DWX4Zro3bEDAeBxgxXR9rDNJsz+DexOG1Sk9KLRBTHwd iF/3RwstlYSBNvExdBf7vO/+vJGhBNXp2e77ckIjCV0zdA84yD7Kqy5VVWqzJJdJCMHX YzPS+rO4L0UR5OvzyvRr25XQpiXPfgC//qsTPTCLOqIc7bAsQ37WDRosppAMsq5yeCBG Boo2oPrMbgQqfS59maCxiiN4oRTAvAPxHHwMTNYvFZ+0vTTHcw6DuzY6+kIaB7WzCBCb oRpA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to; bh=Jn1rNT7YWZIH2z0oO6A1dqXvoIOrx2rvWO0vbd1gErY=; b=I5RvwntfF/AGJ6N81CXWA5ihffNJ1icH8Lr2o866J1bBCwNE2bwRsp0yKpfXh1Wf9F BxPqlunvmQoPXReFKbWskJK1HKhjXKqouZvZegw6qfL8qex/+Lgm8lSdtf9VKP+ycFTk jVBnPV7K6SlyDmw49ocnYGztoNZM6aTOWzM0uQi1UviNSpgxvYKT0+sjWU6X+TTaPyRn mmelyfPWSTBaeQ4vMlQHDExhLn7gqIqa34EALcK17vtyxofVEIKm2VHfP2tZBMODcuBY NVt+Iu6J9NGFNlJGSIVZwAIZdLITGO2FIRHU+ysff/RvjTh5XN6baE/4T+Ld6ROgSmlw OS7w== X-Gm-Message-State: AGi0Pua17Hg2IHRGUq0mERKnH5TyjKIehAbD9BDgtbEdVPPVSqA0gC1a ILSYxKj3A2e4jA4+cXI34f4PnnKUAGuSAw== X-Google-Smtp-Source: APiQypLpEYTRdZxxeseEquuubYj/xaJsaQP/b0r7tRGQU6XTpbR+6qjG+o4Yk8kNLV1VFU/Nh8UuuQ== X-Received: by 2002:a17:902:d693:: with SMTP id v19mr1083415ply.9.1587597217690; Wed, 22 Apr 2020 16:13:37 -0700 (PDT) Received: from localhost ([8.44.146.30]) by smtp.gmail.com with ESMTPSA id w75sm568519pfc.156.2020.04.22.16.13.36 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 22 Apr 2020 16:13:37 -0700 (PDT) Date: Wed, 22 Apr 2020 17:13:35 -0600 From: Taylor Blau To: git@vger.kernel.org Cc: peff@peff.net, chriscool@tuxfamily.org Subject: [PATCH 4/4] pack-bitmap: pass object filter to fill-in traversal Message-ID: <65467a058e7dca6cf1e2db9cdab81513989b5db0.1587597151.git.me@ttaylorr.com> References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Jeff King Sometimes a bitmap traversal still has to walk some commits manually, because those commits aren't included in the bitmap packfile (e.g., due to a push or commit since the last full repack). If we're given an object filter, we don't pass it down to this traversal. It's not necessary for correctness because the bitmap code has its own filters to post-process the bitmap result (which it must, to filter out the objects that _are_ mentioned in the bitmapped packfile). And with blob filters, there was no performance reason to pass along those filters, either. The fill-in traversal could omit them from the result, but it wouldn't save us any time to do so, since we'd still have to walk each tree entry to see if it's a blob or not. But now that we support tree filters, there's opportunity for savings. A tree:depth=0 filter means we can avoid accessing trees entirely, since we know we won't them (or any of the subtrees or blobs they point to). The new test in p5310 shows this off (the "partial bitmap" state is one where HEAD~100 and its ancestors are all in a bitmapped pack, but HEAD~100..HEAD are not). Here are the results (run against linux.git): Test HEAD^ HEAD ------------------------------------------------------------------------------------------------- [...] 5310.16: rev-list with tree filter (partial bitmap) 0.19(0.17+0.02) 0.03(0.02+0.01) -84.2% The absolute number of savings isn't _huge_, but keep in mind that we only omitted 100 first-parent links (in the version of linux.git here, that's 894 actual commits). In a more pathological case, we might have a much larger proportion of non-bitmapped commits. I didn't bother creating such a case in the perf script because the setup is expensive, and this is plenty to show the savings as a percentage. Signed-off-by: Jeff King Signed-off-by: Taylor Blau --- pack-bitmap.c | 14 +++++++++----- t/perf/p5310-pack-bitmaps.sh | 5 +++++ 2 files changed, 14 insertions(+), 5 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 195ee8cad0..4077e731e8 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -506,7 +506,8 @@ static int should_include(struct commit *commit, void *_data) static struct bitmap *find_objects(struct bitmap_index *bitmap_git, struct rev_info *revs, struct object_list *roots, - struct bitmap *seen) + struct bitmap *seen, + struct list_objects_filter_options *filter) { struct bitmap *base = NULL; int needs_walk = 0; @@ -599,8 +600,9 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git, show_data.bitmap_git = bitmap_git; show_data.base = base; - traverse_commit_list(revs, show_commit, show_object, - &show_data); + traverse_commit_list_filtered(filter, revs, + show_commit, show_object, + &show_data, NULL); } return base; @@ -999,7 +1001,8 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs, if (haves) { revs->ignore_missing_links = 1; - haves_bitmap = find_objects(bitmap_git, revs, haves, NULL); + haves_bitmap = find_objects(bitmap_git, revs, haves, NULL, + filter); reset_revision_walk(); revs->ignore_missing_links = 0; @@ -1007,7 +1010,8 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs, BUG("failed to perform bitmap walk"); } - wants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap); + wants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap, + filter); if (!wants_bitmap) BUG("failed to perform bitmap walk"); diff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh index b629a211f9..95379b1d4e 100755 --- a/t/perf/p5310-pack-bitmaps.sh +++ b/t/perf/p5310-pack-bitmaps.sh @@ -95,4 +95,9 @@ test_perf 'pack to file (partial bitmap)' ' git pack-objects --use-bitmap-index --all pack2b /dev/null ' +test_perf 'rev-list with tree filter (partial bitmap)' ' + git rev-list --use-bitmap-index --count --objects --all \ + --filter=tree:0 >/dev/null +' + test_done