libbt研究笔记-1

转自：http://blog.chinaunix.net/u1/36381/showart_1119891.html
关于libbt
--------------------------------------------------------------------------------
主页：http://sourceforge.net/projects/libbt/

libbt 是一个用C语言开发的BT库，实现在功能不多（没有DHT，没文件选择下载，没磁盘缓冲，没UPnP……），用户界面更是“古老”的CUI。但这些都不是 问题，我要研究的主要是其网络IO模式和一些BT内部的算法（如choke算法，piece选择算法，还有文件如何组织及保存等）

概论
--------------------------------------------------------------------------------
libbt的源码在src目录下，包含文件在include目录下。基本上是一个文件一个模块，下面从总体上来看看各各模块的功能吧。
benc.c         
bitset.c        用于操作比特位串，如BT协议中的btifield
block.c        
btcheck.c       一个小工具，make后成为btcheck可执行文件，具体作用未明。
bterror.c       定义了小量的自定义错误代码和相应的 错误字符串信息
btget.c         主程序，各模块在这个文件中组合起来，make后成为btget可执行文件
btlist.c        另个一个小工具，make后成为btlist可执行文件，具体作用未明。
bts.c          
context.c       这个模块提供了一些全局信息处理的函数，还有修改socket的poll事件通知函数， 最后还有tracker通信的一些函数。
peer.c          BT通信协议的实现模块
random.c        仅仅提供2个函数，randomid(...)用于随机返回一个peerid; rnd(max)函数是随机返回一个不大于max的整数;
segmenter.c     torrent中的数据是piece为单位的，这个模块就是提供相关的piece存取函数。
strbuf.c        内存缓冲模块，实现了一个自动扩展的动态缓冲机制。
stream.c        sokcet的封装模块，除了封装了recv/send外，还实现接收/发送缓冲机制。
types.c        
util.c          一些工具类函数，其中封装了一些内存分配函数(malloc, realloc, free等)


util.c模块
--------------------------------------------------------------------------------
这个模块封装资源分配函数，目的有2点，一是集中在封装函数里检测返回值，如果失败，直接结束进程；二是如果将来要使用内存池，直接修改这几个函数就可以了。

/* malloc, calloc, realloc, free函数的封装函数 */
void *btmalloc( size_t size);
void *btcalloc( size_t nmemb, size_t size);
void *btrealloc( void *buf, size_t size);
void btfree( void *buf);

/* C函数strerror的封装，但同时也自定义了一些错误码(在bterror.h中)，至于两者有没重复还不清楚。*/
char *bts_strerror( int err);

/* fprintf( stderr, "%s: [%d] %s\n", msg, err, bts_strerror(err)); */
void bts_perror( int err, char *msg);

/* 输出输入的信息，并且调用abort()函数，终止进程。 */
int die( char *file, int line, char *msg, int err);

/* 创建文件所需要的目录，因为open()函数不会自动创建不存在的目录。 */
int openPath( char *path, int flags);

/* 用输入的参数打开一个文件 */
int cacheopen( char *path, int flags, int mode);

/* 关闭所有打开的文件 */
void cacheclose( void);

/* 将digest中的每个字节转换成%??形式输出到buf中。 */
void hexencode (const unsigned char *digest, int len, char *buf, int buflen);

/* 将buf中%??形式的数据输入成原始比特位，放到digest中。 */
int hexdecode (unsigned char *digest, int len, const char *buf, int buflen);

总结：封装资源分配函数的做法值得学习，当然前提是你用C作为开发语言。还有值得注意的是在源代码中会看到一些实现跨平台的宏，但我曾经试过在VS2005中编译这个项目但不成功，而且后来查看了源码发现跨平台还没有实现的。



strbuf.c模块
--------------------------------------------------------------------------------
strbuf.c模块比较简单，其中的所有的函数都围绕着一个结构进行。

struct kStringBuffer {
    int bufsize; //缓冲的大小

    int cpos; //已经使用的缓冲大小

    char *buf; //缓冲区地址

};

