From patchwork Tue Aug 1 18:41:36 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Tan X-Patchwork-Id: 13337171 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 CAD26C0015E for ; Tue, 1 Aug 2023 18:42:11 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229814AbjHASmK (ORCPT ); Tue, 1 Aug 2023 14:42:10 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:53308 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230401AbjHASmH (ORCPT ); Tue, 1 Aug 2023 14:42:07 -0400 Received: from mail-yb1-xb49.google.com (mail-yb1-xb49.google.com [IPv6:2607:f8b0:4864:20::b49]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 6C1B12712 for ; Tue, 1 Aug 2023 11:41:50 -0700 (PDT) Received: by mail-yb1-xb49.google.com with SMTP id 3f1490d57ef6-c5fc972760eso6471559276.1 for ; Tue, 01 Aug 2023 11:41:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1690915309; x=1691520109; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=UP7ngzbctY+J++YVHHRiOWNnUiMb65kHHS+WU+BGA8c=; b=nU8JKLA1xPNR9sukGBFIYhTtIVJmUQNrrNVV3GBmCxN852Kd5LC9qmtPDHFxNg+Eqh rJncHVYSQ/L4N8Kp1yzEsXR98uZ/piij33g1n8/Cs80rgKvqG4fIN0Jb7uqztmhEOPkz 2lFHTaRFAeQAkaAj5du1S/OJtDbFCI3F4GP1wa64kGzkUtac485sjoOmoBjy+KGVXZHL Zv4c+G8GZuyUYE30lFzTbB1XYuGsAQjmSxKOGKn5M1f6zU/QQ6F+gp7oeRPQDHPIdeoS bpZIATcVgPlxUXpbfHcvF3ml1UO7IzY0MLXXyzpMB/EL5lcjRoxpSrQcuvMllDaujF54 t+2A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690915309; x=1691520109; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=UP7ngzbctY+J++YVHHRiOWNnUiMb65kHHS+WU+BGA8c=; b=PVqX6MInDLlYxulMUEji07UjkRtIB6XP/j6q3dZ+ur1aiYjmq+ya1lozqFPOtbiXBZ BekGhw9/z7+zEMBONyyiUY187VX+76ceYpks3OXqmGtzP6xDZP2yw/h/2IbZnE31W6I0 6YGMiemUyrrGWWwWZz++NwJ4Px1gCpPf9crY0nGiearcIVE7bNv4a/U7XBFVwRtGMLFg 2tiIFFxMoWHIX4tEnR27N9s9Y+D7M7oc/rRiBPwKtr9HXfol4jv7ft6XuXNz+s0HBIfD mbxca8hL4DGM3dHg5yXHWg3E7Hz8yyAM99ApSojIniTYURisZz78VJBWZ6wDEscu0TbB Y9QQ== X-Gm-Message-State: ABy/qLaDBWgB5Xfez2s11UsirL97Hb0nxfPfAHRE1mvAjZGXjF4y6oIn bm3hFBykdcUwdGeMA+l7HtlZ/6HyP8ZBKYicw0gwDryE0UD+Zz0tvOqH39n20pryVgBdDOPDmHs uO7aYOROIPW9igx9NiLXutsk0c+ymCrBb5t9j9VUwBth4UtpioRXZ+V/tuZukvzNY2QwGD6lS8g E3 X-Google-Smtp-Source: APBJJlFJTNfgzdLrXLm/guh0YrliKW9HlX8PNeMrosHSf1zQAXg9MYtrQdTUJZnb6QkY+X8msTmVa7njthW3kwFJU1/K X-Received: from jonathantanmy0.svl.corp.google.com ([2620:15c:2d3:204:a487:6e54:d296:9521]) (user=jonathantanmy job=sendgmr) by 2002:a25:5016:0:b0:d15:fc00:fc69 with SMTP id e22-20020a255016000000b00d15fc00fc69mr95475ybb.9.1690915309595; Tue, 01 Aug 2023 11:41:49 -0700 (PDT) Date: Tue, 1 Aug 2023 11:41:36 -0700 In-Reply-To: Mime-Version: 1.0 References: X-Mailer: git-send-email 2.41.0.585.gd2178a4bd4-goog Message-ID: <3ce6090a4d3634b2e947d57f06714182207bb33a.1690912539.git.jonathantanmy@google.com> Subject: [PATCH v7 1/7] gitformat-commit-graph: describe version 2 of BDAT From: Jonathan Tan To: git@vger.kernel.org Cc: Jonathan Tan , Junio C Hamano , Taylor Blau Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org 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 --- 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 Tue Aug 1 18:41:37 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Tan X-Patchwork-Id: 13337172 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 5DE27C0015E for ; Tue, 1 Aug 2023 18:42:15 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231475AbjHASmO (ORCPT ); Tue, 1 Aug 2023 14:42:14 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:53282 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229486AbjHASmI (ORCPT ); Tue, 1 Aug 2023 14:42:08 -0400 Received: from mail-yb1-xb49.google.com (mail-yb1-xb49.google.com [IPv6:2607:f8b0:4864:20::b49]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id B134C2706 for ; Tue, 1 Aug 2023 11:41:52 -0700 (PDT) Received: by mail-yb1-xb49.google.com with SMTP id 3f1490d57ef6-d05883d850fso6839432276.3 for ; Tue, 01 Aug 2023 11:41:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1690915312; x=1691520112; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=9QnT3tTtabfqqxs9nL9AlnwZ/6fBBSjxJKX5ob4ntlw=; b=MXCuON6YdWNM8yHjUiiOKhxL5fONZdHAPWlNwVKbdUaovDTP/75s/2hNA+7gtiFcoU 99FQ5zr/9WYiQYEMSQdxx21jdkM6jXeKAL86dvGaJ3Gh2BDQztyKO/hwluRMRz2VpDVm EZ7ZgUBq+wxxOts+xchvNTmABxaH+menvnoU5AVbagAIipuEA92rRPRCl+b3UmHkjHnS UkRGUD6xFQLbjmAMsIDdW5dw006zGDxSMhG9/90JP8EMiv+6gNYDaTvBLN0XH80mYm/D nsqJEDekrBHuYMfBhxDyGQrv5DT/kWQqQcT2WMNWZfmbsOqOPUy3kwi9etTIbc4utU1+ Wz3Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690915312; x=1691520112; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=9QnT3tTtabfqqxs9nL9AlnwZ/6fBBSjxJKX5ob4ntlw=; b=gP/xRZx8JkaiX88fhGM+MvsgMGBVCtXohvlvzdH2ymkjJlJPE/DIsxYqQv0cuaV/IV Ex01tEdXOXabFXpLrUjKmS5QMv2g6TPKi7qvSolOvnKbMej1UTRwczgm5LO+r5fd7aH2 /Corhe1EWx8JpPGjWBlADANjjIoWYBl/L3Ppba2wZfeRYD40DwIPal3wr+VkLsMAuwaY HlJdCFtv2OnAiqaTKx7TMjPP4FzAR6WyvyYRxf4/oKbQNx99ipJB16LcdbyQdM9Cost2 hXZ6GMB7vTFNJLCGCosoXclU0ERq8qyRzlQjvIIJGI4Mw+aP1cOo4Wcv2yYOp6bjXdJi F/Sg== X-Gm-Message-State: ABy/qLbZSc4GEOqapsQgeev7Xd7EfO9zpEKJiNT9gzAh7HzvdmBVVqd8 Dj4ijyonKpUaTUxkTtXN8WYB5FeM34hLFRxrSh6rWU6/YFOK51dNvKzHsZ1qhmB12xoHAn/EUS2 YfkFN3ZgPc3+AF2L9pRToKpmtE3Oqq1cU+tANri54R/0LpCMT6KTm/ezgubpmiWt0epvNRbdRkk S7 X-Google-Smtp-Source: APBJJlHDC2BpDRN4qOdLEJczYIi5paOnvTTUOZ901B4TaHNOK9qJS7DXHQ9+fu5w7W2eKWiRmtohhnu7JxYMPkTmLcQs X-Received: from jonathantanmy0.svl.corp.google.com ([2620:15c:2d3:204:a487:6e54:d296:9521]) (user=jonathantanmy job=sendgmr) by 2002:a05:6902:1804:b0:d07:cb52:a3cf with SMTP id cf4-20020a056902180400b00d07cb52a3cfmr92800ybb.5.1690915311935; Tue, 01 Aug 2023 11:41:51 -0700 (PDT) Date: Tue, 1 Aug 2023 11:41:37 -0700 In-Reply-To: Mime-Version: 1.0 References: X-Mailer: git-send-email 2.41.0.585.gd2178a4bd4-goog Message-ID: Subject: [PATCH v7 2/7] t/helper/test-read-graph.c: extract `dump_graph_info()` From: Jonathan Tan To: git@vger.kernel.org Cc: Taylor Blau , Junio C Hamano , Jonathan Tan Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Taylor Blau 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 --- t/helper/test-read-graph.c | 33 ++++++++++++++++++++------------- 1 file changed, 20 insertions(+), 13 deletions(-) diff --git a/t/helper/test-read-graph.c b/t/helper/test-read-graph.c index 8c7a83f578..c664928412 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,8 +45,27 @@ 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); return 0; } + + From patchwork Tue Aug 1 18:41:38 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Tan X-Patchwork-Id: 13337173 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 8986CC00528 for ; Tue, 1 Aug 2023 18:42:16 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231320AbjHASmP (ORCPT ); Tue, 1 Aug 2023 14:42:15 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:53308 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231146AbjHASmJ (ORCPT ); Tue, 1 Aug 2023 14:42:09 -0400 Received: from mail-yw1-x1149.google.com (mail-yw1-x1149.google.com [IPv6:2607:f8b0:4864:20::1149]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 040D3CC for ; Tue, 1 Aug 2023 11:41:54 -0700 (PDT) Received: by mail-yw1-x1149.google.com with SMTP id 00721157ae682-583312344e7so74223387b3.1 for ; Tue, 01 Aug 2023 11:41:54 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1690915314; x=1691520114; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=W4FSASYFJjEH2RUXE2DEfQwMxTomYyPk0dT3J9KyV5I=; b=d+lxOt4IzX9Rzy+E1Sb/oLWoOr6Sxg2cytLM04WQRr9pLWZBT5c8+N9RU+7V+WnK/c EiwlyZ/+g7XbCCTkAtiOkBdp+axVT8L00Xg7JLznqCO+JhWIYzzq0m7lfywHZItDH9oP ROZWx9Wqfzuh5rtSiF4th6m0YL4XQr/Z+UYDCaZ3fzuVlTxYEHb5nRvbzE3akbpjOsqz mdXJIcnnu+xLrOZ0Vi7mnJG915EoRGSCI0D3PIRhNks3BkgZphemkRQIOrn1nKXhfNZH 0G3HnXlfzFSVVaw5hcsMZiKifPh7l8SyQI7IsNTfFZC71Llq6HXN7Re4Jh5sl4J0qyOD CE+Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690915314; x=1691520114; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=W4FSASYFJjEH2RUXE2DEfQwMxTomYyPk0dT3J9KyV5I=; b=C/IzZwkZVPu9JroOn6s4I+J/8Sz1UgbhlljJ9RD1d/hIB6+3SNXjYaSxxQKJbNDMdA Dfzfh+n0jeEVVW4o9RDwgXegBfqx19pSd1KQcr/j9WrWYFRSSf8aBSgdqoEs93IHG2BU YzG7T1m4Wb8gnCrnrAIOUTURB4eKNcMCR9/y0jTxx/Jsy3M3GKrae4Tr7LPHJaS2PKvY lRwv4wMIJB4RDMC0HEg7WtzXafmzFjlSrcevnQ9bq6znTqVBJzXYAfwGEh2HL5Qb7erD h958FEwTeGzANJC207q4h13AyPxj/UZLdxiMIxyBBPTGyDRnjmz+vzwFM39yI6q+uy6n C2rw== X-Gm-Message-State: ABy/qLaBhh0hBR69ToGjZUUAFBOKlXp5XcpqD4m3aJakPaOMgygPZIZR +0o2GtSbX+Gxg7iQdKxI+vwEhUqLJSH0wyNZrYN0poZT9w9t61oDu5lkLrcKCfpkIDwf1O9vADQ a8l8x/KO99imSh/12TLvU9rpDtz75RNgIi0ble7GQ18gAam65I/AKKgcb3nadrheASdD1bJzJGv c9 X-Google-Smtp-Source: APBJJlFY8qDNhDRRZbda942k0pEjxIbT8EvT2aP4cBushhNzquif/uKJY5FMFdaRQWM0lhfmaOV8hj28o5foBdmbw7Dh X-Received: from jonathantanmy0.svl.corp.google.com ([2620:15c:2d3:204:a487:6e54:d296:9521]) (user=jonathantanmy job=sendgmr) by 2002:a81:4007:0:b0:583:4551:858d with SMTP id l7-20020a814007000000b005834551858dmr120582ywn.9.1690915313974; Tue, 01 Aug 2023 11:41:53 -0700 (PDT) Date: Tue, 1 Aug 2023 11:41:38 -0700 In-Reply-To: Mime-Version: 1.0 References: X-Mailer: git-send-email 2.41.0.585.gd2178a4bd4-goog Message-ID: Subject: [PATCH v7 3/7] bloom.h: make `load_bloom_filter_from_graph()` public From: Jonathan Tan To: git@vger.kernel.org Cc: Taylor Blau , Junio C Hamano , Jonathan Tan Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Taylor Blau 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 --- 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 Tue Aug 1 18:41:39 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Tan X-Patchwork-Id: 13337175 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 80DE7C00528 for ; Tue, 1 Aug 2023 18:42:19 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231559AbjHASmR (ORCPT ); Tue, 1 Aug 2023 14:42:17 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:53416 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231145AbjHASmK (ORCPT ); Tue, 1 Aug 2023 14:42:10 -0400 Received: from mail-yw1-x114a.google.com (mail-yw1-x114a.google.com [IPv6:2607:f8b0:4864:20::114a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C7C3D268C for ; Tue, 1 Aug 2023 11:41:56 -0700 (PDT) Received: by mail-yw1-x114a.google.com with SMTP id 00721157ae682-5840614b107so73956277b3.1 for ; Tue, 01 Aug 2023 11:41:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1690915316; x=1691520116; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=G19IhzqNLSoxiby4b6EqQurINKTfQBn8xfgBlFyGsbE=; b=aUb46+mNjI6xGPtoKUMn5QDRFKGs4gShSj+NqplUuL9/NBwhK0vBR93GhUJ4ET+iol D2DdsYfeXWuyrb2stiCriu0JNbYLUyoOqKYInjVjmRPLV4PIB/crVAhHdYy/P59a1ua7 YWgsi9slExAdtbveQpd9WokUt6BOujOvfEo9ksu3+ViNT10epWoXwUv5zvQzY+GLJgmw p23Pok5o2D4QquwHxAW0xianGu/2pfdB+8rlEogoy1rJepyXWgHYVWEn6ozc159QPjLY UOY6tNvXYjR2+miH1i0cuHmraiMe02L0oKrPLj2lshiqm5zI2n9cSabOAO81vaVJk5ys MYcQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690915316; x=1691520116; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=G19IhzqNLSoxiby4b6EqQurINKTfQBn8xfgBlFyGsbE=; b=gxqSrF8rHkPOdyUueDrHdkpExJGIm8KRDfXRzgfCiUgXzxUtQmV8d4jh4TfeB+1kwN oaySU/1aHr6MtBsS4RyIlQ5FfBiSp/4WCpjtqW0ltZ6UzJpjv7RMShjGPiAUCkIt+p1z iZSm8h+1kOB04UCB5N586BuMnr13trL+xZQxWmuS+/2sWvvcfRrVaNrDpqAG2+uW70d/ a+mVQxONdZiPwKEnNZAwyMMJxovbR+6IEyBAVyR94FaL/SjSavXHwanWGLWv9c7ad7D5 cjmPGFNSFZWfLWXr8hEBgfDqjb/3c5Uhnpi83t2ow2ioVK9CFLsXmEbI3hQrY049iwSp N0AQ== X-Gm-Message-State: ABy/qLbxnKfRgzvqYwGm6qQq3TbJp0PkfjS/svY55ABddIGY4fglzdq+ 7AwzniCpaQCs3BsKIyukAJkRrJwlO0q7VaQRk9U1DkCusBNerVhMowBgvTQuDI8EKFxPOdJQtda skmub0HEWpaDplUULn1V2I56QaDypuoWpWWSuwPKxOTpwlvKTSAM2Jmhp1VkMqnZnn/rrhMBVZ2 JX X-Google-Smtp-Source: APBJJlGTDNZTR1gOLH4SdkCS+POap2nzSJXN8VyZPGaEY2XqTf4R29PwF55yLzbY6z8ruhV08EHG0wI+m2cirLJ6KpJC X-Received: from jonathantanmy0.svl.corp.google.com ([2620:15c:2d3:204:a487:6e54:d296:9521]) (user=jonathantanmy job=sendgmr) by 2002:a05:6902:564:b0:d0f:a0a6:8e87 with SMTP id a4-20020a056902056400b00d0fa0a68e87mr82972ybt.2.1690915315949; Tue, 01 Aug 2023 11:41:55 -0700 (PDT) Date: Tue, 1 Aug 2023 11:41:39 -0700 In-Reply-To: Mime-Version: 1.0 References: X-Mailer: git-send-email 2.41.0.585.gd2178a4bd4-goog Message-ID: <2ade832a230af797ed844947e5e7e90cdbc77c26.1690912539.git.jonathantanmy@google.com> Subject: [PATCH v7 4/7] t/helper/test-read-graph: implement `bloom-filters` mode From: Jonathan Tan To: git@vger.kernel.org Cc: Taylor Blau , Junio C Hamano , Jonathan Tan Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Taylor Blau 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 --- t/helper/test-read-graph.c | 42 +++++++++++++++++++++++++++++++++----- 1 file changed, 37 insertions(+), 5 deletions(-) diff --git a/t/helper/test-read-graph.c b/t/helper/test-read-graph.c index c664928412..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,14 +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 Tue Aug 1 18:41:40 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Tan X-Patchwork-Id: 13337176 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 39B24C0015E for ; Tue, 1 Aug 2023 18:42:21 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231569AbjHASmT (ORCPT ); Tue, 1 Aug 2023 14:42:19 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:53282 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230244AbjHASmK (ORCPT ); Tue, 1 Aug 2023 14:42:10 -0400 Received: from mail-yw1-x1149.google.com (mail-yw1-x1149.google.com [IPv6:2607:f8b0:4864:20::1149]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 336C2268E for ; Tue, 1 Aug 2023 11:41:59 -0700 (PDT) Received: by mail-yw1-x1149.google.com with SMTP id 00721157ae682-5840614b107so73956697b3.1 for ; Tue, 01 Aug 2023 11:41:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1690915318; x=1691520118; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=jaTeEzCxDKWERXQnRcvwGtGl2veNkFFfZk1CxIXl99Q=; b=kLvOlM8M3T1wKyKeL/dz6l7JpTCI1P4+sRN8jyNkZKsSFsv9nEHXO+3YhffxVYZdzy A/ZaQbSph9H3L8QRcE0ZxRv7mDj104lKrmSXmHuG75pyXs8cc/8khU/uPGWAZemcu70u eV+yxOntydtjLRWwSjSwucMr6dzORAz29FU16ZyhB7Jf6EwkL7JIotkAHaWguJ1HZSq1 Pp+7VvzOhzDscbd+MbsTDNPqH7q4DleI+c4X9hrNNMd1UNFUJcaH/HJnXrURV6R5aE2G typgV0Z2IsBACw0owNzQrvxTCEcUbJA9oJK/dvwNt5c5swAwBERocVb3qbxKhAh14BcI eElA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690915318; x=1691520118; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=jaTeEzCxDKWERXQnRcvwGtGl2veNkFFfZk1CxIXl99Q=; b=aHzGIG0XadHfRASJ+RprNkT+6tgYQXXyqYfWFr9G6jJ1pvZGMRvYldFVsYLvb7gieS jKvUD4oVnZ55Duu5Liz24T/IfTDOvx7j76jfGMltY1Q2TEQgH350bNzzHLKXOUpuaeO0 W+r86KfFpJatsnjoxDrog5WPcAf2vdLJzI7Sj7asQ7U9X66pz3oj04y/+9ZIVni5lHDv sceeS7YPNYsqmzy5t3iCgy+88FgGQBTL9iqvkWoupa5F7BncXgpHAUaVMd2Q80HQk4EY JtfRlXgm0ICLiaSTGTUaWhc1guaX6+j5p6KovnL0qLtuZ5aZn/oPSKd4hhveLYvyNvEQ +8pg== X-Gm-Message-State: ABy/qLbNDaFVRVPF/QOv3PG/GxeyEG1ddPZ4RSUhhTBHkLieMJ00de0b okRzbhtUm553aG7QDNtg9vF6yqp7Xjj9FHRZn0xjbhRnmtBICDz4CF6VHPkjmWVCb8IdkLkU5Xn MPMupes2JlDoS61C7D9SSeFvbXA5X3U4nikxZpZ8/NNq4eJCYiCGswPG6H5nI7O1bpWYO0GhxR9 9N X-Google-Smtp-Source: APBJJlEY3rawT5LcYPGKVn57aTUqpRGP8FecQxOCaBMpCeSXfuFt9yAmMHy3fxKoOk2dg2cxAdZNaGFEk6amRJA/5EYH X-Received: from jonathantanmy0.svl.corp.google.com ([2620:15c:2d3:204:a487:6e54:d296:9521]) (user=jonathantanmy job=sendgmr) by 2002:a81:d008:0:b0:57a:e0b:f63 with SMTP id v8-20020a81d008000000b0057a0e0b0f63mr113947ywi.7.1690915318044; Tue, 01 Aug 2023 11:41:58 -0700 (PDT) Date: Tue, 1 Aug 2023 11:41:40 -0700 In-Reply-To: Mime-Version: 1.0 References: X-Mailer: git-send-email 2.41.0.585.gd2178a4bd4-goog Message-ID: <74863c11e59c6dbf3673507b58e7c841162d3d18.1690912539.git.jonathantanmy@google.com> Subject: [PATCH v7 5/7] t4216: test changed path filters with high bit paths From: Jonathan Tan To: git@vger.kernel.org Cc: Jonathan Tan , Junio C Hamano , Taylor Blau Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org 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 --- 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 Tue Aug 1 18:41:41 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Tan X-Patchwork-Id: 13337177 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 0C166C00528 for ; Tue, 1 Aug 2023 18:42:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231583AbjHASmV (ORCPT ); Tue, 1 Aug 2023 14:42:21 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:53284 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231351AbjHASmM (ORCPT ); Tue, 1 Aug 2023 14:42:12 -0400 Received: from mail-yw1-x1149.google.com (mail-yw1-x1149.google.com [IPv6:2607:f8b0:4864:20::1149]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 015352690 for ; Tue, 1 Aug 2023 11:42:00 -0700 (PDT) Received: by mail-yw1-x1149.google.com with SMTP id 00721157ae682-5704995f964so71511967b3.2 for ; Tue, 01 Aug 2023 11:42:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1690915320; x=1691520120; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=m62EFluf3rrteAkRTvi8Wb5maZSXv4vILhSfCu3DXRU=; b=jd195zbwjqPQV1ol/yvluUAQUF7ik3gzpQ0Q2D3ulig+lOzDYIVudGJO29u7/MY1W0 YrCVRg8edHh/0mUXMhyT1Nzkb0RHeS06oEssBMKp2iDNbPPCgExjWkCeUKbzsl6AI01G Z3oz3k2Y3kqr9e2mKWHeOC9yyj4iFXYw33OtrnNfW1FR/xkj7+MAqrhTkLENKhGa+8vA g/wviT6pGqc0aLJbEfK0pgtiM94wDk65Q7+5Kxh7POCsBSw1xGL5M7j04W8cpVqoXd+q N1weV7heB6RA7o9ULEeN3eGH4wpboq0aphAjq1ba1E1cK5F8Pc6Bc5Kv91AFkLGgkhy0 C1DQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690915320; x=1691520120; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=m62EFluf3rrteAkRTvi8Wb5maZSXv4vILhSfCu3DXRU=; b=YHkf9jbHByvpJlbSyV7dPuby+meRU2b72x0Qz3M2pRYKFf8K0mnZyg4/3JwDs5F4qT 984nYespEmg8dGnpp4pWocJQ8MbRyW/uIpj7IWQP03RJSFWsg/3st9lu+T89O8FP3Hzj 79AOVKea+tUAgIcXgjqwM48dvJ2V4OL7ZE27n/7FMROwGoOXG+ZntAx8kMqUVQpn7PCt 4549iAYYQlQxkus+jTJ0sSRl45wDdnZPAdJ+swgi17+zLmL9zRJulzzBkx8GM0niyrQj mYpwsEcNPvz0EfqqWoYOHol1LupxbIEVmjJ86tOvZORxTw5AhZgZPYJO9lJOShMx5R4E 8qFA== X-Gm-Message-State: ABy/qLY12X6Ly+VRnj4UT+qq145iyct9on2mkif/aAZ6r6jwN0I5Udlv FDMP/PXUvrBSVSHyyOP2UqPAyJYVTyjqTWBc6M13kQw8hiy+SoGUPfmlJma9b/QQWyuvy+c96+7 +KOpUGt9Lnk6mPo4TZi9Ntj+/5tYp4UoxhaDAM5Vkem3VW+B3nfm251+lF/QxAs9CvckjmTEg/z Z6 X-Google-Smtp-Source: APBJJlG/To7UZ+Ei6hu9WejucXIwCgiDN+NuN+/NH7e1mx8ALCu4eiw48tE5e8EpyaZ+16bSVYw7M6L2akNDYhIxyESl X-Received: from jonathantanmy0.svl.corp.google.com ([2620:15c:2d3:204:a487:6e54:d296:9521]) (user=jonathantanmy job=sendgmr) by 2002:a81:af0d:0:b0:57a:793:7fb0 with SMTP id n13-20020a81af0d000000b0057a07937fb0mr119385ywh.3.1690915320264; Tue, 01 Aug 2023 11:42:00 -0700 (PDT) Date: Tue, 1 Aug 2023 11:41:41 -0700 In-Reply-To: Mime-Version: 1.0 References: X-Mailer: git-send-email 2.41.0.585.gd2178a4bd4-goog Message-ID: <60f4faeff9e3c53c69acc85f033c33c1be632400.1690912539.git.jonathantanmy@google.com> Subject: [PATCH v7 6/7] repo-settings: introduce commitgraph.changedPathsVersion From: Jonathan Tan To: git@vger.kernel.org Cc: Jonathan Tan , Junio C Hamano , Taylor Blau Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org 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 --- 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 efc697e437..1f26c07de4 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 Tue Aug 1 18:41:42 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Tan X-Patchwork-Id: 13337178 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 2ED15C0015E for ; Tue, 1 Aug 2023 18:42:35 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231734AbjHASmd (ORCPT ); Tue, 1 Aug 2023 14:42:33 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:53526 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231459AbjHASmN (ORCPT ); Tue, 1 Aug 2023 14:42:13 -0400 Received: from mail-yw1-x1149.google.com (mail-yw1-x1149.google.com [IPv6:2607:f8b0:4864:20::1149]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id AE63026A1 for ; Tue, 1 Aug 2023 11:42:03 -0700 (PDT) Received: by mail-yw1-x1149.google.com with SMTP id 00721157ae682-5840614b107so73957647b3.1 for ; Tue, 01 Aug 2023 11:42:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1690915323; x=1691520123; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=WRQi1iWDRPg0prY3v/oRheOaiWkRZ8Tvx1zvoc0l4i0=; b=5aq2FyHax7l71IPQign2GBmm9ju+OMaE7YqVTDyo+5fYYE2DVDRVWlJrM6v0W8RZLr mO1aIYtfixXcQgENFX9v4WirJEaSe0OCAz8clVsOO9EYnDbiGQ9/KSzigFHSp0r8/u0c h5HYRu9ENeWJZnbAZPiIOst2vG9Sx/tJpeJbzhy4yanvher1O16Z2Q9hkmm3ukbruBW0 oKIei/AUyD8kcm+PESETsc3LKFOZLY2GKLIuNJcRiMmUc/kFTM8m3XkUExpCit5ojXtw PS9yKJYv2kbGtg8ouW8PsEs+EQo5B1qaH9JQu0fX+ZNRRKR/duGIm1ou9Vrbdqu2YVG0 sbUQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690915323; x=1691520123; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=WRQi1iWDRPg0prY3v/oRheOaiWkRZ8Tvx1zvoc0l4i0=; b=R4ZEZt4zEc2pqHHb1pPHVdOxnUh3mubGXIwpToZHX+1ltgIEXDHzTULpLrlXAiJPCG kxAuWKvsINx/5yRF+g4ur5jrP8+h41k4Wv526I8AeS2pWdaNMOpPshbYphJrxd0ZRy9T sqpdBrPuMtCB+Jefi7ySX5LUaLSIPuxLVkW45RVhcgqeMwMWzQRmXAnmTo+rCAJaa4+g rmA42FSmN5Hi3kyGEZfpgC7wpQz44boRmLeG72mzPFU+VOAAr+v4yKrzGGvbpdDCHfdo ilYBAn7w0exJpADJhHH/2U5/RWWiKxht1l7vLdlnm775Fcezps1AAt6nc2sdtmQNyHny hsTw== X-Gm-Message-State: ABy/qLbUrt330Z7pas/Lj7GhxbU+BwhwC8Ei+qrS+lLDN4rKdv0U7h0q nwHN+LBLCBsLla7lov+XNfsrKL5TFwINj6n/5alMEgMtMDTHIo9bOE/ZOVG/U/nFNdwJWkqV24k 0ig80vucrJZBrb2huEz1aJJp6OQ6SycMoqprogB28Bby8GIls2HS9hoZWQNq+Fzd3X89MGWN4GT W7 X-Google-Smtp-Source: APBJJlGGyTGLTKF8rLJDTG6ILsHrmYzUAYNOrenbQJsmp5oE5vI5KlT7MCHDC7VpzdD6Ii8nyAPNATGJHU+KPyN1TWL8 X-Received: from jonathantanmy0.svl.corp.google.com ([2620:15c:2d3:204:a487:6e54:d296:9521]) (user=jonathantanmy job=sendgmr) by 2002:a05:690c:708:b0:583:96da:32dd with SMTP id bs8-20020a05690c070800b0058396da32ddmr130750ywb.0.1690915322431; Tue, 01 Aug 2023 11:42:02 -0700 (PDT) Date: Tue, 1 Aug 2023 11:41:42 -0700 In-Reply-To: Mime-Version: 1.0 References: X-Mailer: git-send-email 2.41.0.585.gd2178a4bd4-goog Message-ID: <68258cfd04cee93d1a1a5bfce674f299dd070b84.1690912539.git.jonathantanmy@google.com> Subject: [PATCH v7 7/7] commit-graph: new filter ver. that fixes murmur3 From: Jonathan Tan To: git@vger.kernel.org Cc: Jonathan Tan , Junio C Hamano , Taylor Blau Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org 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 --- Documentation/config/commitgraph.txt | 5 +- bloom.c | 69 +++++++++++++++++++- bloom.h | 8 ++- commit-graph.c | 33 ++++++++-- t/helper/test-bloom.c | 9 ++- t/t0095-bloom.sh | 8 +++ t/t4216-log-bloom.sh | 96 ++++++++++++++++++++++++++++ 7 files changed, 214 insertions(+), 14 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 1f26c07de4..ffbc86151e 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) - return 0; + 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) { @@ -2371,6 +2384,14 @@ int write_commit_graph(struct object_directory *odb, ctx->write_generation_data = (get_configured_generation_version(r) == 2); ctx->num_generation_data_overflows = 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; + } + 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", @@ -2400,7 +2421,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