node源码粗读（6）：从./lib/timers.js来看timers相关API底层实现

[xtx1130]

这篇文章主要从node源码的./lib/timers.js 入手，历经./lib/internal/timers.js、./src/timer_wrap.cc，并最终下沉到./deps/uv/src/unix/timer.c来叙述整体timers的实现流程。

前言

在阅读 ./lib/timers.js代码的时候，首先映入眼帘的便是如下这几行注释：

// ╔════ > Object Map
// ║
// ╠══
// ║ refedLists: { '40': { }, '320': { etc } } (keys of millisecond duration)
// ╚══          ┌─────────┘
//              │
// ╔══          │
// ║ TimersList { _idleNext: { }, _idlePrev: (self), _timer: (TimerWrap) }
// ║         ┌────────────────┘
// ║    ╔══  │                              ^
// ║    ║    { _idleNext: { },  _idlePrev: { }, _onTimeout: (callback) }
// ║    ║      ┌───────────┘
// ║    ║      │                                  ^
// ║    ║      { _idleNext: { etc },  _idlePrev: { }, _onTimeout: (callback) }
// ╠══  ╠══
// ║    ║
// ║    ╚════ >  Actual JavaScript timeouts
// ║
// ╚════ > Linked List

我们按照注释的引导，一点一点把整体的timers.js结构扒开，看它究竟做了什么。

timers中的双向链表

按照注释中的引子，我们先来看一下TimersList究竟是什么样子的，目光直接移向下面这段代码：

function TimersList(msecs, unrefed) {
  this._idleNext = this; // Create the list with the linkedlist properties to
  this._idlePrev = this; // prevent any unnecessary hidden class changes.
  this._unrefed = unrefed;
  this.msecs = msecs;
  this.nextTick = false;
  const timer = this._timer = new TimerWrap();
  timer._list = this;
  if (unrefed === true)
    timer.unref();
  timer.start(msecs);
  timer[kOnTimeout] = listOnTimeout;
}

这里是TimersList的实现代码，不管其他的，看到this.xxxNext和this.xxxPrev，第一时间就会想到双向链表。没错，TimersList就是一个双向链表，那么它的两端分别连接的是什么呢？

function insert(item, unrefed) {
  const msecs = item._idleTimeout;
  if (msecs < 0 || msecs === undefined) return;
  item._idleStart = TimerWrap.now();
  const lists = unrefed === true ? unrefedLists : refedLists;
  var list = lists[msecs];
  if (list === undefined) {
    debug('no %d list was found in insert, creating a new one', msecs);
    lists[msecs] = list = new TimersList(msecs, unrefed);
  }
  //other codes...
  L.append(list, item);
  assert(!L.isEmpty(list)); 
}

大家可以看一下这个insert函数，其中实现了TimersList的实例化，其中：

const lists = unrefed === true ? unrefedLists : refedLists;
 var list = lists[msecs];
  if (list === undefined) {
    debug('no %d list was found in insert, creating a new one', msecs);
    lists[msecs] = list = new TimersList(msecs, unrefed);
  }

这几句话基本涵盖了刚才注释里面的refedLists以及TimersList,这里可以看出referedLists是一个对象，而对象的key是变量msecs, value则对应一个TimersList。
之后的L.append(list, item);，L是来自于./lib/internal/linkedlist.js中操作双向链表的方法，append则是在链表后面插入一个元素，而list是实例化的TimersList，所以也就是在TimersList后插入新的item，到此为止，整体结构如下所示：

refedLists = {
[msecs0]: item<->item<->item<->item<->item,//<->代指双向链表TimersList
[msecs1]: item<->item<->item<->item<->item,
[msecs2]: item<->item<->item<->item<->item
......
}

msecs是什么

在理解了注释的大体结构之后，那么下一个疑问就来了，msecs到底指的是什么？

通过翻阅./lib/timers.js的代码可以找到几个和msecs强相关的地方：

function insert(item, unrefed) {
  const msecs = item._idleTimeout;
  if (msecs < 0 || msecs === undefined) return;
  //...
  if (list === undefined) {
    debug('no %d list was found in insert, creating a new one', msecs);
    lists[msecs] = list = new TimersList(msecs, unrefed);
  }
  //...
}
function TimersList(msecs, unrefed) {
  //...
  this._unrefed = unrefed;
  this.msecs = msecs;
  this.nextTick = false;
  //...
}

从这些代码可以看出来msecs的起源实际是item._idleTimeout，而item根据如下几个地方溯源：

