muduo网络库源码解析(4):TimerQueue定时机制

muduo网络库源码解析(1):多线程异步日志库(上)
muduo网络库源码解析(2):多线程异步日志库(中)
muduo网络库源码解析(3):多线程异步日志库(下)
muduo网络库源码解析(4):TimerQueue定时机制
muduo网络库源码解析(5):EventLoop,Channel与事件分发机制
muduo网络库源码解析(6):TcpServer与TcpConnection(上)
muduo网络库源码解析(7):TcpServer与TcpConnection(下)
muduo网络库源码解析(8):EventLoopThreadPool与EventLoopThread
muduo网络库源码解析(9):Connector与TcpClient

前言

前三篇算是把日志部分讲清楚了,从这篇开始从TimeQueue入手,引入Runinloop.在下一篇或者下下一篇中描述整个muduo的事件分发机制.

TimerQueue这个类看上去麻烦,不知所云,实则非常简单,我们就把它看做一个时间轮即可,其实它本身也可以充当时间轮,不过效率比不上时间轮而已,时间轮可以接近O(1),而muduo中的TimeQueue中使用set,插入和取出(二分)均为O(logn).当然两者都是既可以写成信号驱动,也可以写成事假驱动,在muduo中,TimerQueue为事件驱动,简单的分析就到这里,从源码中我们可以看到更多细节.

(类图)

我们先来看看最重要的三个成员,

  TimerId addTimer(TimerCallback cb,
                   Timestamp when,
                   double interval);

  void cancel(TimerId timerId); 
  
  void handleRead(); 

我们首先来想以下一个通用的计时机制我们需要什么,显然我们需要一个插入和删除,也正是上面我们看到的addTimer和cancel,然后就剩下一个handleRead,因为TimerQueue是事件驱动,当我们收到可读事件后我们自然要执行add进来的回调,那么handleRead的作用就明了了.

我们先来看看构造函数.

TimerQueue::TimerQueue(EventLoop* loop) 
  : loop_(loop),
    timerfd_(createTimerfd()), //创建一个Timerfd
    timerfdChannel_(loop, timerfd_),//创建一个channl对象 加入IO线程的Eventloop
    timers_(),
    callingExpiredTimers_(false)
{
  timerfdChannel_.setReadCallback(
      std::bind(&TimerQueue::handleRead, this));//注册回调事件
  // we are always reading the timerfd, we disarm it with timerfd_settime.
  timerfdChannel_.enableReading(); //IO多路复用中注册可读事件
}

这里其实有不少可说的点:

1. 只有一个构造函数,即Eventloop类型,原因涉及到muduo的整个事件分发机制,我们在下篇中讲解.
2. timerfd,这很有意思,是linux2.6.25版本新增的定时器接口,实体是一个文件描述符,意味着它是基于事件的.
3. callingExpiredTimers_,先埋个悬念,下面我们会着重讲这种机制.
4. channel对象,即==timerfdChannel_==注册回调,涉及到muduo的事件分发机制,在下篇中讲解.

挖下了不少坑,我们会一个一个填上的,开始吧!

TimerId TimerQueue::addTimer(TimerCallback cb, //用户自定义回调
                             Timestamp when, //何时被触发
                             double interval) //重复触发间隔 小于0不重复触发
{
  Timer* timer = new Timer(std::move(cb), when, interval);
  loop_->runInLoop(
      std::bind(&TimerQueue::addTimerInLoop, this, timer));
  return TimerId(timer, timer->sequence()); //唯一标识一个Timer
}

我们可以看到addTimer实际上就是注册了一个回调,我们暂不管runInLoop,这个我都感觉可以专门写一篇…,我们后面再说,这篇文章则着重于TimerQueue的逻辑部分,我们进入TimerQueue::addTimerInLoop,

void TimerQueue::addTimerInLoop(Timer* timer)
{
  loop_->assertInLoopThread();
  bool earliestChanged = insert(timer); //插入Timers和activeTimers_(cancel)

  if (earliestChanged)
  {
    //如果timers中最低的时间限度被更新,就更新一次定时器
    resetTimerfd(timerfd_, timer->expiration());
  }
}

