带你写一个Linux 下的打包软件 Tar，


相信你对 linux 的 .tar.gz 有点熟悉，这就是先 tar 打包(.tar 后缀)，再对此 tar 文件用 gzip 压缩(.tar.gz)的后缀名。

值得注意的是， tar 不是压缩软件，它只做把一堆文件/文件夹打包到一个文件(tar 文件)里的事情，而文件联系，文件权限，相对的路径等都会给你保存好。

一开始设计是 tar 跟 gzip 只做一件事情，各司其事，后来发现太麻烦了，于是就把压缩功能整合到 tar 里了。

  1. - Create a gzipped archive: 
  2.     tar czf target.tar.gz file1 file2 file3 

最近学习 OS 时写了一个类似 tar 的项目，那么今天就趁热打铁简单说一下如何写一个打包软件，这个软件会将重复的文件内容通过 md5 比较，复用旧的内容。

基本单位 block

block 可以理解为文件系统的最小单位，分别有以下类型：

  • directory block，文件夹 block，存储文件夹 meta 信息;
  • file block，文件 block，存储文件 meta 信息;
  • data block，只用来存文件内容;

Directory block，注意的是 entry 里要有 fileindex 来存储重复文件的 name 的下标。

同时，给 项目一个 root dir。

  1. typedef struct { 
  2.     char        name[SIFS_MAX_NAME_LENGTH]; // name of the directory 
  3.     time_t        modtime;    // time last modified <- time() 
  4.  
  5.     uint32_t        nentries;// 文件夹内的文件/文件夹数量 
  6.     struct { 
  7.         SIFS_BLOCKID    blockID;    // subdirectory 或者 file 的 blockID 
  8.         uint32_t    fileindex;    // 重复文件的不同名字 
  9.     } entries[SIFS_MAX_ENTRIES]; 
  10. } SIFS_DIRBLOCK; 

文件 Block，length 就是有多少 bytes 的文件内容，之后用来算有多少个 data block，firstblockID 记录第一个数据 block 的 id，nfiles 记录有多少重复内容的文件数量了，filenames 就是重复此文件 block 的文件内容的文件名字。

  1. typedef struct { 
  2.     time_t        modtime;    // time first file added <- time() 
  3.     size_t        length;        // length of files' contents in bytes 
  4.  
  5.     unsigned char    md5[MD5_BYTELEN];//the MD5 cryptographic digest (a summary) of the files' contents 
  6.     SIFS_BLOCKID    firstblockID;// the block number (blockID) of the files' first data-block 
  7.  
  8.     uint32_t        nfiles;        // n files with identical contents 
  9.     char        filenames[SIFS_MAX_ENTRIES][SIFS_MAX_NAME_LENGTH];// an array of each same file's name and its modification time. 
  10. } SIFS_FILEBLOCK; 

bitmaps数组，记录了每个 block 的类型，有：文件、文件夹以及data block 三种类型。

通用函数

就让大家看看关键函数好了：

读 tar 后的文件的 meta 头，记录了 block 的大小( blocksize) 以及多少个 blocks。

  1. void read_vol_header(FILE *vol, SIFS_VOLUME_HEADER *header) { 
  2.     fread(header, sizeof(SIFS_VOLUME_HEADER), 1, vol); 
  3.     printf("header->blocksize %zu, header->nblocks %u\n", header->blocksize , header->nblocks); 
  4. } 

bitmap，每次操作 tar 文件都要读的。

  1. void read_bitmap(FILE *vol, SIFS_BIT *bitmap, int nblocks) { 
  2.     int size = nblocks * sizeof(SIFS_BIT); 
  3.     fread(bitmap, size, 1, vol); 
  4. } 

root_block 同理，读和写啥东西都要从 root block、root dir 出发。

  1. void read_root_block(FILE *vol, SIFS_DIRBLOCK *dirblock){ 
  2.     fread(dirblock, sizeof(SIFS_DIRBLOCK), 1, vol); 
  3.     printf("read_root_block finish, dirblock.name: %s, dirblock.entrieds: %d, dirblock.modtime %ld\n", dirblock->name, dirblock->nentries,dirblock->modtime); 
  4. } 

路径嘛，你懂的，./sifs_put volumn ~/res.txt /dirB/subdirB/subsubdir/newfileB，要读的内容可以靠 read 函数解决，但是写到 tar 文件里的就要手动解析递归查路径了。

  1. void read_route_names(char* pathname, char** route_names, int *route_cnt) { 
  2.     char *dir; 
  3.     char *pathname_to_split = copyStr(pathname); 
  4.     strcpy(pathname_to_split, pathname); 
  5.     while ((dir = strsep(&pathname_to_split, "/")) != NULL) { 
  6.         route_names[*route_cnt] = copyStr(dir); 
  7.         (*route_cnt)++; 
  8.     } 
  9. } 

