From patchwork Thu Sep 28 14:33:37 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Timofey Titovets X-Patchwork-Id: 9976253 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id A2BB76037E for ; Thu, 28 Sep 2017 14:34:07 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 945C72957C for ; Thu, 28 Sep 2017 14:34:07 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 89463295AE; Thu, 28 Sep 2017 14:34:07 +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=-6.3 required=2.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED, FREEMAIL_FROM, RCVD_IN_DNSWL_HI, RCVD_IN_SORBS_SPAM, T_DKIM_INVALID 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 2EFC62951B for ; Thu, 28 Sep 2017 14:34:07 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753345AbdI1Ody (ORCPT ); Thu, 28 Sep 2017 10:33:54 -0400 Received: from mail-wm0-f65.google.com ([74.125.82.65]:46899 "EHLO mail-wm0-f65.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753335AbdI1Odw (ORCPT ); Thu, 28 Sep 2017 10:33:52 -0400 Received: by mail-wm0-f65.google.com with SMTP id m72so2753575wmc.1 for ; Thu, 28 Sep 2017 07:33: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=2wBLRmLsrdNnGXFB84OyN/TvZbWawPh2ACFVqXcpJ1Y=; b=EJvTylb3Y6LQPEd2z3i87SwDJn9b7J/nlSAytQ1ffUvU4Ylqzjn3i9uObq9erDBBrT NiGfYFs7V9JtG8oYas1JOiF9JHgp1U3eA02zMbFid/L7HAhwenhZsJ6HCzBLOGWbg6Rm uKnK6EjUmyLi5tm4Rv4UVuOtIElPoPHfPFsc1u2WXaPjvJFwx+c53Nk88icm+eXjGQ31 3UwJB55cxAOs8AEI86dlfl+45TIO6FLEWIztqRv+TvOPoyp5TFG+iNFQYRICFxa+PYjx Y8tsLo+8BAz0jRC/J/6eMzDvdaajrqtTYAhfD2grk+PPFmYIA6plghOvrQN5D5iQ1dsZ J4qA== 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=2wBLRmLsrdNnGXFB84OyN/TvZbWawPh2ACFVqXcpJ1Y=; b=W+HTAsCeyyr6ySHnr/hvFynYoAz2uEYLv+zpZyx1gcmgqY9BJTBUYKKRIuteAgpEkT VRo0zd5QrYvdsPqu7km0DfdoHpOWQjC+V7A3quPXjFh3+UNdILBzb31I3SuuXDVeBeay NPaui104Krsk85pM6C0Zb0ebW2M0fgoWaphMgcanqeY0S9LC69wpc/v6y4k8dOCfYxuJ aZ/LJL7LHb2RkyzUbIc658QBVlTPgEh9yH5Y04z9LPWLRv3C0F7bKVq8rPuZiSgJFWBe P2ZDElgUuw9tok3ygxQkvRLYJNP6yBslWArbJ9Nk/Ho7G5798kACuEfsDbvwjxoBs98/ SrJA== X-Gm-Message-State: AMCzsaUrq8DmvElZTaxy6amZUNkYXAKowP9e3Jg4qJ5G5zBnB/uJHYlG jV2gu3LWlr8hcYGDwM1PintYFg== X-Google-Smtp-Source: AOwi7QCce9dmZsapa/145PHzcutwbQq49xIOQCZ5RHblJUTvrdQm4nHwr3Sz5qJck6KfJQc3hq52pg== X-Received: by 10.28.74.89 with SMTP id x86mr1312769wma.57.1506609231087; Thu, 28 Sep 2017 07:33:51 -0700 (PDT) Received: from titovetst-l.itransition.corp ([93.171.6.182]) by smtp.gmail.com with ESMTPSA id k82sm460633wmf.19.2017.09.28.07.33.50 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 28 Sep 2017 07:33:50 -0700 (PDT) From: Timofey Titovets To: linux-btrfs@vger.kernel.org Cc: Timofey Titovets Subject: [PATCH v8 2/6] Btrfs: heuristic workspace add bucket and sample items, macros Date: Thu, 28 Sep 2017 17:33:37 +0300 Message-Id: <20170928143341.24491-3-nefelim4ag@gmail.com> X-Mailer: git-send-email 2.14.2 In-Reply-To: <20170928143341.24491-1-nefelim4ag@gmail.com> References: <20170928143341.24491-1-nefelim4ag@gmail.com> Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Added macros: - For future sampling algo - For bucket size Heuristic workspace: - Add bucket for storing byte type counters - Add sample array for storing partial copy of input data range - Add counter for store current sample size to workspace Signed-off-by: Timofey Titovets --- fs/btrfs/compression.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 56 insertions(+), 1 deletion(-) -- 2.14.2 -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c index c3624e8e3919..1715655d050e 100644 --- a/fs/btrfs/compression.c +++ b/fs/btrfs/compression.c @@ -691,7 +691,50 @@ blk_status_t btrfs_submit_compressed_read(struct inode *inode, struct bio *bio, } +/* + * Heuristic use systematic sampling to collect data from + * input data range, so some constant needed to control algo + * + * @SAMPLING_READ_SIZE - how many bytes will be copied from on each sample + * @SAMPLING_INTERVAL - period that used to iterate over input data range + */ +#define SAMPLING_READ_SIZE 16 +#define SAMPLING_INTERVAL 256 + +/* + * For statistic analize of input data range + * consider that data consists from bytes + * so this is Galois Field with 256 objects + * each object have attribute count, i.e. how many times + * that object detected in sample + */ +#define BUCKET_SIZE 256 + +/* + * The size of the sample is based on a statistical sampling rule of thumb. + * That common to perform sampling tests as long as number of elements in + * each cell is at least five. + * + * Instead of five, for now choose 32 value to obtain more accurate results. + * If the data contains the maximum number of symbols, which is 256, + * lets obtain a sample size bound of 8192. + * + * So sample at most 8KB of data per data range: 16 consecutive + * bytes from up to 512 locations. + */ +#define MAX_SAMPLE_SIZE (BTRFS_MAX_UNCOMPRESSED * \ + SAMPLING_READ_SIZE / SAMPLING_INTERVAL) + + +struct bucket_item { + u32 count; +}; + struct heuristic_ws { + /* Partial copy of input data */ + u8 *sample; + /* Bucket store counter for each byte type */ + struct bucket_item *bucket; struct list_head list; }; @@ -701,6 +744,8 @@ static void free_heuristic_ws(struct list_head *ws) workspace = list_entry(ws, struct heuristic_ws, list); + kvfree(workspace->sample); + kfree(workspace->bucket); kfree(workspace); } @@ -711,9 +756,19 @@ static struct list_head *alloc_heuristic_ws(void){ if (!ws) return ERR_PTR(-ENOMEM); - INIT_LIST_HEAD(&ws->list); + ws->sample = kvmalloc(MAX_SAMPLE_SIZE, GFP_KERNEL); + if (!ws->sample) + goto fail; + + ws->bucket = kcalloc(BUCKET_SIZE, sizeof(*ws->bucket), GFP_KERNEL); + if (!ws->bucket) + goto fail; + INIT_LIST_HEAD(&ws->list); return &ws->list; +fail: + free_heuristic_ws(&ws->list); + return ERR_PTR(-ENOMEM); } struct workspaces_list {