nginx中的定时器源码分析与测试-阿里云开发者社区

在nginx中，定时器是由红黑树来实现的。

有以下几个定时器的接口

init_timer 初始化定时器（初始化红黑树）

add_timer 添加定时器（红黑树左侧时间小，右侧时间大。当时间出现重复的时候，插入右侧）

del_timer 删除定时器

find_nearest_expire_timer 查找时间最近的定时器(红黑树中最左侧的节点)

expire_timer 到期的定时器(执行定时事件，并删除红黑树中对应的节点)

一、nignx中的定时器

rbt-timer.h

#ifndef _MARK_RBT_
#define _MARK_RBT_
#include <stdio.h>
#include <stdint.h> // 整数
#include <unistd.h> // usleep
#include <stdlib.h> // malloc 注意需要强转
#include <stddef.h> //offsetof
#if defined(__APPLE__)
#include <AvailabilityMacros.h>
#include <sys/time.h>
#include <mach/task.h>
#include <mach/mach.h>
#else
#include <time.h>
#endif
#include "rbtree.h"
ngx_rbtree_t              timer;
static ngx_rbtree_node_t  sentinel;//哨兵节点
typedef struct timer_entry_s timer_entry_t;
typedef void (*timer_handler_pt)(timer_entry_t *ev);
struct timer_entry_s {
    ngx_rbtree_node_t rbnode;
    timer_handler_pt handler;
};
static uint32_t
current_time() {
  uint32_t t;
#if !defined(__APPLE__) || defined(AVAILABLE_MAC_OS_X_VERSION_10_12_AND_LATER)
  struct timespec ti;
  clock_gettime(CLOCK_MONOTONIC, &ti);
  t = (uint32_t)ti.tv_sec * 1000;
  t += ti.tv_nsec / 1000000;
#else
  struct timeval tv;
  gettimeofday(&tv, NULL);
  t = (uint32_t)tv.tv_sec * 1000;
  t += tv.tv_usec / 1000;
#endif
  return t;
}
//初始化定时器(初始化红黑树)
ngx_rbtree_t * init_timer() {
    ngx_rbtree_init(&timer, &sentinel, ngx_rbtree_insert_timer_value);
    return &timer;
}
//添加定时器(参数1：时间间隔 参数2：事件函数)
void add_timer(uint32_t msec, timer_handler_pt func) {
    timer_entry_t *te = malloc(sizeof(timer_entry_t));
    memset(te, 0, sizeof(timer_entry_t));
    te->handler = func;
    msec += current_time();
    printf("add_timer expire at msec = %u\n", msec);
    te->rbnode.key = msec;//把时间作为红黑树的key
    ngx_rbtree_insert(&timer, &te->rbnode);//rbtree中插入节点
}
//删除定时器(删除红黑树节点)
void del_timer(timer_entry_t *te) {
    ngx_rbtree_delete(&timer, &te->rbnode);
    free(te);
}
//找到时间最近的定时器（二叉树最左侧的节点）
int find_nearest_expire_timer() {
    ngx_rbtree_node_t  *node;
    if (timer.root == &sentinel) {//没有定时任务(如果红黑树根节点为哨兵节点，说明红黑树是空的,没有定时任务)
        return -1;
    }
    node = ngx_rbtree_min(timer.root, timer.sentinel);
    int diff = (int)node->key - (int)current_time();//时间差（事件还要等待多久,传给epoll_wait最后那个参数）
    return diff > 0 ? diff : 0;
}
void expire_timer() {
    timer_entry_t *te;
    ngx_rbtree_node_t *sentinel, *root, *node;
    sentinel = timer.sentinel;
    uint32_t now = current_time();
    for (;;) {
        root = timer.root;
        if (root == sentinel) break;//空的红黑树，直接退出
        node = ngx_rbtree_min(root, sentinel);
        if (node->key > now) break;//当前红黑树节点的时间大于当前时间，说明事件还没触发，直接退出
        printf("touch timer expire time=%u, now = %u\n", node->key, now);
        te = (timer_entry_t *) ((char *) node - offsetof(timer_entry_t, rbnode));//将红黑树节点转化为该node的定时器事件
        te->handler(te);//事件触发，直接调用事件函数
        ngx_rbtree_delete(&timer, &te->rbnode); //删除红黑树节点
        free(te);
    }
}
#endif

