From patchwork Fri Jun 10 10:54:39 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Abhradeep Chakraborty X-Patchwork-Id: 12877413 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 58792C433EF for ; Fri, 10 Jun 2022 10:57:28 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1344629AbiFJK50 (ORCPT ); Fri, 10 Jun 2022 06:57:26 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56690 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1348781AbiFJK5D (ORCPT ); Fri, 10 Jun 2022 06:57:03 -0400 Received: from mail-wr1-x431.google.com (mail-wr1-x431.google.com [IPv6:2a00:1450:4864:20::431]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 63B5327936B for ; Fri, 10 Jun 2022 03:54:46 -0700 (PDT) Received: by mail-wr1-x431.google.com with SMTP id v14so9747179wra.5 for ; Fri, 10 Jun 2022 03:54:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=E6bKO0VsQQCQlvKxYxRlprN8bVF9guaXMMN/6yBgq20=; b=da4VSliphGRTCrRB4nhb4f9wqi6CPOvCZ7kXMB6o7jXTGW9vY8WZO3Ay/dfDSumqKo fZoRPk+8OM/4EEIOLpT7Xvp3A3mUEaDrg5C/D4CY7tfBegtTyVwS2v9be25wSt2MUAbL kDpLMwxjz1KVx6J4xzIIRyspavb3kcWkILz+90x21PLzAeDiNtamjPV597GKFroNCen3 +ReE3X4tsl4BrHa4zWGXKpntEY6Z7hcE3b87ygRkxSPn/BEWdQ+/2UtXG8xlK2PVpojN mNOWdlyiMzbOnsZgmoLGd03e7Xew5R+TCWHfcNWKTRX0CHD0vInXk6/NfXzWl6v0hqaN Y57Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=E6bKO0VsQQCQlvKxYxRlprN8bVF9guaXMMN/6yBgq20=; b=PvkAOjXznoUBJq+7EHpU4w0+uC9xVB57D2i2AONoAUomgCXDt9K8dh/md6PiNCqNIL xFb5XfmSHI0BqcEJD52xfgb6eHlWchV/JRiFtn9HZfYif+EIlOqHGOi16DCabi4/wYRg qXKTXhK8nGp+ycZxDpHDPsbmykVkI676R2AEBRKHGQLOzwC1yW8S8TWfpXmnWrBG0APK Kpv6KLAtPLdQrvqcTRK+yvR/0R/AjM5cnyLjcNSQpUvd9bVebugwPS1sC7eL5z2eCMpw YY7lMTvePYgxh66vOsUh3/o6rGHHr18vUd4uoDVZUMppFdGjmBZJ2Y408CKxc1ij3747 hNmQ== X-Gm-Message-State: AOAM532XPvpM/6D5xpxlWe5ckiGW05Ck/Vy/d5SS7JufeUd9R513D1BC StNhg4z2dJQrF8byxRqZFP8k6X7vPObjug== X-Google-Smtp-Source: ABdhPJwVSHfBn0kEn2yyxMhyTkfJvdtlfBcJj7XesnonwWcx928PWsUJUv5HfsWP6kGHYuiSowEg3w== X-Received: by 2002:adf:fb82:0:b0:219:af0c:489a with SMTP id a2-20020adffb82000000b00219af0c489amr9887020wrr.212.1654858484364; Fri, 10 Jun 2022 03:54:44 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id h62-20020a1c2141000000b0039c151298b7sm2712976wmh.10.2022.06.10.03.54.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 10 Jun 2022 03:54:43 -0700 (PDT) Message-Id: In-Reply-To: References: Date: Fri, 10 Jun 2022 10:54:39 +0000 Subject: [PATCH v3 1/3] bitmap-format.txt: feed the file to asciidoc to generate html Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Taylor Blau , Kaartic Sivaraam , Derrick Stolee , Junio C Hamano , Abhradeep Chakraborty , Abhradeep Chakraborty Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Abhradeep Chakraborty From: Abhradeep Chakraborty Documentation/Makefile does not include bitmap-format.txt to generate a html page using asciidoc. Teach Documentation/Makefile to also generate a html page for Documentation/technical/bitmap-format.txt file. Signed-off-by: Abhradeep Chakraborty --- Documentation/Makefile | 1 + 1 file changed, 1 insertion(+) diff --git a/Documentation/Makefile b/Documentation/Makefile index d3f043f50d2..8d405a14330 100644 --- a/Documentation/Makefile +++ b/Documentation/Makefile @@ -94,6 +94,7 @@ TECH_DOCS += MyFirstContribution TECH_DOCS += MyFirstObjectWalk TECH_DOCS += SubmittingPatches TECH_DOCS += ToolsForGit +TECH_DOCS += technical/bitmap-format TECH_DOCS += technical/bundle-format TECH_DOCS += technical/hash-function-transition TECH_DOCS += technical/http-protocol From patchwork Fri Jun 10 10:54:40 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Abhradeep Chakraborty X-Patchwork-Id: 12877414 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 7F267C43334 for ; Fri, 10 Jun 2022 10:57:34 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1349138AbiFJK5d (ORCPT ); Fri, 10 Jun 2022 06:57:33 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57322 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1349082AbiFJK5F (ORCPT ); Fri, 10 Jun 2022 06:57:05 -0400 Received: from mail-wm1-x329.google.com (mail-wm1-x329.google.com [IPv6:2a00:1450:4864:20::329]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 025C72A11CA for ; Fri, 10 Jun 2022 03:54:47 -0700 (PDT) Received: by mail-wm1-x329.google.com with SMTP id m32-20020a05600c3b2000b0039756bb41f2so882527wms.3 for ; Fri, 10 Jun 2022 03:54:47 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=Vkyqhm02plQIka8kb3KvivKLbR/KycQGuGJMTJlOrKM=; b=Q5erlb5HD0uBh3pp6FraEh/5+qqIf2caQYsWwAPFRPaCt2uiVVXTqQM4KdZFLMIEDL sy77pP1jhItIuaKpKNcrLpTgSWI/Z8El3T4MhlelygB6mWfVSA2ZQPMXSwwHCxlDE6mU kf8nalUAbcXajRQ/7J/FilbbU9p5YIiWZiWIrUXjw0/QnfnGvYg7ikuFqk8NaUcSKKFs CYMDSuYIPbPvFC74dXUPgSBLdWx+dzqgF9lZDYEtzxAlUh3TFT2XOnWF5QXvJVRskDVo ++qnu000yu+yyRfrDo+uDx1vtUBfzz9Hz4AO2MJhvDom3XQffTZEBaH9NXSwbcBV8NfK AxSQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=Vkyqhm02plQIka8kb3KvivKLbR/KycQGuGJMTJlOrKM=; b=ehEc2j2qyPKQRg4F4Q8r1iswySd2KT0c1XJQQaV8nErnc2bJdNrih2z9E/oichi31p Cmhd8iaoG3ZBoHK/O4YXI3tuazxg/Q4/Ww6d2osSEnv00eML5C7GChzZMWnTQvE0YjbA Th1kARXWQfJK+bIOJV6+AvsTuzcUXDkrpPamOTgRPjiqzNxFEpMzUlcNCO6EKJMBUtKG W+wX2iph5nwNg/P8YeZCQeKg90xkR4UXYrPGz+vefr6jgx5roxUwqpcJn1pzfhic+dcN 98kFxJpWw4RVPbce0nUwQQRifoRVj1/wqWxi3NWMxoXTWUw05hE5GWri9MBVTCQlFMQv Ittw== X-Gm-Message-State: AOAM533Nc3f5np1XjGeDutMBxLkV8GshPxYY8nf4kAPBjCdjByYKbG6A ecj4lDRGjk6BWjqobZtRtezHpipjYVm+Zg== X-Google-Smtp-Source: ABdhPJwrn7S0XAJE5JYYrYeYSuMr5RAAE1J/O2QYfKrtH3Xbq2KHcnemPnkEcDH9V7YpbO1L/3HlIQ== X-Received: by 2002:a05:600c:4f96:b0:39c:7bd0:d4c8 with SMTP id n22-20020a05600c4f9600b0039c7bd0d4c8mr3506990wmq.16.1654858485779; Fri, 10 Jun 2022 03:54:45 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id d14-20020a5d6dce000000b0020c5253d927sm27309015wrz.115.2022.06.10.03.54.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 10 Jun 2022 03:54:44 -0700 (PDT) Message-Id: In-Reply-To: References: Date: Fri, 10 Jun 2022 10:54:40 +0000 Subject: [PATCH v3 2/3] bitmap-format.txt: fix some formatting issues Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Taylor Blau , Kaartic Sivaraam , Derrick Stolee , Junio C Hamano , Abhradeep Chakraborty , Abhradeep Chakraborty Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Abhradeep Chakraborty From: Abhradeep Chakraborty The asciidoc generated html for `Documentation/technical/bitmap- format.txt` is broken. This is mainly because `-` is used for nested lists (which is not allowed in asciidoc) instead of `*`. Fix these and also reformat it for better readability of the html page. Signed-off-by: Abhradeep Chakraborty --- Documentation/technical/bitmap-format.txt | 109 ++++++++++++---------- 1 file changed, 58 insertions(+), 51 deletions(-) diff --git a/Documentation/technical/bitmap-format.txt b/Documentation/technical/bitmap-format.txt index 04b3ec21785..cd621379f42 100644 --- a/Documentation/technical/bitmap-format.txt +++ b/Documentation/technical/bitmap-format.txt @@ -39,19 +39,22 @@ MIDXs, both the bit-cache and rev-cache extensions are required. == On-disk format - - A header appears at the beginning: + * A header appears at the beginning: - 4-byte signature: {'B', 'I', 'T', 'M'} + 4-byte signature: :: {'B', 'I', 'T', 'M'} + + 2-byte version number (network byte order): :: - 2-byte version number (network byte order) The current implementation only supports version 1 of the bitmap index (the same one as JGit). - 2-byte flags (network byte order) + 2-byte flags (network byte order): :: The following flags are supported: - - BITMAP_OPT_FULL_DAG (0x1) REQUIRED + ** {empty} + BITMAP_OPT_FULL_DAG (0x1) REQUIRED: ::: + This flag must always be present. It implies that the bitmap index has been generated for a packfile or multi-pack index (MIDX) with full closure (i.e. where @@ -61,75 +64,79 @@ MIDXs, both the bit-cache and rev-cache extensions are required. JGit, that greatly reduces the complexity of the implementation. - - BITMAP_OPT_HASH_CACHE (0x4) + ** {empty} + BITMAP_OPT_HASH_CACHE (0x4): ::: + If present, the end of the bitmap file contains `N` 32-bit name-hash values, one per object in the pack/MIDX. The format and meaning of the name-hash is described below. - 4-byte entry count (network byte order) - + 4-byte entry count (network byte order): :: The total count of entries (bitmapped commits) in this bitmap index. - 20-byte checksum - + 20-byte checksum: :: The SHA1 checksum of the pack/MIDX this bitmap index belongs to. - - 4 EWAH bitmaps that act as type indexes - - Type indexes are serialized after the hash cache in the shape - of four EWAH bitmaps stored consecutively (see Appendix A for - the serialization format of an EWAH bitmap). - - There is a bitmap for each Git object type, stored in the following - order: - - - Commits - - Trees - - Blobs - - Tags - - In each bitmap, the `n`th bit is set to true if the `n`th object - in the packfile or multi-pack index is of that type. - - The obvious consequence is that the OR of all 4 bitmaps will result - in a full set (all bits set), and the AND of all 4 bitmaps will - result in an empty bitmap (no bits set). - - - N entries with compressed bitmaps, one for each indexed commit - - Where `N` is the total amount of entries in this bitmap index. - Each entry contains the following: - - - 4-byte object position (network byte order) + * 4 EWAH bitmaps that act as type indexes ++ +Type indexes are serialized after the hash cache in the shape +of four EWAH bitmaps stored consecutively (see Appendix A for +the serialization format of an EWAH bitmap). ++ +There is a bitmap for each Git object type, stored in the following +order: ++ + - Commits + - Trees + - Blobs + - Tags + ++ +In each bitmap, the `n`th bit is set to true if the `n`th object +in the packfile or multi-pack index is of that type. + + The obvious consequence is that the OR of all 4 bitmaps will result + in a full set (all bits set), and the AND of all 4 bitmaps will + result in an empty bitmap (no bits set). + + * N entries with compressed bitmaps, one for each indexed commit ++ +Where `N` is the total amount of entries in this bitmap index. +Each entry contains the following: + + ** {empty} + 4-byte object position (network byte order): :: The position **in the index for the packfile or multi-pack index** where the bitmap for this commit is found. - - 1-byte XOR-offset + ** {empty} + 1-byte XOR-offset: :: The xor offset used to compress this bitmap. For an entry in position `x`, a XOR offset of `y` means that the actual bitmap representing this commit is composed by XORing the bitmap for this entry with the bitmap in entry `x-y` (i.e. the bitmap `y` entries before this one). - - Note that this compression can be recursive. In order to - XOR this entry with a previous one, the previous entry needs - to be decompressed first, and so on. - - The hard-limit for this offset is 160 (an entry can only be - xor'ed against one of the 160 entries preceding it). This - number is always positive, and hence entries are always xor'ed - with **previous** bitmaps, not bitmaps that will come afterwards - in the index. - - - 1-byte flags for this bitmap ++ +NOTE: This compression can be recursive. In order to +XOR this entry with a previous one, the previous entry needs +to be decompressed first, and so on. ++ +The hard-limit for this offset is 160 (an entry can only be +xor'ed against one of the 160 entries preceding it). This +number is always positive, and hence entries are always xor'ed +with **previous** bitmaps, not bitmaps that will come afterwards +in the index. + + ** {empty} + 1-byte flags for this bitmap: :: At the moment the only available flag is `0x1`, which hints that this bitmap can be re-used when rebuilding bitmap indexes for the repository. - - The compressed bitmap itself, see Appendix A. + ** The compressed bitmap itself, see Appendix A. == Appendix A: Serialization format for an EWAH bitmap From patchwork Fri Jun 10 10:54:41 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Abhradeep Chakraborty X-Patchwork-Id: 12877415 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 62CEBC43334 for ; Fri, 10 Jun 2022 10:57:38 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1349344AbiFJK5f (ORCPT ); Fri, 10 Jun 2022 06:57:35 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57478 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1349139AbiFJK5M (ORCPT ); Fri, 10 Jun 2022 06:57:12 -0400 Received: from mail-wr1-x432.google.com (mail-wr1-x432.google.com [IPv6:2a00:1450:4864:20::432]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 04BD52ADF59 for ; Fri, 10 Jun 2022 03:54:49 -0700 (PDT) Received: by mail-wr1-x432.google.com with SMTP id x17so36002550wrg.6 for ; Fri, 10 Jun 2022 03:54:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=6NpiRs80V4EyAWLcIpjoCUBwX8WrfETnmq1wjdFiWl4=; b=SBR0Haaz5Bgse9QZBmYpCnJ5zUhUWhFvmGaIgHL3wA5HDBkTYlmR/st7uk/sRU8Prv gYqKNE5EIW8bDatA2WpwxL6gUMrH0dCxPGT7efY+kZLAbvL3SgBmS5k7akz8Q4aKbrpp UJqUrGrvaI8qPpoTccLTLKEt8XzAD6eqeN0boKGMtaj4sNwUPI+Bbe17lzPO2/TmcBVo BZW4AzrpFVJV1zOs+Wm6HEiZXqg8Mw0QkBtBskF8cKz2RFFpTJO1f6wYShW2354EkDXh uyvZoA2HVhDpNNQFnhyoICwk09qb0wg/uvms5dubpvL9CMMZ/RMefli+E5i3InufjaEl QHpw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=6NpiRs80V4EyAWLcIpjoCUBwX8WrfETnmq1wjdFiWl4=; b=m0VCJfHO7bMW+UE6s+Dq6TpDFsSV8NJwkDpGtCkH1Cik9ZoO5UlCaM0g6H5vtRK02G Nwzd/61gCHFmvdX/Nyp7RyMzDNsDBYIZlGNaUTLqxI+IAyLvqc/PhIUn0QKdQoy4BX8r dQCpuicKYqZREDfKAbdTyQCpdUwT9dWzJso2SbICwpX9JR5/SZzRWqVTrJ+Su7r9xR61 sRgSvoWCv/+klKmrWvNoH1siielJejYOFugMH52dEAkL9vsNVjgXtWMctlHmA9nxw/I5 iSspLykclszguBtbtNja6g81zArw5qpiQXyYPjV1I4sC5nNUK6+N7x0TahvXdKrtMVuE ouNA== X-Gm-Message-State: AOAM5324QrQ0whkvjUH4IEy+y4Gr163ICPfmY5Rl51K6kwMdUqVmirzl r4TV+eza1aQUoTuCRIF9bYoIk7QF8fivhw== X-Google-Smtp-Source: ABdhPJyfdiZ1uerh7yHPdOr1VA3pO+WCjZZ4ilNm/fY4ISKnWOqcEnbizzyYJxLdsVakB6kW9qt9FQ== X-Received: by 2002:a5d:6487:0:b0:218:35ed:d4ea with SMTP id o7-20020a5d6487000000b0021835edd4eamr28938373wri.344.1654858487127; Fri, 10 Jun 2022 03:54:47 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id h12-20020a05600c2cac00b003942a244f40sm2717851wmc.25.2022.06.10.03.54.45 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 10 Jun 2022 03:54:46 -0700 (PDT) Message-Id: In-Reply-To: References: Date: Fri, 10 Jun 2022 10:54:41 +0000 Subject: [PATCH v3 3/3] bitmap-format.txt: add information for trailing checksum Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Taylor Blau , Kaartic Sivaraam , Derrick Stolee , Junio C Hamano , Abhradeep Chakraborty , Abhradeep Chakraborty Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Abhradeep Chakraborty From: Abhradeep Chakraborty Bitmap file has a trailing checksum at the end of the file. However there is no information in the bitmap-format documentation about it. Add a trailer section to include the trailing checksum info in the `Documentation/technical/bitmap-format.txt` file. Signed-off-by: Abhradeep Chakraborty --- Documentation/technical/bitmap-format.txt | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/Documentation/technical/bitmap-format.txt b/Documentation/technical/bitmap-format.txt index cd621379f42..3f8cdd0ed91 100644 --- a/Documentation/technical/bitmap-format.txt +++ b/Documentation/technical/bitmap-format.txt @@ -138,6 +138,10 @@ in the index. ** The compressed bitmap itself, see Appendix A. + * {empty} + TRAILER: :: + Trailing checksum of the preceding contents. + == Appendix A: Serialization format for an EWAH bitmap Ewah bitmaps are serialized in the same protocol as the JAVAEWAH