cluster/ec: Add support for hardware acceleration

This patch implements functionalities for fast encoding/decoding
using hardware support. Currently optimized x86_64, SSE and AVX is
added.

Additionally this patch implements a caching mecanism for inverse
matrices to reduce computation time, as well as a new method for
computing the inverse that takes quadratic time instead of cubic.

Finally some unnecessary memory copies have been eliminated to
further increase performance.

Change-Id: I26c75f26fb4201bd22b51335448ea4357235065a
BUG: 1289922
Signed-off-by: Xavier Hernandez <xhernandez@datalab.es>
Reviewed-on: http://review.gluster.org/12837
Tested-by: Pranith Kumar Karampuri <pkarampu@redhat.com>
Smoke: Gluster Build System <jenkins@build.gluster.org>
NetBSD-regression: NetBSD Build System <jenkins@build.gluster.org>
CentOS-regression: Gluster Build System <jenkins@build.gluster.org>
Reviewed-by: Pranith Kumar Karampuri <pkarampu@redhat.com>

1 files changed, 185 insertions, 0 deletions

diff --git a/xlators/cluster/ec/src/ec-galois.c b/xlators/cluster/ec/src/ec-galois.c
new file mode 100644
index 00000000000..7dbbac09713
--- /dev/null
+++ b/xlators/cluster/ec/src/ec-galois.c
@@ -0,0 +1,185 @@
+/*
+  Copyright (c) 2015 DataLab, s.l. <http://www.datalab.es>
+  This file is part of GlusterFS.
+
+  This file is licensed to you under your choice of the GNU Lesser
+  General Public License, version 3 or any later version (LGPLv3 or
+  later), or the GNU General Public License, version 2 (GPLv2), in all
+  cases as published by the Free Software Foundation.
+*/
+
+#include <string.h>
+
+#include "mem-pool.h"
+#include "list.h"
+
+#include "ec-mem-types.h"
+#include "ec-gf8.h"
+
+static ec_gf_t *
+ec_gf_alloc(uint32_t bits, uint32_t mod)
+{
+    ec_gf_t *gf;
+
+    gf = GF_MALLOC(sizeof(ec_gf_t), ec_mt_ec_gf_t);
+    if (gf == NULL) {
+        goto failed;
+    }
+
+    gf->bits = bits;
+    gf->size = 1 << bits;
+    gf->mod = mod;
+
+    gf->log = GF_MALLOC(sizeof(uint32_t) * (gf->size * 2 - 1),
+                        gf_common_mt_int);
+    if (gf->log == NULL) {
+        goto failed_gf;
+    }
+    gf->pow = GF_MALLOC(sizeof(uint32_t) * (gf->size * 2 - 1),
+                        gf_common_mt_int);
+    if (gf->pow == NULL) {
+        goto failed_log;
+    }
+
+    return gf;
+
+failed_log:
+    GF_FREE(gf->log);
+failed_gf:
+    GF_FREE(gf);
+failed:
+    return NULL;
+}
+
+static void
+ec_gf_init_tables(ec_gf_t *gf)
+{
+    uint32_t i, tmp;
+
+    memset(gf->log, -1, sizeof(uint32_t) * gf->size);
+
+    gf->pow[0] = 1;
+    gf->log[0] = gf->size;
+    gf->log[1] = 0;
+    for (i = 1; i < gf->size; i++) {
+        tmp = gf->pow[i - 1] << 1;
+        if (tmp >= gf->size) {
+            tmp ^= gf->mod;
+        }
+        gf->pow[i + gf->size - 1] = gf->pow[i] = tmp;
+        gf->log[tmp + gf->size - 1] = gf->log[tmp] = i;
+    }
+}
+
+ec_gf_t *
+ec_gf_prepare(uint32_t bits, uint32_t mod)
+{
+    ec_gf_mul_t **tbl;
+    ec_gf_t *gf;
+    uint32_t i, j;
+
+    if (bits != 8) {
+        return NULL;
+    }
+
+    tbl = ec_gf8_mul;
+    if (mod == 0) {
+        mod = 0x11d;
+    }
+
+    gf = ec_gf_alloc(bits, mod);
+    if (gf == NULL) {
+        return NULL;
+    }
+    ec_gf_init_tables(gf);
+
+    gf->table = tbl;
+    gf->min_ops = bits * bits;
+    gf->max_ops = 0;
+    gf->avg_ops = 0;
+    for (i = 1; i < gf->size; i++) {
+        for (j = 0; tbl[i]->ops[j].op != EC_GF_OP_END; j++) {
+        }
+        if (gf->max_ops < j) {
+            gf->max_ops = j;
+        }
+        if (gf->min_ops > j) {
+            gf->min_ops = j;
+        }
+        gf->avg_ops += j;
+    }
+    gf->avg_ops /= gf->size;
+
+    return gf;
+}
+
+void
+ec_gf_destroy(ec_gf_t *gf)
+{
+    GF_FREE(gf->pow);
+    GF_FREE(gf->log);
+    GF_FREE(gf);
+}
+
+uint32_t
+ec_gf_add(ec_gf_t *gf, uint32_t a, uint32_t b)
+{
+    if ((a >= gf->size) || (b >= gf->size)) {
+        return gf->size;
+    }
+
+    return a ^ b;
+}
+
+uint32_t
+ec_gf_mul(ec_gf_t *gf, uint32_t a, uint32_t b)
+{
+    if ((a >= gf->size) || (b >= gf->size)) {
+        return gf->size;
+    }
+
+    if ((a != 0) && (b != 0)) {
+        return gf->pow[gf->log[a] + gf->log[b]];
+    }
+
+    return 0;
+}
+
+uint32_t
+ec_gf_div(ec_gf_t *gf, uint32_t a, uint32_t b)
+{
+    if ((a >= gf->size) || (b >= gf->size)) {
+        return gf->size;
+    }
+
+    if (b != 0) {
+        if (a != 0) {
+            return gf->pow[gf->size - 1 + gf->log[a] - gf->log[b]];
+        }
+
+        return 0;
+    }
+
+    return gf->size;
+}
+
+uint32_t
+ec_gf_exp(ec_gf_t *gf, uint32_t a, uint32_t b)
+{
+    uint32_t r;
+
+    if ((a >= gf->size) || ((a == 0) && (b == 0))) {
+        return gf->size;
+    }
+
+    r = 1;
+    while (b != 0) {
+        if ((b & 1) != 0) {
+            r = ec_gf_mul(gf, r, a);
+        }
+        a = ec_gf_mul(gf, a, a);
+        b >>= 1;
+    }
+
+    return r;
+}