const timerInternals = require('internal/timers');
const Timeout = timerInternals.Timeout;
const timeout = new Timeout(callback, after, args, false);//实例化之后传入到item中了
const active = exports.active = function(item) {
  insert(item, false);
};
active(timeout);

直接跟进到./lib/internal/timers.js,
其中有这样一段代码：

function Timeout(callback, after, args, isRepeat) {
  //...
  this._onTimeout = callback;
  this._idleTimeout = after;
  //...
}

所以，msesc其实是Timeout的第二个参数--after，即setTimeout API中的第二个参数，延迟几秒执行，_onTimeout就是最终要执行的callback
读完这个章节，我们的整体结构可以修改成：

// <->代指双向链表TimersList,
// 10/100/1000分别为延迟10/100/1000毫秒后执行
refedLists = {
10: item<->item<->item<->item<->item,
100: item<->item<->item<->item<->item,
1000: item<->item<->item<->item<->item
......
}

TimersList的TimerWrap

根据上面的描述，基本上整体时间链已经比较清晰了：setTimout(callback,time) 会根据time来向refedLists[time]中append一个新的item。那么这个TimersList的机制是什么样的呢？

这里我们要从一个细节入手，在定义TimersList的地方，有一行代码：

const {
  Timer: TimerWrap,
  setImmediateCallback,
} = process.binding('timer_wrap');
function TimersList(msecs, unrefed) {
  //...
  const timer = this._timer = new TimerWrap();
  timer._list = this;
  //...
  timer.start(msecs);
  timer[kOnTimeout] = listOnTimeout;
  //...
}

从这里我们可以看到TimersList有一个属性_timer，而这个_timer的来源又很隐蔽，是通过binding方法挂载进来的内置api。在这种情况下，矛头直接指向./src/timer_wrap.cc中一探究竟。

class TimerWrap : public HandleWrap {
 public:
   static void Initialize(Local<Object> target,
                         Local<Value> unused,
                         Local<Context> context) {
   // ...
   env->SetTemplateMethod(constructor, "now", Now);
   AsyncWrap::AddWrapMethods(env, constructor);
   env->SetProtoMethod(constructor, "close", HandleWrap::Close);
   env->SetProtoMethod(constructor, "ref", HandleWrap::Ref);
   env->SetProtoMethod(constructor, "unref", HandleWrap::Unref);
   env->SetProtoMethod(constructor, "hasRef", HandleWrap::HasRef);
   env->SetProtoMethod(constructor, "start", Start);
   env->SetProtoMethod(constructor, "stop", Stop);
   //...
   }
   NODE_BUILTIN_MODULE_CONTEXT_AWARE(timer_wrap, node::TimerWrap::Initialize)

可以看到，在node中构造了timer_wrap的构造函数，其中包含了若干方法和属性，在这里我们先重点看一下start方法：

  TimerWrap(Environment* env, Local<Object> object)
      : HandleWrap(env,
                   object,
                   reinterpret_cast<uv_handle_t*>(&handle_),
                   AsyncWrap::PROVIDER_TIMERWRAP) {
    int r = uv_timer_init(env->event_loop(), &handle_);
    CHECK_EQ(r, 0);
  }
  static void Start(const FunctionCallbackInfo<Value>& args) {
    TimerWrap* wrap = Unwrap<TimerWrap>(args.Holder());

    CHECK(HandleWrap::IsAlive(wrap));

    int64_t timeout = args[0]->IntegerValue();
    int err = uv_timer_start(&wrap->handle_, OnTimeout, timeout, 0);
    args.GetReturnValue().Set(err);
  }

首先，TimerWrap会执行uv_timer_init(env->event_loop(), &handle_)。uv_timer_init为libuv中定时器的初始化函数，它的参数有两个：第一个参数是定时器初始化时候的主event_loop，第二个参数为指向uv_timer_t的指针。一般以handle命名（因为uv_timer_t为uv_handle_t的子类，uv_handle_t的结构体声明中又包含了uv_loop_t），handle相当于uv_timer_start之后的唯一标识，如下我所了解到的一些用法：

• handle->flags 标识此timer是否已经结束
• handle->type 标识此timer的类型，可选类型有：UV_TCP、UV_NAMED_PIPE、UV_TTY
• handle->timer_cb libuv需要执行的回调函数
• handle->timeout 定时执行的绝对时间
• handle->repeat 是否重复执行
• handle->start_id 定时器启动的id，初始化在loop->timer_counter(uv_loop_t * loop)中,初始为0，逐渐递增

我对libuv也不是十分了解，如上是我大致了解的handle的用途，还希望大家给予补充。
uv_timer_start四个参数的意义可以在 ./deps/uv/src/unix/timer.c中找到，分别为：handle、回调、延迟执行的时间、是否重复执行。
问题马上迎刃而解了，下面我们只需要关注一下OnTimeout：

