leveldb阅读笔记—数据写入

October 24th, 2019 No comments

leveldb的写入可以简单的调用方法.

Status Put(const WriteOptions& options, const Slice& key,
                   const Slice& value) = 0;

其中key和value都可以是任何byte数据. 且可以是任意长度. 但是key的长度尽量越短越好, 这样有助于提供效率.

向leveldb的写入过程是比较简单的. 下图是一个 简化以后的流程, 大致上描述了写入的全过程. 去掉了诸如后台压缩线程的启动等内容.

write flow

首先, 不管是调动DB::Put 还是DB::Write最终都会走到Status DBImpl::Write(const WriteOptions& options, WriteBatch* updates)这个函数来.

首先, leveldb会把updates写入一个deque变量writers_中.

Writer w(&mutex_);
w.batch = updates;
w.sync = options.sync;
w.done = false;

MutexLock l(&mutex_);
writers_.push_back(&w);

然后, leveldb会去检查当前的memory table是否还有足够的空间可以容纳下当前的这一次写入. 不行的话就flush当前的数据到disk, 然后启动新的memory table.

Status DBImpl::MakeRoomForWrite(bool force) {
  bool allow_delay = !force;
  Status s;
  while (true) {
    if (!bg_error_.ok()) {
      // 后台压缩线程如果出现了错误, 就在这里把错误返回出去
      s = bg_error_; 
      break;
    } else if (allow_delay && versions_->NumLevelFiles(0) >= config::kL0_SlowdownWritesTrigger) {
      // level0的文件数量太多, 此时后台压缩线程应该还在工作中. 
      // 所以这里暂停一下, 不要让大量的写入让level0的文件数量越来越多.
      // 这里因为释放了mutex_这把锁. 所以可能会造成writers_中有多个writeBatch
      mutex_.Unlock();
      env_->SleepForMicroseconds(1000);
      allow_delay = false;  // Do not delay a single write more than once
      mutex_.Lock();
    } else if (!force &&
               (mem_->ApproximateMemoryUsage() <= options_.write_buffer_size)) {
      // 当前memory table还可用.
      break;
    } else if (imm_ != nullptr) {
      // imm还存在着, 表明后台的压缩线程还未执行完毕
      background_work_finished_signal_.Wait();
    } else if (versions_->NumLevelFiles(0) >= config::kL0_StopWritesTrigger) {
      // level0的文件实在是太多, 强行等待压缩线程完成其工作.
      background_work_finished_signal_.Wait();
    } else {
      // memory table使用的内存已经超标了, 而且imm也已经被flush到disk
      // 在这里将当前的memory table设置为imm(也就是imutable memory table)
      // 然后再产生一个新的memory table. writes_里面包含的数据都往这个心的
      // memory table中写入了.
      ...
      log_ = new log::Writer(lfile);
      imm_ = mem_;
      has_imm_.store(true, std::memory_order_release);
      mem_ = new MemTable(internal_comparator_);
      mem_->Ref();
      force = false;
      // 这里尝试着启动一下后台压缩线程, 因为产生了一个新的imm.
      MaybeScheduleCompaction();
    }
  }

上述代码描述了MakeRoomForWrite所做的事情

  • 如果后台压缩线程出错了, 那么将这个错误通过write这个线程返回回去
  • 如果level 0的文件数量超过了8个, 那么稍微等一下后台压缩线程, 免得写入太快导致后台压缩线程来不及工作. 不过这里只是稍微等待1ms时间.
  • 如果immutable memory table(imm)还没有被flush到disk, 那么等待后台线程完成这个工作
  • 如果文件实在是太多了, 超过了12个, 那么久强行等待后台压缩线程工作结束
  • 上述条件都不满足, 并且当前的memory table(mm)使用的空间已经超过预设的4M, 那么使用当前mm替换imm, 然后产生一个新的mm供后续写入

运行到这里, 表明mm有足够的空间可以容纳当前的数据. leveldb开始对writers_里面的数据进行打包. 上面MakeRoomForWrite里面如果level 0的文件数量超过8, leveldb会等待1ms时间, 在这个等待的时间里面, leveldb暂时会释放mutex锁. 这就可能导致在这个等待期间内.有新的线程插入新的数据. 所以这时writers里面可能会有多个batch形成的一个batchlist. 打包的任务就是将这些batch打包在一起形成一个新的batch. 但是也有一些限制. 新的batch的size不能超过1M. 并且如果batchlist[0]的大小不超过128K的话, 那么新的batch size不超过batchlist[0].size() + 128K.

数据打包好了以后, leveldb会暂时释放开mutex, 然后向log文件中写入打包好的数据. 然后把这个打包的数据写入memory table. memory table的主体数据结构是一个SkipList. 所以写入的时候实际上又会把刚才打包的数据一个一个拆开成key-value pair. 实际上写入到memory table的时候的key并不是用户传入的key, 而是InternalKey(参见数据结构篇). InternalKey有一个sequenceNumber和一个Type. type很简单, 如果是插入数据,type=1(kTypeValue). 如果是删除数据, type=0(kTypeDeletetion). 而sequence number在每次向skip list插入一个数据以后sequence number都会加一. 这样可以保证在skip list里面的数据是没有重复key的. 我猜这也是为何leveldb的skiplist不允许有重复key的理由.当后台线程被启动以后, 会将imm的数据flush到level0的sst文件中去, 同时该文件的一些metadata如最小的key和最大的key以及文件的size会同version记录到manifest文件中去. 至此, write的流程结束. 后续leveldb会在压缩(整理)后台线程中将imm的数据flush到level0的文件中去.

Categories: programming Tags: ,

leveldb源码阅读笔记 — 基本数据结构

October 21st, 2019 No comments

我们先来看一下leveldb里面的主要的数据机构, 以方便后续代码阅读.

我们知道leveldb对于存入的数据首先是放在内存中的memory table(MemTable)中. 这个MemTable其实是一个SkipList, SkipList例如不同level的指向同level的下一个node指针来达到快速查找的目的. 如图(该图片下载自这里). SkipList的详细信息可以查看这里.

skiplist

当我们插入一个key-value pair到leveldb的时候, 我们用到的这个key叫做user-key. leveldb里面有好几个Key.

lookup key

图上有3个key, LookupKey, InternalKey和UserKey. 其中UserKey就是用户的数据的key, LookupKey是在做查询的时候使用的. InternalKey是leveldb内部使用的key. LookupKey是包含length, userkey以及sequence+type. 这里面, length是整个internalkey的数据长度. seq+type一起构成一个8byte的数据. 其中低8位是key的类型, 高56位是sequence.

这个sequence我们需要讲一下到底是个什么东西. 在向leveldb存储key-value pair的时候会给每一个key-value pair生成一个sequence, 每写入一个pair, sequence就加一. 这样可以保证每一个pair的InternalKey都是不一样的. 在查询的时候也会带上一个sequence, 可能是某个snapshot的sequence也可能是查找当时最新的sequence. 这样可以将查找过程限制在某个snapshot或者查询当时的基础上. 避免在查找的过程中找到刚刚新插入的数据.

LookupKey的的数据结构是这样的

class LookupKey {
public:
  // Return a key suitable for lookup in a MemTable.
  Slice memtable_key() const { return Slice(start_, end_ - start_); }

  // Return an internal key (suitable for passing to an internal iterator)
  Slice internal_key() const { return Slice(kstart_, end_ - kstart_); }

  // Return the user key
  Slice user_key() const { return Slice(kstart_, end_ - kstart_ - 8); }
private:
  const char* start_;
  const char* kstart_;
  const char* end_;
  char space_[200];  // Avoid allocation for short keys
};

我们可以看到LookupKey有一个200字节的space这个field. 这个是为了在userkey的长度 <= 187的时候不需要额外在堆上分配内存而设置的. leveldb里面使用LookupKey的时候都是直接在栈上使用的. 这样可以很好的减少对于对上内存分配的次数.

我们看LookupKey可以看到它在编码的时候使用了诸如Variant32, Fixed64这些方式. leveldb对于数字的存储方式主要有 Fixed32, Fixed64, Varint32, Varint64这四种. leveldb默认是按照小头在前的方式编码数字, 对于Fixed系列, 那么就是直接的内存拷贝就可以了. 对于Variant系列, 编码方式如下

static const int B = 128;
uint8_t* ptr = reinterpret_cast<uint8_t*>(dst);
while (v >= B) {
  //如果数据本身>=128, 那么首先当前只是用其最低7为并且将低8为置为1, 表明还有后续的数据
  *(ptr++) = v | B;
  v >>= 7;
}
*(ptr++) = static_cast<uint8_t>(v);

当然经过这种格式编码以后, 最极端情况下, 如果32bit数据大于等于1<<28会使用5bytes来存储, 或者64bit数据大于等于1<<56会使用8bytes来存储. 当然, 一般情况下如果数值越小节约的存储空间越多. 如下面这个图片.

Varint的读取是写入的逆过程, 首先读取当前的低7位. 然后当前byte的最高位为1的话就将下一个字节的低7位左移以后作为数据的高位, 且一直这样处理到数据结束或者高位为0. 下面的代码是读取Varint32的代码, Varint64的代码是类似的.

uint32_t result = 0;
for (uint32_t shift = 0; shift <= 28 && p < limit; shift += 7) {
  uint32_t byte = *(reinterpret_cast<const uint8_t*>(p));
  p++;
  if (byte & 128) {
    // More bytes are present
    result |= ((byte & 127) << shift);
  } else {
    result |= (byte << shift);
    *value = result;
  }
}

当我们写入数据的时候, 会首先写入一个日志文件, 然后才会写入到memory table中. 那么这个日志文件是什么样子的呢. 实际上呢在leveldb有两种数据都会使用日志文件的格式来记录, 第一个就是我们插入key-value pair的数据的时候, 另外还有一个manifest文件记录数据的时候. 这两种文件记录的数据本身不一样, 但是在log文件这一层的格式是一致的. 我们这里先看看log文件本身的格式是啥样的.

log文件按照Block为单位来记录数据, 每一个Block都是固定的32Kbytes. 然后在每一个Block里面数据按照Record为单位记录数据. 每一个Record由RecordHeader和RecordBody构成, 如图

log record layout

RecordHeader一共7个字节, 分别是4byte是的CRC, 2bytes的length和1byte的type. 这里的length记录的是RecordBody的长度. Record的type有如下几种

enum RecordType {
  // Zero is reserved for preallocated files
  kZeroType = 0,

  kFullType = 1,

  // For fragments
  kFirstType = 2,
  kMiddleType = 3,
  kLastType = 4
};

由于Log的Record的长度是固定的, 但是一次数据的大小是不固定的, 所以leveldb使用不同的record来组成一个完整的数据. 如果一个record容纳不了数据, 那么就会将数据分成很多的record, 然后用type来表示当前的这个record是数据本身哪一段. 在读取的数据的时候会根据type来使用多个record合成原来的数据.如果record可以容纳数据, 那么很简单使用type为kFullType即可.

有一个需要注意的地方是, 如果一个Block在写入record后剩余的空间<7bytes,也就是无法容纳一个RecordHeader的话, 那么这些剩下的部分全部填0. 并且被忽略掉. 而如果Block的剩余空间刚好是7bytes, 这个时候level会记录一个length为0, 且crc为0x49258fd2的一个record.

接下面我们来看看leveldb里面的table文件的格式是什么样子的. leveldb记录的用户数据就保存在table文件中. 我们这里先不关心数据是如何记录到table文件的, 我们先看看table文件的格式是怎么样的.

每一个table文件由 DataBlock, FilterBlock, IndexBlock, Footer构成. 这里记录一下leveldb官方文档上对于table格式的描述

<beginning_of_file>
[data block 1]
[data block 2]
...
[data block N]
[meta block 1]
...
[meta block K]
[metaindex block]
[index block]
[Footer]  (fixed size; starts at file_size - sizeof(Footer))
<end_of_file>

可以看出其实Table文件就是一堆的Block和一个Footer构成, 只是不同的Block记录了不同的数据. 当前一共有4中类型的Block. 分别是

  1. DataBlock, 这里记录着用户数据, 就是你调用Put方法放入的数据编码以后保存在这个地方.
  2. MetaBlock, 当前leveldb支持BloomFilter的MetaBlock.
  3. MetaIndex Block
  4. Index Block

这些不同Block承载的数据都有自己的格式, 但是Block本身的格式都是一样的. 我们来看看Block的格式.

block format

一个Block的原始数据是大约4K, 可以超过4K这个限制. 但是压缩以后就不知道具体是多大了. Block分为3个部分, 如图, 最上面的是数据区, 每一个key-value pair被编码以后一个接着一个的放到这里. 紧接着是记录restarts offset的区域, 每一个记录的restart offset都是Fixed32编码的. 这个restarts是用来干什么的呢? 这个和block里面存放数据的方式有关.

table key-value format

leveldb在存储用户数据的时候, 首先会对key和value进行编码. 如上图, 在向Block里写入key-value pair的时候并不是直接写入key和value的值. 而是对key做了一个前缀压缩, 因为在imm里面的key是有序的, 所以就有了做前缀压缩的基础. 这个前缀压缩的方式是找到当前的key和上一个key的longest common prefix. 然后记录这个prefix的长度记为shared, 当前key的剩下部分的长度记为non_shared. 上图中的前两个field就是shared和non_shared的Variant32编码后的数据, 紧接着的数据是value的size的Variant32编码数据. 然后对于key的数据就只保存non_shared部分.

这样每一个key的内容都依赖于前一个key的内容一直延续到该Block的第一个key. restarts就是中断这个依赖而设定的, restarts的最大值是16个, 也就是说每过16个key就会强制的将shared设置为0, 全量记录key的内容. 那么在对key进行复原的时候最大多只需要读取16个key的内容即可. restarts里面记录的是每一次全量记录key的时候的offset. 然后在Block的尾部记录一下当前的Block有多少的restarts. 以方便读取的时候找到所有的restarts的数据. 需要注意的是如果是index block的话, 那么允许的最大的restarts数量是1, 也就是全部全量记录.

现在我们来说一下leveldb里面的一个用于缓存Block数据的数据 结构, LRUCache.

LRUCache由一个HashTable和两个双向链表构成. 暂且称其为hash_table, lru_list和inuse_list. 这三个结构的关系是这样的. 所有的数据都在hash_table里面, 这样就可以快速找到这个数据. 如果一个数据正在被使用, 那么这个数据只会记录在inuse_list里面. 如果一个数据没有被使用, 那么这个数据只会被记录在lru_list里面. LRUCache有一个capacity, 这个不是缓存的条目的数量, 而是缓存的数据的size之和. 这个capacity默认是8M. 当插入到LRUCache的数据过多的时候, 超过设定的capacity就会从lru_list里面按照从老到新的顺序删除一部分数据. 如果一个数据本来在lru_list里面, 这个时候被使用了, 那么就会从lru_list里面摘除, 同时放入到inuse_list. 相反的, 如果一个在inuse_list里面的数据不被使用, 那么就会脱离inuse_list, 然后加入到lru_list中.

Categories: programming Tags: ,

renew

October 10th, 2019 No comments

这个地方已经荒的不像样了, 近来整理一下以前记录的东西放到这里来. 也算作一个知识的renew.

Categories: mutter Tags:

如何回退已经push到upstream的版本

March 23rd, 2017 No comments

当不小心commit了一些错误的内容,并且糟糕的是这些new commits已经push到了upstream。我们该如何会退到正常的commit上去呢?
一种办法是reset到正常的commit, 然后push -f到upstream。 但是这样有一个问题,那就是如果别人已经获得了你push的错误的commits,那么会比较麻烦,可能别人也需要做同样的reset动作。

其实我们可以这样做。

  1. reset –hard good–commit
  2. do something or do nothing
  3. git reset –soft ORIG_HEAD
  4. git ci -am “revert to commit xxx”
  5. git push

这样以来,别人可以继续使用git pull拿到正确的内容而不会有任何的冲突或者手动调整的过程。

当然了,git操作上更加简单的做法是git revert good_commit, 然后git add && git commit&& git push. 不过这样的话可能需要手动resolve conflict.

Categories: programming Tags:

g++4.8.4的regex貌似有问题哦

October 28th, 2015 No comments

使用c++11(g++ 4.8.4)的regex的时候发现了一个问题。因为我不了解ECMAScript的表达式规则,所以我选用了std::regex::extended。 但是测试下来发现连"[0-9]{1,3}"这个表达式也无法正常工作。

#include <regex>
#include <string>
#include <iostream>

int main(int argc, char*argv[]) {
if( argc < 2 ) {
std::cerr<<"please input text you want"<<std::endl;
return -2;
}
std::string text(argv[1]);
std::regex expression("[0-9]{1,3}", std::regex::extended);
std::smatch m;
if( std::regex_match(text, m, expression )) {
for( auto it = m.begin(); it != m.end(); it ++ ) {
std::cout<<"Match: " << *it << std::endl;
}
} else {
std::cerr<<"not matched"<<std::endl;
}
return 0;
}

上述代码用./a.out 123会得到not matched. 也就是无法匹配。 
开始我一直认为是我的正则表达式弄错了,但是我用grep来验证发现这个表达式是OK的。

roy@DevBox:~/temp$ echo "123" | grep -E "[0-9]{1,3}"
123

当然到此为止还是不能证明g++的regex是错的,可能c++11的regex和grep的语法有些不一样。

于是我用boost来测试上述代码, 发现使用boost::regex以后上述代码(需要修改regex的namespace)build出来的程序是可以正确匹配"123"的。同时我又使用Visual Studio 2015( Community Edition)来测试上述代码,在VC下,自带的std::regex和boost::regex构建出来的程序都可以正常匹配"123"。

 那么看起来g++4.8.4的std::regex应该是有问题的。在linux下面暂时需要使用boost::regex来构建正则表达式相关的东西了。

Categories: programming Tags: , , ,

强引用智能指针与弱引用智能指针

February 25th, 2015 No comments

c++代码中最麻烦的就是内存管理了, 还好有了RAII,这样至少可以解放一点我们的脑细胞,不需要时时刻刻注意释放内存或者避免多次释放内存。现在很多人都使用std::shared_ptr 当然了,如果你没有用到C++11,那么可以使用boost::shared_ptr. 不过我们当时使用的不是shared_ptr. 而是学习了ICE以后自己倒腾出来的一个intrusive_ptr,俺们管它叫做Pointer, 非常类似于boost::intrusive_ptr。不过我们当时还不知道boost有这个东西而已(也可能当时还没有这个玩意儿)。

侵入式智能指针和非侵入式智能指针的差别还是挺大的,我们用一幅图来说明一下。 
smart_pointer
这幅图的左边是侵入式智能指针,其引用计数放在了被指向的object的里面,intrusive_ptr指向这个object即可。而右边是非侵入式智能指针,引用计数被单独放在一块区域(其中还包括一个弱引用的计数)。non-intrusive_ptr(shared_ptr, weak_ptr)指向object和引用计数区域。这样一来,对于intrusive_ptr,我们还是可以直接使用raw pointer, 当然这样并不好,也可以再把一个raw pointer传递给一个intrusive_ptr, 其引用计数不会有被中断的情况。而non-intrusive_ptr就不能这样,raw pointer传递给他们以后引用计数只能重新开始计数。还有就是由于侵入式智能指针的引用计数和目标object实例在一块, 那么可以更加有效的利用CPU cache。 而非侵入式的智能指针因为有两个指针,就会稍弱一点。但是呢,侵入式智能指针相比非侵入式智能指针也有一个缺点,这就是我们要讲的弱引用智能指针。 
那么弱引用到底是什么?有什么用处呢? 我们知道智能指针的引入是为了减少内存泄漏的问题,顺带着把野指针,多次释放内存等问题一块解决了。但是有的时候只能指针也会有内存泄漏问题,循环引用–就是这种情况。当两个object互相持有对方的引用,那么他们的引用计数都不会减少到0,那么这两个object也都不会被释放。解决的办法也就是弱引用. 当两个object需要持有对方的时候,其中一方持有对方的弱引用,弱引用是不增加(强)引用计数的–即上图右中的reference count,但是会增加weak reference count. 举个例子,有A,B两个对象实例,其中A持有B的强引用refB, 但是B只持有A的弱引用refA. 当除B以外的object不再持有对A的引用的时候,由于弱引用不会增加引用计数,所以A的引用计数会降至0,此时A会被释放掉,同时B的引用计数也会减少。这样就可以有效的解决循环引用造成的内存泄漏问题。

现在我们来看看弱引用是如何实现的。如上图右边所示,非侵入式智能指针有两个指针。其中一个指向对象实例,我们命名为px; 另外一个指向一块专门用来存放引用计数的区域,我们为之命名为pn. pn所指向的区域( 就叫RefCountZone吧 )里面一共有两个变量,reference count和weak reference count, 他们分别记录强引用和弱引用的次数。当使用shared_ptr的时候,reference count就会加1,而weak reference count不会有变化。而使用weak_ptr的时候, weak reference count就会加1,但是reference count不会有变化。这样一来当所有的强引用都消失了, 那么reference count就会变成0,这个时候就可以删除px所指向的对象实例了。但是值得注意的是在这个时候pn所指向的区域不一定被删除。我们假设这个时候还有弱引用到这个区域,那么pn指向的区域是不会被删除的。这时候如果我们需要使用weak_ptr指向的object 实例的时候,首先需要调用weak_ptr::lock方法,该方法可以获得一个shared_ptr(但可能是空)。weak_ptr::lock首先检查pn->reference count是否为0,如果是0 的话,那么说明px指向的实例已经被删除,那么lock方法会失败,返回一个不指向任何实例的shared_ptr,如果pn->reference count不为0,那么说明px所指向的实例还存在,这个时候可以返回一个该实例的shared_ptr. 当所有的弱引用都消失的时候,也就是pn->weak reference count == 0的时候,同时pn->reference count也是0,那么说明已经没有任何对这个实例的引用了(不论是强引用还是弱引用),这是pn指向的区域就可以被安全删除了。 
从上面我们也可以看出弱引用很巧妙的利用了非侵入式智能指针的RefCountZone。同时利用了reference count和weak reference count来分别控制强引用和弱引用的个数。但是侵入式智能指针就不能很好的实现弱引用了,因为如果我们要实现弱引用,那么就需要一块区域来存放所引用的次数,而且这个块区域不能随着object instance的消亡而消亡,否者当强引用完全消失但还存在弱引用的时候由于object instance已经被删除导致弱引用计数无法被访问。如果我们也想像非侵入式智能指针 一样新开辟一块区域来存储ref count, 那么就变得和shared_ptr/weak_ptr一样,没有重新实现的必要了。所以如今在使用侵入式只能指针并且有循环引用风险的地方,我们会将其中一方持有对方的智能指针修改为原始指针或者是引用。

正确关闭一个 tcp socket

February 11th, 2015 No comments

在将现有的阻塞同步socket库转换为异步非阻塞socket库(好吧,其实我们叫它非阻塞异步事件库)的时候,我们发现了一个问题。 就是当数据发送端发送完大量数据(例如20G)的最后一段数据以后,close掉socket(tcp socket)以后客户端收到的数据总是不能达到预期的数据大小,总是比预期的数据少一部分,而且具体少多少数据看起来还是随机的。debug多次以后我们认为是我们最后一次send以后就调用了close(socket_fd)造成的。 
我们知道, send其实只是把要发送的数据放到kernel的buffer中去,具体的发送动作是由kernel自己触发的。当我们发送最后一段数据以后立即调用close的时候可能还有很多没法发送出去的数据在内核的buffer中,而内核可能会直接丢弃掉未发送的数据,这样对方就可能无法接收到完整的数据。由于我们的异步事件库都是非阻塞的,所以我们不能设置SO_LINGER来等待socket把剩下的数据发送出去。否则这个close可能会阻塞调用很长一段时间。所以解决办法是当socket需要被close的时候,首先调用shutdown(socket_fd,SD_WR),也就是关闭写, 这个时候应该会向tcp socket kernel buffer中添加一个FIN的数据包。 然后我们通过epoll监视EPOLL_IN事件来接收对方的close事件(也就是对方发送FIN). 当收到对方的FIN以后我们就可以真正的关掉这个socket了。 当然了实际的代码是在发送shutdown(fd,SD_WR)以后就设置一个timer(例如5秒timeout)。如果timer过期了,那么无论是否收到对方的FIN都会关掉这个socket。这样可以防止对方程序出现永远不关闭socket的情形发生进而影响本机的socket的关闭。

Categories: programming Tags: ,

ip分片与重组

December 19th, 2014 No comments

最近在做udp pump, 突然手贱的想要知道一个udp包的最大负载的是多少.
于是写了一个简单的程序来测试了一下, client不断的发送payload size不断增加的包, 然后在server端收数据包. 当然了由于IP的最大payload只有65535-sizeof(IP Header).所以Udp的最大负载也就是只有大约65535-20-8 = 65507个. 如果超过这个大小以后,不是收不到, 而是client根本发不出去这个数据包

#!/usr/bin/env python
#-*- coding:utf-8 -*-

import socket
import random
import string
import sys
import hashlib

def sendData(udp, ip,port, size):
    data = ''.join(random.choice(string.ascii_uppercase + string.digits) for _ in range(size))
    md5 = hashlib.new('md5')
    md5.update(data)
    udp.getsockname()
    udp.sendto(data,(ip,port))
    print "%s :: sending %08d bytes to %s:%d   --> %s" % ( udp.getsockname(), len(data), ip,port, md5.hexdigest())


def run(ip,port,begin,inc,end):
    udp = socket.socket(socket.AF_INET, socket.SOCK_DGRAM, socket.IPPROTO_IP)
    udp.bind(("0.0.0.0",0))
    sendData(udp, ip, port, 65507)
    sendData(udp, ip, port, 65508)

用上面的代码发送可以很轻松的验证,发送65507个字节的时候是OK的,但是65508的数据就会得到Message Too Long的错误.

接下来呢, 我做了一件错误的事情,然后导致了后来一系列的事情的发生.
我在server端使用tcpdump来查看网络数据包, udp server listen在6666端口.所以我使用命令来查看数据包

sudo tcpdump -i any -nnn -vvv "port 6666"

注意我的 tcpdump的filter是”port 6666″,也就是采用过滤端口的方式.这个也就是我想当然的认为ip fragment以后的每一个udp packet的port应该和原始数据是一致.

拿到tcpdump的数据以后我下了一大跳

17:06:09.875525 IP (tos 0x0, ttl 61, id 28605, offset 0, flags [+], proto UDP (17), length 1500)
    192.168.80.233.52099 > 10.15.10.50.6666: UDP, length 65507

请看IP的段显示的数据大小为1500, 这个很容易理解,毕竟大部分的网络的MTU都是1500,这里也不例外.但是UDP段显示的length是65507, 这个也说得过去, 我发送的数据就是这么大的. 但是问题来了,为啥只有这么一个数据包. 于是我猜测抓包显示的数据错掉了.我把抓包数据存下来以后发现文件大小也就是1500多一点大.那么很明显这个数据包里面的数据真的只有1500 bytes. 这里的事情被我认为是非常诡异的, 因为我发送数据的时候对数据做了一个md5,udpserver收到数据以后也会做一个md5. 这两个md5是一模一样的,那么很明显证明了server端收到的数据和client发送的数据是一样的.
但是抓的包却只有1500 bytes啊,剩下的数据死到哪里去了呢?
我一度怀疑tcpdump有bug,于是换成了wireshark(tshark). 但是得到的结果是一样,见鬼了. 于是乎一阵google以后找到了使用raw socket来抓数据包的代码在这里.感谢作者的无私分享. 用这个程序跑了一下,只抓udp的包. 从抓包数据看,端口为6666的仍旧只有1500字节的ip数据, 但是很奇怪的是那些非6666端口的其他数据包里面的数据和我发送的数据十分相似–随机的字符数字组合. 然后我发现了一个东西,也是这个东西让我明白了这到底是怎么回事.

IP Header
   |-IP Version        : 4
   |-IP Header Length  : 5 DWORDS or 20 Bytes
   |-Type Of Service   : 0
   |-IP Total Length   : 1500  Bytes(Size of Packet)
   |-Identification    : 63208
   |-Dont Fragment Field   : 0
   |-More Fragment Field   : 0
   |-TTL      : 62
   |-Protocol : 17
   |-Checksum : 35759

这个让我感觉很奇妙的东西就是Identification. 因为抓包数据中的所有包头都含有相同的Identification. 这个不免让我觉得其实IP分片以后实际上是靠Identification来决定是不是同一个上层数据包的内容的. 于是我查看了一下ip分片的实现

/* Find the correct entry in the "incomplete datagrams" queue for
 * this IP datagram, and create new one, if nothing is found.
 */
static inline struct ipq *ip_find(struct net *net, struct iphdr *iph, u32 user)
{
        struct inet_frag_queue *q;
        struct ip4_create_arg arg;
        unsigned int hash;

        arg.iph = iph;
        arg.user = user;

        read_lock(&ip4_frags.lock);
        hash = ipqhashfn(iph->id, iph->saddr, iph->daddr, iph->protocol);

        q = inet_frag_find(&net->ipv4.frags, &ip4_frags, &arg, hash);
        if (q == NULL)
                goto out_nomem;

        return container_of(q, struct ipq, q);

out_nomem:
        LIMIT_NETDEBUG(KERN_ERR "ip_frag_create: no memory left !\n");
        return NULL;
}

上面的ip_find是从ip_local_deliver => ip_defrag => ip_find这个调用链过来的. 我们可以看到这里使用ip header里面的id, source addr, dest addr和protocol来做一个hash, 远没有port啥事.
到这里已经很清楚了, udp发的数据的最大负载是65535-20 -8 = 65507. 但是到了ip层的话还是需要被分片的, 否则过不了交换机. ip分片的依据的ip header中的id, 当然还需要由frags来指明fragment的offset之类的信息.
这个时候再回头来想想当初为何就没有想到, port是udp/tcp层的东西, ip层是没有这个玩意儿的. 那么分片自然就是和port无关的了.

Categories: programming Tags: , , ,

Debug Heap Corrupt

December 12th, 2014 No comments

c/c++代码对内存操作有着极强的控制力, 但是也很容易造成问题。 特别是内存访问越界这类问, 一旦出现了,在很多情况下是很难查找的。 如果软件中的某个模块因为单元测试没有完全覆盖(这个通常也很难)然后集成起来以后出来的这类问题就更加难以查找。 很多时候出现问题的地方根本就不是你看到的地方。 我们来举个例子, 这个也是我们遇到的问题的一个简化版本。 直接上代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <vector>

void corrupt( ) {
    char* p = (char*)malloc(1);
    memset(p,0x47,32);//fill some garbage to corrupt the heap
}

void victim( ) {
    std::vector<int> arr;
    for(int i = 0 ; i < 100; i ++ ) {
        arr.push_back(i);
    }
}

int main(int argc, char* argv[]){
    corrupt();
    victim();
    return 0;
}

上面的代码在corrupt函数中分配了一个字节的空间,接着调用memset向分配的地址写入32个0x47. 那么很明显,写越界了。 这样的操作会把heap的维护链表弄坏,导致以后再次进行内存分配释放的时候出现错误,也可能写入另外一块分配的内存区域。
在vc(visual studio 2005)下面编译运行以后在

        arr.push_back(i);

出现错误。 output窗口(调试模式下面)输出

First-chance exception at 0x7c922bb3 (ntdll.dll) in heap_corrupt.exe: 0xC0000005: Access violation reading location 0x003b6000.

很明显出现错误的地方并不是造成问题的地方, 这个简单的程序你可能很容易就可以看出问题出在什么位置。但是如果是一个很复杂的大型工程,那么很可能就没有那么容易了。如果没有其他的帮助工具的话估计要花很大的时间和精力来逐步收缩出问题的范围。
上面的代码在g++下面(需要增加一些include的头文件)编译运行以后也会显示是arr.push_back(i)这一行除了问题。
为了能有效的快速定位此类问题, 我们通常需要借助其他的工具。 在windows上面我们可以使用gflags来做到这一点。
使用如下命令,monitor heap的操作

gflags /p /enable heap_corrupt.exe /full

然后再来调试改程序,就会在memset(p,0x47,32);这一行发生异常。 那么我们就可以很快的检查出来是因为对p的写越界造成了这个问题。 但并不是有这个工具就万事OK了。如果我们把memset那一句改成memset(p,0x47,2);的话。那么程序在整个调试过程中是不会出错的,当然了,这个很可能是因为malloc(1)的时候得到的内存块的真是大小不是1而是某个最小的bucket的大小.
在linux上面呢, 我们可以使用AddressSanitizer这种神器来快速定位这个问题。因为我们的gcc版本是4.4.7的,还没有AddressSanitizer的支持,所以可以使用clang.

clang++ -g -fsanitize=address -o t test.cpp

然后直接运行程序就可以在输出上看到一堆东西

[hongquan.zhang@devbox Download]$ ./t
=================================================================
==1216==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000f00f at pc 0x48aaab bp 0x7fff4a1687d0 sp 0x7fff4a1687c8
WRITE of size 32 at 0x60200000f00f thread T0
    #0 0x48aaaa in corrupt() /home/hongquan.zhang/Download/test.cpp:10
    #1 0x48b0d0 in main /home/hongquan.zhang/Download/test.cpp:21
    #2 0x3f7201ecdc in __libc_start_main (/lib64/libc.so.6+0x3f7201ecdc)
    #3 0x48a84c in _start (/home/hongquan.zhang/Download/t+0x48a84c)

0x60200000f00f is located 30 bytes to the right of 1-byte region [0x60200000eff0,0x60200000eff1)
allocated by thread T0 here:
    #0 0x473131 in malloc /home/hongquan.zhang/Work/tools/llvm/projects/compiler-rt/lib/asan/asan_malloc_linux.cc:74
    #1 0x48a9cb in corrupt() /home/hongquan.zhang/Download/test.cpp:9
    #2 0x48b0d0 in main /home/hongquan.zhang/Download/test.cpp:21
    #3 0x3f7201ecdc in __libc_start_main (/lib64/libc.so.6+0x3f7201ecdc)

SUMMARY: AddressSanitizer: heap-buffer-overflow /home/hongquan.zhang/Download/test.cpp:10 corrupt()
Shadow bytes around the buggy address:
  0x0c047fff9db0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9dc0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9dd0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9de0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9df0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa 01 fa
=>0x0c047fff9e00: fa[fa]fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9e10: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9e20: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9e30: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9e40: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9e50: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Heap right redzone:      fb
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack partial redzone:   f4
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Contiguous container OOB:fc
  ASan internal:           fe
==1216==ABORTING

输出的最开始就表明了出错的地方是corrupt函数,可以非常方便的让我们在第一时间发现真正制造问题的地方。而且即便你把memset调用改成memset(p,0x47,1)也依然有效。

上面的方法也许对你在遇到问题的时候有一些帮助,当然了最好还是在操作内存的时候小心一些。如果可以的话,尽量使用c++已经封装好的class。 如果不得已需要直接操作内存需要慎之又慎。

Categories: programming Tags: ,

C++抛exception会主动让出CPU吗?

September 10th, 2014 No comments

虽然我自己并不是很喜欢使用exception.但是在有的场合用exception比return code让代码更具可阅读性.一直以来,我都认为throw exception不会大幅度降低程序的性能, 但是最近线上发生的一件事情却把exception这个东西牵扯了进来.
事情很简单, 现场报说有的请求timeout(500ms超时). 查看log以后发现一部分代码可能造成这个问题,但是当时并无法肯定是哪一个调用造成的耗时长. 后来做了一系列的实验以后发现居然是一个查找部分的代码会很耗时(最长可达1s), 但是这个查找的代码的实现及其的简单.基本上就是这个样子:

void findXXX( ) {
    find in a std::map<std::string, std::string> instance;
    if not found {
        throw InvalidParameter();
    }
}

而当时的情况是, map中是没有数据的,也就是说一定会出发抛出异常. 开始我怎么都觉得throw exception会那么耗时.可是多次的测试下来却发现总是在这个点上可能耗时很长.那么无论如何这个抛异常看起来都有点问题.
于是我做了一个小程序,就是很简单的抛异常100w次.但是没有发现耗时很长的情况发生(至少和我预期是一样的). 那么为何线上程序总是在这个抛异常的地方出现问题呢? 于是对比了自己的模拟程序和线上程序,发现了一个很大的不同点,那就是线上程序是多线程的,而且线程相当多(500+),而我的测试程序是单线程的.那么有没有可能是抛异常会导致线程切换,最终引发耗时长呢?
于是我修改了一下测试程序,加入线程,线程run里面就是不断的++一个long long,过一会儿sleep 30ms. 我一共new了800个线程(我也是够猛的). 这次测试程序我做了两个版本,一个是抛异常的,另外一个是不抛异常,取而代之的是循环++10次,然后return的.
从这两个版本的测试结果来看,在同一个环境(CentOS5, 4core cpu, 16G mem)上测试10次,平均下来,抛异常的版本运行时间为26s,而不抛异常的版本运行时间为1.5s左右. 同时抛异常的版本中能监测到有很50+次调用函数耗时达1ms以上的.而不抛异常的版本平均只有2次不到.
基于这些测试, 我猜测很可能抛异常会引发context switch. 同时由于线程数量巨大,线程切换十分频繁. 最终造成这个简单的findXXX耗时很大.
当然了,这个只是我的猜测,没有证实. 希望以后可以继续看看是不是真的造成了主动的线程切换.

PS: google了好一阵, 还没有直接证据可以证明throw exception可能导致线程上下文切换. 以后有空倒是可以看看libstdc++的实现.

Categories: programming Tags: ,