...............

bool TimerQueue::insert(Timer* timer)
{
  loop_->assertInLoopThread();
  assert(timers_.size() == activeTimers_.size());
  bool earliestChanged = false;
  Timestamp when = timer->expiration();
  /*获取队列中定时时间最短的项,即第一个 因为数据结构是set,红黑树有序,
  比较顺序为pair的比较顺序 即先比较first,相同比较second*/
  TimerList::iterator it = timers_.begin(); 
  if (it == timers_.end() || when < it->first) //timers中不存在Timer或者定时时间小于最小的那一个
  {
    earliestChanged = true; //为true说明插入timers后为第一个元素 即更新最小值
  }
  {
    std::pair<TimerList::iterator, bool> result
      = timers_.insert(Entry(when, timer)); //就算Timestamp一样后面的地址也一定不一样
    assert(result.second); (void)result; //断言永真
  }
  {
    std::pair<ActiveTimerSet::iterator, bool> result
      = activeTimers_.insert(ActiveTimer(timer, timer->sequence()));
    assert(result.second); (void)result; // TODO activeTimers是干什么的?
  }

  assert(timers_.size() == activeTimers_.size());
  return earliestChanged;
}

...............

void resetTimerfd(int timerfd, Timestamp expiration)
{
  // wake up loop by timerfd_settime()
  struct itimerspec newValue;
  struct itimerspec oldValue;
  memZero(&newValue, sizeof newValue);
  memZero(&oldValue, sizeof oldValue);
  newValue.it_value = howMuchTimeFromNow(expiration); //提供所给时间与现在的差值 大于100微秒
  //expiration到now的时间 大于等于100微秒 也就是说timer_fd触发时一定有可执行的回调 也有一个重置定时器的作用
  int ret = ::timerfd_settime(timerfd, 0, &newValue, &oldValue);//重新设置定时器,第四个参数可为空
  if (ret) //成功返回零 失败返回-1
  {
    LOG_SYSERR << "timerfd_settime()";
  }
}

我们注意到在插入后会返回一个TimerId,这个我们不分析,其实就是为了标识唯一对象.

事件驱动与信号驱动区别

这里最重要的是resetTimerfd中的timerfd_settime,这是一个定时器是信号驱动还是事件驱动的核心,我们不妨想象,何为信号驱动和事件驱动,TimerWheel和TimerQueue不过是提供了一个添加和执行的功能而已,定时机制仍需我们在代码中展现,而timerfd_settime就是提供这样一个定时机制,用大白话来说,就是告诉系统多长时间后一个给我的eventfd写点东西告诉时间到了!信号驱动呢?无非是使用alarm,在信号处理函数中再发出一次信号罢了.

我们继续来看看cancel,映入眼帘的还是一个回调

void TimerQueue::cancel(TimerId timerId)
{
  loop_->runInLoop(
      std::bind(&TimerQueue::cancelInLoop, this, timerId));
}

void TimerQueue::cancelInLoop(TimerId timerId)
{
  loop_->assertInLoopThread();
  assert(timers_.size() == activeTimers_.size());
  ActiveTimer timer(timerId.timer_, timerId.sequence_);
  ActiveTimerSet::iterator it = activeTimers_.find(timer);
  if (it != activeTimers_.end()) //已加入的集合中找到了要删除的元素
  {
    size_t n = timers_.erase(Entry(it->first->expiration(), it->first));
    assert(n == 1); (void)n;
    delete it->first; // FIXME: no delete please
    activeTimers_.erase(it); //153,156 在timers和activeTimer中直接删除 
  }
  else if (callingExpiredTimers_)
  {
    cancelingTimers_.insert(timer); //加入删除队列 在被触发时删除
  }
  assert(timers_.size() == activeTimers_.size());
}

这里有一个重点要说,大部分人在这里的疑问就是callingExpiredTimers_,为什么为true才向删除集合中加入呢?我们可以看到在第一个if判断里面实际上已经从现有的集合中删除了事件,我们不禁要问,还需要cancelingTimers_吗?答案是肯定的,见下代码,即第三个重要的函数handleRead