二、nignx中定时器测试

rbt-timer.c

#include <stdio.h>
#include <string.h>
#include <sys/epoll.h>
#include "rbt-timer.h"
void hello_world(timer_entry_t *te) {
    printf("hello world time = %u\n", te->rbnode.key);
}
int main()
{
    init_timer();
    add_timer(3000, hello_world);
    int epfd = epoll_create(1);
    struct epoll_event events[512];
    for (;;) {
        int nearest = find_nearest_expire_timer();
        int n = epoll_wait(epfd, events, 512, nearest);
        for (int i=0; i < n; i++) {
            // 
        }
        expire_timer();
    }
    return 0;
}

通过rbt-timer.h、rbt-timer.c、以及附件中的rbtree.h、rbtree.c可以直接编译运行测试

三、附件

rbtree.h

/*
 * Copyright (C) Igor Sysoev
 * Copyright (C) Nginx, Inc.
 */
#ifndef _NGX_RBTREE_H_INCLUDED_
#define _NGX_RBTREE_H_INCLUDED_
typedef unsigned int  ngx_rbtree_key_t;
typedef unsigned int  ngx_uint_t;
typedef int   ngx_rbtree_key_int_t;
typedef unsigned char u_char;
#ifndef NULL
    #define NULL ((void*)0)
#endif
typedef struct ngx_rbtree_node_s  ngx_rbtree_node_t;
struct ngx_rbtree_node_s {
    ngx_rbtree_key_t       key;
    ngx_rbtree_node_t     *left;
    ngx_rbtree_node_t     *right;
    ngx_rbtree_node_t     *parent;
    u_char                 color;
    u_char                 data;
};
typedef struct ngx_rbtree_s  ngx_rbtree_t;
typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,
    ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
struct ngx_rbtree_s {
    ngx_rbtree_node_t     *root;
    ngx_rbtree_node_t     *sentinel;
    ngx_rbtree_insert_pt   insert;
};
#define ngx_rbtree_init(tree, s, i)                                           \
    ngx_rbtree_sentinel_init(s);                                              \
    (tree)->root = s;                                                         \
    (tree)->sentinel = s;                                                     \
    (tree)->insert = i
void 
ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);
void
ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);
void
ngx_rbtree_insert_value(ngx_rbtree_node_t *root, ngx_rbtree_node_t *node,
    ngx_rbtree_node_t *sentinel);
void
ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *root,
    ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
ngx_rbtree_node_t *
ngx_rbtree_next(ngx_rbtree_t *tree,
    ngx_rbtree_node_t *node);