  static void OnTimeout(uv_timer_t* handle) {
    TimerWrap* wrap = static_cast<TimerWrap*>(handle->data);
    Environment* env = wrap->env();
    HandleScope handle_scope(env->isolate());
    Context::Scope context_scope(env->context());
    wrap->MakeCallback(kOnTimeout, 0, nullptr);
  }

在这里有一个比较重要的过程，就是handle->data,这里的handle指向的是uv_timer_t，而这个data则是通过node中的HandleWrap传递给libuv的handle_warp.cc：

class TimerWrap : public HandleWrap{}
HandleWrap::HandleWrap(Environment* env,
                       Local<Object> object,
                       uv_handle_t* handle,
                       AsyncWrap::ProviderType provider)
    : AsyncWrap(env, object, provider),
      state_(kInitialized),
      handle_(handle) {
  handle_->data = this;// 在这里把上下文传递给libuv
  HandleScope scope(env->isolate());
  Wrap(object, this);
  env->handle_wrap_queue()->PushBack(this);
}

所以接下来就可以通过wrap->MakeCallback调用MakeCallback实现对js函数的调用。
通过这一章节的叙述，可以基本缕清refedLists的整体结构：

// <->代指双向链表TimersList,
// 10/100/1000分别为延迟10/100/1000毫秒后执行
// TimerWrap中为10毫秒后待执行的链表
refedLists = {
10: TimerWrap._list (TimersList(item<->item<->item<->item<->item)),
100: TimerWrap._list (TimersList(item<->item<->item<->item<->item)),
1000: TimerWrap._list (TimersList(item<->item<->item<->item<->item))
......
}

执行阶段

沿用刚才的逻辑，其实暴露出来的timer.start方法就会调用uv_timer_start来启动定时循环处理，由此可见，在TimersList中：

function TimersList(msecs, unrefed) {
  // ...
  timer.start(msecs);
  timer[kOnTimeout] = listOnTimeout;
}

随着每一个TimersList的注册，会启动uv_timer_start，来开始整体的一个事件循环，拿上面的总结举例子来说：

refedLists = {
10: TimerWrap._list (TimersList(item<->item<->item<->item<->item))
......
}

当refedLists中注册了10毫秒后需要执行的TimersList的时候，旋即启动uv_timer_start，每隔十秒执行timer[kOnTimeout] = listOnTimeout即listOnTimeout，下面是整个完整的回调函数调用链：

function listOnTimeout() {
  // ...
  while (timer = L.peek(list)) {
  // ...
  }
  // ...
  tryOnTimeout(timer, list);
}

function tryOnTimeout(timer, list) {
  // ...
  try {
    ontimeout(timer);
    threw = false;
  } finally {
  // ...
  }
  // ...
}

function ontimeout(timer) {
  // ...
  if (!args)
    timer._onTimeout();
  else
    Reflect.apply(timer._onTimeout, timer, args);
  if (timer._repeat)
    rearm(timer);
}

刚才经过分析，大家应该还对_onTimeout有印象吧？没错，这就是最后要执行的callback，也就是listOnTimeout最终执行了setTimeout方法的callback。至此，整个timers的整体流程就分析结束了。

by 小菜

[xtx1130]

在此次pr: timers: refactor timer list processing 之后，listOnTimeout 流程转移到了processTimers 中，并最终由 timer_wrap.cc中的SetupTimers注册，底层还是由OnTimeout调用运行

[sunstdot]

为毛没提时间轮跟链表 结合的效率啊大佬， 那个时间更新那 看不懂，求给科普

[xtx1130]

@sunstdot chromium中没有用这种形式的链表，chromium的setTimeout都是单个执行的，不是这种串行的。理论上来说node效率应该是高的，不知道chromium基于什么原因没有这么做，所以也不好品头论足了。
时间更新的机制和libuv有关，libuv在每次循环的时候都会通过uv__update_time不断更新时间为loop->time，提供给event-loop使用，而uv_timer_start 相当于在本次循环的时间点注册了一个回调，在loop->time+timeout之后会调用回调。所以当uv__update_time时间更新到loop->time+timeout就会直接触发相应的回调（OnTimeout ）了。