下面简单地说一说每个函数的用法（英文好的朋友，可以直接看strbuf.h，里面有详细的函数说明）

/* 创建一个kStringBuffer。当参数sb非NULL时，将它初始化并返回它；否则malloc一个新的。*/
kStringBuffer* kStringBuffer_create( kStringBuffer *sb);

/* 释放sb的缓冲，并且将结构中的全部成员置0 */
void kStringBuffer_finit( kStringBuffer *sb);

/* 清空sb中的数据 */
void sbclear( kStringBuffer *sb);

/* 添加字符c到sb的缓冲中 */
int sbputc( kStringBuffer *sb, char c);

/* 添加一个C字符串到sb的缓冲中 */
int sbstrcat( kStringBuffer *sb, char *str);

/* 添加一个长度为len的内存块到sb的缓冲中 */
int sbcat( kStringBuffer *sb, char *str, int len);

/* 删除sb缓冲中的首first_cahr个字符*/
int sbtail( kStringBuffer *sb, int first_char);

/* 在sb的缓冲中查找ch的第一次出现的位置 */
int sbindex( kStringBuffer *sb, int ch);

总结：短小但非常有用的一个模块，socket的接收和发送缓冲就是用它作为基础的。
stream.c模块
--------------------------------------------------------------------------------
这个模块在源文件stream.h中有很好的英语说明了，英文好的朋友可以直接去看。但作为笔记我也把这个模块的分析也记录下来。这个模块封装了socket函数recv/send，并且加入了接收/发送缓冲功能。比较奇怪的是socket描述符的创建和删除并不是在这个模块里。这个模块同样围绕着一个结构进行。

typedef struct kStream {
    int fd; //socket描述符，创建和删除都不在本模块进行。
    int inputready; //作用未明，我搜索源码中所有文件，也没有引用的地方。
    int error; //错误码
    int error_count; //recv()函数返回EAGAIN的次数
    int read_count; //recv了多少个次字
    int write_count; //send了多少个字节
    kStringBuffer ibuf; //recv的缓冲
    kStringBuffer obuf; //send的缓冲
} kStream;

/* 创建一个kStream对象，str为NULL时分配一个新的kStream对象。sd为和本对象关联的socket描述符。 */
kStream* kStream_create( kStream *str, int sd);

/* 消毁一个kStream对象。值的注意的是它的源码
void
kStream_finit( kStream *str) {
    kStringBuffer_finit( &str->ibuf);
    kStringBuffer_finit( &str->obuf);
}
为什么没有free掉自身呢？原因是这个结构只以成员变量存在于别的结构（在peer.h的btPeer结构中）
*/
void kStream_finit( kStream *str);

/* recv()函数的封装函数，同时会更新kStream内的一些成员变量（read_count等） */
int kStream_read( kStream *str, char *buf, int max);

/* send()函数的封装函数，同时会更新kStream内的一些成员变量（write_count等） */
int kStream_write( kStream *str, char *buf, int len);

/* 发送发送缓冲中的数据，返回发送后发送缓冲还有多少个节字未发送。 */
int kStream_flush( kStream* str);

/* 清除发送缓冲中的数据，总是返回0 */
int kStream_clear( kStream* str);

/* 带缓冲功能的发送函数，如果不能一次发送完全部数据就会把未发出的数据放进发送缓冲中。返回发送缓冲中的数据长度，或者出错返回0 */
int kStream_fwrite( kStream *str, char *buf, int len);

/* 接收size节字的数据，如果接收到size个字节的数据就复制到buf中，并且清空接收缓冲。但是当接收的数据长度不足size时不向buf写入数据。成功返回接收了多少个字节，出错返回-1。若要判断出错原因，可以查看kStream.error。*/
int kStream_fread( kStream *str, char *buf, int size) ;

/* 和kStream_fread(...)函数一样，但是无论什么清况也不清空接收缓冲。 */
int kStream_fpeek( kStream *str, char *buf, int size) ;

/* 接收缓冲中的数据长度。 */
int kStream_iqlen( kStream *str);

/* 发送缓冲中的数据长度。 */
int kStream_oqlen( kStream *str);

