zfec 源码分析

zfec 是Tahoe(一个基于云的文件系统)中纠删码的一个模块,其中的fec 模块是核心部分,实现了基于范德蒙矩阵的系统纠删码,对外提供以下接口:

  1. fec_t :这是一个结构,通过fec_new() 返回可以得到,不用自己初始化。fec->k 是数据块的数目,fec->n 是所有块总数(数据块+校验块)
  2. fec_new():初始化,生成fec_t 结构,并给定了k,m(需要重建数据块数,总数据块数)
  3. fec_free():释放初始化的空间
  4. fec_encode():编码 (具体参数如下)
  5. fec_decode():解码 (具体参数如下)

 

fec_t

   1: typedef struct {    

   2:     unsigned long magic;    

   3:     unsigned short k, n;     /* parameters of the code */    

   4:     gf* enc_matrix;

   5: } fec_t;

 

fec_new()

   1: fec_t* fec_new(

   2:     unsigned short k,     /*原数据块个数,对应编码理论中k */

   3:     unsigned short m      /*编码后所有数据块个数,对应编码理论中n */

   4: )

 

fec_free()

   1: void fec_free(

   2: fec_t* p

   3: )

 

fec_encode()

   1: void fec_encode(

   2:     const fec_t* code, /*fec_t 结构的指针*/

   3:     const gf*restrict const*restrict const src, /*原始数据指针*/

   4:     gf*restrict const*restrict const fecs, /*fec 生成的校验数据的指针*/

   5:     const unsigned*restrict const block_nums, 

   6:     /*记录冗余数据块在整个数据(包含原始数据)中的索引数组*/

   7:     size_t num_block_nums, /*冗余数组的大小*/

   8:     size_t sz /*每个数据块的大小*/

   9: ) 

  1. src[0] 到src[ECC_K-1] 是指向第0 个到第ECC_K-1 个数据块的指针;(分别指向D1-D5)
  2. fecs[0] 到fecs[ECC_C-1] 是指向第0 个到第ECC_C-1 个校验块的指针;(需要预先分配好校验块的空间,分别指向C1-C3)
  3. blocks_nums 是校验块索引数组的指针,blocks_nums 指向的空间也应该提前分配好,是一个ECC_C 大小的空间,保存从ECC_K,…,ECC_N-1。(对应下图,索引数组保存5、6、7 )
  4. num_block_nums 是上面blocks_nums 指向空间的大小,也就是校验块个数:ECC_C = ECC_N – ECC_K。

5

fec_decode()

   1: void fec_decode( 

   2:     const fec_t* code, /*fec_t 结构的指针*/

   3:     const gf*restrict const*restrict const inpkts, 

   4:     /*用来恢复丢失数据的数据数组,其内的指针必须按编码前的顺序升序存放,如果丢包则拿冗余块补入,

   5:       其中冗余块必须放在丢失数据块的位置。指针所指数组大小为k*/

   6:     gf*restrict const*restrict const outpkts, 

   7:     /*存放找回的数据块,所指数组大小为丢失块数量*/

   8:     const unsigned*restrict const index, 

   9:     /*传入的数据包的序号,数组大小为k,对应inpkts中每个数据块在全部数据块中的索引*/

  10:     size_t sz 

  11: ) 

  1. inpkts 是恢复数据块和校验块指针,需要注意的是数据块应该按照其原来的位置放置,缺少数据块的部分用校验块填充,不可以按照数据块校验块顺序放置,否则会解码错误
  2. outpkts 是恢复出来的数据块的指针,也要预先分配空间
  3. index 是用于恢复的数据块与校验块对应在inpkts 里面的索引。

如下图D1/D4/C2 块发生损坏,那么重建的数据块由D2/D3/D5/C1/C3。那么inpkts 指针应该有这样关系:

inpkts->C1(校验块的位置只需和后面index 索引对齐即可)

inpkts+1->D2 (数据块应该保持其原来位置)

inpkts+2->D3(数据块应该保持其原来位置)

inpkts+3->C3(校验块的位置只需和后面index 索引对齐即可)

inpkts+4->D5(数据块应该保持其原来位置)

那么对应index 指向的数组应该为[5,1,2,7,4] ,对应的也就是C1/D2/D3/C3/D5 在初始位置的索引。

 

6

写自己程序的需要将fec.c 编译为fec.o ,再和自己的测试程序一起编译链接生成执行文件,fec 中使用了C99 的语法,需要gcc test.c libfec.o –o out.a –std=c99 生成执行程序out.a 。