以上几乎是 mkdir，rmdir，writefile，readfile，putfile 等等操作都要做的。

实现

然后，应该举一个 readfile 的例子就可以做代表了。

  1. int recursive_dirinfo(SIFS_DIRBLOCK *cur_dir_block, char **route_names, int route_name_p, int route_cnt); 

实现：

  1. int recursive_dirinfo(SIFS_DIRBLOCK *cur_dir_block, char **route_names, int route_name_p, int route_cnt) { 
  2.     for(int i=0; i<cur_dir_block->nentries ; i++) { 
  3.         int blockid = cur_dir_block->entries[i].blockID; 
  4.         if(bitmap[blockid]==SIFS_DIR) { 
  5.             SIFS_DIRBLOCK dirblock; 
  6.             int start = sizeof(SIFS_VOLUME_HEADER) + header.nblocks*sizeof(SIFS_BIT); 
  7.             read_dir_block(vol, &dirblock, blockid * blocksize, start); 
  8.             if(strcmp(dirblock.name, route_names[route_name_p]) == 0) { 
  9.                 if(route_name_p+2 == route_cnt) { 
  10.                     return do_read_file(cur_dir_block, route_names[route_name_p+1], blockid); 
  11.                 } 
  12.                 return recursive_dirinfo(&dirblock, route_names, route_name_p+1, route_cnt); 
  13.             } 
  14.         } 
  15.     } 
  16.     return 1; 
  17. } 

以``./sifs_put volumn ~/res.txt /dirB/subdirB/subsubdir/newfileB 为例子，如果递归找到 subsubdir`这个文件夹 block，进行相应操作：

  • 写文件就往 bitmap 一直找没有用过的 block，够写文件就写进去，文件夹更新一下信息。
  • 读文件就是根据此文件夹 block，找里面的 newfileB
  1. int do_read_file(SIFS_DIRBLOCK *parent_dir, char *filename,  int parent_dir_block) { 
  2.     printf("do_find_file_info, filename %s\n", filename); 
  3.     for(int i=1; i<header.nblocks ; i++) { 
  4.         SIFS_FILEBLOCK fileblock; 
  5.         if(bitmap[i]==SIFS_FILE) { 
  6.             int start = sizeof(SIFS_VOLUME_HEADER) + header.nblocks*sizeof(SIFS_BIT); 
  7.             read_file_block(vol, &fileblock, i * blocksize, start); 
  8.             *nbytes = fileblock.length; 
  9.             int need_data_blocks = *nbytes / header.blocksize; 
  10.             if(strcmp(fileblock.filenames[0],  filename) == 0) { 
  11.                 for(int d_block_id = fileblock.firstblockID; d_block_id - i -1 < need_data_blocks; d_block_id++) { 
  12.                     read_data_block(vol, (char*)(*data)+(d_block_id - i -1), blocksize, d_block_id * header.blocksize, start); 
  13.                 } 
  14.                 return 0; 
  15.             } 
  16.  
  17.         } 
  18.     } 
  19.     return 1; 
  20. } 

而真实的 tar 自然更复杂，还要记录用户权限、用户、group文件等等：

  1. struct posix_header 
  2. {                       /* byte offset */ 
  3.   char name[100];       /*   0 */   文件名 
  4.   char mode[8];         /* 100 */   用户权限 
  5.   char uid[8];          /* 108 */   user id 
  6.   char gid[8];          /* 116 */   group id 
  7.   char size[12];        /* 124 */   文件大小 
  8.   char mtime[12];       /* 136 */   修改时间 
  9.   char chksum[8];       /* 148 */   校验值 
  10.   char typeflag;        /* 156 */   文件类型标志 
  11.   char linkname[100];   /* 157 */   符号链接指向 
  12.   char magic[6];        /* 257 */    
  13.   char version[2];      /* 263 */ 
  14.   char uname[32];       /* 265 */   user name 
  15.   char gname[32];       /* 297 */   group name 
  16.   char devmajor[8];     /* 329 */   设备文件 major 
  17.   char devminor[8];     /* 337 */   设备文件 minor 
  18.   char prefix[155];     /* 345 */ 
  19.                         /* 500 */ 
  20. }; 
  21.  
  22. 文件类型标志定义，包含了所有 Unix 系统中的文件类型 
  23.  
  24. #define REGTYPE  '0'            /* regular file */ 
  25. #define LNKTYPE  '1'            /* link */ 
  26. #define SYMTYPE  '2'            /* reserved */ 
  27. #define CHRTYPE  '3'            /* character special */ 
  28. #define BLKTYPE  '4'            /* block special */ 
  29. #define DIRTYPE  '5'            /* directory */ 
  30. #define FIFOTYPE '6'            /* FIFO special */ 
  31. #define CONTTYPE '7'            /* reserved */ 

概览如此，写起来其实有点烦 - = -，有兴趣的读者可以写写。

相关内容