From patchwork Wed Oct 10 15:59:33 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ben Peart X-Patchwork-Id: 10634789 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 112ED46E4 for ; Wed, 10 Oct 2018 15:59:56 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id CDD702A2B8 for ; Wed, 10 Oct 2018 15:59:55 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id C1B942A84E; Wed, 10 Oct 2018 15:59:55 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 60B832A3E2 for ; Wed, 10 Oct 2018 15:59:55 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726883AbeJJXWl (ORCPT ); Wed, 10 Oct 2018 19:22:41 -0400 Received: from mail-qt1-f194.google.com ([209.85.160.194]:40978 "EHLO mail-qt1-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726479AbeJJXWk (ORCPT ); Wed, 10 Oct 2018 19:22:40 -0400 Received: by mail-qt1-f194.google.com with SMTP id l41-v6so6226727qtl.8 for ; Wed, 10 Oct 2018 08:59:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=iyTVoSLlgxNzmh7nGrmmjLlBb1pCULUhhmNBx6PivJI=; b=NphCddzQe/+W7Ww5BSDhCzxSE0D8ZQuvxKgRS2ZYaZJafPHOsp/3UdDAmg6SBCmqrP +oznTxk/tTVk94P87s+2wfyHi2C+QtlAq/47l8ORTowMPIIvcepJ7dW5aGyIaeWIbEHW xORsz3L1Bjyqts9cib1Lp1cp4YhUeUXo0vT/L9wKS08JlC1Gmd1eUBGGqUes9x+pjgT4 e08hMEtdgem84D65UYmthkUXL+tDsFB2xCYrxiwCTyTVT3ro6l2yeQXRpNQgCo4eyLy0 0/KE+cAQFllzxSeisokLXse9pCKcdVMDORLPlcQcr2wFaorObA6cO8XkuCP5MG96MGMN 47Kw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=iyTVoSLlgxNzmh7nGrmmjLlBb1pCULUhhmNBx6PivJI=; b=DBp5J6SPxiYsmpin7wfQ95FH387j289XbeRkVz26tDT9qh5+FPj1WvenjnzC/ggzOH glzfDJqvh2FBgzbxDl60BkajyEG4u6KspPYJTwr2LbVeztoD8V1TUFGtqsbjmy/Fd+3N +rCNxFtx+Bune+XPpiZX9y882ggxurRaf+c9oM/XR2yClrIDlwUAu1Lqf+5pQ0y4wAeY y8v0cdrKUZevD2uX9rfOyktrZW4x6cfFwpRmotOQYYIhzEWYZCmLuF6/q8lMg5zczfaK 63R99EiNGN8AckD3Lg6zRMTDfPYNOQWNgvbM8Wx2FvfwK5npa4FtgH+VRwxgoS1c08bd bJeA== X-Gm-Message-State: ABuFfoiDFrpiFTY9pzldG4sko1qDQWCzdE2nFiVXQi5NVSSBavszTNpG 6oIA/CLtg1fg6TRpAQeC9JKr///SY1o= X-Google-Smtp-Source: ACcGV62Xy2OgMBBbJ1fuMX3Zr5wEfJDopDpNQuTUJauAK1rL2WvplKfHLOUaaJxWckkZVOps1AQQ5A== X-Received: by 2002:ac8:2729:: with SMTP id g38-v6mr27372063qtg.168.1539187191893; Wed, 10 Oct 2018 08:59:51 -0700 (PDT) Received: from localhost.localdomain (70-33-148-227.unassigned.ntelos.net. [70.33.148.227]) by smtp.gmail.com with ESMTPSA id d89-v6sm13704920qkj.29.2018.10.10.08.59.50 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 10 Oct 2018 08:59:51 -0700 (PDT) From: Ben Peart To: git@vger.kernel.org Cc: gitster@pobox.com, pclouds@gmail.com, Ben Peart Subject: [PATCH v8 2/7] read-cache: clean up casting and byte decoding Date: Wed, 10 Oct 2018 11:59:33 -0400 Message-Id: <20181010155938.20996-3-peartben@gmail.com> X-Mailer: git-send-email 2.18.0.windows.1 In-Reply-To: <20181010155938.20996-1-peartben@gmail.com> References: <20180823154053.20212-1-benpeart@microsoft.com> <20181010155938.20996-1-peartben@gmail.com> Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Ben Peart This patch does a clean up pass to minimize the casting required to work with the memory mapped index (mmap). It also makes the decoding of network byte order more consistent by using get_be32() where possible. Signed-off-by: Ben Peart --- read-cache.c | 23 +++++++++++------------ 1 file changed, 11 insertions(+), 12 deletions(-) diff --git a/read-cache.c b/read-cache.c index 583a4fb1f8..6ba99e2c96 100644 --- a/read-cache.c +++ b/read-cache.c @@ -1650,7 +1650,7 @@ int verify_index_checksum; /* Allow fsck to force verification of the cache entry order. */ int verify_ce_order; -static int verify_hdr(struct cache_header *hdr, unsigned long size) +static int verify_hdr(const struct cache_header *hdr, unsigned long size) { git_hash_ctx c; unsigned char hash[GIT_MAX_RAWSZ]; @@ -1674,7 +1674,7 @@ static int verify_hdr(struct cache_header *hdr, unsigned long size) } static int read_index_extension(struct index_state *istate, - const char *ext, void *data, unsigned long sz) + const char *ext, const char *data, unsigned long sz) { switch (CACHE_EXT(ext)) { case CACHE_EXT_TREE: @@ -1889,8 +1889,8 @@ int do_read_index(struct index_state *istate, const char *path, int must_exist) int fd, i; struct stat st; unsigned long src_offset; - struct cache_header *hdr; - void *mmap; + const struct cache_header *hdr; + const char *mmap; size_t mmap_size; const struct cache_entry *previous_ce = NULL; @@ -1918,7 +1918,7 @@ int do_read_index(struct index_state *istate, const char *path, int must_exist) die_errno("unable to map index file"); close(fd); - hdr = mmap; + hdr = (const struct cache_header *)mmap; if (verify_hdr(hdr, mmap_size) < 0) goto unmap; @@ -1943,7 +1943,7 @@ int do_read_index(struct index_state *istate, const char *path, int must_exist) struct cache_entry *ce; unsigned long consumed; - disk_ce = (struct ondisk_cache_entry *)((char *)mmap + src_offset); + disk_ce = (struct ondisk_cache_entry *)(mmap + src_offset); ce = create_from_disk(istate, disk_ce, &consumed, previous_ce); set_index_entry(istate, i, ce); @@ -1961,21 +1961,20 @@ int do_read_index(struct index_state *istate, const char *path, int must_exist) * in 4-byte network byte order. */ uint32_t extsize; - memcpy(&extsize, (char *)mmap + src_offset + 4, 4); - extsize = ntohl(extsize); + extsize = get_be32(mmap + src_offset + 4); if (read_index_extension(istate, - (const char *) mmap + src_offset, - (char *) mmap + src_offset + 8, + mmap + src_offset, + mmap + src_offset + 8, extsize) < 0) goto unmap; src_offset += 8; src_offset += extsize; } - munmap(mmap, mmap_size); + munmap((void *)mmap, mmap_size); return istate->cache_nr; unmap: - munmap(mmap, mmap_size); + munmap((void *)mmap, mmap_size); die("index file corrupt"); } From patchwork Wed Oct 10 15:59:35 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ben Peart X-Patchwork-Id: 10634793 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 888DF69B5 for ; Wed, 10 Oct 2018 15:59:58 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 5BC9C2A2B8 for ; Wed, 10 Oct 2018 15:59:58 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 4FC372A49B; Wed, 10 Oct 2018 15:59:58 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id D87B72A81F for ; Wed, 10 Oct 2018 15:59:57 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726791AbeJJXWn (ORCPT ); Wed, 10 Oct 2018 19:22:43 -0400 Received: from mail-qt1-f193.google.com ([209.85.160.193]:35758 "EHLO mail-qt1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726886AbeJJXWn (ORCPT ); Wed, 10 Oct 2018 19:22:43 -0400 Received: by mail-qt1-f193.google.com with SMTP id v19-v6so6251649qtg.2 for ; Wed, 10 Oct 2018 08:59:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=aBPf2za6nKHCvpeqqCz4bJrAxFunCwTylZ9S/Zn8TFE=; b=L7ZqnYdXyqpI9PNL3hLldtGacxhVRhTr0CvQo3E5qjcDvkVWnVdhaCv0PrQd2NQxXJ rhGakVnhvauMrupjc/g+Srsa3efMvjQgzT2btgJ5ADDbrOUqnVg3FeFFqatlBX6uy2tk EV85ZCgvH26B+j4Z71EgzWLUXU7leZFD5i/8wzZ0JD6szaLBFfYlEu29McS5AAigQm4i Qfha89PCPgB0Jq+z/nFvPZYZ1pxgsRs5EKR/67Cyx3+R4V3jz+Sl7vn24C2T81t7a9h/ 5J72QiiskyuIq4QX1jQ8UZm2jloCeM+9uCQLMs588niLy6U5wCIZM3qlRJHk86oV56xa wyEg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=aBPf2za6nKHCvpeqqCz4bJrAxFunCwTylZ9S/Zn8TFE=; b=cHT81nt6hVeYw75mAgJL2Ic1uLKowrtixDTDRm+AHbRbypwpCrFggyuWwXNdWWyCsl AMdM0dNhRUPslTeA3Eds9HZs+UTy9bqkDKf6b8AbWoOpe/mcMwnXaFrkG/acQZSq5xX9 LvQIIYHq3u9Nu45z1BzmJEzNCUYxzV3z0y/sGr4B/gfAdhCgsaxW9QGvNfWrl3ZOHu3y QpCpKykwEbIdQzr2ACsLJzfRFo7Qveen/ONA19kTITO/keQdlRWujh3aCVLtnKx66Cb7 kB8HiUHmrRkMK2zHJQY65X5XzYIqKksIauZzbR3vAoS9erd1YPyEN52hyDQJoW9sjtNy UnWQ== X-Gm-Message-State: ABuFfogVqu/42hVWj9hoadgyKk4TP8zdT6xddaqK/6XVAIQsEAJ3+S7t o/yxUe3ZlDihkeEaHAUA8dr0VGdBrVo= X-Google-Smtp-Source: ACcGV62NLKL86uGPtdqrM5KmTryhQDhBHQNjCwuRLb2K0m1diWNjq8WIz89HGFezqESHnSbWIbMYww== X-Received: by 2002:a0c:ec4f:: with SMTP id n15mr13858227qvq.91.1539187194513; Wed, 10 Oct 2018 08:59:54 -0700 (PDT) Received: from localhost.localdomain (70-33-148-227.unassigned.ntelos.net. [70.33.148.227]) by smtp.gmail.com with ESMTPSA id d89-v6sm13704920qkj.29.2018.10.10.08.59.53 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 10 Oct 2018 08:59:53 -0700 (PDT) From: Ben Peart To: git@vger.kernel.org Cc: gitster@pobox.com, pclouds@gmail.com, Ben Peart Subject: [PATCH v8 4/7] config: add new index.threads config setting Date: Wed, 10 Oct 2018 11:59:35 -0400 Message-Id: <20181010155938.20996-5-peartben@gmail.com> X-Mailer: git-send-email 2.18.0.windows.1 In-Reply-To: <20181010155938.20996-1-peartben@gmail.com> References: <20180823154053.20212-1-benpeart@microsoft.com> <20181010155938.20996-1-peartben@gmail.com> Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Ben Peart Add support for a new index.threads config setting which will be used to control the threading code in do_read_index(). A value of 0 will tell the index code to automatically determine the correct number of threads to use. A value of 1 will make the code single threaded. A value greater than 1 will set the maximum number of threads to use. For testing purposes, this setting can be overwritten by setting the GIT_TEST_INDEX_THREADS= environment variable to a value greater than 0. Signed-off-by: Ben Peart --- Documentation/config.txt | 7 +++++++ config.c | 18 ++++++++++++++++++ config.h | 1 + t/README | 5 +++++ t/t1700-split-index.sh | 5 +++++ 5 files changed, 36 insertions(+) diff --git a/Documentation/config.txt b/Documentation/config.txt index ad0f4510c3..8fd973b76b 100644 --- a/Documentation/config.txt +++ b/Documentation/config.txt @@ -2413,6 +2413,13 @@ imap:: The configuration variables in the 'imap' section are described in linkgit:git-imap-send[1]. +index.threads:: + Specifies the number of threads to spawn when loading the index. + This is meant to reduce index load time on multiprocessor machines. + Specifying 0 or 'true' will cause Git to auto-detect the number of + CPU's and set the number of threads accordingly. Specifying 1 or + 'false' will disable multithreading. Defaults to 'true'. + index.version:: Specify the version with which new index files should be initialized. This does not affect existing repositories. diff --git a/config.c b/config.c index 3461993f0a..2ee29f6f86 100644 --- a/config.c +++ b/config.c @@ -2289,6 +2289,24 @@ int git_config_get_fsmonitor(void) return 0; } +int git_config_get_index_threads(void) +{ + int is_bool, val = 0; + + val = git_env_ulong("GIT_TEST_INDEX_THREADS", 0); + if (val) + return val; + + if (!git_config_get_bool_or_int("index.threads", &is_bool, &val)) { + if (is_bool) + return val ? 0 : 1; + else + return val; + } + + return 0; /* auto */ +} + NORETURN void git_die_config_linenr(const char *key, const char *filename, int linenr) { diff --git a/config.h b/config.h index ab46e0165d..a06027e69b 100644 --- a/config.h +++ b/config.h @@ -250,6 +250,7 @@ extern int git_config_get_untracked_cache(void); extern int git_config_get_split_index(void); extern int git_config_get_max_percent_split_change(void); extern int git_config_get_fsmonitor(void); +extern int git_config_get_index_threads(void); /* This dies if the configured or default date is in the future */ extern int git_config_get_expiry(const char *key, const char **output); diff --git a/t/README b/t/README index 3ea6c85460..8f5c0620ea 100644 --- a/t/README +++ b/t/README @@ -327,6 +327,11 @@ GIT_TEST_COMMIT_GRAPH=, when true, forces the commit-graph to be written after every 'git commit' command, and overrides the 'core.commitGraph' setting to true. +GIT_TEST_INDEX_THREADS= enables exercising the multi-threaded loading +of the index for the whole test suite by bypassing the default number of +cache entries and thread minimums. Setting this to 1 will make the +index loading single threaded. + Naming Tests ------------ diff --git a/t/t1700-split-index.sh b/t/t1700-split-index.sh index 8e17f8e7a0..ef9349bd70 100755 --- a/t/t1700-split-index.sh +++ b/t/t1700-split-index.sh @@ -6,7 +6,12 @@ test_description='split index mode tests' # We need total control of index splitting here sane_unset GIT_TEST_SPLIT_INDEX + +# Testing a hard coded SHA against an index with an extension +# that can vary from run to run is problematic so we disable +# those extensions. sane_unset GIT_FSMONITOR_TEST +sane_unset GIT_TEST_INDEX_THREADS test_expect_success 'enable split index' ' git config splitIndex.maxPercentChange 100 && From patchwork Wed Oct 10 15:59:36 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ben Peart X-Patchwork-Id: 10634795 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 0F20269B7 for ; Wed, 10 Oct 2018 16:00:00 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id D9F172A2B8 for ; Wed, 10 Oct 2018 15:59:59 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id CE27F2A84D; Wed, 10 Oct 2018 15:59:59 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 4C1672A2B8 for ; Wed, 10 Oct 2018 15:59:59 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726908AbeJJXWp (ORCPT ); Wed, 10 Oct 2018 19:22:45 -0400 Received: from mail-qk1-f193.google.com ([209.85.222.193]:40187 "EHLO mail-qk1-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726886AbeJJXWo (ORCPT ); Wed, 10 Oct 2018 19:22:44 -0400 Received: by mail-qk1-f193.google.com with SMTP id a13-v6so3469653qkc.7 for ; Wed, 10 Oct 2018 08:59:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=NguxvchCWRx+eTHiOIE9c1tuF7L8Nutv/DNloC40yRQ=; b=Z0c4UfZGabn2YX91VZojbpC3qA/VvD5R+YHuZXbLOqW4Z5etDRJKyomGGY9Czl+/MJ YApdA2qV/erIiSN5xA1k+SuPyzGdm1BzOxD7be30W2wkclV3PoGnMQhTsJjcQNQ8M0Ue +g6AYi9z+7XNi9YeQj5hQwIkwW7IzrlZMLROLddeuy0gwhNl+fo85U+gQFFZzwjVdUGI WeX+2Wv1+JKQKfVRmb8FZTz0Lo5dcWR2xg5b8qFhZgbVjy54YfwGVP7CIwRgAGUvpfKF VkyYsOot4KlCX2adxJthDltVKicmP2QXXeFNiK00Xr8trcEnJ0yZz4AAQyBUzE5yo9K8 a+pg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=NguxvchCWRx+eTHiOIE9c1tuF7L8Nutv/DNloC40yRQ=; b=WpX3+zoMVUQZ7j3PCyrS5mJ14xfvnTFSxemrzYyhk6BhRw9XLe0BY3+XUQALGbS9hR F0yju6KrDQhgqk3UW4uLsHHdqamTjmhmpgkHzPo8M/ShxApHdIlLwenwGjf3f2ouB2Lq faRLzEeyQgzGY5Da8ToJ4i2OqzQtA0u4L7hDDc9J823PLdSFvzrp3f3JmHmJPhfi+wmK NowHw7Z48f8MTwpesb5EynuK9sLEw5iPDNaK/nPpm6PmuM81L6l9MohwrpPC/bXoKO6q 0tTSInq/GLwLJKyOv+PXUvxTSpGq4dEinp3N+IlUnu6/6yJt/6sNEzJv9/iarG5Tec6J 7TBg== X-Gm-Message-State: ABuFfoiZYfHAtikj/77bBGl3DmGiVtrEp4n193OidnPuTOWC0/a4ao96 qglxA7Z0brhNcCIwmZBl5eXUYSfTfQI= X-Google-Smtp-Source: ACcGV609IDYJvy5FM2+FS1apyaE0wzIb1vTRw8fFYSOXMtu3wTFnjU9TSr7UPi5jPibPGpVfzee+pw== X-Received: by 2002:a37:37d5:: with SMTP id e204-v6mr26262321qka.1.1539187195810; Wed, 10 Oct 2018 08:59:55 -0700 (PDT) Received: from localhost.localdomain (70-33-148-227.unassigned.ntelos.net. [70.33.148.227]) by smtp.gmail.com with ESMTPSA id d89-v6sm13704920qkj.29.2018.10.10.08.59.54 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 10 Oct 2018 08:59:54 -0700 (PDT) From: Ben Peart To: git@vger.kernel.org Cc: gitster@pobox.com, pclouds@gmail.com, Ben Peart Subject: [PATCH v8 5/7] read-cache: load cache extensions on a worker thread Date: Wed, 10 Oct 2018 11:59:36 -0400 Message-Id: <20181010155938.20996-6-peartben@gmail.com> X-Mailer: git-send-email 2.18.0.windows.1 In-Reply-To: <20181010155938.20996-1-peartben@gmail.com> References: <20180823154053.20212-1-benpeart@microsoft.com> <20181010155938.20996-1-peartben@gmail.com> Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Ben Peart This patch helps address the CPU cost of loading the index by loading the cache extensions on a worker thread in parallel with loading the cache entries. In some cases, loading the extensions takes longer than loading the cache entries so this patch utilizes the new EOIE to start the thread to load the extensions before loading all the cache entries in parallel. This is possible because the current extensions don't access the cache entries in the index_state structure so are OK that they don't all exist yet. The CACHE_EXT_TREE, CACHE_EXT_RESOLVE_UNDO, and CACHE_EXT_UNTRACKED extensions don't even get a pointer to the index so don't have access to the cache entries. CACHE_EXT_LINK only uses the index_state to initialize the split index. CACHE_EXT_FSMONITOR only uses the index_state to save the fsmonitor last update and dirty flags. I used p0002-read-cache.sh to generate some performance data: Test w/100,000 files reduced the time by 0.53% Test w/1,000,000 files reduced the time by 27.78% Signed-off-by: Ben Peart --- read-cache.c | 95 +++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 79 insertions(+), 16 deletions(-) diff --git a/read-cache.c b/read-cache.c index 4781515252..2214b3153d 100644 --- a/read-cache.c +++ b/read-cache.c @@ -23,6 +23,7 @@ #include "split-index.h" #include "utf8.h" #include "fsmonitor.h" +#include "thread-utils.h" /* Mask for the name length in ce_flags in the on-disk index */ @@ -1890,6 +1891,44 @@ static size_t estimate_cache_size(size_t ondisk_size, unsigned int entries) static size_t read_eoie_extension(const char *mmap, size_t mmap_size); static void write_eoie_extension(struct strbuf *sb, git_hash_ctx *eoie_context, size_t offset); +struct load_index_extensions +{ +#ifndef NO_PTHREADS + pthread_t pthread; +#endif + struct index_state *istate; + const char *mmap; + size_t mmap_size; + unsigned long src_offset; +}; + +static void *load_index_extensions(void *_data) +{ + struct load_index_extensions *p = _data; + unsigned long src_offset = p->src_offset; + + while (src_offset <= p->mmap_size - the_hash_algo->rawsz - 8) { + /* After an array of active_nr index entries, + * there can be arbitrary number of extended + * sections, each of which is prefixed with + * extension name (4-byte) and section length + * in 4-byte network byte order. + */ + uint32_t extsize = get_be32(p->mmap + src_offset + 4); + if (read_index_extension(p->istate, + p->mmap + src_offset, + p->mmap + src_offset + 8, + extsize) < 0) { + munmap((void *)p->mmap, p->mmap_size); + die(_("index file corrupt")); + } + src_offset += 8; + src_offset += extsize; + } + + return NULL; +} + /* remember to discard_cache() before reading a different cache! */ int do_read_index(struct index_state *istate, const char *path, int must_exist) { @@ -1900,6 +1939,11 @@ int do_read_index(struct index_state *istate, const char *path, int must_exist) const char *mmap; size_t mmap_size; const struct cache_entry *previous_ce = NULL; + struct load_index_extensions p; + size_t extension_offset = 0; +#ifndef NO_PTHREADS + int nr_threads; +#endif if (istate->initialized) return istate->cache_nr; @@ -1936,6 +1980,30 @@ int do_read_index(struct index_state *istate, const char *path, int must_exist) istate->cache = xcalloc(istate->cache_alloc, sizeof(*istate->cache)); istate->initialized = 1; + p.istate = istate; + p.mmap = mmap; + p.mmap_size = mmap_size; + +#ifndef NO_PTHREADS + nr_threads = git_config_get_index_threads(); + if (!nr_threads) + nr_threads = online_cpus(); + + if (nr_threads > 1) { + extension_offset = read_eoie_extension(mmap, mmap_size); + if (extension_offset) { + int err; + + p.src_offset = extension_offset; + err = pthread_create(&p.pthread, NULL, load_index_extensions, &p); + if (err) + die(_("unable to create load_index_extensions thread: %s"), strerror(err)); + + nr_threads--; + } + } +#endif + if (istate->version == 4) { mem_pool_init(&istate->ce_mem_pool, estimate_cache_size_from_compressed(istate->cache_nr)); @@ -1960,22 +2028,17 @@ int do_read_index(struct index_state *istate, const char *path, int must_exist) istate->timestamp.sec = st.st_mtime; istate->timestamp.nsec = ST_MTIME_NSEC(st); - while (src_offset <= mmap_size - the_hash_algo->rawsz - 8) { - /* After an array of active_nr index entries, - * there can be arbitrary number of extended - * sections, each of which is prefixed with - * extension name (4-byte) and section length - * in 4-byte network byte order. - */ - uint32_t extsize; - extsize = get_be32(mmap + src_offset + 4); - if (read_index_extension(istate, - mmap + src_offset, - mmap + src_offset + 8, - extsize) < 0) - goto unmap; - src_offset += 8; - src_offset += extsize; + /* if we created a thread, join it otherwise load the extensions on the primary thread */ +#ifndef NO_PTHREADS + if (extension_offset) { + int ret = pthread_join(p.pthread, NULL); + if (ret) + die(_("unable to join load_index_extensions thread: %s"), strerror(ret)); + } +#endif + if (!extension_offset) { + p.src_offset = src_offset; + load_index_extensions(&p); } munmap((void *)mmap, mmap_size); return istate->cache_nr; From patchwork Wed Oct 10 15:59:37 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ben Peart X-Patchwork-Id: 10634797 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 9938A15E2 for ; Wed, 10 Oct 2018 16:00:01 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 664742A2B8 for ; Wed, 10 Oct 2018 16:00:01 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 5A7362A84D; Wed, 10 Oct 2018 16:00:01 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 8B9042A2B8 for ; Wed, 10 Oct 2018 16:00:00 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726911AbeJJXWq (ORCPT ); Wed, 10 Oct 2018 19:22:46 -0400 Received: from mail-qt1-f196.google.com ([209.85.160.196]:39637 "EHLO mail-qt1-f196.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726902AbeJJXWq (ORCPT ); Wed, 10 Oct 2018 19:22:46 -0400 Received: by mail-qt1-f196.google.com with SMTP id e22-v6so6240114qto.6 for ; Wed, 10 Oct 2018 08:59:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=hpRbBlSipRLeuxAufuwxwXJeHkphMMDwISNEiKI86JI=; b=lqQ7yQt8RZMh6Fqn2ci3rNNodZAES3uJXY+0z/G5dWLEbw7eVRlIas0JAhP4znJWVl S9pKnDxfOaNYFHSIpbb209UPKrSVc3cRoITJrsQ8gPd7l0odA+3cE1kX3jynB9bPKTLy bcbBAk3Og4N+wf8S+5NyCO3ByHsNGGbyQ/Fwki2RSl20DC/n2zkOLXu2Q6fdxB+Cf4uO 8WMpKtN7Cnsbm8rOx+NemsgiSLO0p+plKb55yVaYxf5T9xQ/0hUCGkv8TKSUSHEF9WNA l+8z0Rb6waFKwMyjfFXoC4VK8hQ27VleVNTdHH8OiR/9DggV/YlPiO7v7hN0iVwbZJA5 yw5A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=hpRbBlSipRLeuxAufuwxwXJeHkphMMDwISNEiKI86JI=; b=ApuhOvoYXzgsMRVTlrrSSBJWXRsYhnuSqBSclVygtYZ8aa9T8vVGRF1VuU56N/oNpK oBYdsG4pDj6uMILhvW0GkVAgTCOKHcXOLR8b7b4xR45sE1DabJRR5iJAggj2o3tTUafO Q+sLUMtTO8pONuLcT2xOAgL+cTk2cemd1SsSlCauiNUQfZAu00ez7Ve7bh94I63t1Ltz ZYo6S9B/EJKuoreeW0VJXnpclIQ810l6HwRS0lVyWN4Ep9sS/NeINQ7wje7K4fjkRI+J yHfBLw+BgjKfkQRIF7++amxD1assNjqbb4Q6XVlPdiRExpTAPvcwdwDAsoDEAjJTNwVi XvCQ== X-Gm-Message-State: ABuFfoiolqFaw/35mHVz4RbfSdIm63AnNSmrJ/JVEwqyEbVI2yaW1aX3 u5ENo8EiroWDOs9qhJb06Abm1+Vd0n4= X-Google-Smtp-Source: ACcGV63SD8eR20DoDT0VECSuum0Bmjf+EANmKy6HgX9ET0ASrXWRradGXadTSpf9q+EhlgEzxgh8Iw== X-Received: by 2002:ac8:7397:: with SMTP id t23-v6mr27505797qtp.4.1539187197085; Wed, 10 Oct 2018 08:59:57 -0700 (PDT) Received: from localhost.localdomain (70-33-148-227.unassigned.ntelos.net. [70.33.148.227]) by smtp.gmail.com with ESMTPSA id d89-v6sm13704920qkj.29.2018.10.10.08.59.55 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 10 Oct 2018 08:59:56 -0700 (PDT) From: Ben Peart To: git@vger.kernel.org Cc: gitster@pobox.com, pclouds@gmail.com, Ben Peart Subject: [PATCH v8 6/7] ieot: add Index Entry Offset Table (IEOT) extension Date: Wed, 10 Oct 2018 11:59:37 -0400 Message-Id: <20181010155938.20996-7-peartben@gmail.com> X-Mailer: git-send-email 2.18.0.windows.1 In-Reply-To: <20181010155938.20996-1-peartben@gmail.com> References: <20180823154053.20212-1-benpeart@microsoft.com> <20181010155938.20996-1-peartben@gmail.com> Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Ben Peart This patch enables addressing the CPU cost of loading the index by adding additional data to the index that will allow us to efficiently multi- thread the loading and conversion of cache entries. It accomplishes this by adding an (optional) index extension that is a table of offsets to blocks of cache entries in the index file. To make this work for V4 indexes, when writing the cache entries, it periodically "resets" the prefix-compression by encoding the current entry as if the path name for the previous entry is completely different and saves the offset of that entry in the IEOT. Basically, with V4 indexes, it generates offsets into blocks of prefix-compressed entries. Signed-off-by: Ben Peart --- Documentation/technical/index-format.txt | 18 +++ read-cache.c | 196 ++++++++++++++++++++++- 2 files changed, 211 insertions(+), 3 deletions(-) diff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt index 6bc2d90f7f..7c4d67aa6a 100644 --- a/Documentation/technical/index-format.txt +++ b/Documentation/technical/index-format.txt @@ -337,3 +337,21 @@ The remaining data of each directory block is grouped by type: SHA-1("TREE" + + "REUC" + ) + +== Index Entry Offset Table + + The Index Entry Offset Table (IEOT) is used to help address the CPU + cost of loading the index by enabling multi-threading the process of + converting cache entries from the on-disk format to the in-memory format. + The signature for this extension is { 'I', 'E', 'O', 'T' }. + + The extension consists of: + + - 32-bit version (currently 1) + + - A number of index offset entries each consisting of: + + - 32-bit offset from the begining of the file to the first cache entry + in this block of entries. + + - 32-bit count of cache entries in this block diff --git a/read-cache.c b/read-cache.c index 2214b3153d..3ace29d58f 100644 --- a/read-cache.c +++ b/read-cache.c @@ -45,6 +45,7 @@ #define CACHE_EXT_UNTRACKED 0x554E5452 /* "UNTR" */ #define CACHE_EXT_FSMONITOR 0x46534D4E /* "FSMN" */ #define CACHE_EXT_ENDOFINDEXENTRIES 0x454F4945 /* "EOIE" */ +#define CACHE_EXT_INDEXENTRYOFFSETTABLE 0x49454F54 /* "IEOT" */ /* changes that can be kept in $GIT_DIR/index (basically all extensions) */ #define EXTMASK (RESOLVE_UNDO_CHANGED | CACHE_TREE_CHANGED | \ @@ -1696,6 +1697,7 @@ static int read_index_extension(struct index_state *istate, read_fsmonitor_extension(istate, data, sz); break; case CACHE_EXT_ENDOFINDEXENTRIES: + case CACHE_EXT_INDEXENTRYOFFSETTABLE: /* already handled in do_read_index() */ break; default: @@ -1888,6 +1890,23 @@ static size_t estimate_cache_size(size_t ondisk_size, unsigned int entries) return ondisk_size + entries * per_entry; } +struct index_entry_offset +{ + /* starting byte offset into index file, count of index entries in this block */ + int offset, nr; +}; + +struct index_entry_offset_table +{ + int nr; + struct index_entry_offset entries[FLEX_ARRAY]; +}; + +#ifndef NO_PTHREADS +static struct index_entry_offset_table *read_ieot_extension(const char *mmap, size_t mmap_size, size_t offset); +static void write_ieot_extension(struct strbuf *sb, struct index_entry_offset_table *ieot); +#endif + static size_t read_eoie_extension(const char *mmap, size_t mmap_size); static void write_eoie_extension(struct strbuf *sb, git_hash_ctx *eoie_context, size_t offset); @@ -1929,6 +1948,15 @@ static void *load_index_extensions(void *_data) return NULL; } +/* + * Mostly randomly chosen maximum thread counts: we + * cap the parallelism to online_cpus() threads, and we want + * to have at least 10000 cache entries per thread for it to + * be worth starting a thread. + */ + +#define THREAD_COST (10000) + /* remember to discard_cache() before reading a different cache! */ int do_read_index(struct index_state *istate, const char *path, int must_exist) { @@ -2521,6 +2549,9 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile, struct strbuf previous_name_buf = STRBUF_INIT, *previous_name; int drop_cache_tree = istate->drop_cache_tree; off_t offset; + int ieot_blocks = 1; + struct index_entry_offset_table *ieot = NULL; + int nr, nr_threads; for (i = removed = extended = 0; i < entries; i++) { if (cache[i]->ce_flags & CE_REMOVE) @@ -2554,10 +2585,44 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile, if (ce_write(&c, newfd, &hdr, sizeof(hdr)) < 0) return -1; +#ifndef NO_PTHREADS + nr_threads = git_config_get_index_threads(); + if (nr_threads != 1) { + int ieot_blocks, cpus; + + /* + * ensure default number of ieot blocks maps evenly to the + * default number of threads that will process them leaving + * room for the thread to load the index extensions. + */ + if (!nr_threads) { + ieot_blocks = istate->cache_nr / THREAD_COST; + cpus = online_cpus(); + if (ieot_blocks > cpus - 1) + ieot_blocks = cpus - 1; + } else { + ieot_blocks = nr_threads; + } + + /* + * no reason to write out the IEOT extension if we don't + * have enough blocks to utilize multi-threading + */ + if (ieot_blocks > 1) { + ieot = xcalloc(1, sizeof(struct index_entry_offset_table) + + (ieot_blocks * sizeof(struct index_entry_offset))); + ieot_blocks = DIV_ROUND_UP(entries, ieot_blocks); + } + } +#endif + offset = lseek(newfd, 0, SEEK_CUR); - if (offset < 0) + if (offset < 0) { + free(ieot); return -1; + } offset += write_buffer_len; + nr = 0; previous_name = (hdr_version == 4) ? &previous_name_buf : NULL; for (i = 0; i < entries; i++) { @@ -2579,24 +2644,74 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile, drop_cache_tree = 1; } + if (ieot && i && (i % ieot_blocks == 0)) { + ieot->entries[ieot->nr].nr = nr; + ieot->entries[ieot->nr].offset = offset; + ieot->nr++; + /* + * If we have a V4 index, set the first byte to an invalid + * character to ensure there is nothing common with the previous + * entry + */ + if (previous_name) + previous_name->buf[0] = 0; + nr = 0; + offset = lseek(newfd, 0, SEEK_CUR); + if (offset < 0) { + free(ieot); + return -1; + } + offset += write_buffer_len; + } if (ce_write_entry(&c, newfd, ce, previous_name, (struct ondisk_cache_entry *)&ondisk) < 0) err = -1; if (err) break; + nr++; + } + if (ieot && nr) { + ieot->entries[ieot->nr].nr = nr; + ieot->entries[ieot->nr].offset = offset; + ieot->nr++; } strbuf_release(&previous_name_buf); - if (err) + if (err) { + free(ieot); return err; + } /* Write extension data here */ offset = lseek(newfd, 0, SEEK_CUR); - if (offset < 0) + if (offset < 0) { + free(ieot); return -1; + } offset += write_buffer_len; the_hash_algo->init_fn(&eoie_c); + /* + * Lets write out CACHE_EXT_INDEXENTRYOFFSETTABLE first so that we + * can minimize the number of extensions we have to scan through to + * find it during load. Write it out regardless of the + * strip_extensions parameter as we need it when loading the shared + * index. + */ +#ifndef NO_PTHREADS + if (ieot) { + struct strbuf sb = STRBUF_INIT; + + write_ieot_extension(&sb, ieot); + err = write_index_ext_header(&c, &eoie_c, newfd, CACHE_EXT_INDEXENTRYOFFSETTABLE, sb.len) < 0 + || ce_write(&c, newfd, sb.buf, sb.len) < 0; + strbuf_release(&sb); + free(ieot); + if (err) + return -1; + } +#endif + if (!strip_extensions && istate->split_index) { struct strbuf sb = STRBUF_INIT; @@ -3180,3 +3295,78 @@ static void write_eoie_extension(struct strbuf *sb, git_hash_ctx *eoie_context, the_hash_algo->final_fn(hash, eoie_context); strbuf_add(sb, hash, the_hash_algo->rawsz); } + +#ifndef NO_PTHREADS +#define IEOT_VERSION (1) + +static struct index_entry_offset_table *read_ieot_extension(const char *mmap, size_t mmap_size, size_t offset) +{ + const char *index = NULL; + uint32_t extsize, ext_version; + struct index_entry_offset_table *ieot; + int i, nr; + + /* find the IEOT extension */ + if (!offset) + return NULL; + while (offset <= mmap_size - the_hash_algo->rawsz - 8) { + extsize = get_be32(mmap + offset + 4); + if (CACHE_EXT((mmap + offset)) == CACHE_EXT_INDEXENTRYOFFSETTABLE) { + index = mmap + offset + 4 + 4; + break; + } + offset += 8; + offset += extsize; + } + if (!index) + return NULL; + + /* validate the version is IEOT_VERSION */ + ext_version = get_be32(index); + if (ext_version != IEOT_VERSION) { + error("invalid IEOT version %d", ext_version); + return NULL; + } + index += sizeof(uint32_t); + + /* extension size - version bytes / bytes per entry */ + nr = (extsize - sizeof(uint32_t)) / (sizeof(uint32_t) + sizeof(uint32_t)); + if (!nr) { + error("invalid number of IEOT entries %d", nr); + return NULL; + } + ieot = xmalloc(sizeof(struct index_entry_offset_table) + + (nr * sizeof(struct index_entry_offset))); + ieot->nr = nr; + for (i = 0; i < nr; i++) { + ieot->entries[i].offset = get_be32(index); + index += sizeof(uint32_t); + ieot->entries[i].nr = get_be32(index); + index += sizeof(uint32_t); + } + + return ieot; +} + +static void write_ieot_extension(struct strbuf *sb, struct index_entry_offset_table *ieot) +{ + uint32_t buffer; + int i; + + /* version */ + put_be32(&buffer, IEOT_VERSION); + strbuf_add(sb, &buffer, sizeof(uint32_t)); + + /* ieot */ + for (i = 0; i < ieot->nr; i++) { + + /* offset */ + put_be32(&buffer, ieot->entries[i].offset); + strbuf_add(sb, &buffer, sizeof(uint32_t)); + + /* count */ + put_be32(&buffer, ieot->entries[i].nr); + strbuf_add(sb, &buffer, sizeof(uint32_t)); + } +} +#endif From patchwork Wed Oct 10 15:59:38 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ben Peart X-Patchwork-Id: 10634799 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id EC64113AD for ; Wed, 10 Oct 2018 16:00:03 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 57A272A84D for ; Wed, 10 Oct 2018 16:00:03 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 4B0A12A85B; Wed, 10 Oct 2018 16:00:03 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 714702A84D for ; Wed, 10 Oct 2018 16:00:02 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726918AbeJJXWs (ORCPT ); Wed, 10 Oct 2018 19:22:48 -0400 Received: from mail-qt1-f194.google.com ([209.85.160.194]:35770 "EHLO mail-qt1-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726902AbeJJXWs (ORCPT ); Wed, 10 Oct 2018 19:22:48 -0400 Received: by mail-qt1-f194.google.com with SMTP id v19-v6so6251931qtg.2 for ; Wed, 10 Oct 2018 08:59:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=7khLTFOeNkcY3nhXBlaUR571vCUJrHfKFVxCfPPwQ2Q=; b=PREHZ+dgJDXD3IxjNkhMzFdS5dNjb5a004rAOwdk+H/frzjJ+rRc4EXRGfjznceVgR U7sI/vX9LF/NUAOyVKHJs2BLcmlEC54ZcGVsS6F+vXMJJwjABqmfNSXuia7phF3nQ4V3 i/IyWigM01l4Z9MXelYeAmdnyfIzp/ZKaAIVea0EZn+5LWI1cfZn79tKo/8erP7xPcWP JSaUR6J4vJdGf57jVYIJFbnEIp0+JCq5JpvxmjBHE6s2xe97dWHevbruotGrLDiljBGq wrKbSOmgZlcJgheEc0zUkTXwW6VcELpvBaTt2aqZOW+ATjxxsFHnvpfL8+NgfD40SLD4 Ss5g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=7khLTFOeNkcY3nhXBlaUR571vCUJrHfKFVxCfPPwQ2Q=; b=PBb8SZe3/CyYeE/Cqnksl+xLwANyGn0/k/iZl/lxagOX4MLRkpNIx4322j2hK/7R/l bwSguVdIhdgItgqAO7M+SCCP6kx53hLkFs9B3FU8y4WEuN88+3/L/Wd7sC03YLFb68fh frnD0TnSLaWh1JcH2W8XWImuqRcgpJCX6hk8NjitO6Ai9lTpXS1XPBoRvjHxBO8+65eI bLezl8ARQTSbGr0bj+KqthRloLyjOxIghfoOGy7IxQsJyWUkCdLpi6eGzph8ZNiC+uHQ +vgAwPsAlCWwyJhpQnMC+eoIpKExvSCYDu443B2gifRQF8wiIathme7DRjZENxQ+b+bU y4Lg== X-Gm-Message-State: ABuFfogXUqM5izNxJ44e1RuJBhyJlmlzIMbP6RuaqJMo1LIezTNZag6b GjM380rFdn/3GjDi7n2miF8SXk3Sh1U= X-Google-Smtp-Source: ACcGV62YV7mklVl2DpBWzj3HZ0jA3pHw89Jq7lwKd8SGOHbJCGXfbijfKJeKJyjg7fhzrWL6SbW8sg== X-Received: by 2002:a0c:f042:: with SMTP id b2-v6mr26847611qvl.232.1539187198517; Wed, 10 Oct 2018 08:59:58 -0700 (PDT) Received: from localhost.localdomain (70-33-148-227.unassigned.ntelos.net. [70.33.148.227]) by smtp.gmail.com with ESMTPSA id d89-v6sm13704920qkj.29.2018.10.10.08.59.57 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 10 Oct 2018 08:59:57 -0700 (PDT) From: Ben Peart To: git@vger.kernel.org Cc: gitster@pobox.com, pclouds@gmail.com, Ben Peart Subject: [PATCH v8 7/7] read-cache: load cache entries on worker threads Date: Wed, 10 Oct 2018 11:59:38 -0400 Message-Id: <20181010155938.20996-8-peartben@gmail.com> X-Mailer: git-send-email 2.18.0.windows.1 In-Reply-To: <20181010155938.20996-1-peartben@gmail.com> References: <20180823154053.20212-1-benpeart@microsoft.com> <20181010155938.20996-1-peartben@gmail.com> Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Ben Peart This patch helps address the CPU cost of loading the index by utilizing the Index Entry Offset Table (IEOT) to divide loading and conversion of the cache entries across multiple threads in parallel. I used p0002-read-cache.sh to generate some performance data: Test w/100,000 files reduced the time by 32.24% Test w/1,000,000 files reduced the time by -4.77% Note that on the 1,000,000 files case, multi-threading the cache entry parsing does not yield a performance win. This is because the cost to parse the index extensions in this repo, far outweigh the cost of loading the cache entries. The high cost of parsing the index extensions is driven by the cache tree and the untracked cache extensions. As this is currently the longest pole, any reduction in this time will reduce the overall index load times so is worth further investigation in another patch series. Signed-off-by: Ben Peart --- read-cache.c | 230 ++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 193 insertions(+), 37 deletions(-) diff --git a/read-cache.c b/read-cache.c index 3ace29d58f..7acc2c86f4 100644 --- a/read-cache.c +++ b/read-cache.c @@ -1720,7 +1720,8 @@ int read_index(struct index_state *istate) return read_index_from(istate, get_index_file(), get_git_dir()); } -static struct cache_entry *create_from_disk(struct index_state *istate, +static struct cache_entry *create_from_disk(struct mem_pool *ce_mem_pool, + unsigned int version, struct ondisk_cache_entry *ondisk, unsigned long *ent_size, const struct cache_entry *previous_ce) @@ -1737,7 +1738,7 @@ static struct cache_entry *create_from_disk(struct index_state *istate, * number of bytes to be stripped from the end of the previous name, * and the bytes to append to the result, to come up with its name. */ - int expand_name_field = istate->version == 4; + int expand_name_field = version == 4; /* On-disk flags are just 16 bits */ flags = get_be16(&ondisk->flags); @@ -1761,16 +1762,17 @@ static struct cache_entry *create_from_disk(struct index_state *istate, const unsigned char *cp = (const unsigned char *)name; size_t strip_len, previous_len; - previous_len = previous_ce ? previous_ce->ce_namelen : 0; + /* If we're at the begining of a block, ignore the previous name */ strip_len = decode_varint(&cp); - if (previous_len < strip_len) { - if (previous_ce) + if (previous_ce) { + previous_len = previous_ce->ce_namelen; + if (previous_len < strip_len) die(_("malformed name field in the index, near path '%s'"), - previous_ce->name); - else - die(_("malformed name field in the index in the first path")); + previous_ce->name); + copy_len = previous_len - strip_len; + } else { + copy_len = 0; } - copy_len = previous_len - strip_len; name = (const char *)cp; } @@ -1780,7 +1782,7 @@ static struct cache_entry *create_from_disk(struct index_state *istate, len += copy_len; } - ce = mem_pool__ce_alloc(istate->ce_mem_pool, len); + ce = mem_pool__ce_alloc(ce_mem_pool, len); ce->ce_stat_data.sd_ctime.sec = get_be32(&ondisk->ctime.sec); ce->ce_stat_data.sd_mtime.sec = get_be32(&ondisk->mtime.sec); @@ -1948,6 +1950,52 @@ static void *load_index_extensions(void *_data) return NULL; } +/* + * A helper function that will load the specified range of cache entries + * from the memory mapped file and add them to the given index. + */ +static unsigned long load_cache_entry_block(struct index_state *istate, + struct mem_pool *ce_mem_pool, int offset, int nr, const char *mmap, + unsigned long start_offset, const struct cache_entry *previous_ce) +{ + int i; + unsigned long src_offset = start_offset; + + for (i = offset; i < offset + nr; i++) { + struct ondisk_cache_entry *disk_ce; + struct cache_entry *ce; + unsigned long consumed; + + disk_ce = (struct ondisk_cache_entry *)(mmap + src_offset); + ce = create_from_disk(ce_mem_pool, istate->version, disk_ce, &consumed, previous_ce); + set_index_entry(istate, i, ce); + + src_offset += consumed; + previous_ce = ce; + } + return src_offset - start_offset; +} + +static unsigned long load_all_cache_entries(struct index_state *istate, + const char *mmap, size_t mmap_size, unsigned long src_offset) +{ + unsigned long consumed; + + if (istate->version == 4) { + mem_pool_init(&istate->ce_mem_pool, + estimate_cache_size_from_compressed(istate->cache_nr)); + } else { + mem_pool_init(&istate->ce_mem_pool, + estimate_cache_size(mmap_size, istate->cache_nr)); + } + + consumed = load_cache_entry_block(istate, istate->ce_mem_pool, + 0, istate->cache_nr, mmap, src_offset, NULL); + return consumed; +} + +#ifndef NO_PTHREADS + /* * Mostly randomly chosen maximum thread counts: we * cap the parallelism to online_cpus() threads, and we want @@ -1957,20 +2005,123 @@ static void *load_index_extensions(void *_data) #define THREAD_COST (10000) +struct load_cache_entries_thread_data +{ + pthread_t pthread; + struct index_state *istate; + struct mem_pool *ce_mem_pool; + int offset; + const char *mmap; + struct index_entry_offset_table *ieot; + int ieot_start; /* starting index into the ieot array */ + int ieot_blocks; /* count of ieot entries to process */ + unsigned long consumed; /* return # of bytes in index file processed */ +}; + +/* + * A thread proc to run the load_cache_entries() computation + * across multiple background threads. + */ +static void *load_cache_entries_thread(void *_data) +{ + struct load_cache_entries_thread_data *p = _data; + int i; + + /* iterate across all ieot blocks assigned to this thread */ + for (i = p->ieot_start; i < p->ieot_start + p->ieot_blocks; i++) { + p->consumed += load_cache_entry_block(p->istate, p->ce_mem_pool, + p->offset, p->ieot->entries[i].nr, p->mmap, p->ieot->entries[i].offset, NULL); + p->offset += p->ieot->entries[i].nr; + } + return NULL; +} + +static unsigned long load_cache_entries_threaded(struct index_state *istate, const char *mmap, size_t mmap_size, + unsigned long src_offset, int nr_threads, struct index_entry_offset_table *ieot) +{ + int i, offset, ieot_blocks, ieot_start, err; + struct load_cache_entries_thread_data *data; + unsigned long consumed = 0; + + /* a little sanity checking */ + if (istate->name_hash_initialized) + BUG("the name hash isn't thread safe"); + + mem_pool_init(&istate->ce_mem_pool, 0); + + /* ensure we have no more threads than we have blocks to process */ + if (nr_threads > ieot->nr) + nr_threads = ieot->nr; + data = xcalloc(nr_threads, sizeof(*data)); + + offset = ieot_start = 0; + ieot_blocks = DIV_ROUND_UP(ieot->nr, nr_threads); + for (i = 0; i < nr_threads; i++) { + struct load_cache_entries_thread_data *p = &data[i]; + int nr, j; + + if (ieot_start + ieot_blocks > ieot->nr) + ieot_blocks = ieot->nr - ieot_start; + + p->istate = istate; + p->offset = offset; + p->mmap = mmap; + p->ieot = ieot; + p->ieot_start = ieot_start; + p->ieot_blocks = ieot_blocks; + + /* create a mem_pool for each thread */ + nr = 0; + for (j = p->ieot_start; j < p->ieot_start + p->ieot_blocks; j++) + nr += p->ieot->entries[j].nr; + if (istate->version == 4) { + mem_pool_init(&p->ce_mem_pool, + estimate_cache_size_from_compressed(nr)); + } else { + mem_pool_init(&p->ce_mem_pool, + estimate_cache_size(mmap_size, nr)); + } + + err = pthread_create(&p->pthread, NULL, load_cache_entries_thread, p); + if (err) + die(_("unable to create load_cache_entries thread: %s"), strerror(err)); + + /* increment by the number of cache entries in the ieot block being processed */ + for (j = 0; j < ieot_blocks; j++) + offset += ieot->entries[ieot_start + j].nr; + ieot_start += ieot_blocks; + } + + for (i = 0; i < nr_threads; i++) { + struct load_cache_entries_thread_data *p = &data[i]; + + err = pthread_join(p->pthread, NULL); + if (err) + die(_("unable to join load_cache_entries thread: %s"), strerror(err)); + mem_pool_combine(istate->ce_mem_pool, p->ce_mem_pool); + consumed += p->consumed; + } + + free(data); + + return consumed; +} +#endif + /* remember to discard_cache() before reading a different cache! */ int do_read_index(struct index_state *istate, const char *path, int must_exist) { - int fd, i; + int fd; struct stat st; unsigned long src_offset; const struct cache_header *hdr; const char *mmap; size_t mmap_size; - const struct cache_entry *previous_ce = NULL; struct load_index_extensions p; size_t extension_offset = 0; #ifndef NO_PTHREADS - int nr_threads; + int nr_threads, cpus; + struct index_entry_offset_table *ieot = NULL; #endif if (istate->initialized) @@ -2012,10 +2163,18 @@ int do_read_index(struct index_state *istate, const char *path, int must_exist) p.mmap = mmap; p.mmap_size = mmap_size; + src_offset = sizeof(*hdr); + #ifndef NO_PTHREADS nr_threads = git_config_get_index_threads(); - if (!nr_threads) - nr_threads = online_cpus(); + + /* TODO: does creating more threads than cores help? */ + if (!nr_threads) { + nr_threads = istate->cache_nr / THREAD_COST; + cpus = online_cpus(); + if (nr_threads > cpus) + nr_threads = cpus; + } if (nr_threads > 1) { extension_offset = read_eoie_extension(mmap, mmap_size); @@ -2030,29 +2189,24 @@ int do_read_index(struct index_state *istate, const char *path, int must_exist) nr_threads--; } } -#endif - if (istate->version == 4) { - mem_pool_init(&istate->ce_mem_pool, - estimate_cache_size_from_compressed(istate->cache_nr)); + /* + * Locate and read the index entry offset table so that we can use it + * to multi-thread the reading of the cache entries. + */ + if (extension_offset && nr_threads > 1) + ieot = read_ieot_extension(mmap, mmap_size, extension_offset); + + if (ieot) { + src_offset += load_cache_entries_threaded(istate, mmap, mmap_size, src_offset, nr_threads, ieot); + free(ieot); } else { - mem_pool_init(&istate->ce_mem_pool, - estimate_cache_size(mmap_size, istate->cache_nr)); + src_offset += load_all_cache_entries(istate, mmap, mmap_size, src_offset); } +#else + src_offset += load_all_cache_entries(istate, mmap, mmap_size, src_offset); +#endif - src_offset = sizeof(*hdr); - for (i = 0; i < istate->cache_nr; i++) { - struct ondisk_cache_entry *disk_ce; - struct cache_entry *ce; - unsigned long consumed; - - disk_ce = (struct ondisk_cache_entry *)(mmap + src_offset); - ce = create_from_disk(istate, disk_ce, &consumed, previous_ce); - set_index_entry(istate, i, ce); - - src_offset += consumed; - previous_ce = ce; - } istate->timestamp.sec = st.st_mtime; istate->timestamp.nsec = ST_MTIME_NSEC(st); @@ -2549,7 +2703,7 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile, struct strbuf previous_name_buf = STRBUF_INIT, *previous_name; int drop_cache_tree = istate->drop_cache_tree; off_t offset; - int ieot_blocks = 1; + int ieot_entries = 1; struct index_entry_offset_table *ieot = NULL; int nr, nr_threads; @@ -2602,6 +2756,8 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile, ieot_blocks = cpus - 1; } else { ieot_blocks = nr_threads; + if (ieot_blocks > istate->cache_nr) + ieot_blocks = istate->cache_nr; } /* @@ -2611,7 +2767,7 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile, if (ieot_blocks > 1) { ieot = xcalloc(1, sizeof(struct index_entry_offset_table) + (ieot_blocks * sizeof(struct index_entry_offset))); - ieot_blocks = DIV_ROUND_UP(entries, ieot_blocks); + ieot_entries = DIV_ROUND_UP(entries, ieot_blocks); } } #endif @@ -2644,7 +2800,7 @@ static int do_write_index(struct index_state *istate, struct tempfile *tempfile, drop_cache_tree = 1; } - if (ieot && i && (i % ieot_blocks == 0)) { + if (ieot && i && (i % ieot_entries == 0)) { ieot->entries[ieot->nr].nr = nr; ieot->entries[ieot->nr].offset = offset; ieot->nr++;