下面是encode 和decode 一段简单测试,对指定字符串进行编码解码:

   1: #include <stdlib.h>

   2: #include <stdio.h>

   3: #include <sys/fcntl.h>

   4: #include <sys/stat.h>

   5: #include <unistd.h>

   6: #include "fec.h"

   7:  

   8: #define ECC_K 4

   9: #define ECC_N 8

  10: #define ECC_C (ECC_N - ECC_K)

  11:  

  12: #define BLK_SZ (48/ECC_K)

  13:  

  14: int main(int argv, char *argc[]){

  15:     fec_t *code;   

  16:     char data[] = "0123456789qwertyuiopasdfghjklzxcvbnm-=[];',./`!%";

  17:     char cdata[49] = {0};

  18:     char *src[ECC_K];

  19:     unsigned blocks[ECC_C];

  20:     char *fecs[ECC_C];

  21:     int i;

  22:     unsigned index[ECC_K]={4,5,6,7};

  23:     char *in_recovery[ECC_K];

  24:     char *out_recovery[ECC_K];

  25:     char buf_recovery[ECC_K*BLK_SZ+1];

  26:  

  27:     for(i = 0; i < ECC_K; i++)

  28:         src[i] = data + i*BLK_SZ;

  29:     for(i = 0; i < ECC_C; i++){

  30:         blocks[i] = ECC_K + i;

  31:         fecs[i] = cdata + i*BLK_SZ;

  32:     }

  33:  

  34:     code = fec_new(ECC_K, ECC_N);

  35:     printf("src:\t%s\n",*src);

  36:     printf("cdata:\t%s\n",*cdata);

  37:     printf("fecs:\t%s\n",*fecs);

  38:     printf("blocks:\t%c\n",*blocks);

  39:     printf("ECC_C/BLK_SZ:\t%d / %d\n",ECC_C,BLK_SZ);

  40:     fec_encode(code, src, fecs, blocks, ECC_C, BLK_SZ);

  41:     printf("========================\n");

  42:     for(i = 0 ; i < ECC_K ; i++){

  43:         in_recovery[i] = fecs[i];

  44:         out_recovery[i] = buf_recovery + i*BLK_SZ;

  45:     }

  46:     fec_decode(code, in_recovery, out_recovery, index, BLK_SZ);

  47:     buf_recovery[ECC_K*BLK_SZ] = '\0';

  48:     printf("Recovery:\t%s\n",buf_recovery);

  49:  

  50:     index[0] = 6;

  51:     index[1] = 1;

  52:     index[2] = 2;

  53:     index[3] = 7;

  54:     in_recovery[0] = data + 1*BLK_SZ;

  55:     in_recovery[1] = fecs[2];

  56:     in_recovery[2] = fecs[3];

  57:     in_recovery[3] = data + 2*BLK_SZ;

  58:     for(i = 0 ; i < ECC_K ; i++){

  59:         out_recovery[i] = buf_recovery + i*BLK_SZ;

  60:     }

  61:     fec_decode(code, in_recovery, out_recovery, index, BLK_SZ);

  62:     buf_recovery[ECC_K*BLK_SZ] = '\0';

  63:     printf("Recovery:\t%s\n",buf_recovery);

  64: }

 

下面是一个[4,8] 编码速度的测试,选择合适大小的缓存(数据块大小也随之改变)很重要:

speed