/*
return str->read_count - str->ibuf.cpos; ??
return str->write_count + str->obuf.cpos; ??
*/
int kStream_in_addr( kStream *str);
int kStream_out_addr( kStream *str);

#endif /* __DR1STREAM__H */




bitset模块
--------------------------------------------------------------------------------
这个模块用来操作一个内存块的每个比特位，用处对应BT协议的bitfield。在这个程序中还有多处用到这个模块来表示其它的信息。如哪个piece在下载，对哪些piece感兴趣，哪些piece已经下载等。

先来看看数据结构

typedef struct kBitSet {
    int nbits; //有多少个比特位
    char *bits; //比特位的缓冲

} kBitSet;

/* 创建一个可以容纳nbits个比特位的kBitSet对象 */
kBitSet* kBitSet_create( kBitSet *set, int nbits) ;

/* 根据orig复制并创建一个kBitSet */
kBitSet* kBitSet_createCopy( kBitSet *set, kBitSet *orig);

/* 销毁一个kBitSet对象 */
void kBitSet_finit( kBitSet *set);

/* 复制len长度的kBitSet对象的缓冲区到bytes */
void kBitSet_readBytes( kBitSet *set, char* bytes, int len) ;

/* 设置kBitSet缓冲中的bit位为1 */
void bs_set( kBitSet *set, int bit) ;

/* 设置kBitSet缓冲指定范围的为1 */
void bs_setRange( kBitSet *set, int start, int endplus1);

/* 设置kBitSet缓冲中的bit位为0 */
void bs_clr( kBitSet *set, int bit) ;

/* kBitSet缓冲中的bit位为0返回0，否则返回1*/
int bs_isSet( kBitSet *set, int bit) ;

/* 返回kBitSet中第一个为0的比特位序号 */
int bs_firstClr( kBitSet *set);

/* 测试kBitSet中的所有比特位是否为1 */
int bs_isFull( kBitSet *set);

/* 测试kBitSet中的所有比特位是否为0 */
int bs_isEmpty( kBitSet *set);

/* 返回kBitSet中比特位为1的数量 */
int bs_countBits( kBitSet *set) ;

/* 随机返回一个存在于peer和intr，但不在req中的piece序号 */
int bs_pickblock( kBitSet *req, kBitSet *peer, kBitSet *intr);
   /*
    * randomly picks a block to get from a peer, without asking for any
    * that have already been requested elsewhere and are listed in 'req'.
    */

/* 返回真，如果存在一个piece它 存在于peer和intr，但不在req中*/
int bs_hasInteresting( kBitSet *req, kBitSet *peer, kBitSet *intr);
   /*
    * returns true iff the peer has at least one block that hasn't
    * already been requested.
    */


segmenter.c模块
--------------------------------------------------------------------------------
BT 的协议把一个torrent任务中的所有文件看只看作为一个巨大的数据块，这个巨大的数据块被分成n个大小相同的piece，每个piece又可以分为n 个slice。数据交换时是以slice为单位的，这个模块的主要作用就是处理这几种关系，并且把下载回来的数据组织成文件。

先来看看这个模块的数据结构：

/* 代表一个torrent任务中的每个文件的信息。torrent包含多少个文件，就有多少个。 */
typedef struct btFile {
    _int64 start; //文件巨大的数据块中的偏移值
    _int64 len; //文件长度
    char *path; //文件名（不包括其保存路径，只包含.torrent中提供的路径）
} btFile;

/* 代表的是一个正在下载的piece */
typedef struct btPartialPiece {
    struct btPartialPiece *next; //链表指针，可以把一串btPartialPiece链在一起
    int piecenumber; //这个结构所代表的piece的序号
    kBitSet filled; //每个kBitSet的比特位代表piece中的一个字节，用来标识这个piece哪里未下载
    int nextbyteReq;        /* next request from here */ //
    int isdone;            /* 0-filling, 1-retry */
    /* 为0时代表正在下载，如果下载完毕后SHA正确，这个结构会从next链表中删除。
    如果出错，这个字段设置为1，但并不从链表删除。当peer_send_request函数检测到这个字段为1时会重新请求该piece */
    char buffer[0];        /* blocksize - allocation trick when creating piece */ //sizeof(buffer)==0
} btPartialPiece;