#define ngx_rbt_red(node)               ((node)->color = 1)
#define ngx_rbt_black(node)             ((node)->color = 0)
#define ngx_rbt_is_red(node)            ((node)->color)
#define ngx_rbt_is_black(node)          (!ngx_rbt_is_red(node))
#define ngx_rbt_copy_color(n1, n2)      (n1->color = n2->color)
/* a sentinel must be black */
#define ngx_rbtree_sentinel_init(node)  ngx_rbt_black(node)
static ngx_rbtree_node_t *
ngx_rbtree_min(ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
{
    while (node->left != sentinel) {
        node = node->left;
    }
    return node;
}
#endif /* _NGX_RBTREE_H_INCLUDED_ */

rbtree.c

/*
 * Copyright (C) Igor Sysoev
 * Copyright (C) Nginx, Inc.
 */
#include "rbtree.h"
/*
 * The red-black tree code is based on the algorithm described in
 * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
 */
static inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root,
    ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
static inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root,
    ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
void
ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
{
    ngx_rbtree_node_t  **root, *temp, *sentinel;
    /* a binary tree insert */
    root = &tree->root;
    sentinel = tree->sentinel;
    if (*root == sentinel) {
        node->parent = NULL;
        node->left = sentinel;
        node->right = sentinel;
        ngx_rbt_black(node);
        *root = node;
        return;
    }
    tree->insert(*root, node, sentinel);
    /* re-balance tree */
    while (node != *root && ngx_rbt_is_red(node->parent)) {
        if (node->parent == node->parent->parent->left) {
            temp = node->parent->parent->right;
            if (ngx_rbt_is_red(temp)) {
                ngx_rbt_black(node->parent);
                ngx_rbt_black(temp);
                ngx_rbt_red(node->parent->parent);
                node = node->parent->parent;
            } else {
                if (node == node->parent->right) {
                    node = node->parent;
                    ngx_rbtree_left_rotate(root, sentinel, node);
                }
                ngx_rbt_black(node->parent);
                ngx_rbt_red(node->parent->parent);
                ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
            }
        } else {
            temp = node->parent->parent->left;
            if (ngx_rbt_is_red(temp)) {
                ngx_rbt_black(node->parent);
                ngx_rbt_black(temp);
                ngx_rbt_red(node->parent->parent);
                node = node->parent->parent;
            } else {
                if (node == node->parent->left) {
                    node = node->parent;
                    ngx_rbtree_right_rotate(root, sentinel, node);
                }
                ngx_rbt_black(node->parent);
                ngx_rbt_red(node->parent->parent);
                ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
            }
        }
    }
    ngx_rbt_black(*root);
}
void
ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
    ngx_rbtree_node_t *sentinel)
{
    ngx_rbtree_node_t  **p;
    for ( ;; ) {
        p = (node->key < temp->key) ? &temp->left : &temp->right;
        if (*p == sentinel) {
            break;
        }
        temp = *p;
    }
    *p = node;
    node->parent = temp;
    node->left = sentinel;
    node->right = sentinel;
    ngx_rbt_red(node);
}
void
ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
    ngx_rbtree_node_t *sentinel)
{
    ngx_rbtree_node_t  **p;
    for ( ;; ) {
        /*
         * Timer values
         * 1) are spread in small range, usually several minutes,
         * 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
         * The comparison takes into account that overflow.
         */
        /*  node->key < temp->key */  //node 是要插入的节点,temp是树的节点，如果相等，就插入到右边.(也就是说，如果定时器的时间相等的话，定时事件后加入的就后触发)
        p = ((ngx_rbtree_key_int_t) (node->key - temp->key) < 0)
            ? &temp->left : &temp->right;
        if (*p == sentinel) {
            break;
        }
        temp = *p;
    }
    *p = node;
    node->parent = temp;
    node->left = sentinel;
    node->right = sentinel;
    ngx_rbt_red(node);
}
void
ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
{
    ngx_uint_t           red;
    ngx_rbtree_node_t  **root, *sentinel, *subst, *temp, *w;
    /* a binary tree delete */
    root = &tree->root;
    sentinel = tree->sentinel;
    if (node->left == sentinel) {
        temp = node->right;
        subst = node;
    } else if (node->right == sentinel) {
        temp = node->left;
        subst = node;
    } else {
        subst = ngx_rbtree_min(node->right, sentinel);
        if (subst->left != sentinel) {
            temp = subst->left;
        } else {
            temp = subst->right;
        }
    }
    if (subst == *root) {
        *root = temp;
        ngx_rbt_black(temp);
        /* DEBUG stuff */
        node->left = NULL;
        node->right = NULL;
        node->parent = NULL;
        node->key = 0;
        return;
    }
    red = ngx_rbt_is_red(subst);
    if (subst == subst->parent->left) {
        subst->parent->left = temp;
    } else {
        subst->parent->right = temp;
    }
    if (subst == node) {
        temp->parent = subst->parent;
    } else {
        if (subst->parent == node) {
            temp->parent = subst;
        } else {
            temp->parent = subst->parent;
        }
        subst->left = node->left;
        subst->right = node->right;
        subst->parent = node->parent;
        ngx_rbt_copy_color(subst, node);
        if (node == *root) {
            *root = subst;
        } else {
            if (node == node->parent->left) {
                node->parent->left = subst;
            } else {
                node->parent->right = subst;
            }
        }
        if (subst->left != sentinel) {
            subst->left->parent = subst;
        }
        if (subst->right != sentinel) {
            subst->right->parent = subst;
        }
    }
    /* DEBUG stuff */
    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;
    node->key = 0;
    if (red) {
        return;
    }
    /* a delete fixup */
    while (temp != *root && ngx_rbt_is_black(temp)) {
        if (temp == temp->parent->left) {
            w = temp->parent->right;
            if (ngx_rbt_is_red(w)) {
                ngx_rbt_black(w);
                ngx_rbt_red(temp->parent);
                ngx_rbtree_left_rotate(root, sentinel, temp->parent);
                w = temp->parent->right;
            }
            if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
                ngx_rbt_red(w);
                temp = temp->parent;
            } else {
                if (ngx_rbt_is_black(w->right)) {
                    ngx_rbt_black(w->left);
                    ngx_rbt_red(w);
                    ngx_rbtree_right_rotate(root, sentinel, w);
                    w = temp->parent->right;
                }
                ngx_rbt_copy_color(w, temp->parent);
                ngx_rbt_black(temp->parent);
                ngx_rbt_black(w->right);
                ngx_rbtree_left_rotate(root, sentinel, temp->parent);
                temp = *root;
            }
        } else {
            w = temp->parent->left;
            if (ngx_rbt_is_red(w)) {
                ngx_rbt_black(w);
                ngx_rbt_red(temp->parent);
                ngx_rbtree_right_rotate(root, sentinel, temp->parent);
                w = temp->parent->left;
            }
            if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
                ngx_rbt_red(w);
                temp = temp->parent;
            } else {
                if (ngx_rbt_is_black(w->left)) {
                    ngx_rbt_black(w->right);
                    ngx_rbt_red(w);
                    ngx_rbtree_left_rotate(root, sentinel, w);
                    w = temp->parent->left;
                }
                ngx_rbt_copy_color(w, temp->parent);
                ngx_rbt_black(temp->parent);
                ngx_rbt_black(w->left);
                ngx_rbtree_right_rotate(root, sentinel, temp->parent);
                temp = *root;
            }
        }
    }
    ngx_rbt_black(temp);
}
static inline void
ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
    ngx_rbtree_node_t *node)
{
    ngx_rbtree_node_t  *temp;
    temp = node->right;
    node->right = temp->left;
    if (temp->left != sentinel) {
        temp->left->parent = node;
    }
    temp->parent = node->parent;
    if (node == *root) {
        *root = temp;
    } else if (node == node->parent->left) {
        node->parent->left = temp;
    } else {
        node->parent->right = temp;
    }
    temp->left = node;
    node->parent = temp;
}
static inline void
ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
    ngx_rbtree_node_t *node)
{
    ngx_rbtree_node_t  *temp;
    temp = node->left;
    node->left = temp->right;
    if (temp->right != sentinel) {
        temp->right->parent = node;
    }
    temp->parent = node->parent;
    if (node == *root) {
        *root = temp;
    } else if (node == node->parent->right) {
        node->parent->right = temp;
    } else {
        node->parent->left = temp;
    }
    temp->right = node;
    node->parent = temp;
}
ngx_rbtree_node_t *
ngx_rbtree_next(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
{
    ngx_rbtree_node_t  *root, *sentinel, *parent;
    sentinel = tree->sentinel;
    if (node->right != sentinel) {
        return ngx_rbtree_min(node->right, sentinel);
    }
    root = tree->root;
    for ( ;; ) {
        parent = node->parent;
        if (node == root) {
            return NULL;
        }
        if (node == parent->left) {
            return parent;
        }
        node = parent;
    }
}

nginx中的定时器源码分析与测试

一、nignx中的定时器

二、nignx中定时器测试

三、附件

热门文章

最新文章

相关课程

相关电子书

相关实验场景