void TimerQueue::handleRead()
{
  loop_->assertInLoopThread();
  Timestamp now(Timestamp::now());
  readTimerfd(timerfd_, now); //读取超时时间,因为muduo默认LT 防止多次触发

  std::vector<Entry> expired = getExpired(now); //获取目前超时的Timer RVO 不必担心效率

  callingExpiredTimers_ = true;
  cancelingTimers_.clear();
  // safe to callback outside critical section
  for (const Entry& it : expired)
  {
    it.second->run(); //执行Timer中回调 ,
  }
  callingExpiredTimers_ = false;
  reset(expired, now);
}

因为触发这个函数的时候我们可以确定Timerfd已经可读,我们可以看到ReadTimerfd先进行读取,因为muduo默认LT,然后通过getExpired获取可读集合.下面进入重点,callingExpiredTimers_,为什么要用true和false把这里包起来呢,原因是run中的回调可能执行cancelInLoop, 那时timers中已经没有了要删除的,这样就会丢失信息,所以维护一个cancelingTimers_,我们再回到cancelInLoop中,callingExpiredTimers_为true才加入删除集合,即cancelingTimers_,什么时候使用呢,我们在handleRead执行完回调执行reset

//可重复且不希望删除的的再加入请求队列 
void TimerQueue::reset(const std::vector<Entry>& expired, Timestamp now)
{
  Timestamp nextExpire;

  for (const Entry& it : expired)
  {
    ActiveTimer timer(it.second, it.second->sequence());
    if (it.second->repeat()
        && cancelingTimers_.find(timer) == cancelingTimers_.end()) //重复且要删除的集合中未找到
    {
      it.second->restart(now); //重新设置超时时间
      insert(it.second); //重新插入 前面erase掉了
    }
    else
    {
      // FIXME move to a free list
      delete it.second; // FIXME: no delete please //不管是哪一种都要删除了 裸指针并不好 unique_ptr更优
    }
  }

  if (!timers_.empty())
  {
    nextExpire = timers_.begin()->second->expiration(); //最小的期望时间数
  }

  if (nextExpire.valid()) //最小的时间项数有效的话
  {
    resetTimerfd(timerfd_, nextExpire); //重置定时器
  }
}

这里便用到了cancelingTimers_

最后就是TimerQueue的工作机制的核心,即getExpired,在触发可读时间后如何取出时间,这也是和时间轮最大的区别之一.

std::vector<TimerQueue::Entry> TimerQueue::getExpired(Timestamp now)
{
  assert(timers_.size() == activeTimers_.size());
  std::vector<Entry> expired;
  //UINTPTR_MAX为 uintptr_t 类型对象的最大值,为的是在时间相同的情况下放入所有时间相同的值 
  Entry sentry(now, reinterpret_cast<Timer*>(UINTPTR_MAX));
  TimerList::iterator end = timers_.lower_bound(sentry);
  assert(end == timers_.end() || now < end->first);
  std::copy(timers_.begin(), end, back_inserter(expired));
  timers_.erase(timers_.begin(), end);

  for (const Entry& it : expired)
  {
    ActiveTimer timer(it.second, it.second->sequence());
    size_t n = activeTimers_.erase(timer); //activeTimers中删除项数
    assert(n == 1); (void)n;
  }

  assert(timers_.size() == activeTimers_.size());
  return expired;
}

说完了成员函数,还有一点值得一提,就是数据结构的选取,Entry的选择是std::pair<Timestamp, Timer> Entry,这样可以保证在Timestamp相同时(这也是不使用map的原因),能够在容器中占用两个地方,因为地址一定不同(对象不同的话).,为什么不用hash_map呢,用库提供的hash函数我们就可以保证不同的对象有不同的hash值,原因就是我们需要数据结构有序,当然库优先队列是不行的,因为没办法删除对象.至于mulity_map,没必要,能用set就没必要用那个.*

总结

说两点有意思的地方

1. Timerqueue选取的时间触发时超时时间时取set去前几项,这是与timewheel不同的一点.
2. activeTimers是否有必要?我看了很久,也查了资料始终没有搞清楚这个问题.

最后的最后,
重要的事情说三遍!

事件驱动

事件驱动

事件驱动