From patchwork Wed Feb 26 08:49:41 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Linus Arver via GitGitGadget X-Patchwork-Id: 11405585 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 63255924 for ; Wed, 26 Feb 2020 08:49:54 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 41E0A206E6 for ; Wed, 26 Feb 2020 08:49:54 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="QHuhrmTF" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726679AbgBZItv (ORCPT ); Wed, 26 Feb 2020 03:49:51 -0500 Received: from mail-ed1-f65.google.com ([209.85.208.65]:37847 "EHLO mail-ed1-f65.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725872AbgBZItv (ORCPT ); Wed, 26 Feb 2020 03:49:51 -0500 Received: by mail-ed1-f65.google.com with SMTP id t7so2799776edr.4 for ; Wed, 26 Feb 2020 00:49:50 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=NfPWVYm5oJnAy6N3ND7qYx88WtkIig5hT6uesdXdV6c=; b=QHuhrmTFrQ884Sw/bdjOL8YJLE7cKCyRDpueat0kw29RPoPRskGC8ZVDOnRCMNBn89 kfl2hNbIHMDF9m/Zg46ILlV4Y5CfExJtMAfhJSkKDBubXH2S4zDlTOFYbpSSy/vcKe4U m+HakXKnzPpXLKcW1dHOMAOeKnK02EZysoG5ebh+uZzvzIFW64hqxOk7NHilfXphMTA9 oR2o5wsOkZzKtP5Q2KIg3Ed+ipEmIW0qdLSFblxsMv6iv1bL7jK2VtG1BwncyE7Yy2TI dTQ0VgHRu9qE9fIsScMqbL16z/yh7SBw9Ba3Wj5IrmeZHzQOiDn0KDaIvaFCISYOG05H 8hoQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=NfPWVYm5oJnAy6N3ND7qYx88WtkIig5hT6uesdXdV6c=; b=X0Tilm0sLRB61rQGS7lK3Sh8nSzMMxGomO6cjkTbC6qv59ZavO3HmlpH0uLLwfMmD2 ooXz8Jgl0ALuDWEKfhlICfEEOrF4HOvRaE0wAaJHmv4agdaAnrbapIdtnOAqGKwv+3WK weubiiNMw1RU+Zyy8pXkDf7HgRxONQ8PzRfxKgdi1srlGFinax9aOCb8p1dAPzRLJNgk 9I/1gLE565ienGpt5eWHmbeTnnkCtCVfPIxp44HFpNzrj6zG1WvGkmfpfGjS8ZIAtxQF yYass/SI13sJdgVB8fHwBe72uVg0lagL6rphqV15aIh7S0SvNH0Fk87U6rD6FdcBMxlo c0Iw== X-Gm-Message-State: APjAAAUr7QVv8gWPci0VWUVoDjvGH8K+ND20sQHuIKQBsnDyFUnNfZy5 g8Rg0Pa9cUxXP038jcW3/OnZ0rVK X-Google-Smtp-Source: APXvYqxG7w944afpLosWVcOiU0ZagHijS5P/zAGThBDJnRfaYafTAEkBfymOwCERmJpfjtc19xQA1A== X-Received: by 2002:aa7:c68f:: with SMTP id n15mr3574720edq.112.1582706989282; Wed, 26 Feb 2020 00:49:49 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id be18sm57012edb.19.2020.02.26.00.49.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Feb 2020 00:49:48 -0800 (PST) Message-Id: In-Reply-To: References: From: "Han-Wen Nienhuys via GitGitGadget" Date: Wed, 26 Feb 2020 08:49:41 +0000 Subject: [PATCH v7 1/6] refs.h: clarify reflog iteration order Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Han-Wen Nienhuys , Han-Wen Nienhuys Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Han-Wen Nienhuys Signed-off-by: Han-Wen Nienhuys --- refs.h | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) diff --git a/refs.h b/refs.h index 545029c6d80..87c9ec921b9 100644 --- a/refs.h +++ b/refs.h @@ -444,18 +444,21 @@ int delete_refs(const char *msg, struct string_list *refnames, int refs_delete_reflog(struct ref_store *refs, const char *refname); int delete_reflog(const char *refname); -/* iterate over reflog entries */ +/* Iterate over reflog entries. */ typedef int each_reflog_ent_fn( struct object_id *old_oid, struct object_id *new_oid, const char *committer, timestamp_t timestamp, int tz, const char *msg, void *cb_data); +/* Iterate in over reflog entries, oldest entry first. */ int refs_for_each_reflog_ent(struct ref_store *refs, const char *refname, each_reflog_ent_fn fn, void *cb_data); int refs_for_each_reflog_ent_reverse(struct ref_store *refs, const char *refname, each_reflog_ent_fn fn, void *cb_data); + +/* Call a function for each reflog entry, oldest entry first. */ int for_each_reflog_ent(const char *refname, each_reflog_ent_fn fn, void *cb_data); int for_each_reflog_ent_reverse(const char *refname, each_reflog_ent_fn fn, void *cb_data); From patchwork Wed Feb 26 08:49:42 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Linus Arver via GitGitGadget X-Patchwork-Id: 11405589 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id C84D314D5 for ; Wed, 26 Feb 2020 08:49:54 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id A85C824653 for ; Wed, 26 Feb 2020 08:49:54 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="pEXVgM76" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727040AbgBZItx (ORCPT ); Wed, 26 Feb 2020 03:49:53 -0500 Received: from mail-ed1-f65.google.com ([209.85.208.65]:34464 "EHLO mail-ed1-f65.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726787AbgBZItx (ORCPT ); Wed, 26 Feb 2020 03:49:53 -0500 Received: by mail-ed1-f65.google.com with SMTP id dm3so1970513edb.1 for ; Wed, 26 Feb 2020 00:49:50 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=zvV6ikoarnwTEEvMB5pK+kHoMHc6Mf8HUaG+5pG6Nus=; b=pEXVgM76X2anb6n8m+2x6HwODnPqH+C3WiWnzA2BJwhPq4kPgZzuXmDx+Nmbjw4PxP tjJZAA3lQRooPtBHAxcqr6gn3e24rcxKiZh6essVG5YFC7WAXiHOWATdTOTtOGBn2NDq +52neKh8pzyGBdYswQuKfvFoLPJEy2NLXJ5aqS0n0a9el8ENM2zDv0xo02urtUs/z4Uw y/wjAGYL5PD7H6zwZ+IF8cWIcQY+CY6R+Vqi07wcxgahziFJCJBRYQkAKNblgb4Zgryz lXtp+jsjiWQHU4aMQ4ILgpLbx2/b2/R4eXr62uh0h3J0lVwf970UMpH9aKichCVd2D+P 0aHg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=zvV6ikoarnwTEEvMB5pK+kHoMHc6Mf8HUaG+5pG6Nus=; b=gVKa0d3CudVcSU5770REvS7uLSqg0A1j//wMYW1ESuGkzDRGsCAVHD9VqlJSGkX3HX dV+bzOG059crSDmGbz9u4ToVNlupQUaw9E/PmlNkoiRcXWjYlIOzt8Of+TmmEHH1n6Fv E0iwg6N0qB3FDonnhEHxm5A5QLfQlvZYGoLImrva2ylj7L9WTaU5nTGD7jCiADSzox6B kkK2Jsi86e8iOPjh2gdNt4tQhni6Oy3zXvRgzD7qRQc52TMXvefQd3I0GijpLOkj3o77 T1Q4+l/jeF40FkC1YOE0oruHajHDsHKpI4Qwr69Yo4MH0rUv5JqQ7vgZ7so4qVpbU3Sl eL2Q== X-Gm-Message-State: APjAAAXZRjKz9MQPqpjabhtfbbmobFvboH0b9cihv/JYKn3nNZfLoB2c JzvVmrg0wd/jTNhuDUJVj5RR9P5m X-Google-Smtp-Source: APXvYqxNb3j9i2a6DRPvB/+rnNQdCzYbZl6oTtxN5KK2QzRvsrqZby3zl0nII35eBLCXFf4E9i2hyQ== X-Received: by 2002:a17:907:2623:: with SMTP id aq3mr3334342ejc.153.1582706990071; Wed, 26 Feb 2020 00:49:50 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id i31sm57607edi.42.2020.02.26.00.49.49 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Feb 2020 00:49:49 -0800 (PST) Message-Id: In-Reply-To: References: From: "Han-Wen Nienhuys via GitGitGadget" Date: Wed, 26 Feb 2020 08:49:42 +0000 Subject: [PATCH v7 2/6] create .git/refs in files-backend.c Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Han-Wen Nienhuys , Han-Wen Nienhuys Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Han-Wen Nienhuys This prepares for supporting the reftable format, which will want create its own file system layout in .git Signed-off-by: Han-Wen Nienhuys --- builtin/init-db.c | 2 -- refs/files-backend.c | 6 ++++++ 2 files changed, 6 insertions(+), 2 deletions(-) diff --git a/builtin/init-db.c b/builtin/init-db.c index 944ec77fe10..45bdea05890 100644 --- a/builtin/init-db.c +++ b/builtin/init-db.c @@ -226,8 +226,6 @@ static int create_default_files(const char *template_path, * We need to create a "refs" dir in any case so that older * versions of git can tell that this is a repository. */ - safe_create_dir(git_path("refs"), 1); - adjust_shared_perm(git_path("refs")); if (refs_init_db(&err)) die("failed to set up refs db: %s", err.buf); diff --git a/refs/files-backend.c b/refs/files-backend.c index 561c33ac8a9..ab7899a9c77 100644 --- a/refs/files-backend.c +++ b/refs/files-backend.c @@ -3157,9 +3157,15 @@ static int files_init_db(struct ref_store *ref_store, struct strbuf *err) files_downcast(ref_store, REF_STORE_WRITE, "init_db"); struct strbuf sb = STRBUF_INIT; + files_ref_path(refs, &sb, "refs"); + safe_create_dir(sb.buf, 1); + /* adjust permissions even if directory already exists. */ + adjust_shared_perm(sb.buf); + /* * Create .git/refs/{heads,tags} */ + strbuf_reset(&sb); files_ref_path(refs, &sb, "refs/heads"); safe_create_dir(sb.buf, 1); From patchwork Wed Feb 26 08:49:43 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Linus Arver via GitGitGadget X-Patchwork-Id: 11405587 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 8D05C1805 for ; Wed, 26 Feb 2020 08:49:54 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 6C225206E6 for ; Wed, 26 Feb 2020 08:49:54 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="KlZtIyL/" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726936AbgBZItx (ORCPT ); Wed, 26 Feb 2020 03:49:53 -0500 Received: from mail-ed1-f66.google.com ([209.85.208.66]:36062 "EHLO mail-ed1-f66.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726764AbgBZItw (ORCPT ); Wed, 26 Feb 2020 03:49:52 -0500 Received: by mail-ed1-f66.google.com with SMTP id j17so2805162edp.3 for ; Wed, 26 Feb 2020 00:49:51 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=4D690/NLx/9daAF2hWG5tCfDYzmNZsPcuZnuRxKSdQk=; b=KlZtIyL/AdlOkvcfUSPnRLdypcpHIfKk6p+HppfXV78O6CyDBElgOu8mwv6rSny0u8 GKnlARj5lBBoFIiPtR9igYIWTKSRnh2VLhBUwv1aqXiR4wYrA5ICR9bHpRHpdN0NZqpg BqBiZWOLmenpQTJo8gzlcqeNwaYYq7L1Ut/1Dnrgo+1iqwKGFubkX8mgdJsiG+MCZiJO RFm7cm31NClcy4r3QmLOK9BgGtZVb87IU9y/XK5K7uTTtRKzaHx+mZrHqOYanVh/Se32 hZkpmqHvAOF5eBUDd3EhHfqmq38SZbOBevHWE017tZ0bCAilr8LRe2s0EzpgxVsDVHYU 2PXQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=4D690/NLx/9daAF2hWG5tCfDYzmNZsPcuZnuRxKSdQk=; b=JSz2KbfxxRufqP2TZ2sa7nIjM7wKNfWZZqQHREPA998akE4FRx+tgd+24uFz0Cqu7J 2EleFe6fEQYfGjGRO6Ug6NMwNRABEp1aDZBw8zV/lXzOVE6rV//sPd8VcfF+a8/Ezgm/ EJDB8DVKWq7giVGCIdBQE8Jb2twIiG/dYkKG2Lbb+gPpv8Eo3bjM5PQLlvvIP50+4ED7 GNVOvK2ZXfKhoQIdxvIFi7InX7Mb6ev5ZDtJ5d1mI5aBDFJacc1sOX6BIgTpUr9srQey hPcMiRzphSL3aOB/txhodN7c2Y9YwubA+rdMXE/cIYgQq7qbxQE2MdNW+yLf2IDApIFh 6z8Q== X-Gm-Message-State: APjAAAUya60SHp9w1NVJcU/zoZgYHH+yGHZ3BxKoD2LldHG0yReVW+Ih 2U5up7Qspuap8/G6oZo2jFFPPzZP X-Google-Smtp-Source: APXvYqx885BIwm7x80yJbqfx80DmEUqeGDQ0dJlyzXAEnxjIYbecHI0C44fbUH/XdyUsDO4J3inF1w== X-Received: by 2002:aa7:dad2:: with SMTP id x18mr3110402eds.384.1582706990820; Wed, 26 Feb 2020 00:49:50 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id i4sm59537edq.45.2020.02.26.00.49.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Feb 2020 00:49:50 -0800 (PST) Message-Id: In-Reply-To: References: From: "Han-Wen Nienhuys via GitGitGadget" Date: Wed, 26 Feb 2020 08:49:43 +0000 Subject: [PATCH v7 3/6] refs: document how ref_iterator_advance_fn should handle symrefs Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Han-Wen Nienhuys , Han-Wen Nienhuys Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Han-Wen Nienhuys Signed-off-by: Han-Wen Nienhuys --- refs/refs-internal.h | 5 +++++ 1 file changed, 5 insertions(+) diff --git a/refs/refs-internal.h b/refs/refs-internal.h index ff2436c0fb7..3490aac3a40 100644 --- a/refs/refs-internal.h +++ b/refs/refs-internal.h @@ -438,6 +438,11 @@ void base_ref_iterator_free(struct ref_iterator *iter); /* Virtual function declarations for ref_iterators: */ +/* + * backend-specific implementation of ref_iterator_advance. + * For symrefs, the function should set REF_ISSYMREF, and it should also + * dereference the symref to provide the OID referent. + */ typedef int ref_iterator_advance_fn(struct ref_iterator *ref_iterator); typedef int ref_iterator_peel_fn(struct ref_iterator *ref_iterator, From patchwork Wed Feb 26 08:49:44 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Linus Arver via GitGitGadget X-Patchwork-Id: 11405591 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 2A361924 for ; Wed, 26 Feb 2020 08:49:58 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id DEFE624653 for ; Wed, 26 Feb 2020 08:49:57 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="B5Aj7bYv" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727191AbgBZIt5 (ORCPT ); Wed, 26 Feb 2020 03:49:57 -0500 Received: from mail-ed1-f41.google.com ([209.85.208.41]:36494 "EHLO mail-ed1-f41.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726787AbgBZIt4 (ORCPT ); Wed, 26 Feb 2020 03:49:56 -0500 Received: by mail-ed1-f41.google.com with SMTP id j17so2805328edp.3 for ; Wed, 26 Feb 2020 00:49:54 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=SihTHykcjy5u3qL56dAedX770ziGTt4tKk5o1MzIYhI=; b=B5Aj7bYvu0JnmjIr/QPZFMRMAXSZxx7X9MwXtNKqlzVytIZWd/5gZG0y59r7DW6q8K ZfULPp5a3rpdtJ2DH6cArWTV1WmrQheCSBCfOzyELJGnTT+nMmVFsqPs7tJflg3XLykl 40cC3SZOi0SDf5HPLnGFGTrSVkOHCQ0IRaGFxH5cXp0J5og3vyxrFyIw502uroXXxRd+ d/vcR8HYNWmJwABxg6E3r/PwgRHmtgRiUTGVQDYmeE3y6WAPOnwT/G7UxTelo+TBeaQ1 utZRFrcHQL3JLvo/sEQVrAvMI741FtvBgZhlbp+WaUqMBSZdSOxN0NJmATJcUFJ1t8Kk bBoQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=SihTHykcjy5u3qL56dAedX770ziGTt4tKk5o1MzIYhI=; b=a2308MLhxg83yepWW8jZQrpZySxXyTnoI8Ez9ZcZAHZaeNkrKY1cJB8ZptjE9A2aA4 OJZNqz5jXCqiVecN+i8PnGcAVEctG71qjKXFw4DXBZwUFAYnG9M64D0sGLFitu3JvEHe KK+XY9789NvV360iIkX9joFOVKc8If4uZZ7rMBWR8PwX7j5LtPBxJKiQE+k4qP901Z2h EvN9QsdlyR8RSFXDhCPZkgbkpDGox+BeCzPOUyJx1W48Z1iIgzw2ti98HlyBmgFkB0Hq uJy/BjMRF3VNLFT2406KQ0EhTga2xesZqfdrJwem56D16UnJ48+6cxqxpVr7FsBTTyV/ yarg== X-Gm-Message-State: APjAAAXiW4TUAUnbHsvNSpZeGVZ+8wfSQYGCp7naTpcfuUYDprtVWaKG qYSfrG1CI7HoeYHDgOvRN0JI8KfS X-Google-Smtp-Source: APXvYqzdEzeiurIIR+vMYY8mf3hCXVDGc7tmYzylXk+M2MobDjHibjrr7YB9vY5XLr0t3YmdsH/wwQ== X-Received: by 2002:a50:ee14:: with SMTP id g20mr3475038eds.10.1582706991764; Wed, 26 Feb 2020 00:49:51 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id f10sm57145eds.31.2020.02.26.00.49.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Feb 2020 00:49:51 -0800 (PST) Message-Id: In-Reply-To: References: From: "Jonathan Nieder via GitGitGadget" Date: Wed, 26 Feb 2020 08:49:44 +0000 Subject: [PATCH v7 4/6] reftable: file format documentation Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Han-Wen Nienhuys , Jonathan Nieder Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Jonathan Nieder Shawn Pearce explains: Some repositories contain a lot of references (e.g. android at 866k, rails at 31k). The reftable format provides: - Near constant time lookup for any single reference, even when the repository is cold and not in process or kernel cache. - Near constant time verification a SHA-1 is referred to by at least one reference (for allow-tip-sha1-in-want). - Efficient lookup of an entire namespace, such as `refs/tags/`. - Support atomic push `O(size_of_update)` operations. - Combine reflog storage with ref storage. This file format spec was originally written in July, 2017 by Shawn Pearce. Some refinements since then were made by Shawn and by Han-Wen Nienhuys based on experiences implementing and experimenting with the format. (All of this was in the context of our work at Google and Google is happy to contribute the result to the Git project.) Imported from JGit[1]'s current version (c217d33ff, "Documentation/technical/reftable: improve repo layout", 2020-02-04) of Documentation/technical/reftable.md and converted to asciidoc by running pandoc -t asciidoc -f markdown reftable.md >reftable.txt using pandoc 2.2.1. The result required the following additional minor changes: - removed the [TOC] directive to add a table of contents, since asciidoc does not support it - replaced git-scm.com/docs links with linkgit: directives that link to other pages within Git's documentation [1] https://eclipse.googlesource.com/jgit/jgit Signed-off-by: Jonathan Nieder --- Documentation/Makefile | 1 + Documentation/technical/reftable.txt | 1067 ++++++++++++++++++++++++++ 2 files changed, 1068 insertions(+) create mode 100644 Documentation/technical/reftable.txt diff --git a/Documentation/Makefile b/Documentation/Makefile index 8fe829cc1b8..3aab9b8d61a 100644 --- a/Documentation/Makefile +++ b/Documentation/Makefile @@ -92,6 +92,7 @@ TECH_DOCS += technical/protocol-capabilities TECH_DOCS += technical/protocol-common TECH_DOCS += technical/protocol-v2 TECH_DOCS += technical/racy-git +TECH_DOCS += technical/reftable TECH_DOCS += technical/send-pack-pipeline TECH_DOCS += technical/shallow TECH_DOCS += technical/signature-format diff --git a/Documentation/technical/reftable.txt b/Documentation/technical/reftable.txt new file mode 100644 index 00000000000..9fa4657d9ff --- /dev/null +++ b/Documentation/technical/reftable.txt @@ -0,0 +1,1067 @@ +reftable +-------- + +Overview +~~~~~~~~ + +Problem statement +^^^^^^^^^^^^^^^^^ + +Some repositories contain a lot of references (e.g. android at 866k, +rails at 31k). The existing packed-refs format takes up a lot of space +(e.g. 62M), and does not scale with additional references. Lookup of a +single reference requires linearly scanning the file. + +Atomic pushes modifying multiple references require copying the entire +packed-refs file, which can be a considerable amount of data moved +(e.g. 62M in, 62M out) for even small transactions (2 refs modified). + +Repositories with many loose references occupy a large number of disk +blocks from the local file system, as each reference is its own file +storing 41 bytes (and another file for the corresponding reflog). This +negatively affects the number of inodes available when a large number of +repositories are stored on the same filesystem. Readers can be penalized +due to the larger number of syscalls required to traverse and read the +`$GIT_DIR/refs` directory. + +Objectives +^^^^^^^^^^ + +* Near constant time lookup for any single reference, even when the +repository is cold and not in process or kernel cache. +* Near constant time verification if a SHA-1 is referred to by at least +one reference (for allow-tip-sha1-in-want). +* Efficient lookup of an entire namespace, such as `refs/tags/`. +* Support atomic push with `O(size_of_update)` operations. +* Combine reflog storage with ref storage for small transactions. +* Separate reflog storage for base refs and historical logs. + +Description +^^^^^^^^^^^ + +A reftable file is a portable binary file format customized for +reference storage. References are sorted, enabling linear scans, binary +search lookup, and range scans. + +Storage in the file is organized into variable sized blocks. Prefix +compression is used within a single block to reduce disk space. Block +size and alignment is tunable by the writer. + +Performance +^^^^^^^^^^^ + +Space used, packed-refs vs. reftable: + +[cols=",>,>,>,>,>",options="header",] +|=============================================================== +|repository |packed-refs |reftable |% original |avg ref |avg obj +|android |62.2 M |36.1 M |58.0% |33 bytes |5 bytes +|rails |1.8 M |1.1 M |57.7% |29 bytes |4 bytes +|git |78.7 K |48.1 K |61.0% |50 bytes |4 bytes +|git (heads) |332 b |269 b |81.0% |33 bytes |0 bytes +|=============================================================== + +Scan (read 866k refs), by reference name lookup (single ref from 866k +refs), and by SHA-1 lookup (refs with that SHA-1, from 866k refs): + +[cols=",>,>,>,>",options="header",] +|========================================================= +|format |cache |scan |by name |by SHA-1 +|packed-refs |cold |402 ms |409,660.1 usec |412,535.8 usec +|packed-refs |hot | |6,844.6 usec |20,110.1 usec +|reftable |cold |112 ms |33.9 usec |323.2 usec +|reftable |hot | |20.2 usec |320.8 usec +|========================================================= + +Space used for 149,932 log entries for 43,061 refs, reflog vs. reftable: + +[cols=",>,>",options="header",] +|================================ +|format |size |avg entry +|$GIT_DIR/logs |173 M |1209 bytes +|reftable |5 M |37 bytes +|================================ + +Details +~~~~~~~ + +Peeling +^^^^^^^ + +References stored in a reftable are peeled, a record for an annotated +(or signed) tag records both the tag object, and the object it refers +to. + +Reference name encoding +^^^^^^^^^^^^^^^^^^^^^^^ + +Reference names are an uninterpreted sequence of bytes that must pass +linkgit:git-check-ref-format[1] as a valid reference name. + +Key unicity +^^^^^^^^^^^ + +Each entry must have a unique key; repeated keys are disallowed. + +Network byte order +^^^^^^^^^^^^^^^^^^ + +All multi-byte, fixed width fields are in network byte order. + +Ordering +^^^^^^^^ + +Blocks are lexicographically ordered by their first reference. + +Directory/file conflicts +^^^^^^^^^^^^^^^^^^^^^^^^ + +The reftable format accepts both `refs/heads/foo` and +`refs/heads/foo/bar` as distinct references. + +This property is useful for retaining log records in reftable, but may +confuse versions of Git using `$GIT_DIR/refs` directory tree to maintain +references. Users of reftable may choose to continue to reject `foo` and +`foo/bar` type conflicts to prevent problems for peers. + +File format +~~~~~~~~~~~ + +Structure +^^^^^^^^^ + +A reftable file has the following high-level structure: + +.... +first_block { + header + first_ref_block +} +ref_block* +ref_index* +obj_block* +obj_index* +log_block* +log_index* +footer +.... + +A log-only file omits the `ref_block`, `ref_index`, `obj_block` and +`obj_index` sections, containing only the file header and log block: + +.... +first_block { + header +} +log_block* +log_index* +footer +.... + +in a log-only file the first log block immediately follows the file +header, without padding to block alignment. + +Block size +^^^^^^^^^^ + +The file’s block size is arbitrarily determined by the writer, and does +not have to be a power of 2. The block size must be larger than the +longest reference name or log entry used in the repository, as +references cannot span blocks. + +Powers of two that are friendly to the virtual memory system or +filesystem (such as 4k or 8k) are recommended. Larger sizes (64k) can +yield better compression, with a possible increased cost incurred by +readers during access. + +The largest block size is `16777215` bytes (15.99 MiB). + +Block alignment +^^^^^^^^^^^^^^^ + +Writers may choose to align blocks at multiples of the block size by +including `padding` filled with NUL bytes at the end of a block to round +out to the chosen alignment. When alignment is used, writers must +specify the alignment with the file header’s `block_size` field. + +Block alignment is not required by the file format. Unaligned files must +set `block_size = 0` in the file header, and omit `padding`. Unaligned +files with more than one ref block must include the link:#Ref-index[ref +index] to support fast lookup. Readers must be able to read both aligned +and non-aligned files. + +Very small files (e.g. 1 only ref block) may omit `padding` and the ref +index to reduce total file size. + +Header +^^^^^^ + +A 24-byte header appears at the beginning of the file: + +.... +'REFT' +uint8( version_number = 1 ) +uint24( block_size ) +uint64( min_update_index ) +uint64( max_update_index ) +.... + +Aligned files must specify `block_size` to configure readers with the +expected block alignment. Unaligned files must set `block_size = 0`. + +The `min_update_index` and `max_update_index` describe bounds for the +`update_index` field of all log records in this file. When reftables are +used in a stack for link:#Update-transactions[transactions], these +fields can order the files such that the prior file’s +`max_update_index + 1` is the next file’s `min_update_index`. + +First ref block +^^^^^^^^^^^^^^^ + +The first ref block shares the same block as the file header, and is 24 +bytes smaller than all other blocks in the file. The first block +immediately begins after the file header, at position 24. + +If the first block is a log block (a log-only file), its block header +begins immediately at position 24. + +Ref block format +^^^^^^^^^^^^^^^^ + +A ref block is written as: + +.... +'r' +uint24( block_len ) +ref_record+ +uint24( restart_offset )+ +uint16( restart_count ) + +padding? +.... + +Blocks begin with `block_type = 'r'` and a 3-byte `block_len` which +encodes the number of bytes in the block up to, but not including the +optional `padding`. This is always less than or equal to the file’s +block size. In the first ref block, `block_len` includes 24 bytes for +the file header. + +The 2-byte `restart_count` stores the number of entries in the +`restart_offset` list, which must not be empty. Readers can use +`restart_count` to binary search between restarts before starting a +linear scan. + +Exactly `restart_count` 3-byte `restart_offset` values precedes the +`restart_count`. Offsets are relative to the start of the block and +refer to the first byte of any `ref_record` whose name has not been +prefix compressed. Entries in the `restart_offset` list must be sorted, +ascending. Readers can start linear scans from any of these records. + +A variable number of `ref_record` fill the middle of the block, +describing reference names and values. The format is described below. + +As the first ref block shares the first file block with the file header, +all `restart_offset` in the first block are relative to the start of the +file (position 0), and include the file header. This forces the first +`restart_offset` to be `28`. + +ref record +++++++++++ + +A `ref_record` describes a single reference, storing both the name and +its value(s). Records are formatted as: + +.... +varint( prefix_length ) +varint( (suffix_length << 3) | value_type ) +suffix +varint( update_index_delta ) +value? +.... + +The `prefix_length` field specifies how many leading bytes of the prior +reference record’s name should be copied to obtain this reference’s +name. This must be 0 for the first reference in any block, and also must +be 0 for any `ref_record` whose offset is listed in the `restart_offset` +table at the end of the block. + +Recovering a reference name from any `ref_record` is a simple concat: + +.... +this_name = prior_name[0..prefix_length] + suffix +.... + +The `suffix_length` value provides the number of bytes available in +`suffix` to copy from `suffix` to complete the reference name. + +The `update_index` that last modified the reference can be obtained by +adding `update_index_delta` to the `min_update_index` from the file +header: `min_update_index + update_index_delta`. + +The `value` follows. Its format is determined by `value_type`, one of +the following: + +* `0x0`: deletion; no value data (see transactions, below) +* `0x1`: one 20-byte object id; value of the ref +* `0x2`: two 20-byte object ids; value of the ref, peeled target +* `0x3`: symbolic reference: `varint( target_len ) target` + +Symbolic references use `0x3`, followed by the complete name of the +reference target. No compression is applied to the target name. + +Types `0x4..0x7` are reserved for future use. + +Ref index +^^^^^^^^^ + +The ref index stores the name of the last reference from every ref block +in the file, enabling reduced disk seeks for lookups. Any reference can +be found by searching the index, identifying the containing block, and +searching within that block. + +The index may be organized into a multi-level index, where the 1st level +index block points to additional ref index blocks (2nd level), which may +in turn point to either additional index blocks (e.g. 3rd level) or ref +blocks (leaf level). Disk reads required to access a ref go up with +higher index levels. Multi-level indexes may be required to ensure no +single index block exceeds the file format’s max block size of +`16777215` bytes (15.99 MiB). To acheive constant O(1) disk seeks for +lookups the index must be a single level, which is permitted to exceed +the file’s configured block size, but not the format’s max block size of +15.99 MiB. + +If present, the ref index block(s) appears after the last ref block. + +If there are at least 4 ref blocks, a ref index block should be written +to improve lookup times. Cold reads using the index require 2 disk reads +(read index, read block), and binary searching < 4 blocks also requires +<= 2 reads. Omitting the index block from smaller files saves space. + +If the file is unaligned and contains more than one ref block, the ref +index must be written. + +Index block format: + +.... +'i' +uint24( block_len ) +index_record+ +uint24( restart_offset )+ +uint16( restart_count ) + +padding? +.... + +The index blocks begin with `block_type = 'i'` and a 3-byte `block_len` +which encodes the number of bytes in the block, up to but not including +the optional `padding`. + +The `restart_offset` and `restart_count` fields are identical in format, +meaning and usage as in ref blocks. + +To reduce the number of reads required for random access in very large +files the index block may be larger than other blocks. However, readers +must hold the entire index in memory to benefit from this, so it’s a +time-space tradeoff in both file size and reader memory. + +Increasing the file’s block size decreases the index size. Alternatively +a multi-level index may be used, keeping index blocks within the file’s +block size, but increasing the number of blocks that need to be +accessed. + +index record +++++++++++++ + +An index record describes the last entry in another block. Index records +are written as: + +.... +varint( prefix_length ) +varint( (suffix_length << 3) | 0 ) +suffix +varint( block_position ) +.... + +Index records use prefix compression exactly like `ref_record`. + +Index records store `block_position` after the suffix, specifying the +absolute position in bytes (from the start of the file) of the block +that ends with this reference. Readers can seek to `block_position` to +begin reading the block header. + +Readers must examine the block header at `block_position` to determine +if the next block is another level index block, or the leaf-level ref +block. + +Reading the index ++++++++++++++++++ + +Readers loading the ref index must first read the footer (below) to +obtain `ref_index_position`. If not present, the position will be 0. The +`ref_index_position` is for the 1st level root of the ref index. + +Obj block format +^^^^^^^^^^^^^^^^ + +Object blocks are optional. Writers may choose to omit object blocks, +especially if readers will not use the SHA-1 to ref mapping. + +Object blocks use unique, abbreviated 2-20 byte SHA-1 keys, mapping to +ref blocks containing references pointing to that object directly, or as +the peeled value of an annotated tag. Like ref blocks, object blocks use +the file’s standard block size. The abbrevation length is available in +the footer as `obj_id_len`. + +To save space in small files, object blocks may be omitted if the ref +index is not present, as brute force search will only need to read a few +ref blocks. When missing, readers should brute force a linear search of +all references to lookup by SHA-1. + +An object block is written as: + +.... +'o' +uint24( block_len ) +obj_record+ +uint24( restart_offset )+ +uint16( restart_count ) + +padding? +.... + +Fields are identical to ref block. Binary search using the restart table +works the same as in reference blocks. + +Because object identifiers are abbreviated by writers to the shortest +unique abbreviation within the reftable, obj key lengths are variable +between 2 and 20 bytes. Readers must compare only for common prefix +match within an obj block or obj index. + +obj record +++++++++++ + +An `obj_record` describes a single object abbreviation, and the blocks +containing references using that unique abbreviation: + +.... +varint( prefix_length ) +varint( (suffix_length << 3) | cnt_3 ) +suffix +varint( cnt_large )? +varint( position_delta )* +.... + +Like in reference blocks, abbreviations are prefix compressed within an +obj block. On large reftables with many unique objects, higher block +sizes (64k), and higher restart interval (128), a `prefix_length` of 2 +or 3 and `suffix_length` of 3 may be common in obj records (unique +abbreviation of 5-6 raw bytes, 10-12 hex digits). + +Each record contains `position_count` number of positions for matching +ref blocks. For 1-7 positions the count is stored in `cnt_3`. When +`cnt_3 = 0` the actual count follows in a varint, `cnt_large`. + +The use of `cnt_3` bets most objects are pointed to by only a single +reference, some may be pointed to by a couple of references, and very +few (if any) are pointed to by more than 7 references. + +A special case exists when `cnt_3 = 0` and `cnt_large = 0`: there are no +`position_delta`, but at least one reference starts with this +abbreviation. A reader that needs exact reference names must scan all +references to find which specific references have the desired object. +Writers should use this format when the `position_delta` list would have +overflowed the file’s block size due to a high number of references +pointing to the same object. + +The first `position_delta` is the position from the start of the file. +Additional `position_delta` entries are sorted ascending and relative to +the prior entry, e.g. a reader would perform: + +.... +pos = position_delta[0] +prior = pos +for (j = 1; j < position_count; j++) { + pos = prior + position_delta[j] + prior = pos +} +.... + +With a position in hand, a reader must linearly scan the ref block, +starting from the first `ref_record`, testing each reference’s SHA-1s +(for `value_type = 0x1` or `0x2`) for full equality. Faster searching by +SHA-1 within a single ref block is not supported by the reftable format. +Smaller block sizes reduce the number of candidates this step must +consider. + +Obj index +^^^^^^^^^ + +The obj index stores the abbreviation from the last entry for every obj +block in the file, enabling reduced disk seeks for all lookups. It is +formatted exactly the same as the ref index, but refers to obj blocks. + +The obj index should be present if obj blocks are present, as obj blocks +should only be written in larger files. + +Readers loading the obj index must first read the footer (below) to +obtain `obj_index_position`. If not present, the position will be 0. + +Log block format +^^^^^^^^^^^^^^^^ + +Unlike ref and obj blocks, log blocks are always unaligned. + +Log blocks are variable in size, and do not match the `block_size` +specified in the file header or footer. Writers should choose an +appropriate buffer size to prepare a log block for deflation, such as +`2 * block_size`. + +A log block is written as: + +.... +'g' +uint24( block_len ) +zlib_deflate { + log_record+ + uint24( restart_offset )+ + uint16( restart_count ) +} +.... + +Log blocks look similar to ref blocks, except `block_type = 'g'`. + +The 4-byte block header is followed by the deflated block contents using +zlib deflate. The `block_len` in the header is the inflated size +(including 4-byte block header), and should be used by readers to +preallocate the inflation output buffer. A log block’s `block_len` may +exceed the file’s block size. + +Offsets within the log block (e.g. `restart_offset`) still include the +4-byte header. Readers may prefer prefixing the inflation output buffer +with the 4-byte header. + +Within the deflate container, a variable number of `log_record` describe +reference changes. The log record format is described below. See ref +block format (above) for a description of `restart_offset` and +`restart_count`. + +Because log blocks have no alignment or padding between blocks, readers +must keep track of the bytes consumed by the inflater to know where the +next log block begins. + +log record +++++++++++ + +Log record keys are structured as: + +.... +ref_name '\0' reverse_int64( update_index ) +.... + +where `update_index` is the unique transaction identifier. The +`update_index` field must be unique within the scope of a `ref_name`. +See the update transactions section below for further details. + +The `reverse_int64` function inverses the value so lexographical +ordering the network byte order encoding sorts the more recent records +with higher `update_index` values first: + +.... +reverse_int64(int64 t) { + return 0xffffffffffffffff - t; +} +.... + +Log records have a similar starting structure to ref and index records, +utilizing the same prefix compression scheme applied to the log record +key described above. + +.... + varint( prefix_length ) + varint( (suffix_length << 3) | log_type ) + suffix + log_data { + old_id + new_id + varint( name_length ) name + varint( email_length ) email + varint( time_seconds ) + sint16( tz_offset ) + varint( message_length ) message + }? +.... + +Log record entries use `log_type` to indicate what follows: + +* `0x0`: deletion; no log data. +* `0x1`: standard git reflog data using `log_data` above. + +The `log_type = 0x0` is mostly useful for `git stash drop`, removing an +entry from the reflog of `refs/stash` in a transaction file (below), +without needing to rewrite larger files. Readers reading a stack of +reflogs must treat this as a deletion. + +For `log_type = 0x1`, the `log_data` section follows +linkgit:git-update-ref[1] logging and includes: + +* two 20-byte SHA-1s (old id, new id) +* varint string of committer’s name +* varint string of committer’s email +* varint time in seconds since epoch (Jan 1, 1970) +* 2-byte timezone offset in minutes (signed) +* varint string of message + +`tz_offset` is the absolute number of minutes from GMT the committer was +at the time of the update. For example `GMT-0800` is encoded in reftable +as `sint16(-480)` and `GMT+0230` is `sint16(150)`. + +The committer email does not contain `<` or `>`, it’s the value normally +found between the `<>` in a git commit object header. + +The `message_length` may be 0, in which case there was no message +supplied for the update. + +Contrary to traditional reflog (which is a file), renames are encoded as +a combination of ref deletion and ref creation. + +Reading the log ++++++++++++++++ + +Readers accessing the log must first read the footer (below) to +determine the `log_position`. The first block of the log begins at +`log_position` bytes since the start of the file. The `log_position` is +not block aligned. + +Importing logs +++++++++++++++ + +When importing from `$GIT_DIR/logs` writers should globally order all +log records roughly by timestamp while preserving file order, and assign +unique, increasing `update_index` values for each log line. Newer log +records get higher `update_index` values. + +Although an import may write only a single reftable file, the reftable +file must span many unique `update_index`, as each log line requires its +own `update_index` to preserve semantics. + +Log index +^^^^^^^^^ + +The log index stores the log key +(`refname \0 reverse_int64(update_index)`) for the last log record of +every log block in the file, supporting bounded-time lookup. + +A log index block must be written if 2 or more log blocks are written to +the file. If present, the log index appears after the last log block. +There is no padding used to align the log index to block alignment. + +Log index format is identical to ref index, except the keys are 9 bytes +longer to include `'\0'` and the 8-byte `reverse_int64(update_index)`. +Records use `block_position` to refer to the start of a log block. + +Reading the index ++++++++++++++++++ + +Readers loading the log index must first read the footer (below) to +obtain `log_index_position`. If not present, the position will be 0. + +Footer +^^^^^^ + +After the last block of the file, a file footer is written. It begins +like the file header, but is extended with additional data. + +A 68-byte footer appears at the end: + +.... + 'REFT' + uint8( version_number = 1 ) + uint24( block_size ) + uint64( min_update_index ) + uint64( max_update_index ) + + uint64( ref_index_position ) + uint64( (obj_position << 5) | obj_id_len ) + uint64( obj_index_position ) + + uint64( log_position ) + uint64( log_index_position ) + + uint32( CRC-32 of above ) +.... + +If a section is missing (e.g. ref index) the corresponding position +field (e.g. `ref_index_position`) will be 0. + +* `obj_position`: byte position for the first obj block. +* `obj_id_len`: number of bytes used to abbreviate object identifiers in +obj blocks. +* `log_position`: byte position for the first log block. +* `ref_index_position`: byte position for the start of the ref index. +* `obj_index_position`: byte position for the start of the obj index. +* `log_index_position`: byte position for the start of the log index. + +Reading the footer +++++++++++++++++++ + +Readers must seek to `file_length - 68` to access the footer. A trusted +external source (such as `stat(2)`) is necessary to obtain +`file_length`. When reading the footer, readers must verify: + +* 4-byte magic is correct +* 1-byte version number is recognized +* 4-byte CRC-32 matches the other 64 bytes (including magic, and +version) + +Once verified, the other fields of the footer can be accessed. + +Varint encoding +^^^^^^^^^^^^^^^ + +Varint encoding is identical to the ofs-delta encoding method used +within pack files. + +Decoder works such as: + +.... +val = buf[ptr] & 0x7f +while (buf[ptr] & 0x80) { + ptr++ + val = ((val + 1) << 7) | (buf[ptr] & 0x7f) +} +.... + +Binary search +^^^^^^^^^^^^^ + +Binary search within a block is supported by the `restart_offset` fields +at the end of the block. Readers can binary search through the restart +table to locate between which two restart points the sought reference or +key should appear. + +Each record identified by a `restart_offset` stores the complete key in +the `suffix` field of the record, making the compare operation during +binary search straightforward. + +Once a restart point lexicographically before the sought reference has +been identified, readers can linearly scan through the following record +entries to locate the sought record, terminating if the current record +sorts after (and therefore the sought key is not present). + +Restart point selection ++++++++++++++++++++++++ + +Writers determine the restart points at file creation. The process is +arbitrary, but every 16 or 64 records is recommended. Every 16 may be +more suitable for smaller block sizes (4k or 8k), every 64 for larger +block sizes (64k). + +More frequent restart points reduces prefix compression and increases +space consumed by the restart table, both of which increase file size. + +Less frequent restart points makes prefix compression more effective, +decreasing overall file size, with increased penalities for readers +walking through more records after the binary search step. + +A maximum of `65535` restart points per block is supported. + +Considerations +~~~~~~~~~~~~~~ + +Lightweight refs dominate +^^^^^^^^^^^^^^^^^^^^^^^^^ + +The reftable format assumes the vast majority of references are single +SHA-1 valued with common prefixes, such as Gerrit Code Review’s +`refs/changes/` namespace, GitHub’s `refs/pulls/` namespace, or many +lightweight tags in the `refs/tags/` namespace. + +Annotated tags storing the peeled object cost an additional 20 bytes per +reference. + +Low overhead +^^^^^^^^^^^^ + +A reftable with very few references (e.g. git.git with 5 heads) is 269 +bytes for reftable, vs. 332 bytes for packed-refs. This supports +reftable scaling down for transaction logs (below). + +Block size +^^^^^^^^^^ + +For a Gerrit Code Review type repository with many change refs, larger +block sizes (64 KiB) and less frequent restart points (every 64) yield +better compression due to more references within the block compressing +against the prior reference. + +Larger block sizes reduce the index size, as the reftable will require +fewer blocks to store the same number of references. + +Minimal disk seeks +^^^^^^^^^^^^^^^^^^ + +Assuming the index block has been loaded into memory, binary searching +for any single reference requires exactly 1 disk seek to load the +containing block. + +Scans and lookups dominate +^^^^^^^^^^^^^^^^^^^^^^^^^^ + +Scanning all references and lookup by name (or namespace such as +`refs/heads/`) are the most common activities performed on repositories. +SHA-1s are stored directly with references to optimize this use case. + +Logs are infrequently read +^^^^^^^^^^^^^^^^^^^^^^^^^^ + +Logs are infrequently accessed, but can be large. Deflating log blocks +saves disk space, with some increased penalty at read time. + +Logs are stored in an isolated section from refs, reducing the burden on +reference readers that want to ignore logs. Further, historical logs can +be isolated into log-only files. + +Logs are read backwards +^^^^^^^^^^^^^^^^^^^^^^^ + +Logs are frequently accessed backwards (most recent N records for master +to answer `master@{4}`), so log records are grouped by reference, and +sorted descending by update index. + +Repository format +~~~~~~~~~~~~~~~~~ + +Version 1 +^^^^^^^^^ + +A repository must set its `$GIT_DIR/config` to configure reftable: + +.... +[core] + repositoryformatversion = 1 +[extensions] + refStorage = reftable +.... + +Layout +^^^^^^ + +A collection of reftable files are stored in the `$GIT_DIR/reftable/` +directory: + +.... +00000001-00000001.log +00000002-00000002.ref +00000003-00000003.ref +.... + +where reftable files are named by a unique name such as produced by the +function `${min_update_index}-${max_update_index}.ref`. + +Log-only files use the `.log` extension, while ref-only and mixed ref +and log files use `.ref`. extension. + +The stack ordering file is `$GIT_DIR/reftable/tables.list` and lists the +current files, one per line, in order, from oldest (base) to newest +(most recent): + +.... +$ cat .git/reftable/tables.list +00000001-00000001.log +00000002-00000002.ref +00000003-00000003.ref +.... + +Readers must read `$GIT_DIR/reftable/tables.list` to determine which +files are relevant right now, and search through the stack in reverse +order (last reftable is examined first). + +Reftable files not listed in `tables.list` may be new (and about to be +added to the stack by the active writer), or ancient and ready to be +pruned. + +Backward compatibility +^^^^^^^^^^^^^^^^^^^^^^ + +Older clients should continue to recognize the directory as a git +repository so they don’t look for an enclosing repository in parent +directories. To this end, a reftable-enabled repository must contain the +following dummy files + +* `.git/HEAD`, a regular file containing `ref: refs/heads/.invalid`. +* `.git/refs/`, a directory +* `.git/refs/heads`, a regular file + +Readers +^^^^^^^ + +Readers can obtain a consistent snapshot of the reference space by +following: + +1. Open and read the `tables.list` file. +2. Open each of the reftable files that it mentions. +3. If any of the files is missing, goto 1. +4. Read from the now-open files as long as necessary. + +Update transactions +^^^^^^^^^^^^^^^^^^^ + +Although reftables are immutable, mutations are supported by writing a +new reftable and atomically appending it to the stack: + +1. Acquire `tables.list.lock`. +2. Read `tables.list` to determine current reftables. +3. Select `update_index` to be most recent file’s +`max_update_index + 1`. +4. Prepare temp reftable `tmp_XXXXXX`, including log entries. +5. Rename `tmp_XXXXXX` to `${update_index}-${update_index}.ref`. +6. Copy `tables.list` to `tables.list.lock`, appending file from (5). +7. Rename `tables.list.lock` to `tables.list`. + +During step 4 the new file’s `min_update_index` and `max_update_index` +are both set to the `update_index` selected by step 3. All log records +for the transaction use the same `update_index` in their keys. This +enables later correlation of which references were updated by the same +transaction. + +Because a single `tables.list.lock` file is used to manage locking, the +repository is single-threaded for writers. Writers may have to busy-spin +(with backoff) around creating `tables.list.lock`, for up to an +acceptable wait period, aborting if the repository is too busy to +mutate. Application servers wrapped around repositories (e.g. Gerrit +Code Review) can layer their own lock/wait queue to improve fairness to +writers. + +Reference deletions +^^^^^^^^^^^^^^^^^^^ + +Deletion of any reference can be explicitly stored by setting the `type` +to `0x0` and omitting the `value` field of the `ref_record`. This serves +as a tombstone, overriding any assertions about the existence of the +reference from earlier files in the stack. + +Compaction +^^^^^^^^^^ + +A partial stack of reftables can be compacted by merging references +using a straightforward merge join across reftables, selecting the most +recent value for output, and omitting deleted references that do not +appear in remaining, lower reftables. + +A compacted reftable should set its `min_update_index` to the smallest +of the input files’ `min_update_index`, and its `max_update_index` +likewise to the largest input `max_update_index`. + +For sake of illustration, assume the stack currently consists of +reftable files (from oldest to newest): A, B, C, and D. The compactor is +going to compact B and C, leaving A and D alone. + +1. Obtain lock `tables.list.lock` and read the `tables.list` file. +2. Obtain locks `B.lock` and `C.lock`. Ownership of these locks +prevents other processes from trying to compact these files. +3. Release `tables.list.lock`. +4. Compact `B` and `C` into a temp file +`${min_update_index}-${max_update_index}_XXXXXX`. +5. Reacquire lock `tables.list.lock`. +6. Verify that `B` and `C` are still in the stack, in that order. This +should always be the case, assuming that other processes are adhering to +the locking protocol. +7. Rename `${min_update_index}-${max_update_index}_XXXXXX` to +`${min_update_index}-${max_update_index}.ref`. +8. Write the new stack to `tables.list.lock`, replacing `B` and `C` +with the file from (4). +9. Rename `tables.list.lock` to `tables.list`. +10. Delete `B` and `C`, perhaps after a short sleep to avoid forcing +readers to backtrack. + +This strategy permits compactions to proceed independently of updates. + +Each reftable (compacted or not) is uniquely identified by its name, so +open reftables can be cached by their name. + +Alternatives considered +~~~~~~~~~~~~~~~~~~~~~~~ + +bzip packed-refs +^^^^^^^^^^^^^^^^ + +`bzip2` can significantly shrink a large packed-refs file (e.g. 62 MiB +compresses to 23 MiB, 37%). However the bzip format does not support +random access to a single reference. Readers must inflate and discard +while performing a linear scan. + +Breaking packed-refs into chunks (individually compressing each chunk) +would reduce the amount of data a reader must inflate, but still leaves +the problem of indexing chunks to support readers efficiently locating +the correct chunk. + +Given the compression achieved by reftable’s encoding, it does not seem +necessary to add the complexity of bzip/gzip/zlib. + +Michael Haggerty’s alternate format +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +Michael Haggerty proposed +https://public-inbox.org/git/CAMy9T_HCnyc1g8XWOOWhe7nN0aEFyyBskV2aOMb_fe+wGvEJ7A@mail.gmail.com/[an +alternate] format to reftable on the Git mailing list. This format uses +smaller chunks, without the restart table, and avoids block alignment +with padding. Reflog entries immediately follow each ref, and are thus +interleaved between refs. + +Performance testing indicates reftable is faster for lookups (51% +faster, 11.2 usec vs. 5.4 usec), although reftable produces a slightly +larger file (+ ~3.2%, 28.3M vs 29.2M): + +[cols=">,>,>,>",options="header",] +|===================================== +|format |size |seek cold |seek hot +|mh-alt |28.3 M |23.4 usec |11.2 usec +|reftable |29.2 M |19.9 usec |5.4 usec +|===================================== + +JGit Ketch RefTree +^^^^^^^^^^^^^^^^^^ + +https://dev.eclipse.org/mhonarc/lists/jgit-dev/msg03073.html[JGit Ketch] +proposed +https://public-inbox.org/git/CAJo=hJvnAPNAdDcAAwAvU9C4RVeQdoS3Ev9WTguHx4fD0V_nOg@mail.gmail.com/[RefTree], +an encoding of references inside Git tree objects stored as part of the +repository’s object database. + +The RefTree format adds additional load on the object database storage +layer (more loose objects, more objects in packs), and relies heavily on +the packer’s delta compression to save space. Namespaces which are flat +(e.g. thousands of tags in refs/tags) initially create very large loose +objects, and so RefTree does not address the problem of copying many +references to modify a handful. + +Flat namespaces are not efficiently searchable in RefTree, as tree +objects in canonical formatting cannot be binary searched. This fails +the need to handle a large number of references in a single namespace, +such as GitHub’s `refs/pulls`, or a project with many tags. + +LMDB +^^^^ + +David Turner proposed +https://public-inbox.org/git/1455772670-21142-26-git-send-email-dturner@twopensource.com/[using +LMDB], as LMDB is lightweight (64k of runtime code) and GPL-compatible +license. + +A downside of LMDB is its reliance on a single C implementation. This +makes embedding inside JGit (a popular reimplemenation of Git) +difficult, and hoisting onto virtual storage (for JGit DFS) virtually +impossible. + +A common format that can be supported by all major Git implementations +(git-core, JGit, libgit2) is strongly preferred. + +Future +~~~~~~ + +Longer hashes +^^^^^^^^^^^^^ + +Version will bump (e.g. 2) to indicate `value` uses a different object +id length other than 20. The length could be stored in an expanded file +header, or hardcoded as part of the version. From patchwork Wed Feb 26 08:49:45 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Linus Arver via GitGitGadget X-Patchwork-Id: 11405597 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id A7694924 for ; Wed, 26 Feb 2020 08:50:05 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 26DEA24653 for ; Wed, 26 Feb 2020 08:50:05 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="ADZ8Nfyr" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727311AbgBZIuE (ORCPT ); Wed, 26 Feb 2020 03:50:04 -0500 Received: from mail-ed1-f43.google.com ([209.85.208.43]:46472 "EHLO mail-ed1-f43.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727141AbgBZIuE (ORCPT ); Wed, 26 Feb 2020 03:50:04 -0500 Received: by mail-ed1-f43.google.com with SMTP id p14so2730416edy.13 for ; Wed, 26 Feb 2020 00:49:57 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=92gmnrqD9neOty5d/BkYZIwhqJTY30lDcg5GeuNe9EE=; b=ADZ8Nfyr4+MGbqPHVRckGoM41C8unP0/Q6sCeDgDdK3iRKQEEytimu7HLG+BXviIFt n3BwiuQVZIB3jEa6Wbdvm2RNAo3UGDl3QuCHmqDMT3pfOVTOnKvcCjKQSzE8QbxDhuP8 FzW8yRR1hT3735Mv4oWRBLLDjBXVnwk/LHMtYRw+PPslhz6QSamI41ejkInsGsD8kCui F3JP6NiXeKibwgECwoQdcU/fEm6KfH7ZzQq7Qy3CgG1VceJJqOBMQIV+bruZj6MLNdJ+ kxX3XLf96ozxpS8XGkq3cpxx8Peb/jAJtqZUxMoeGrjEwWgtzCeWr6dApiTKAJeCH0dR iDrQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=92gmnrqD9neOty5d/BkYZIwhqJTY30lDcg5GeuNe9EE=; b=CDDXMSy6TucifKPDgRlxrprxf996VfBY/WN+lmTWUZm69qyJ9CBkiNHu08bgRcLhTC DpEBRprT8Qz4Rq/2sNo/6RwGoxezd34tdniKY1IpxiacgYdxE3voAAw9f7Lc5Ijepk+1 Pqfx+1JoyiIqHFFFk2xXh4MsYt9cXQbtoRKE65nJT1UMGnUJLHDsKVErW9tmA4nxjiSK 4lY5OGCk2fJAgQ9dqM7ixzuhbnXplb/k6q8bgmyLqxM+aLUNr3K9ximSgjmfsFth3LyB YshczLoYgLvvvYf9tLzWaPWciDaeJg8gr+nNchaUwsvfxr1FAoGBC7iwN3TYp85i6okx fYqA== X-Gm-Message-State: APjAAAVux/QtTQ1NSJHgvDsxZ+60dZExls8SpPMgzjrb69seEGh/z5es 2aZYpHrb1Nwgd2pwDViSLtlbHMBD X-Google-Smtp-Source: APXvYqxFCJpvz5sf8Kzc6CPuRXPNYJ4Ivna+yoSH9z0UKmC7waSy9HJoMh/tnUYEZNoyd17Lac6X1g== X-Received: by 2002:a05:6402:309b:: with SMTP id de27mr3409240edb.269.1582706992884; Wed, 26 Feb 2020 00:49:52 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id a9sm55407edm.82.2020.02.26.00.49.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Feb 2020 00:49:52 -0800 (PST) Message-Id: <30ed43a4fdbe2122955af5d4fc222103938521d7.1582706986.git.gitgitgadget@gmail.com> In-Reply-To: References: From: "Han-Wen Nienhuys via GitGitGadget" Date: Wed, 26 Feb 2020 08:49:45 +0000 Subject: [PATCH v7 5/6] Add reftable library Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Han-Wen Nienhuys , Han-Wen Nienhuys Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Han-Wen Nienhuys Reftable is a format for storing the ref database. Its rationale and specification is in the preceding commit. Further context and motivation can be found in background reading: * Original discussion on JGit-dev: https://www.eclipse.org/lists/jgit-dev/msg03389.html * First design discussion on git@vger: https://public-inbox.org/git/CAJo=hJtTp2eA3z9wW9cHo-nA7kK40vVThqh6inXpbCcqfdMP9g@mail.gmail.com/ * Last design discussion on git@vger: https://public-inbox.org/git/CAJo=hJsZcAM9sipdVr7TMD-FD2V2W6_pvMQ791EGCDsDkQ033w@mail.gmail.com/ * First attempt at implementation: https://public-inbox.org/git/CAP8UFD0PPZSjBnxCA7ez91vBuatcHKQ+JUWvTD1iHcXzPBjPBg@mail.gmail.com/ * libgit2 support issue: https://github.com/libgit2/libgit2/issues * GitLab support issue: https://gitlab.com/gitlab-org/git/issues/6 * go-git support issue: https://github.com/src-d/go-git/issues/1059 Signed-off-by: Han-Wen Nienhuys --- reftable/LICENSE | 31 ++ reftable/README.md | 11 + reftable/VERSION | 5 + reftable/basics.c | 160 ++++++ reftable/basics.h | 30 ++ reftable/block.c | 413 +++++++++++++++ reftable/block.h | 71 +++ reftable/blocksource.h | 20 + reftable/bytes.c | 0 reftable/config.h | 1 + reftable/constants.h | 25 + reftable/dump.c | 97 ++++ reftable/file.c | 97 ++++ reftable/iter.c | 229 ++++++++ reftable/iter.h | 56 ++ reftable/merged.c | 290 +++++++++++ reftable/merged.h | 34 ++ reftable/pq.c | 114 ++++ reftable/pq.h | 34 ++ reftable/reader.c | 720 ++++++++++++++++++++++++++ reftable/reader.h | 52 ++ reftable/record.c | 1119 ++++++++++++++++++++++++++++++++++++++++ reftable/record.h | 79 +++ reftable/reftable.h | 409 +++++++++++++++ reftable/slice.c | 199 +++++++ reftable/slice.h | 39 ++ reftable/stack.c | 1007 ++++++++++++++++++++++++++++++++++++ reftable/stack.h | 40 ++ reftable/system.h | 53 ++ reftable/tree.c | 66 +++ reftable/tree.h | 24 + reftable/update.sh | 13 + reftable/writer.c | 637 +++++++++++++++++++++++ reftable/writer.h | 45 ++ reftable/zlib-compat.c | 92 ++++ 35 files changed, 6312 insertions(+) create mode 100644 reftable/LICENSE create mode 100644 reftable/README.md create mode 100644 reftable/VERSION create mode 100644 reftable/basics.c create mode 100644 reftable/basics.h create mode 100644 reftable/block.c create mode 100644 reftable/block.h create mode 100644 reftable/blocksource.h create mode 100644 reftable/bytes.c create mode 100644 reftable/config.h create mode 100644 reftable/constants.h create mode 100644 reftable/dump.c create mode 100644 reftable/file.c create mode 100644 reftable/iter.c create mode 100644 reftable/iter.h create mode 100644 reftable/merged.c create mode 100644 reftable/merged.h create mode 100644 reftable/pq.c create mode 100644 reftable/pq.h create mode 100644 reftable/reader.c create mode 100644 reftable/reader.h create mode 100644 reftable/record.c create mode 100644 reftable/record.h create mode 100644 reftable/reftable.h create mode 100644 reftable/slice.c create mode 100644 reftable/slice.h create mode 100644 reftable/stack.c create mode 100644 reftable/stack.h create mode 100644 reftable/system.h create mode 100644 reftable/tree.c create mode 100644 reftable/tree.h create mode 100644 reftable/update.sh create mode 100644 reftable/writer.c create mode 100644 reftable/writer.h create mode 100644 reftable/zlib-compat.c diff --git a/reftable/LICENSE b/reftable/LICENSE new file mode 100644 index 00000000000..402e0f9356b --- /dev/null +++ b/reftable/LICENSE @@ -0,0 +1,31 @@ +BSD License + +Copyright (c) 2020, Google LLC +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + +* Redistributions of source code must retain the above copyright notice, +this list of conditions and the following disclaimer. + +* Redistributions in binary form must reproduce the above copyright +notice, this list of conditions and the following disclaimer in the +documentation and/or other materials provided with the distribution. + +* Neither the name of Google LLC nor the names of its contributors may +be used to endorse or promote products derived from this software +without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. diff --git a/reftable/README.md b/reftable/README.md new file mode 100644 index 00000000000..21500563fd4 --- /dev/null +++ b/reftable/README.md @@ -0,0 +1,11 @@ + +The source code in this directory comes from https://github.com/google/reftable. + +The VERSION file keeps track of the current version of the reftable library. + +To update the library, do: + + sh reftable/update.sh + +Bugfixes should be accompanied by a test and applied to upstream project at +https://github.com/google/reftable. diff --git a/reftable/VERSION b/reftable/VERSION new file mode 100644 index 00000000000..f3f33eae71e --- /dev/null +++ b/reftable/VERSION @@ -0,0 +1,5 @@ +commit ccce3b3eb763e79b23a3b4677d65ecceb4155ba3 +Author: Han-Wen Nienhuys +Date: Tue Feb 25 20:42:29 2020 +0100 + + C: rephrase the hash ID API in terms of a uint32_t diff --git a/reftable/basics.c b/reftable/basics.c new file mode 100644 index 00000000000..ab2d09ef637 --- /dev/null +++ b/reftable/basics.c @@ -0,0 +1,160 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#include "basics.h" + +#include "system.h" + +void put_be24(byte *out, uint32_t i) +{ + out[0] = (byte)((i >> 16) & 0xff); + out[1] = (byte)((i >> 8) & 0xff); + out[2] = (byte)((i)&0xff); +} + +uint32_t get_be24(byte *in) +{ + return (uint32_t)(in[0]) << 16 | (uint32_t)(in[1]) << 8 | + (uint32_t)(in[2]); +} + +void put_be16(uint8_t *out, uint16_t i) +{ + out[0] = (uint8_t)((i >> 8) & 0xff); + out[1] = (uint8_t)((i)&0xff); +} + +/* + find smallest index i in [0, sz) at which f(i) is true, assuming + that f is ascending. Return sz if f(i) is false for all indices. +*/ +int binsearch(int sz, int (*f)(int k, void *args), void *args) +{ + int lo = 0; + int hi = sz; + + /* invariant: (hi == sz) || f(hi) == true + (lo == 0 && f(0) == true) || fi(lo) == false + */ + while (hi - lo > 1) { + int mid = lo + (hi - lo) / 2; + + int val = f(mid, args); + if (val) { + hi = mid; + } else { + lo = mid; + } + } + + if (lo == 0) { + if (f(0, args)) { + return 0; + } else { + return 1; + } + } + + return hi; +} + +void free_names(char **a) +{ + char **p = a; + if (p == NULL) { + return; + } + while (*p) { + free(*p); + p++; + } + free(a); +} + +int names_length(char **names) +{ + int len = 0; + char **p = names; + while (*p) { + p++; + len++; + } + return len; +} + +/* parse a newline separated list of names. Empty names are discarded. */ +void parse_names(char *buf, int size, char ***namesp) +{ + char **names = NULL; + int names_cap = 0; + int names_len = 0; + + char *p = buf; + char *end = buf + size; + while (p < end) { + char *next = strchr(p, '\n'); + if (next != NULL) { + *next = 0; + } else { + next = end; + } + if (p < next) { + if (names_len == names_cap) { + names_cap = 2 * names_cap + 1; + names = realloc(names, + names_cap * sizeof(char *)); + } + names[names_len++] = xstrdup(p); + } + p = next + 1; + } + + if (names_len == names_cap) { + names_cap = 2 * names_cap + 1; + names = realloc(names, names_cap * sizeof(char *)); + } + + names[names_len] = NULL; + *namesp = names; +} + +int names_equal(char **a, char **b) +{ + while (*a && *b) { + if (strcmp(*a, *b)) { + return 0; + } + + a++; + b++; + } + + return *a == *b; +} + +const char *error_str(int err) +{ + switch (err) { + case IO_ERROR: + return "I/O error"; + case FORMAT_ERROR: + return "FORMAT_ERROR"; + case NOT_EXIST_ERROR: + return "NOT_EXIST_ERROR"; + case LOCK_ERROR: + return "LOCK_ERROR"; + case API_ERROR: + return "API_ERROR"; + case ZLIB_ERROR: + return "ZLIB_ERROR"; + case -1: + return "general error"; + default: + return "unknown error code"; + } +} diff --git a/reftable/basics.h b/reftable/basics.h new file mode 100644 index 00000000000..fd0a9796f84 --- /dev/null +++ b/reftable/basics.h @@ -0,0 +1,30 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#ifndef BASICS_H +#define BASICS_H + +#include "system.h" + +#include "reftable.h" + +#define true 1 +#define false 0 + +void put_be24(byte *out, uint32_t i); +uint32_t get_be24(byte *in); +void put_be16(uint8_t *out, uint16_t i); + +int binsearch(int sz, int (*f)(int k, void *args), void *args); + +void free_names(char **a); +void parse_names(char *buf, int size, char ***namesp); +int names_equal(char **a, char **b); +int names_length(char **names); + +#endif diff --git a/reftable/block.c b/reftable/block.c new file mode 100644 index 00000000000..aa69c8abe21 --- /dev/null +++ b/reftable/block.c @@ -0,0 +1,413 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#include "block.h" + +#include "system.h" + +#include "blocksource.h" +#include "constants.h" +#include "record.h" +#include "reftable.h" +#include "zlib.h" + +int block_writer_register_restart(struct block_writer *w, int n, bool restart, + struct slice key); + +void block_writer_init(struct block_writer *bw, byte typ, byte *buf, + uint32_t block_size, uint32_t header_off, int hash_size) +{ + bw->buf = buf; + bw->hash_size = hash_size; + bw->block_size = block_size; + bw->header_off = header_off; + bw->buf[header_off] = typ; + bw->next = header_off + 4; + bw->restart_interval = 16; + bw->entries = 0; +} + +byte block_writer_type(struct block_writer *bw) +{ + return bw->buf[bw->header_off]; +} + +/* adds the record to the block. Returns -1 if it does not fit, 0 on + success */ +int block_writer_add(struct block_writer *w, struct record rec) +{ + struct slice empty = { 0 }; + struct slice last = w->entries % w->restart_interval == 0 ? empty : + w->last_key; + struct slice out = { + .buf = w->buf + w->next, + .len = w->block_size - w->next, + }; + + struct slice start = out; + + bool restart = false; + struct slice key = { 0 }; + int n = 0; + + record_key(rec, &key); + n = encode_key(&restart, out, last, key, record_val_type(rec)); + if (n < 0) { + goto err; + } + out.buf += n; + out.len -= n; + + n = record_encode(rec, out, w->hash_size); + if (n < 0) { + goto err; + } + + out.buf += n; + out.len -= n; + + if (block_writer_register_restart(w, start.len - out.len, restart, + key) < 0) { + goto err; + } + + free(slice_yield(&key)); + return 0; + +err: + free(slice_yield(&key)); + return -1; +} + +int block_writer_register_restart(struct block_writer *w, int n, bool restart, + struct slice key) +{ + int rlen = w->restart_len; + if (rlen >= MAX_RESTARTS) { + restart = false; + } + + if (restart) { + rlen++; + } + if (2 + 3 * rlen + n > w->block_size - w->next) { + return -1; + } + if (restart) { + if (w->restart_len == w->restart_cap) { + w->restart_cap = w->restart_cap * 2 + 1; + w->restarts = realloc( + w->restarts, sizeof(uint32_t) * w->restart_cap); + } + + w->restarts[w->restart_len++] = w->next; + } + + w->next += n; + slice_copy(&w->last_key, key); + w->entries++; + return 0; +} + +int block_writer_finish(struct block_writer *w) +{ + int i = 0; + for (i = 0; i < w->restart_len; i++) { + put_be24(w->buf + w->next, w->restarts[i]); + w->next += 3; + } + + put_be16(w->buf + w->next, w->restart_len); + w->next += 2; + put_be24(w->buf + 1 + w->header_off, w->next); + + if (block_writer_type(w) == BLOCK_TYPE_LOG) { + int block_header_skip = 4 + w->header_off; + struct slice compressed = { 0 }; + int zresult = 0; + uLongf src_len = w->next - block_header_skip; + slice_resize(&compressed, src_len); + + while (1) { + uLongf dest_len = compressed.len; + + zresult = compress2(compressed.buf, &dest_len, + w->buf + block_header_skip, src_len, + 9); + if (zresult == Z_BUF_ERROR) { + slice_resize(&compressed, 2 * compressed.len); + continue; + } + + if (Z_OK != zresult) { + free(slice_yield(&compressed)); + return ZLIB_ERROR; + } + + memcpy(w->buf + block_header_skip, compressed.buf, + dest_len); + w->next = dest_len + block_header_skip; + break; + } + } + return w->next; +} + +byte block_reader_type(struct block_reader *r) +{ + return r->block.data[r->header_off]; +} + +int block_reader_init(struct block_reader *br, struct block *block, + uint32_t header_off, uint32_t table_block_size, + int hash_size) +{ + uint32_t full_block_size = table_block_size; + byte typ = block->data[header_off]; + uint32_t sz = get_be24(block->data + header_off + 1); + + if (!is_block_type(typ)) { + return FORMAT_ERROR; + } + + if (typ == BLOCK_TYPE_LOG) { + struct slice uncompressed = { 0 }; + int block_header_skip = 4 + header_off; + uLongf dst_len = sz - block_header_skip; + uLongf src_len = block->len - block_header_skip; + + slice_resize(&uncompressed, sz); + memcpy(uncompressed.buf, block->data, block_header_skip); + + if (Z_OK != uncompress_return_consumed( + uncompressed.buf + block_header_skip, + &dst_len, block->data + block_header_skip, + &src_len)) { + free(slice_yield(&uncompressed)); + return ZLIB_ERROR; + } + + block_source_return_block(block->source, block); + block->data = uncompressed.buf; + block->len = dst_len; /* XXX: 4 bytes missing? */ + block->source = malloc_block_source(); + full_block_size = src_len + block_header_skip; + } else if (full_block_size == 0) { + full_block_size = sz; + } else if (sz < full_block_size && sz < block->len && + block->data[sz] != 0) { + /* If the block is smaller than the full block size, it is + padded (data followed by '\0') or the next block is + unaligned. */ + full_block_size = sz; + } + + { + uint16_t restart_count = get_be16(block->data + sz - 2); + uint32_t restart_start = sz - 2 - 3 * restart_count; + + byte *restart_bytes = block->data + restart_start; + + /* transfer ownership. */ + br->block = *block; + block->data = NULL; + block->len = 0; + + br->hash_size = hash_size; + br->block_len = restart_start; + br->full_block_size = full_block_size; + br->header_off = header_off; + br->restart_count = restart_count; + br->restart_bytes = restart_bytes; + } + + return 0; +} + +static uint32_t block_reader_restart_offset(struct block_reader *br, int i) +{ + return get_be24(br->restart_bytes + 3 * i); +} + +void block_reader_start(struct block_reader *br, struct block_iter *it) +{ + it->br = br; + slice_resize(&it->last_key, 0); + it->next_off = br->header_off + 4; +} + +struct restart_find_args { + int error; + struct slice key; + struct block_reader *r; +}; + +static int restart_key_less(int idx, void *args) +{ + struct restart_find_args *a = (struct restart_find_args *)args; + uint32_t off = block_reader_restart_offset(a->r, idx); + struct slice in = { + .buf = a->r->block.data + off, + .len = a->r->block_len - off, + }; + + /* the restart key is verbatim in the block, so this could avoid the + alloc for decoding the key */ + struct slice rkey = { 0 }; + struct slice last_key = { 0 }; + byte unused_extra; + int n = decode_key(&rkey, &unused_extra, last_key, in); + if (n < 0) { + a->error = 1; + return -1; + } + + { + int result = slice_compare(a->key, rkey); + free(slice_yield(&rkey)); + return result; + } +} + +void block_iter_copy_from(struct block_iter *dest, struct block_iter *src) +{ + dest->br = src->br; + dest->next_off = src->next_off; + slice_copy(&dest->last_key, src->last_key); +} + +/* return < 0 for error, 0 for OK, > 0 for EOF. */ +int block_iter_next(struct block_iter *it, struct record rec) +{ + if (it->next_off >= it->br->block_len) { + return 1; + } + + { + struct slice in = { + .buf = it->br->block.data + it->next_off, + .len = it->br->block_len - it->next_off, + }; + struct slice start = in; + struct slice key = { 0 }; + byte extra; + int n = decode_key(&key, &extra, it->last_key, in); + if (n < 0) { + return -1; + } + + in.buf += n; + in.len -= n; + n = record_decode(rec, key, extra, in, it->br->hash_size); + if (n < 0) { + return -1; + } + in.buf += n; + in.len -= n; + + slice_copy(&it->last_key, key); + it->next_off += start.len - in.len; + free(slice_yield(&key)); + return 0; + } +} + +int block_reader_first_key(struct block_reader *br, struct slice *key) +{ + struct slice empty = { 0 }; + int off = br->header_off + 4; + struct slice in = { + .buf = br->block.data + off, + .len = br->block_len - off, + }; + + byte extra = 0; + int n = decode_key(key, &extra, empty, in); + if (n < 0) { + return n; + } + return 0; +} + +int block_iter_seek(struct block_iter *it, struct slice want) +{ + return block_reader_seek(it->br, it, want); +} + +void block_iter_close(struct block_iter *it) +{ + free(slice_yield(&it->last_key)); +} + +int block_reader_seek(struct block_reader *br, struct block_iter *it, + struct slice want) +{ + struct restart_find_args args = { + .key = want, + .r = br, + }; + + int i = binsearch(br->restart_count, &restart_key_less, &args); + if (args.error) { + return -1; + } + + it->br = br; + if (i > 0) { + i--; + it->next_off = block_reader_restart_offset(br, i); + } else { + it->next_off = br->header_off + 4; + } + + { + struct record rec = new_record(block_reader_type(br)); + struct slice key = { 0 }; + int result = 0; + int err = 0; + struct block_iter next = { 0 }; + while (true) { + block_iter_copy_from(&next, it); + + err = block_iter_next(&next, rec); + if (err < 0) { + result = -1; + goto exit; + } + + record_key(rec, &key); + if (err > 0 || slice_compare(key, want) >= 0) { + result = 0; + goto exit; + } + + block_iter_copy_from(it, &next); + } + + exit: + free(slice_yield(&key)); + free(slice_yield(&next.last_key)); + record_clear(rec); + free(record_yield(&rec)); + + return result; + } +} + +void block_writer_reset(struct block_writer *bw) +{ + bw->restart_len = 0; + bw->last_key.len = 0; +} + +void block_writer_clear(struct block_writer *bw) +{ + FREE_AND_NULL(bw->restarts); + free(slice_yield(&bw->last_key)); + /* the block is not owned. */ +} diff --git a/reftable/block.h b/reftable/block.h new file mode 100644 index 00000000000..66c7772c304 --- /dev/null +++ b/reftable/block.h @@ -0,0 +1,71 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#ifndef BLOCK_H +#define BLOCK_H + +#include "basics.h" +#include "record.h" +#include "reftable.h" + +struct block_writer { + byte *buf; + uint32_t block_size; + uint32_t header_off; + int restart_interval; + int hash_size; + + uint32_t next; + uint32_t *restarts; + uint32_t restart_len; + uint32_t restart_cap; + struct slice last_key; + int entries; +}; + +void block_writer_init(struct block_writer *bw, byte typ, byte *buf, + uint32_t block_size, uint32_t header_off, int hash_size); +byte block_writer_type(struct block_writer *bw); +int block_writer_add(struct block_writer *w, struct record rec); +int block_writer_finish(struct block_writer *w); +void block_writer_reset(struct block_writer *bw); +void block_writer_clear(struct block_writer *bw); + +struct block_reader { + uint32_t header_off; + struct block block; + int hash_size; + + /* size of the data, excluding restart data. */ + uint32_t block_len; + byte *restart_bytes; + uint32_t full_block_size; + uint16_t restart_count; +}; + +struct block_iter { + uint32_t next_off; + struct block_reader *br; + struct slice last_key; +}; + +int block_reader_init(struct block_reader *br, struct block *bl, + uint32_t header_off, uint32_t table_block_size, + int hash_size); +void block_reader_start(struct block_reader *br, struct block_iter *it); +int block_reader_seek(struct block_reader *br, struct block_iter *it, + struct slice want); +byte block_reader_type(struct block_reader *r); +int block_reader_first_key(struct block_reader *br, struct slice *key); + +void block_iter_copy_from(struct block_iter *dest, struct block_iter *src); +int block_iter_next(struct block_iter *it, struct record rec); +int block_iter_seek(struct block_iter *it, struct slice want); +void block_iter_close(struct block_iter *it); + +#endif diff --git a/reftable/blocksource.h b/reftable/blocksource.h new file mode 100644 index 00000000000..f3ad3a4c229 --- /dev/null +++ b/reftable/blocksource.h @@ -0,0 +1,20 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#ifndef BLOCKSOURCE_H +#define BLOCKSOURCE_H + +#include "reftable.h" + +uint64_t block_source_size(struct block_source source); +int block_source_read_block(struct block_source source, struct block *dest, + uint64_t off, uint32_t size); +void block_source_return_block(struct block_source source, struct block *ret); +void block_source_close(struct block_source source); + +#endif diff --git a/reftable/bytes.c b/reftable/bytes.c new file mode 100644 index 00000000000..e69de29bb2d diff --git a/reftable/config.h b/reftable/config.h new file mode 100644 index 00000000000..40a8c178f10 --- /dev/null +++ b/reftable/config.h @@ -0,0 +1 @@ +/* empty */ diff --git a/reftable/constants.h b/reftable/constants.h new file mode 100644 index 00000000000..85399fa4758 --- /dev/null +++ b/reftable/constants.h @@ -0,0 +1,25 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#ifndef CONSTANTS_H +#define CONSTANTS_H + +#define VERSION 1 +#define HEADER_SIZE 24 +#define FOOTER_SIZE 68 + +#define BLOCK_TYPE_LOG 'g' +#define BLOCK_TYPE_INDEX 'i' +#define BLOCK_TYPE_REF 'r' +#define BLOCK_TYPE_OBJ 'o' +#define BLOCK_TYPE_ANY 0 + +#define MAX_RESTARTS ((1 << 16) - 1) +#define DEFAULT_BLOCK_SIZE 4096 + +#endif diff --git a/reftable/dump.c b/reftable/dump.c new file mode 100644 index 00000000000..c0065792a4f --- /dev/null +++ b/reftable/dump.c @@ -0,0 +1,97 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#include "system.h" + +#include "reftable.h" + +static int dump_table(const char *tablename) +{ + struct block_source src = { 0 }; + int err = block_source_from_file(&src, tablename); + if (err < 0) { + return err; + } + + struct reader *r = NULL; + err = new_reader(&r, src, tablename); + if (err < 0) { + return err; + } + + { + struct iterator it = { 0 }; + err = reader_seek_ref(r, &it, ""); + if (err < 0) { + return err; + } + + struct ref_record ref = { 0 }; + while (1) { + err = iterator_next_ref(it, &ref); + if (err > 0) { + break; + } + if (err < 0) { + return err; + } + ref_record_print(&ref, 20); + } + iterator_destroy(&it); + ref_record_clear(&ref); + } + + { + struct iterator it = { 0 }; + err = reader_seek_log(r, &it, ""); + if (err < 0) { + return err; + } + struct log_record log = { 0 }; + while (1) { + err = iterator_next_log(it, &log); + if (err > 0) { + break; + } + if (err < 0) { + return err; + } + log_record_print(&log, 20); + } + iterator_destroy(&it); + log_record_clear(&log); + } + return 0; +} + +int main(int argc, char *argv[]) +{ + int opt; + const char *table = NULL; + while ((opt = getopt(argc, argv, "t:")) != -1) { + switch (opt) { + case 't': + table = xstrdup(optarg); + break; + case '?': + printf("usage: %s [-table tablefile]\n", argv[0]); + return 2; + break; + } + } + + if (table != NULL) { + int err = dump_table(table); + if (err < 0) { + fprintf(stderr, "%s: %s: %s\n", argv[0], table, + error_str(err)); + return 1; + } + } + return 0; +} diff --git a/reftable/file.c b/reftable/file.c new file mode 100644 index 00000000000..253ec400253 --- /dev/null +++ b/reftable/file.c @@ -0,0 +1,97 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#include "system.h" + +#include "block.h" +#include "iter.h" +#include "record.h" +#include "reftable.h" +#include "tree.h" + +struct file_block_source { + int fd; + uint64_t size; +}; + +static uint64_t file_size(void *b) +{ + return ((struct file_block_source *)b)->size; +} + +static void file_return_block(void *b, struct block *dest) +{ + memset(dest->data, 0xff, dest->len); + free(dest->data); +} + +static void file_close(void *b) +{ + int fd = ((struct file_block_source *)b)->fd; + if (fd > 0) { + close(fd); + ((struct file_block_source *)b)->fd = 0; + } + + free(b); +} + +static int file_read_block(void *v, struct block *dest, uint64_t off, + uint32_t size) +{ + struct file_block_source *b = (struct file_block_source *)v; + assert(off + size <= b->size); + dest->data = malloc(size); + if (pread(b->fd, dest->data, size, off) != size) { + return -1; + } + dest->len = size; + return size; +} + +struct block_source_vtable file_vtable = { + .size = &file_size, + .read_block = &file_read_block, + .return_block = &file_return_block, + .close = &file_close, +}; + +int block_source_from_file(struct block_source *bs, const char *name) +{ + struct stat st = { 0 }; + int err = 0; + int fd = open(name, O_RDONLY); + if (fd < 0) { + if (errno == ENOENT) { + return NOT_EXIST_ERROR; + } + return -1; + } + + err = fstat(fd, &st); + if (err < 0) { + return -1; + } + + { + struct file_block_source *p = + calloc(sizeof(struct file_block_source), 1); + p->size = st.st_size; + p->fd = fd; + + bs->ops = &file_vtable; + bs->arg = p; + } + return 0; +} + +int fd_writer(void *arg, byte *data, int sz) +{ + int *fdp = (int *)arg; + return write(*fdp, data, sz); +} diff --git a/reftable/iter.c b/reftable/iter.c new file mode 100644 index 00000000000..38464617c28 --- /dev/null +++ b/reftable/iter.c @@ -0,0 +1,229 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#include "iter.h" + +#include "system.h" + +#include "block.h" +#include "constants.h" +#include "reader.h" +#include "reftable.h" + +bool iterator_is_null(struct iterator it) +{ + return it.ops == NULL; +} + +static int empty_iterator_next(void *arg, struct record rec) +{ + return 1; +} + +static void empty_iterator_close(void *arg) +{ +} + +struct iterator_vtable empty_vtable = { + .next = &empty_iterator_next, + .close = &empty_iterator_close, +}; + +void iterator_set_empty(struct iterator *it) +{ + it->iter_arg = NULL; + it->ops = &empty_vtable; +} + +int iterator_next(struct iterator it, struct record rec) +{ + return it.ops->next(it.iter_arg, rec); +} + +void iterator_destroy(struct iterator *it) +{ + if (it->ops == NULL) { + return; + } + it->ops->close(it->iter_arg); + it->ops = NULL; + FREE_AND_NULL(it->iter_arg); +} + +int iterator_next_ref(struct iterator it, struct ref_record *ref) +{ + struct record rec = { 0 }; + record_from_ref(&rec, ref); + return iterator_next(it, rec); +} + +int iterator_next_log(struct iterator it, struct log_record *log) +{ + struct record rec = { 0 }; + record_from_log(&rec, log); + return iterator_next(it, rec); +} + +static void filtering_ref_iterator_close(void *iter_arg) +{ + struct filtering_ref_iterator *fri = + (struct filtering_ref_iterator *)iter_arg; + free(slice_yield(&fri->oid)); + iterator_destroy(&fri->it); +} + +static int filtering_ref_iterator_next(void *iter_arg, struct record rec) +{ + struct filtering_ref_iterator *fri = + (struct filtering_ref_iterator *)iter_arg; + struct ref_record *ref = (struct ref_record *)rec.data; + + while (true) { + int err = iterator_next_ref(fri->it, ref); + if (err != 0) { + return err; + } + + if (fri->double_check) { + struct iterator it = { 0 }; + + int err = reader_seek_ref(fri->r, &it, ref->ref_name); + if (err == 0) { + err = iterator_next_ref(it, ref); + } + + iterator_destroy(&it); + + if (err < 0) { + return err; + } + + if (err > 0) { + continue; + } + } + + if ((ref->target_value != NULL && + !memcmp(fri->oid.buf, ref->target_value, fri->oid.len)) || + (ref->value != NULL && + !memcmp(fri->oid.buf, ref->value, fri->oid.len))) { + return 0; + } + } +} + +struct iterator_vtable filtering_ref_iterator_vtable = { + .next = &filtering_ref_iterator_next, + .close = &filtering_ref_iterator_close, +}; + +void iterator_from_filtering_ref_iterator(struct iterator *it, + struct filtering_ref_iterator *fri) +{ + it->iter_arg = fri; + it->ops = &filtering_ref_iterator_vtable; +} + +static void indexed_table_ref_iter_close(void *p) +{ + struct indexed_table_ref_iter *it = (struct indexed_table_ref_iter *)p; + block_iter_close(&it->cur); + reader_return_block(it->r, &it->block_reader.block); + free(slice_yield(&it->oid)); +} + +static int indexed_table_ref_iter_next_block(struct indexed_table_ref_iter *it) +{ + if (it->offset_idx == it->offset_len) { + it->finished = true; + return 1; + } + + reader_return_block(it->r, &it->block_reader.block); + + { + uint64_t off = it->offsets[it->offset_idx++]; + int err = reader_init_block_reader(it->r, &it->block_reader, + off, BLOCK_TYPE_REF); + if (err < 0) { + return err; + } + if (err > 0) { + /* indexed block does not exist. */ + return FORMAT_ERROR; + } + } + block_reader_start(&it->block_reader, &it->cur); + return 0; +} + +static int indexed_table_ref_iter_next(void *p, struct record rec) +{ + struct indexed_table_ref_iter *it = (struct indexed_table_ref_iter *)p; + struct ref_record *ref = (struct ref_record *)rec.data; + + while (true) { + int err = block_iter_next(&it->cur, rec); + if (err < 0) { + return err; + } + + if (err > 0) { + err = indexed_table_ref_iter_next_block(it); + if (err < 0) { + return err; + } + + if (it->finished) { + return 1; + } + continue; + } + + if (!memcmp(it->oid.buf, ref->target_value, it->oid.len) || + !memcmp(it->oid.buf, ref->value, it->oid.len)) { + return 0; + } + } +} + +int new_indexed_table_ref_iter(struct indexed_table_ref_iter **dest, + struct reader *r, byte *oid, int oid_len, + uint64_t *offsets, int offset_len) +{ + struct indexed_table_ref_iter *itr = + calloc(sizeof(struct indexed_table_ref_iter), 1); + int err = 0; + + itr->r = r; + slice_resize(&itr->oid, oid_len); + memcpy(itr->oid.buf, oid, oid_len); + + itr->offsets = offsets; + itr->offset_len = offset_len; + + err = indexed_table_ref_iter_next_block(itr); + if (err < 0) { + free(itr); + } else { + *dest = itr; + } + return err; +} + +struct iterator_vtable indexed_table_ref_iter_vtable = { + .next = &indexed_table_ref_iter_next, + .close = &indexed_table_ref_iter_close, +}; + +void iterator_from_indexed_table_ref_iter(struct iterator *it, + struct indexed_table_ref_iter *itr) +{ + it->iter_arg = itr; + it->ops = &indexed_table_ref_iter_vtable; +} diff --git a/reftable/iter.h b/reftable/iter.h new file mode 100644 index 00000000000..41538c6babd --- /dev/null +++ b/reftable/iter.h @@ -0,0 +1,56 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#ifndef ITER_H +#define ITER_H + +#include "block.h" +#include "record.h" +#include "slice.h" + +struct iterator_vtable { + int (*next)(void *iter_arg, struct record rec); + void (*close)(void *iter_arg); +}; + +void iterator_set_empty(struct iterator *it); +int iterator_next(struct iterator it, struct record rec); +bool iterator_is_null(struct iterator it); + +struct filtering_ref_iterator { + bool double_check; + struct reader *r; + struct slice oid; + struct iterator it; +}; + +void iterator_from_filtering_ref_iterator(struct iterator *, + struct filtering_ref_iterator *); + +struct indexed_table_ref_iter { + struct reader *r; + struct slice oid; + + /* mutable */ + uint64_t *offsets; + + /* Points to the next offset to read. */ + int offset_idx; + int offset_len; + struct block_reader block_reader; + struct block_iter cur; + bool finished; +}; + +void iterator_from_indexed_table_ref_iter(struct iterator *it, + struct indexed_table_ref_iter *itr); +int new_indexed_table_ref_iter(struct indexed_table_ref_iter **dest, + struct reader *r, byte *oid, int oid_len, + uint64_t *offsets, int offset_len); + +#endif diff --git a/reftable/merged.c b/reftable/merged.c new file mode 100644 index 00000000000..c1e8a0aed9a --- /dev/null +++ b/reftable/merged.c @@ -0,0 +1,290 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#include "merged.h" + +#include "system.h" + +#include "constants.h" +#include "iter.h" +#include "pq.h" +#include "reader.h" + +static int merged_iter_init(struct merged_iter *mi) +{ + int i = 0; + for (i = 0; i < mi->stack_len; i++) { + struct record rec = new_record(mi->typ); + int err = iterator_next(mi->stack[i], rec); + if (err < 0) { + return err; + } + + if (err > 0) { + iterator_destroy(&mi->stack[i]); + record_clear(rec); + free(record_yield(&rec)); + } else { + struct pq_entry e = { + .rec = rec, + .index = i, + }; + merged_iter_pqueue_add(&mi->pq, e); + } + } + + return 0; +} + +static void merged_iter_close(void *p) +{ + struct merged_iter *mi = (struct merged_iter *)p; + int i = 0; + merged_iter_pqueue_clear(&mi->pq); + for (i = 0; i < mi->stack_len; i++) { + iterator_destroy(&mi->stack[i]); + } + free(mi->stack); +} + +static int merged_iter_advance_subiter(struct merged_iter *mi, int idx) +{ + if (iterator_is_null(mi->stack[idx])) { + return 0; + } + + { + struct record rec = new_record(mi->typ); + struct pq_entry e = { + .rec = rec, + .index = idx, + }; + int err = iterator_next(mi->stack[idx], rec); + if (err < 0) { + return err; + } + + if (err > 0) { + iterator_destroy(&mi->stack[idx]); + record_clear(rec); + free(record_yield(&rec)); + return 0; + } + + merged_iter_pqueue_add(&mi->pq, e); + } + return 0; +} + +static int merged_iter_next(struct merged_iter *mi, struct record rec) +{ + struct slice entry_key = { 0 }; + struct pq_entry entry = merged_iter_pqueue_remove(&mi->pq); + int err = merged_iter_advance_subiter(mi, entry.index); + if (err < 0) { + return err; + } + + record_key(entry.rec, &entry_key); + while (!merged_iter_pqueue_is_empty(mi->pq)) { + struct pq_entry top = merged_iter_pqueue_top(mi->pq); + struct slice k = { 0 }; + int err = 0, cmp = 0; + + record_key(top.rec, &k); + + cmp = slice_compare(k, entry_key); + free(slice_yield(&k)); + + if (cmp > 0) { + break; + } + + merged_iter_pqueue_remove(&mi->pq); + err = merged_iter_advance_subiter(mi, top.index); + if (err < 0) { + return err; + } + record_clear(top.rec); + free(record_yield(&top.rec)); + } + + record_copy_from(rec, entry.rec, hash_size(mi->hash_id)); + record_clear(entry.rec); + free(record_yield(&entry.rec)); + free(slice_yield(&entry_key)); + return 0; +} + +static int merged_iter_next_void(void *p, struct record rec) +{ + struct merged_iter *mi = (struct merged_iter *)p; + if (merged_iter_pqueue_is_empty(mi->pq)) { + return 1; + } + + return merged_iter_next(mi, rec); +} + +struct iterator_vtable merged_iter_vtable = { + .next = &merged_iter_next_void, + .close = &merged_iter_close, +}; + +static void iterator_from_merged_iter(struct iterator *it, + struct merged_iter *mi) +{ + it->iter_arg = mi; + it->ops = &merged_iter_vtable; +} + +int new_merged_table(struct merged_table **dest, struct reader **stack, int n, + uint32_t hash_id) +{ + uint64_t last_max = 0; + uint64_t first_min = 0; + int i = 0; + for (i = 0; i < n; i++) { + struct reader *r = stack[i]; + if (r->hash_id != hash_id) { + return FORMAT_ERROR; + } + if (i > 0 && last_max >= reader_min_update_index(r)) { + return FORMAT_ERROR; + } + if (i == 0) { + first_min = reader_min_update_index(r); + } + + last_max = reader_max_update_index(r); + } + + { + struct merged_table m = { + .stack = stack, + .stack_len = n, + .min = first_min, + .max = last_max, + .hash_id = hash_id, + }; + + *dest = calloc(sizeof(struct merged_table), 1); + **dest = m; + } + return 0; +} + +void merged_table_close(struct merged_table *mt) +{ + int i = 0; + for (i = 0; i < mt->stack_len; i++) { + reader_free(mt->stack[i]); + } + FREE_AND_NULL(mt->stack); + mt->stack_len = 0; +} + +/* clears the list of subtable, without affecting the readers themselves. */ +void merged_table_clear(struct merged_table *mt) +{ + FREE_AND_NULL(mt->stack); + mt->stack_len = 0; +} + +void merged_table_free(struct merged_table *mt) +{ + if (mt == NULL) { + return; + } + merged_table_clear(mt); + free(mt); +} + +uint64_t merged_max_update_index(struct merged_table *mt) +{ + return mt->max; +} + +uint64_t merged_min_update_index(struct merged_table *mt) +{ + return mt->min; +} + +static int merged_table_seek_record(struct merged_table *mt, + struct iterator *it, struct record rec) +{ + struct iterator *iters = calloc(sizeof(struct iterator), mt->stack_len); + struct merged_iter merged = { + .stack = iters, + .typ = record_type(rec), + .hash_id = mt->hash_id, + }; + int n = 0; + int err = 0; + int i = 0; + for (i = 0; i < mt->stack_len && err == 0; i++) { + int e = reader_seek(mt->stack[i], &iters[n], rec); + if (e < 0) { + err = e; + } + if (e == 0) { + n++; + } + } + if (err < 0) { + int i = 0; + for (i = 0; i < n; i++) { + iterator_destroy(&iters[i]); + } + free(iters); + return err; + } + + merged.stack_len = n, err = merged_iter_init(&merged); + if (err < 0) { + merged_iter_close(&merged); + return err; + } + + { + struct merged_iter *p = malloc(sizeof(struct merged_iter)); + *p = merged; + iterator_from_merged_iter(it, p); + } + return 0; +} + +int merged_table_seek_ref(struct merged_table *mt, struct iterator *it, + const char *name) +{ + struct ref_record ref = { + .ref_name = (char *)name, + }; + struct record rec = { 0 }; + record_from_ref(&rec, &ref); + return merged_table_seek_record(mt, it, rec); +} + +int merged_table_seek_log_at(struct merged_table *mt, struct iterator *it, + const char *name, uint64_t update_index) +{ + struct log_record log = { + .ref_name = (char *)name, + .update_index = update_index, + }; + struct record rec = { 0 }; + record_from_log(&rec, &log); + return merged_table_seek_record(mt, it, rec); +} + +int merged_table_seek_log(struct merged_table *mt, struct iterator *it, + const char *name) +{ + uint64_t max = ~((uint64_t)0); + return merged_table_seek_log_at(mt, it, name, max); +} diff --git a/reftable/merged.h b/reftable/merged.h new file mode 100644 index 00000000000..f2b20c5a26e --- /dev/null +++ b/reftable/merged.h @@ -0,0 +1,34 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#ifndef MERGED_H +#define MERGED_H + +#include "pq.h" +#include "reftable.h" + +struct merged_table { + struct reader **stack; + int stack_len; + uint32_t hash_id; + + uint64_t min; + uint64_t max; +}; + +struct merged_iter { + struct iterator *stack; + uint32_t hash_id; + int stack_len; + byte typ; + struct merged_iter_pqueue pq; +} merged_iter; + +void merged_table_clear(struct merged_table *mt); + +#endif diff --git a/reftable/pq.c b/reftable/pq.c new file mode 100644 index 00000000000..8b1f54a5bb3 --- /dev/null +++ b/reftable/pq.c @@ -0,0 +1,114 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#include "pq.h" + +#include "system.h" + +int pq_less(struct pq_entry a, struct pq_entry b) +{ + struct slice ak = { 0 }; + struct slice bk = { 0 }; + int cmp = 0; + record_key(a.rec, &ak); + record_key(b.rec, &bk); + + cmp = slice_compare(ak, bk); + + free(slice_yield(&ak)); + free(slice_yield(&bk)); + + if (cmp == 0) { + return a.index > b.index; + } + + return cmp < 0; +} + +struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq) +{ + return pq.heap[0]; +} + +bool merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq) +{ + return pq.len == 0; +} + +void merged_iter_pqueue_check(struct merged_iter_pqueue pq) +{ + int i = 0; + for (i = 1; i < pq.len; i++) { + int parent = (i - 1) / 2; + + assert(pq_less(pq.heap[parent], pq.heap[i])); + } +} + +struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq) +{ + int i = 0; + struct pq_entry e = pq->heap[0]; + pq->heap[0] = pq->heap[pq->len - 1]; + pq->len--; + + i = 0; + while (i < pq->len) { + int min = i; + int j = 2 * i + 1; + int k = 2 * i + 2; + if (j < pq->len && pq_less(pq->heap[j], pq->heap[i])) { + min = j; + } + if (k < pq->len && pq_less(pq->heap[k], pq->heap[min])) { + min = k; + } + + if (min == i) { + break; + } + + SWAP(pq->heap[i], pq->heap[min]); + i = min; + } + + return e; +} + +void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry e) +{ + int i = 0; + if (pq->len == pq->cap) { + pq->cap = 2 * pq->cap + 1; + pq->heap = realloc(pq->heap, pq->cap * sizeof(struct pq_entry)); + } + + pq->heap[pq->len++] = e; + i = pq->len - 1; + while (i > 0) { + int j = (i - 1) / 2; + if (pq_less(pq->heap[j], pq->heap[i])) { + break; + } + + SWAP(pq->heap[j], pq->heap[i]); + + i = j; + } +} + +void merged_iter_pqueue_clear(struct merged_iter_pqueue *pq) +{ + int i = 0; + for (i = 0; i < pq->len; i++) { + record_clear(pq->heap[i].rec); + free(record_yield(&pq->heap[i].rec)); + } + FREE_AND_NULL(pq->heap); + pq->len = pq->cap = 0; +} diff --git a/reftable/pq.h b/reftable/pq.h new file mode 100644 index 00000000000..b585a52ee14 --- /dev/null +++ b/reftable/pq.h @@ -0,0 +1,34 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#ifndef PQ_H +#define PQ_H + +#include "record.h" + +struct pq_entry { + int index; + struct record rec; +}; + +int pq_less(struct pq_entry a, struct pq_entry b); + +struct merged_iter_pqueue { + struct pq_entry *heap; + int len; + int cap; +}; + +struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq); +bool merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq); +void merged_iter_pqueue_check(struct merged_iter_pqueue pq); +struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq); +void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry e); +void merged_iter_pqueue_clear(struct merged_iter_pqueue *pq); + +#endif diff --git a/reftable/reader.c b/reftable/reader.c new file mode 100644 index 00000000000..90542d79e42 --- /dev/null +++ b/reftable/reader.c @@ -0,0 +1,720 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#include "reader.h" + +#include "system.h" + +#include "block.h" +#include "constants.h" +#include "iter.h" +#include "record.h" +#include "reftable.h" +#include "tree.h" + +uint64_t block_source_size(struct block_source source) +{ + return source.ops->size(source.arg); +} + +int block_source_read_block(struct block_source source, struct block *dest, + uint64_t off, uint32_t size) +{ + int result = source.ops->read_block(source.arg, dest, off, size); + dest->source = source; + return result; +} + +void block_source_return_block(struct block_source source, struct block *blockp) +{ + source.ops->return_block(source.arg, blockp); + blockp->data = NULL; + blockp->len = 0; + blockp->source.ops = NULL; + blockp->source.arg = NULL; +} + +void block_source_close(struct block_source *source) +{ + if (source->ops == NULL) { + return; + } + + source->ops->close(source->arg); + source->ops = NULL; +} + +static struct reader_offsets *reader_offsets_for(struct reader *r, byte typ) +{ + switch (typ) { + case BLOCK_TYPE_REF: + return &r->ref_offsets; + case BLOCK_TYPE_LOG: + return &r->log_offsets; + case BLOCK_TYPE_OBJ: + return &r->obj_offsets; + } + abort(); +} + +static int reader_get_block(struct reader *r, struct block *dest, uint64_t off, + uint32_t sz) +{ + if (off >= r->size) { + return 0; + } + + if (off + sz > r->size) { + sz = r->size - off; + } + + return block_source_read_block(r->source, dest, off, sz); +} + +void reader_return_block(struct reader *r, struct block *p) +{ + block_source_return_block(r->source, p); +} + +uint32_t reader_hash_id(struct reader *r) +{ + return r->hash_id; +} + +const char *reader_name(struct reader *r) +{ + return r->name; +} + +static int parse_footer(struct reader *r, byte *footer, byte *header) +{ + byte *f = footer; + int err = 0; + if (memcmp(f, "REFT", 4)) { + err = FORMAT_ERROR; + goto exit; + } + f += 4; + + if (memcmp(footer, header, HEADER_SIZE)) { + err = FORMAT_ERROR; + goto exit; + } + + r->hash_id = SHA1_ID; + { + byte version = *f++; + if (version == 2) { + /* DO NOT SUBMIT. Not yet in the standard. */ + r->hash_id = SHA256_ID; + version = 1; + } + if (version != 1) { + err = FORMAT_ERROR; + goto exit; + } + } + + r->block_size = get_be24(f); + + f += 3; + r->min_update_index = get_be64(f); + f += 8; + r->max_update_index = get_be64(f); + f += 8; + + r->ref_offsets.index_offset = get_be64(f); + f += 8; + + r->obj_offsets.offset = get_be64(f); + f += 8; + + r->object_id_len = r->obj_offsets.offset & ((1 << 5) - 1); + r->obj_offsets.offset >>= 5; + + r->obj_offsets.index_offset = get_be64(f); + f += 8; + r->log_offsets.offset = get_be64(f); + f += 8; + r->log_offsets.index_offset = get_be64(f); + f += 8; + + { + uint32_t computed_crc = crc32(0, footer, f - footer); + uint32_t file_crc = get_be32(f); + f += 4; + if (computed_crc != file_crc) { + err = FORMAT_ERROR; + goto exit; + } + } + + { + byte first_block_typ = header[HEADER_SIZE]; + r->ref_offsets.present = (first_block_typ == BLOCK_TYPE_REF); + r->ref_offsets.offset = 0; + r->log_offsets.present = (first_block_typ == BLOCK_TYPE_LOG || + r->log_offsets.offset > 0); + r->obj_offsets.present = r->obj_offsets.offset > 0; + } + err = 0; +exit: + return err; +} + +int init_reader(struct reader *r, struct block_source source, const char *name) +{ + struct block footer = { 0 }; + struct block header = { 0 }; + int err = 0; + + memset(r, 0, sizeof(struct reader)); + r->size = block_source_size(source) - FOOTER_SIZE; + r->source = source; + r->name = xstrdup(name); + r->hash_id = 0; + + err = block_source_read_block(source, &footer, r->size, FOOTER_SIZE); + if (err != FOOTER_SIZE) { + err = IO_ERROR; + goto exit; + } + + /* Need +1 to read type of first block. */ + err = reader_get_block(r, &header, 0, HEADER_SIZE + 1); + if (err != HEADER_SIZE + 1) { + err = IO_ERROR; + goto exit; + } + + err = parse_footer(r, footer.data, header.data); +exit: + block_source_return_block(r->source, &footer); + block_source_return_block(r->source, &header); + return err; +} + +struct table_iter { + struct reader *r; + byte typ; + uint64_t block_off; + struct block_iter bi; + bool finished; +}; + +static void table_iter_copy_from(struct table_iter *dest, + struct table_iter *src) +{ + dest->r = src->r; + dest->typ = src->typ; + dest->block_off = src->block_off; + dest->finished = src->finished; + block_iter_copy_from(&dest->bi, &src->bi); +} + +static int table_iter_next_in_block(struct table_iter *ti, struct record rec) +{ + int res = block_iter_next(&ti->bi, rec); + if (res == 0 && record_type(rec) == BLOCK_TYPE_REF) { + ((struct ref_record *)rec.data)->update_index += + ti->r->min_update_index; + } + + return res; +} + +static void table_iter_block_done(struct table_iter *ti) +{ + if (ti->bi.br == NULL) { + return; + } + reader_return_block(ti->r, &ti->bi.br->block); + FREE_AND_NULL(ti->bi.br); + + ti->bi.last_key.len = 0; + ti->bi.next_off = 0; +} + +static int32_t extract_block_size(byte *data, byte *typ, uint64_t off) +{ + int32_t result = 0; + + if (off == 0) { + data += 24; + } + + *typ = data[0]; + if (is_block_type(*typ)) { + result = get_be24(data + 1); + } + return result; +} + +int reader_init_block_reader(struct reader *r, struct block_reader *br, + uint64_t next_off, byte want_typ) +{ + int32_t guess_block_size = r->block_size ? r->block_size : + DEFAULT_BLOCK_SIZE; + struct block block = { 0 }; + byte block_typ = 0; + int err = 0; + uint32_t header_off = next_off ? 0 : HEADER_SIZE; + int32_t block_size = 0; + + if (next_off >= r->size) { + return 1; + } + + err = reader_get_block(r, &block, next_off, guess_block_size); + if (err < 0) { + return err; + } + + block_size = extract_block_size(block.data, &block_typ, next_off); + if (block_size < 0) { + return block_size; + } + + if (want_typ != BLOCK_TYPE_ANY && block_typ != want_typ) { + reader_return_block(r, &block); + return 1; + } + + if (block_size > guess_block_size) { + reader_return_block(r, &block); + err = reader_get_block(r, &block, next_off, block_size); + if (err < 0) { + return err; + } + } + + return block_reader_init(br, &block, header_off, r->block_size, + hash_size(r->hash_id)); +} + +static int table_iter_next_block(struct table_iter *dest, + struct table_iter *src) +{ + uint64_t next_block_off = src->block_off + src->bi.br->full_block_size; + struct block_reader br = { 0 }; + int err = 0; + + dest->r = src->r; + dest->typ = src->typ; + dest->block_off = next_block_off; + + err = reader_init_block_reader(src->r, &br, next_block_off, src->typ); + if (err > 0) { + dest->finished = true; + return 1; + } + if (err != 0) { + return err; + } + + { + struct block_reader *brp = malloc(sizeof(struct block_reader)); + *brp = br; + + dest->finished = false; + block_reader_start(brp, &dest->bi); + } + return 0; +} + +static int table_iter_next(struct table_iter *ti, struct record rec) +{ + if (record_type(rec) != ti->typ) { + return API_ERROR; + } + + while (true) { + struct table_iter next = { 0 }; + int err = 0; + if (ti->finished) { + return 1; + } + + err = table_iter_next_in_block(ti, rec); + if (err <= 0) { + return err; + } + + err = table_iter_next_block(&next, ti); + if (err != 0) { + ti->finished = true; + } + table_iter_block_done(ti); + if (err != 0) { + return err; + } + table_iter_copy_from(ti, &next); + block_iter_close(&next.bi); + } +} + +static int table_iter_next_void(void *ti, struct record rec) +{ + return table_iter_next((struct table_iter *)ti, rec); +} + +static void table_iter_close(void *p) +{ + struct table_iter *ti = (struct table_iter *)p; + table_iter_block_done(ti); + block_iter_close(&ti->bi); +} + +struct iterator_vtable table_iter_vtable = { + .next = &table_iter_next_void, + .close = &table_iter_close, +}; + +static void iterator_from_table_iter(struct iterator *it, struct table_iter *ti) +{ + it->iter_arg = ti; + it->ops = &table_iter_vtable; +} + +static int reader_table_iter_at(struct reader *r, struct table_iter *ti, + uint64_t off, byte typ) +{ + struct block_reader br = { 0 }; + struct block_reader *brp = NULL; + + int err = reader_init_block_reader(r, &br, off, typ); + if (err != 0) { + return err; + } + + brp = malloc(sizeof(struct block_reader)); + *brp = br; + ti->r = r; + ti->typ = block_reader_type(brp); + ti->block_off = off; + block_reader_start(brp, &ti->bi); + return 0; +} + +static int reader_start(struct reader *r, struct table_iter *ti, byte typ, + bool index) +{ + struct reader_offsets *offs = reader_offsets_for(r, typ); + uint64_t off = offs->offset; + if (index) { + off = offs->index_offset; + if (off == 0) { + return 1; + } + typ = BLOCK_TYPE_INDEX; + } + + return reader_table_iter_at(r, ti, off, typ); +} + +static int reader_seek_linear(struct reader *r, struct table_iter *ti, + struct record want) +{ + struct record rec = new_record(record_type(want)); + struct slice want_key = { 0 }; + struct slice got_key = { 0 }; + struct table_iter next = { 0 }; + int err = -1; + record_key(want, &want_key); + + while (true) { + err = table_iter_next_block(&next, ti); + if (err < 0) { + goto exit; + } + + if (err > 0) { + break; + } + + err = block_reader_first_key(next.bi.br, &got_key); + if (err < 0) { + goto exit; + } + { + int cmp = slice_compare(got_key, want_key); + if (cmp > 0) { + table_iter_block_done(&next); + break; + } + } + + table_iter_block_done(ti); + table_iter_copy_from(ti, &next); + } + + err = block_iter_seek(&ti->bi, want_key); + if (err < 0) { + goto exit; + } + err = 0; + +exit: + block_iter_close(&next.bi); + record_clear(rec); + free(record_yield(&rec)); + free(slice_yield(&want_key)); + free(slice_yield(&got_key)); + return err; +} + +static int reader_seek_indexed(struct reader *r, struct iterator *it, + struct record rec) +{ + struct index_record want_index = { 0 }; + struct record want_index_rec = { 0 }; + struct index_record index_result = { 0 }; + struct record index_result_rec = { 0 }; + struct table_iter index_iter = { 0 }; + struct table_iter next = { 0 }; + int err = 0; + + record_key(rec, &want_index.last_key); + record_from_index(&want_index_rec, &want_index); + record_from_index(&index_result_rec, &index_result); + + err = reader_start(r, &index_iter, record_type(rec), true); + if (err < 0) { + goto exit; + } + + err = reader_seek_linear(r, &index_iter, want_index_rec); + while (true) { + err = table_iter_next(&index_iter, index_result_rec); + table_iter_block_done(&index_iter); + if (err != 0) { + goto exit; + } + + err = reader_table_iter_at(r, &next, index_result.offset, 0); + if (err != 0) { + goto exit; + } + + err = block_iter_seek(&next.bi, want_index.last_key); + if (err < 0) { + goto exit; + } + + if (next.typ == record_type(rec)) { + err = 0; + break; + } + + if (next.typ != BLOCK_TYPE_INDEX) { + err = FORMAT_ERROR; + break; + } + + table_iter_copy_from(&index_iter, &next); + } + + if (err == 0) { + struct table_iter *malloced = + calloc(sizeof(struct table_iter), 1); + table_iter_copy_from(malloced, &next); + iterator_from_table_iter(it, malloced); + } +exit: + block_iter_close(&next.bi); + table_iter_close(&index_iter); + record_clear(want_index_rec); + record_clear(index_result_rec); + return err; +} + +static int reader_seek_internal(struct reader *r, struct iterator *it, + struct record rec) +{ + struct reader_offsets *offs = reader_offsets_for(r, record_type(rec)); + uint64_t idx = offs->index_offset; + struct table_iter ti = { 0 }; + int err = 0; + if (idx > 0) { + return reader_seek_indexed(r, it, rec); + } + + err = reader_start(r, &ti, record_type(rec), false); + if (err < 0) { + return err; + } + err = reader_seek_linear(r, &ti, rec); + if (err < 0) { + return err; + } + + { + struct table_iter *p = malloc(sizeof(struct table_iter)); + *p = ti; + iterator_from_table_iter(it, p); + } + + return 0; +} + +int reader_seek(struct reader *r, struct iterator *it, struct record rec) +{ + byte typ = record_type(rec); + + struct reader_offsets *offs = reader_offsets_for(r, typ); + if (!offs->present) { + iterator_set_empty(it); + return 0; + } + + return reader_seek_internal(r, it, rec); +} + +int reader_seek_ref(struct reader *r, struct iterator *it, const char *name) +{ + struct ref_record ref = { + .ref_name = (char *)name, + }; + struct record rec = { 0 }; + record_from_ref(&rec, &ref); + return reader_seek(r, it, rec); +} + +int reader_seek_log_at(struct reader *r, struct iterator *it, const char *name, + uint64_t update_index) +{ + struct log_record log = { + .ref_name = (char *)name, + .update_index = update_index, + }; + struct record rec = { 0 }; + record_from_log(&rec, &log); + return reader_seek(r, it, rec); +} + +int reader_seek_log(struct reader *r, struct iterator *it, const char *name) +{ + uint64_t max = ~((uint64_t)0); + return reader_seek_log_at(r, it, name, max); +} + +void reader_close(struct reader *r) +{ + block_source_close(&r->source); + FREE_AND_NULL(r->name); +} + +int new_reader(struct reader **p, struct block_source src, char const *name) +{ + struct reader *rd = calloc(sizeof(struct reader), 1); + int err = init_reader(rd, src, name); + if (err == 0) { + *p = rd; + } else { + free(rd); + } + return err; +} + +void reader_free(struct reader *r) +{ + reader_close(r); + free(r); +} + +static int reader_refs_for_indexed(struct reader *r, struct iterator *it, + byte *oid) +{ + struct obj_record want = { + .hash_prefix = oid, + .hash_prefix_len = r->object_id_len, + }; + struct record want_rec = { 0 }; + struct iterator oit = { 0 }; + struct obj_record got = { 0 }; + struct record got_rec = { 0 }; + int err = 0; + + record_from_obj(&want_rec, &want); + + err = reader_seek(r, &oit, want_rec); + if (err != 0) { + return err; + } + + record_from_obj(&got_rec, &got); + err = iterator_next(oit, got_rec); + iterator_destroy(&oit); + if (err < 0) { + return err; + } + + if (err > 0 || + memcmp(want.hash_prefix, got.hash_prefix, r->object_id_len)) { + iterator_set_empty(it); + return 0; + } + + { + struct indexed_table_ref_iter *itr = NULL; + err = new_indexed_table_ref_iter(&itr, r, oid, + hash_size(r->hash_id), + got.offsets, got.offset_len); + if (err < 0) { + record_clear(got_rec); + return err; + } + got.offsets = NULL; + record_clear(got_rec); + + iterator_from_indexed_table_ref_iter(it, itr); + } + + return 0; +} + +static int reader_refs_for_unindexed(struct reader *r, struct iterator *it, + byte *oid, int oid_len) +{ + struct table_iter *ti = calloc(sizeof(struct table_iter), 1); + struct filtering_ref_iterator *filter = NULL; + int err = reader_start(r, ti, BLOCK_TYPE_REF, false); + if (err < 0) { + free(ti); + return err; + } + + filter = calloc(sizeof(struct filtering_ref_iterator), 1); + slice_resize(&filter->oid, oid_len); + memcpy(filter->oid.buf, oid, oid_len); + filter->r = r; + filter->double_check = false; + iterator_from_table_iter(&filter->it, ti); + + iterator_from_filtering_ref_iterator(it, filter); + return 0; +} + +int reader_refs_for(struct reader *r, struct iterator *it, byte *oid, + int oid_len) +{ + if (r->obj_offsets.present) { + return reader_refs_for_indexed(r, it, oid); + } + return reader_refs_for_unindexed(r, it, oid, oid_len); +} + +uint64_t reader_max_update_index(struct reader *r) +{ + return r->max_update_index; +} + +uint64_t reader_min_update_index(struct reader *r) +{ + return r->min_update_index; +} diff --git a/reftable/reader.h b/reftable/reader.h new file mode 100644 index 00000000000..4ea37c4cea6 --- /dev/null +++ b/reftable/reader.h @@ -0,0 +1,52 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#ifndef READER_H +#define READER_H + +#include "block.h" +#include "record.h" +#include "reftable.h" + +uint64_t block_source_size(struct block_source source); + +int block_source_read_block(struct block_source source, struct block *dest, + uint64_t off, uint32_t size); +void block_source_return_block(struct block_source source, struct block *ret); +void block_source_close(struct block_source *source); + +struct reader_offsets { + bool present; + uint64_t offset; + uint64_t index_offset; +}; + +struct reader { + char *name; + struct block_source source; + uint32_t hash_id; + uint64_t size; + uint32_t block_size; + uint64_t min_update_index; + uint64_t max_update_index; + int object_id_len; + + struct reader_offsets ref_offsets; + struct reader_offsets obj_offsets; + struct reader_offsets log_offsets; +}; + +int init_reader(struct reader *r, struct block_source source, const char *name); +int reader_seek(struct reader *r, struct iterator *it, struct record rec); +void reader_close(struct reader *r); +const char *reader_name(struct reader *r); +void reader_return_block(struct reader *r, struct block *p); +int reader_init_block_reader(struct reader *r, struct block_reader *br, + uint64_t next_off, byte want_typ); + +#endif diff --git a/reftable/record.c b/reftable/record.c new file mode 100644 index 00000000000..a839aa14b2c --- /dev/null +++ b/reftable/record.c @@ -0,0 +1,1119 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#include "record.h" + +#include "system.h" + +#include "constants.h" +#include "reftable.h" + +int is_block_type(byte typ) +{ + switch (typ) { + case BLOCK_TYPE_REF: + case BLOCK_TYPE_LOG: + case BLOCK_TYPE_OBJ: + case BLOCK_TYPE_INDEX: + return true; + } + return false; +} + +int get_var_int(uint64_t *dest, struct slice in) +{ + int ptr = 0; + uint64_t val; + + if (in.len == 0) { + return -1; + } + val = in.buf[ptr] & 0x7f; + + while (in.buf[ptr] & 0x80) { + ptr++; + if (ptr > in.len) { + return -1; + } + val = (val + 1) << 7 | (uint64_t)(in.buf[ptr] & 0x7f); + } + + *dest = val; + return ptr + 1; +} + +int put_var_int(struct slice dest, uint64_t val) +{ + byte buf[10] = { 0 }; + int i = 9; + buf[i] = (byte)(val & 0x7f); + i--; + while (true) { + val >>= 7; + if (!val) { + break; + } + val--; + buf[i] = 0x80 | (byte)(val & 0x7f); + i--; + } + + { + int n = sizeof(buf) - i - 1; + if (dest.len < n) { + return -1; + } + memcpy(dest.buf, &buf[i + 1], n); + return n; + } +} + +int common_prefix_size(struct slice a, struct slice b) +{ + int p = 0; + while (p < a.len && p < b.len) { + if (a.buf[p] != b.buf[p]) { + break; + } + p++; + } + + return p; +} + +static int decode_string(struct slice *dest, struct slice in) +{ + int start_len = in.len; + uint64_t tsize = 0; + int n = get_var_int(&tsize, in); + if (n <= 0) { + return -1; + } + in.buf += n; + in.len -= n; + if (in.len < tsize) { + return -1; + } + + slice_resize(dest, tsize + 1); + dest->buf[tsize] = 0; + memcpy(dest->buf, in.buf, tsize); + in.buf += tsize; + in.len -= tsize; + + return start_len - in.len; +} + +int encode_key(bool *restart, struct slice dest, struct slice prev_key, + struct slice key, byte extra) +{ + struct slice start = dest; + int prefix_len = common_prefix_size(prev_key, key); + uint64_t suffix_len = key.len - prefix_len; + int n = put_var_int(dest, (uint64_t)prefix_len); + if (n < 0) { + return -1; + } + dest.buf += n; + dest.len -= n; + + *restart = (prefix_len == 0); + + n = put_var_int(dest, suffix_len << 3 | (uint64_t)extra); + if (n < 0) { + return -1; + } + dest.buf += n; + dest.len -= n; + + if (dest.len < suffix_len) { + return -1; + } + memcpy(dest.buf, key.buf + prefix_len, suffix_len); + dest.buf += suffix_len; + dest.len -= suffix_len; + + return start.len - dest.len; +} + +static byte ref_record_type(void) +{ + return BLOCK_TYPE_REF; +} + +static void ref_record_key(const void *r, struct slice *dest) +{ + const struct ref_record *rec = (const struct ref_record *)r; + slice_set_string(dest, rec->ref_name); +} + +static void ref_record_copy_from(void *rec, const void *src_rec, int hash_size) +{ + struct ref_record *ref = (struct ref_record *)rec; + struct ref_record *src = (struct ref_record *)src_rec; + assert(hash_size > 0); + + /* This is simple and correct, but we could probably reuse the hash + fields. */ + ref_record_clear(ref); + if (src->ref_name != NULL) { + ref->ref_name = xstrdup(src->ref_name); + } + + if (src->target != NULL) { + ref->target = xstrdup(src->target); + } + + if (src->target_value != NULL) { + ref->target_value = malloc(hash_size); + memcpy(ref->target_value, src->target_value, hash_size); + } + + if (src->value != NULL) { + ref->value = malloc(hash_size); + memcpy(ref->value, src->value, hash_size); + } + ref->update_index = src->update_index; +} + +static char hexdigit(int c) +{ + if (c <= 9) { + return '0' + c; + } + return 'a' + (c - 10); +} + +static void hex_format(char *dest, byte *src, int hash_size) +{ + assert(hash_size > 0); + if (src != NULL) { + int i = 0; + for (i = 0; i < hash_size; i++) { + dest[2 * i] = hexdigit(src[i] >> 4); + dest[2 * i + 1] = hexdigit(src[i] & 0xf); + } + dest[2 * hash_size] = 0; + } +} + +void ref_record_print(struct ref_record *ref, int hash_size) +{ + char hex[SHA256_SIZE + 1] = { 0 }; + + printf("ref{%s(%" PRIu64 ") ", ref->ref_name, ref->update_index); + if (ref->value != NULL) { + hex_format(hex, ref->value, hash_size); + printf("%s", hex); + } + if (ref->target_value != NULL) { + hex_format(hex, ref->target_value, hash_size); + printf(" (T %s)", hex); + } + if (ref->target != NULL) { + printf("=> %s", ref->target); + } + printf("}\n"); +} + +static void ref_record_clear_void(void *rec) +{ + ref_record_clear((struct ref_record *)rec); +} + +void ref_record_clear(struct ref_record *ref) +{ + free(ref->ref_name); + free(ref->target); + free(ref->target_value); + free(ref->value); + memset(ref, 0, sizeof(struct ref_record)); +} + +static byte ref_record_val_type(const void *rec) +{ + const struct ref_record *r = (const struct ref_record *)rec; + if (r->value != NULL) { + if (r->target_value != NULL) { + return 2; + } else { + return 1; + } + } else if (r->target != NULL) { + return 3; + } + return 0; +} + +static int encode_string(char *str, struct slice s) +{ + struct slice start = s; + int l = strlen(str); + int n = put_var_int(s, l); + if (n < 0) { + return -1; + } + s.buf += n; + s.len -= n; + if (s.len < l) { + return -1; + } + memcpy(s.buf, str, l); + s.buf += l; + s.len -= l; + + return start.len - s.len; +} + +static int ref_record_encode(const void *rec, struct slice s, int hash_size) +{ + const struct ref_record *r = (const struct ref_record *)rec; + struct slice start = s; + int n = put_var_int(s, r->update_index); + assert(hash_size > 0); + if (n < 0) { + return -1; + } + s.buf += n; + s.len -= n; + + if (r->value != NULL) { + if (s.len < hash_size) { + return -1; + } + memcpy(s.buf, r->value, hash_size); + s.buf += hash_size; + s.len -= hash_size; + } + + if (r->target_value != NULL) { + if (s.len < hash_size) { + return -1; + } + memcpy(s.buf, r->target_value, hash_size); + s.buf += hash_size; + s.len -= hash_size; + } + + if (r->target != NULL) { + int n = encode_string(r->target, s); + if (n < 0) { + return -1; + } + s.buf += n; + s.len -= n; + } + + return start.len - s.len; +} + +static int ref_record_decode(void *rec, struct slice key, byte val_type, + struct slice in, int hash_size) +{ + struct ref_record *r = (struct ref_record *)rec; + struct slice start = in; + bool seen_value = false; + bool seen_target_value = false; + bool seen_target = false; + + int n = get_var_int(&r->update_index, in); + if (n < 0) { + return n; + } + assert(hash_size > 0); + + in.buf += n; + in.len -= n; + + r->ref_name = realloc(r->ref_name, key.len + 1); + memcpy(r->ref_name, key.buf, key.len); + r->ref_name[key.len] = 0; + + switch (val_type) { + case 1: + case 2: + if (in.len < hash_size) { + return -1; + } + + if (r->value == NULL) { + r->value = malloc(hash_size); + } + seen_value = true; + memcpy(r->value, in.buf, hash_size); + in.buf += hash_size; + in.len -= hash_size; + if (val_type == 1) { + break; + } + if (r->target_value == NULL) { + r->target_value = malloc(hash_size); + } + seen_target_value = true; + memcpy(r->target_value, in.buf, hash_size); + in.buf += hash_size; + in.len -= hash_size; + break; + case 3: { + struct slice dest = { 0 }; + int n = decode_string(&dest, in); + if (n < 0) { + return -1; + } + in.buf += n; + in.len -= n; + seen_target = true; + r->target = (char *)slice_as_string(&dest); + } break; + + case 0: + break; + default: + abort(); + break; + } + + if (!seen_target && r->target != NULL) { + FREE_AND_NULL(r->target); + } + if (!seen_target_value && r->target_value != NULL) { + FREE_AND_NULL(r->target_value); + } + if (!seen_value && r->value != NULL) { + FREE_AND_NULL(r->value); + } + + return start.len - in.len; +} + +int decode_key(struct slice *key, byte *extra, struct slice last_key, + struct slice in) +{ + int start_len = in.len; + uint64_t prefix_len = 0; + uint64_t suffix_len = 0; + int n = get_var_int(&prefix_len, in); + if (n < 0) { + return -1; + } + in.buf += n; + in.len -= n; + + if (prefix_len > last_key.len) { + return -1; + } + + n = get_var_int(&suffix_len, in); + if (n <= 0) { + return -1; + } + in.buf += n; + in.len -= n; + + *extra = (byte)(suffix_len & 0x7); + suffix_len >>= 3; + + if (in.len < suffix_len) { + return -1; + } + + slice_resize(key, suffix_len + prefix_len); + memcpy(key->buf, last_key.buf, prefix_len); + + memcpy(key->buf + prefix_len, in.buf, suffix_len); + in.buf += suffix_len; + in.len -= suffix_len; + + return start_len - in.len; +} + +struct record_vtable ref_record_vtable = { + .key = &ref_record_key, + .type = &ref_record_type, + .copy_from = &ref_record_copy_from, + .val_type = &ref_record_val_type, + .encode = &ref_record_encode, + .decode = &ref_record_decode, + .clear = &ref_record_clear_void, +}; + +static byte obj_record_type(void) +{ + return BLOCK_TYPE_OBJ; +} + +static void obj_record_key(const void *r, struct slice *dest) +{ + const struct obj_record *rec = (const struct obj_record *)r; + slice_resize(dest, rec->hash_prefix_len); + memcpy(dest->buf, rec->hash_prefix, rec->hash_prefix_len); +} + +static void obj_record_copy_from(void *rec, const void *src_rec, int hash_size) +{ + struct obj_record *ref = (struct obj_record *)rec; + const struct obj_record *src = (const struct obj_record *)src_rec; + + *ref = *src; + ref->hash_prefix = malloc(ref->hash_prefix_len); + memcpy(ref->hash_prefix, src->hash_prefix, ref->hash_prefix_len); + + { + int olen = ref->offset_len * sizeof(uint64_t); + ref->offsets = malloc(olen); + memcpy(ref->offsets, src->offsets, olen); + } +} + +static void obj_record_clear(void *rec) +{ + struct obj_record *ref = (struct obj_record *)rec; + FREE_AND_NULL(ref->hash_prefix); + FREE_AND_NULL(ref->offsets); + memset(ref, 0, sizeof(struct obj_record)); +} + +static byte obj_record_val_type(const void *rec) +{ + struct obj_record *r = (struct obj_record *)rec; + if (r->offset_len > 0 && r->offset_len < 8) { + return r->offset_len; + } + return 0; +} + +static int obj_record_encode(const void *rec, struct slice s, int hash_size) +{ + struct obj_record *r = (struct obj_record *)rec; + struct slice start = s; + int n = 0; + if (r->offset_len == 0 || r->offset_len >= 8) { + n = put_var_int(s, r->offset_len); + if (n < 0) { + return -1; + } + s.buf += n; + s.len -= n; + } + if (r->offset_len == 0) { + return start.len - s.len; + } + n = put_var_int(s, r->offsets[0]); + if (n < 0) { + return -1; + } + s.buf += n; + s.len -= n; + + { + uint64_t last = r->offsets[0]; + int i = 0; + for (i = 1; i < r->offset_len; i++) { + int n = put_var_int(s, r->offsets[i] - last); + if (n < 0) { + return -1; + } + s.buf += n; + s.len -= n; + last = r->offsets[i]; + } + } + return start.len - s.len; +} + +static int obj_record_decode(void *rec, struct slice key, byte val_type, + struct slice in, int hash_size) +{ + struct slice start = in; + struct obj_record *r = (struct obj_record *)rec; + uint64_t count = val_type; + int n = 0; + r->hash_prefix = malloc(key.len); + memcpy(r->hash_prefix, key.buf, key.len); + r->hash_prefix_len = key.len; + + if (val_type == 0) { + n = get_var_int(&count, in); + if (n < 0) { + return n; + } + + in.buf += n; + in.len -= n; + } + + r->offsets = NULL; + r->offset_len = 0; + if (count == 0) { + return start.len - in.len; + } + + r->offsets = malloc(count * sizeof(uint64_t)); + r->offset_len = count; + + n = get_var_int(&r->offsets[0], in); + if (n < 0) { + return n; + } + + in.buf += n; + in.len -= n; + + { + uint64_t last = r->offsets[0]; + int j = 1; + while (j < count) { + uint64_t delta = 0; + int n = get_var_int(&delta, in); + if (n < 0) { + return n; + } + + in.buf += n; + in.len -= n; + + last = r->offsets[j] = (delta + last); + j++; + } + } + return start.len - in.len; +} + +struct record_vtable obj_record_vtable = { + .key = &obj_record_key, + .type = &obj_record_type, + .copy_from = &obj_record_copy_from, + .val_type = &obj_record_val_type, + .encode = &obj_record_encode, + .decode = &obj_record_decode, + .clear = &obj_record_clear, +}; + +void log_record_print(struct log_record *log, int hash_size) +{ + char hex[SHA256_SIZE + 1] = { 0 }; + + printf("log{%s(%" PRIu64 ") %s <%s> %" PRIu64 " %04d\n", log->ref_name, + log->update_index, log->name, log->email, log->time, + log->tz_offset); + hex_format(hex, log->old_hash, hash_size); + printf("%s => ", hex); + hex_format(hex, log->new_hash, hash_size); + printf("%s\n\n%s\n}\n", hex, log->message); +} + +static byte log_record_type(void) +{ + return BLOCK_TYPE_LOG; +} + +static void log_record_key(const void *r, struct slice *dest) +{ + const struct log_record *rec = (const struct log_record *)r; + int len = strlen(rec->ref_name); + uint64_t ts = 0; + slice_resize(dest, len + 9); + memcpy(dest->buf, rec->ref_name, len + 1); + ts = (~ts) - rec->update_index; + put_be64(dest->buf + 1 + len, ts); +} + +static void log_record_copy_from(void *rec, const void *src_rec, int hash_size) +{ + struct log_record *dst = (struct log_record *)rec; + const struct log_record *src = (const struct log_record *)src_rec; + + *dst = *src; + dst->ref_name = xstrdup(dst->ref_name); + dst->email = xstrdup(dst->email); + dst->name = xstrdup(dst->name); + dst->message = xstrdup(dst->message); + if (dst->new_hash != NULL) { + dst->new_hash = malloc(hash_size); + memcpy(dst->new_hash, src->new_hash, hash_size); + } + if (dst->old_hash != NULL) { + dst->old_hash = malloc(hash_size); + memcpy(dst->old_hash, src->old_hash, hash_size); + } +} + +static void log_record_clear_void(void *rec) +{ + struct log_record *r = (struct log_record *)rec; + log_record_clear(r); +} + +void log_record_clear(struct log_record *r) +{ + free(r->ref_name); + free(r->new_hash); + free(r->old_hash); + free(r->name); + free(r->email); + free(r->message); + memset(r, 0, sizeof(struct log_record)); +} + +static byte log_record_val_type(const void *rec) +{ + return 1; +} + +static byte zero[SHA256_SIZE] = { 0 }; + +static int log_record_encode(const void *rec, struct slice s, int hash_size) +{ + struct log_record *r = (struct log_record *)rec; + struct slice start = s; + int n = 0; + byte *oldh = r->old_hash; + byte *newh = r->new_hash; + if (oldh == NULL) { + oldh = zero; + } + if (newh == NULL) { + newh = zero; + } + + if (s.len < 2 * hash_size) { + return -1; + } + + memcpy(s.buf, oldh, hash_size); + memcpy(s.buf + hash_size, newh, hash_size); + s.buf += 2 * hash_size; + s.len -= 2 * hash_size; + + n = encode_string(r->name ? r->name : "", s); + if (n < 0) { + return -1; + } + s.len -= n; + s.buf += n; + + n = encode_string(r->email ? r->email : "", s); + if (n < 0) { + return -1; + } + s.len -= n; + s.buf += n; + + n = put_var_int(s, r->time); + if (n < 0) { + return -1; + } + s.buf += n; + s.len -= n; + + if (s.len < 2) { + return -1; + } + + put_be16(s.buf, r->tz_offset); + s.buf += 2; + s.len -= 2; + + n = encode_string(r->message ? r->message : "", s); + if (n < 0) { + return -1; + } + s.len -= n; + s.buf += n; + + return start.len - s.len; +} + +static int log_record_decode(void *rec, struct slice key, byte val_type, + struct slice in, int hash_size) +{ + struct slice start = in; + struct log_record *r = (struct log_record *)rec; + uint64_t max = 0; + uint64_t ts = 0; + struct slice dest = { 0 }; + int n; + + if (key.len <= 9 || key.buf[key.len - 9] != 0) { + return FORMAT_ERROR; + } + + r->ref_name = realloc(r->ref_name, key.len - 8); + memcpy(r->ref_name, key.buf, key.len - 8); + ts = get_be64(key.buf + key.len - 8); + + r->update_index = (~max) - ts; + + if (in.len < 2 * hash_size) { + return FORMAT_ERROR; + } + + r->old_hash = realloc(r->old_hash, hash_size); + r->new_hash = realloc(r->new_hash, hash_size); + + memcpy(r->old_hash, in.buf, hash_size); + memcpy(r->new_hash, in.buf + hash_size, hash_size); + + in.buf += 2 * hash_size; + in.len -= 2 * hash_size; + + n = decode_string(&dest, in); + if (n < 0) { + goto error; + } + in.len -= n; + in.buf += n; + + r->name = realloc(r->name, dest.len + 1); + memcpy(r->name, dest.buf, dest.len); + r->name[dest.len] = 0; + + slice_resize(&dest, 0); + n = decode_string(&dest, in); + if (n < 0) { + goto error; + } + in.len -= n; + in.buf += n; + + r->email = realloc(r->email, dest.len + 1); + memcpy(r->email, dest.buf, dest.len); + r->email[dest.len] = 0; + + ts = 0; + n = get_var_int(&ts, in); + if (n < 0) { + goto error; + } + in.len -= n; + in.buf += n; + r->time = ts; + if (in.len < 2) { + goto error; + } + + r->tz_offset = get_be16(in.buf); + in.buf += 2; + in.len -= 2; + + slice_resize(&dest, 0); + n = decode_string(&dest, in); + if (n < 0) { + goto error; + } + in.len -= n; + in.buf += n; + + r->message = realloc(r->message, dest.len + 1); + memcpy(r->message, dest.buf, dest.len); + r->message[dest.len] = 0; + + return start.len - in.len; + +error: + free(slice_yield(&dest)); + return FORMAT_ERROR; +} + +static bool null_streq(char *a, char *b) +{ + char *empty = ""; + if (a == NULL) { + a = empty; + } + if (b == NULL) { + b = empty; + } + return 0 == strcmp(a, b); +} + +static bool zero_hash_eq(byte *a, byte *b, int sz) +{ + if (a == NULL) { + a = zero; + } + if (b == NULL) { + b = zero; + } + return !memcmp(a, b, sz); +} + +bool log_record_equal(struct log_record *a, struct log_record *b, int hash_size) +{ + return null_streq(a->name, b->name) && null_streq(a->email, b->email) && + null_streq(a->message, b->message) && + zero_hash_eq(a->old_hash, b->old_hash, hash_size) && + zero_hash_eq(a->new_hash, b->new_hash, hash_size) && + a->time == b->time && a->tz_offset == b->tz_offset && + a->update_index == b->update_index; +} + +struct record_vtable log_record_vtable = { + .key = &log_record_key, + .type = &log_record_type, + .copy_from = &log_record_copy_from, + .val_type = &log_record_val_type, + .encode = &log_record_encode, + .decode = &log_record_decode, + .clear = &log_record_clear_void, +}; + +struct record new_record(byte typ) +{ + struct record rec; + switch (typ) { + case BLOCK_TYPE_REF: { + struct ref_record *r = calloc(1, sizeof(struct ref_record)); + record_from_ref(&rec, r); + return rec; + } + + case BLOCK_TYPE_OBJ: { + struct obj_record *r = calloc(1, sizeof(struct obj_record)); + record_from_obj(&rec, r); + return rec; + } + case BLOCK_TYPE_LOG: { + struct log_record *r = calloc(1, sizeof(struct log_record)); + record_from_log(&rec, r); + return rec; + } + case BLOCK_TYPE_INDEX: { + struct index_record *r = calloc(1, sizeof(struct index_record)); + record_from_index(&rec, r); + return rec; + } + } + abort(); + return rec; +} + +static byte index_record_type(void) +{ + return BLOCK_TYPE_INDEX; +} + +static void index_record_key(const void *r, struct slice *dest) +{ + struct index_record *rec = (struct index_record *)r; + slice_copy(dest, rec->last_key); +} + +static void index_record_copy_from(void *rec, const void *src_rec, + int hash_size) +{ + struct index_record *dst = (struct index_record *)rec; + struct index_record *src = (struct index_record *)src_rec; + + slice_copy(&dst->last_key, src->last_key); + dst->offset = src->offset; +} + +static void index_record_clear(void *rec) +{ + struct index_record *idx = (struct index_record *)rec; + free(slice_yield(&idx->last_key)); +} + +static byte index_record_val_type(const void *rec) +{ + return 0; +} + +static int index_record_encode(const void *rec, struct slice out, int hash_size) +{ + const struct index_record *r = (const struct index_record *)rec; + struct slice start = out; + + int n = put_var_int(out, r->offset); + if (n < 0) { + return n; + } + + out.buf += n; + out.len -= n; + + return start.len - out.len; +} + +static int index_record_decode(void *rec, struct slice key, byte val_type, + struct slice in, int hash_size) +{ + struct slice start = in; + struct index_record *r = (struct index_record *)rec; + int n = 0; + + slice_copy(&r->last_key, key); + + n = get_var_int(&r->offset, in); + if (n < 0) { + return n; + } + + in.buf += n; + in.len -= n; + return start.len - in.len; +} + +struct record_vtable index_record_vtable = { + .key = &index_record_key, + .type = &index_record_type, + .copy_from = &index_record_copy_from, + .val_type = &index_record_val_type, + .encode = &index_record_encode, + .decode = &index_record_decode, + .clear = &index_record_clear, +}; + +void record_key(struct record rec, struct slice *dest) +{ + rec.ops->key(rec.data, dest); +} + +byte record_type(struct record rec) +{ + return rec.ops->type(); +} + +int record_encode(struct record rec, struct slice dest, int hash_size) +{ + return rec.ops->encode(rec.data, dest, hash_size); +} + +void record_copy_from(struct record rec, struct record src, int hash_size) +{ + assert(src.ops->type() == rec.ops->type()); + + rec.ops->copy_from(rec.data, src.data, hash_size); +} + +byte record_val_type(struct record rec) +{ + return rec.ops->val_type(rec.data); +} + +int record_decode(struct record rec, struct slice key, byte extra, + struct slice src, int hash_size) +{ + return rec.ops->decode(rec.data, key, extra, src, hash_size); +} + +void record_clear(struct record rec) +{ + return rec.ops->clear(rec.data); +} + +void record_from_ref(struct record *rec, struct ref_record *ref_rec) +{ + rec->data = ref_rec; + rec->ops = &ref_record_vtable; +} + +void record_from_obj(struct record *rec, struct obj_record *obj_rec) +{ + rec->data = obj_rec; + rec->ops = &obj_record_vtable; +} + +void record_from_index(struct record *rec, struct index_record *index_rec) +{ + rec->data = index_rec; + rec->ops = &index_record_vtable; +} + +void record_from_log(struct record *rec, struct log_record *log_rec) +{ + rec->data = log_rec; + rec->ops = &log_record_vtable; +} + +void *record_yield(struct record *rec) +{ + void *p = rec->data; + rec->data = NULL; + return p; +} + +struct ref_record *record_as_ref(struct record rec) +{ + assert(record_type(rec) == BLOCK_TYPE_REF); + return (struct ref_record *)rec.data; +} + +static bool hash_equal(byte *a, byte *b, int hash_size) +{ + if (a != NULL && b != NULL) { + return !memcmp(a, b, hash_size); + } + + return a == b; +} + +static bool str_equal(char *a, char *b) +{ + if (a != NULL && b != NULL) { + return 0 == strcmp(a, b); + } + + return a == b; +} + +bool ref_record_equal(struct ref_record *a, struct ref_record *b, int hash_size) +{ + assert(hash_size > 0); + return 0 == strcmp(a->ref_name, b->ref_name) && + a->update_index == b->update_index && + hash_equal(a->value, b->value, hash_size) && + hash_equal(a->target_value, b->target_value, hash_size) && + str_equal(a->target, b->target); +} + +int ref_record_compare_name(const void *a, const void *b) +{ + return strcmp(((struct ref_record *)a)->ref_name, + ((struct ref_record *)b)->ref_name); +} + +bool ref_record_is_deletion(const struct ref_record *ref) +{ + return ref->value == NULL && ref->target == NULL && + ref->target_value == NULL; +} + +int log_record_compare_key(const void *a, const void *b) +{ + struct log_record *la = (struct log_record *)a; + struct log_record *lb = (struct log_record *)b; + + int cmp = strcmp(la->ref_name, lb->ref_name); + if (cmp) { + return cmp; + } + if (la->update_index > lb->update_index) { + return -1; + } + return (la->update_index < lb->update_index) ? 1 : 0; +} + +bool log_record_is_deletion(const struct log_record *log) +{ + /* XXX */ + return false; +} + +int hash_size(uint32_t id) +{ + switch (id) { + case 0: + case SHA1_ID: + return SHA1_SIZE; + case SHA256_ID: + return SHA256_SIZE; + } + abort(); +} diff --git a/reftable/record.h b/reftable/record.h new file mode 100644 index 00000000000..726a073f430 --- /dev/null +++ b/reftable/record.h @@ -0,0 +1,79 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#ifndef RECORD_H +#define RECORD_H + +#include "reftable.h" +#include "slice.h" + +struct record_vtable { + void (*key)(const void *rec, struct slice *dest); + byte (*type)(void); + void (*copy_from)(void *rec, const void *src, int hash_size); + byte (*val_type)(const void *rec); + int (*encode)(const void *rec, struct slice dest, int hash_size); + int (*decode)(void *rec, struct slice key, byte extra, struct slice src, + int hash_size); + void (*clear)(void *rec); +}; + +/* record is a generic wrapper for different types of records. */ +struct record { + void *data; + struct record_vtable *ops; +}; + +int get_var_int(uint64_t *dest, struct slice in); +int put_var_int(struct slice dest, uint64_t val); +int common_prefix_size(struct slice a, struct slice b); + +int is_block_type(byte typ); +struct record new_record(byte typ); + +extern struct record_vtable ref_record_vtable; + +int encode_key(bool *restart, struct slice dest, struct slice prev_key, + struct slice key, byte extra); +int decode_key(struct slice *key, byte *extra, struct slice last_key, + struct slice in); + +struct index_record { + uint64_t offset; + struct slice last_key; +}; + +struct obj_record { + byte *hash_prefix; + int hash_prefix_len; + uint64_t *offsets; + int offset_len; +}; + +void record_key(struct record rec, struct slice *dest); +byte record_type(struct record rec); +void record_copy_from(struct record rec, struct record src, int hash_size); +byte record_val_type(struct record rec); +int record_encode(struct record rec, struct slice dest, int hash_size); +int record_decode(struct record rec, struct slice key, byte extra, + struct slice src, int hash_size); +void record_clear(struct record rec); +void *record_yield(struct record *rec); +void record_from_obj(struct record *rec, struct obj_record *objrec); +void record_from_index(struct record *rec, struct index_record *idxrec); +void record_from_ref(struct record *rec, struct ref_record *refrec); +void record_from_log(struct record *rec, struct log_record *logrec); +struct ref_record *record_as_ref(struct record ref); + +/* for qsort. */ +int ref_record_compare_name(const void *a, const void *b); + +/* for qsort. */ +int log_record_compare_key(const void *a, const void *b); + +#endif diff --git a/reftable/reftable.h b/reftable/reftable.h new file mode 100644 index 00000000000..e61669bb539 --- /dev/null +++ b/reftable/reftable.h @@ -0,0 +1,409 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#ifndef REFTABLE_H +#define REFTABLE_H + +#include + +/* block_source is a generic wrapper for a seekable readable file. + It is generally passed around by value. + */ +struct block_source { + struct block_source_vtable *ops; + void *arg; +}; + +/* a contiguous segment of bytes. It keeps track of its generating block_source + so it can return itself into the pool. +*/ +struct block { + uint8_t *data; + int len; + struct block_source source; +}; + +/* block_source_vtable are the operations that make up block_source */ +struct block_source_vtable { + /* returns the size of a block source */ + uint64_t (*size)(void *source); + + /* reads a segment from the block source. It is an error to read + beyond the end of the block */ + int (*read_block)(void *source, struct block *dest, uint64_t off, + uint32_t size); + /* mark the block as read; may return the data back to malloc */ + void (*return_block)(void *source, struct block *blockp); + + /* release all resources associated with the block source */ + void (*close)(void *source); +}; + +/* opens a file on the file system as a block_source */ +int block_source_from_file(struct block_source *block_src, const char *name); + +/* write_options sets options for writing a single reftable. */ +struct write_options { + /* boolean: do not pad out blocks to block size. */ + int unpadded; + + /* the blocksize. Should be less than 2^24. */ + uint32_t block_size; + + /* boolean: do not generate a SHA1 => ref index. */ + int skip_index_objects; + + /* how often to write complete keys in each block. */ + int restart_interval; + + /* 4-byte identifier ("sha1", "s256") of the hash. + * Defaults to SHA1 if unset + */ + uint32_t hash_id; +}; + +/* ref_record holds a ref database entry target_value */ +struct ref_record { + char *ref_name; /* Name of the ref, malloced. */ + uint64_t update_index; /* Logical timestamp at which this value is + written */ + uint8_t *value; /* SHA1, or NULL. malloced. */ + uint8_t *target_value; /* peeled annotated tag, or NULL. malloced. */ + char *target; /* symref, or NULL. malloced. */ +}; + +/* returns whether 'ref' represents a deletion */ +int ref_record_is_deletion(const struct ref_record *ref); + +/* prints a ref_record onto stdout */ +void ref_record_print(struct ref_record *ref, int hash_size); + +/* frees and nulls all pointer values. */ +void ref_record_clear(struct ref_record *ref); + +/* returns whether two ref_records are the same */ +int ref_record_equal(struct ref_record *a, struct ref_record *b, int hash_size); + +/* log_record holds a reflog entry */ +struct log_record { + char *ref_name; + uint64_t update_index; + uint8_t *new_hash; + uint8_t *old_hash; + char *name; + char *email; + uint64_t time; + int16_t tz_offset; + char *message; +}; + +/* returns whether 'ref' represents the deletion of a log record. */ +int log_record_is_deletion(const struct log_record *log); + +/* frees and nulls all pointer values. */ +void log_record_clear(struct log_record *log); + +/* returns whether two records are equal. */ +int log_record_equal(struct log_record *a, struct log_record *b, int hash_size); + +void log_record_print(struct log_record *log, int hash_size); + +/* iterator is the generic interface for walking over data stored in a + reftable. It is generally passed around by value. +*/ +struct iterator { + struct iterator_vtable *ops; + void *iter_arg; +}; + +/* reads the next ref_record. Returns < 0 for error, 0 for OK and > 0: + end of iteration. +*/ +int iterator_next_ref(struct iterator it, struct ref_record *ref); + +/* reads the next log_record. Returns < 0 for error, 0 for OK and > 0: + end of iteration. +*/ +int iterator_next_log(struct iterator it, struct log_record *log); + +/* releases resources associated with an iterator. */ +void iterator_destroy(struct iterator *it); + +/* block_stats holds statistics for a single block type */ +struct block_stats { + /* total number of entries written */ + int entries; + /* total number of key restarts */ + int restarts; + /* total number of blocks */ + int blocks; + /* total number of index blocks */ + int index_blocks; + /* depth of the index */ + int max_index_level; + + /* offset of the first block for this type */ + uint64_t offset; + /* offset of the top level index block for this type, or 0 if not + * present */ + uint64_t index_offset; +}; + +/* stats holds overall statistics for a single reftable */ +struct stats { + /* total number of blocks written. */ + int blocks; + /* stats for ref data */ + struct block_stats ref_stats; + /* stats for the SHA1 to ref map. */ + struct block_stats obj_stats; + /* stats for index blocks */ + struct block_stats idx_stats; + /* stats for log blocks */ + struct block_stats log_stats; + + /* disambiguation length of shortened object IDs. */ + int object_id_len; +}; + +/* different types of errors */ + +/* Unexpected file system behavior */ +#define IO_ERROR -2 + +/* Format inconsistency on reading data + */ +#define FORMAT_ERROR -3 + +/* File does not exist. Returned from block_source_from_file(), because it + needs special handling in stack. +*/ +#define NOT_EXIST_ERROR -4 + +/* Trying to write out-of-date data. */ +#define LOCK_ERROR -5 + +/* Misuse of the API: + - on writing a record with NULL ref_name. + - on writing a ref_record outside the table limits + - on writing a ref or log record before the stack's next_update_index + - on reading a ref_record from log iterator, or vice versa. + */ +#define API_ERROR -6 + +/* Decompression error */ +#define ZLIB_ERROR -7 + +/* Wrote a table without blocks. */ +#define EMPTY_TABLE_ERROR -8 + +const char *error_str(int err); + +/* new_writer creates a new writer */ +struct writer *new_writer(int (*writer_func)(void *, uint8_t *, int), + void *writer_arg, struct write_options *opts); + +/* write to a file descriptor. fdp should be an int* pointing to the fd. */ +int fd_writer(void *fdp, uint8_t *data, int size); + +/* Set the range of update indices for the records we will add. When + writing a table into a stack, the min should be at least + stack_next_update_index(), or API_ERROR is returned. + */ +void writer_set_limits(struct writer *w, uint64_t min, uint64_t max); + +/* adds a ref_record. Must be called in ascending + order. The update_index must be within the limits set by + writer_set_limits(), or API_ERROR is returned. + */ +int writer_add_ref(struct writer *w, struct ref_record *ref); + +/* Convenience function to add multiple refs. Will sort the refs by + name before adding. */ +int writer_add_refs(struct writer *w, struct ref_record *refs, int n); + +/* adds a log_record. Must be called in ascending order (with more + recent log entries first.) + */ +int writer_add_log(struct writer *w, struct log_record *log); + +/* Convenience function to add multiple logs. Will sort the records by + key before adding. */ +int writer_add_logs(struct writer *w, struct log_record *logs, int n); + +/* writer_close finalizes the reftable. The writer is retained so statistics can + * be inspected. */ +int writer_close(struct writer *w); + +/* writer_stats returns the statistics on the reftable being written. */ +struct stats *writer_stats(struct writer *w); + +/* writer_free deallocates memory for the writer */ +void writer_free(struct writer *w); + +struct reader; + +/* new_reader opens a reftable for reading. If successful, returns 0 + * code and sets pp. The name is used for creating a + * stack. Typically, it is the basename of the file. + */ +int new_reader(struct reader **pp, struct block_source, const char *name); + +/* reader_seek_ref returns an iterator where 'name' would be inserted in the + table. + + example: + + struct reader *r = NULL; + int err = new_reader(&r, src, "filename"); + if (err < 0) { ... } + struct iterator it = {0}; + err = reader_seek_ref(r, &it, "refs/heads/master"); + if (err < 0) { ... } + struct ref_record ref = {0}; + while (1) { + err = iterator_next_ref(it, &ref); + if (err > 0) { + break; + } + if (err < 0) { + ..error handling.. + } + ..found.. + } + iterator_destroy(&it); + ref_record_clear(&ref); + */ +int reader_seek_ref(struct reader *r, struct iterator *it, const char *name); + +/* returns the hash ID used in this table. */ +uint32_t reader_hash_id(struct reader *r); + +/* seek to logs for the given name, older than update_index. */ +int reader_seek_log_at(struct reader *r, struct iterator *it, const char *name, + uint64_t update_index); + +/* seek to newest log entry for given name. */ +int reader_seek_log(struct reader *r, struct iterator *it, const char *name); + +/* closes and deallocates a reader. */ +void reader_free(struct reader *); + +/* return an iterator for the refs pointing to oid */ +int reader_refs_for(struct reader *r, struct iterator *it, uint8_t *oid, + int oid_len); + +/* return the max_update_index for a table */ +uint64_t reader_max_update_index(struct reader *r); + +/* return the min_update_index for a table */ +uint64_t reader_min_update_index(struct reader *r); + +/* a merged table is implements seeking/iterating over a stack of tables. */ +struct merged_table; + +/* new_merged_table creates a new merged table. It takes ownership of the stack + array. +*/ +int new_merged_table(struct merged_table **dest, struct reader **stack, int n, + uint32_t hash_id); + +/* returns the hash id used in this merged table. */ +uint32_t merged_hash_id(struct merged_table *mt); + +/* returns an iterator positioned just before 'name' */ +int merged_table_seek_ref(struct merged_table *mt, struct iterator *it, + const char *name); + +/* returns an iterator for log entry, at given update_index */ +int merged_table_seek_log_at(struct merged_table *mt, struct iterator *it, + const char *name, uint64_t update_index); + +/* like merged_table_seek_log_at but look for the newest entry. */ +int merged_table_seek_log(struct merged_table *mt, struct iterator *it, + const char *name); + +/* returns the max update_index covered by this merged table. */ +uint64_t merged_max_update_index(struct merged_table *mt); + +/* returns the min update_index covered by this merged table. */ +uint64_t merged_min_update_index(struct merged_table *mt); + +/* closes readers for the merged tables */ +void merged_table_close(struct merged_table *mt); + +/* releases memory for the merged_table */ +void merged_table_free(struct merged_table *m); + +/* a stack is a stack of reftables, which can be mutated by pushing a table to + * the top of the stack */ +struct stack; + +/* open a new reftable stack. The tables will be stored in 'dir', while the list + of tables is in 'list_file'. Typically, this should be .git/reftables and + .git/refs respectively. +*/ +int new_stack(struct stack **dest, const char *dir, const char *list_file, + struct write_options config); + +/* returns the update_index at which a next table should be written. */ +uint64_t stack_next_update_index(struct stack *st); + +/* add a new table to the stack. The write_table function must call + writer_set_limits, add refs and return an error value. */ +int stack_add(struct stack *st, + int (*write_table)(struct writer *wr, void *write_arg), + void *write_arg); + +/* returns the merged_table for seeking. This table is valid until the + next write or reload, and should not be closed or deleted. +*/ +struct merged_table *stack_merged_table(struct stack *st); + +/* frees all resources associated with the stack. */ +void stack_destroy(struct stack *st); + +/* reloads the stack if necessary. */ +int stack_reload(struct stack *st); + +/* Policy for expiring reflog entries. */ +struct log_expiry_config { + /* Drop entries older than this timestamp */ + uint64_t time; + + /* Drop older entries */ + uint64_t min_update_index; +}; + +/* compacts all reftables into a giant table. Expire reflog entries if config is + * non-NULL */ +int stack_compact_all(struct stack *st, struct log_expiry_config *config); + +/* heuristically compact unbalanced table stack. */ +int stack_auto_compact(struct stack *st); + +/* convenience function to read a single ref. Returns < 0 for error, 0 + for success, and 1 if ref not found. */ +int stack_read_ref(struct stack *st, const char *refname, + struct ref_record *ref); + +/* convenience function to read a single log. Returns < 0 for error, 0 + for success, and 1 if ref not found. */ +int stack_read_log(struct stack *st, const char *refname, + struct log_record *log); + +/* statistics on past compactions. */ +struct compaction_stats { + uint64_t bytes; + int attempts; + int failures; +}; + +struct compaction_stats *stack_compaction_stats(struct stack *st); + +#endif diff --git a/reftable/slice.c b/reftable/slice.c new file mode 100644 index 00000000000..567ed6cf5fe --- /dev/null +++ b/reftable/slice.c @@ -0,0 +1,199 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#include "slice.h" + +#include "system.h" + +#include "reftable.h" + +void slice_set_string(struct slice *s, const char *str) +{ + if (str == NULL) { + s->len = 0; + return; + } + + { + int l = strlen(str); + l++; /* \0 */ + slice_resize(s, l); + memcpy(s->buf, str, l); + s->len = l - 1; + } +} + +void slice_resize(struct slice *s, int l) +{ + if (s->cap < l) { + int c = s->cap * 2; + if (c < l) { + c = l; + } + s->cap = c; + s->buf = realloc(s->buf, s->cap); + } + s->len = l; +} + +void slice_append_string(struct slice *d, const char *s) +{ + int l1 = d->len; + int l2 = strlen(s); + + slice_resize(d, l2 + l1); + memcpy(d->buf + l1, s, l2); +} + +void slice_append(struct slice *s, struct slice a) +{ + int end = s->len; + slice_resize(s, s->len + a.len); + memcpy(s->buf + end, a.buf, a.len); +} + +byte *slice_yield(struct slice *s) +{ + byte *p = s->buf; + s->buf = NULL; + s->cap = 0; + s->len = 0; + return p; +} + +void slice_copy(struct slice *dest, struct slice src) +{ + slice_resize(dest, src.len); + memcpy(dest->buf, src.buf, src.len); +} + +/* return the underlying data as char*. len is left unchanged, but + a \0 is added at the end. */ +const char *slice_as_string(struct slice *s) +{ + if (s->cap == s->len) { + int l = s->len; + slice_resize(s, l + 1); + s->len = l; + } + s->buf[s->len] = 0; + return (const char *)s->buf; +} + +/* return a newly malloced string for this slice */ +char *slice_to_string(struct slice in) +{ + struct slice s = { 0 }; + slice_resize(&s, in.len + 1); + s.buf[in.len] = 0; + memcpy(s.buf, in.buf, in.len); + return (char *)slice_yield(&s); +} + +bool slice_equal(struct slice a, struct slice b) +{ + if (a.len != b.len) { + return 0; + } + return memcmp(a.buf, b.buf, a.len) == 0; +} + +int slice_compare(struct slice a, struct slice b) +{ + int min = a.len < b.len ? a.len : b.len; + int res = memcmp(a.buf, b.buf, min); + if (res != 0) { + return res; + } + if (a.len < b.len) { + return -1; + } else if (a.len > b.len) { + return 1; + } else { + return 0; + } +} + +int slice_write(struct slice *b, byte *data, int sz) +{ + if (b->len + sz > b->cap) { + int newcap = 2 * b->cap + 1; + if (newcap < b->len + sz) { + newcap = (b->len + sz); + } + b->buf = realloc(b->buf, newcap); + b->cap = newcap; + } + + memcpy(b->buf + b->len, data, sz); + b->len += sz; + return sz; +} + +int slice_write_void(void *b, byte *data, int sz) +{ + return slice_write((struct slice *)b, data, sz); +} + +static uint64_t slice_size(void *b) +{ + return ((struct slice *)b)->len; +} + +static void slice_return_block(void *b, struct block *dest) +{ + memset(dest->data, 0xff, dest->len); + free(dest->data); +} + +static void slice_close(void *b) +{ +} + +static int slice_read_block(void *v, struct block *dest, uint64_t off, + uint32_t size) +{ + struct slice *b = (struct slice *)v; + assert(off + size <= b->len); + dest->data = calloc(size, 1); + memcpy(dest->data, b->buf + off, size); + dest->len = size; + return size; +} + +struct block_source_vtable slice_vtable = { + .size = &slice_size, + .read_block = &slice_read_block, + .return_block = &slice_return_block, + .close = &slice_close, +}; + +void block_source_from_slice(struct block_source *bs, struct slice *buf) +{ + bs->ops = &slice_vtable; + bs->arg = buf; +} + +static void malloc_return_block(void *b, struct block *dest) +{ + memset(dest->data, 0xff, dest->len); + free(dest->data); +} + +struct block_source_vtable malloc_vtable = { + .return_block = &malloc_return_block, +}; + +struct block_source malloc_block_source_instance = { + .ops = &malloc_vtable, +}; + +struct block_source malloc_block_source(void) +{ + return malloc_block_source_instance; +} diff --git a/reftable/slice.h b/reftable/slice.h new file mode 100644 index 00000000000..f12a6db228c --- /dev/null +++ b/reftable/slice.h @@ -0,0 +1,39 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#ifndef SLICE_H +#define SLICE_H + +#include "basics.h" +#include "reftable.h" + +struct slice { + byte *buf; + int len; + int cap; +}; + +void slice_set_string(struct slice *dest, const char *); +void slice_append_string(struct slice *dest, const char *); +char *slice_to_string(struct slice src); +const char *slice_as_string(struct slice *src); +bool slice_equal(struct slice a, struct slice b); +byte *slice_yield(struct slice *s); +void slice_copy(struct slice *dest, struct slice src); +void slice_resize(struct slice *s, int l); +int slice_compare(struct slice a, struct slice b); +int slice_write(struct slice *b, byte *data, int sz); +int slice_write_void(void *b, byte *data, int sz); +void slice_append(struct slice *dest, struct slice add); + +struct block_source; +void block_source_from_slice(struct block_source *bs, struct slice *buf); + +struct block_source malloc_block_source(void); + +#endif diff --git a/reftable/stack.c b/reftable/stack.c new file mode 100644 index 00000000000..720907e6f23 --- /dev/null +++ b/reftable/stack.c @@ -0,0 +1,1007 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#include "stack.h" + +#include "system.h" +#include "merged.h" +#include "reader.h" +#include "reftable.h" +#include "writer.h" + +int new_stack(struct stack **dest, const char *dir, const char *list_file, + struct write_options config) +{ + struct stack *p = calloc(sizeof(struct stack), 1); + int err = 0; + *dest = NULL; + p->list_file = xstrdup(list_file); + p->reftable_dir = xstrdup(dir); + p->config = config; + + err = stack_reload(p); + if (err < 0) { + stack_destroy(p); + } else { + *dest = p; + } + return err; +} + +static int fread_lines(FILE *f, char ***namesp) +{ + long size = 0; + int err = fseek(f, 0, SEEK_END); + char *buf = NULL; + if (err < 0) { + err = IO_ERROR; + goto exit; + } + size = ftell(f); + if (size < 0) { + err = IO_ERROR; + goto exit; + } + err = fseek(f, 0, SEEK_SET); + if (err < 0) { + err = IO_ERROR; + goto exit; + } + + buf = malloc(size + 1); + if (fread(buf, 1, size, f) != size) { + err = IO_ERROR; + goto exit; + } + buf[size] = 0; + + parse_names(buf, size, namesp); +exit: + free(buf); + return err; +} + +int read_lines(const char *filename, char ***namesp) +{ + FILE *f = fopen(filename, "r"); + int err = 0; + if (f == NULL) { + if (errno == ENOENT) { + *namesp = calloc(sizeof(char *), 1); + return 0; + } + + return IO_ERROR; + } + err = fread_lines(f, namesp); + fclose(f); + return err; +} + +struct merged_table *stack_merged_table(struct stack *st) +{ + return st->merged; +} + +/* Close and free the stack */ +void stack_destroy(struct stack *st) +{ + if (st->merged == NULL) { + return; + } + + merged_table_close(st->merged); + merged_table_free(st->merged); + st->merged = NULL; + + FREE_AND_NULL(st->list_file); + FREE_AND_NULL(st->reftable_dir); + free(st); +} + +static struct reader **stack_copy_readers(struct stack *st, int cur_len) +{ + struct reader **cur = calloc(sizeof(struct reader *), cur_len); + int i = 0; + for (i = 0; i < cur_len; i++) { + cur[i] = st->merged->stack[i]; + } + return cur; +} + +static int stack_reload_once(struct stack *st, char **names, bool reuse_open) +{ + int cur_len = st->merged == NULL ? 0 : st->merged->stack_len; + struct reader **cur = stack_copy_readers(st, cur_len); + int err = 0; + int names_len = names_length(names); + struct reader **new_tables = + malloc(sizeof(struct reader *) * names_len); + int new_tables_len = 0; + struct merged_table *new_merged = NULL; + + struct slice table_path = { 0 }; + + while (*names) { + struct reader *rd = NULL; + char *name = *names++; + + /* this is linear; we assume compaction keeps the number of + tables under control so this is not quadratic. */ + int j = 0; + for (j = 0; reuse_open && j < cur_len; j++) { + if (cur[j] != NULL && 0 == strcmp(cur[j]->name, name)) { + rd = cur[j]; + cur[j] = NULL; + break; + } + } + + if (rd == NULL) { + struct block_source src = { 0 }; + slice_set_string(&table_path, st->reftable_dir); + slice_append_string(&table_path, "/"); + slice_append_string(&table_path, name); + + err = block_source_from_file( + &src, slice_as_string(&table_path)); + if (err < 0) { + goto exit; + } + + err = new_reader(&rd, src, name); + if (err < 0) { + goto exit; + } + } + + new_tables[new_tables_len++] = rd; + } + + /* success! */ + err = new_merged_table(&new_merged, new_tables, new_tables_len, + st->config.hash_id); + if (err < 0) { + goto exit; + } + + new_tables = NULL; + new_tables_len = 0; + if (st->merged != NULL) { + merged_table_clear(st->merged); + merged_table_free(st->merged); + } + st->merged = new_merged; + + { + int i = 0; + for (i = 0; i < cur_len; i++) { + if (cur[i] != NULL) { + reader_close(cur[i]); + reader_free(cur[i]); + } + } + } +exit: + free(slice_yield(&table_path)); + { + int i = 0; + for (i = 0; i < new_tables_len; i++) { + reader_close(new_tables[i]); + } + } + free(new_tables); + free(cur); + return err; +} + +/* return negative if a before b. */ +static int tv_cmp(struct timeval *a, struct timeval *b) +{ + time_t diff = a->tv_sec - b->tv_sec; + int udiff = a->tv_usec - b->tv_usec; + + if (diff != 0) { + return diff; + } + + return udiff; +} + +static int stack_reload_maybe_reuse(struct stack *st, bool reuse_open) +{ + struct timeval deadline = { 0 }; + int err = gettimeofday(&deadline, NULL); + int64_t delay = 0; + int tries = 0; + if (err < 0) { + return err; + } + + deadline.tv_sec += 3; + while (true) { + char **names = NULL; + char **names_after = NULL; + struct timeval now = { 0 }; + int err = gettimeofday(&now, NULL); + if (err < 0) { + return err; + } + + /* Only look at deadlines after the first few times. This + simplifies debugging in GDB */ + tries++; + if (tries > 3 && tv_cmp(&now, &deadline) >= 0) { + break; + } + + err = read_lines(st->list_file, &names); + if (err < 0) { + free_names(names); + return err; + } + err = stack_reload_once(st, names, reuse_open); + if (err == 0) { + free_names(names); + break; + } + if (err != NOT_EXIST_ERROR) { + free_names(names); + return err; + } + + err = read_lines(st->list_file, &names_after); + if (err < 0) { + free_names(names); + return err; + } + + if (names_equal(names_after, names)) { + free_names(names); + free_names(names_after); + return -1; + } + free_names(names); + free_names(names_after); + + delay = delay + (delay * rand()) / RAND_MAX + 100; + usleep(delay); + } + + return 0; +} + +int stack_reload(struct stack *st) +{ + return stack_reload_maybe_reuse(st, true); +} + +/* -1 = error + 0 = up to date + 1 = changed. */ +static int stack_uptodate(struct stack *st) +{ + char **names = NULL; + int err = read_lines(st->list_file, &names); + int i = 0; + if (err < 0) { + return err; + } + + for (i = 0; i < st->merged->stack_len; i++) { + if (names[i] == NULL) { + err = 1; + goto exit; + } + + if (strcmp(st->merged->stack[i]->name, names[i])) { + err = 1; + goto exit; + } + } + + if (names[st->merged->stack_len] != NULL) { + err = 1; + goto exit; + } + +exit: + free_names(names); + return err; +} + +int stack_add(struct stack *st, int (*write)(struct writer *wr, void *arg), + void *arg) +{ + int err = stack_try_add(st, write, arg); + if (err < 0) { + if (err == LOCK_ERROR) { + err = stack_reload(st); + } + return err; + } + + return stack_auto_compact(st); +} + +static void format_name(struct slice *dest, uint64_t min, uint64_t max) +{ + char buf[100]; + snprintf(buf, sizeof(buf), "%012" PRIx64 "-%012" PRIx64, min, max); + slice_set_string(dest, buf); +} + +int stack_try_add(struct stack *st, + int (*write_table)(struct writer *wr, void *arg), void *arg) +{ + struct slice lock_name = { 0 }; + struct slice temp_tab_name = { 0 }; + struct slice tab_name = { 0 }; + struct slice next_name = { 0 }; + struct slice table_list = { 0 }; + struct writer *wr = NULL; + int err = 0; + int tab_fd = 0; + int lock_fd = 0; + uint64_t next_update_index = 0; + + slice_set_string(&lock_name, st->list_file); + slice_append_string(&lock_name, ".lock"); + + lock_fd = open(slice_as_string(&lock_name), O_EXCL | O_CREAT | O_WRONLY, + 0644); + if (lock_fd < 0) { + if (errno == EEXIST) { + err = LOCK_ERROR; + goto exit; + } + err = IO_ERROR; + goto exit; + } + + err = stack_uptodate(st); + if (err < 0) { + goto exit; + } + + if (err > 1) { + err = LOCK_ERROR; + goto exit; + } + + next_update_index = stack_next_update_index(st); + + slice_resize(&next_name, 0); + format_name(&next_name, next_update_index, next_update_index); + + slice_set_string(&temp_tab_name, st->reftable_dir); + slice_append_string(&temp_tab_name, "/"); + slice_append(&temp_tab_name, next_name); + slice_append_string(&temp_tab_name, ".temp.XXXXXX"); + + tab_fd = mkstemp((char *)slice_as_string(&temp_tab_name)); + if (tab_fd < 0) { + err = IO_ERROR; + goto exit; + } + + wr = new_writer(fd_writer, &tab_fd, &st->config); + err = write_table(wr, arg); + if (err < 0) { + goto exit; + } + + err = writer_close(wr); + if (err == EMPTY_TABLE_ERROR) { + err = 0; + goto exit; + } + if (err < 0) { + goto exit; + } + + err = close(tab_fd); + tab_fd = 0; + if (err < 0) { + err = IO_ERROR; + goto exit; + } + + if (wr->min_update_index < next_update_index) { + err = API_ERROR; + goto exit; + } + + { + int i = 0; + for (i = 0; i < st->merged->stack_len; i++) { + slice_append_string(&table_list, + st->merged->stack[i]->name); + slice_append_string(&table_list, "\n"); + } + } + + format_name(&next_name, wr->min_update_index, wr->max_update_index); + slice_append_string(&next_name, ".ref"); + slice_append(&table_list, next_name); + slice_append_string(&table_list, "\n"); + + slice_set_string(&tab_name, st->reftable_dir); + slice_append_string(&tab_name, "/"); + slice_append(&tab_name, next_name); + + err = rename(slice_as_string(&temp_tab_name), + slice_as_string(&tab_name)); + if (err < 0) { + err = IO_ERROR; + goto exit; + } + free(slice_yield(&temp_tab_name)); + + err = write(lock_fd, table_list.buf, table_list.len); + if (err < 0) { + err = IO_ERROR; + goto exit; + } + err = close(lock_fd); + lock_fd = 0; + if (err < 0) { + unlink(slice_as_string(&tab_name)); + err = IO_ERROR; + goto exit; + } + + err = rename(slice_as_string(&lock_name), st->list_file); + if (err < 0) { + unlink(slice_as_string(&tab_name)); + err = IO_ERROR; + goto exit; + } + + err = stack_reload(st); +exit: + if (tab_fd > 0) { + close(tab_fd); + tab_fd = 0; + } + if (temp_tab_name.len > 0) { + unlink(slice_as_string(&temp_tab_name)); + } + unlink(slice_as_string(&lock_name)); + + if (lock_fd > 0) { + close(lock_fd); + lock_fd = 0; + } + + free(slice_yield(&lock_name)); + free(slice_yield(&temp_tab_name)); + free(slice_yield(&tab_name)); + free(slice_yield(&next_name)); + free(slice_yield(&table_list)); + writer_free(wr); + return err; +} + +uint64_t stack_next_update_index(struct stack *st) +{ + int sz = st->merged->stack_len; + if (sz > 0) { + return reader_max_update_index(st->merged->stack[sz - 1]) + 1; + } + return 1; +} + +static int stack_compact_locked(struct stack *st, int first, int last, + struct slice *temp_tab, + struct log_expiry_config *config) +{ + struct slice next_name = { 0 }; + int tab_fd = -1; + struct writer *wr = NULL; + int err = 0; + + format_name(&next_name, + reader_min_update_index(st->merged->stack[first]), + reader_max_update_index(st->merged->stack[first])); + + slice_set_string(temp_tab, st->reftable_dir); + slice_append_string(temp_tab, "/"); + slice_append(temp_tab, next_name); + slice_append_string(temp_tab, ".temp.XXXXXX"); + + tab_fd = mkstemp((char *)slice_as_string(temp_tab)); + wr = new_writer(fd_writer, &tab_fd, &st->config); + + err = stack_write_compact(st, wr, first, last, config); + if (err < 0) { + goto exit; + } + err = writer_close(wr); + if (err < 0) { + goto exit; + } + writer_free(wr); + + err = close(tab_fd); + tab_fd = 0; + +exit: + if (tab_fd > 0) { + close(tab_fd); + tab_fd = 0; + } + if (err != 0 && temp_tab->len > 0) { + unlink(slice_as_string(temp_tab)); + free(slice_yield(temp_tab)); + } + free(slice_yield(&next_name)); + return err; +} + +int stack_write_compact(struct stack *st, struct writer *wr, int first, + int last, struct log_expiry_config *config) +{ + int subtabs_len = last - first + 1; + struct reader **subtabs = + calloc(sizeof(struct reader *), last - first + 1); + struct merged_table *mt = NULL; + int err = 0; + struct iterator it = { 0 }; + struct ref_record ref = { 0 }; + struct log_record log = { 0 }; + + int i = 0, j = 0; + for (i = first, j = 0; i <= last; i++) { + struct reader *t = st->merged->stack[i]; + subtabs[j++] = t; + st->stats.bytes += t->size; + } + writer_set_limits(wr, st->merged->stack[first]->min_update_index, + st->merged->stack[last]->max_update_index); + + err = new_merged_table(&mt, subtabs, subtabs_len, st->config.hash_id); + if (err < 0) { + free(subtabs); + goto exit; + } + + err = merged_table_seek_ref(mt, &it, ""); + if (err < 0) { + goto exit; + } + + while (true) { + err = iterator_next_ref(it, &ref); + if (err > 0) { + err = 0; + break; + } + if (err < 0) { + break; + } + if (first == 0 && ref_record_is_deletion(&ref)) { + continue; + } + + err = writer_add_ref(wr, &ref); + if (err < 0) { + break; + } + } + + err = merged_table_seek_log(mt, &it, ""); + if (err < 0) { + goto exit; + } + + while (true) { + err = iterator_next_log(it, &log); + if (err > 0) { + err = 0; + break; + } + if (err < 0) { + break; + } + if (first == 0 && log_record_is_deletion(&log)) { + continue; + } + + /* XXX collect stats? */ + + if (config != NULL && config->time > 0 && + log.time < config->time) { + continue; + } + + if (config != NULL && config->min_update_index > 0 && + log.update_index < config->min_update_index) { + continue; + } + + err = writer_add_log(wr, &log); + if (err < 0) { + break; + } + } + +exit: + iterator_destroy(&it); + if (mt != NULL) { + merged_table_clear(mt); + merged_table_free(mt); + } + ref_record_clear(&ref); + + return err; +} + +/* < 0: error. 0 == OK, > 0 attempt failed; could retry. */ +static int stack_compact_range(struct stack *st, int first, int last, + struct log_expiry_config *expiry) +{ + struct slice temp_tab_name = { 0 }; + struct slice new_table_name = { 0 }; + struct slice lock_file_name = { 0 }; + struct slice ref_list_contents = { 0 }; + struct slice new_table_path = { 0 }; + int err = 0; + bool have_lock = false; + int lock_file_fd = 0; + int compact_count = last - first + 1; + char **delete_on_success = calloc(sizeof(char *), compact_count + 1); + char **subtable_locks = calloc(sizeof(char *), compact_count + 1); + int i = 0; + int j = 0; + bool is_empty_table = false; + + if (first > last || (expiry == NULL && first == last)) { + err = 0; + goto exit; + } + + st->stats.attempts++; + + slice_set_string(&lock_file_name, st->list_file); + slice_append_string(&lock_file_name, ".lock"); + + lock_file_fd = open(slice_as_string(&lock_file_name), + O_EXCL | O_CREAT | O_WRONLY, 0644); + if (lock_file_fd < 0) { + if (errno == EEXIST) { + err = 1; + } else { + err = IO_ERROR; + } + goto exit; + } + have_lock = true; + err = stack_uptodate(st); + if (err != 0) { + goto exit; + } + + for (i = first, j = 0; i <= last; i++) { + struct slice subtab_name = { 0 }; + struct slice subtab_lock = { 0 }; + slice_set_string(&subtab_name, st->reftable_dir); + slice_append_string(&subtab_name, "/"); + slice_append_string(&subtab_name, + reader_name(st->merged->stack[i])); + + slice_copy(&subtab_lock, subtab_name); + slice_append_string(&subtab_lock, ".lock"); + + { + int sublock_file_fd = + open(slice_as_string(&subtab_lock), + O_EXCL | O_CREAT | O_WRONLY, 0644); + if (sublock_file_fd > 0) { + close(sublock_file_fd); + } else if (sublock_file_fd < 0) { + if (errno == EEXIST) { + err = 1; + } + err = IO_ERROR; + } + } + + subtable_locks[j] = (char *)slice_as_string(&subtab_lock); + delete_on_success[j] = (char *)slice_as_string(&subtab_name); + j++; + + if (err != 0) { + goto exit; + } + } + + err = unlink(slice_as_string(&lock_file_name)); + if (err < 0) { + goto exit; + } + have_lock = false; + + err = stack_compact_locked(st, first, last, &temp_tab_name, expiry); + /* Compaction + tombstones can create an empty table out of non-empty + * tables. */ + is_empty_table = (err == EMPTY_TABLE_ERROR); + if (is_empty_table) { + err = 0; + } + if (err < 0) { + goto exit; + } + + lock_file_fd = open(slice_as_string(&lock_file_name), + O_EXCL | O_CREAT | O_WRONLY, 0644); + if (lock_file_fd < 0) { + if (errno == EEXIST) { + err = 1; + } else { + err = IO_ERROR; + } + goto exit; + } + have_lock = true; + + format_name(&new_table_name, st->merged->stack[first]->min_update_index, + st->merged->stack[last]->max_update_index); + slice_append_string(&new_table_name, ".ref"); + + slice_set_string(&new_table_path, st->reftable_dir); + slice_append_string(&new_table_path, "/"); + + slice_append(&new_table_path, new_table_name); + + if (!is_empty_table) { + err = rename(slice_as_string(&temp_tab_name), + slice_as_string(&new_table_path)); + if (err < 0) { + goto exit; + } + } + + for (i = 0; i < first; i++) { + slice_append_string(&ref_list_contents, + st->merged->stack[i]->name); + slice_append_string(&ref_list_contents, "\n"); + } + if (!is_empty_table) { + slice_append(&ref_list_contents, new_table_name); + slice_append_string(&ref_list_contents, "\n"); + } + for (i = last + 1; i < st->merged->stack_len; i++) { + slice_append_string(&ref_list_contents, + st->merged->stack[i]->name); + slice_append_string(&ref_list_contents, "\n"); + } + + err = write(lock_file_fd, ref_list_contents.buf, ref_list_contents.len); + if (err < 0) { + unlink(slice_as_string(&new_table_path)); + goto exit; + } + err = close(lock_file_fd); + lock_file_fd = 0; + if (err < 0) { + unlink(slice_as_string(&new_table_path)); + goto exit; + } + + err = rename(slice_as_string(&lock_file_name), st->list_file); + if (err < 0) { + unlink(slice_as_string(&new_table_path)); + goto exit; + } + have_lock = false; + + { + char **p = delete_on_success; + while (*p) { + if (strcmp(*p, slice_as_string(&new_table_path))) { + unlink(*p); + } + p++; + } + } + + err = stack_reload_maybe_reuse(st, first < last); +exit: + free_names(delete_on_success); + { + char **p = subtable_locks; + while (*p) { + unlink(*p); + p++; + } + } + free_names(subtable_locks); + if (lock_file_fd > 0) { + close(lock_file_fd); + lock_file_fd = 0; + } + if (have_lock) { + unlink(slice_as_string(&lock_file_name)); + } + free(slice_yield(&new_table_name)); + free(slice_yield(&new_table_path)); + free(slice_yield(&ref_list_contents)); + free(slice_yield(&temp_tab_name)); + free(slice_yield(&lock_file_name)); + return err; +} + +int stack_compact_all(struct stack *st, struct log_expiry_config *config) +{ + return stack_compact_range(st, 0, st->merged->stack_len - 1, config); +} + +static int stack_compact_range_stats(struct stack *st, int first, int last, + struct log_expiry_config *config) +{ + int err = stack_compact_range(st, first, last, config); + if (err > 0) { + st->stats.failures++; + } + return err; +} + +static int segment_size(struct segment *s) +{ + return s->end - s->start; +} + +int fastlog2(uint64_t sz) +{ + int l = 0; + assert(sz > 0); + for (; sz; sz /= 2) { + l++; + } + return l - 1; +} + +struct segment *sizes_to_segments(int *seglen, uint64_t *sizes, int n) +{ + struct segment *segs = calloc(sizeof(struct segment), n); + int next = 0; + struct segment cur = { 0 }; + int i = 0; + for (i = 0; i < n; i++) { + int log = fastlog2(sizes[i]); + if (cur.log != log && cur.bytes > 0) { + struct segment fresh = { + .start = i, + }; + + segs[next++] = cur; + cur = fresh; + } + + cur.log = log; + cur.end = i + 1; + cur.bytes += sizes[i]; + } + + segs[next++] = cur; + *seglen = next; + return segs; +} + +struct segment suggest_compaction_segment(uint64_t *sizes, int n) +{ + int seglen = 0; + struct segment *segs = sizes_to_segments(&seglen, sizes, n); + struct segment min_seg = { + .log = 64, + }; + int i = 0; + for (i = 0; i < seglen; i++) { + if (segment_size(&segs[i]) == 1) { + continue; + } + + if (segs[i].log < min_seg.log) { + min_seg = segs[i]; + } + } + + while (min_seg.start > 0) { + int prev = min_seg.start - 1; + if (fastlog2(min_seg.bytes) < fastlog2(sizes[prev])) { + break; + } + + min_seg.start = prev; + min_seg.bytes += sizes[prev]; + } + + free(segs); + return min_seg; +} + +static uint64_t *stack_table_sizes_for_compaction(struct stack *st) +{ + uint64_t *sizes = calloc(sizeof(uint64_t), st->merged->stack_len); + int i = 0; + for (i = 0; i < st->merged->stack_len; i++) { + /* overhead is 24 + 68 = 92. */ + sizes[i] = st->merged->stack[i]->size - 91; + } + return sizes; +} + +int stack_auto_compact(struct stack *st) +{ + uint64_t *sizes = stack_table_sizes_for_compaction(st); + struct segment seg = + suggest_compaction_segment(sizes, st->merged->stack_len); + free(sizes); + if (segment_size(&seg) > 0) { + return stack_compact_range_stats(st, seg.start, seg.end - 1, + NULL); + } + + return 0; +} + +struct compaction_stats *stack_compaction_stats(struct stack *st) +{ + return &st->stats; +} + +int stack_read_ref(struct stack *st, const char *refname, + struct ref_record *ref) +{ + struct iterator it = { 0 }; + struct merged_table *mt = stack_merged_table(st); + int err = merged_table_seek_ref(mt, &it, refname); + if (err) { + goto exit; + } + + err = iterator_next_ref(it, ref); + if (err) { + goto exit; + } + + if (strcmp(ref->ref_name, refname) || ref_record_is_deletion(ref)) { + err = 1; + goto exit; + } + +exit: + iterator_destroy(&it); + return err; +} + +int stack_read_log(struct stack *st, const char *refname, + struct log_record *log) +{ + struct iterator it = { 0 }; + struct merged_table *mt = stack_merged_table(st); + int err = merged_table_seek_log(mt, &it, refname); + if (err) { + goto exit; + } + + err = iterator_next_log(it, log); + if (err) { + goto exit; + } + + if (strcmp(log->ref_name, refname) || log_record_is_deletion(log)) { + err = 1; + goto exit; + } + +exit: + iterator_destroy(&it); + return err; +} diff --git a/reftable/stack.h b/reftable/stack.h new file mode 100644 index 00000000000..d5e2c93c293 --- /dev/null +++ b/reftable/stack.h @@ -0,0 +1,40 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#ifndef STACK_H +#define STACK_H + +#include "reftable.h" + +struct stack { + char *list_file; + char *reftable_dir; + + struct write_options config; + + struct merged_table *merged; + struct compaction_stats stats; +}; + +int read_lines(const char *filename, char ***lines); +int stack_try_add(struct stack *st, + int (*write_table)(struct writer *wr, void *arg), void *arg); +int stack_write_compact(struct stack *st, struct writer *wr, int first, + int last, struct log_expiry_config *config); +int fastlog2(uint64_t sz); + +struct segment { + int start, end; + int log; + uint64_t bytes; +}; + +struct segment *sizes_to_segments(int *seglen, uint64_t *sizes, int n); +struct segment suggest_compaction_segment(uint64_t *sizes, int n); + +#endif diff --git a/reftable/system.h b/reftable/system.h new file mode 100644 index 00000000000..99f453bfec8 --- /dev/null +++ b/reftable/system.h @@ -0,0 +1,53 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#ifndef SYSTEM_H +#define SYSTEM_H + +#if 1 /* REFTABLE_IN_GITCORE */ + +#include "git-compat-util.h" +#include + +#else + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "compat.h" + +#endif /* REFTABLE_IN_GITCORE */ + +#define SHA1_ID 0x73686131 +#define SHA256_ID 0x73323536 +#define SHA1_SIZE 20 +#define SHA256_SIZE 32 + +typedef uint8_t byte; +typedef int bool; + +/* This is uncompress2, which is only available in zlib as of 2017. + * + * TODO: in git-core, this should fallback to uncompress2 if it is available. + */ +int uncompress_return_consumed(Bytef *dest, uLongf *destLen, + const Bytef *source, uLong *sourceLen); +int hash_size(uint32_t id); + +#endif diff --git a/reftable/tree.c b/reftable/tree.c new file mode 100644 index 00000000000..9bf7fe531ff --- /dev/null +++ b/reftable/tree.c @@ -0,0 +1,66 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#include "tree.h" + +#include "system.h" + +struct tree_node *tree_search(void *key, struct tree_node **rootp, + int (*compare)(const void *, const void *), + int insert) +{ + if (*rootp == NULL) { + if (!insert) { + return NULL; + } else { + struct tree_node *n = + calloc(sizeof(struct tree_node), 1); + n->key = key; + *rootp = n; + return *rootp; + } + } + + { + int res = compare(key, (*rootp)->key); + if (res < 0) { + return tree_search(key, &(*rootp)->left, compare, + insert); + } else if (res > 0) { + return tree_search(key, &(*rootp)->right, compare, + insert); + } + } + return *rootp; +} + +void infix_walk(struct tree_node *t, void (*action)(void *arg, void *key), + void *arg) +{ + if (t->left != NULL) { + infix_walk(t->left, action, arg); + } + action(arg, t->key); + if (t->right != NULL) { + infix_walk(t->right, action, arg); + } +} + +void tree_free(struct tree_node *t) +{ + if (t == NULL) { + return; + } + if (t->left != NULL) { + tree_free(t->left); + } + if (t->right != NULL) { + tree_free(t->right); + } + free(t); +} diff --git a/reftable/tree.h b/reftable/tree.h new file mode 100644 index 00000000000..86a71715aee --- /dev/null +++ b/reftable/tree.h @@ -0,0 +1,24 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#ifndef TREE_H +#define TREE_H + +struct tree_node { + void *key; + struct tree_node *left, *right; +}; + +struct tree_node *tree_search(void *key, struct tree_node **rootp, + int (*compare)(const void *, const void *), + int insert); +void infix_walk(struct tree_node *t, void (*action)(void *arg, void *key), + void *arg); +void tree_free(struct tree_node *t); + +#endif diff --git a/reftable/update.sh b/reftable/update.sh new file mode 100644 index 00000000000..70c0a7dee3e --- /dev/null +++ b/reftable/update.sh @@ -0,0 +1,13 @@ +#!/bin/sh + +set -eux + +((cd reftable-repo && git fetch origin && git checkout origin/master ) || +git clone https://github.com/google/reftable reftable-repo) && \ +cp reftable-repo/c/*.[ch] reftable/ && \ +cp reftable-repo/LICENSE reftable/ && +git --git-dir reftable-repo/.git show --no-patch origin/master \ +> reftable/VERSION && \ +sed -i~ 's|if REFTABLE_IN_GITCORE|if 1 /* REFTABLE_IN_GITCORE */|' reftable/system.h +rm reftable/*_test.c reftable/test_framework.* reftable/compat.* +git add reftable/*.[ch] diff --git a/reftable/writer.c b/reftable/writer.c new file mode 100644 index 00000000000..22331d193d0 --- /dev/null +++ b/reftable/writer.c @@ -0,0 +1,637 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#include "writer.h" + +#include "system.h" + +#include "block.h" +#include "constants.h" +#include "record.h" +#include "reftable.h" +#include "tree.h" + +static struct block_stats *writer_block_stats(struct writer *w, byte typ) +{ + switch (typ) { + case 'r': + return &w->stats.ref_stats; + case 'o': + return &w->stats.obj_stats; + case 'i': + return &w->stats.idx_stats; + case 'g': + return &w->stats.log_stats; + } + assert(false); + return NULL; +} + +/* write data, queuing the padding for the next write. Returns negative for + * error. */ +static int padded_write(struct writer *w, byte *data, size_t len, int padding) +{ + int n = 0; + if (w->pending_padding > 0) { + byte *zeroed = calloc(w->pending_padding, 1); + int n = w->write(w->write_arg, zeroed, w->pending_padding); + if (n < 0) { + return n; + } + + w->pending_padding = 0; + free(zeroed); + } + + w->pending_padding = padding; + n = w->write(w->write_arg, data, len); + if (n < 0) { + return n; + } + n += padding; + return 0; +} + +static void options_set_defaults(struct write_options *opts) +{ + if (opts->restart_interval == 0) { + opts->restart_interval = 16; + } + + if (opts->hash_id == 0) { + opts->hash_id = SHA1_ID; + } + if (opts->block_size == 0) { + opts->block_size = DEFAULT_BLOCK_SIZE; + } +} + +static int writer_write_header(struct writer *w, byte *dest) +{ + memcpy((char *)dest, "REFT", 4); + + /* DO NOT SUBMIT. This has not been encoded in the standard yet. */ + dest[4] = (hash_size(w->opts.hash_id) == SHA1_SIZE) ? 1 : 2; /* version + */ + + put_be24(dest + 5, w->opts.block_size); + put_be64(dest + 8, w->min_update_index); + put_be64(dest + 16, w->max_update_index); + return 24; +} + +static void writer_reinit_block_writer(struct writer *w, byte typ) +{ + int block_start = 0; + if (w->next == 0) { + block_start = HEADER_SIZE; + } + + block_writer_init(&w->block_writer_data, typ, w->block, + w->opts.block_size, block_start, + hash_size(w->opts.hash_id)); + w->block_writer = &w->block_writer_data; + w->block_writer->restart_interval = w->opts.restart_interval; +} + +struct writer *new_writer(int (*writer_func)(void *, byte *, int), + void *writer_arg, struct write_options *opts) +{ + struct writer *wp = calloc(sizeof(struct writer), 1); + options_set_defaults(opts); + if (opts->block_size >= (1 << 24)) { + /* TODO - error return? */ + abort(); + } + wp->block = calloc(opts->block_size, 1); + wp->write = writer_func; + wp->write_arg = writer_arg; + wp->opts = *opts; + writer_reinit_block_writer(wp, BLOCK_TYPE_REF); + + return wp; +} + +void writer_set_limits(struct writer *w, uint64_t min, uint64_t max) +{ + w->min_update_index = min; + w->max_update_index = max; +} + +void writer_free(struct writer *w) +{ + free(w->block); + free(w); +} + +struct obj_index_tree_node { + struct slice hash; + uint64_t *offsets; + int offset_len; + int offset_cap; +}; + +static int obj_index_tree_node_compare(const void *a, const void *b) +{ + return slice_compare(((const struct obj_index_tree_node *)a)->hash, + ((const struct obj_index_tree_node *)b)->hash); +} + +static void writer_index_hash(struct writer *w, struct slice hash) +{ + uint64_t off = w->next; + + struct obj_index_tree_node want = { .hash = hash }; + + struct tree_node *node = tree_search(&want, &w->obj_index_tree, + &obj_index_tree_node_compare, 0); + struct obj_index_tree_node *key = NULL; + if (node == NULL) { + key = calloc(sizeof(struct obj_index_tree_node), 1); + slice_copy(&key->hash, hash); + tree_search((void *)key, &w->obj_index_tree, + &obj_index_tree_node_compare, 1); + } else { + key = node->key; + } + + if (key->offset_len > 0 && key->offsets[key->offset_len - 1] == off) { + return; + } + + if (key->offset_len == key->offset_cap) { + key->offset_cap = 2 * key->offset_cap + 1; + key->offsets = realloc(key->offsets, + sizeof(uint64_t) * key->offset_cap); + } + + key->offsets[key->offset_len++] = off; +} + +static int writer_add_record(struct writer *w, struct record rec) +{ + int result = -1; + struct slice key = { 0 }; + int err = 0; + record_key(rec, &key); + if (slice_compare(w->last_key, key) >= 0) { + goto exit; + } + + slice_copy(&w->last_key, key); + if (w->block_writer == NULL) { + writer_reinit_block_writer(w, record_type(rec)); + } + + assert(block_writer_type(w->block_writer) == record_type(rec)); + + if (block_writer_add(w->block_writer, rec) == 0) { + result = 0; + goto exit; + } + + err = writer_flush_block(w); + if (err < 0) { + result = err; + goto exit; + } + + writer_reinit_block_writer(w, record_type(rec)); + err = block_writer_add(w->block_writer, rec); + if (err < 0) { + result = err; + goto exit; + } + + result = 0; +exit: + free(slice_yield(&key)); + return result; +} + +int writer_add_ref(struct writer *w, struct ref_record *ref) +{ + struct record rec = { 0 }; + struct ref_record copy = *ref; + int err = 0; + + if (ref->ref_name == NULL) { + return API_ERROR; + } + if (ref->update_index < w->min_update_index || + ref->update_index > w->max_update_index) { + return API_ERROR; + } + + record_from_ref(&rec, ©); + copy.update_index -= w->min_update_index; + err = writer_add_record(w, rec); + if (err < 0) { + return err; + } + + if (!w->opts.skip_index_objects && ref->value != NULL) { + struct slice h = { + .buf = ref->value, + .len = hash_size(w->opts.hash_id), + }; + + writer_index_hash(w, h); + } + if (!w->opts.skip_index_objects && ref->target_value != NULL) { + struct slice h = { + .buf = ref->target_value, + .len = hash_size(w->opts.hash_id), + }; + writer_index_hash(w, h); + } + return 0; +} + +int writer_add_refs(struct writer *w, struct ref_record *refs, int n) +{ + int err = 0; + int i = 0; + QSORT(refs, n, ref_record_compare_name); + for (i = 0; err == 0 && i < n; i++) { + err = writer_add_ref(w, &refs[i]); + } + return err; +} + +int writer_add_log(struct writer *w, struct log_record *log) +{ + if (log->ref_name == NULL) { + return API_ERROR; + } + + if (w->block_writer != NULL && + block_writer_type(w->block_writer) == BLOCK_TYPE_REF) { + int err = writer_finish_public_section(w); + if (err < 0) { + return err; + } + } + + w->next -= w->pending_padding; + w->pending_padding = 0; + + { + struct record rec = { 0 }; + int err; + record_from_log(&rec, log); + err = writer_add_record(w, rec); + return err; + } +} + +int writer_add_logs(struct writer *w, struct log_record *logs, int n) +{ + int err = 0; + int i = 0; + QSORT(logs, n, log_record_compare_key); + for (i = 0; err == 0 && i < n; i++) { + err = writer_add_log(w, &logs[i]); + } + return err; +} + +static int writer_finish_section(struct writer *w) +{ + byte typ = block_writer_type(w->block_writer); + uint64_t index_start = 0; + int max_level = 0; + int threshold = w->opts.unpadded ? 1 : 3; + int before_blocks = w->stats.idx_stats.blocks; + int err = writer_flush_block(w); + int i = 0; + if (err < 0) { + return err; + } + + while (w->index_len > threshold) { + struct index_record *idx = NULL; + int idx_len = 0; + + max_level++; + index_start = w->next; + writer_reinit_block_writer(w, BLOCK_TYPE_INDEX); + + idx = w->index; + idx_len = w->index_len; + + w->index = NULL; + w->index_len = 0; + w->index_cap = 0; + for (i = 0; i < idx_len; i++) { + struct record rec = { 0 }; + record_from_index(&rec, idx + i); + if (block_writer_add(w->block_writer, rec) == 0) { + continue; + } + + { + int err = writer_flush_block(w); + if (err < 0) { + return err; + } + } + + writer_reinit_block_writer(w, BLOCK_TYPE_INDEX); + + err = block_writer_add(w->block_writer, rec); + assert(err == 0); + } + for (i = 0; i < idx_len; i++) { + free(slice_yield(&idx[i].last_key)); + } + free(idx); + } + + writer_clear_index(w); + + err = writer_flush_block(w); + if (err < 0) { + return err; + } + + { + struct block_stats *bstats = writer_block_stats(w, typ); + bstats->index_blocks = + w->stats.idx_stats.blocks - before_blocks; + bstats->index_offset = index_start; + bstats->max_index_level = max_level; + } + + /* Reinit lastKey, as the next section can start with any key. */ + w->last_key.len = 0; + + return 0; +} + +struct common_prefix_arg { + struct slice *last; + int max; +}; + +static void update_common(void *void_arg, void *key) +{ + struct common_prefix_arg *arg = (struct common_prefix_arg *)void_arg; + struct obj_index_tree_node *entry = (struct obj_index_tree_node *)key; + if (arg->last != NULL) { + int n = common_prefix_size(entry->hash, *arg->last); + if (n > arg->max) { + arg->max = n; + } + } + arg->last = &entry->hash; +} + +struct write_record_arg { + struct writer *w; + int err; +}; + +static void write_object_record(void *void_arg, void *key) +{ + struct write_record_arg *arg = (struct write_record_arg *)void_arg; + struct obj_index_tree_node *entry = (struct obj_index_tree_node *)key; + struct obj_record obj_rec = { + .hash_prefix = entry->hash.buf, + .hash_prefix_len = arg->w->stats.object_id_len, + .offsets = entry->offsets, + .offset_len = entry->offset_len, + }; + struct record rec = { 0 }; + if (arg->err < 0) { + goto exit; + } + + record_from_obj(&rec, &obj_rec); + arg->err = block_writer_add(arg->w->block_writer, rec); + if (arg->err == 0) { + goto exit; + } + + arg->err = writer_flush_block(arg->w); + if (arg->err < 0) { + goto exit; + } + + writer_reinit_block_writer(arg->w, BLOCK_TYPE_OBJ); + arg->err = block_writer_add(arg->w->block_writer, rec); + if (arg->err == 0) { + goto exit; + } + obj_rec.offset_len = 0; + arg->err = block_writer_add(arg->w->block_writer, rec); + + /* Should be able to write into a fresh block. */ + assert(arg->err == 0); + +exit:; +} + +static void object_record_free(void *void_arg, void *key) +{ + struct obj_index_tree_node *entry = (struct obj_index_tree_node *)key; + + FREE_AND_NULL(entry->offsets); + free(slice_yield(&entry->hash)); + free(entry); +} + +static int writer_dump_object_index(struct writer *w) +{ + struct write_record_arg closure = { .w = w }; + struct common_prefix_arg common = { 0 }; + if (w->obj_index_tree != NULL) { + infix_walk(w->obj_index_tree, &update_common, &common); + } + w->stats.object_id_len = common.max + 1; + + writer_reinit_block_writer(w, BLOCK_TYPE_OBJ); + + if (w->obj_index_tree != NULL) { + infix_walk(w->obj_index_tree, &write_object_record, &closure); + } + + if (closure.err < 0) { + return closure.err; + } + return writer_finish_section(w); +} + +int writer_finish_public_section(struct writer *w) +{ + byte typ = 0; + int err = 0; + + if (w->block_writer == NULL) { + return 0; + } + + typ = block_writer_type(w->block_writer); + err = writer_finish_section(w); + if (err < 0) { + return err; + } + if (typ == BLOCK_TYPE_REF && !w->opts.skip_index_objects && + w->stats.ref_stats.index_blocks > 0) { + err = writer_dump_object_index(w); + if (err < 0) { + return err; + } + } + + if (w->obj_index_tree != NULL) { + infix_walk(w->obj_index_tree, &object_record_free, NULL); + tree_free(w->obj_index_tree); + w->obj_index_tree = NULL; + } + + w->block_writer = NULL; + return 0; +} + +int writer_close(struct writer *w) +{ + byte footer[68]; + byte *p = footer; + + int err = writer_finish_public_section(w); + if (err != 0) { + goto exit; + } + + writer_write_header(w, footer); + p += 24; + put_be64(p, w->stats.ref_stats.index_offset); + p += 8; + put_be64(p, (w->stats.obj_stats.offset) << 5 | w->stats.object_id_len); + p += 8; + put_be64(p, w->stats.obj_stats.index_offset); + p += 8; + + put_be64(p, w->stats.log_stats.offset); + p += 8; + put_be64(p, w->stats.log_stats.index_offset); + p += 8; + + put_be32(p, crc32(0, footer, p - footer)); + p += 4; + w->pending_padding = 0; + + err = padded_write(w, footer, sizeof(footer), 0); + if (err < 0) { + goto exit; + } + + if (w->stats.log_stats.entries + w->stats.ref_stats.entries == 0) { + err = EMPTY_TABLE_ERROR; + goto exit; + } + +exit: + /* free up memory. */ + block_writer_clear(&w->block_writer_data); + writer_clear_index(w); + free(slice_yield(&w->last_key)); + return err; +} + +void writer_clear_index(struct writer *w) +{ + int i = 0; + for (i = 0; i < w->index_len; i++) { + free(slice_yield(&w->index[i].last_key)); + } + + FREE_AND_NULL(w->index); + w->index_len = 0; + w->index_cap = 0; +} + +const int debug = 0; + +static int writer_flush_nonempty_block(struct writer *w) +{ + byte typ = block_writer_type(w->block_writer); + struct block_stats *bstats = writer_block_stats(w, typ); + uint64_t block_typ_off = (bstats->blocks == 0) ? w->next : 0; + int raw_bytes = block_writer_finish(w->block_writer); + int padding = 0; + int err = 0; + if (raw_bytes < 0) { + return raw_bytes; + } + + if (!w->opts.unpadded && typ != BLOCK_TYPE_LOG) { + padding = w->opts.block_size - raw_bytes; + } + + if (block_typ_off > 0) { + bstats->offset = block_typ_off; + } + + bstats->entries += w->block_writer->entries; + bstats->restarts += w->block_writer->restart_len; + bstats->blocks++; + w->stats.blocks++; + + if (debug) { + fprintf(stderr, "block %c off %" PRIu64 " sz %d (%d)\n", typ, + w->next, raw_bytes, + get_be24(w->block + w->block_writer->header_off + 1)); + } + + if (w->next == 0) { + writer_write_header(w, w->block); + } + + err = padded_write(w, w->block, raw_bytes, padding); + if (err < 0) { + return err; + } + + if (w->index_cap == w->index_len) { + w->index_cap = 2 * w->index_cap + 1; + w->index = realloc(w->index, + sizeof(struct index_record) * w->index_cap); + } + + { + struct index_record ir = { + .offset = w->next, + }; + slice_copy(&ir.last_key, w->block_writer->last_key); + w->index[w->index_len] = ir; + } + + w->index_len++; + w->next += padding + raw_bytes; + block_writer_reset(&w->block_writer_data); + w->block_writer = NULL; + return 0; +} + +int writer_flush_block(struct writer *w) +{ + if (w->block_writer == NULL) { + return 0; + } + if (w->block_writer->entries == 0) { + return 0; + } + return writer_flush_nonempty_block(w); +} + +struct stats *writer_stats(struct writer *w) +{ + return &w->stats; +} diff --git a/reftable/writer.h b/reftable/writer.h new file mode 100644 index 00000000000..42ad03e9ec6 --- /dev/null +++ b/reftable/writer.h @@ -0,0 +1,45 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#ifndef WRITER_H +#define WRITER_H + +#include "basics.h" +#include "block.h" +#include "reftable.h" +#include "slice.h" +#include "tree.h" + +struct writer { + int (*write)(void *, byte *, int); + void *write_arg; + int pending_padding; + struct slice last_key; + + uint64_t next; + uint64_t min_update_index, max_update_index; + struct write_options opts; + + byte *block; + struct block_writer *block_writer; + struct block_writer block_writer_data; + struct index_record *index; + int index_len; + int index_cap; + + /* tree for use with tsearch */ + struct tree_node *obj_index_tree; + + struct stats stats; +}; + +int writer_flush_block(struct writer *w); +void writer_clear_index(struct writer *w); +int writer_finish_public_section(struct writer *w); + +#endif diff --git a/reftable/zlib-compat.c b/reftable/zlib-compat.c new file mode 100644 index 00000000000..3e0b0f24f1c --- /dev/null +++ b/reftable/zlib-compat.c @@ -0,0 +1,92 @@ +/* taken from zlib's uncompr.c + + commit cacf7f1d4e3d44d871b605da3b647f07d718623f + Author: Mark Adler + Date: Sun Jan 15 09:18:46 2017 -0800 + + zlib 1.2.11 + +*/ + +/* + * Copyright (C) 1995-2003, 2010, 2014, 2016 Jean-loup Gailly, Mark Adler + * For conditions of distribution and use, see copyright notice in zlib.h + */ + +#include "system.h" + +/* clang-format off */ + +/* =========================================================================== + Decompresses the source buffer into the destination buffer. *sourceLen is + the byte length of the source buffer. Upon entry, *destLen is the total size + of the destination buffer, which must be large enough to hold the entire + uncompressed data. (The size of the uncompressed data must have been saved + previously by the compressor and transmitted to the decompressor by some + mechanism outside the scope of this compression library.) Upon exit, + *destLen is the size of the decompressed data and *sourceLen is the number + of source bytes consumed. Upon return, source + *sourceLen points to the + first unused input byte. + + uncompress returns Z_OK if success, Z_MEM_ERROR if there was not enough + memory, Z_BUF_ERROR if there was not enough room in the output buffer, or + Z_DATA_ERROR if the input data was corrupted, including if the input data is + an incomplete zlib stream. +*/ +int ZEXPORT uncompress_return_consumed ( + Bytef *dest, + uLongf *destLen, + const Bytef *source, + uLong *sourceLen) { + z_stream stream; + int err; + const uInt max = (uInt)-1; + uLong len, left; + Byte buf[1]; /* for detection of incomplete stream when *destLen == 0 */ + + len = *sourceLen; + if (*destLen) { + left = *destLen; + *destLen = 0; + } + else { + left = 1; + dest = buf; + } + + stream.next_in = (z_const Bytef *)source; + stream.avail_in = 0; + stream.zalloc = (alloc_func)0; + stream.zfree = (free_func)0; + stream.opaque = (voidpf)0; + + err = inflateInit(&stream); + if (err != Z_OK) return err; + + stream.next_out = dest; + stream.avail_out = 0; + + do { + if (stream.avail_out == 0) { + stream.avail_out = left > (uLong)max ? max : (uInt)left; + left -= stream.avail_out; + } + if (stream.avail_in == 0) { + stream.avail_in = len > (uLong)max ? max : (uInt)len; + len -= stream.avail_in; + } + err = inflate(&stream, Z_NO_FLUSH); + } while (err == Z_OK); + + *sourceLen -= len + stream.avail_in; + if (dest != buf) + *destLen = stream.total_out; + else if (stream.total_out && err == Z_BUF_ERROR) + left = 1; + + inflateEnd(&stream); + return err == Z_STREAM_END ? Z_OK : + err == Z_NEED_DICT ? Z_DATA_ERROR : + err == Z_BUF_ERROR && left + stream.avail_out ? Z_DATA_ERROR : + err; +} From patchwork Wed Feb 26 08:49:46 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Linus Arver via GitGitGadget X-Patchwork-Id: 11405595 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 998411805 for ; Wed, 26 Feb 2020 08:50:01 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 4A4D12084E for ; Wed, 26 Feb 2020 08:50:01 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Bju23RA5" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727267AbgBZIuA (ORCPT ); Wed, 26 Feb 2020 03:50:00 -0500 Received: from mail-ed1-f49.google.com ([209.85.208.49]:33050 "EHLO mail-ed1-f49.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727163AbgBZIt7 (ORCPT ); Wed, 26 Feb 2020 03:49:59 -0500 Received: by mail-ed1-f49.google.com with SMTP id r21so2829444edq.0 for ; Wed, 26 Feb 2020 00:49:55 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=GhYxR2AmMYPBC9EYLUmb0yfgxoaimXr1rzRs0GJIJUk=; b=Bju23RA53fiaO0y5CaI0lymEqLhx7V7o3siX3LTOBDAn9WnHIEFPSZ8Cif6AutjcDu qJISBUGe2QoW/PPiqli9fJTLFbuWf2ps+4MguMrfNb54JGUY/5AEwDCYbg7I8z3QrnFC 0RGVl1Ow+rFspMhWrsWgPkUU7Mnl1V26xBvL/HJgFuzZ9yofLgf5U8f2wVwZBe6L2Jdd OUJJtCERbZJA5QdyxRBwcGAKjWTBnimcnguknmZ8NV4rS47l+XZZgd2du1bEZNm2Dlzr 27ZFa9Fy0BLzkNVhaiTCbGdnZ7zTgtxbexDRpyaTu+3eQO3EqxOWRDBq989Y8fJw4D1q ksCA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=GhYxR2AmMYPBC9EYLUmb0yfgxoaimXr1rzRs0GJIJUk=; b=Nbes1ltumjxiirLGADNS9/kutQZIRJb7PencGok71RbLiA16b8e9Dp4RcKw0rG7/Yz 0HG40pCrPwwsFVgz5ThPqWeGmzTvk7uiWaCsUWeTGXEhJc3mdgkeopQBYsdLve+EfIB1 Yq6GsPJn7FUDvtKW7kXDgLd5o6SSzle0qqGE7+cHN8/8BtSpFacVgruNUfv1ltWnK5S9 bBzoSONwLuvfAx9Hxkk7ZFFTW/0IYtD0sCrAzb6H/9SBD0LVhDly07GnkJ7YbRGXrlJf LI9yAdFJFdZMC1UlREXQGDNIbPGfEHCxUwvFLEc5ANtaVrqs53aJ9ghN9cGmrzSSRs76 2R9Q== X-Gm-Message-State: APjAAAVYgylwW1iCa7/a0n9JYcLM5kLhwf5Uwbxn/3b+52YA1m5Ai/fz L2zwIp1jWfHqlgTGlp9hsYHgNpfn X-Google-Smtp-Source: APXvYqwZPANaCSvH1ejG1Yc5q6qL12qSAN9+/2mAxa6mACioqNmhmVr3HYQc+QSPRtQMuJ6D3Ynh6w== X-Received: by 2002:a50:f612:: with SMTP id c18mr3504318edn.1.1582706993814; Wed, 26 Feb 2020 00:49:53 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id f25sm54844edt.73.2020.02.26.00.49.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 26 Feb 2020 00:49:53 -0800 (PST) Message-Id: In-Reply-To: References: From: "Han-Wen Nienhuys via GitGitGadget" Date: Wed, 26 Feb 2020 08:49:46 +0000 Subject: [PATCH v7 6/6] Reftable support for git-core Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Han-Wen Nienhuys , Han-Wen Nienhuys Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Han-Wen Nienhuys For background, see the previous commit introducing the library. TODO: * Resolve spots marked with XXX * Test strategy? Example use: see t/t0031-reftable.sh Signed-off-by: Han-Wen Nienhuys Co-authored-by: Jeff King --- .../technical/repository-version.txt | 7 + Makefile | 24 +- builtin/clone.c | 4 +- builtin/init-db.c | 55 +- cache.h | 4 +- refs.c | 20 +- refs.h | 3 + refs/refs-internal.h | 1 + refs/reftable-backend.c | 1015 +++++++++++++++++ repository.c | 2 + repository.h | 3 + setup.c | 12 +- t/t0031-reftable.sh | 31 + 13 files changed, 1152 insertions(+), 29 deletions(-) create mode 100644 refs/reftable-backend.c create mode 100755 t/t0031-reftable.sh diff --git a/Documentation/technical/repository-version.txt b/Documentation/technical/repository-version.txt index 7844ef30ffd..72576235833 100644 --- a/Documentation/technical/repository-version.txt +++ b/Documentation/technical/repository-version.txt @@ -100,3 +100,10 @@ If set, by default "git config" reads from both "config" and multiple working directory mode, "config" file is shared while "config.worktree" is per-working directory (i.e., it's in GIT_COMMON_DIR/worktrees//config.worktree) + +==== `refStorage` + +Specifies the file format for the ref database. Values are `files` +(for the traditional packed + loose ref format) and `reftable` for the +binary reftable format. See https://github.com/google/reftable for +more information. diff --git a/Makefile b/Makefile index 6134104ae65..706bb0a9814 100644 --- a/Makefile +++ b/Makefile @@ -814,6 +814,7 @@ TEST_SHELL_PATH = $(SHELL_PATH) LIB_FILE = libgit.a XDIFF_LIB = xdiff/lib.a VCSSVN_LIB = vcs-svn/lib.a +REFTABLE_LIB = reftable/libreftable.a GENERATED_H += command-list.h @@ -959,6 +960,7 @@ LIB_OBJS += rebase-interactive.o LIB_OBJS += reflog-walk.o LIB_OBJS += refs.o LIB_OBJS += refs/files-backend.o +LIB_OBJS += refs/reftable-backend.o LIB_OBJS += refs/iterator.o LIB_OBJS += refs/packed-backend.o LIB_OBJS += refs/ref-cache.o @@ -1163,7 +1165,7 @@ THIRD_PARTY_SOURCES += compat/regex/% THIRD_PARTY_SOURCES += sha1collisiondetection/% THIRD_PARTY_SOURCES += sha1dc/% -GITLIBS = common-main.o $(LIB_FILE) $(XDIFF_LIB) +GITLIBS = common-main.o $(LIB_FILE) $(XDIFF_LIB) $(REFTABLE_LIB) EXTLIBS = GIT_USER_AGENT = git/$(GIT_VERSION) @@ -2347,11 +2349,28 @@ VCSSVN_OBJS += vcs-svn/fast_export.o VCSSVN_OBJS += vcs-svn/svndiff.o VCSSVN_OBJS += vcs-svn/svndump.o +REFTABLE_OBJS += reftable/basics.o +REFTABLE_OBJS += reftable/block.o +REFTABLE_OBJS += reftable/bytes.o +REFTABLE_OBJS += reftable/file.o +REFTABLE_OBJS += reftable/iter.o +REFTABLE_OBJS += reftable/merged.o +REFTABLE_OBJS += reftable/pq.o +REFTABLE_OBJS += reftable/reader.o +REFTABLE_OBJS += reftable/record.o +REFTABLE_OBJS += reftable/slice.o +REFTABLE_OBJS += reftable/stack.o +REFTABLE_OBJS += reftable/tree.o +REFTABLE_OBJS += reftable/writer.o +REFTABLE_OBJS += reftable/zlib-compat.o + + TEST_OBJS := $(patsubst %$X,%.o,$(TEST_PROGRAMS)) $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS)) OBJECTS := $(LIB_OBJS) $(BUILTIN_OBJS) $(PROGRAM_OBJS) $(TEST_OBJS) \ $(XDIFF_OBJS) \ $(VCSSVN_OBJS) \ $(FUZZ_OBJS) \ + $(REFTABLE_OBJS) \ common-main.o \ git.o ifndef NO_CURL @@ -2488,6 +2507,9 @@ $(XDIFF_LIB): $(XDIFF_OBJS) $(VCSSVN_LIB): $(VCSSVN_OBJS) $(QUIET_AR)$(RM) $@ && $(AR) $(ARFLAGS) $@ $^ +$(REFTABLE_LIB): $(REFTABLE_OBJS) + $(QUIET_AR)$(RM) $@ && $(AR) $(ARFLAGS) $@ $^ + export DEFAULT_EDITOR DEFAULT_PAGER Documentation/GIT-EXCLUDED-PROGRAMS: FORCE diff --git a/builtin/clone.c b/builtin/clone.c index 4f6150c55c3..4bcea0c18da 100644 --- a/builtin/clone.c +++ b/builtin/clone.c @@ -1097,7 +1097,9 @@ int cmd_clone(int argc, const char **argv, const char *prefix) } } - init_db(git_dir, real_git_dir, option_template, INIT_DB_QUIET); + init_db(git_dir, real_git_dir, option_template, + DEFAULT_REF_STORAGE, /* XXX */ + INIT_DB_QUIET); if (real_git_dir) git_dir = real_git_dir; diff --git a/builtin/init-db.c b/builtin/init-db.c index 45bdea05890..d51a99ed77e 100644 --- a/builtin/init-db.c +++ b/builtin/init-db.c @@ -177,7 +177,8 @@ static int needs_work_tree_config(const char *git_dir, const char *work_tree) } static int create_default_files(const char *template_path, - const char *original_git_dir) + const char *original_git_dir, + const char *ref_storage_format, int flags) { struct stat st1; struct strbuf buf = STRBUF_INIT; @@ -213,6 +214,7 @@ static int create_default_files(const char *template_path, is_bare_repository_cfg = init_is_bare_repository; if (init_shared_repository != -1) set_shared_repository(init_shared_repository); + the_repository->ref_storage_format = xstrdup(ref_storage_format); /* * We would have created the above under user's umask -- under @@ -222,6 +224,15 @@ static int create_default_files(const char *template_path, adjust_shared_perm(get_git_dir()); } + /* + * Check to see if .git/HEAD exists; this must happen before + * initializing the ref db, because we want to see if there is an + * existing HEAD. + */ + path = git_path_buf(&buf, "HEAD"); + reinit = (!access(path, R_OK) || + readlink(path, junk, sizeof(junk) - 1) != -1); + /* * We need to create a "refs" dir in any case so that older * versions of git can tell that this is a repository. @@ -234,17 +245,21 @@ static int create_default_files(const char *template_path, * Create the default symlink from ".git/HEAD" to the "master" * branch, if it does not exist yet. */ - path = git_path_buf(&buf, "HEAD"); - reinit = (!access(path, R_OK) - || readlink(path, junk, sizeof(junk)-1) != -1); if (!reinit) { if (create_symref("HEAD", "refs/heads/master", NULL) < 0) exit(1); + } else { + /* + * XXX should check whether our ref backend matches the + * original one; if not, either die() or convert + */ } /* This forces creation of new config file */ - xsnprintf(repo_version_string, sizeof(repo_version_string), - "%d", GIT_REPO_VERSION); + xsnprintf(repo_version_string, sizeof(repo_version_string), "%d", + !strcmp(ref_storage_format, "reftable") ? + GIT_REPO_VERSION_READ : + GIT_REPO_VERSION); git_config_set("core.repositoryformatversion", repo_version_string); /* Check filemode trustability */ @@ -339,7 +354,8 @@ static void separate_git_dir(const char *git_dir, const char *git_link) } int init_db(const char *git_dir, const char *real_git_dir, - const char *template_dir, unsigned int flags) + const char *template_dir, const char *ref_storage_format, + unsigned int flags) { int reinit; int exist_ok = flags & INIT_DB_EXIST_OK; @@ -378,7 +394,8 @@ int init_db(const char *git_dir, const char *real_git_dir, */ check_repository_format(); - reinit = create_default_files(template_dir, original_git_dir); + reinit = create_default_files(template_dir, original_git_dir, + ref_storage_format, flags); create_object_directory(); @@ -403,6 +420,8 @@ int init_db(const char *git_dir, const char *real_git_dir, git_config_set("receive.denyNonFastforwards", "true"); } + git_config_set("extensions.refStorage", ref_storage_format); + if (!(flags & INIT_DB_QUIET)) { int len = strlen(git_dir); @@ -476,20 +495,24 @@ static const char *const init_db_usage[] = { int cmd_init_db(int argc, const char **argv, const char *prefix) { const char *git_dir; + const char *ref_storage_format = DEFAULT_REF_STORAGE; const char *real_git_dir = NULL; const char *work_tree; const char *template_dir = NULL; unsigned int flags = 0; const struct option init_db_options[] = { - OPT_STRING(0, "template", &template_dir, N_("template-directory"), - N_("directory from which templates will be used")), + OPT_STRING(0, "template", &template_dir, + N_("template-directory"), + N_("directory from which templates will be used")), OPT_SET_INT(0, "bare", &is_bare_repository_cfg, - N_("create a bare repository"), 1), + N_("create a bare repository"), 1), { OPTION_CALLBACK, 0, "shared", &init_shared_repository, - N_("permissions"), - N_("specify that the git repository is to be shared amongst several users"), - PARSE_OPT_OPTARG | PARSE_OPT_NONEG, shared_callback, 0}, + N_("permissions"), + N_("specify that the git repository is to be shared amongst several users"), + PARSE_OPT_OPTARG | PARSE_OPT_NONEG, shared_callback, 0 }, OPT_BIT('q', "quiet", &flags, N_("be quiet"), INIT_DB_QUIET), + OPT_STRING(0, "ref-storage", &ref_storage_format, N_("backend"), + N_("the ref storage format to use")), OPT_STRING(0, "separate-git-dir", &real_git_dir, N_("gitdir"), N_("separate git dir from working tree")), OPT_END() @@ -591,9 +614,11 @@ int cmd_init_db(int argc, const char **argv, const char *prefix) } UNLEAK(real_git_dir); + UNLEAK(ref_storage_format); UNLEAK(git_dir); UNLEAK(work_tree); flags |= INIT_DB_EXIST_OK; - return init_db(git_dir, real_git_dir, template_dir, flags); + return init_db(git_dir, real_git_dir, template_dir, ref_storage_format, + flags); } diff --git a/cache.h b/cache.h index 37c899b53f7..4d905e2d565 100644 --- a/cache.h +++ b/cache.h @@ -627,7 +627,8 @@ int path_inside_repo(const char *prefix, const char *path); #define INIT_DB_EXIST_OK 0x0002 int init_db(const char *git_dir, const char *real_git_dir, - const char *template_dir, unsigned int flags); + const char *template_dir, const char *ref_storage_format, + unsigned int flags); void sanitize_stdfds(void); int daemonize(void); @@ -1041,6 +1042,7 @@ struct repository_format { int is_bare; int hash_algo; char *work_tree; + char *ref_storage; struct string_list unknown_extensions; }; diff --git a/refs.c b/refs.c index 1ab0bb54d3d..6530219762f 100644 --- a/refs.c +++ b/refs.c @@ -20,7 +20,7 @@ /* * List of all available backends */ -static struct ref_storage_be *refs_backends = &refs_be_files; +static struct ref_storage_be *refs_backends = &refs_be_reftable; static struct ref_storage_be *find_ref_storage_backend(const char *name) { @@ -1836,13 +1836,13 @@ static struct ref_store *lookup_ref_store_map(struct hashmap *map, * Create, record, and return a ref_store instance for the specified * gitdir. */ -static struct ref_store *ref_store_init(const char *gitdir, +static struct ref_store *ref_store_init(const char *gitdir, const char *be_name, unsigned int flags) { - const char *be_name = "files"; - struct ref_storage_be *be = find_ref_storage_backend(be_name); + struct ref_storage_be *be; struct ref_store *refs; + be = find_ref_storage_backend(be_name); if (!be) BUG("reference backend %s is unknown", be_name); @@ -1858,7 +1858,10 @@ struct ref_store *get_main_ref_store(struct repository *r) if (!r->gitdir) BUG("attempting to get main_ref_store outside of repository"); - r->refs = ref_store_init(r->gitdir, REF_STORE_ALL_CAPS); + r->refs = ref_store_init(r->gitdir, + r->ref_storage_format ? r->ref_storage_format : + DEFAULT_REF_STORAGE, + REF_STORE_ALL_CAPS); return r->refs; } @@ -1913,7 +1916,7 @@ struct ref_store *get_submodule_ref_store(const char *submodule) goto done; /* assume that add_submodule_odb() has been called */ - refs = ref_store_init(submodule_sb.buf, + refs = ref_store_init(submodule_sb.buf, DEFAULT_REF_STORAGE, /* XXX */ REF_STORE_READ | REF_STORE_ODB); register_ref_store_map(&submodule_ref_stores, "submodule", refs, submodule); @@ -1927,6 +1930,7 @@ struct ref_store *get_submodule_ref_store(const char *submodule) struct ref_store *get_worktree_ref_store(const struct worktree *wt) { + const char *format = DEFAULT_REF_STORAGE; /* XXX */ struct ref_store *refs; const char *id; @@ -1940,9 +1944,9 @@ struct ref_store *get_worktree_ref_store(const struct worktree *wt) if (wt->id) refs = ref_store_init(git_common_path("worktrees/%s", wt->id), - REF_STORE_ALL_CAPS); + format, REF_STORE_ALL_CAPS); else - refs = ref_store_init(get_git_common_dir(), + refs = ref_store_init(get_git_common_dir(), format, REF_STORE_ALL_CAPS); if (refs) diff --git a/refs.h b/refs.h index 87c9ec921b9..2b5985ad593 100644 --- a/refs.h +++ b/refs.h @@ -9,6 +9,9 @@ struct string_list; struct string_list_item; struct worktree; +/* XXX where should this be? */ +#define DEFAULT_REF_STORAGE "files" + /* * Resolve a reference, recursively following symbolic refererences. * diff --git a/refs/refs-internal.h b/refs/refs-internal.h index 3490aac3a40..cafe5b97376 100644 --- a/refs/refs-internal.h +++ b/refs/refs-internal.h @@ -661,6 +661,7 @@ struct ref_storage_be { }; extern struct ref_storage_be refs_be_files; +extern struct ref_storage_be refs_be_reftable; extern struct ref_storage_be refs_be_packed; /* diff --git a/refs/reftable-backend.c b/refs/reftable-backend.c new file mode 100644 index 00000000000..4279c06010c --- /dev/null +++ b/refs/reftable-backend.c @@ -0,0 +1,1015 @@ +#include "../cache.h" +#include "../config.h" +#include "../refs.h" +#include "refs-internal.h" +#include "../iterator.h" +#include "../lockfile.h" +#include "../chdir-notify.h" + +#include "../reftable/reftable.h" + +extern struct ref_storage_be refs_be_reftable; + +struct reftable_ref_store { + struct ref_store base; + unsigned int store_flags; + + int err; + char *reftable_dir; + char *table_list_file; + struct stack *stack; +}; + +static void clear_log_record(struct log_record *log) +{ + log->old_hash = NULL; + log->new_hash = NULL; + log->message = NULL; + log->ref_name = NULL; + log_record_clear(log); +} + +static void fill_log_record(struct log_record *log) +{ + const char *info = git_committer_info(0); + struct ident_split split = {}; + int result = split_ident_line(&split, info, strlen(info)); + int sign = 1; + assert(0 == result); + + log_record_clear(log); + log->name = + xstrndup(split.name_begin, split.name_end - split.name_begin); + log->email = + xstrndup(split.mail_begin, split.mail_end - split.mail_begin); + log->time = atol(split.date_begin); + if (*split.tz_begin == '-') { + sign = -1; + split.tz_begin++; + } + if (*split.tz_begin == '+') { + sign = 1; + split.tz_begin++; + } + + log->tz_offset = sign * atoi(split.tz_begin); +} + +static struct ref_store *reftable_ref_store_create(const char *path, + unsigned int store_flags) +{ + struct reftable_ref_store *refs = xcalloc(1, sizeof(*refs)); + struct ref_store *ref_store = (struct ref_store *)refs; + struct write_options cfg = { + .block_size = 4096, + .hash_id = the_hash_algo->format_id, + }; + struct strbuf sb = STRBUF_INIT; + + base_ref_store_init(ref_store, &refs_be_reftable); + refs->store_flags = store_flags; + + strbuf_addf(&sb, "%s/reftable", path); + refs->reftable_dir = xstrdup(sb.buf); + strbuf_reset(&sb); + + strbuf_addf(&sb, "%s/reftable/tables.list", path); + refs->table_list_file = xstrdup(sb.buf); + strbuf_reset(&sb); + + strbuf_addf(&sb, "%s/refs", path); + safe_create_dir(sb.buf, 1); + strbuf_reset(&sb); + + strbuf_addf(&sb, "%s/HEAD", path); + write_file(sb.buf, "ref: refs/.invalid"); + strbuf_reset(&sb); + + strbuf_addf(&sb, "%s/refs/heads", path); + write_file(sb.buf, "this repository uses the reftable format"); + + refs->err = new_stack(&refs->stack, refs->reftable_dir, + refs->table_list_file, cfg); + strbuf_release(&sb); + return ref_store; +} + +static int reftable_init_db(struct ref_store *ref_store, struct strbuf *err) +{ + struct reftable_ref_store *refs = + (struct reftable_ref_store *)ref_store; + FILE *file; + safe_create_dir(refs->reftable_dir, 1); + + file = fopen(refs->table_list_file, "a"); + if (file == NULL) { + return -1; + } + fclose(file); + return 0; +} + +struct reftable_iterator { + struct ref_iterator base; + struct iterator iter; + struct ref_record ref; + struct object_id oid; + struct ref_store *ref_store; + unsigned int flags; + int err; + char *prefix; +}; + +static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator) +{ + struct reftable_iterator *ri = (struct reftable_iterator *)ref_iterator; + while (ri->err == 0) { + ri->err = iterator_next_ref(ri->iter, &ri->ref); + if (ri->err) { + break; + } + + ri->base.refname = ri->ref.ref_name; + if (ri->prefix != NULL && + strncmp(ri->prefix, ri->ref.ref_name, strlen(ri->prefix))) { + ri->err = 1; + break; + } + if (ri->flags & DO_FOR_EACH_PER_WORKTREE_ONLY && + ref_type(ri->base.refname) != REF_TYPE_PER_WORKTREE) + continue; + + ri->base.flags = 0; + if (ri->ref.value != NULL) { + hashcpy(ri->oid.hash, ri->ref.value); + } else if (ri->ref.target != NULL) { + int out_flags = 0; + const char *resolved = refs_resolve_ref_unsafe( + ri->ref_store, ri->ref.ref_name, + RESOLVE_REF_READING, &ri->oid, &out_flags); + ri->base.flags = out_flags; + if (resolved == NULL && + !(ri->flags & DO_FOR_EACH_INCLUDE_BROKEN) && + (ri->base.flags & REF_ISBROKEN)) { + continue; + } + } + + ri->base.oid = &ri->oid; + if (!(ri->flags & DO_FOR_EACH_INCLUDE_BROKEN) && + !ref_resolves_to_object(ri->base.refname, ri->base.oid, + ri->base.flags)) { + continue; + } + + break; + } + + if (ri->err > 0) { + return ITER_DONE; + } + if (ri->err < 0) { + return ITER_ERROR; + } + + return ITER_OK; +} + +static int reftable_ref_iterator_peel(struct ref_iterator *ref_iterator, + struct object_id *peeled) +{ + struct reftable_iterator *ri = (struct reftable_iterator *)ref_iterator; + if (ri->ref.target_value != NULL) { + hashcpy(peeled->hash, ri->ref.target_value); + return 0; + } + + return -1; +} + +static int reftable_ref_iterator_abort(struct ref_iterator *ref_iterator) +{ + struct reftable_iterator *ri = (struct reftable_iterator *)ref_iterator; + ref_record_clear(&ri->ref); + iterator_destroy(&ri->iter); + return 0; +} + +static struct ref_iterator_vtable reftable_ref_iterator_vtable = { + reftable_ref_iterator_advance, reftable_ref_iterator_peel, + reftable_ref_iterator_abort +}; + +static struct ref_iterator * +reftable_ref_iterator_begin(struct ref_store *ref_store, const char *prefix, + unsigned int flags) +{ + struct reftable_ref_store *refs = + (struct reftable_ref_store *)ref_store; + struct reftable_iterator *ri = xcalloc(1, sizeof(*ri)); + struct merged_table *mt = NULL; + + if (refs->err < 0) { + ri->err = refs->err; + } else { + mt = stack_merged_table(refs->stack); + ri->err = merged_table_seek_ref(mt, &ri->iter, prefix); + } + + base_ref_iterator_init(&ri->base, &reftable_ref_iterator_vtable, 1); + ri->base.oid = &ri->oid; + ri->flags = flags; + ri->ref_store = ref_store; + return &ri->base; +} + +static int reftable_transaction_prepare(struct ref_store *ref_store, + struct ref_transaction *transaction, + struct strbuf *err) +{ + return 0; +} + +static int reftable_transaction_abort(struct ref_store *ref_store, + struct ref_transaction *transaction, + struct strbuf *err) +{ + struct reftable_ref_store *refs = + (struct reftable_ref_store *)ref_store; + (void)refs; + return 0; +} + +static int reftable_check_old_oid(struct ref_store *refs, const char *refname, + struct object_id *want_oid) +{ + struct object_id out_oid = {}; + int out_flags = 0; + const char *resolved = refs_resolve_ref_unsafe( + refs, refname, RESOLVE_REF_READING, &out_oid, &out_flags); + if (is_null_oid(want_oid) != (resolved == NULL)) { + return LOCK_ERROR; + } + + if (resolved != NULL && !oideq(&out_oid, want_oid)) { + return LOCK_ERROR; + } + + return 0; +} + +static int ref_update_cmp(const void *a, const void *b) +{ + return strcmp(((struct ref_update *)a)->refname, + ((struct ref_update *)b)->refname); +} + +static int write_transaction_table(struct writer *writer, void *arg) +{ + struct ref_transaction *transaction = (struct ref_transaction *)arg; + struct reftable_ref_store *refs = + (struct reftable_ref_store *)transaction->ref_store; + uint64_t ts = stack_next_update_index(refs->stack); + int err = 0; + struct log_record *logs = calloc(transaction->nr, sizeof(*logs)); + struct ref_update **sorted = + malloc(transaction->nr * sizeof(struct ref_update *)); + COPY_ARRAY(sorted, transaction->updates, transaction->nr); + QSORT(sorted, transaction->nr, ref_update_cmp); + writer_set_limits(writer, ts, ts); + + for (int i = 0; i < transaction->nr; i++) { + struct ref_update *u = sorted[i]; + if (u->flags & REF_HAVE_OLD) { + err = reftable_check_old_oid(transaction->ref_store, + u->refname, &u->old_oid); + if (err < 0) { + goto exit; + } + } + } + + for (int i = 0; i < transaction->nr; i++) { + struct ref_update *u = sorted[i]; + struct log_record *log = &logs[i]; + fill_log_record(log); + log->ref_name = (char *)u->refname; + log->old_hash = u->old_oid.hash; + log->new_hash = u->new_oid.hash; + log->update_index = ts; + log->message = u->msg; + + if (u->flags & REF_HAVE_NEW) { + struct object_id out_oid = {}; + int out_flags = 0; + /* Memory owned by refs_resolve_ref_unsafe, no need to + * free(). */ + const char *resolved = refs_resolve_ref_unsafe( + transaction->ref_store, u->refname, 0, &out_oid, + &out_flags); + struct ref_record ref = {}; + ref.ref_name = + (char *)(resolved ? resolved : u->refname); + log->ref_name = ref.ref_name; + ref.value = u->new_oid.hash; + ref.update_index = ts; + err = writer_add_ref(writer, &ref); + if (err < 0) { + goto exit; + } + } + } + + for (int i = 0; i < transaction->nr; i++) { + err = writer_add_log(writer, &logs[i]); + clear_log_record(&logs[i]); + if (err < 0) { + goto exit; + } + } + +exit: + free(logs); + free(sorted); + return err; +} + +static int reftable_transaction_commit(struct ref_store *ref_store, + struct ref_transaction *transaction, + struct strbuf *errmsg) +{ + struct reftable_ref_store *refs = + (struct reftable_ref_store *)ref_store; + int err = 0; + if (refs->err < 0) { + return refs->err; + } + + err = stack_add(refs->stack, &write_transaction_table, transaction); + if (err < 0) { + strbuf_addf(errmsg, "reftable: transaction failure %s", + error_str(err)); + return -1; + } + + return 0; +} + +static int reftable_transaction_finish(struct ref_store *ref_store, + struct ref_transaction *transaction, + struct strbuf *err) +{ + return reftable_transaction_commit(ref_store, transaction, err); +} + +struct write_delete_refs_arg { + struct stack *stack; + struct string_list *refnames; + const char *logmsg; + unsigned int flags; +}; + +static int write_delete_refs_table(struct writer *writer, void *argv) +{ + struct write_delete_refs_arg *arg = + (struct write_delete_refs_arg *)argv; + uint64_t ts = stack_next_update_index(arg->stack); + int err = 0; + + writer_set_limits(writer, ts, ts); + for (int i = 0; i < arg->refnames->nr; i++) { + struct ref_record ref = { + .ref_name = (char *)arg->refnames->items[i].string, + .update_index = ts, + }; + err = writer_add_ref(writer, &ref); + if (err < 0) { + return err; + } + } + + for (int i = 0; i < arg->refnames->nr; i++) { + struct log_record log = {}; + struct ref_record current = {}; + fill_log_record(&log); + log.message = xstrdup(arg->logmsg); + log.new_hash = NULL; + log.old_hash = NULL; + log.update_index = ts; + log.ref_name = (char *)arg->refnames->items[i].string; + + if (stack_read_ref(arg->stack, log.ref_name, ¤t) == 0) { + log.old_hash = current.value; + } + err = writer_add_log(writer, &log); + log.old_hash = NULL; + ref_record_clear(¤t); + + clear_log_record(&log); + if (err < 0) { + return err; + } + } + return 0; +} + +static int reftable_delete_refs(struct ref_store *ref_store, const char *msg, + struct string_list *refnames, + unsigned int flags) +{ + struct reftable_ref_store *refs = + (struct reftable_ref_store *)ref_store; + struct write_delete_refs_arg arg = { + .stack = refs->stack, + .refnames = refnames, + .logmsg = msg, + .flags = flags, + }; + if (refs->err < 0) { + return refs->err; + } + + return stack_add(refs->stack, &write_delete_refs_table, &arg); +} + +static int reftable_pack_refs(struct ref_store *ref_store, unsigned int flags) +{ + struct reftable_ref_store *refs = + (struct reftable_ref_store *)ref_store; + if (refs->err < 0) { + return refs->err; + } + return stack_compact_all(refs->stack, NULL); +} + +struct write_create_symref_arg { + struct reftable_ref_store *refs; + const char *refname; + const char *target; + const char *logmsg; +}; + +static int write_create_symref_table(struct writer *writer, void *arg) +{ + struct write_create_symref_arg *create = + (struct write_create_symref_arg *)arg; + uint64_t ts = stack_next_update_index(create->refs->stack); + int err = 0; + + struct ref_record ref = { + .ref_name = (char *)create->refname, + .target = (char *)create->target, + .update_index = ts, + }; + writer_set_limits(writer, ts, ts); + err = writer_add_ref(writer, &ref); + if (err < 0) { + return err; + } + + { + struct log_record log = {}; + struct object_id new_oid = {}; + struct object_id old_oid = {}; + struct ref_record current = {}; + stack_read_ref(create->refs->stack, create->refname, ¤t); + + fill_log_record(&log); + log.ref_name = current.ref_name; + if (refs_resolve_ref_unsafe( + (struct ref_store *)create->refs, create->refname, + RESOLVE_REF_READING, &old_oid, NULL) != NULL) { + log.old_hash = old_oid.hash; + } + + if (refs_resolve_ref_unsafe((struct ref_store *)create->refs, + create->target, RESOLVE_REF_READING, + &new_oid, NULL) != NULL) { + log.new_hash = new_oid.hash; + } + + if (log.old_hash != NULL || log.new_hash != NULL) { + writer_add_log(writer, &log); + } + log.ref_name = NULL; + log.old_hash = NULL; + log.new_hash = NULL; + clear_log_record(&log); + } + return 0; +} + +static int reftable_create_symref(struct ref_store *ref_store, + const char *refname, const char *target, + const char *logmsg) +{ + struct reftable_ref_store *refs = + (struct reftable_ref_store *)ref_store; + struct write_create_symref_arg arg = { .refs = refs, + .refname = refname, + .target = target, + .logmsg = logmsg }; + if (refs->err < 0) { + return refs->err; + } + return stack_add(refs->stack, &write_create_symref_table, &arg); +} + +struct write_rename_arg { + struct stack *stack; + const char *oldname; + const char *newname; + const char *logmsg; +}; + +static int write_rename_table(struct writer *writer, void *argv) +{ + struct write_rename_arg *arg = (struct write_rename_arg *)argv; + uint64_t ts = stack_next_update_index(arg->stack); + struct ref_record ref = {}; + int err = stack_read_ref(arg->stack, arg->oldname, &ref); + + if (err) { + goto exit; + } + + /* XXX do ref renames overwrite the target? */ + if (stack_read_ref(arg->stack, arg->newname, &ref) == 0) { + goto exit; + } + + free(ref.ref_name); + ref.ref_name = strdup(arg->newname); + writer_set_limits(writer, ts, ts); + ref.update_index = ts; + + { + struct ref_record todo[2] = {}; + todo[0].ref_name = (char *)arg->oldname; + todo[0].update_index = ts; + /* leave todo[0] empty */ + todo[1] = ref; + todo[1].update_index = ts; + + err = writer_add_refs(writer, todo, 2); + if (err < 0) { + goto exit; + } + } + + if (ref.value != NULL) { + struct log_record todo[2] = {}; + fill_log_record(&todo[0]); + fill_log_record(&todo[1]); + + todo[0].ref_name = (char *)arg->oldname; + todo[0].update_index = ts; + todo[0].message = (char *)arg->logmsg; + todo[0].old_hash = ref.value; + todo[0].new_hash = NULL; + + todo[1].ref_name = (char *)arg->newname; + todo[1].update_index = ts; + todo[1].old_hash = NULL; + todo[1].new_hash = ref.value; + todo[1].message = (char *)arg->logmsg; + + err = writer_add_logs(writer, todo, 2); + + clear_log_record(&todo[0]); + clear_log_record(&todo[1]); + + if (err < 0) { + goto exit; + } + + } else { + /* XXX symrefs? */ + } + +exit: + ref_record_clear(&ref); + return err; +} + +static int reftable_rename_ref(struct ref_store *ref_store, + const char *oldrefname, const char *newrefname, + const char *logmsg) +{ + struct reftable_ref_store *refs = + (struct reftable_ref_store *)ref_store; + struct write_rename_arg arg = { + .stack = refs->stack, + .oldname = oldrefname, + .newname = newrefname, + .logmsg = logmsg, + }; + if (refs->err < 0) { + return refs->err; + } + + return stack_add(refs->stack, &write_rename_table, &arg); +} + +static int reftable_copy_ref(struct ref_store *ref_store, + const char *oldrefname, const char *newrefname, + const char *logmsg) +{ + BUG("reftable reference store does not support copying references"); +} + +struct reftable_reflog_ref_iterator { + struct ref_iterator base; + struct iterator iter; + struct log_record log; + struct object_id oid; + char *last_name; +}; + +static int +reftable_reflog_ref_iterator_advance(struct ref_iterator *ref_iterator) +{ + struct reftable_reflog_ref_iterator *ri = + (struct reftable_reflog_ref_iterator *)ref_iterator; + + while (1) { + int err = iterator_next_log(ri->iter, &ri->log); + if (err > 0) { + return ITER_DONE; + } + if (err < 0) { + return ITER_ERROR; + } + + ri->base.refname = ri->log.ref_name; + if (ri->last_name != NULL && + !strcmp(ri->log.ref_name, ri->last_name)) { + continue; + } + + free(ri->last_name); + ri->last_name = xstrdup(ri->log.ref_name); + hashcpy(ri->oid.hash, ri->log.new_hash); + return ITER_OK; + } +} + +static int reftable_reflog_ref_iterator_peel(struct ref_iterator *ref_iterator, + struct object_id *peeled) +{ + BUG("not supported."); + return -1; +} + +static int reftable_reflog_ref_iterator_abort(struct ref_iterator *ref_iterator) +{ + struct reftable_reflog_ref_iterator *ri = + (struct reftable_reflog_ref_iterator *)ref_iterator; + log_record_clear(&ri->log); + iterator_destroy(&ri->iter); + return 0; +} + +static struct ref_iterator_vtable reftable_reflog_ref_iterator_vtable = { + reftable_reflog_ref_iterator_advance, reftable_reflog_ref_iterator_peel, + reftable_reflog_ref_iterator_abort +}; + +static struct ref_iterator * +reftable_reflog_iterator_begin(struct ref_store *ref_store) +{ + struct reftable_reflog_ref_iterator *ri = xcalloc(sizeof(*ri), 1); + struct reftable_ref_store *refs = + (struct reftable_ref_store *)ref_store; + + struct merged_table *mt = stack_merged_table(refs->stack); + int err = merged_table_seek_log(mt, &ri->iter, ""); + if (err < 0) { + free(ri); + return NULL; + } + + base_ref_iterator_init(&ri->base, &reftable_reflog_ref_iterator_vtable, + 1); + ri->base.oid = &ri->oid; + + return (struct ref_iterator *)ri; +} + +static int +reftable_for_each_reflog_ent_newest_first(struct ref_store *ref_store, + const char *refname, + each_reflog_ent_fn fn, void *cb_data) +{ + struct iterator it = {}; + struct reftable_ref_store *refs = + (struct reftable_ref_store *)ref_store; + struct merged_table *mt = NULL; + int err = 0; + struct log_record log = {}; + + if (refs->err < 0) { + return refs->err; + } + + mt = stack_merged_table(refs->stack); + err = merged_table_seek_log(mt, &it, refname); + while (err == 0) { + err = iterator_next_log(it, &log); + if (err != 0) { + break; + } + + if (strcmp(log.ref_name, refname)) { + break; + } + + { + struct object_id old_oid = {}; + struct object_id new_oid = {}; + const char *full_committer = ""; + + hashcpy(old_oid.hash, log.old_hash); + hashcpy(new_oid.hash, log.new_hash); + + full_committer = fmt_ident(log.name, log.email, + WANT_COMMITTER_IDENT, + /*date*/ NULL, + IDENT_NO_DATE); + if (fn(&old_oid, &new_oid, full_committer, log.time, + log.tz_offset, log.message, cb_data)) { + err = -1; + break; + } + } + } + + log_record_clear(&log); + iterator_destroy(&it); + if (err > 0) { + err = 0; + } + return err; +} + +static int +reftable_for_each_reflog_ent_oldest_first(struct ref_store *ref_store, + const char *refname, + each_reflog_ent_fn fn, void *cb_data) +{ + struct iterator it = {}; + struct reftable_ref_store *refs = + (struct reftable_ref_store *)ref_store; + struct merged_table *mt = NULL; + struct log_record *logs = NULL; + int cap = 0; + int len = 0; + int err = 0; + + if (refs->err < 0) { + return refs->err; + } + mt = stack_merged_table(refs->stack); + err = merged_table_seek_log(mt, &it, refname); + + while (err == 0) { + struct log_record log = {}; + err = iterator_next_log(it, &log); + if (err != 0) { + break; + } + + if (strcmp(log.ref_name, refname)) { + break; + } + + if (len == cap) { + cap = 2 * cap + 1; + logs = realloc(logs, cap * sizeof(*logs)); + } + + logs[len++] = log; + } + + for (int i = len; i--;) { + struct log_record *log = &logs[i]; + struct object_id old_oid = {}; + struct object_id new_oid = {}; + const char *full_committer = ""; + + hashcpy(old_oid.hash, log->old_hash); + hashcpy(new_oid.hash, log->new_hash); + + full_committer = fmt_ident(log->name, log->email, + WANT_COMMITTER_IDENT, NULL, + IDENT_NO_DATE); + if (!fn(&old_oid, &new_oid, full_committer, log->time, + log->tz_offset, log->message, cb_data)) { + err = -1; + break; + } + } + + for (int i = 0; i < len; i++) { + log_record_clear(&logs[i]); + } + free(logs); + + iterator_destroy(&it); + if (err > 0) { + err = 0; + } + return err; +} + +static int reftable_reflog_exists(struct ref_store *ref_store, + const char *refname) +{ + /* always exists. */ + return 1; +} + +static int reftable_create_reflog(struct ref_store *ref_store, + const char *refname, int force_create, + struct strbuf *err) +{ + return 0; +} + +static int reftable_delete_reflog(struct ref_store *ref_store, + const char *refname) +{ + return 0; +} + +struct reflog_expiry_arg { + struct reftable_ref_store *refs; + struct log_record *tombstones; + int len; + int cap; +}; + +static void clear_log_tombstones(struct reflog_expiry_arg *arg) +{ + int i = 0; + for (; i < arg->len; i++) { + log_record_clear(&arg->tombstones[i]); + } + + FREE_AND_NULL(arg->tombstones); +} + +static void add_log_tombstone(struct reflog_expiry_arg *arg, + const char *refname, uint64_t ts) +{ + struct log_record tombstone = { + .ref_name = xstrdup(refname), + .update_index = ts, + }; + if (arg->len == arg->cap) { + arg->cap = 2 * arg->cap + 1; + arg->tombstones = + realloc(arg->tombstones, arg->cap * sizeof(tombstone)); + } + arg->tombstones[arg->len++] = tombstone; +} + +static int write_reflog_expiry_table(struct writer *writer, void *argv) +{ + struct reflog_expiry_arg *arg = (struct reflog_expiry_arg *)argv; + uint64_t ts = stack_next_update_index(arg->refs->stack); + int i = 0; + writer_set_limits(writer, ts, ts); + for (i = 0; i < arg->len; i++) { + int err = writer_add_log(writer, &arg->tombstones[i]); + if (err) { + return err; + } + } + return 0; +} + +static int reftable_reflog_expire(struct ref_store *ref_store, + const char *refname, + const struct object_id *oid, + unsigned int flags, + reflog_expiry_prepare_fn prepare_fn, + reflog_expiry_should_prune_fn should_prune_fn, + reflog_expiry_cleanup_fn cleanup_fn, + void *policy_cb_data) +{ + /* + For log expiry, we write tombstones in place of the expired entries, + This means that the entries are still retrievable by delving into the + stack, and expiring entries paradoxically takes extra memory. + + This memory is only reclaimed when some operation issues a + reftable_pack_refs(), which will compact the entire stack and get rid + of deletion entries. + + It would be better if the refs backend supported an API that sets a + criterion for all refs, passing the criterion to pack_refs(). + */ + struct reftable_ref_store *refs = + (struct reftable_ref_store *)ref_store; + struct merged_table *mt = NULL; + struct reflog_expiry_arg arg = { + .refs = refs, + }; + struct log_record log = {}; + struct iterator it = {}; + int err = 0; + if (refs->err < 0) { + return refs->err; + } + + mt = stack_merged_table(refs->stack); + err = merged_table_seek_log(mt, &it, refname); + if (err < 0) { + return err; + } + + while (1) { + struct object_id ooid = {}; + struct object_id noid = {}; + + int err = iterator_next_log(it, &log); + if (err < 0) { + return err; + } + + if (err > 0 || strcmp(log.ref_name, refname)) { + break; + } + hashcpy(ooid.hash, log.old_hash); + hashcpy(noid.hash, log.new_hash); + + if (should_prune_fn(&ooid, &noid, log.email, + (timestamp_t)log.time, log.tz_offset, + log.message, policy_cb_data)) { + add_log_tombstone(&arg, refname, log.update_index); + } + } + log_record_clear(&log); + iterator_destroy(&it); + err = stack_add(refs->stack, &write_reflog_expiry_table, &arg); + clear_log_tombstones(&arg); + return err; +} + +static int reftable_read_raw_ref(struct ref_store *ref_store, + const char *refname, struct object_id *oid, + struct strbuf *referent, unsigned int *type) +{ + struct reftable_ref_store *refs = + (struct reftable_ref_store *)ref_store; + struct ref_record ref = {}; + int err = 0; + if (refs->err < 0) { + return refs->err; + } + + err = stack_read_ref(refs->stack, refname, &ref); + if (err) { + goto exit; + } + if (ref.target != NULL) { + /* XXX recurse? */ + strbuf_reset(referent); + strbuf_addstr(referent, ref.target); + *type |= REF_ISSYMREF; + } else { + hashcpy(oid->hash, ref.value); + } +exit: + ref_record_clear(&ref); + return err; +} + +struct ref_storage_be refs_be_reftable = { + &refs_be_files, + "reftable", + reftable_ref_store_create, + reftable_init_db, + reftable_transaction_prepare, + reftable_transaction_finish, + reftable_transaction_abort, + reftable_transaction_commit, + + reftable_pack_refs, + reftable_create_symref, + reftable_delete_refs, + reftable_rename_ref, + reftable_copy_ref, + + reftable_ref_iterator_begin, + reftable_read_raw_ref, + + reftable_reflog_iterator_begin, + reftable_for_each_reflog_ent_newest_first, + reftable_for_each_reflog_ent_oldest_first, + reftable_reflog_exists, + reftable_create_reflog, + reftable_delete_reflog, + reftable_reflog_expire +}; diff --git a/repository.c b/repository.c index a4174ddb062..ff0988dac84 100644 --- a/repository.c +++ b/repository.c @@ -174,6 +174,8 @@ int repo_init(struct repository *repo, if (worktree) repo_set_worktree(repo, worktree); + repo->ref_storage_format = xstrdup_or_null(format.ref_storage); + clear_repository_format(&format); return 0; diff --git a/repository.h b/repository.h index 040057dea6f..198d4aa0907 100644 --- a/repository.h +++ b/repository.h @@ -70,6 +70,9 @@ struct repository { /* The store in which the refs are held. */ struct ref_store *refs; + /* The format to use for the ref database. */ + char *ref_storage_format; + /* * Contains path to often used file names. */ diff --git a/setup.c b/setup.c index 4ea7a0b081b..81dcc23fc90 100644 --- a/setup.c +++ b/setup.c @@ -458,9 +458,11 @@ static int check_repo_format(const char *var, const char *value, void *vdata) if (!value) return config_error_nonbool(var); data->partial_clone = xstrdup(value); - } else if (!strcmp(ext, "worktreeconfig")) + } else if (!strcmp(ext, "worktreeconfig")) { data->worktree_config = git_config_bool(var, value); - else + } else if (!strcmp(ext, "refstorage")) { + data->ref_storage = xstrdup(value); + } else string_list_append(&data->unknown_extensions, ext); } @@ -549,6 +551,7 @@ void clear_repository_format(struct repository_format *format) string_list_clear(&format->unknown_extensions, 0); free(format->work_tree); free(format->partial_clone); + free(format->ref_storage); init_repository_format(format); } @@ -1191,8 +1194,11 @@ const char *setup_git_directory_gently(int *nongit_ok) gitdir = DEFAULT_GIT_DIR_ENVIRONMENT; setup_git_env(gitdir); } - if (startup_info->have_repository) + if (startup_info->have_repository) { repo_set_hash_algo(the_repository, repo_fmt.hash_algo); + the_repository->ref_storage_format = + xstrdup_or_null(repo_fmt.ref_storage); + } } strbuf_release(&dir); diff --git a/t/t0031-reftable.sh b/t/t0031-reftable.sh new file mode 100755 index 00000000000..d35211c9db2 --- /dev/null +++ b/t/t0031-reftable.sh @@ -0,0 +1,31 @@ +#!/bin/sh +# +# Copyright (c) 2020 Google LLC +# + +test_description='reftable basics' + +. ./test-lib.sh + +test_expect_success 'basic operation of reftable storage' ' + git init --ref-storage=reftable repo && + cd repo && + echo "hello" > world.txt && + git add world.txt && + git commit -m "first post" && + printf "HEAD\nrefs/heads/master\n" > want && + git show-ref | cut -f2 -d" " > got && + test_cmp got want && + for count in $(test_seq 1 10); do + echo "hello" >> world.txt + git commit -m "number ${count}" world.txt + done && + git gc && + nfiles=$(ls -1 .git/reftable | wc -l | tr -d "[ \t]" ) && + test "${nfiles}" = "2" && + git reflog refs/heads/master > output && + grep "commit (initial): first post" output && + grep "commit: number 10" output +' + +test_done