4
Jerasure - A C/C++ Library for a Variety of Reed-Solomon and RAID-6 Erasure Coding Techniques
10
Department of Electrical Engineering and Computer Science
11
University of Tennessee
15
Copyright (c) 2011, James S. Plank
18
Redistribution and use in source and binary forms, with or without
19
modification, are permitted provided that the following conditions
22
- Redistributions of source code must retain the above copyright
23
notice, this list of conditions and the following disclaimer.
25
- Redistributions in binary form must reproduce the above copyright
26
notice, this list of conditions and the following disclaimer in
27
the documentation and/or other materials provided with the
30
- Neither the name of the University of Tennessee nor the names of its
31
contributors may be used to endorse or promote products derived
32
from this software without specific prior written permission.
34
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
35
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
36
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
37
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
38
HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
39
INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
40
BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
41
OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
42
AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
43
LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
44
WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
45
POSSIBILITY OF SUCH DAMAGE.
56
#define talloc(type, num) (type *) malloc(sizeof(type)*(num))
58
static double jerasure_total_xor_bytes = 0;
59
static double jerasure_total_gf_bytes = 0;
60
static double jerasure_total_memcpy_bytes = 0;
62
void jerasure_print_matrix(int *m, int rows, int cols, int w)
73
sprintf(s, "%u", w2-1);
77
for (i = 0; i < rows; i++) {
78
for (j = 0; j < cols; j++) {
79
if (j != 0) printf(" ");
80
printf("%*u", fw, m[i*cols+j]);
86
void jerasure_print_bitmatrix(int *m, int rows, int cols, int w)
90
for (i = 0; i < rows; i++) {
91
if (i != 0 && i%w == 0) printf("\n");
92
for (j = 0; j < cols; j++) {
93
if (j != 0 && j%w == 0) printf(" ");
94
printf("%d", m[i*cols+j]);
100
int jerasure_make_decoding_matrix(int k, int m, int w, int *matrix, int *erased, int *decoding_matrix, int *dm_ids)
105
for (i = 0; j < k; i++) {
106
if (erased[i] == 0) {
112
tmpmat = talloc(int, k*k);
113
if (tmpmat == NULL) { return -1; }
114
for (i = 0; i < k; i++) {
116
for (j = 0; j < k; j++) tmpmat[i*k+j] = 0;
117
tmpmat[i*k+dm_ids[i]] = 1;
119
for (j = 0; j < k; j++) {
120
tmpmat[i*k+j] = matrix[(dm_ids[i]-k)*k+j];
125
i = jerasure_invert_matrix(tmpmat, decoding_matrix, k, w);
130
/* Internal Routine */
131
int jerasure_make_decoding_bitmatrix(int k, int m, int w, int *matrix, int *erased, int *decoding_matrix, int *dm_ids)
137
for (i = 0; j < k; i++) {
138
if (erased[i] == 0) {
144
tmpmat = talloc(int, k*k*w*w);
145
if (tmpmat == NULL) { return -1; }
146
for (i = 0; i < k; i++) {
149
for (j = 0; j < k*w*w; j++) tmpmat[index+j] = 0;
150
index = i*k*w*w+dm_ids[i]*w;
151
for (j = 0; j < w; j++) {
157
mindex = (dm_ids[i]-k)*k*w*w;
158
for (j = 0; j < k*w*w; j++) {
159
tmpmat[index+j] = matrix[mindex+j];
164
i = jerasure_invert_bitmatrix(tmpmat, decoding_matrix, k*w);
169
int jerasure_matrix_decode(int k, int m, int w, int *matrix, int row_k_ones, int *erasures,
170
char **data_ptrs, char **coding_ptrs, int size)
172
int i, edd, lastdrive;
174
int *erased, *decoding_matrix, *dm_ids;
176
if (w != 8 && w != 16 && w != 32) return -1;
178
erased = jerasure_erasures_to_erased(k, m, erasures);
179
if (erased == NULL) return -1;
181
/* Find the number of data drives failed */
186
for (i = 0; i < k; i++) {
193
/* You only need to create the decoding matrix in the following cases:
195
1. edd > 0 and row_k_ones is false.
196
2. edd > 0 and row_k_ones is true and coding device 0 has been erased.
199
We're going to use lastdrive to denote when to stop decoding data.
200
At this point in the code, it is equal to the last erased data device.
201
However, if we can't use the parity row to decode it (i.e. row_k_ones=0
202
or erased[k] = 1, we're going to set it to k so that the decoding
203
pass will decode all data.
206
if (!row_k_ones || erased[k]) lastdrive = k;
209
decoding_matrix = NULL;
211
if (edd > 1 || (edd > 0 && (!row_k_ones || erased[k]))) {
212
dm_ids = talloc(int, k);
213
if (dm_ids == NULL) {
218
decoding_matrix = talloc(int, k*k);
219
if (decoding_matrix == NULL) {
225
if (jerasure_make_decoding_matrix(k, m, w, matrix, erased, decoding_matrix, dm_ids) < 0) {
228
free(decoding_matrix);
233
/* Decode the data drives.
234
If row_k_ones is true and coding device 0 is intact, then only decode edd-1 drives.
235
This is done by stopping at lastdrive.
236
We test whether edd > 0 so that we can exit the loop early if we're done.
239
for (i = 0; edd > 0 && i < lastdrive; i++) {
241
jerasure_matrix_dotprod(k, w, decoding_matrix+(i*k), dm_ids, i, data_ptrs, coding_ptrs, size);
246
/* Then if necessary, decode drive lastdrive */
249
tmpids = talloc(int, k);
250
for (i = 0; i < k; i++) {
251
tmpids[i] = (i < lastdrive) ? i : i+1;
253
jerasure_matrix_dotprod(k, w, matrix, tmpids, lastdrive, data_ptrs, coding_ptrs, size);
257
/* Finally, re-encode any erased coding devices */
259
for (i = 0; i < m; i++) {
261
jerasure_matrix_dotprod(k, w, matrix+(i*k), NULL, i+k, data_ptrs, coding_ptrs, size);
266
if (dm_ids != NULL) free(dm_ids);
267
if (decoding_matrix != NULL) free(decoding_matrix);
273
int *jerasure_matrix_to_bitmatrix(int k, int m, int w, int *matrix)
276
int rowelts, rowindex, colindex, elt, i, j, l, x;
278
bitmatrix = talloc(int, k*m*w*w);
279
if (bitmatrix == NULL) { return NULL; }
284
for (i = 0; i < m; i++) {
286
for (j = 0; j < k; j++) {
288
for (x = 0; x < w; x++) {
289
for (l = 0; l < w; l++) {
290
bitmatrix[colindex+x+l*rowelts] = ((elt & (1 << l)) ? 1 : 0);
292
elt = galois_single_multiply(elt, 2, w);
296
rowindex += rowelts * w;
301
void jerasure_matrix_encode(int k, int m, int w, int *matrix,
302
char **data_ptrs, char **coding_ptrs, int size)
306
if (w != 8 && w != 16 && w != 32) {
307
fprintf(stderr, "ERROR: jerasure_matrix_encode() and w is not 8, 16 or 32\n");
311
for (i = 0; i < m; i++) {
312
jerasure_matrix_dotprod(k, w, matrix+(i*k), NULL, k+i, data_ptrs, coding_ptrs, size);
316
void jerasure_bitmatrix_dotprod(int k, int w, int *bitmatrix_row,
317
int *src_ids, int dest_id,
318
char **data_ptrs, char **coding_ptrs, int size, int packetsize)
320
int j, sindex, pstarted, index, x, y;
321
char *dptr, *pptr, *bdptr, *bpptr;
323
if (size%(w*packetsize) != 0) {
324
fprintf(stderr, "jerasure_bitmatrix_dotprod - size%c(w*packetsize)) must = 0\n", '%');
328
bpptr = (dest_id < k) ? data_ptrs[dest_id] : coding_ptrs[dest_id-k];
330
for (sindex = 0; sindex < size; sindex += (packetsize*w)) {
332
for (j = 0; j < w; j++) {
334
pptr = bpptr + sindex + j*packetsize;
335
for (x = 0; x < k; x++) {
336
if (src_ids == NULL) {
337
bdptr = data_ptrs[x];
338
} else if (src_ids[x] < k) {
339
bdptr = data_ptrs[src_ids[x]];
341
bdptr = coding_ptrs[src_ids[x]-k];
343
for (y = 0; y < w; y++) {
344
if (bitmatrix_row[index]) {
345
dptr = bdptr + sindex + y*packetsize;
347
memcpy(pptr, dptr, packetsize);
348
jerasure_total_memcpy_bytes += packetsize;
351
galois_region_xor(pptr, dptr, pptr, packetsize);
352
jerasure_total_xor_bytes += packetsize;
362
void jerasure_do_parity(int k, char **data_ptrs, char *parity_ptr, int size)
366
memcpy(parity_ptr, data_ptrs[0], size);
367
jerasure_total_memcpy_bytes += size;
369
for (i = 1; i < k; i++) {
370
galois_region_xor(data_ptrs[i], parity_ptr, parity_ptr, size);
371
jerasure_total_xor_bytes += size;
375
int jerasure_invert_matrix(int *mat, int *inv, int rows, int w)
377
int cols, i, j, k, x, rs2;
378
int row_start, tmp, inverse;
383
for (i = 0; i < rows; i++) {
384
for (j = 0; j < cols; j++) {
385
inv[k] = (i == j) ? 1 : 0;
390
/* First -- convert into upper triangular */
391
for (i = 0; i < cols; i++) {
394
/* Swap rows if we ave a zero i,i element. If we can't swap, then the
395
matrix was not invertible */
397
if (mat[row_start+i] == 0) {
398
for (j = i+1; j < rows && mat[cols*j+i] == 0; j++) ;
399
if (j == rows) return -1;
401
for (k = 0; k < cols; k++) {
402
tmp = mat[row_start+k];
403
mat[row_start+k] = mat[rs2+k];
405
tmp = inv[row_start+k];
406
inv[row_start+k] = inv[rs2+k];
411
/* Multiply the row by 1/element i,i */
412
tmp = mat[row_start+i];
414
inverse = galois_single_divide(1, tmp, w);
415
for (j = 0; j < cols; j++) {
416
mat[row_start+j] = galois_single_multiply(mat[row_start+j], inverse, w);
417
inv[row_start+j] = galois_single_multiply(inv[row_start+j], inverse, w);
421
/* Now for each j>i, add A_ji*Ai to Aj */
423
for (j = i+1; j != cols; j++) {
428
for (x = 0; x < cols; x++) {
429
mat[rs2+x] ^= mat[row_start+x];
430
inv[rs2+x] ^= inv[row_start+x];
435
for (x = 0; x < cols; x++) {
436
mat[rs2+x] ^= galois_single_multiply(tmp, mat[row_start+x], w);
437
inv[rs2+x] ^= galois_single_multiply(tmp, inv[row_start+x], w);
444
/* Now the matrix is upper triangular. Start at the top and multiply down */
446
for (i = rows-1; i >= 0; i--) {
448
for (j = 0; j < i; j++) {
450
if (mat[rs2+i] != 0) {
453
for (k = 0; k < cols; k++) {
454
inv[rs2+k] ^= galois_single_multiply(tmp, inv[row_start+k], w);
462
int jerasure_invertible_matrix(int *mat, int rows, int w)
464
int cols, i, j, k, x, rs2;
465
int row_start, tmp, inverse;
469
/* First -- convert into upper triangular */
470
for (i = 0; i < cols; i++) {
473
/* Swap rows if we ave a zero i,i element. If we can't swap, then the
474
matrix was not invertible */
476
if (mat[row_start+i] == 0) {
477
for (j = i+1; j < rows && mat[cols*j+i] == 0; j++) ;
478
if (j == rows) return 0;
480
for (k = 0; k < cols; k++) {
481
tmp = mat[row_start+k];
482
mat[row_start+k] = mat[rs2+k];
487
/* Multiply the row by 1/element i,i */
488
tmp = mat[row_start+i];
490
inverse = galois_single_divide(1, tmp, w);
491
for (j = 0; j < cols; j++) {
492
mat[row_start+j] = galois_single_multiply(mat[row_start+j], inverse, w);
496
/* Now for each j>i, add A_ji*Ai to Aj */
498
for (j = i+1; j != cols; j++) {
503
for (x = 0; x < cols; x++) {
504
mat[rs2+x] ^= mat[row_start+x];
509
for (x = 0; x < cols; x++) {
510
mat[rs2+x] ^= galois_single_multiply(tmp, mat[row_start+x], w);
519
/* Converts a list-style version of the erasures into an array of k+m elements
520
where the element = 1 if the index has been erased, and zero otherwise */
522
int *jerasure_erasures_to_erased(int k, int m, int *erasures)
530
erased = talloc(int, td);
531
if (erased == NULL) return NULL;
534
for (i = 0; i < td; i++) erased[i] = 0;
536
for (i = 0; erasures[i] != -1; i++) {
537
if (erased[erasures[i]] == 0) {
538
erased[erasures[i]] = 1;
540
if (t_non_erased < k) {
549
void jerasure_free_schedule(int **schedule)
553
for (i = 0; schedule[i][0] >= 0; i++) free(schedule[i]);
558
void jerasure_free_schedule_cache(int k, int m, int ***cache)
563
fprintf(stderr, "jerasure_free_schedule_cache(): m must equal 2\n");
567
for (e1 = 0; e1 < k+m; e1++) {
568
for (e2 = 0; e2 < e1; e2++) {
569
jerasure_free_schedule(cache[e1*(k+m)+e2]);
571
jerasure_free_schedule(cache[e1*(k+m)+e1]);
576
void jerasure_matrix_dotprod(int k, int w, int *matrix_row,
577
int *src_ids, int dest_id,
578
char **data_ptrs, char **coding_ptrs, int size)
584
if (w != 1 && w != 8 && w != 16 && w != 32) {
585
fprintf(stderr, "ERROR: jerasure_matrix_dotprod() called and w is not 1, 8, 16 or 32\n");
591
dptr = (dest_id < k) ? data_ptrs[dest_id] : coding_ptrs[dest_id-k];
593
/* First copy or xor any data that does not need to be multiplied by a factor */
595
for (i = 0; i < k; i++) {
596
if (matrix_row[i] == 1) {
597
if (src_ids == NULL) {
599
} else if (src_ids[i] < k) {
600
sptr = data_ptrs[src_ids[i]];
602
sptr = coding_ptrs[src_ids[i]-k];
605
memcpy(dptr, sptr, size);
606
jerasure_total_memcpy_bytes += size;
609
galois_region_xor(sptr, dptr, dptr, size);
610
jerasure_total_xor_bytes += size;
615
/* Now do the data that needs to be multiplied by a factor */
617
for (i = 0; i < k; i++) {
618
if (matrix_row[i] != 0 && matrix_row[i] != 1) {
619
if (src_ids == NULL) {
621
} else if (src_ids[i] < k) {
622
sptr = data_ptrs[src_ids[i]];
624
sptr = coding_ptrs[src_ids[i]-k];
627
case 8: galois_w08_region_multiply(sptr, matrix_row[i], size, dptr, init); break;
628
case 16: galois_w16_region_multiply(sptr, matrix_row[i], size, dptr, init); break;
629
case 32: galois_w32_region_multiply(sptr, matrix_row[i], size, dptr, init); break;
631
jerasure_total_gf_bytes += size;
638
int jerasure_bitmatrix_decode(int k, int m, int w, int *bitmatrix, int row_k_ones, int *erasures,
639
char **data_ptrs, char **coding_ptrs, int size, int packetsize)
643
int *decoding_matrix;
645
int edd, *tmpids, lastdrive;
647
erased = jerasure_erasures_to_erased(k, m, erasures);
648
if (erased == NULL) return -1;
650
/* See jerasure_matrix_decode for the logic of this routine. This one works just like
651
it, but calls the bitmatrix ops instead */
656
for (i = 0; i < k; i++) {
663
if (row_k_ones != 1 || erased[k]) lastdrive = k;
666
decoding_matrix = NULL;
668
if (edd > 1 || (edd > 0 && (row_k_ones != 1 || erased[k]))) {
670
dm_ids = talloc(int, k);
671
if (dm_ids == NULL) {
676
decoding_matrix = talloc(int, k*k*w*w);
677
if (decoding_matrix == NULL) {
683
if (jerasure_make_decoding_bitmatrix(k, m, w, bitmatrix, erased, decoding_matrix, dm_ids) < 0) {
686
free(decoding_matrix);
691
for (i = 0; edd > 0 && i < lastdrive; i++) {
693
jerasure_bitmatrix_dotprod(k, w, decoding_matrix+i*k*w*w, dm_ids, i, data_ptrs, coding_ptrs, size, packetsize);
699
tmpids = talloc(int, k);
700
for (i = 0; i < k; i++) {
701
tmpids[i] = (i < lastdrive) ? i : i+1;
703
jerasure_bitmatrix_dotprod(k, w, bitmatrix, tmpids, lastdrive, data_ptrs, coding_ptrs, size, packetsize);
707
for (i = 0; i < m; i++) {
709
jerasure_bitmatrix_dotprod(k, w, bitmatrix+i*k*w*w, NULL, k+i, data_ptrs, coding_ptrs, size, packetsize);
714
if (dm_ids != NULL) free(dm_ids);
715
if (decoding_matrix != NULL) free(decoding_matrix);
720
static char **set_up_ptrs_for_scheduled_decoding(int k, int m, int *erasures, char **data_ptrs, char **coding_ptrs)
729
for (i = 0; erasures[i] != -1; i++) {
730
if (erasures[i] < k) ddf++; else cdf++;
733
erased = jerasure_erasures_to_erased(k, m, erasures);
734
if (erased == NULL) return NULL;
736
/* Set up ptrs. It will be as follows:
738
- If data drive i has not failed, then ptrs[i] = data_ptrs[i].
739
- If data drive i has failed, then ptrs[i] = coding_ptrs[j], where j is the
740
lowest unused non-failed coding drive.
741
- Elements k to k+ddf-1 are data_ptrs[] of the failed data drives.
742
- Elements k+ddf to k+ddf+cdf-1 are coding_ptrs[] of the failed data drives.
744
The array row_ids contains the ids of ptrs.
745
The array ind_to_row_ids contains the row_id of drive i.
747
However, we're going to set row_ids and ind_to_row in a different procedure.
750
ptrs = talloc(char *, k+m);
754
for (i = 0; i < k; i++) {
755
if (erased[i] == 0) {
756
ptrs[i] = data_ptrs[i];
758
while (erased[j]) j++;
759
ptrs[i] = coding_ptrs[j-k];
761
ptrs[x] = data_ptrs[i];
765
for (i = k; i < k+m; i++) {
767
ptrs[x] = coding_ptrs[i-k];
775
static int set_up_ids_for_scheduled_decoding(int k, int m, int *erasures, int *row_ids, int *ind_to_row)
783
for (i = 0; erasures[i] != -1; i++) {
784
if (erasures[i] < k) ddf++; else cdf++;
787
erased = jerasure_erasures_to_erased(k, m, erasures);
788
if (erased == NULL) return -1;
790
/* See set_up_ptrs_for_scheduled_decoding for how these are set */
794
for (i = 0; i < k; i++) {
795
if (erased[i] == 0) {
799
while (erased[j]) j++;
808
for (i = k; i < k+m; i++) {
819
static int **jerasure_generate_decoding_schedule(int k, int m, int w, int *bitmatrix, int *erasures, int smart)
821
int i, j, x, drive, y, index, z;
822
int *decoding_matrix, *inverse, *real_decoding_matrix;
830
/* First, figure out the number of data drives that have failed, and the
831
number of coding drives that have failed: ddf and cdf */
835
for (i = 0; erasures[i] != -1; i++) {
836
if (erasures[i] < k) ddf++; else cdf++;
839
row_ids = talloc(int, k+m);
840
ind_to_row = talloc(int, k+m);
842
if (set_up_ids_for_scheduled_decoding(k, m, erasures, row_ids, ind_to_row) < 0) {
848
/* Now, we're going to create one decoding matrix which is going to
849
decode everything with one call. The hope is that the scheduler
850
will do a good job. This matrix has w*e rows, where e is the
851
number of erasures (ddf+cdf) */
853
real_decoding_matrix = talloc(int, k*w*(cdf+ddf)*w);
855
/* First, if any data drives have failed, then initialize the first
856
ddf*w rows of the decoding matrix from the standard decoding
861
decoding_matrix = talloc(int, k*k*w*w);
862
ptr = decoding_matrix;
863
for (i = 0; i < k; i++) {
864
if (row_ids[i] == i) {
865
bzero(ptr, k*w*w*sizeof(int));
866
for (x = 0; x < w; x++) {
867
ptr[x+i*w+x*k*w] = 1;
870
memcpy(ptr, bitmatrix+k*w*w*(row_ids[i]-k), k*w*w*sizeof(int));
874
inverse = talloc(int, k*k*w*w);
875
jerasure_invert_bitmatrix(decoding_matrix, inverse, k*w);
877
/* printf("\nMatrix to invert\n");
878
jerasure_print_bitmatrix(decoding_matrix, k*w, k*w, w);
880
printf("\nInverse\n");
881
jerasure_print_bitmatrix(inverse, k*w, k*w, w);
884
free(decoding_matrix);
885
ptr = real_decoding_matrix;
886
for (i = 0; i < ddf; i++) {
887
memcpy(ptr, inverse+k*w*w*row_ids[k+i], sizeof(int)*k*w*w);
893
/* Next, here comes the hard part. For each coding node that needs
894
to be decoded, you start by putting its rows of the distribution
895
matrix into the decoding matrix. If there were no failed data
896
nodes, then you're done. However, if there have been failed
897
data nodes, then you need to modify the columns that correspond
898
to the data nodes. You do that by first zeroing them. Then
899
whereever there is a one in the distribution matrix, you XOR
900
in the corresponding row from the failed data node's entry in
901
the decoding matrix. The whole process kind of makes my head
905
for (x = 0; x < cdf; x++) {
906
drive = row_ids[x+ddf+k]-k;
907
ptr = real_decoding_matrix + k*w*w*(ddf+x);
908
memcpy(ptr, bitmatrix+drive*k*w*w, sizeof(int)*k*w*w);
910
for (i = 0; i < k; i++) {
911
if (row_ids[i] != i) {
912
for (j = 0; j < w; j++) {
913
bzero(ptr+j*k*w+i*w, sizeof(int)*w);
918
/* There's the yucky part */
921
for (i = 0; i < k; i++) {
922
if (row_ids[i] != i) {
923
b1 = real_decoding_matrix+(ind_to_row[i]-k)*k*w*w;
924
for (j = 0; j < w; j++) {
926
for (y = 0; y < w; y++) {
927
if (bitmatrix[index+j*k*w+i*w+y]) {
928
for (z = 0; z < k*w; z++) {
929
b2[z] = b2[z] ^ b1[z+y*k*w];
939
printf("\n\nReal Decoding Matrix\n\n");
940
jerasure_print_bitmatrix(real_decoding_matrix, (ddf+cdf)*w, k*w, w);
943
schedule = jerasure_smart_bitmatrix_to_schedule(k, ddf+cdf, w, real_decoding_matrix);
945
schedule = jerasure_dumb_bitmatrix_to_schedule(k, ddf+cdf, w, real_decoding_matrix);
949
free(real_decoding_matrix);
953
int jerasure_schedule_decode_lazy(int k, int m, int w, int *bitmatrix, int *erasures,
954
char **data_ptrs, char **coding_ptrs, int size, int packetsize,
961
ptrs = set_up_ptrs_for_scheduled_decoding(k, m, erasures, data_ptrs, coding_ptrs);
962
if (ptrs == NULL) return -1;
964
schedule = jerasure_generate_decoding_schedule(k, m, w, bitmatrix, erasures, smart);
965
if (schedule == NULL) {
970
for (tdone = 0; tdone < size; tdone += packetsize*w) {
971
jerasure_do_scheduled_operations(ptrs, schedule, packetsize);
972
for (i = 0; i < k+m; i++) ptrs[i] += (packetsize*w);
975
jerasure_free_schedule(schedule);
981
int jerasure_schedule_decode_cache(int k, int m, int w, int ***scache, int *erasures,
982
char **data_ptrs, char **coding_ptrs, int size, int packetsize)
989
if (erasures[1] == -1) {
990
index = erasures[0]*(k+m) + erasures[0];
991
} else if (erasures[2] == -1) {
992
index = erasures[0]*(k+m) + erasures[1];
997
schedule = scache[index];
999
ptrs = set_up_ptrs_for_scheduled_decoding(k, m, erasures, data_ptrs, coding_ptrs);
1000
if (ptrs == NULL) return -1;
1003
for (tdone = 0; tdone < size; tdone += packetsize*w) {
1004
jerasure_do_scheduled_operations(ptrs, schedule, packetsize);
1005
for (i = 0; i < k+m; i++) ptrs[i] += (packetsize*w);
1013
/* This only works when m = 2 */
1015
int ***jerasure_generate_schedule_cache(int k, int m, int w, int *bitmatrix, int smart)
1021
/* Ok -- this is yucky, but it's how I'm doing it. You will make an index out
1022
of erasures, which will be e1*(k+m)+(e2). If there is no e2, then e2 = e1.
1023
Isn't that clever and confusing. Sorry.
1025
We're not going to worry about ordering -- in other words, the schedule for
1026
e1,e2 will be the same as e2,e1. They will have the same pointer -- the
1027
schedule will not be duplicated. */
1029
if (m != 2) return NULL;
1031
scache = talloc(int **, (k+m)*(k+m+1));
1032
if (scache == NULL) return NULL;
1034
for (e1 = 0; e1 < k+m; e1++) {
1036
for (e2 = 0; e2 < e1; e2++) {
1039
scache[e1*(k+m)+e2] = jerasure_generate_decoding_schedule(k, m, w, bitmatrix, erasures, smart);
1040
scache[e2*(k+m)+e1] = scache[e1*(k+m)+e2];
1043
scache[e1*(k+m)+e1] = jerasure_generate_decoding_schedule(k, m, w, bitmatrix, erasures, smart);
1049
int jerasure_invert_bitmatrix(int *mat, int *inv, int rows)
1057
for (i = 0; i < rows; i++) {
1058
for (j = 0; j < cols; j++) {
1059
inv[k] = (i == j) ? 1 : 0;
1064
/* First -- convert into upper triangular */
1066
for (i = 0; i < cols; i++) {
1068
/* Swap rows if we have a zero i,i element. If we can't swap, then the
1069
matrix was not invertible */
1071
if ((mat[i*cols+i]) == 0) {
1072
for (j = i+1; j < rows && (mat[j*cols+i]) == 0; j++) ;
1073
if (j == rows) return -1;
1074
for (k = 0; k < cols; k++) {
1075
tmp = mat[i*cols+k]; mat[i*cols+k] = mat[j*cols+k]; mat[j*cols+k] = tmp;
1076
tmp = inv[i*cols+k]; inv[i*cols+k] = inv[j*cols+k]; inv[j*cols+k] = tmp;
1080
/* Now for each j>i, add A_ji*Ai to Aj */
1081
for (j = i+1; j != rows; j++) {
1082
if (mat[j*cols+i] != 0) {
1083
for (k = 0; k < cols; k++) {
1084
mat[j*cols+k] ^= mat[i*cols+k];
1085
inv[j*cols+k] ^= inv[i*cols+k];
1091
/* Now the matrix is upper triangular. Start at the top and multiply down */
1093
for (i = rows-1; i >= 0; i--) {
1094
for (j = 0; j < i; j++) {
1095
if (mat[j*cols+i]) {
1096
for (k = 0; k < cols; k++) {
1097
mat[j*cols+k] ^= mat[i*cols+k];
1098
inv[j*cols+k] ^= inv[i*cols+k];
1106
int jerasure_invertible_bitmatrix(int *mat, int rows)
1113
/* First -- convert into upper triangular */
1115
for (i = 0; i < cols; i++) {
1117
/* Swap rows if we have a zero i,i element. If we can't swap, then the
1118
matrix was not invertible */
1120
if ((mat[i*cols+i]) == 0) {
1121
for (j = i+1; j < rows && (mat[j*cols+i]) == 0; j++) ;
1122
if (j == rows) return 0;
1123
for (k = 0; k < cols; k++) {
1124
tmp = mat[i*cols+k]; mat[i*cols+k] = mat[j*cols+k]; mat[j*cols+k] = tmp;
1128
/* Now for each j>i, add A_ji*Ai to Aj */
1129
for (j = i+1; j != rows; j++) {
1130
if (mat[j*cols+i] != 0) {
1131
for (k = 0; k < cols; k++) {
1132
mat[j*cols+k] ^= mat[i*cols+k];
1141
int *jerasure_matrix_multiply(int *m1, int *m2, int r1, int c1, int r2, int c2, int w)
1143
int *product, i, j, k;
1145
product = (int *) malloc(sizeof(int)*r1*c2);
1146
for (i = 0; i < r1*c2; i++) product[i] = 0;
1148
for (i = 0; i < r1; i++) {
1149
for (j = 0; j < c2; j++) {
1150
for (k = 0; k < r2; k++) {
1151
product[i*c2+j] ^= galois_single_multiply(m1[i*c1+k], m2[k*c2+j], w);
1158
void jerasure_get_stats(double *fill_in)
1160
fill_in[0] = jerasure_total_xor_bytes;
1161
fill_in[1] = jerasure_total_gf_bytes;
1162
fill_in[2] = jerasure_total_memcpy_bytes;
1163
jerasure_total_xor_bytes = 0;
1164
jerasure_total_gf_bytes = 0;
1165
jerasure_total_memcpy_bytes = 0;
1168
void jerasure_do_scheduled_operations(char **ptrs, int **operations, int packetsize)
1174
for (op = 0; operations[op][0] >= 0; op++) {
1175
sptr = ptrs[operations[op][0]] + operations[op][1]*packetsize;
1176
dptr = ptrs[operations[op][2]] + operations[op][3]*packetsize;
1177
if (operations[op][4]) {
1178
/* printf("%d,%d %d,%d\n", operations[op][0],
1182
printf("xor(0x%x, 0x%x -> 0x%x, %d)\n", sptr, dptr, dptr, packetsize); */
1183
galois_region_xor(sptr, dptr, dptr, packetsize);
1184
jerasure_total_xor_bytes += packetsize;
1186
/* printf("memcpy(0x%x <- 0x%x)\n", dptr, sptr); */
1187
memcpy(dptr, sptr, packetsize);
1188
jerasure_total_memcpy_bytes += packetsize;
1193
void jerasure_schedule_encode(int k, int m, int w, int **schedule,
1194
char **data_ptrs, char **coding_ptrs, int size, int packetsize)
1199
ptr_copy = talloc(char *, (k+m));
1200
for (i = 0; i < k; i++) ptr_copy[i] = data_ptrs[i];
1201
for (i = 0; i < m; i++) ptr_copy[i+k] = coding_ptrs[i];
1202
for (tdone = 0; tdone < size; tdone += packetsize*w) {
1203
jerasure_do_scheduled_operations(ptr_copy, schedule, packetsize);
1204
for (i = 0; i < k+m; i++) ptr_copy[i] += (packetsize*w);
1209
int **jerasure_dumb_bitmatrix_to_schedule(int k, int m, int w, int *bitmatrix)
1213
int index, optodo, i, j;
1215
operations = talloc(int *, k*m*w*w+1);
1219
for (i = 0; i < m*w; i++) {
1221
for (j = 0; j < k*w; j++) {
1222
if (bitmatrix[index]) {
1223
operations[op] = talloc(int, 5);
1224
operations[op][4] = optodo;
1225
operations[op][0] = j/w;
1226
operations[op][1] = j%w;
1227
operations[op][2] = k+i/w;
1228
operations[op][3] = i%w;
1236
operations[op] = talloc(int, 5);
1237
operations[op][0] = -1;
1241
int **jerasure_smart_bitmatrix_to_schedule(int k, int m, int w, int *bitmatrix)
1246
int *diff, *from, *b1, *flink, *blink;
1249
int bestrow = 0, bestdiff, top;
1251
/* printf("Scheduling:\n\n");
1252
jerasure_print_bitmatrix(bitmatrix, m*w, k*w, w); */
1254
operations = talloc(int *, k*m*w*w+1);
1257
diff = talloc(int, m*w);
1258
from = talloc(int, m*w);
1259
flink = talloc(int, m*w);
1260
blink = talloc(int, m*w);
1266
for (i = 0; i < m*w; i++) {
1268
for (j = 0; j < k*w; j++) {
1276
if (no < bestdiff) {
1286
/* printf("Doing row %d - %d from %d\n", row, diff[row], from[row]); */
1288
if (blink[row] == -1) {
1290
if (top != -1) blink[top] = -1;
1292
flink[blink[row]] = flink[row];
1293
if (flink[row] != -1) {
1294
blink[flink[row]] = blink[row];
1298
ptr = bitmatrix + row*k*w;
1299
if (from[row] == -1) {
1301
for (j = 0; j < k*w; j++) {
1303
operations[op] = talloc(int, 5);
1304
operations[op][4] = optodo;
1305
operations[op][0] = j/w;
1306
operations[op][1] = j%w;
1307
operations[op][2] = k+row/w;
1308
operations[op][3] = row%w;
1314
operations[op] = talloc(int, 5);
1315
operations[op][4] = 0;
1316
operations[op][0] = k+from[row]/w;
1317
operations[op][1] = from[row]%w;
1318
operations[op][2] = k+row/w;
1319
operations[op][3] = row%w;
1321
b1 = bitmatrix + from[row]*k*w;
1322
for (j = 0; j < k*w; j++) {
1323
if (ptr[j] ^ b1[j]) {
1324
operations[op] = talloc(int, 5);
1325
operations[op][4] = 1;
1326
operations[op][0] = j/w;
1327
operations[op][1] = j%w;
1328
operations[op][2] = k+row/w;
1329
operations[op][3] = row%w;
1336
for (i = top; i != -1; i = flink[i]) {
1338
b1 = bitmatrix + i*k*w;
1339
for (j = 0; j < k*w; j++) no += (ptr[j] ^ b1[j]);
1344
if (diff[i] < bestdiff) {
1351
operations[op] = talloc(int, 5);
1352
operations[op][0] = -1;
1361
void jerasure_bitmatrix_encode(int k, int m, int w, int *bitmatrix,
1362
char **data_ptrs, char **coding_ptrs, int size, int packetsize)
1366
if (packetsize%sizeof(long) != 0) {
1367
fprintf(stderr, "jerasure_bitmatrix_encode - packetsize(%d) %c sizeof(long) != 0\n", packetsize, '%');
1370
if (size%(packetsize*w) != 0) {
1371
fprintf(stderr, "jerasure_bitmatrix_encode - size(%d) %c (packetsize(%d)*w(%d))) != 0\n",
1372
size, '%', packetsize, w);
1376
for (i = 0; i < m; i++) {
1377
jerasure_bitmatrix_dotprod(k, w, bitmatrix+i*k*w*w, NULL, k+i, data_ptrs, coding_ptrs, size, packetsize);
added
removed
src/erasure-code/jerasure/jerasure.c