测试程序:

   1: #include <stdlib.h>

   2: #include <stdio.h>

   3: #include <sys/fcntl.h>

   4: #include <sys/stat.h>

   5: #include <unistd.h>

   6: #include <sys/time.h>

   7: #include "fec.h"

   8:  

   9: #define DATASIZE 1024*1024*512

  10: #define DATASIZEM (DATASIZE/(1024*1024))

  11: #define BUFSIZE 1024*4

  12: #define TIMES (DATASIZE/BUFSIZE)

  13:  

  14: #define ECC_K 4

  15: #define ECC_N 8

  16: #define ECC_C (ECC_N - ECC_K)

  17:  

  18: #define BLK_SZ (BUFSIZE/ECC_K)

  19:  

  20: double dt(struct timeval end , struct timeval start){

  21:     double tm;

  22:     tm = ((end.tv_sec-start.tv_sec)*1000.0)+(end.tv_usec-start.tv_usec)/1000.0;

  23:     return tm;

  24: }

  25:  

  26:  

  27: int main(int argv, char *argc[]){

  28:     fec_t *code;   

  29:     char *inbuf;

  30:     char *outbuf;

  31:     char *src[ECC_K];

  32:     char *fecs[ECC_C];

  33:     unsigned blocks[ECC_K];

  34:     int i;

  35:     int j=0;

  36:     double delta;

  37:     struct timeval start,end;

  38:  

  39:     code = fec_new(ECC_K, ECC_N);

  40:     

  41:     printf("===== START TO COUNT =====\n");

  42:     printf("k/n:\t%d\t%d\n" , ECC_K , ECC_N);

  43:     printf("Data/buf = %d MB\t%d KB\n" , DATASIZEM , BUFSIZE/1024);

  44:     gettimeofday(&start , NULL);

  45:     while( j < TIMES ){

  46:         inbuf = (char *)malloc(BUFSIZE*sizeof(char));

  47:         outbuf = (char *)malloc(BUFSIZE*sizeof(char));

  48:         for(i = 0; i < ECC_K; i++){

  49:             src[i] = inbuf + i*BLK_SZ;

  50:             blocks[i] = ECC_K + i;

  51:             fecs[i] = outbuf + i*BLK_SZ;

  52:         }

  53:         fec_encode(code , src , fecs , blocks , ECC_C , BLK_SZ);

  54:         j++;

  55:         free(inbuf);

  56:         free(outbuf);

  57:     }

  58:     gettimeofday(&end,NULL);

  59:     delta=dt(end,start)/1000;

  60:     printf("Time:\t%lf s\t\tSpeed:\t%3.1lf MB/S\t\n",delta,DATASIZEM/delta);

 

 

程序中在对求余使用了改进的modnn () 方法,在注释中是这样解释的:

/*
* modnn(x) computes x % GF_SIZE, where GF_SIZE is 2**GF_BITS – 1,
* without a slow divide.
*/

该方法没有使用常规的除法,从而加速了求余,但估计现代处理器中对求余上进行了硬件上的优化,所有在下面的测试中并没有得到更快的速度,normal mod 使用% 进行求余,fast mod 使用modnn() 方法求余。将这个方法进行了修改再次进行了上面编码速度的测试,发现速度没有改变,可见这里的求余并不是计算的瓶颈。

  • 0:     normal mod
    Time:    2.242347 s       
    1:     fast mod
    Time:    5.798104 s       
    2:     normal function mod
    Time:    3.876389 s       
    3:     fast function mod
    Time:    6.808311 s   

 

   1: #include <stdlib.h>

   2: #include <stdio.h>

   3: #include <sys/time.h>

   4:  

   5: double dt(struct timeval end , struct timeval start){

   6:         double tm;

   7:             tm = ((end.tv_sec-start.tv_sec)*1000.0)+(end.tv_usec-start.tv_usec)/1000.0;

   8:                 return tm;

   9: }

  10:  

  11: int modnn(int x) {

  12:     while (x >= 255) {

  13:         x -= 255;

  14:         x = (x >> 8) + (x & 255);

  15:     }

  16:     return x;

  17: }

  18:  

  19: int moddd(int x){

  20:     x = x % 255;

  21:     return x;

  22: }

  23:  

  24: int main(void){

  25:     int i,j;

  26:     int x=65535;

  27:     double delta;

  28:     struct timeval start,end;

  29:  

  30:     printf(" 0:\t normal mod \n");

  31:     gettimeofday(&start , NULL);

  32:     for(i = 0 ; i < 1000 ; i++)

  33:         for(x = 65535 ; x < 655350 ; x++)

  34:             j = x % 255;

  35:     gettimeofday(&end,NULL);

  36:     delta=dt(end,start)/1000;

  37:     printf("Time:\t%lf s\t\t\n",delta);

  38:  

  39:     printf(" 1:\t fast mod \n");

  40:     gettimeofday(&start , NULL);

  41:     for(i = 0 ; i < 1000 ; i++)

  42:         for(x = 65535 ; x < 655350 ; x++){

  43:             j = x;

  44:             while (j >= 255) {

  45:                 j -= 255;

  46:                 j = (j >> 8) + (j & 255);

  47:             }

  48:         }

  49:     gettimeofday(&end,NULL);

  50:     delta=dt(end,start)/1000;

  51:     printf("Time:\t%lf s\t\t\n",delta);

  52:     

  53:     gettimeofday(&start , NULL);

  54:     printf(" 2:\t normal function mod \n");

  55:     for(i = 0 ; i < 1000 ; i++)

  56:         for(x = 65535 ; x < 655350 ; x++)

  57:             j = moddd(x);

  58:     gettimeofday(&end,NULL);

  59:     delta=dt(end,start)/1000;

  60:     printf("Time:\t%lf s\t\t\n",delta);

  61:     

  62:     gettimeofday(&start , NULL);

  63:     printf(" 3:\t fast function mod \n");

  64:     for(i = 0 ; i < 1000 ; i++)

  65:         for(x = 65535 ; x < 655350 ; x++)

  66:             j = modnn(x);

  67:     gettimeofday(&end,NULL);

  68:     delta=dt(end,start)/1000;

  69:     printf("Time:\t%lf s\t\t\n",delta);

  70:     return(1);

  71: }

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据