"Fossies" - the Fresh Open Source Software Archive

Member "glusterfs-8.2/xlators/cluster/ec/src/ec-method.c" (16 Sep 2020, 11136 Bytes) of package /linux/misc/glusterfs-8.2.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "ec-method.c" see the Fossies "Dox" file reference documentation.

    1 /*
    2   Copyright (c) 2012-2015 DataLab, s.l. <http://www.datalab.es>
    3   This file is part of GlusterFS.
    4 
    5   This file is licensed to you under your choice of the GNU Lesser
    6   General Public License, version 3 or any later version (LGPLv3 or
    7   later), or the GNU General Public License, version 2 (GPLv2), in all
    8   cases as published by the Free Software Foundation.
    9 */
   10 
   11 #include <string.h>
   12 #include <inttypes.h>
   13 
   14 #include "ec-types.h"
   15 #include "ec-mem-types.h"
   16 #include "ec-galois.h"
   17 #include "ec-code.h"
   18 #include "ec-method.h"
   19 #include "ec-helpers.h"
   20 
   21 static void
   22 ec_method_matrix_normal(ec_gf_t *gf, uint32_t *matrix, uint32_t columns,
   23                         uint32_t *values, uint32_t count)
   24 {
   25     uint32_t i, j, v, tmp;
   26 
   27     columns--;
   28     for (i = 0; i < count; i++) {
   29         v = *values++;
   30         *matrix++ = tmp = ec_gf_exp(gf, v, columns);
   31         for (j = 0; j < columns; j++) {
   32             *matrix++ = tmp = ec_gf_div(gf, tmp, v);
   33         }
   34     }
   35 }
   36 
   37 static void
   38 ec_method_matrix_inverse(ec_gf_t *gf, uint32_t *matrix, uint32_t *values,
   39                          uint32_t count)
   40 {
   41     uint32_t a[count];
   42     uint32_t i, j, p, last, tmp;
   43 
   44     last = count - 1;
   45     for (i = 0; i < last; i++) {
   46         a[i] = 1;
   47     }
   48     a[i] = values[0];
   49     for (i = last; i > 0; i--) {
   50         for (j = i - 1; j < last; j++) {
   51             a[j] = a[j + 1] ^ ec_gf_mul(gf, values[i], a[j]);
   52         }
   53         a[j] = ec_gf_mul(gf, values[i], a[j]);
   54     }
   55     for (i = 0; i < count; i++) {
   56         p = a[0];
   57         matrix += count;
   58         *matrix = tmp = p ^ values[i];
   59         for (j = 1; j < last; j++) {
   60             matrix += count;
   61             *matrix = tmp = a[j] ^ ec_gf_mul(gf, values[i], tmp);
   62             p = tmp ^ ec_gf_mul(gf, values[i], p);
   63         }
   64         for (j = 0; j < last; j++) {
   65             *matrix = ec_gf_div(gf, *matrix, p);
   66             matrix -= count;
   67         }
   68         *matrix = ec_gf_div(gf, 1, p);
   69         matrix++;
   70     }
   71 }
   72 
   73 static void
   74 ec_method_matrix_init(ec_matrix_list_t *list, ec_matrix_t *matrix,
   75                       uintptr_t mask, uint32_t *rows, gf_boolean_t inverse)
   76 {
   77     uint32_t i;
   78 
   79     matrix->refs = 1;
   80     matrix->mask = mask;
   81     matrix->code = list->code;
   82     matrix->columns = list->columns;
   83     INIT_LIST_HEAD(&matrix->lru);
   84 
   85     if (inverse) {
   86         matrix->rows = list->columns;
   87         ec_method_matrix_inverse(matrix->code->gf, matrix->values, rows,
   88                                  matrix->rows);
   89         for (i = 0; i < matrix->rows; i++) {
   90             matrix->row_data[i].values = matrix->values + i * matrix->columns;
   91             matrix->row_data[i].func.interleaved = ec_code_build_interleaved(
   92                 matrix->code, EC_METHOD_WORD_SIZE, matrix->row_data[i].values,
   93                 matrix->columns);
   94         }
   95     } else {
   96         matrix->rows = list->rows;
   97         ec_method_matrix_normal(matrix->code->gf, matrix->values,
   98                                 matrix->columns, rows, matrix->rows);
   99         for (i = 0; i < matrix->rows; i++) {
  100             matrix->row_data[i].values = matrix->values + i * matrix->columns;
  101             matrix->row_data[i].func.linear = ec_code_build_linear(
  102                 matrix->code, EC_METHOD_WORD_SIZE, matrix->row_data[i].values,
  103                 matrix->columns);
  104         }
  105     }
  106 }
  107 
  108 static void
  109 ec_method_matrix_release(ec_matrix_t *matrix)
  110 {
  111     uint32_t i;
  112 
  113     for (i = 0; i < matrix->rows; i++) {
  114         if (matrix->row_data[i].func.linear != NULL) {
  115             ec_code_release(matrix->code, &matrix->row_data[i].func);
  116             matrix->row_data[i].func.linear = NULL;
  117         }
  118     }
  119 }
  120 
  121 static void
  122 ec_method_matrix_destroy(ec_matrix_list_t *list, ec_matrix_t *matrix)
  123 {
  124     list_del_init(&matrix->lru);
  125 
  126     ec_method_matrix_release(matrix);
  127 
  128     mem_put(matrix);
  129 
  130     list->count--;
  131 }
  132 
  133 static void
  134 ec_method_matrix_unref(ec_matrix_list_t *list, ec_matrix_t *matrix)
  135 {
  136     if (--matrix->refs == 0) {
  137         list_add_tail(&matrix->lru, &list->lru);
  138         if (list->count > list->max) {
  139             matrix = list_first_entry(&list->lru, ec_matrix_t, lru);
  140             ec_method_matrix_destroy(list, matrix);
  141         }
  142     }
  143 }
  144 
  145 static ec_matrix_t *
  146 ec_method_matrix_lookup(ec_matrix_list_t *list, uintptr_t mask, uint32_t *pos)
  147 {
  148     ec_matrix_t *matrix;
  149     uint32_t i, j, k;
  150 
  151     i = 0;
  152     j = list->count;
  153     while (i < j) {
  154         k = (i + j) >> 1;
  155         matrix = list->objects[k];
  156         if (matrix->mask == mask) {
  157             *pos = k;
  158             return matrix;
  159         }
  160         if (matrix->mask < mask) {
  161             i = k + 1;
  162         } else {
  163             j = k;
  164         }
  165     }
  166     *pos = i;
  167 
  168     return NULL;
  169 }
  170 
  171 static void
  172 ec_method_matrix_remove(ec_matrix_list_t *list, uintptr_t mask)
  173 {
  174     uint32_t pos;
  175 
  176     if (ec_method_matrix_lookup(list, mask, &pos) != NULL) {
  177         list->count--;
  178         if (pos < list->count) {
  179             memmove(list->objects + pos, list->objects + pos + 1,
  180                     sizeof(ec_matrix_t *) * (list->count - pos));
  181         }
  182     }
  183 }
  184 
  185 static void
  186 ec_method_matrix_insert(ec_matrix_list_t *list, ec_matrix_t *matrix)
  187 {
  188     uint32_t pos;
  189 
  190     GF_ASSERT(ec_method_matrix_lookup(list, matrix->mask, &pos) == NULL);
  191 
  192     if (pos < list->count) {
  193         memmove(list->objects + pos + 1, list->objects + pos,
  194                 sizeof(ec_matrix_t *) * (list->count - pos));
  195     }
  196     list->objects[pos] = matrix;
  197     list->count++;
  198 }
  199 
  200 static ec_matrix_t *
  201 ec_method_matrix_get(ec_matrix_list_t *list, uintptr_t mask, uint32_t *rows)
  202 {
  203     ec_matrix_t *matrix;
  204     uint32_t pos;
  205 
  206     LOCK(&list->lock);
  207 
  208     matrix = ec_method_matrix_lookup(list, mask, &pos);
  209     if (matrix != NULL) {
  210         list_del_init(&matrix->lru);
  211         matrix->refs++;
  212 
  213         goto out;
  214     }
  215 
  216     if ((list->count >= list->max) && !list_empty(&list->lru)) {
  217         matrix = list_first_entry(&list->lru, ec_matrix_t, lru);
  218         list_del_init(&matrix->lru);
  219 
  220         ec_method_matrix_remove(list, matrix->mask);
  221 
  222         ec_method_matrix_release(matrix);
  223     } else {
  224         matrix = mem_get0(list->pool);
  225         if (matrix == NULL) {
  226             matrix = EC_ERR(ENOMEM);
  227             goto out;
  228         }
  229         matrix->values = (uint32_t *)((uintptr_t)matrix + sizeof(ec_matrix_t) +
  230                                       sizeof(ec_matrix_row_t) * list->columns);
  231     }
  232 
  233     ec_method_matrix_init(list, matrix, mask, rows, _gf_true);
  234 
  235     if (list->count < list->max) {
  236         ec_method_matrix_insert(list, matrix);
  237     } else {
  238         matrix->mask = 0;
  239     }
  240 
  241 out:
  242     UNLOCK(&list->lock);
  243 
  244     return matrix;
  245 }
  246 
  247 static void
  248 ec_method_matrix_put(ec_matrix_list_t *list, ec_matrix_t *matrix)
  249 {
  250     LOCK(&list->lock);
  251 
  252     ec_method_matrix_unref(list, matrix);
  253 
  254     UNLOCK(&list->lock);
  255 }
  256 
  257 static int32_t
  258 ec_method_setup(xlator_t *xl, ec_matrix_list_t *list, const char *gen)
  259 {
  260     ec_matrix_t *matrix;
  261     uint32_t values[list->rows];
  262     uint32_t i;
  263     int32_t err;
  264 
  265     matrix = GF_MALLOC(sizeof(ec_matrix_t) +
  266                            sizeof(ec_matrix_row_t) * list->rows +
  267                            sizeof(uint32_t) * list->columns * list->rows,
  268                        ec_mt_ec_matrix_t);
  269     if (matrix == NULL) {
  270         err = -ENOMEM;
  271         goto failed;
  272     }
  273     memset(matrix, 0, sizeof(ec_matrix_t));
  274     matrix->values = (uint32_t *)((uintptr_t)matrix + sizeof(ec_matrix_t) +
  275                                   sizeof(ec_matrix_row_t) * list->rows);
  276 
  277     list->code = ec_code_create(list->gf, ec_code_detect(xl, gen));
  278     if (EC_IS_ERR(list->code)) {
  279         err = EC_GET_ERR(list->code);
  280         list->code = NULL;
  281         goto failed_matrix;
  282     }
  283 
  284     for (i = 0; i < list->rows; i++) {
  285         values[i] = i + 1;
  286     }
  287     ec_method_matrix_init(list, matrix, 0, values, _gf_false);
  288 
  289     list->encode = matrix;
  290 
  291     return 0;
  292 
  293 failed_matrix:
  294     GF_FREE(matrix);
  295 failed:
  296     return err;
  297 }
  298 
  299 int32_t
  300 ec_method_init(xlator_t *xl, ec_matrix_list_t *list, uint32_t columns,
  301                uint32_t rows, uint32_t max, const char *gen)
  302 {
  303     list->columns = columns;
  304     list->rows = rows;
  305     list->max = max;
  306     list->stripe = EC_METHOD_CHUNK_SIZE * list->columns;
  307     INIT_LIST_HEAD(&list->lru);
  308     int32_t err;
  309 
  310     list->pool = mem_pool_new_fn(xl->ctx,
  311                                  sizeof(ec_matrix_t) +
  312                                      sizeof(ec_matrix_row_t) * columns +
  313                                      sizeof(uint32_t) * columns * columns,
  314                                  128, "ec_matrix_t");
  315     if (list->pool == NULL) {
  316         err = -ENOMEM;
  317         goto failed;
  318     }
  319 
  320     list->objects = GF_MALLOC(sizeof(ec_matrix_t *) * max, ec_mt_ec_matrix_t);
  321     if (list->objects == NULL) {
  322         err = -ENOMEM;
  323         goto failed_pool;
  324     }
  325 
  326     list->gf = ec_gf_prepare(EC_GF_BITS, EC_GF_MOD);
  327     if (EC_IS_ERR(list->gf)) {
  328         err = EC_GET_ERR(list->gf);
  329         goto failed_objects;
  330     }
  331 
  332     err = ec_method_setup(xl, list, gen);
  333     if (err != 0) {
  334         goto failed_gf;
  335     }
  336 
  337     LOCK_INIT(&list->lock);
  338 
  339     return 0;
  340 
  341 failed_gf:
  342     ec_gf_destroy(list->gf);
  343 failed_objects:
  344     GF_FREE(list->objects);
  345 failed_pool:
  346     mem_pool_destroy(list->pool);
  347 failed:
  348     list->pool = NULL;
  349     list->objects = NULL;
  350     list->gf = NULL;
  351 
  352     return err;
  353 }
  354 
  355 void
  356 ec_method_fini(ec_matrix_list_t *list)
  357 {
  358     ec_matrix_t *matrix;
  359 
  360     if (list->encode == NULL) {
  361         return;
  362     }
  363 
  364     while (!list_empty(&list->lru)) {
  365         matrix = list_first_entry(&list->lru, ec_matrix_t, lru);
  366         ec_method_matrix_destroy(list, matrix);
  367     }
  368 
  369     GF_ASSERT(list->count == 0);
  370 
  371     if (list->pool) /*Init was successful*/
  372         LOCK_DESTROY(&list->lock);
  373 
  374     ec_method_matrix_release(list->encode);
  375     GF_FREE(list->encode);
  376 
  377     ec_code_destroy(list->code);
  378     ec_gf_destroy(list->gf);
  379     GF_FREE(list->objects);
  380 
  381     if (list->pool)
  382         mem_pool_destroy(list->pool);
  383 }
  384 
  385 int32_t
  386 ec_method_update(xlator_t *xl, ec_matrix_list_t *list, const char *gen)
  387 {
  388     /* TODO: Allow changing code generator */
  389 
  390     return 0;
  391 }
  392 
  393 void
  394 ec_method_encode(ec_matrix_list_t *list, uint64_t size, void *in, void **out)
  395 {
  396     ec_matrix_t *matrix;
  397     uint64_t pos;
  398     uint32_t i;
  399 
  400     matrix = list->encode;
  401     for (pos = 0; pos < size; pos += list->stripe) {
  402         for (i = 0; i < matrix->rows; i++) {
  403             matrix->row_data[i].func.linear(
  404                 out[i], in, pos, matrix->row_data[i].values, list->columns);
  405             out[i] += EC_METHOD_CHUNK_SIZE;
  406         }
  407     }
  408 }
  409 
  410 int32_t
  411 ec_method_decode(ec_matrix_list_t *list, uint64_t size, uintptr_t mask,
  412                  uint32_t *rows, void **in, void *out)
  413 {
  414     ec_matrix_t *matrix;
  415     uint64_t pos;
  416     uint32_t i;
  417 
  418     matrix = ec_method_matrix_get(list, mask, rows);
  419     if (EC_IS_ERR(matrix)) {
  420         return EC_GET_ERR(matrix);
  421     }
  422     for (pos = 0; pos < size; pos += EC_METHOD_CHUNK_SIZE) {
  423         for (i = 0; i < matrix->rows; i++) {
  424             matrix->row_data[i].func.interleaved(
  425                 out, in, pos, matrix->row_data[i].values, list->columns);
  426             out += EC_METHOD_CHUNK_SIZE;
  427         }
  428     }
  429 
  430     ec_method_matrix_put(list, matrix);
  431 
  432     return 0;
  433 }