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 <nefelim...@gmail.com> --- fs/btrfs/heuristic.c | 51 ++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 50 insertions(+), 1 deletion(-) diff --git a/fs/btrfs/heuristic.c b/fs/btrfs/heuristic.c index 4815d1becf7e..8a5397b74597 100644 --- a/fs/btrfs/heuristic.c +++ b/fs/btrfs/heuristic.c @@ -18,6 +18,7 @@ #include <linux/pagemap.h> #include <linux/string.h> #include <linux/bio.h> +#include <linux/sort.h> #include "compression.h" #define READ_SIZE 16 @@ -25,6 +26,8 @@ #define BUCKET_SIZE 256 #define MAX_SAMPLE_SIZE (BTRFS_MAX_UNCOMPRESSED*READ_SIZE/ITER_SHIFT) #define BYTE_SET_THRESHOLD 64 +#define BYTE_CORE_SET_LOW BYTE_SET_THRESHOLD +#define BYTE_CORE_SET_HIGH 200 // ~80% struct bucket_item { u32 count; @@ -67,6 +70,45 @@ static struct list_head *heuristic_alloc_workspace(void) return ERR_PTR(-ENOMEM); } +/* For bucket sorting */ +static inline int bucket_compare(const void *lv, const void *rv) +{ + struct bucket_item *l = (struct bucket_item *)(lv); + struct bucket_item *r = (struct bucket_item *)(rv); + + return r->count - l->count; +} + +/* + * Byte Core set size + * How many bytes use 90% of sample + */ +static int byte_core_set_size(struct workspace *ws) +{ + u32 a = 0; + 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_compare, NULL); + + for (; a < BYTE_CORE_SET_LOW; a++) + coreset_sum += bucket[a].count; + + if (coreset_sum > core_set_threshold) + return a; + + for (; a < BYTE_CORE_SET_HIGH && bucket[a].count > 0; a++) { + coreset_sum += bucket[a].count; + if (coreset_sum > core_set_threshold) + break; + } + + return a; +} + static u32 byte_set_size(const struct workspace *ws) { u32 a = 0; @@ -167,7 +209,14 @@ static int heuristic(struct list_head *ws, struct inode *inode, if (a > BYTE_SET_THRESHOLD) return 2; - return 1; + a = byte_core_set_size(workspace); + if (a <= BYTE_CORE_SET_LOW) + return 3; + + if (a >= BYTE_CORE_SET_HIGH) + return 0; + + return 4; } const struct btrfs_compress_op btrfs_heuristic = { -- 2.14.1 -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html