]>
git.proxmox.com Git - ceph.git/blob - ceph/src/erasure-code/jerasure/jerasure/Examples/cauchy_02.c
2 * Copyright (c) 2014, James S. Plank and Kevin Greenan
5 * Jerasure - A C/C++ Library for a Variety of Reed-Solomon and RAID-6 Erasure
8 * Revision 2.0: Galois Field backend now links to GF-Complete
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
14 * - Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
17 * - Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in
19 * the documentation and/or other materials provided with the
22 * - Neither the name of the University of Tennessee nor the names of its
23 * contributors may be used to endorse or promote products derived
24 * from this software without specific prior written permission.
26 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
27 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
28 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
29 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
30 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
31 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
32 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
33 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
34 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
35 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
36 * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
37 * POSSIBILITY OF SUCH DAMAGE.
40 /* Jerasure's authors:
42 Revision 2.x - 2014: James S. Plank and Kevin M. Greenan
43 Revision 1.2 - 2008: James S. Plank, Scott Simmerman and Catherine D. Schuman.
44 Revision 1.0 - 2007: James S. Plank
55 #define talloc(type, num) (type *) malloc(sizeof(type)*(num))
59 fprintf(stderr
, "usage: cauchy_02 k m w seed - CRS coding example using Bloemer's original matrix.\n");
60 fprintf(stderr
, " \n");
61 fprintf(stderr
, "k+m must be <= 2^w\n");
62 fprintf(stderr
, "This sets up a generator matrix (G^T) in GF(2^w) whose last m rows are\n");
63 fprintf(stderr
, "created from a Cauchy matrix, using the original definition from [Bloemer95].\n");
64 fprintf(stderr
, "It converts this matrix to a bitmatrix, and then it encodes w packets from\n");
65 fprintf(stderr
, "each of k disks (simulated) onto w packets on each of m disks. Packets are \n");
66 fprintf(stderr
, "simply longs. Then, it deletes m random disks, and decodes. \n");
67 fprintf(stderr
, "\n");
68 fprintf(stderr
, "The encoding and decoding are done twice, first, with jerasure_bitmatrix_encode()\n");
69 fprintf(stderr
, "and jerasure_bitmatrix_decode(), and second using 'smart' scheduling with\n");
70 fprintf(stderr
, "jerasure_schedule_encode() and jerasure_schedule_decode_lazy().\n");
72 fprintf(stderr
, "\n");
73 fprintf(stderr
, "This demonstrates: cauchy_original_coding_matrix()\n");
74 fprintf(stderr
, " jerasure_bitmatrix_encode()\n");
75 fprintf(stderr
, " jerasure_bitmatrix_decode()\n");
76 fprintf(stderr
, " cauchy_n_ones()\n");
77 fprintf(stderr
, " jerasure_smart_bitmatrix_to_schedule()\n");
78 fprintf(stderr
, " jerasure_schedule_encode()\n");
79 fprintf(stderr
, " jerasure_schedule_decode_lazy()\n");
80 fprintf(stderr
, " jerasure_print_matrix()\n");
81 fprintf(stderr
, " jerasure_print_bitmatrix()\n");
82 fprintf(stderr
, " jerasure_get_stats()\n");
83 if (s
!= NULL
) fprintf(stderr
, "%s\n", s
);
87 static print_array(char **ptrs
, int ndevices
, int size
, int packetsize
, char *label
)
92 printf("<center><table border=3 cellpadding=3><tr><td></td>\n");
94 for (i
= 0; i
< ndevices
; i
++) printf("<td align=center>%s%x</td>\n", label
, i
);
96 printf("<td align=right><pre>");
97 for (j
= 0; j
< size
/packetsize
; j
++) printf("Packet %d\n", j
);
98 printf("</pre></td>\n");
99 for (i
= 0; i
< ndevices
; i
++) {
101 up
= (unsigned char *) ptrs
[i
];
102 for (j
= 0; j
< size
/packetsize
; j
++) {
103 for (x
= 0; x
< packetsize
; x
++) {
104 if (x
> 0 && x
%4 == 0) printf(" ");
105 printf("%02x", up
[j
*packetsize
+x
]);
111 printf("</tr></table></center>\n");
114 int main(int argc
, char **argv
)
117 int *matrix
, *bitmatrix
, **schedule
;
118 char **data
, **coding
, **ptrs
, **dcopy
, **ccopy
;
120 int *erasures
, *erased
;
121 double mstats
[3], sstats
[3];
124 if (argc
!= 5) usage(NULL
);
125 if (sscanf(argv
[1], "%d", &k
) == 0 || k
<= 0) usage("Bad k");
126 if (sscanf(argv
[2], "%d", &m
) == 0 || m
<= 0) usage("Bad m");
127 if (sscanf(argv
[3], "%d", &w
) == 0 || w
<= 0 || w
> 32) usage("Bad w");
128 if (sscanf(argv
[4], "%d", &seed
) == 0) usage("Bad seed");
129 if (w
< 30 && (k
+m
) > (1 << w
)) usage("k + m is too big");
131 matrix
= cauchy_original_coding_matrix(k
, m
, w
);
132 if (matrix
== NULL
) {
133 usage("couldn't make coding matrix");
136 /* Print out header information to the output file. */
138 printf("<TITLE>Jerasure Example Output: cauchy_02 %d %d %d %d</TITLE>\n", k
, m
, w
, seed
);
139 printf("<h2>Jerasure Example Output: cauchy_02 %d %d %d %d</h3>\n", k
, m
, w
, seed
);
142 printf("Parameters:\n");
143 printf("<UL><LI> Number of data disks <i>(k)</i>: %d\n", k
);
144 printf("<LI> Number of coding disks <i>(m)</i>: %d\n", m
);
145 printf("<LI> Word size of the Galois Field: <i>(w)</i>: %d\n", w
);
146 printf("<LI> Seed for the random number generator: %d\n", seed
);
147 printf("<LI> Number of bytes stored per disk: %ld\n", sizeof(long)*w
);
148 printf("<LI> Number of packets stored per disk: %d\n", w
);
149 printf("<LI> Number of bytes per packet: %ld\n", sizeof(long));
152 /* Print out the matrix and the bitmatrix */
154 printf("Here is the matrix, which was created with <b>cauchy_original_coding_matrix()</b>.\n");
155 printf("This is not the best matrix to use, but we include it to show an example\n");
156 printf("of <b>cauchy_original_coding_matrix()</b>. For the best matrix and encoding/decoding\n");
157 printf("methodology, see <b>cauchy_04.</b><p><pre>\n");
159 jerasure_print_matrix(matrix
, m
, k
, w
);
162 bitmatrix
= jerasure_matrix_to_bitmatrix(k
, m
, w
, matrix
);
165 for (i
= 0; i
< k
*m
; i
++) {
166 no
+= cauchy_n_ones(matrix
[i
], w
);
169 printf("The bitmatrix, which has %d one%s:<p><pre>\n", no
, (no
== 1) ? "" : "s");
170 jerasure_print_bitmatrix(bitmatrix
, m
*w
, k
*w
, w
);
175 data
= talloc(char *, k
);
176 dcopy
= talloc(char *, k
);
177 for (i
= 0; i
< k
; i
++) {
178 data
[i
] = talloc(char, sizeof(long)*w
);
179 dcopy
[i
] = talloc(char, sizeof(long)*w
);
180 MOA_Fill_Random_Region(data
[i
], sizeof(long)*w
);
181 memcpy(dcopy
[i
], data
[i
], sizeof(long)*w
);
184 printf("Here are the packets on the data disks:<p>\n");
185 print_array(data
, k
, sizeof(long)*w
, sizeof(long), "D");
187 coding
= talloc(char *, m
);
188 ccopy
= talloc(char *, m
);
189 for (i
= 0; i
< m
; i
++) {
190 coding
[i
] = talloc(char, sizeof(long)*w
);
191 ccopy
[i
] = talloc(char, sizeof(long)*w
);
194 jerasure_bitmatrix_encode(k
, m
, w
, bitmatrix
, data
, coding
, w
*sizeof(long), sizeof(long));
195 jerasure_get_stats(mstats
);
197 schedule
= jerasure_smart_bitmatrix_to_schedule(k
, m
, w
, bitmatrix
);
198 jerasure_schedule_encode(k
, m
, w
, schedule
, data
, ccopy
, w
*sizeof(long), sizeof(long));
199 jerasure_get_stats(sstats
);
201 printf("<p>Encoding with jerasure_bitmatrix_encode() - Bytes XOR'd: %.0lf.<br>\n", mstats
[0]);
202 printf("Encoding with jerasure_schedule_encode() - Bytes XOR'd: %.0lf.<br>\n", sstats
[0]);
204 for (i
= 0; i
< m
; i
++) {
205 if (memcmp(coding
[i
], ccopy
[i
], sizeof(long)*w
) != 0) {
206 printf("Problem: the two encodings don't match on disk C%x\n", i
);
211 printf("Here are the packets on the coding disks.<br>\n");
212 print_array(coding
, m
, sizeof(long)*w
, sizeof(long), "C");
215 erasures
= talloc(int, (m
+1));
216 erased
= talloc(int, (k
+m
));
217 for (i
= 0; i
< m
+k
; i
++) erased
[i
] = 0;
218 for (i
= 0; i
< m
; ) {
219 erasures
[i
] = MOA_Random_W(31, 1)%(k
+m
);
220 if (erased
[erasures
[i
]] == 0) {
221 erased
[erasures
[i
]] = 1;
222 bzero((erasures
[i
] < k
) ? data
[erasures
[i
]] : coding
[erasures
[i
]-k
], sizeof(long)*w
);
227 printf("Erasures on the following devices:");
228 for (i
= 0; erasures
[i
] != -1; i
++) {
229 printf(" %c%x", ((erasures
[i
] < k
) ? 'D' : 'C'), (erasures
[i
] < k
? erasures
[i
] : erasures
[i
]-k
));
231 printf("<br>\nHere is the state of the system:\n<p>\n");
232 print_array(data
, k
, sizeof(long)*w
, sizeof(long), "D");
234 print_array(coding
, m
, sizeof(long)*w
, sizeof(long), "C");
237 jerasure_bitmatrix_decode(k
, m
, w
, bitmatrix
, 0, erasures
, data
, coding
, w
*sizeof(long), sizeof(long));
238 jerasure_get_stats(mstats
);
240 printf("<p>Decoded with jerasure_bitmatrix_decode - Bytes XOR'd: %.0lf.<br>\n", mstats
[0]);
242 for (i
= 0; i
< k
; i
++) if (memcmp(data
[i
], dcopy
[i
], sizeof(long)*w
) != 0) {
243 printf("ERROR: D%x after decoding does not match its state before decoding!<br>\n", i
);
245 for (i
= 0; i
< m
; i
++) if (memcmp(coding
[i
], ccopy
[i
], sizeof(long)*w
) != 0) {
246 printf("ERROR: C%x after decoding does not match its state before decoding!<br>\n", i
);
249 for (i
= 0; erasures
[i
] != -1; i
++) {
250 bzero((erasures
[i
] < k
) ? data
[erasures
[i
]] : coding
[erasures
[i
]-k
], sizeof(long)*w
);
253 jerasure_schedule_decode_lazy(k
, m
, w
, bitmatrix
, erasures
, data
, coding
, w
*sizeof(long), sizeof(long), 1);
254 jerasure_get_stats(sstats
);
256 printf("jerasure_schedule_decode_lazy - Bytes XOR'd: %.0lf.<br>\n", sstats
[0]);
258 for (i
= 0; i
< k
; i
++) if (memcmp(data
[i
], dcopy
[i
], sizeof(long)*w
) != 0) {
259 printf("ERROR: D%x after decoding does not match its state before decoding!<br>\n", i
);
261 for (i
= 0; i
< m
; i
++) if (memcmp(coding
[i
], ccopy
[i
], sizeof(long)*w
) != 0) {
262 printf("ERROR: C%x after decoding does not match its state before decoding!<br>\n", i
);
265 printf("Here is the state of the system:\n<p>\n");
266 print_array(data
, k
, sizeof(long)*w
, sizeof(long), "D");
268 print_array(coding
, m
, sizeof(long)*w
, sizeof(long), "C");