From patchwork Thu Sep 28 14:33:41 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Timofey Titovets X-Patchwork-Id: 9976251 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 033A96037E for ; Thu, 28 Sep 2017 14:34:04 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id E9EFC2951A for ; Thu, 28 Sep 2017 14:34:03 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id DF0812951D; Thu, 28 Sep 2017 14:34: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=-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 86DC02951A for ; Thu, 28 Sep 2017 14:34:03 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932122AbdI1OeB (ORCPT ); Thu, 28 Sep 2017 10:34:01 -0400 Received: from mail-wr0-f194.google.com ([209.85.128.194]:35132 "EHLO mail-wr0-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753335AbdI1Odz (ORCPT ); Thu, 28 Sep 2017 10:33:55 -0400 Received: by mail-wr0-f194.google.com with SMTP id n64so2244532wrb.2 for ; Thu, 28 Sep 2017 07:33: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=vrrEZY3JHXJ2ZeY4A/39vhWjmRlqKLk6J+jYFZ3fOek=; b=farkwLXCyXe94Uw1XRtJ5CmYlUJMBOou8QbWX76+uN4NQU6GfoHE7fwKQQzMdZ+c5V sGZoMauy8Ga5EGJcHxnaRCKgXlx1mzpbncW5TpikioJqiffdG4K6XojE7PDpFnxOBB8h rHNMtD8VMhVNtYEiISvWPPkOo8F+jGPBkYDNNPMnATUVmUbALTdGiJtDemJwFupbEBpS aYE1euu2Eh004nNIBxopK6Wg0c/Geu32A7SHNNlwdfUmlHAR8T7ffZTU0yjrcqt8syAE 57B7+65rXk+8Qy3pSvwFgAGrch4cKBiE+KuVzuf9C4GLwyuycYURbHwE6SUpOIFV4saP 4sTA== 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=vrrEZY3JHXJ2ZeY4A/39vhWjmRlqKLk6J+jYFZ3fOek=; b=Izfbj5FKHSSLnhXfMLDcvog4AaqXJKqZecbPPKpYYFkKBpzGP+L056LLYlVJf0+Njv WbxI82Y18rzOC1xfo1n60SJ+V341vtm4n3R4biTHzpFpisDihy2tMUW508JA3Wwo/fcN OvC1CjQe618iJ2I4R12sCwQn06xGA1JbXkitcK2sq13WW31JuKlvML3A/zgmjRr3bYg7 dlWYiQ+DcoAbH+fUZBzys1MOuoCpcbxoPR33iF/S9dR3E6HZel63p5H4/KnpOVvcxzc5 vDbO9MXRtgH8CQbfJEWAeG36vMqvfEMUt6T2VN/RN4rP/u/Rev998jmrdFEJzeNJvbDV cKNA== X-Gm-Message-State: AHPjjUjagvgf9wgDiq6yWvd/DHeKLgro+U11fGC4COeZ2vqgpGoEkrVm 9eGOKCoULYpa7DXjSLKPckVMUg== X-Google-Smtp-Source: AOwi7QCuS+Fxmgcfun74ucYploOo96o2pIKHW7L/S8xUOYQA47EErmYxTugwJulm+ei/xpoBzhNYeQ== X-Received: by 10.223.142.172 with SMTP id q41mr5205876wrb.106.1506609234546; Thu, 28 Sep 2017 07:33:54 -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.53 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 28 Sep 2017 07:33:54 -0700 (PDT) From: Timofey Titovets To: linux-btrfs@vger.kernel.org Cc: Timofey Titovets Subject: [PATCH v8 6/6] Btrfs: heuristic add byte core set calculation Date: Thu, 28 Sep 2017 17:33:41 +0300 Message-Id: <20170928143341.24491-7-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 Calculate byte core set for data sample: Sort bucket's numbers in decreasing order Count how many numbers use 90% of sample If core set are low (<=25%), data are easily compressible If core set high (>=80%), data are not compressible Signed-off-by: Timofey Titovets --- fs/btrfs/compression.c | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 68 insertions(+) -- 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 83daf2f9d051..1aa04ae214a7 100644 --- a/fs/btrfs/compression.c +++ b/fs/btrfs/compression.c @@ -33,6 +33,7 @@ #include #include #include +#include #include "ctree.h" #include "disk-io.h" #include "transaction.h" @@ -1201,6 +1202,62 @@ int btrfs_decompress_buf2page(const char *buf, unsigned long buf_start, } +/* Compare buckets by size, ascending */ +static inline int bucket_comp_rev(const void *lv, const void *rv) +{ + const struct bucket_item *l = (struct bucket_item *)(lv); + const struct bucket_item *r = (struct bucket_item *)(rv); + + return r->count - l->count; +} + +/* + * Byte Core set size + * How many bytes use 90% of sample + * + * Several type of structure d binary data have in general + * nearly all types of bytes, but distribution can be Uniform + * where in bucket all byte types will have the nearly same count + * (ex. Encrypted data) + * and as ex. Normal (Gaussian), where count of bytes will be not so linear + * in that case data can be compressible, probably compressible, and + * not compressible, so assume: + * + * @BYTE_CORE_SET_LOW - main part of byte types repeated frequently + * compression algo can easy fix that + * @BYTE_CORE_SET_HIGH - data have Uniform distribution and with high + * probability not compressible + * + */ + +#define BYTE_CORE_SET_LOW 64 +#define BYTE_CORE_SET_HIGH 200 + +static int byte_core_set_size(struct heuristic_ws *ws) +{ + u32 i; + u32 coreset_sum = 0; + u32 core_set_threshold = ws->sample_size * 90 / 100; + struct bucket_item *bucket = ws->bucket; + + /* Sort in reverse order */ + sort(bucket, BUCKET_SIZE, sizeof(*bucket), &bucket_comp_rev, NULL); + + for (i = 0; i < BYTE_CORE_SET_LOW; i++) + coreset_sum += bucket[i].count; + + if (coreset_sum > core_set_threshold) + return i; + + for (; i < BYTE_CORE_SET_HIGH && bucket[i].count > 0; i++) { + coreset_sum += bucket[i].count; + if (coreset_sum > core_set_threshold) + break; + } + + return i; +} + /* * Count byte types in bucket * That heuristic can detect text like data (configs, xml, json, html & etc) @@ -1348,6 +1405,17 @@ int btrfs_compress_heuristic(struct inode *inode, u64 start, u64 end) goto out; } + i = byte_core_set_size(ws); + if (i <= BYTE_CORE_SET_LOW) { + ret = 3; + goto out; + } + + if (i >= BYTE_CORE_SET_HIGH) { + ret = 0; + goto out; + } + out: __free_workspace(0, ws_list, true); return ret;