/* 代表的是一个torrent任务的文件信息.每任务只有一个 */
typedef struct btFileSet {
    _int64 tsize;        /* total size */ //所有文件大小的总和
    _int64 ul;            /* bytes uploaded */ //上传了多少字节 在peer.c==>process_queue进行累加
    _int64 dl;            /* bytes downloaded */ //下载了多少字节 seg_writebuf()进行累加
    _int64 left;        /* bytes left */ //还有多少个字节未下载 seg_writebuf()进行累加
    kBitSet completed;        /* completed blocks */ //已经完成下载的piece的bitfield
    int nfiles; //torrent中有多少个文件
    int blocksize; //piece大小，除了最后一个piece，其它piece的大小都相同
    btFile** file; //文件信息链表
    int npieces; //torrent中有多少个piece
    char *hashes;        /* SHA data */ //SHA校检数据
    btPartialPiece *partial; //未完成下载的piece的链表。
} btFileSet;


/* 输入piece数目，piece大小，sha hash的数据，创建一个btFileSet对象。每个torrent对应一个。 */
btFileSet* btFileSet_create( btFileSet *fs, int npieces, int blocksize, const char *hashbuf) ;

/* 销毁btFileSet对象*/
void btFileSet_destroy( btFileSet *fs);

/* 将一个文件信息添加到btFileSet中，文件信息是.torrent中对应的 */
int btFileSet_addfile( btFileSet *fs, const char *path, _int64 len) ;

/* 输入piece序号，返回相关的btFile文件信息 */
btFile *seg_findFile( btFileSet *fs, int piece);

/* 返回指定piece的长度 */
int seg_piecelen( btFileSet *fs, int piece);

/* finds or allocates the given piece */
/* 在btFileSet的partial链表中查找piecenumber为piece的btPartialPiece并返回。
   若找不到，创建一个piecenumber为piece的btPartialPiece并返回。 */
btPartialPiece *seg_getPiece( btFileSet *fs, int piece);

/* 将参数所标识的数据，写入fs结构中对应文件的对应位置。 */
int seg_writebuf( btFileSet *fs, int piece, int offset, char *buf, int len) ;

/* 从fs中读取参数所标识数据，放到buf中。 */
int seg_readbuf( btFileSet *fs, int piece, int start, char *buf, int len) ;

/* 重新对piece的数据进行SHA校检 */
int seg_review( btFileSet *fs, int piece);

/* 将filename对应的piece设置成1, 返回到interest中。 */
void seg_markFile( btFileSet *fs, char *filename, kBitSet *interest);


关于这个模块是如何运何的，我也只能说说大体上的东西，毕竟项目不是我写的，同时也很复杂。

每个torrent下载任务只有一个btFileSet，在程序的某处用btFileSet_create(...)创建了btFileSet对象，并初始化了它的一些成员变量。之后还调用了btFileSet_addfile(...)添加文件信息到里面。下一步是对下载了的数据进行SHA校检，在btFileSet.complete中标识出哪些piece下载了。

最后来说一下btFileSet.partial。
1. 当本地peer决定发送一个未请求过的piece的请求时，兜兜转转会调用seg_getPiece(...)函数来要求返回一个btPartialPiece结构，seg_getPiece(...)函数malloc后也趁机把它连接到btFileSet.partial链表的未端。
2. 之后是根据返回的btPartialPiece进行发送request
3. 进行数据的接收, 调用seg_writebuf(...)保存数据
4. 最后当下载完毕就对这个piece进行SHA校检，设置相关数据结构，标识这个piece已经下载。再把这个piece的btPartialPiece结构从btFileSet.partial链表中删除。

上面的过程对应下面的函数
1, 2: peer_send_request(...)
3: recv_peermsg(...)的BT_MSG_PIECE消息处理部分
4: seg_writebuf(...)