From patchwork Mon Aug 21 21:43:59 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13359843 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 3EFD4EE49A6 for ; Mon, 21 Aug 2023 21:44:03 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230421AbjHUVoD (ORCPT ); Mon, 21 Aug 2023 17:44:03 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:43316 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229638AbjHUVoC (ORCPT ); Mon, 21 Aug 2023 17:44:02 -0400 Received: from mail-yb1-xb33.google.com (mail-yb1-xb33.google.com [IPv6:2607:f8b0:4864:20::b33]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 57B15CE for ; Mon, 21 Aug 2023 14:44:01 -0700 (PDT) Received: by mail-yb1-xb33.google.com with SMTP id 3f1490d57ef6-c5ffb6cda23so3902782276.0 for ; Mon, 21 Aug 2023 14:44:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20221208.gappssmtp.com; s=20221208; t=1692654240; x=1693259040; 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=KRkNE1/nGOI82nK7u38WemxT+IQUINtiXVcM9B7Bgyg=; b=aovnDSdXvdc3NZWSRKupQjEsewG00GrRjYIYETUc75VZQpI+1B1L7VZwjUJ0h0m4XP xbFFi91atJlVkVyd19CD2cljUAORTeGdpq2hNcxFKsGCe/5sAafSh/Pabx/O7jjpHEhi 9LQjr4Jq5wUwHXBEWRnXaF1Njo5xoCk1G1jD8EMhYFTUMX+Y2SEFHBkY90jVw7diiPvv OBe5fXbtCnFSt7GC1E1ZrERfIoEgV4j7p/6+/XCXW3L47+CY67JTJUwLGZ/fmRxltcyl QeyWW3jksbpZ8xGMGaeM/XTY7g2+MI09XV0iKSgipOURNAyHDQvi0Ohjss8YvWyaOR3Q digg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692654240; x=1693259040; 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=KRkNE1/nGOI82nK7u38WemxT+IQUINtiXVcM9B7Bgyg=; b=YU+0tujaRtl4l3ntQ0yunaCkTL2gvgPYqL4cdmZSfjiWJymxCVLvlWIO+HUvmrB6L/ sBtAxzN0F/q9OEKYtC5U2AxmTPK2pDbMhESI3KgPujV2Mc919Cu0J8GPQ85RZEk383FU 4ep0c3kvyJ59hwkvJ2eWgfuBxjUn9QPYNXc0tH4QNZQ9D4gYgAldJ856Aey/8bgx4N3L e+kYe8ngfM5Lh+WdlSXZYVSIz1OXNl6iV+T53CDUjHacmCt6a/vBKRugABw9HzT7YcOn ZHFdGmG8Auc/H6JeDIJ3Y+q15Cb1Lurh2j+/7c7SB7f3z51Mm95AgmBL4qreHdsvyh2q DhQA== X-Gm-Message-State: AOJu0Ywc7NQTI4CvCF2onLAqISdxaCGiREnzDA3lpYswE+hJKfg96lxc aZqpAb6ILsjlesyxSLqaCTZt4s3lApd5xXgqcbAxKQ== X-Google-Smtp-Source: AGHT+IFUiOF8DR0XhNLDZAIArqP6glANhILpqq+GOFsLua552vnT3h/XBtZC1mVBq8kzhbs8nY3s0A== X-Received: by 2002:a25:e042:0:b0:d16:bdcf:943d with SMTP id x63-20020a25e042000000b00d16bdcf943dmr8420730ybg.6.1692654240412; Mon, 21 Aug 2023 14:44: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 l64-20020a252543000000b00d145ec9f495sm2055483ybl.46.2023.08.21.14.44.00 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 21 Aug 2023 14:44:00 -0700 (PDT) Date: Mon, 21 Aug 2023 17:43:59 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jonathan Tan , Junio C Hamano , Jeff King , Derrick Stolee Subject: [PATCH 01/15] gitformat-commit-graph: describe version 2 of BDAT Message-ID: <0241b6e18867dab34c8dd8b49a861884e9818d37.1692654233.git.me@ttaylorr.com> References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Jonathan Tan The code change to Git to support version 2 will be done in subsequent commits. Signed-off-by: Jonathan Tan Signed-off-by: Junio C Hamano Signed-off-by: Taylor Blau --- Documentation/gitformat-commit-graph.txt | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) diff --git a/Documentation/gitformat-commit-graph.txt b/Documentation/gitformat-commit-graph.txt index 31cad585e2..3e906e8030 100644 --- a/Documentation/gitformat-commit-graph.txt +++ b/Documentation/gitformat-commit-graph.txt @@ -142,13 +142,16 @@ All multi-byte numbers are in network byte order. ==== Bloom Filter Data (ID: {'B', 'D', 'A', 'T'}) [Optional] * It starts with header consisting of three unsigned 32-bit integers: - - Version of the hash algorithm being used. We currently only support - value 1 which corresponds to the 32-bit version of the murmur3 hash + - Version of the hash algorithm being used. We currently support + value 2 which corresponds to the 32-bit version of the murmur3 hash implemented exactly as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm and the double hashing technique using seed values 0x293ae76f and 0x7e646e2 as described in https://doi.org/10.1007/978-3-540-30494-4_26 "Bloom Filters - in Probabilistic Verification" + in Probabilistic Verification". Version 1 Bloom filters have a bug that appears + when char is signed and the repository has path names that have characters >= + 0x80; Git supports reading and writing them, but this ability will be removed + in a future version of Git. - The number of times a path is hashed and hence the number of bit positions that cumulatively determine whether a file is present in the commit. - The minimum number of bits 'b' per entry in the Bloom filter. If the filter From patchwork Mon Aug 21 21:44:02 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13359844 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id CAD3FEE49A5 for ; Mon, 21 Aug 2023 21:44:07 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230434AbjHUVoI (ORCPT ); Mon, 21 Aug 2023 17:44:08 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:43402 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230457AbjHUVoF (ORCPT ); Mon, 21 Aug 2023 17:44:05 -0400 Received: from mail-yb1-xb34.google.com (mail-yb1-xb34.google.com [IPv6:2607:f8b0:4864:20::b34]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 09F7E11D for ; Mon, 21 Aug 2023 14:44:04 -0700 (PDT) Received: by mail-yb1-xb34.google.com with SMTP id 3f1490d57ef6-d776e1f181bso715065276.3 for ; Mon, 21 Aug 2023 14:44:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20221208.gappssmtp.com; s=20221208; t=1692654243; x=1693259043; 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=w8vuNFBcFdWPskEdv+zdwigDuglzVVzyTUSDJAmUDl4=; b=zSU7cnfSydgMAqKsuVknE20//pAtdZELU6xuRbtsDnEkJB6FOF9JE+qkQBIf/wRULk ruZsUt5uUIM4NQMdngzWwCv7vdqX8/C0dWsuBL6cvCkDBVInkBSmRtGK//PZbnK4ARRD p8tSr9M9hCFzlMnYwiiPlNOVVh2cvWaZlz68DjzFAFzNS6jfpCZjQkXStrorXfxRQc00 JexpCkp6UApxXQwPCDJStxm2gHPDK462qAJTvoY78W4DKtVQEUqbBBUL/ErBkM50BEhk xohjEdbI5DVwe0F6R/Ca2ZUI/NMYsTXAGAfMB4sCcbSPx3HeH9QGVYvSs32YiuHyxPQD fZ/w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692654243; x=1693259043; 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=w8vuNFBcFdWPskEdv+zdwigDuglzVVzyTUSDJAmUDl4=; b=al98CK5e+uqpFEyrYQO2Tpedx2lifUOvgeGn+z3hAIwlnJS9HPKVyeYuWBIhWOtFoV HyXbnNlvY5NgynJeBDSHknM7DcAKQyzZ99XywsTP5CCe+v1uMWRwcRvkHktKAQadi5Jv 71vOhRZlkUFTd9b8ABecbZd9umBTOKVOkSokUuHJ+ppeITVxy0fOG14DJ1V2Drnw79Ae wD1+LyCz7GoNO1Wta56N4wjEHtvUpYjWgcTiBfYx/GTY9rAdIkcPeueGhKwWb0aH0/Fg CV4rfQ0+r4uk6Xf6fQJPpZNifPmhuYmZ6+0OSh4YQZn3NfPCBZiFj/gN0QbbNsNvCAT3 Zc7g== X-Gm-Message-State: AOJu0YzoAaNCsskE9VPWMjUjluMHFBX8+w9Y4iVUjENn7wU/2yxg05uy Nmhto8NHw4LmRG1zzjYyk7IBhcLkZViPNYW2n74+ag== X-Google-Smtp-Source: AGHT+IESIVd6HcUuiNqRn8u54nhxBoERDdzZnUViiLGbtWdYm3GCXeFJYoZlSFtX9Mg58DXsj+6ptQ== X-Received: by 2002:a25:9783:0:b0:d16:f35b:a35f with SMTP id i3-20020a259783000000b00d16f35ba35fmr7112905ybo.40.1692654243089; Mon, 21 Aug 2023 14:44: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 f7-20020a5b0d47000000b00d0bad22d652sm1967033ybr.36.2023.08.21.14.44.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 21 Aug 2023 14:44:02 -0700 (PDT) Date: Mon, 21 Aug 2023 17:44:02 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jonathan Tan , Junio C Hamano , Jeff King , Derrick Stolee Subject: [PATCH 02/15] t/helper/test-read-graph.c: extract `dump_graph_info()` Message-ID: <9c129c733e689f02abafdc97011395653c2708d4.1692654233.git.me@ttaylorr.com> References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Prepare for the 'read-graph' test helper to perform other tasks besides dumping high-level information about the commit-graph by extracting its main routine into a separate function. Signed-off-by: Taylor Blau Signed-off-by: Jonathan Tan Signed-off-by: Junio C Hamano Signed-off-by: Taylor Blau --- t/helper/test-read-graph.c | 31 ++++++++++++++++++------------- 1 file changed, 18 insertions(+), 13 deletions(-) diff --git a/t/helper/test-read-graph.c b/t/helper/test-read-graph.c index 8c7a83f578..3375392f6c 100644 --- a/t/helper/test-read-graph.c +++ b/t/helper/test-read-graph.c @@ -5,20 +5,8 @@ #include "bloom.h" #include "setup.h" -int cmd__read_graph(int argc UNUSED, const char **argv UNUSED) +static void dump_graph_info(struct commit_graph *graph) { - struct commit_graph *graph = NULL; - struct object_directory *odb; - - setup_git_directory(); - odb = the_repository->objects->odb; - - prepare_repo_settings(the_repository); - - graph = read_commit_graph_one(the_repository, odb); - if (!graph) - return 1; - printf("header: %08x %d %d %d %d\n", ntohl(*(uint32_t*)graph->data), *(unsigned char*)(graph->data + 4), @@ -57,6 +45,23 @@ int cmd__read_graph(int argc UNUSED, const char **argv UNUSED) if (graph->topo_levels) printf(" topo_levels"); printf("\n"); +} + +int cmd__read_graph(int argc UNUSED, const char **argv UNUSED) +{ + struct commit_graph *graph = NULL; + struct object_directory *odb; + + setup_git_directory(); + odb = the_repository->objects->odb; + + prepare_repo_settings(the_repository); + + graph = read_commit_graph_one(the_repository, odb); + if (!graph) + return 1; + + dump_graph_info(graph); UNLEAK(graph); From patchwork Mon Aug 21 21:44:04 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13359845 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id ED11DEE49A6 for ; Mon, 21 Aug 2023 21:44:08 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230489AbjHUVoJ (ORCPT ); Mon, 21 Aug 2023 17:44:09 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:43472 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230483AbjHUVoI (ORCPT ); Mon, 21 Aug 2023 17:44:08 -0400 Received: from mail-yw1-x112f.google.com (mail-yw1-x112f.google.com [IPv6:2607:f8b0:4864:20::112f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A202F183 for ; Mon, 21 Aug 2023 14:44:06 -0700 (PDT) Received: by mail-yw1-x112f.google.com with SMTP id 00721157ae682-58dfe2d5b9aso52409917b3.1 for ; Mon, 21 Aug 2023 14:44:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20221208.gappssmtp.com; s=20221208; t=1692654245; x=1693259045; 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=NpeNsy9E+Tz9gW/gHL8pRzM+YaqzHk/FuZOzIAvMvfM=; b=rAUiAd9NDsymd/ORnw5EC2CfGgDsTDFQYyVyYiz7dyrTY1p/Xp2dfv+Oh8X8VQoy5U r43ALvnYcNMQDJNrs5MRPGy4gJ3pipsKEatrovxejUIC/9FL8ENvVD5XTGomY7MpcS98 7vl5shAld13GsmM98mn/86HKiEbGuhv0APLr/DAohTGoPktrrr9Qv46vNpDKZiBT9483 Xw6Zk9Leyg+PF7bKi3oXFXHPsBmdjyBgSa3Khhqo1k9swCxsvJXqYb/Bh0Bc7/p+Q0p3 OmonjjOJbQbahOJzM4AN3IP8ogdyI3Atyb48RFlZw7ge642FH9v0AuZb1eLRgSJ+JTWG CpPQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692654245; x=1693259045; 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=NpeNsy9E+Tz9gW/gHL8pRzM+YaqzHk/FuZOzIAvMvfM=; b=UEk8L6/Br9vgchCelunYiE6Ia33Iwj3Oa/flBOp6UXxEIqtuJNNdW1BQHn8TDqT2VN e9bMK9b2itys4AfGHxT1r00Lil6fRikuQcoMOKKP4/ShmyFtCdMgl8szWV/YHvqBORba BdvXaTXQMcBwuHOWsQM3JAw37aw7fMjY12ZXE9ngMeHOteddx4Mn2QOS5RdfQfwsEBIC Gg5xCAOLWrlMNUPa70iKqwpt7ABtOuUbEeqRwGB96+zHy0AoGQJiPDxmOwnW12xypFIM tOzGvqhBRZfohmJBWnsNtJ8DOYEob00TviKUdbl89B0L2LBgFGiJhkZAVyM2JXcMbb+J JFIg== X-Gm-Message-State: AOJu0YxJeMP+yoMz68ueAeiD/N344JhInPF7ggXGxYw6vO2wfvUkjr5c GX42iFBu92kPqiNAmIZIx3caZ9ZueA2H/orhCnmCNw== X-Google-Smtp-Source: AGHT+IFWx+qtAViGB8/wfYGdrzB6Fhvbdr8UzQAYre2sJIqkRkhjSN9jh1h4j6bGwgJbZ3EXyoOFzA== X-Received: by 2002:a0d:ca0b:0:b0:57a:3942:bb74 with SMTP id m11-20020a0dca0b000000b0057a3942bb74mr5701110ywd.17.1692654245733; Mon, 21 Aug 2023 14:44: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 l4-20020a81d544000000b005839a780c29sm2405784ywj.102.2023.08.21.14.44.05 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 21 Aug 2023 14:44:05 -0700 (PDT) Date: Mon, 21 Aug 2023 17:44:04 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jonathan Tan , Junio C Hamano , Jeff King , Derrick Stolee Subject: [PATCH 03/15] bloom.h: make `load_bloom_filter_from_graph()` public Message-ID: <766feac8cb8e796eaf99ecd4b92ff66293356814.1692654233.git.me@ttaylorr.com> References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Prepare for a future commit to use the load_bloom_filter_from_graph() function directly to load specific Bloom filters out of the commit-graph for manual inspection (to be used during tests). Signed-off-by: Taylor Blau Signed-off-by: Jonathan Tan Signed-off-by: Junio C Hamano Signed-off-by: Taylor Blau --- bloom.c | 6 +++--- bloom.h | 5 +++++ 2 files changed, 8 insertions(+), 3 deletions(-) diff --git a/bloom.c b/bloom.c index aef6b5fea2..3e78cfe79d 100644 --- a/bloom.c +++ b/bloom.c @@ -29,9 +29,9 @@ static inline unsigned char get_bitmask(uint32_t pos) return ((unsigned char)1) << (pos & (BITS_PER_WORD - 1)); } -static int load_bloom_filter_from_graph(struct commit_graph *g, - struct bloom_filter *filter, - uint32_t graph_pos) +int load_bloom_filter_from_graph(struct commit_graph *g, + struct bloom_filter *filter, + uint32_t graph_pos) { uint32_t lex_pos, start_index, end_index; diff --git a/bloom.h b/bloom.h index adde6dfe21..1e4f612d2c 100644 --- a/bloom.h +++ b/bloom.h @@ -3,6 +3,7 @@ struct commit; struct repository; +struct commit_graph; struct bloom_filter_settings { /* @@ -68,6 +69,10 @@ struct bloom_key { uint32_t *hashes; }; +int load_bloom_filter_from_graph(struct commit_graph *g, + struct bloom_filter *filter, + uint32_t graph_pos); + /* * Calculate the murmur3 32-bit hash value for the given data * using the given seed. From patchwork Mon Aug 21 21:44:07 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13359846 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 513FFEE4996 for ; Mon, 21 Aug 2023 21:44:16 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231135AbjHUVoQ (ORCPT ); Mon, 21 Aug 2023 17:44:16 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34454 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230498AbjHUVoO (ORCPT ); Mon, 21 Aug 2023 17:44:14 -0400 Received: from mail-yw1-x112f.google.com (mail-yw1-x112f.google.com [IPv6:2607:f8b0:4864:20::112f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8D8F8184 for ; Mon, 21 Aug 2023 14:44:09 -0700 (PDT) Received: by mail-yw1-x112f.google.com with SMTP id 00721157ae682-58c92a2c52dso43639987b3.2 for ; Mon, 21 Aug 2023 14:44:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20221208.gappssmtp.com; s=20221208; t=1692654248; x=1693259048; 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=NxNwZkn3g2SSRrZUNiETz3zUJWWuDbypV2yIC9yy4zs=; b=YJikXEE8jx79WiAqNKMwTMvL69WT2F67z+/QueDss/FWR2W/pKfFLPGExAWZwTNad9 ++t72fifHTuU7f/UvyLTT2c0f8GVcKJmTGzf/aqWr3TlTzZxR9ybtIpzuF84f1g5HpsL Dj45WAvvdlQhTWIgdpUbgzsl5xu3vwuor22KEtfRMzQxlrK71MFlo9GMtdKbrjWaZUmr 9fjF20oJJHp19kvLWs9dOE1U/3vEiLwH1pXtb6hb/6/N1OL6KRQOlE1hWrly1xSaGsVU v/MGc1fZyKhfvIieEfYvq/sLLcN4NTfkpK1bF9mnjsB+dZsIv5eUNLuVFL+njZeoKaFS J58w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692654248; x=1693259048; 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=NxNwZkn3g2SSRrZUNiETz3zUJWWuDbypV2yIC9yy4zs=; b=joMa6jJ3h6tmyk1Le7zcHns83d0pjsOvLaS1JOjb8qwiVqNR9Ne1eTQTmvYiRd8i+b 4cOykUiCJY3dEfpJ8sWVNoiEMpZSvY66yVEBXN1iMVpXoNGd8Mxnk5CmKVh1KG1yaGq1 XNIFBcgbYeH/WXaLHohdABxxYd9ishcsNmERVoXjgzcEjh9Z6ItGB+kB7Yzexl5iU2zx 7FCgcSM+c2eE+dxLWDPRsrlWFtGw/Qo2T7etyDjt7wPxLF/JDDS3nsEeHJQ7jBrzYVWR UjnuqCt6IJrS8Ihu1lFO7EGV/4RSgsaoylOngB22yTjOtJXWf3fPymS5xNOAn7ZW8Bho U5zQ== X-Gm-Message-State: AOJu0Yybj7b2Y38NvSwvZBGFN1MScoTl97HztIJcGIAGyzqABViDUIwA bp+QWeBRxF1BJn/OwIz0gq7UVja/ZrCqibT+3ARsVQ== X-Google-Smtp-Source: AGHT+IGAxb0FU1M9YZtgpYb+QTZCEtwOz5FMP1HYSbUjlgw1utFhVT3WBWUuf9N8yERP0dd6lmnX+w== X-Received: by 2002:a81:5cd4:0:b0:586:a141:3b3e with SMTP id q203-20020a815cd4000000b00586a1413b3emr8726061ywb.13.1692654248414; Mon, 21 Aug 2023 14:44: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 n2-20020a0dfd02000000b005837633d9cbsm2423405ywf.64.2023.08.21.14.44.08 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 21 Aug 2023 14:44:08 -0700 (PDT) Date: Mon, 21 Aug 2023 17:44:07 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jonathan Tan , Junio C Hamano , Jeff King , Derrick Stolee Subject: [PATCH 04/15] t/helper/test-read-graph: implement `bloom-filters` mode Message-ID: <9a98ca09dc85d1bad79a79425fe88c83f5756c14.1692654233.git.me@ttaylorr.com> References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Implement a mode of the "read-graph" test helper to dump out the hexadecimal contents of the Bloom filter(s) contained in a commit-graph. Signed-off-by: Taylor Blau Signed-off-by: Jonathan Tan Signed-off-by: Junio C Hamano Signed-off-by: Taylor Blau --- t/helper/test-read-graph.c | 44 +++++++++++++++++++++++++++++++++----- 1 file changed, 39 insertions(+), 5 deletions(-) diff --git a/t/helper/test-read-graph.c b/t/helper/test-read-graph.c index 3375392f6c..da9ac8584d 100644 --- a/t/helper/test-read-graph.c +++ b/t/helper/test-read-graph.c @@ -47,10 +47,32 @@ static void dump_graph_info(struct commit_graph *graph) printf("\n"); } -int cmd__read_graph(int argc UNUSED, const char **argv UNUSED) +static void dump_graph_bloom_filters(struct commit_graph *graph) +{ + uint32_t i; + + for (i = 0; i < graph->num_commits + graph->num_commits_in_base; i++) { + struct bloom_filter filter = { 0 }; + size_t j; + + if (load_bloom_filter_from_graph(graph, &filter, i) < 0) { + fprintf(stderr, "missing Bloom filter for graph " + "position %"PRIu32"\n", i); + continue; + } + + for (j = 0; j < filter.len; j++) + printf("%02x", filter.data[j]); + if (filter.len) + printf("\n"); + } +} + +int cmd__read_graph(int argc, const char **argv) { struct commit_graph *graph = NULL; struct object_directory *odb; + int ret = 0; setup_git_directory(); odb = the_repository->objects->odb; @@ -58,12 +80,24 @@ int cmd__read_graph(int argc UNUSED, const char **argv UNUSED) prepare_repo_settings(the_repository); graph = read_commit_graph_one(the_repository, odb); - if (!graph) - return 1; + if (!graph) { + ret = 1; + goto done; + } - dump_graph_info(graph); + if (argc <= 1) + dump_graph_info(graph); + else if (!strcmp(argv[1], "bloom-filters")) + dump_graph_bloom_filters(graph); + else { + fprintf(stderr, "unknown sub-command: '%s'\n", argv[1]); + ret = 1; + } +done: UNLEAK(graph); - return 0; + return ret; } + + From patchwork Mon Aug 21 21:44:10 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13359847 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id B0E81EE49A6 for ; Mon, 21 Aug 2023 21:44:17 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229638AbjHUVoR (ORCPT ); Mon, 21 Aug 2023 17:44:17 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34442 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230490AbjHUVoP (ORCPT ); Mon, 21 Aug 2023 17:44:15 -0400 Received: from mail-yw1-x112d.google.com (mail-yw1-x112d.google.com [IPv6:2607:f8b0:4864:20::112d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 0D957194 for ; Mon, 21 Aug 2023 14:44:12 -0700 (PDT) Received: by mail-yw1-x112d.google.com with SMTP id 00721157ae682-5920efd91c7so18981317b3.2 for ; Mon, 21 Aug 2023 14:44:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20221208.gappssmtp.com; s=20221208; t=1692654251; x=1693259051; 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=1nEgjLbW1muImALuZZyXVL7jJVqMiM2vmZmrliyQ7cU=; b=jGghZr6HmSlWf7af34F3Sa2yPXEvmZns55pWZXCAGOh8jfUcEeCCCAB8eU5YS+nDAO uX3tuw3rasCKle38dJqw6gHKwYrBI+5KlTPL+8R/eUuTlIlh4bf/+zTOWLzERV2dS6Ns S1DHcH9sNMqf+Ehyx8dOCI4vgUiofPXGSyrV8BbIcaOvLslh9o/doBiK5N/j1cO8m0DQ KQITiEOXG8TVNoBGvex+JvMp1IbdYAOW7vgKLYKXx3Gb6koVHAZMpVhVMtz1Zu6cKRY/ IQxJ9O+szoeCzNoXIfkh6ZKmkMt7dnpXSCx55xjosoC0XQXD7sG5EauY9HamS5oEO676 tKtQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692654251; x=1693259051; 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=1nEgjLbW1muImALuZZyXVL7jJVqMiM2vmZmrliyQ7cU=; b=a7ddBBDcIv5YOvVFME+UGcDJu1vhnWCIwdYvHNqLcGRAolJRyMzuPLLr+7xobbbUYZ fXFC9ePOE8GqOZ9xvPb5pHr5NklKm13L5CQQsFsVUtfqIxx3o8xXfbS2B+tuvlBjJkqw jOaza0AkNCzEshiSKVdze8EvNIzHQD+CMyrX2IJtHY3qr3T6pURQF1jNlSWU9kfXs8RQ cWhymioqF1C2Hq66m49Zhn0C6krPz46+l+wisEEpG0lUyB6LNpD3T15EhkvWpEfPxOkV igFt0LYplqpR7Cq2S8vDAF9FQsFRvFgnlYGSqOsfsYwoxsbUmfeQfDz5bvUGOk7uN32t egIA== X-Gm-Message-State: AOJu0YzwGsW4VsL++TX+1aL/mR/lpcHmmdH6RG9EMTrqGyUEJfPgEIOQ mX7YzSxze/kQC0nmqsseAnlTHvQbHh4Vp5MX7PukTQ== X-Google-Smtp-Source: AGHT+IGSm4x4WOvpZsjn3HctXd+c5iwWmMP5BqaoT9vyoJBjjV0R1Uag65mv+/Avf24JYRL6lg+AJA== X-Received: by 2002:a81:9208:0:b0:58c:4e63:109 with SMTP id j8-20020a819208000000b0058c4e630109mr8892293ywg.0.1692654251152; Mon, 21 Aug 2023 14:44: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 a124-20020a818a82000000b005869ca8da8esm2416848ywg.146.2023.08.21.14.44.10 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 21 Aug 2023 14:44:10 -0700 (PDT) Date: Mon, 21 Aug 2023 17:44:10 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jonathan Tan , Junio C Hamano , Jeff King , Derrick Stolee Subject: [PATCH 05/15] t4216: test changed path filters with high bit paths Message-ID: References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Jonathan Tan Subsequent commits will teach Git another version of changed path filter that has different behavior with paths that contain at least one character with its high bit set, so test the existing behavior as a baseline. Signed-off-by: Jonathan Tan Signed-off-by: Junio C Hamano Signed-off-by: Taylor Blau --- t/t4216-log-bloom.sh | 43 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 43 insertions(+) diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh index fa9d32facf..2d4a3fefee 100755 --- a/t/t4216-log-bloom.sh +++ b/t/t4216-log-bloom.sh @@ -404,4 +404,47 @@ test_expect_success 'Bloom generation backfills empty commits' ' ) ' +get_first_changed_path_filter () { + test-tool read-graph bloom-filters >filters.dat && + head -n 1 filters.dat +} + +# chosen to be the same under all Unicode normalization forms +CENT=$(printf "\302\242") + +test_expect_success 'set up repo with high bit path, version 1 changed-path' ' + git init highbit1 && + test_commit -C highbit1 c1 "$CENT" && + git -C highbit1 commit-graph write --reachable --changed-paths +' + +test_expect_success 'setup check value of version 1 changed-path' ' + ( + cd highbit1 && + echo "52a9" >expect && + get_first_changed_path_filter >actual && + test_cmp expect actual + ) +' + +# expect will not match actual if char is unsigned by default. Write the test +# in this way, so that a user running this test script can still see if the two +# files match. (It will appear as an ordinary success if they match, and a skip +# if not.) +if test_cmp highbit1/expect highbit1/actual +then + test_set_prereq SIGNED_CHAR_BY_DEFAULT +fi +test_expect_success SIGNED_CHAR_BY_DEFAULT 'check value of version 1 changed-path' ' + # Only the prereq matters for this test. + true +' + +test_expect_success 'version 1 changed-path used when version 1 requested' ' + ( + cd highbit1 && + test_bloom_filters_used "-- $CENT" + ) +' + test_done From patchwork Mon Aug 21 21:44:12 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13359848 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 76447EE4996 for ; Mon, 21 Aug 2023 21:44:20 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230490AbjHUVoU (ORCPT ); Mon, 21 Aug 2023 17:44:20 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34486 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230512AbjHUVoS (ORCPT ); Mon, 21 Aug 2023 17:44:18 -0400 Received: from mail-yw1-x1134.google.com (mail-yw1-x1134.google.com [IPv6:2607:f8b0:4864:20::1134]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E96E1132 for ; Mon, 21 Aug 2023 14:44:14 -0700 (PDT) Received: by mail-yw1-x1134.google.com with SMTP id 00721157ae682-58df8cab1f2so42574977b3.3 for ; Mon, 21 Aug 2023 14:44:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20221208.gappssmtp.com; s=20221208; t=1692654254; x=1693259054; 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=9coSinmdfSKWrEGXwxhlRm8qq0mw3reh9gVyDvDbsd0=; b=X89HXgslLx1oetRwF3X8n485dveMwVGxvVibE5b+4zPujMGWO9Omf7OUF7yWv1W9hp MxI5dJeIEM9/ePKisfXPhDg+cJeL6AHxhX4dO+AnI/2GZiF0ZH1rcwLgvABVWH9eemkB yqtVRxtE56uWsLe0PkqOW9fPYqOpspUEnHtJfDF5MniVpcHQhmb39UfbR9wcvlnfrgRf 9r8DK8XiSLlQTzOONq8IYULrSn4O2hg9r7d7wDPWvXn1CKZjn9cohCC8EQjycdV+1eA0 eqUIBEZcsTdeCG13Zd1SG5PR50Uk/ulFIFDxdXeB4G6KlX5WWf+sFvmY9ssdAjxtkPZ5 mqjg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692654254; x=1693259054; 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=9coSinmdfSKWrEGXwxhlRm8qq0mw3reh9gVyDvDbsd0=; b=I7b/Q7AHn4JihEwfVRq4ZfKycVHl3BDv4U2kn7ldd+DeTSjrMTuhcJRBNFladPwwiW zkHUnEVWIctPVqC5Z2j54cxAvvAyJlhit8yb/OG/XVBWV5B+PVA8MxQK+YiKay1cLZL5 66Bw8uQctlsif8R8tvYxWlU09kbi/J8n+KxKRQFMMRW3LrSN3K0kWitAfY3ctLGtTV7E m9m8lnAILnvE2kPAcPy6CB2+eB4vOs3mTez0L4VpNEkZDFfkyqvWHrokBXMvqlQDRNzj XViuZZSDG7xKekpbGrKRR2/O4xUfsvoMLV5bUpp5/IYL4hLLRLUPBg0thtV5CF0pxtdQ znEQ== X-Gm-Message-State: AOJu0YzDH5LQETsYcFLzMD9PgI4tP0sbaqF/+kccJFDKBWrvrIb41r5X gRc6usUAREalDJOn8YVSpITomQdbl4KkbBvhtGRDGg== X-Google-Smtp-Source: AGHT+IEc++oaGr7PkutGADdzPpvnmyIVIgY8toK5P59ZGbUO0DO6M0FmR+pMN0bn4QvLMJgBo+CajA== X-Received: by 2002:a0d:ccc9:0:b0:576:7dfc:e73e with SMTP id o192-20020a0dccc9000000b005767dfce73emr8643333ywd.32.1692654253956; Mon, 21 Aug 2023 14:44:13 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id u193-20020a8184ca000000b0058419c57c66sm2429057ywf.4.2023.08.21.14.44.13 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 21 Aug 2023 14:44:13 -0700 (PDT) Date: Mon, 21 Aug 2023 17:44:12 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jonathan Tan , Junio C Hamano , Jeff King , Derrick Stolee Subject: [PATCH 06/15] repo-settings: introduce commitgraph.changedPathsVersion Message-ID: References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Jonathan Tan A subsequent commit will introduce another version of the changed-path filter in the commit graph file. In order to control which version to write (and read), a config variable is needed. Therefore, introduce this config variable. For forwards compatibility, teach Git to not read commit graphs when the config variable is set to an unsupported version. Because we teach Git this, commitgraph.readChangedPaths is now redundant, so deprecate it and define its behavior in terms of the config variable we introduce. This commit does not change the behavior of writing (Git writes changed path filters when explicitly instructed regardless of any config variable), but a subsequent commit will restrict Git such that it will only write when commitgraph.changedPathsVersion is a recognized value. Signed-off-by: Jonathan Tan Signed-off-by: Junio C Hamano Signed-off-by: Taylor Blau --- Documentation/config/commitgraph.txt | 23 ++++++++++++++++++++--- commit-graph.c | 2 +- oss-fuzz/fuzz-commit-graph.c | 2 +- repo-settings.c | 6 +++++- repository.h | 2 +- 5 files changed, 28 insertions(+), 7 deletions(-) diff --git a/Documentation/config/commitgraph.txt b/Documentation/config/commitgraph.txt index 30604e4a4c..2dc9170622 100644 --- a/Documentation/config/commitgraph.txt +++ b/Documentation/config/commitgraph.txt @@ -9,6 +9,23 @@ commitGraph.maxNewFilters:: commit-graph write` (c.f., linkgit:git-commit-graph[1]). commitGraph.readChangedPaths:: - If true, then git will use the changed-path Bloom filters in the - commit-graph file (if it exists, and they are present). Defaults to - true. See linkgit:git-commit-graph[1] for more information. + Deprecated. Equivalent to commitGraph.changedPathsVersion=-1 if true, and + commitGraph.changedPathsVersion=0 if false. (If commitGraph.changedPathVersion + is also set, commitGraph.changedPathsVersion takes precedence.) + +commitGraph.changedPathsVersion:: + Specifies the version of the changed-path Bloom filters that Git will read and + write. May be -1, 0 or 1. ++ +Defaults to -1. ++ +If -1, Git will use the version of the changed-path Bloom filters in the +repository, defaulting to 1 if there are none. ++ +If 0, Git will not read any Bloom filters, and will write version 1 Bloom +filters when instructed to write. ++ +If 1, Git will only read version 1 Bloom filters, and will write version 1 +Bloom filters. ++ +See linkgit:git-commit-graph[1] for more information. diff --git a/commit-graph.c b/commit-graph.c index 0aa1640d15..da99f15fdf 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -401,7 +401,7 @@ struct commit_graph *parse_commit_graph(struct repo_settings *s, graph->read_generation_data = 1; } - if (s->commit_graph_read_changed_paths) { + if (s->commit_graph_changed_paths_version) { pair_chunk(cf, GRAPH_CHUNKID_BLOOMINDEXES, &graph->chunk_bloom_indexes); read_chunk(cf, GRAPH_CHUNKID_BLOOMDATA, diff --git a/oss-fuzz/fuzz-commit-graph.c b/oss-fuzz/fuzz-commit-graph.c index 2992079dd9..325c0b991a 100644 --- a/oss-fuzz/fuzz-commit-graph.c +++ b/oss-fuzz/fuzz-commit-graph.c @@ -19,7 +19,7 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) * possible. */ the_repository->settings.commit_graph_generation_version = 2; - the_repository->settings.commit_graph_read_changed_paths = 1; + the_repository->settings.commit_graph_changed_paths_version = 1; g = parse_commit_graph(&the_repository->settings, (void *)data, size); repo_clear(the_repository); free_commit_graph(g); diff --git a/repo-settings.c b/repo-settings.c index 525f69c0c7..db8fe817f3 100644 --- a/repo-settings.c +++ b/repo-settings.c @@ -24,6 +24,7 @@ void prepare_repo_settings(struct repository *r) int value; const char *strval; int manyfiles; + int read_changed_paths; if (!r->gitdir) BUG("Cannot add settings for uninitialized repository"); @@ -54,7 +55,10 @@ void prepare_repo_settings(struct repository *r) /* Commit graph config or default, does not cascade (simple) */ repo_cfg_bool(r, "core.commitgraph", &r->settings.core_commit_graph, 1); repo_cfg_int(r, "commitgraph.generationversion", &r->settings.commit_graph_generation_version, 2); - repo_cfg_bool(r, "commitgraph.readchangedpaths", &r->settings.commit_graph_read_changed_paths, 1); + repo_cfg_bool(r, "commitgraph.readchangedpaths", &read_changed_paths, 1); + repo_cfg_int(r, "commitgraph.changedpathsversion", + &r->settings.commit_graph_changed_paths_version, + read_changed_paths ? -1 : 0); repo_cfg_bool(r, "gc.writecommitgraph", &r->settings.gc_write_commit_graph, 1); repo_cfg_bool(r, "fetch.writecommitgraph", &r->settings.fetch_write_commit_graph, 0); diff --git a/repository.h b/repository.h index 5f18486f64..f71154e12c 100644 --- a/repository.h +++ b/repository.h @@ -29,7 +29,7 @@ struct repo_settings { int core_commit_graph; int commit_graph_generation_version; - int commit_graph_read_changed_paths; + int commit_graph_changed_paths_version; int gc_write_commit_graph; int fetch_write_commit_graph; int command_requires_full_index; From patchwork Mon Aug 21 21:44:15 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13359849 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 71371EE4996 for ; Mon, 21 Aug 2023 21:44:24 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231140AbjHUVoY (ORCPT ); Mon, 21 Aug 2023 17:44:24 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34498 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230484AbjHUVoU (ORCPT ); Mon, 21 Aug 2023 17:44:20 -0400 Received: from mail-yw1-x1131.google.com (mail-yw1-x1131.google.com [IPv6:2607:f8b0:4864:20::1131]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C53B5184 for ; Mon, 21 Aug 2023 14:44:17 -0700 (PDT) Received: by mail-yw1-x1131.google.com with SMTP id 00721157ae682-58c5642701fso43850907b3.0 for ; Mon, 21 Aug 2023 14:44:17 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20221208.gappssmtp.com; s=20221208; t=1692654257; x=1693259057; 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=BfL8ogu3VT6TwMJw6xqSfGl5xvrkuduEjY85wMbvyE0=; b=hpL6qFGBpVeOpReZ2Erhl759OMZxDZ7EAVGgqLiLj4uirLvOrX+1H7Y/p+TEfxGTCe /cxiVxqhmq/In0VRMfv3ryP3QqvHkoX9TYudGSMnCjpUtqhONMxD05IeszOooh5+ENAT 1KvNG2Q3pzedRBwfA7K1NBc8L3UrDTdKSMUt7ZX4OsgpVZxBTRM+zshf4HK4GkGhbH2f b9jlRZpAGNEASrtnMa0nKneDBZbZCxVN4htJy29ekQuxfK7Nk8rHnjKLL1LWoOrBOCSx cZwguTp7Oi0YgfBzpRuFr0tf42JhJP9o6rzW6V+5HG30GsrikpWzBV5VqxpXyDOYIHdC /vKA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692654257; x=1693259057; 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=BfL8ogu3VT6TwMJw6xqSfGl5xvrkuduEjY85wMbvyE0=; b=fqYtsgc+Oec1H6uqByvWBq6xhzEOlzXlXju1OVIpS7zefTop2Fb6doVMU54sHnEmTk 43TwisVUZJV3j7S9Ti8+KEQp52w0jBsZjRkvTc+04Dv5St/d49nm5XrdBisejuiOwA+d Pnju7J0coWmCWpccxZgDJE4Pe6caKStKGBI+hpNJtX6zqAdy7im89ZxQLPT2cPF2PiO9 H/IoBZN/jod39JiZoGplgQ+reNEcDpdfJyT0yMbW2RDWuKBOX/FSf8+DKemrKlpVAipn 6Adl5iR66tX1mMN6SffsmmQ4Uqc6G6Z0UeZUs8uA1I05p1ARlS9MrP96ysTbyIabOx9Y fAvw== X-Gm-Message-State: AOJu0YxdHGoxMKVfBUKc7gfZTAvhzjvK03LeOfhSkKyuJFkI6zgdyaIE RUwEN1Eqn4CrW6wIeKaRU5KyihOnp09gcRwqmXBYgA== X-Google-Smtp-Source: AGHT+IGiQUTcZXwgJJQQQY65MzV+rQQnisBwhHaoeO3iXkvGcC2u7FMLIHyhlSXmUO+5Hzp+tMV8NQ== X-Received: by 2002:a81:9141:0:b0:57a:8ecb:11ad with SMTP id i62-20020a819141000000b0057a8ecb11admr8861897ywg.43.1692654256676; Mon, 21 Aug 2023 14:44:16 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id l201-20020a0de2d2000000b0057a5302e2fesm2446358ywe.5.2023.08.21.14.44.16 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 21 Aug 2023 14:44:16 -0700 (PDT) Date: Mon, 21 Aug 2023 17:44:15 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jonathan Tan , Junio C Hamano , Jeff King , Derrick Stolee Subject: [PATCH 07/15] commit-graph: new filter ver. that fixes murmur3 Message-ID: <72150bd026befc758b41386cf571c6a33a754d4e.1692654233.git.me@ttaylorr.com> References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Jonathan Tan The murmur3 implementation in bloom.c has a bug when converting series of 4 bytes into network-order integers when char is signed (which is controllable by a compiler option, and the default signedness of char is platform-specific). When a string contains characters with the high bit set, this bug causes results that, although internally consistent within Git, does not accord with other implementations of murmur3 (thus, the changed path filters wouldn't be readable by other off-the-shelf implementatios of murmur3) and even with Git binaries that were compiled with different signedness of char. This bug affects both how Git writes changed path filters to disk and how Git interprets changed path filters on disk. Therefore, introduce a new version (2) of changed path filters that corrects this problem. The existing version (1) is still supported and is still the default, but users should migrate away from it as soon as possible. Because this bug only manifests with characters that have the high bit set, it may be possible that some (or all) commits in a given repo would have the same changed path filter both before and after this fix is applied. However, in order to determine whether this is the case, the changed paths would first have to be computed, at which point it is not much more expensive to just compute a new changed path filter. So this patch does not include any mechanism to "salvage" changed path filters from repositories. There is also no "mixed" mode - for each invocation of Git, reading and writing changed path filters are done with the same version number; this version number may be explicitly stated (typically if the user knows which version they need) or automatically determined from the version of the existing changed path filters in the repository. There is a change in write_commit_graph(). graph_read_bloom_data() makes it possible for chunk_bloom_data to be non-NULL but bloom_filter_settings to be NULL, which causes a segfault later on. I produced such a segfault while developing this patch, but couldn't find a way to reproduce it neither after this complete patch (or before), but in any case it seemed like a good thing to include that might help future patch authors. The value in t0095 was obtained from another murmur3 implementation using the following Go source code: package main import "fmt" import "github.com/spaolacci/murmur3" func main() { fmt.Printf("%x\n", murmur3.Sum32([]byte("Hello world!"))) fmt.Printf("%x\n", murmur3.Sum32([]byte{0x99, 0xaa, 0xbb, 0xcc, 0xdd, 0xee, 0xff})) } Signed-off-by: Jonathan Tan Signed-off-by: Junio C Hamano Signed-off-by: Taylor Blau --- Documentation/config/commitgraph.txt | 5 +- bloom.c | 69 +++++++++++++++++++- bloom.h | 8 ++- commit-graph.c | 32 ++++++++-- t/helper/test-bloom.c | 9 ++- t/t0095-bloom.sh | 8 +++ t/t4216-log-bloom.sh | 96 ++++++++++++++++++++++++++++ 7 files changed, 214 insertions(+), 13 deletions(-) diff --git a/Documentation/config/commitgraph.txt b/Documentation/config/commitgraph.txt index 2dc9170622..acc74a2f27 100644 --- a/Documentation/config/commitgraph.txt +++ b/Documentation/config/commitgraph.txt @@ -15,7 +15,7 @@ commitGraph.readChangedPaths:: commitGraph.changedPathsVersion:: Specifies the version of the changed-path Bloom filters that Git will read and - write. May be -1, 0 or 1. + write. May be -1, 0, 1, or 2. + Defaults to -1. + @@ -28,4 +28,7 @@ filters when instructed to write. If 1, Git will only read version 1 Bloom filters, and will write version 1 Bloom filters. + +If 2, Git will only read version 2 Bloom filters, and will write version 2 +Bloom filters. ++ See linkgit:git-commit-graph[1] for more information. diff --git a/bloom.c b/bloom.c index 3e78cfe79d..ebef5cfd2f 100644 --- a/bloom.c +++ b/bloom.c @@ -66,7 +66,64 @@ int load_bloom_filter_from_graph(struct commit_graph *g, * Not considered to be cryptographically secure. * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm */ -uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len) +uint32_t murmur3_seeded_v2(uint32_t seed, const char *data, size_t len) +{ + const uint32_t c1 = 0xcc9e2d51; + const uint32_t c2 = 0x1b873593; + const uint32_t r1 = 15; + const uint32_t r2 = 13; + const uint32_t m = 5; + const uint32_t n = 0xe6546b64; + int i; + uint32_t k1 = 0; + const char *tail; + + int len4 = len / sizeof(uint32_t); + + uint32_t k; + for (i = 0; i < len4; i++) { + uint32_t byte1 = (uint32_t)(unsigned char)data[4*i]; + uint32_t byte2 = ((uint32_t)(unsigned char)data[4*i + 1]) << 8; + uint32_t byte3 = ((uint32_t)(unsigned char)data[4*i + 2]) << 16; + uint32_t byte4 = ((uint32_t)(unsigned char)data[4*i + 3]) << 24; + k = byte1 | byte2 | byte3 | byte4; + k *= c1; + k = rotate_left(k, r1); + k *= c2; + + seed ^= k; + seed = rotate_left(seed, r2) * m + n; + } + + tail = (data + len4 * sizeof(uint32_t)); + + switch (len & (sizeof(uint32_t) - 1)) { + case 3: + k1 ^= ((uint32_t)(unsigned char)tail[2]) << 16; + /*-fallthrough*/ + case 2: + k1 ^= ((uint32_t)(unsigned char)tail[1]) << 8; + /*-fallthrough*/ + case 1: + k1 ^= ((uint32_t)(unsigned char)tail[0]) << 0; + k1 *= c1; + k1 = rotate_left(k1, r1); + k1 *= c2; + seed ^= k1; + break; + } + + seed ^= (uint32_t)len; + seed ^= (seed >> 16); + seed *= 0x85ebca6b; + seed ^= (seed >> 13); + seed *= 0xc2b2ae35; + seed ^= (seed >> 16); + + return seed; +} + +static uint32_t murmur3_seeded_v1(uint32_t seed, const char *data, size_t len) { const uint32_t c1 = 0xcc9e2d51; const uint32_t c2 = 0x1b873593; @@ -131,8 +188,14 @@ void fill_bloom_key(const char *data, int i; const uint32_t seed0 = 0x293ae76f; const uint32_t seed1 = 0x7e646e2c; - const uint32_t hash0 = murmur3_seeded(seed0, data, len); - const uint32_t hash1 = murmur3_seeded(seed1, data, len); + uint32_t hash0, hash1; + if (settings->hash_version == 2) { + hash0 = murmur3_seeded_v2(seed0, data, len); + hash1 = murmur3_seeded_v2(seed1, data, len); + } else { + hash0 = murmur3_seeded_v1(seed0, data, len); + hash1 = murmur3_seeded_v1(seed1, data, len); + } key->hashes = (uint32_t *)xcalloc(settings->num_hashes, sizeof(uint32_t)); for (i = 0; i < settings->num_hashes; i++) diff --git a/bloom.h b/bloom.h index 1e4f612d2c..138d57a86b 100644 --- a/bloom.h +++ b/bloom.h @@ -8,9 +8,11 @@ struct commit_graph; struct bloom_filter_settings { /* * The version of the hashing technique being used. - * We currently only support version = 1 which is + * The newest version is 2, which is * the seeded murmur3 hashing technique implemented - * in bloom.c. + * in bloom.c. Bloom filters of version 1 were created + * with prior versions of Git, which had a bug in the + * implementation of the hash function. */ uint32_t hash_version; @@ -80,7 +82,7 @@ int load_bloom_filter_from_graph(struct commit_graph *g, * Not considered to be cryptographically secure. * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm */ -uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len); +uint32_t murmur3_seeded_v2(uint32_t seed, const char *data, size_t len); void fill_bloom_key(const char *data, size_t len, diff --git a/commit-graph.c b/commit-graph.c index da99f15fdf..f7322c4fff 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -304,17 +304,26 @@ static int graph_read_oid_lookup(const unsigned char *chunk_start, return 0; } +struct graph_read_bloom_data_context { + struct commit_graph *g; + int *commit_graph_changed_paths_version; +}; + static int graph_read_bloom_data(const unsigned char *chunk_start, size_t chunk_size, void *data) { - struct commit_graph *g = data; + struct graph_read_bloom_data_context *c = data; + struct commit_graph *g = c->g; uint32_t hash_version; - g->chunk_bloom_data = chunk_start; hash_version = get_be32(chunk_start); - if (hash_version != 1) + if (*c->commit_graph_changed_paths_version == -1) { + *c->commit_graph_changed_paths_version = hash_version; + } else if (hash_version != *c->commit_graph_changed_paths_version) { return 0; + } + g->chunk_bloom_data = chunk_start; g->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings)); g->bloom_filter_settings->hash_version = hash_version; g->bloom_filter_settings->num_hashes = get_be32(chunk_start + 4); @@ -402,10 +411,14 @@ struct commit_graph *parse_commit_graph(struct repo_settings *s, } if (s->commit_graph_changed_paths_version) { + struct graph_read_bloom_data_context context = { + .g = graph, + .commit_graph_changed_paths_version = &s->commit_graph_changed_paths_version + }; pair_chunk(cf, GRAPH_CHUNKID_BLOOMINDEXES, &graph->chunk_bloom_indexes); read_chunk(cf, GRAPH_CHUNKID_BLOOMDATA, - graph_read_bloom_data, graph); + graph_read_bloom_data, &context); } if (graph->chunk_bloom_indexes && graph->chunk_bloom_data) { @@ -2376,6 +2389,13 @@ int write_commit_graph(struct object_directory *odb, } if (!commit_graph_compatible(r)) return 0; + if (r->settings.commit_graph_changed_paths_version < -1 + || r->settings.commit_graph_changed_paths_version > 2) { + warning(_("attempting to write a commit-graph, but " + "'commitgraph.changedPathsVersion' (%d) is not supported"), + r->settings.commit_graph_changed_paths_version); + return 0; + } CALLOC_ARRAY(ctx, 1); ctx->r = r; @@ -2388,6 +2408,8 @@ int write_commit_graph(struct object_directory *odb, ctx->write_generation_data = (get_configured_generation_version(r) == 2); ctx->num_generation_data_overflows = 0; + bloom_settings.hash_version = r->settings.commit_graph_changed_paths_version == 2 + ? 2 : 1; bloom_settings.bits_per_entry = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY", bloom_settings.bits_per_entry); bloom_settings.num_hashes = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_NUM_HASHES", @@ -2417,7 +2439,7 @@ int write_commit_graph(struct object_directory *odb, g = ctx->r->objects->commit_graph; /* We have changed-paths already. Keep them in the next graph */ - if (g && g->chunk_bloom_data) { + if (g && g->bloom_filter_settings) { ctx->changed_paths = 1; ctx->bloom_settings = g->bloom_filter_settings; } diff --git a/t/helper/test-bloom.c b/t/helper/test-bloom.c index aabe31d724..3cbc0a5b50 100644 --- a/t/helper/test-bloom.c +++ b/t/helper/test-bloom.c @@ -50,6 +50,7 @@ static void get_bloom_filter_for_commit(const struct object_id *commit_oid) static const char *bloom_usage = "\n" " test-tool bloom get_murmur3 \n" +" test-tool bloom get_murmur3_seven_highbit\n" " test-tool bloom generate_filter [...]\n" " test-tool bloom get_filter_for_commit \n"; @@ -64,7 +65,13 @@ int cmd__bloom(int argc, const char **argv) uint32_t hashed; if (argc < 3) usage(bloom_usage); - hashed = murmur3_seeded(0, argv[2], strlen(argv[2])); + hashed = murmur3_seeded_v2(0, argv[2], strlen(argv[2])); + printf("Murmur3 Hash with seed=0:0x%08x\n", hashed); + } + + if (!strcmp(argv[1], "get_murmur3_seven_highbit")) { + uint32_t hashed; + hashed = murmur3_seeded_v2(0, "\x99\xaa\xbb\xcc\xdd\xee\xff", 7); printf("Murmur3 Hash with seed=0:0x%08x\n", hashed); } diff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh index b567383eb8..c8d84ab606 100755 --- a/t/t0095-bloom.sh +++ b/t/t0095-bloom.sh @@ -29,6 +29,14 @@ test_expect_success 'compute unseeded murmur3 hash for test string 2' ' test_cmp expect actual ' +test_expect_success 'compute unseeded murmur3 hash for test string 3' ' + cat >expect <<-\EOF && + Murmur3 Hash with seed=0:0xa183ccfd + EOF + test-tool bloom get_murmur3_seven_highbit >actual && + test_cmp expect actual +' + test_expect_success 'compute bloom key for empty string' ' cat >expect <<-\EOF && Hashes:0x5615800c|0x5b966560|0x61174ab4|0x66983008|0x6c19155c|0x7199fab0|0x771ae004| diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh index 2d4a3fefee..775e59d864 100755 --- a/t/t4216-log-bloom.sh +++ b/t/t4216-log-bloom.sh @@ -447,4 +447,100 @@ test_expect_success 'version 1 changed-path used when version 1 requested' ' ) ' +test_expect_success 'version 1 changed-path not used when version 2 requested' ' + ( + cd highbit1 && + git config --add commitgraph.changedPathsVersion 2 && + test_bloom_filters_not_used "-- $CENT" + ) +' + +test_expect_success 'version 1 changed-path used when autodetect requested' ' + ( + cd highbit1 && + git config --add commitgraph.changedPathsVersion -1 && + test_bloom_filters_used "-- $CENT" + ) +' + +test_expect_success 'when writing another commit graph, preserve existing version 1 of changed-path' ' + test_commit -C highbit1 c1double "$CENT$CENT" && + git -C highbit1 commit-graph write --reachable --changed-paths && + ( + cd highbit1 && + git config --add commitgraph.changedPathsVersion -1 && + echo "options: bloom(1,10,7) read_generation_data" >expect && + test-tool read-graph >full && + grep options full >actual && + test_cmp expect actual + ) +' + +test_expect_success 'set up repo with high bit path, version 2 changed-path' ' + git init highbit2 && + git -C highbit2 config --add commitgraph.changedPathsVersion 2 && + test_commit -C highbit2 c2 "$CENT" && + git -C highbit2 commit-graph write --reachable --changed-paths +' + +test_expect_success 'check value of version 2 changed-path' ' + ( + cd highbit2 && + echo "c01f" >expect && + get_first_changed_path_filter >actual && + test_cmp expect actual + ) +' + +test_expect_success 'version 2 changed-path used when version 2 requested' ' + ( + cd highbit2 && + test_bloom_filters_used "-- $CENT" + ) +' + +test_expect_success 'version 2 changed-path not used when version 1 requested' ' + ( + cd highbit2 && + git config --add commitgraph.changedPathsVersion 1 && + test_bloom_filters_not_used "-- $CENT" + ) +' + +test_expect_success 'version 2 changed-path used when autodetect requested' ' + ( + cd highbit2 && + git config --add commitgraph.changedPathsVersion -1 && + test_bloom_filters_used "-- $CENT" + ) +' + +test_expect_success 'when writing another commit graph, preserve existing version 2 of changed-path' ' + test_commit -C highbit2 c2double "$CENT$CENT" && + git -C highbit2 commit-graph write --reachable --changed-paths && + ( + cd highbit2 && + git config --add commitgraph.changedPathsVersion -1 && + echo "options: bloom(2,10,7) read_generation_data" >expect && + test-tool read-graph >full && + grep options full >actual && + test_cmp expect actual + ) +' + +test_expect_success 'when writing commit graph, do not reuse changed-path of another version' ' + git init doublewrite && + test_commit -C doublewrite c "$CENT" && + git -C doublewrite config --add commitgraph.changedPathsVersion 1 && + git -C doublewrite commit-graph write --reachable --changed-paths && + git -C doublewrite config --add commitgraph.changedPathsVersion 2 && + git -C doublewrite commit-graph write --reachable --changed-paths && + ( + cd doublewrite && + echo "c01f" >expect && + get_first_changed_path_filter >actual && + test_cmp expect actual + ) +' + test_done From patchwork Mon Aug 21 21:44:19 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13359850 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 16C35EE49A6 for ; Mon, 21 Aug 2023 21:44:26 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230518AbjHUVoZ (ORCPT ); Mon, 21 Aug 2023 17:44:25 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35490 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231128AbjHUVoX (ORCPT ); Mon, 21 Aug 2023 17:44:23 -0400 Received: from mail-yb1-xb36.google.com (mail-yb1-xb36.google.com [IPv6:2607:f8b0:4864:20::b36]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 34D96136 for ; Mon, 21 Aug 2023 14:44:21 -0700 (PDT) Received: by mail-yb1-xb36.google.com with SMTP id 3f1490d57ef6-d62bdd1a97dso3885670276.3 for ; Mon, 21 Aug 2023 14:44:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20221208.gappssmtp.com; s=20221208; t=1692654260; x=1693259060; 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=Te2AZ3P/HGGnsA/Ke/hZvaKdqlqL+o6m0CJ5WKhMSYs=; b=qE9TRLXwQIf2IL27dBerYKrSPU1uHZxCVrxjBqE8Kbt8A1bMCWCYI/p1ZyPN4ufAkX 3ddZVqWh55uX6eiqjlR+8Hu3+KL0w7ncIQr1dIcuSzo+SGGuFDvXLosgqQE+zY2HzzSW u7/lSuWdUEkPf0pYc9GZJ8I2K16czGRy+ydlhfndK4crmmsZPSngPKvD5WSSIkiuEGeo Dq31B3C/ozVhjcwLyIX070vzc+HLtPPwntuxh0A0U5Kvwqye9wziJC5zr96rJVJ2r9SH LS7en8+rNtN4CZFTTfDVYWM+L/KYc0PQfSOvsdHTdQsjQSuyf0oH0uf3AMBy0BJTeC8X vjWg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692654260; x=1693259060; 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=Te2AZ3P/HGGnsA/Ke/hZvaKdqlqL+o6m0CJ5WKhMSYs=; b=VKDSEax9y+fx5Ml5HGwYK/fYDoFKf/1dJXWemyvYhjQ4ewhAE9ifp+yTs2VhQEm1N/ Ll3g31eI3oFzPHLlr4afUId40PdbR7LrxPFsx5UoSRp8iudCMzpj7tq3IPS/Ecbq4/eY TY5+1blX5LDr/fYnnLooj+uaF/EcrlLzMsMfuUWaRXzbrzc2u6CMb6gROKLPAfs+Jl/B 0tOVXBgY5FImmdd70NkncHZs+BZgBj7QS64n7k4NVXgloetERfxv2WRqLT1+0Vqt4LLM OWPNQ6Kz5P3COYQby9RGBflp7IqWDftflVQgqC6pgDmTFTjuffb3wpYxY6WqlasSXWbY bTuA== X-Gm-Message-State: AOJu0Yx27dcnuh9M7dM346Iu0p7g3a3BxEjolB6G7aR/sJOlaWm33Bfk zHkmq94u11ltr9BlPvJVPd9SNkcgfEGgUeUyNnKC+Q== X-Google-Smtp-Source: AGHT+IHZ00/k3KEdYrpQOI0ODh9hQQ6B3p9g73YHc6MsbSmN0ZSIn+BCBPzCTqbCIx5aroPWHN7hGw== X-Received: by 2002:a25:d650:0:b0:d06:f117:774a with SMTP id n77-20020a25d650000000b00d06f117774amr8772479ybg.30.1692654260325; Mon, 21 Aug 2023 14:44: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 203-20020a2510d4000000b00d05bb67965dsm2066657ybq.8.2023.08.21.14.44.20 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 21 Aug 2023 14:44:20 -0700 (PDT) Date: Mon, 21 Aug 2023 17:44:19 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jonathan Tan , Junio C Hamano , Jeff King , Derrick Stolee Subject: [PATCH 08/15] bloom: annotate filters with hash version Message-ID: <48347796c81f03f676295cf0217715e39192a522.1692654233.git.me@ttaylorr.com> References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org In subsequent commits, we will want to load existing Bloom filters out of a commit-graph, even when the hash version they were computed with does not match the value of `commitGraph.changedPathVersion`. In order to differentiate between the two, add a "version" field to each Bloom filter. Signed-off-by: Taylor Blau --- bloom.c | 11 ++++++++--- bloom.h | 1 + 2 files changed, 9 insertions(+), 3 deletions(-) diff --git a/bloom.c b/bloom.c index ebef5cfd2f..9b6a30f6f6 100644 --- a/bloom.c +++ b/bloom.c @@ -55,6 +55,7 @@ int load_bloom_filter_from_graph(struct commit_graph *g, filter->data = (unsigned char *)(g->chunk_bloom_data + sizeof(unsigned char) * start_index + BLOOMDATA_CHUNK_HEADER_SIZE); + filter->version = g->bloom_filter_settings->hash_version; return 1; } @@ -240,11 +241,13 @@ static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED, return strcmp(e1->path, e2->path); } -static void init_truncated_large_filter(struct bloom_filter *filter) +static void init_truncated_large_filter(struct bloom_filter *filter, + int version) { filter->data = xmalloc(1); filter->data[0] = 0xFF; filter->len = 1; + filter->version = version; } struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, @@ -329,13 +332,15 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, } if (hashmap_get_size(&pathmap) > settings->max_changed_paths) { - init_truncated_large_filter(filter); + init_truncated_large_filter(filter, + settings->hash_version); if (computed) *computed |= BLOOM_TRUNC_LARGE; goto cleanup; } filter->len = (hashmap_get_size(&pathmap) * settings->bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD; + filter->version = settings->hash_version; if (!filter->len) { if (computed) *computed |= BLOOM_TRUNC_EMPTY; @@ -355,7 +360,7 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, } else { for (i = 0; i < diff_queued_diff.nr; i++) diff_free_filepair(diff_queued_diff.queue[i]); - init_truncated_large_filter(filter); + init_truncated_large_filter(filter, settings->hash_version); if (computed) *computed |= BLOOM_TRUNC_LARGE; diff --git a/bloom.h b/bloom.h index 138d57a86b..330a140520 100644 --- a/bloom.h +++ b/bloom.h @@ -55,6 +55,7 @@ struct bloom_filter_settings { struct bloom_filter { unsigned char *data; size_t len; + int version; }; /* From patchwork Mon Aug 21 21:44:25 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13359851 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 0D418EE4996 for ; Mon, 21 Aug 2023 21:44:32 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231127AbjHUVoc (ORCPT ); Mon, 21 Aug 2023 17:44:32 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35640 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230523AbjHUVoa (ORCPT ); Mon, 21 Aug 2023 17:44:30 -0400 Received: from mail-yw1-x1131.google.com (mail-yw1-x1131.google.com [IPv6:2607:f8b0:4864:20::1131]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 3FEE9197 for ; Mon, 21 Aug 2023 14:44:27 -0700 (PDT) Received: by mail-yw1-x1131.google.com with SMTP id 00721157ae682-58fc4eaa04fso25543427b3.0 for ; Mon, 21 Aug 2023 14:44:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20221208.gappssmtp.com; s=20221208; t=1692654266; x=1693259066; 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=BxFnySS/I+7iqAJ3evyX3JM4TeSu6TWvOmMqyNnJz1w=; b=j068tic6DRqKPPBSXBs7O9MV9IF4Rfh0tOglpT+cuvPrEMP87BofaCWaKDo+UMFkhK M5O7oeWCV2+6VJIDDZdNvvCCKc22cvEAN84xvojHJseM0TufMkzNHSvOPo1FCAmnfeun dAmRp+U+2WNYjDlnQrWFbZM2RGBRAmyYm4eR0m6Ejdp9OwGys+strOvwgqEvugU4ZMuh javsoivlCEI0gkuVv5dTNKXj3Ph9YN+LspXaQxwhajtKEixnIkTDhJy1QVlEWgEsGNdP N/p+wc6Wj3W//5eaHGjudRzIIoyu06oHm95f+hInnVtaDjXaKDCe0HNjUhYH8aMnPptB KDMQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692654266; x=1693259066; 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=BxFnySS/I+7iqAJ3evyX3JM4TeSu6TWvOmMqyNnJz1w=; b=gLu3RsFIzccJ2wQ1B96CP2Jic78goyvV+lmDWbGoKleBfvrJpl6mALZoAEaP3iBxH+ +C8H0QpXSLUW4gurP7gfEE9jD+sIX+fmh1jqHc2iPILGT5FWGs+WLKJkq5dLTZiKKJ5p 0hwT5K1D1ynKaF/XZzn6ov0eSBsgqQdGrCCq9BOv8f8TL2E1D1gcwb26xV35XhPjPKBW mZtf7BZYBxnLYW0P7d0k2VUAHLiXxp4SaX5lk5vlg/TyQ1jgSepMuJO0+1eJmKsqhGi7 pn+UtuDQAF7fjZ0+zuwiOLAredr2g0sUnT21WGvxUYhWbDvn8JBYJnV9TZ0BxjYRCT4j BCzA== X-Gm-Message-State: AOJu0YxVniKJ9riG4ouDyCLkvLbNRLbzQy7XltkxAaFLvnpreaQXjQch JHpXPRACgxWADS+0Uqhh/PUMAVSQvi2cfc0mvyyRVw== X-Google-Smtp-Source: AGHT+IFGVPIzE7Ija5o+UJtX7EuLjpSnkHbAA4ECDJeNCz3DTois1Y3tcOLDT7t6MMCCz3Aq1+q7nQ== X-Received: by 2002:a81:d346:0:b0:58c:d790:b129 with SMTP id d6-20020a81d346000000b0058cd790b129mr7841339ywl.46.1692654266188; Mon, 21 Aug 2023 14:44: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 s67-20020a817746000000b0057a05834754sm2455566ywc.75.2023.08.21.14.44.25 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 21 Aug 2023 14:44:25 -0700 (PDT) Date: Mon, 21 Aug 2023 17:44:25 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jonathan Tan , Junio C Hamano , Jeff King , Derrick Stolee Subject: [PATCH 09/15] bloom: prepare to discard incompatible Bloom filters Message-ID: <7c5a0090b52f829cab3ab2e107029a74b7ecfa87.1692654233.git.me@ttaylorr.com> References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Callers use the inline `get_bloom_filter()` implementation as a thin wrapper around `get_or_compute_bloom_filter()`. The former calls the latter with a value of "0" for `compute_if_not_present`, making `get_bloom_filter()` the default read-only path for fetching an existing Bloom filter. Callers expect the value returned from `get_bloom_filter()` is usable, that is that it's compatible with the configured value corresponding to `commitGraph.changedPathsVersion`. This is OK, since the commit-graph machinery only initializes its BDAT chunk (thereby enabling it to service Bloom filter queries) when the Bloom filter hash_version is compatible with our settings. So any value returned by `get_bloom_filter()` is trivially useable. However, subsequent commits will load the BDAT chunk even when the Bloom filters are built with incompatible hash versions. Prepare to handle this by teaching `get_bloom_filter()` to discard filters that are incompatible with the configured hash version. Callers who wish to read incompatible filters (e.g., for upgrading filters from v1 to v2) may use the lower level routine, `get_or_compute_bloom_filter()`. Signed-off-by: Taylor Blau --- bloom.c | 20 +++++++++++++++++++- bloom.h | 20 ++++++++++++++++++-- 2 files changed, 37 insertions(+), 3 deletions(-) diff --git a/bloom.c b/bloom.c index 9b6a30f6f6..739fa093ba 100644 --- a/bloom.c +++ b/bloom.c @@ -250,6 +250,23 @@ static void init_truncated_large_filter(struct bloom_filter *filter, filter->version = version; } +struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c) +{ + struct bloom_filter *filter; + int hash_version; + + filter = get_or_compute_bloom_filter(r, c, 0, NULL, NULL); + if (!filter) + return NULL; + + prepare_repo_settings(r); + hash_version = r->settings.commit_graph_changed_paths_version; + + if (!(hash_version == -1 || hash_version == filter->version)) + return NULL; /* unusable filter */ + return filter; +} + struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, struct commit *c, int compute_if_not_present, @@ -275,7 +292,8 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, filter, graph_pos); } - if (filter->data && filter->len) + if ((filter->data && filter->len) && + (!settings || settings->hash_version == filter->version)) return filter; if (!compute_if_not_present) return NULL; diff --git a/bloom.h b/bloom.h index 330a140520..bfe389e29c 100644 --- a/bloom.h +++ b/bloom.h @@ -110,8 +110,24 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, const struct bloom_filter_settings *settings, enum bloom_filter_computed *computed); -#define get_bloom_filter(r, c) get_or_compute_bloom_filter( \ - (r), (c), 0, NULL, NULL) +/* + * Find the Bloom filter associated with the given commit "c". + * + * If any of the following are true + * + * - the repository does not have a commit-graph, or + * - the repository disables reading from the commit-graph, or + * - the given commit does not have a Bloom filter computed, or + * - there is a Bloom filter for commit "c", but it cannot be read + * because the filter uses an incompatible version of murmur3 + * + * , then `get_bloom_filter()` will return NULL. Otherwise, the corresponding + * Bloom filter will be returned. + * + * For callers who wish to inspect Bloom filters with incompatible hash + * versions, use get_or_compute_bloom_filter(). + */ +struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c); int bloom_filter_contains(const struct bloom_filter *filter, const struct bloom_key *key, From patchwork Mon Aug 21 21:44:28 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13359852 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 08593EE4996 for ; Mon, 21 Aug 2023 21:44:35 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231143AbjHUVof (ORCPT ); Mon, 21 Aug 2023 17:44:35 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38126 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230520AbjHUVod (ORCPT ); Mon, 21 Aug 2023 17:44:33 -0400 Received: from mail-yb1-xb32.google.com (mail-yb1-xb32.google.com [IPv6:2607:f8b0:4864:20::b32]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 6AF7912C for ; Mon, 21 Aug 2023 14:44:30 -0700 (PDT) Received: by mail-yb1-xb32.google.com with SMTP id 3f1490d57ef6-d743a5fe05aso3476667276.2 for ; Mon, 21 Aug 2023 14:44:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20221208.gappssmtp.com; s=20221208; t=1692654269; x=1693259069; 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=/I7tI3w2DMU4MzDAcYe5XwikCSrCjmf0gM0LYCrp5V8=; b=IKMvLLYatrdc7KJVeSVIuOGu5nHdTjTukj0g+kJRQjXHBeTlY/iPFl/c7HUllCRxHL FqsE0pmgIyLgii6+EgmCwE4zaW2Rx3cIdvSfDzQWJdwcPDcxA09IyVuj7YhxWl2NVNaX qF7r2Fd6CiSIbXZUMoIeSvQvo4W1v+FqQrwEuSyGyar0MuidaX3PZPIWSakFtfdNv9eY an5f8gGBb2iQnTpgXiWrsvg1w7YnVbZXqHshRJWKvTUzOxyHhv/juJOun67f0x2nG3Hn 8tMt6bYrSBIuYmrKNsTQfv0HEwqlTqqKYjqlca49HStbAEBckV5sG+dG6RXJB9s4bFrQ JXSA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692654269; x=1693259069; 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=/I7tI3w2DMU4MzDAcYe5XwikCSrCjmf0gM0LYCrp5V8=; b=VCWEzQPirJmPhVWd14lpWgRPTPphmb3dhlXWevXLfrzKDELQjDBidVoxejQ7iCSuvt W1L9XsEEMDk82rIH86idPR7qDlap+shbbfI2lXSlCUfEwXAjewqHN2cabC6Qg56BQaDm I0LoUkKBQyULLTHQXnETatef0W1yFWP6Iux9T1LWZM3sdaSCG6HfMkCd4ZRvdP07/Fsf elMnY/TH/rawsZ9H/Xhvc+U6T4LPsdOLrFVD0zEy1WkxA/vlTpKAQ9dobOgPtgPVwMXB 7JF9WYu0xqyoqnXKd6ZdDWN6WzZeTZw2vvvlDULFO0cJgEhZRDfPzLVued5vvR6tO2I5 zlrQ== X-Gm-Message-State: AOJu0YwYcG0srgJpHEB8L08UX4v1pPz9LU1h7ZLpec6euJH0cX2HW0XR 61GknSYwPde3MlhGgkO1tLLtURbEsAy+KCRkA5d1iw== X-Google-Smtp-Source: AGHT+IHhsYLo1iTetjggrLtp/MJXtn8zSo5H8KQ13Ez08VEz13VQV2JAytLx4twaJbKfJTeDO53gwQ== X-Received: by 2002:a25:2f17:0:b0:d12:25d:fd60 with SMTP id v23-20020a252f17000000b00d12025dfd60mr7755802ybv.9.1692654269552; Mon, 21 Aug 2023 14:44: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 v193-20020a25c5ca000000b00d43697c429esm2067413ybe.50.2023.08.21.14.44.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 21 Aug 2023 14:44:29 -0700 (PDT) Date: Mon, 21 Aug 2023 17:44:28 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jonathan Tan , Junio C Hamano , Jeff King , Derrick Stolee Subject: [PATCH 10/15] t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()` Message-ID: References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org The existing implementation of test_bloom_filters_not_used() asserts that the Bloom filter sub-system has not been initialized at all, by checking for the absence of any data from it from trace2. In the following commit, it will become possible to load Bloom filters without using them (e.g., because `commitGraph.changedPathVersion` is incompatible with the hash version with which the commit-graph's Bloom filters were written). When this is the case, it's possible to initialize the Bloom filter sub-system, while still not using any Bloom filters. When this is the case, check that the data dump from the Bloom sub-system is all zeros, indicating that no filters were used. Signed-off-by: Taylor Blau --- t/t4216-log-bloom.sh | 14 +++++++++++++- 1 file changed, 13 insertions(+), 1 deletion(-) diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh index 775e59d864..a77caca789 100755 --- a/t/t4216-log-bloom.sh +++ b/t/t4216-log-bloom.sh @@ -81,7 +81,19 @@ test_bloom_filters_used () { test_bloom_filters_not_used () { log_args=$1 setup "$log_args" && - ! grep -q "statistics:{\"filter_not_present\":" "$TRASH_DIRECTORY/trace.perf" && + + if grep -q "statistics:{\"filter_not_present\":" "$TRASH_DIRECTORY/trace.perf" + then + # if the Bloom filter system is initialized, ensure that no + # filters were used + data="statistics:{" + data="$data\"filter_not_present\":0," + data="$data\"maybe\":0," + data="$data\"definitely_not\":0," + data="$data\"false_positive\":0}" + + grep -q "$data" "$TRASH_DIRECTORY/trace.perf" + fi && test_cmp log_wo_bloom log_w_bloom } From patchwork Mon Aug 21 21:44:32 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13359853 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 084B5EE4996 for ; Mon, 21 Aug 2023 21:44:41 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230525AbjHUVol (ORCPT ); Mon, 21 Aug 2023 17:44:41 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:40612 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231130AbjHUVok (ORCPT ); Mon, 21 Aug 2023 17:44:40 -0400 Received: from mail-yw1-x112f.google.com (mail-yw1-x112f.google.com [IPv6:2607:f8b0:4864:20::112f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 14D2E18D for ; Mon, 21 Aug 2023 14:44:34 -0700 (PDT) Received: by mail-yw1-x112f.google.com with SMTP id 00721157ae682-58caaedb20bso43621667b3.1 for ; Mon, 21 Aug 2023 14:44:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20221208.gappssmtp.com; s=20221208; t=1692654273; x=1693259073; 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=tqpZRffTNAuTW9lnNBgr48lAndSmA4HxvpZWVnPLdn4=; b=MtCC7wghOiLrB3t5dDu6uoDO7lWMIHxDhIgscv4xBFt8JNEDp2ZIHOVXF3wayYeSMN fiak3RVFE47AcplLu5NsyRTb409+cd7DHu0sSltrwmG5UBkzEoshykpJVv2Or2Iks0r8 yOyxgfAVZI8JAQ+FjXW3BYJJniQ+AxBPs5pCbG/AnS+9FJ8HE92iMIkfzigyFJIZ+gDt dhAM3b/4HWZintVone/wV0IOa//4uZPMQmtFKZJsM3KP1364WXQj1gBh+oZ5gSlxy4VY lhlFxAajdfYq2/mZH4S5qzhhxircsYYoABpojc/5Lzo0aTSDDicZi1AdqfjZ927/5ZHQ Tf/A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692654273; x=1693259073; 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=tqpZRffTNAuTW9lnNBgr48lAndSmA4HxvpZWVnPLdn4=; b=h484xFr/mDcRP8ID1Nb9mENzlNlZH+e8RjDzd9tZGeM5VRjK2nlQQ9gvDCV4EaIq2A mjIhD7yFUfNa+GVLSomgoEZRXds1yhm7Y+XmGdOkgIMYGdtFNLruThfn6IwSzXr1Sz/o kyMlbkmS6QzXFom24wYAaY+xTpbl1q9TJUvBNAX06/v0/dqtQ1gCr1Tt9t6EK5AgJMMt UcutlnC5yVAoZacC6PcOAwZOF7NcGHy1asl3PhezxqHuDuPWMpohqQ8TYIq2lgNJoTRL oVLFs75UoaCpCeblozwx9KYgbKW7QOL4t308x6SmAHqwdSPeLDWLnwZD79rMlsc6SFa9 1NgQ== X-Gm-Message-State: AOJu0YylY2AzJsd4N0HOiYM9qs4D4bUtoXh8Rc9AfVqiRiRd2xH6fdJW lf3NpXtrZkXVP9BcLazj1QBM0azOI7OJ6Y8qECn3CA== X-Google-Smtp-Source: AGHT+IHpjWx1XPHm+VXdZZuqLyeMD4KUvhAmuPSKzl+YHXB0Lx/WfgBcaTYAWqr5F3wR3dU14kLSLg== X-Received: by 2002:a0d:e2c5:0:b0:589:a937:2b67 with SMTP id l188-20020a0de2c5000000b00589a9372b67mr8151738ywe.9.1692654273186; Mon, 21 Aug 2023 14:44:33 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id u64-20020a816043000000b00582fae92aa7sm2442988ywb.93.2023.08.21.14.44.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 21 Aug 2023 14:44:33 -0700 (PDT) Date: Mon, 21 Aug 2023 17:44:32 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jonathan Tan , Junio C Hamano , Jeff King , Derrick Stolee Subject: [PATCH 11/15] commit-graph.c: unconditionally load Bloom filters Message-ID: <05516aa898aa5008eac113381b6aa58ef7b90065.1692654233.git.me@ttaylorr.com> References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org In 9e4df4da07 (commit-graph: new filter ver. that fixes murmur3, 2023-08-01), we began ignoring the Bloom data ("BDAT") chunk for commit-graphs whose Bloom filters were computed using a hash version incompatible with the value of `commitGraph.changedPathVersion`. Now that the Bloom API has been hardened to discard these incompatible filters (with the exception of low-level APIs), we can safely load these Bloom filters unconditionally. We no longer want to return early from `graph_read_bloom_data()`, and similarly do not want to set the bloom_settings' `hash_version` field as a side-effect. The latter is because we want to wait until we know which Bloom settings we're using (either the defaults, from the GIT_TEST variables, or from the previous commit-graph layer) before deciding what hash_version to use. If we detect an existing BDAT chunk, we'll infer the rest of the settings (e.g., number of hashes, bits per entry, and maximum number of changed paths) from the earlier graph layer. The hash_version will be inferred from the previous layer as well, unless one has already been specified via configuration. Once all of that is done, we normalize the value of the hash_version to either "1" or "2". Signed-off-by: Taylor Blau --- commit-graph.c | 19 ++++++++++--------- 1 file changed, 10 insertions(+), 9 deletions(-) diff --git a/commit-graph.c b/commit-graph.c index f7322c4fff..665a3edf78 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -317,12 +317,6 @@ static int graph_read_bloom_data(const unsigned char *chunk_start, uint32_t hash_version; hash_version = get_be32(chunk_start); - if (*c->commit_graph_changed_paths_version == -1) { - *c->commit_graph_changed_paths_version = hash_version; - } else if (hash_version != *c->commit_graph_changed_paths_version) { - return 0; - } - g->chunk_bloom_data = chunk_start; g->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings)); g->bloom_filter_settings->hash_version = hash_version; @@ -2408,8 +2402,7 @@ int write_commit_graph(struct object_directory *odb, ctx->write_generation_data = (get_configured_generation_version(r) == 2); ctx->num_generation_data_overflows = 0; - bloom_settings.hash_version = r->settings.commit_graph_changed_paths_version == 2 - ? 2 : 1; + bloom_settings.hash_version = r->settings.commit_graph_changed_paths_version; bloom_settings.bits_per_entry = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY", bloom_settings.bits_per_entry); bloom_settings.num_hashes = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_NUM_HASHES", @@ -2441,10 +2434,18 @@ int write_commit_graph(struct object_directory *odb, /* We have changed-paths already. Keep them in the next graph */ if (g && g->bloom_filter_settings) { ctx->changed_paths = 1; - ctx->bloom_settings = g->bloom_filter_settings; + + /* don't propagate the hash_version unless unspecified */ + if (bloom_settings.hash_version == -1) + bloom_settings.hash_version = g->bloom_filter_settings->hash_version; + bloom_settings.bits_per_entry = g->bloom_filter_settings->bits_per_entry; + bloom_settings.num_hashes = g->bloom_filter_settings->num_hashes; + bloom_settings.max_changed_paths = g->bloom_filter_settings->max_changed_paths; } } + bloom_settings.hash_version = bloom_settings.hash_version == 2 ? 2 : 1; + if (ctx->split) { struct commit_graph *g = ctx->r->objects->commit_graph; From patchwork Mon Aug 21 21:44:36 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13359854 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id EB03BEE49A5 for ; Mon, 21 Aug 2023 21:44:45 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231130AbjHUVoq (ORCPT ); Mon, 21 Aug 2023 17:44:46 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:40726 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231156AbjHUVoo (ORCPT ); Mon, 21 Aug 2023 17:44:44 -0400 Received: from mail-yw1-x1130.google.com (mail-yw1-x1130.google.com [IPv6:2607:f8b0:4864:20::1130]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 1B56618E for ; Mon, 21 Aug 2023 14:44:38 -0700 (PDT) Received: by mail-yw1-x1130.google.com with SMTP id 00721157ae682-58caaedb20bso43622027b3.1 for ; Mon, 21 Aug 2023 14:44:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20221208.gappssmtp.com; s=20221208; t=1692654277; x=1693259077; 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=4e6CTo3zCBO/PX00stZfCGUtsN45iWmh3zhdV8cVHmQ=; b=4O9U+6bbH73iDJrifbaYswWr10Hh+ZsJTe8uLblpNMOyCQSNTdKELU/AbqKru1UpWw UT/XoMnXXtXGF1q4EUaSSTQ+bSUjU85h8I9cnmkMWN3wzLllhEnspVPBIrpgXdurJz5I ZY7BYSO/VAy0hh/eLzp7sjLuWgFXAWXEDJrWunW/rpekJO5M2DVvKu8awD3jTjuHF1Wm PzUrzmt5HiNxKrJLcpqrANWRkrTxw/pmTwRFhZY1fN5gFxO8WCIT+aRl9dkvm+TADaHQ WibPLXVOMe2iMb8+4qrT8+LK0hJ6JmBXrUt0BvAjER/+LxKcLWfoo8ul4ZPp6eIP46xL AIXg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692654277; x=1693259077; 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=4e6CTo3zCBO/PX00stZfCGUtsN45iWmh3zhdV8cVHmQ=; b=c5SrN0MSoQ4IgJVDP8FaGlpA+AJ2cvJ1ZopTbyhESNCBDT9uWqfooFtGc3dIM8IALv 6fW0KbzlqZspHdMfrRsazRiU0d1FNrE605xJzwkOikLVzHpcSk/m2zQLQuPpa/Bvj32g JTjw4/RIe/jmz+pFyZk9/XPXEesufCX5ekwIr7vATSzFVzEQXVkyP1mJUy4BBZ08YjN3 kV59E2QK9hMVvXIuoEgKyOFQvJTcYo9/MRRWFDsAIYjghS5YZhursSIQ77Uu6eTVvN0v zCQfNmEZbjLZMyzrYOcHoTxqCqT1EOhsLvkMdI7usoP3AXgmLJ2xbSI5Rb98mlj9mxO+ 1bFg== X-Gm-Message-State: AOJu0YwDvJA/mriqzbmKmsLPa6NzIVYfVYjdZLaZoUlpUn7VYRv9Woih 5kJatlhSKNxs3BANZflugbXWc07d3uhRXiH7N31JAA== X-Google-Smtp-Source: AGHT+IFqZqMzJ8hNRI8ivMv5cQWepWdGp4VTcvu3Pm3F5dP66YQsmotI4M80+BI7YNGZSpPja1npsw== X-Received: by 2002:a0d:d608:0:b0:584:61df:45e8 with SMTP id y8-20020a0dd608000000b0058461df45e8mr7395486ywd.13.1692654277143; Mon, 21 Aug 2023 14:44:37 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id x185-20020a817cc2000000b00577269ba9e9sm2429770ywc.86.2023.08.21.14.44.36 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 21 Aug 2023 14:44:36 -0700 (PDT) Date: Mon, 21 Aug 2023 17:44:36 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jonathan Tan , Junio C Hamano , Jeff King , Derrick Stolee Subject: [PATCH 12/15] commit-graph: drop unnecessary `graph_read_bloom_data_context` Message-ID: <7c144a535d30dbccff5e9b32b18571058d16c809.1692654233.git.me@ttaylorr.com> References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org The `graph_read_bloom_data_context` struct was introduced in an earlier commit in order to pass pointers to the commit-graph and changed-path Bloom filter version when reading the BDAT chunk. The previous commit no longer writes through the changed_paths_version pointer, making the surrounding context structure unnecessary. Drop it and pass a pointer to the commit-graph directly when reading the BDAT chunk. Noticed-by: Jonathan Tan Signed-off-by: Taylor Blau --- commit-graph.c | 14 ++------------ 1 file changed, 2 insertions(+), 12 deletions(-) diff --git a/commit-graph.c b/commit-graph.c index 665a3edf78..a8e33c0739 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -304,16 +304,10 @@ static int graph_read_oid_lookup(const unsigned char *chunk_start, return 0; } -struct graph_read_bloom_data_context { - struct commit_graph *g; - int *commit_graph_changed_paths_version; -}; - static int graph_read_bloom_data(const unsigned char *chunk_start, size_t chunk_size, void *data) { - struct graph_read_bloom_data_context *c = data; - struct commit_graph *g = c->g; + struct commit_graph *g = data; uint32_t hash_version; hash_version = get_be32(chunk_start); @@ -405,14 +399,10 @@ struct commit_graph *parse_commit_graph(struct repo_settings *s, } if (s->commit_graph_changed_paths_version) { - struct graph_read_bloom_data_context context = { - .g = graph, - .commit_graph_changed_paths_version = &s->commit_graph_changed_paths_version - }; pair_chunk(cf, GRAPH_CHUNKID_BLOOMINDEXES, &graph->chunk_bloom_indexes); read_chunk(cf, GRAPH_CHUNKID_BLOOMDATA, - graph_read_bloom_data, &context); + graph_read_bloom_data, graph); } if (graph->chunk_bloom_indexes && graph->chunk_bloom_data) { From patchwork Mon Aug 21 21:44:39 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13359855 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 244FCEE49A5 for ; Mon, 21 Aug 2023 21:44:49 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231153AbjHUVot (ORCPT ); Mon, 21 Aug 2023 17:44:49 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:40818 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231156AbjHUVos (ORCPT ); Mon, 21 Aug 2023 17:44:48 -0400 Received: from mail-yw1-x1131.google.com (mail-yw1-x1131.google.com [IPv6:2607:f8b0:4864:20::1131]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8F279132 for ; Mon, 21 Aug 2023 14:44:41 -0700 (PDT) Received: by mail-yw1-x1131.google.com with SMTP id 00721157ae682-58df8cab1f2so42577757b3.3 for ; Mon, 21 Aug 2023 14:44:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20221208.gappssmtp.com; s=20221208; t=1692654280; x=1693259080; 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=AFVkjvLL1z2bJFpK4xCHS/gzkxsTrBHG4zxDSPjI0po=; b=NoIrxPK2S8HURDBFRbCQj+U286jicn81M+IP8TswOlt8h1N8t+xZWFeUQOyJHNW89s kEV0Exn0faENr59CUfn1rApBnnVCU1Ll0eI1xLMBrpv3dKS7+MYFzMpV2IQwNxESSrPE XnFiQzFgjaxs/7aWk64HKmLeN/Ug7QNitbHWCanKEKMWoYoQVfGb92HELrD29Tc1DHBE eevIgH5J7tIypDZZVn28tXE9wDZ7t2uuNP5UHWuS5udYCZtRvoZ1tK8sKWBsoHkTtpc+ +wJE1uAdw145e0Sv+jybQ+hwNBig0V9rhJGm+iz0jnxNM+aKOkmrICy1uihqduo2TUTR RWPQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692654280; x=1693259080; 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=AFVkjvLL1z2bJFpK4xCHS/gzkxsTrBHG4zxDSPjI0po=; b=UevN0x/O7tlY49s+jYO1p33hyZba5gvxMRgqPiq+9fCTBvxSAbjgGAaz2DJAqwZkih s6zW+29y6J17knkiYy/jEJgpAJWxz2OVJ0gU9h6zcLhdDG3xNCayCFfaVKfvBW6uYRe3 8sMenl6wo5lu1YjLZ9fZ6A/MvaSbwX9g13rdQgSFNIJMLFdA7W+/4PLdfk8I1N84uA0A /GtB2afWQPPcdiOpwZ8lizsVrq7TGik3ZdQ7jWy+flwyatTcmgCds6AemtEQh7Kty2cW CTCM99Q7esDtIAnkfd+6mhmQyKn0e1vu5iukIdg3lb3g3JBbNDBe5pocFLp/QSv0HcVh oe+g== X-Gm-Message-State: AOJu0YyknuxsxESsmqvMEXvet13MHKoxoc4yyh7EApBc0sbcyypyZR36 V8J16wTddjTFjfsfOYNr0tx/uJ9+dJ2U4GXdP3o45Q== X-Google-Smtp-Source: AGHT+IHw9CzzC+Groq83F1udp5zX50+QFEWoFD9lxjV7FzbMqm0Bo9rYPGmywP7MWRO2blo4PSe00g== X-Received: by 2002:a81:7106:0:b0:592:36d:7430 with SMTP id m6-20020a817106000000b00592036d7430mr6079897ywc.39.1692654280695; Mon, 21 Aug 2023 14:44:40 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id v22-20020a814816000000b005922c29c025sm459207ywa.108.2023.08.21.14.44.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 21 Aug 2023 14:44:40 -0700 (PDT) Date: Mon, 21 Aug 2023 17:44:39 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jonathan Tan , Junio C Hamano , Jeff King , Derrick Stolee Subject: [PATCH 13/15] object.h: fix mis-aligned flag bits table Message-ID: References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Bit position 23 is one column too far to the left. Signed-off-by: Taylor Blau --- object.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/object.h b/object.h index 114d45954d..db25714b4e 100644 --- a/object.h +++ b/object.h @@ -62,7 +62,7 @@ void object_array_init(struct object_array *array); /* * object flag allocation: - * revision.h: 0---------10 15 23------27 + * revision.h: 0---------10 15 23------27 * fetch-pack.c: 01 67 * negotiator/default.c: 2--5 * walker.c: 0-2 From patchwork Mon Aug 21 21:44:42 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13359856 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id EAA90EE4996 for ; Mon, 21 Aug 2023 21:44:53 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231163AbjHUVoy (ORCPT ); Mon, 21 Aug 2023 17:44:54 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57632 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231150AbjHUVox (ORCPT ); Mon, 21 Aug 2023 17:44:53 -0400 Received: from mail-yb1-xb30.google.com (mail-yb1-xb30.google.com [IPv6:2607:f8b0:4864:20::b30]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 7D23A13E for ; Mon, 21 Aug 2023 14:44:44 -0700 (PDT) Received: by mail-yb1-xb30.google.com with SMTP id 3f1490d57ef6-d73ee75a796so3802548276.0 for ; Mon, 21 Aug 2023 14:44:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20221208.gappssmtp.com; s=20221208; t=1692654283; x=1693259083; h=in-reply-to:content-transfer-encoding:content-disposition :mime-version:references:message-id:subject:cc:to:from:date:from:to :cc:subject:date:message-id:reply-to; bh=sGtERO8/JYDWyA7SFLHcgHl+MdA5CVEly2K83HRrf1g=; b=vccFGg1WPtuc33Ft5T4+OLdyZbgUfsoZklCDFVcmmlwzwtE5lMJ8yHhLEQ5YfKvIOM cyDDzeuXhfUQgU8Mj27UW8cNu1V0T3fd8J4LZDY9zi3tQBobdlA+F75Lf01jYc7iXI1A vWmKZbLl9d50r53hvRIpYxP+w3hJFAhQ9Gl7q1/TjHxyW0YCxqslb6jnJZXbjBz2vM5c 2FezCgUUx28i0emmWBQk3CZoATHoyzR/ZOpA/3Koo50si/ZxbRcn1WzReRMvNQyslony KNHsiuB7Y7uBHwbmPXmBS2/3NuuE6I71ZNEJIi91b2VGZLzBRQVO/pslBxChfzLVmQO5 7TzA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692654283; x=1693259083; h=in-reply-to:content-transfer-encoding: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=sGtERO8/JYDWyA7SFLHcgHl+MdA5CVEly2K83HRrf1g=; b=PoIFgCOY2afGNilJtSbKp6HrMaxbJ59TPkxvwY1Ak1MB0JcCSYk6My7cPsu+y9Zob4 oZlRgV7bguB9aEBy2vDe4tvcNfO4DKMWvvZT2ttZrJe37+S+haHXxY+3JG6MPFemSqTd 93WyKayzOvEbFdtAfZwrhHt7UObcSBBA1jiMTuEU3T4kxoJVqk53I8A/gA4dRRLV3ns3 10CE0Wu2TJ44HzAXy2IYt5Hh/PcgY2NbjYEtWkoFeJN1uvcnS0s+rSxVRDWr08td5/r6 514dntCIT8ukKu+2Wba1BCzj4Y6GKFiL071tyZWg/ktdphQAstL39IteeGtxTfMFfRTt 568g== X-Gm-Message-State: AOJu0Yz6oDNYfC2bEAoRDMQZpTwpsO5OXRYnlElNqt0tlvjhzOvXDoKN w6Ckms+kgT7E/Fq9GTVZ3PAV1HRiZ+9pNKj/q3DEAw== X-Google-Smtp-Source: AGHT+IFYskbYYNr8yoLrzhOgzgcg5YBQOoM/wwxW5Ygm8PvpeyRQOt0UPIPgtDD4K9q+wlrAkRN6mg== X-Received: by 2002:a25:ae1b:0:b0:d2c:32cb:c631 with SMTP id a27-20020a25ae1b000000b00d2c32cbc631mr7952144ybj.27.1692654283523; Mon, 21 Aug 2023 14:44:43 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id e142-20020a25d394000000b00d743e00bb03sm1947786ybf.39.2023.08.21.14.44.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 21 Aug 2023 14:44:43 -0700 (PDT) Date: Mon, 21 Aug 2023 17:44:42 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jonathan Tan , Junio C Hamano , Jeff King , Derrick Stolee Subject: [PATCH 14/15] commit-graph: reuse existing Bloom filters where possible Message-ID: <4f69a4c41d935ede83bd89871f2f84b334953d8f.1692654233.git.me@ttaylorr.com> References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org In 9e4df4da07 (commit-graph: new filter ver. that fixes murmur3, 2023-08-01), a bug was described where it's possible for Git to produce non-murmur3 hashes when the platform's "char" type is signed, and there are paths with characters whose highest bit is set (i.e. all characters >= 0x80). That patch allows the caller to control which version of Bloom filters are read and written. However, even on platforms with a signed "char" type, it is possible to reuse existing Bloom filters if and only if there are no changed paths in any commit's first parent tree-diff whose characters have their highest bit set. When this is the case, we can reuse the existing filter without having to compute a new one. This is done by marking trees which are known to have (or not have) any such paths. When a commit's root tree is verified to not have any such paths, we mark it as such and declare that the commit's Bloom filter is reusable. Note that this heuristic only goes in one direction. If neither a commit nor its first parent have any paths in their trees with non-ASCII characters, then we know for certain that a path with non-ASCII characters will not appear in a tree-diff against that commit's first parent. The reverse isn't necessarily true: just because the tree-diff doesn't contain any such paths does not imply that no such paths exist in either tree. So we end up recomputing some Bloom filters that we don't strictly have to (i.e. their bits are the same no matter which version of murmur3 we use). But culling these out is impossible, since we'd have to perform the full tree-diff, which is the same effort as computing the Bloom filter from scratch. But because we can cache our results in each tree's flag bits, we can often avoid recomputing many filters, thereby reducing the time it takes to run $ git commit-graph write --changed-paths --reachable when upgrading from v1 to v2 Bloom filters. To benchmark this, let's generate a commit-graph in linux.git with v1 changed-paths in generation order[^1]: $ git clone git@github.com:torvalds/linux.git $ cd linux $ git commit-graph write --reachable --changed-paths $ graph=".git/objects/info/commit-graph" $ mv $graph{,.bak} Then let's time how long it takes to go from v1 to v2 filters (with and without the upgrade path enabled), resetting the state of the commit-graph each time: $ git config commitGraph.changedPathsVersion 2 $ hyperfine -p 'cp -f $graph.bak $graph' -L v 0,1 \ 'GIT_TEST_UPGRADE_BLOOM_FILTERS={v} git.compile commit-graph write --reachable --changed-paths' On linux.git (where there aren't any non-ASCII paths), the timings indicate that this patch represents a speed-up over recomputing all Bloom filters from scratch: Benchmark 1: GIT_TEST_UPGRADE_BLOOM_FILTERS=0 git.compile commit-graph write --reachable --changed-paths Time (mean ± σ): 124.873 s ± 0.316 s [User: 124.081 s, System: 0.643 s] Range (min … max): 124.621 s … 125.227 s 3 runs Benchmark 2: GIT_TEST_UPGRADE_BLOOM_FILTERS=1 git.compile commit-graph write --reachable --changed-paths Time (mean ± σ): 79.271 s ± 0.163 s [User: 74.611 s, System: 4.521 s] Range (min … max): 79.112 s … 79.437 s 3 runs Summary 'GIT_TEST_UPGRADE_BLOOM_FILTERS=1 git.compile commit-graph write --reachable --changed-paths' ran 1.58 ± 0.01 times faster than 'GIT_TEST_UPGRADE_BLOOM_FILTERS=0 git.compile commit-graph write --reachable --changed-paths' On git.git, we do have some non-ASCII paths, giving us a more modest improvement from 4.163 seconds to 3.348 seconds, for a 1.24x speed-up. On my machine, the stats for git.git are: - 8,285 Bloom filters computed from scratch - 10 Bloom filters generated as empty - 4 Bloom filters generated as truncated due to too many changed paths - 65,114 Bloom filters were reused when transitioning from v1 to v2. [^1]: Note that this is is important, since `--stdin-packs` or `--stdin-commits` orders commits in the commit-graph by their pack position (with `--stdin-packs`) or in the raw input (with `--stdin-commits`). Since we compute Bloom filters in the same order that commits appear in the graph, we must see a commit's (first) parent before we process the commit itself. This is only guaranteed to happen when sorting commits by their generation number. Signed-off-by: Taylor Blau --- bloom.c | 90 ++++++++++++++++++++++++++++++++++++++++++-- bloom.h | 1 + commit-graph.c | 5 +++ object.h | 1 + t/t4216-log-bloom.sh | 35 ++++++++++++++++- 5 files changed, 127 insertions(+), 5 deletions(-) diff --git a/bloom.c b/bloom.c index 739fa093ba..24dd874e46 100644 --- a/bloom.c +++ b/bloom.c @@ -7,6 +7,9 @@ #include "commit-graph.h" #include "commit.h" #include "commit-slab.h" +#include "tree.h" +#include "tree-walk.h" +#include "config.h" define_commit_slab(bloom_filter_slab, struct bloom_filter); @@ -250,6 +253,73 @@ static void init_truncated_large_filter(struct bloom_filter *filter, filter->version = version; } +#define VISITED (1u<<21) +#define HIGH_BITS (1u<<22) + +static int has_entries_with_high_bit(struct repository *r, struct tree *t) +{ + if (parse_tree(t)) + return 1; + + if (!(t->object.flags & VISITED)) { + struct tree_desc desc; + struct name_entry entry; + + init_tree_desc(&desc, t->buffer, t->size); + while (tree_entry(&desc, &entry)) { + size_t i; + for (i = 0; i < entry.pathlen; i++) { + if (entry.path[i] & 0x80) { + t->object.flags |= HIGH_BITS; + goto done; + } + } + + if (S_ISDIR(entry.mode)) { + struct tree *sub = lookup_tree(r, &entry.oid); + if (sub && has_entries_with_high_bit(r, sub)) { + t->object.flags |= HIGH_BITS; + goto done; + } + } + + } + +done: + t->object.flags |= VISITED; + } + + return !!(t->object.flags & HIGH_BITS); +} + +static int commit_tree_has_high_bit_paths(struct repository *r, + struct commit *c) +{ + struct tree *t; + if (repo_parse_commit(r, c)) + return 1; + t = repo_get_commit_tree(r, c); + if (!t) + return 1; + return has_entries_with_high_bit(r, t); +} + +static struct bloom_filter *upgrade_filter(struct repository *r, struct commit *c, + struct bloom_filter *filter, + int hash_version) +{ + struct commit_list *p = c->parents; + if (commit_tree_has_high_bit_paths(r, c)) + return NULL; + + if (p && commit_tree_has_high_bit_paths(r, p->item)) + return NULL; + + filter->version = hash_version; + + return filter; +} + struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c) { struct bloom_filter *filter; @@ -292,9 +362,23 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, filter, graph_pos); } - if ((filter->data && filter->len) && - (!settings || settings->hash_version == filter->version)) - return filter; + if (filter->data && filter->len) { + struct bloom_filter *upgrade; + if (!settings || settings->hash_version == filter->version) + return filter; + + /* version mismatch, see if we can upgrade */ + if (compute_if_not_present && + git_env_bool("GIT_TEST_UPGRADE_BLOOM_FILTERS", 1)) { + upgrade = upgrade_filter(r, c, filter, + settings->hash_version); + if (upgrade) { + if (computed) + *computed |= BLOOM_UPGRADED; + return upgrade; + } + } + } if (!compute_if_not_present) return NULL; diff --git a/bloom.h b/bloom.h index bfe389e29c..e3a9b68905 100644 --- a/bloom.h +++ b/bloom.h @@ -102,6 +102,7 @@ enum bloom_filter_computed { BLOOM_COMPUTED = (1 << 1), BLOOM_TRUNC_LARGE = (1 << 2), BLOOM_TRUNC_EMPTY = (1 << 3), + BLOOM_UPGRADED = (1 << 4), }; struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, diff --git a/commit-graph.c b/commit-graph.c index a8e33c0739..a3473df515 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -1045,6 +1045,7 @@ struct write_commit_graph_context { int count_bloom_filter_not_computed; int count_bloom_filter_trunc_empty; int count_bloom_filter_trunc_large; + int count_bloom_filter_upgraded; }; static int write_graph_chunk_fanout(struct hashfile *f, @@ -1651,6 +1652,8 @@ static void trace2_bloom_filter_write_statistics(struct write_commit_graph_conte ctx->count_bloom_filter_trunc_empty); trace2_data_intmax("commit-graph", ctx->r, "filter-trunc-large", ctx->count_bloom_filter_trunc_large); + trace2_data_intmax("commit-graph", ctx->r, "filter-upgraded", + ctx->count_bloom_filter_upgraded); } static void compute_bloom_filters(struct write_commit_graph_context *ctx) @@ -1692,6 +1695,8 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx) ctx->count_bloom_filter_trunc_empty++; if (computed & BLOOM_TRUNC_LARGE) ctx->count_bloom_filter_trunc_large++; + } else if (computed & BLOOM_UPGRADED) { + ctx->count_bloom_filter_upgraded++; } else if (computed & BLOOM_NOT_COMPUTED) ctx->count_bloom_filter_not_computed++; ctx->total_bloom_filter_data_size += filter diff --git a/object.h b/object.h index db25714b4e..2e5e08725f 100644 --- a/object.h +++ b/object.h @@ -75,6 +75,7 @@ void object_array_init(struct object_array *array); * commit-reach.c: 16-----19 * sha1-name.c: 20 * list-objects-filter.c: 21 + * bloom.c: 2122 * builtin/fsck.c: 0--3 * builtin/gc.c: 0 * builtin/index-pack.c: 2021 diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh index a77caca789..48f8109a66 100755 --- a/t/t4216-log-bloom.sh +++ b/t/t4216-log-bloom.sh @@ -217,6 +217,10 @@ test_filter_trunc_large () { grep "\"key\":\"filter-trunc-large\",\"value\":\"$1\"" $2 } +test_filter_upgraded () { + grep "\"key\":\"filter-upgraded\",\"value\":\"$1\"" $2 +} + test_expect_success 'correctly report changes over limit' ' git init limits && ( @@ -543,10 +547,19 @@ test_expect_success 'when writing another commit graph, preserve existing versio test_expect_success 'when writing commit graph, do not reuse changed-path of another version' ' git init doublewrite && test_commit -C doublewrite c "$CENT" && + git -C doublewrite config --add commitgraph.changedPathsVersion 1 && - git -C doublewrite commit-graph write --reachable --changed-paths && + GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \ + git -C doublewrite commit-graph write --reachable --changed-paths && + test_filter_computed 1 trace2.txt && + test_filter_upgraded 0 trace2.txt && + git -C doublewrite config --add commitgraph.changedPathsVersion 2 && - git -C doublewrite commit-graph write --reachable --changed-paths && + GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \ + git -C doublewrite commit-graph write --reachable --changed-paths && + test_filter_computed 1 trace2.txt && + test_filter_upgraded 0 trace2.txt && + ( cd doublewrite && echo "c01f" >expect && @@ -555,4 +568,22 @@ test_expect_success 'when writing commit graph, do not reuse changed-path of ano ) ' +test_expect_success 'when writing commit graph, reuse changed-path of another version where possible' ' + git init upgrade && + + test_commit -C upgrade base no-high-bits && + + git -C upgrade config --add commitgraph.changedPathsVersion 1 && + GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \ + git -C upgrade commit-graph write --reachable --changed-paths && + test_filter_computed 1 trace2.txt && + test_filter_upgraded 0 trace2.txt && + + git -C upgrade config --add commitgraph.changedPathsVersion 2 && + GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \ + git -C upgrade commit-graph write --reachable --changed-paths && + test_filter_computed 0 trace2.txt && + test_filter_upgraded 1 trace2.txt +' + test_done From patchwork Mon Aug 21 21:44:46 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 13359857 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 64323EE49A6 for ; Mon, 21 Aug 2023 21:44:59 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231207AbjHUVo6 (ORCPT ); Mon, 21 Aug 2023 17:44:58 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57704 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231183AbjHUVoz (ORCPT ); Mon, 21 Aug 2023 17:44:55 -0400 Received: from mail-yw1-x112d.google.com (mail-yw1-x112d.google.com [IPv6:2607:f8b0:4864:20::112d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C6222123 for ; Mon, 21 Aug 2023 14:44:48 -0700 (PDT) Received: by mail-yw1-x112d.google.com with SMTP id 00721157ae682-58c5642701fso43854607b3.0 for ; Mon, 21 Aug 2023 14:44:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20221208.gappssmtp.com; s=20221208; t=1692654288; x=1693259088; 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=eIyUsHtsDpp7Haa++pzGZqnhdSljz2LPLeXiNQz8j1Q=; b=TtnbVh+l1CIPd9Y+KvyglYP+hTslA6tFXOAai7gVv57JW4WPmkwdboV7nvpQJIpPh5 fwREYOn2sImEf3v3wQRef+WfAEHz8naSi5OyzphC5v35kGHNRwMfgf6U1jGwWwplRVkK cBnJ/izUHIgxSh+8DWbF7O/M+xQT2xbe52r9Av1Em90FQZRQXsoSaL408HCpYmlygzxx jj78Q4DPHm9tq1eWfm0NELzTUez71VxPesoh8LD8pmsaXthBznaPZpeHJ3R36UnyHcDR EHQ0SvhdKx3HHg8cl7ju0CvL4L3w4yLkXTauwcH8f6Anm0r2OX9xe32IUmNqMB3YFKgB tjlw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692654288; x=1693259088; 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=eIyUsHtsDpp7Haa++pzGZqnhdSljz2LPLeXiNQz8j1Q=; b=HCmxXbGU7HIA7fk9TyIjOWoWSGmp9RlWdeDw62BgvRmCAwUPHeYpl/vdciLkX/x96z Ank9KU/N1X8sc9BK7eRHRfJCgg7LWedcg9P9b2Z1nXmSPSBqYUSjpJwdj4QMJWOeEZS9 ou3hQ2tmu9igQdcgifvTagJQ/CKVl/17viEiNXw9q8oG8Vonz+n1fByXcnPGK3HmzCw4 6E+MaQnIN9X1modHhoiijtOWsqDWSLC6OfbLcvu5/5tZY7EXRglWd9/vpLi2WTI0Xt95 8U0DHhz7ueNSEropVf2+m/1z+zi7UZd/xf1qoY64rA9IKRGJewMFkbvoHchSzwR28NEF LX1A== X-Gm-Message-State: AOJu0Yw0tDJKWs5NPVS+wh/FR9gWgeWGiBnEBvWKKwbGvvBK0sOBkPp+ CaBbYJkAAjAwSOUIBWMxfUnJtqIS6MJehqOLnPq3WA== X-Google-Smtp-Source: AGHT+IEqfMYqjP64ZqtlJ2HrOMGYvEipqU3g192GkvWTDHYO6ojQzDNM8ahq84J+2UJu+2MMOKZCyQ== X-Received: by 2002:a0d:ccc2:0:b0:58c:f957:d1c4 with SMTP id o185-20020a0dccc2000000b0058cf957d1c4mr7888390ywd.36.1692654287899; Mon, 21 Aug 2023 14:44:47 -0700 (PDT) Received: from localhost (104-178-186-189.lightspeed.milwwi.sbcglobal.net. [104.178.186.189]) by smtp.gmail.com with ESMTPSA id t125-20020a0dd183000000b005837fe8dbe8sm2435897ywd.8.2023.08.21.14.44.47 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 21 Aug 2023 14:44:47 -0700 (PDT) Date: Mon, 21 Aug 2023 17:44:46 -0400 From: Taylor Blau To: git@vger.kernel.org Cc: Jonathan Tan , Junio C Hamano , Jeff King , Derrick Stolee Subject: [PATCH 15/15] bloom: introduce `deinit_bloom_filters()` Message-ID: References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org After we are done using Bloom filters, we do not currently clean up any memory allocated by the commit slab used to store those filters in the first place. Besides the bloom_filter structures themselves, there is mostly nothing to free() in the first place, since in the read-only path all Bloom filter's `data` members point to a memory mapped region in the commit-graph file itself. But when generating Bloom filters from scratch (or initializing truncated filters) we allocate additional memory to store the filter's data. Keep track of when we need to free() this additional chunk of memory by using an extra pointer `to_free`. Most of the time this will be NULL (indicating that we are representing an existing Bloom filter stored in a memory mapped region). When it is non-NULL, free it before discarding the Bloom filters slab. Suggested-by: Jonathan Tan Signed-off-by: Taylor Blau --- bloom.c | 16 +++++++++++++++- bloom.h | 3 +++ commit-graph.c | 4 ++++ 3 files changed, 22 insertions(+), 1 deletion(-) diff --git a/bloom.c b/bloom.c index 24dd874e46..ff131893cd 100644 --- a/bloom.c +++ b/bloom.c @@ -59,6 +59,7 @@ int load_bloom_filter_from_graph(struct commit_graph *g, sizeof(unsigned char) * start_index + BLOOMDATA_CHUNK_HEADER_SIZE); filter->version = g->bloom_filter_settings->hash_version; + filter->to_free = NULL; return 1; } @@ -231,6 +232,18 @@ void init_bloom_filters(void) init_bloom_filter_slab(&bloom_filters); } +static void free_one_bloom_filter(struct bloom_filter *filter) +{ + if (!filter) + return; + free(filter->to_free); +} + +void deinit_bloom_filters(void) +{ + deep_clear_bloom_filter_slab(&bloom_filters, free_one_bloom_filter); +} + static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED, const struct hashmap_entry *eptr, const struct hashmap_entry *entry_or_key, @@ -247,7 +260,7 @@ static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED, static void init_truncated_large_filter(struct bloom_filter *filter, int version) { - filter->data = xmalloc(1); + filter->data = filter->to_free = xmalloc(1); filter->data[0] = 0xFF; filter->len = 1; filter->version = version; @@ -449,6 +462,7 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, filter->len = 1; } CALLOC_ARRAY(filter->data, filter->len); + filter->to_free = filter->data; hashmap_for_each_entry(&pathmap, &iter, e, entry) { struct bloom_key key; diff --git a/bloom.h b/bloom.h index e3a9b68905..d20e64bfbb 100644 --- a/bloom.h +++ b/bloom.h @@ -56,6 +56,8 @@ struct bloom_filter { unsigned char *data; size_t len; int version; + + void *to_free; }; /* @@ -96,6 +98,7 @@ void add_key_to_filter(const struct bloom_key *key, const struct bloom_filter_settings *settings); void init_bloom_filters(void); +void deinit_bloom_filters(void); enum bloom_filter_computed { BLOOM_NOT_COMPUTED = (1 << 0), diff --git a/commit-graph.c b/commit-graph.c index a3473df515..585539da2f 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -723,6 +723,7 @@ static void close_commit_graph_one(struct commit_graph *g) void close_commit_graph(struct raw_object_store *o) { close_commit_graph_one(o->commit_graph); + deinit_bloom_filters(); o->commit_graph = NULL; } @@ -2523,6 +2524,9 @@ int write_commit_graph(struct object_directory *odb, res = write_commit_graph_file(ctx); + if (ctx->changed_paths) + deinit_bloom_filters(); + if (ctx->split) mark_commit_graphs(ctx);