pjlib-内存池-计时器解析

开始

PJSIP是一个开放源代码的SIP协议栈。它支持多种SIP的扩展功能，目前可说算是最流行的sip协议栈之一了。

构成

• PJSIP - Open Source SIP Stack[开源的SIP协议栈]
• PJMEDIA - Open Source Media Stack[开源的媒体栈]
• PJNATH - Open Source NAT Traversal Helper Library[开源的NAT-T辅助库]
• PJLIB-UTIL - Auxiliary Library[辅助工具库]
• PJLIB - Ultra Portable Base Framework Library[基础框架库]

PJLIB

要理解好PJSIP，就不得不先说说PJLIB，PJLIB算的上是这个库中最基础的库，正是这个
库的优美实现，才让PJSIP变得如此优越。

运行的平台有：

• Win32/x86 (Win95/98/ME, NT/2000/XP/2003, mingw).
• arm, WinCE and Windows Mobile.
• Linux/x86, (user mode and as kernel module(!)).
• Linux/alpha
• Solaris/ultra.
• MacOS X/powerpc
• RTEMS (x86 and powerpc).

PJLIB提供了一系列特征，涉及到：

• 非动态内存分配[No Dynamic Memory Allocations]

  实现了内存池，获取内存是从与分配的内存池中获取，高性能程序多会自己构造内存池
  ，后面我们会解释该内存池的使用以及基本的原理。根据作者的比较，是常规的 malloc(
  )/free()函数的30倍。

• OS抽象[Operating System Abstraction]

  • 线程[Threads.]
  • 线程本地存储[Thread Local Storage.]
  • 互斥[Mutexes.]
  • 信号灯[Semaphores.]
  • 原子变量[Atomic Variables.]
  • 临届区[Critical sections.]
  • 锁对象[Lock Objects.]
  • 事件对象[Event Object.]
  • 时间管理[Time Data Type and Manipulation.]
  • 高解析的时间戳[High Resolution Timestamp.]

• 低层的网络相关IO[Low-Level Network I/O]

  • Socket抽象[Socket Abstraction.]
  • 网络地址解析[Network Address Resolution.]
  • 实现针对Socket的select API[Socket select() API.]

• 时间管理[Timer Management]

  这主要涉及到两个部分，一个时定时器的管理，还有就是时间解析的精度(举例说来，就是能精确到哪个时间等级，比如 POSIX sleep(),就只能以秒为单位，而使用select()则可以实现毫秒级别的计时)

• 各种数据结构[Various Data Structures]

  • 针对字符串的操作[String Operations]
  • 数组辅助[Array helper]
  • Hash表[Hash Tabl]
  • 链表[Linked List]
  • 红黑平衡树[Red/Black Balanced Tree]

• 异常处理[Exception Construct]

• LOG机制[Logging Facility]

• 随机数以及GUID的产生[Random and GUID Generation]

内存池模块

没有动态分配内存，PJLIB的中心思想是，为了使应用程序尽可能快地运行，它根本不应该使用malloc（），而应该从预分配的存储池中获取内存。使用此方法可以优化的一些：

• 复杂度[alloc() is a O(1) operation.]
• no mutex is used inside alloc(). It is assumed that synchronization will be used in higher abstraction by application anyway.
• no free() is required. All chunks will be deleted when the pool is destroyed.

函数

函数名	说明
pj_init()	初始化PJ库。在使用库之前，必须先调用此函数。此函数的目的是初始化静态库数据（例如用于随机字符串生成的字符表），以及初始化依赖于操作系统的功能（例如Windows中的WSAStartup（））。
pj_caching_pool_init()	Create the pool factory.创建池工厂
pj_caching_pool_destroy()	destroy caching pool.销毁缓存池
pj_pool_create()	Must create pool before we can allocate anything.必须创建池在我们分配前
pj_pool_release()	释放池内存
pj_pool_alloc()	allocate some memory chunks,分配内存

源代码解析

首先是几个结构体的介绍：

struct pj_pool_t

内存池的结构

/**
 * This structure describes the memory pool. Only implementors of pool factory
 * need to care about the contents of this structure.
 */
struct pj_pool_t
{
    PJ_DECL_LIST_MEMBER(struct pj_pool_t);  /**< Standard list elements.    */

    /** Pool name */
    char	    obj_name[PJ_MAX_OBJ_NAME];

    /** Pool factory. */
    pj_pool_factory *factory;

    /** Data put by factory */
    void	    *factory_data;

    /** Current capacity allocated by the pool. */
    pj_size_t	    capacity;

    /** Size of memory block to be allocated when the pool runs out of memory */
    pj_size_t	    increment_size;

    /** List of memory blocks allcoated by the pool. */
    pj_pool_block   block_list;

    /** The callback to be called when the pool is unable to allocate memory. */
    pj_pool_callback *callback;

};

PJ_MAX_OBJ_NAME = 32，就是说内存池的名称大小要在32个字符以内

increment_size 是当空间不足时，扩容每个block的大小，比如increment=4,申请9时会，给出4*3个block并将这3个block合并

上面有个链表结构：

#define PJ_DECL_LIST_MEMBER(type)                       \
                                   /** List @a prev. */ \
                                   type *prev;          \
                                   /** List @a next. */ \
                                   type *next 

struct pj_list
{
    PJ_DECL_LIST_MEMBER(void);
};

看传入的类型，分配对应类型的链表。

struct pj_pool_block

内存池块block结构：

typedef struct pj_pool_block
{
    PJ_DECL_LIST_MEMBER(struct pj_pool_block);  /**< List's prev and next.  */
    unsigned char    *buf;                      /**< Start of buffer.       */
    unsigned char    *cur;                      /**< Current alloc ptr.     */
    unsigned char    *end;                      /**< End of buffer.         */
} pj_pool_block;

struct pj_caching_pool

缓存池

/**
 * Declaration for caching pool. Application doesn't normally need to
 * care about the contents of this struct, it is only provided here because
 * application need to define an instance of this struct (we can not allocate
 * the struct from a pool since there is no pool factory yet!).
 */
struct pj_caching_pool 
{
    /** Pool factory interface, must be declared first. */
    pj_pool_factory factory;

    /** Current factory's capacity, i.e. number of bytes that are allocated
     *  and available for application in this factory. The factory's
     *  capacity represents the size of all pools kept by this factory
     *  in it's free list, which will be returned to application when it
     *  requests to create a new pool.
     *  当前工厂的容量大小，工厂容量代表该工厂在空闲列表中持有的所有池的大小
     */
    pj_size_t	    capacity;

    /** Maximum size that can be held by this factory. Once the capacity
     *  has exceeded @a max_capacity, further #pj_pool_release() will
     *  flush the pool. If the capacity is still below the @a max_capacity,
     *  #pj_pool_release() will save the pool to the factory's free list.
     *  该工厂空闲容量的最大大小
     */
    pj_size_t       max_capacity;

    /**
     * Number of pools currently held by applications. This number gets
     * incremented everytime #pj_pool_create() is called, and gets
     * decremented when #pj_pool_release() is called.
     * 应用持有池数量
     */
    pj_size_t       used_count;

    /**
     * Total size of memory currently used by application.
     * 应用使用地内存大小
     */
    pj_size_t	    used_size;

    /**
     * The maximum size of memory used by application throughout the life
     * of the caching pool.
     * 在缓存池的整个生命周期中，应用程序使用的最大内存大小
     */
    pj_size_t	    peak_used_size;

    /**
     * Lists of pools in the cache, indexed by pool size.
     * 缓存池中的池列表
     */
    pj_list	    free_list[PJ_CACHING_POOL_ARRAY_SIZE];

    /**
     * List of pools currently allocated by applications.
     * 当前应用分配的池列表
     */
    pj_list	    used_list;

    /**
     * Internal pool.
     */
    char	    pool_buf[256 * (sizeof(long) / 4)];

    /**
     * Mutex.
     * 互斥锁
     */
    pj_lock_t	   *lock;
};

pj_list是一个双向链表结构,记录前后节点.free_list大小为16，就是说有16条链表结构。free_list是空闲池列表，表示该表中的内存池处于空闲状态，used_list应用分配的内存池列表也就是当前正在使用的内存池列表。capacity表示当前空闲池的容量大小，max_capacity表示空闲池容量的最大大小。

struct pj_pool_factory

/**
 * This structure contains the declaration for pool factory interface.
 */
struct pj_pool_factory
{
    /**
     * Memory pool policy.
     * 内存池策略
     */
    pj_pool_factory_policy policy;

    /**
    * Create a new pool from the pool factory.[从工厂中创建新池]
    *
    * @param factory	The pool factory.[工厂]
    * @param name	the name to be assigned to the pool. The name should 
    *			not be longer than PJ_MAX_OBJ_NAME (32 chars), or 
    *			otherwise it will be truncated.[池名称]
    * @param initial_size the size of initial memory blocks taken by the pool.
    *			Note that the pool will take 68+20 bytes for 
    *			administrative area from this block.[池初始化分配到的大小]
    * @param increment_size the size of each additional blocks to be allocated
    *			when the pool is running out of memory. If user 
    *			requests memory which is larger than this size, then 
    *			an error occurs.
    *			Note that each time a pool allocates additional block, 
    *			it needs 20 bytes (equal to sizeof(pj_pool_block)) to 
    *			store some administrative info.
    * [池内存不足时要分配的每个其他块的大小。 而且需要20个字节存储一些管理信息]
    * @param callback	Cllback to be called when error occurs in the pool.
    *			Note that when an error occurs during pool creation, 
    *			the callback itself is not called. Instead, NULL 
    *			will be returned.
    *
    * @return the memory pool, or NULL.
    */
    pj_pool_t*	(*create_pool)( pj_pool_factory *factory,
				const char *name,
				pj_size_t initial_size, 
				pj_size_t increment_size,
				pj_pool_callback *callback);

    /**
     * Release the pool to the pool factory.
     * [释放池到工厂]
     * @param factory	The pool factory.
     * @param pool	The pool to be released.
    */
    void (*release_pool)( pj_pool_factory *factory, pj_pool_t *pool );

    /**
     * Dump pool status to log.
     * [转储池状态记录]
     *
     * @param factory	The pool factory.
     */
    void (*dump_status)( pj_pool_factory *factory, pj_bool_t detail );

    /**
     * This is optional callback to be called by allocation policy when
     * it allocates a new memory block. The factory may use this callback
     * for example to keep track of the total number of memory blocks
     * currently allocated by applications.
     * [分配策略在分配新内存时的回调]
     * @param factory	    The pool factory.
     * @param size	    Size requested by application.
     *
     * @return		    MUST return PJ_TRUE, otherwise the block
     *                      allocation is cancelled.
     */
    pj_bool_t (*on_block_alloc)(pj_pool_factory *factory, pj_size_t size);

    /**
     * This is optional callback to be called by allocation policy when
     * it frees memory block. The factory may use this callback
     * for example to keep track of the total number of memory blocks
     * currently allocated by applications.
     * [分配策略在释放内存时的回调]
     * @param factory	    The pool factory.
     * @param size	    Size freed.
     */
    void (*on_block_free)(pj_pool_factory *factory, pj_size_t size);

};

struct pj_pool_factory_policy

缓存池工厂策略

typedef struct pj_pool_factory_policy
{
    /**
     * Allocate memory block (for use by pool). This function is called
     * by memory pool to allocate memory block.
     * 
     * @param factory	Pool factory.
     * @param size	The size of memory block to allocate.
     *
     * @return		Memory block.
     * [分配内存]
     */
    void* (*block_alloc)(pj_pool_factory *factory, pj_size_t size);

    /**
     * Free memory block.
     *
     * @param factory	Pool factory.
     * @param mem	Memory block previously allocated by block_alloc().
     * @param size	The size of memory block.
     * [释放内存]
     */
    void (*block_free)(pj_pool_factory *factory, void *mem, pj_size_t size);

    /**
     * Default callback to be called when memory allocation fails.
     * [分配内存失败时的回调]
     */
    pj_pool_callback *callback;

    /**
     * Option flags.
     */
    unsigned flags;

} pj_pool_factory_policy;

pj_caching_pool_init()

初始化缓存池

/** 创建池工厂
* @param cp  缓存池
* @param policy 池工厂策略 NULL默认
* @param max_capacity 池容量大小
*/
PJ_DEF(void) pj_caching_pool_init( pj_caching_pool *cp, 
				   const pj_pool_factory_policy *policy,
				   pj_size_t max_capacity)
{
    int i;
    pj_pool_t *pool;

    PJ_CHECK_STACK();

    pj_bzero(cp, sizeof(*cp));
    // 设置池容量
    cp->max_capacity = max_capacity;
    // 初始化当前由应用程序分配的池列表
    pj_list_init(&cp->used_list);
    // 初始化缓存中的池列表
    for (i=0; i<PJ_CACHING_POOL_ARRAY_SIZE; ++i)
	pj_list_init(&cp->free_list[i]);
	
    // 如果策略为空，那么设置为默认策略
    if (policy == NULL) {
    	policy = &pj_pool_factory_default_policy;
    }
    // 将策略分配给池工厂
    pj_memcpy(&cp->factory.policy, policy, sizeof(pj_pool_factory_policy));
    // 创建新池的方法
    cp->factory.create_pool = &cpool_create_pool;
    // 释放池的方法
    cp->factory.release_pool = &cpool_release_pool;
    // 转储池状态log记录
    cp->factory.dump_status = &cpool_dump_status;
    // 分配内存的回调
    cp->factory.on_block_alloc = &cpool_on_block_alloc;
    // 释放内存的回调
    cp->factory.on_block_free = &cpool_on_block_free;
	
    pool = pj_pool_create_on_buf("cachingpool", cp->pool_buf, sizeof(cp->pool_buf));
    pj_lock_create_simple_mutex(pool, "cachingpool", &cp->lock);
}

pj_list_init，对链表进行初始化

/**
 * Initialize the list.
 * Initially, the list will have no member, and function pj_list_empty() will
 * always return nonzero (which indicates TRUE) for the newly initialized 
 * list.
 *
 * @param node The list head.
 */
PJ_INLINE(void) pj_list_init(pj_list_type * node)
{
    ((pj_list*)node)->next = ((pj_list*)node)->prev = node;
}

将当前节点前后节点都指向当前节点。

policy，管理策略，工厂只是用来管理内存池对象，对于如何分配内存（有kmalloc,malloc,new），则由策略组件来实现,默认是malloc.但是C 里并没有new，默认地分配块函数如下：

static void *default_block_alloc(pj_pool_factory *factory, pj_size_t size)
{
  void *p;

  PJ_CHECK_STACK();

  if (factory->on_block_alloc)
  {
    int rc;
    rc = factory->on_block_alloc(factory, size);
    if (!rc)
      return NULL;
  }

  p = malloc(size + (SIG_SIZE << 1));

  if (p == NULL)
  {
    if (factory->on_block_free)
      factory->on_block_free(factory, size);
  }
  else
  {
    /* Apply signature when PJ_SAFE_POOL is set. It will move
	 * "p" pointer forward.
	 */
    APPLY_SIG(p, size);
  }

  return p;
}

pj_pool_create()

创建新池的函数指向了cpool_create_pool:

static pj_pool_t *cpool_create_pool(pj_pool_factory *pf,
                                    const char *name,
                                    pj_size_t initial_size,
                                    pj_size_t increment_sz,
                                    pj_pool_callback *callback)
{
  pj_caching_pool *cp = (pj_caching_pool *)pf;
  pj_pool_t *pool;
  int idx;

  PJ_CHECK_STACK();
  // 请求锁
  pj_lock_acquire(cp->lock);

  /* Use pool factory's policy when callback is NULL */
  if (callback == NULL)
  {
    callback = pf->policy.callback;
  }

  /** 
  * 为内存池的寻找合适大小，已经为你推荐了16个池的大小
  * 从找到大于等于initial_size并且最接近inintial_size大小
  * 如果大于这16个大小，那么就直接使用initial_size.
  * START_SIZE = 5
  * pool_sizes = {
        256, 512, 1024, 2048, 4096, 8192, 12288, 16384,
        20480, 24576, 28672, 32768, 40960, 49152, 57344, 65536};
    从12288为分界线，二分查找
  */
  if (initial_size <= pool_sizes[START_SIZE])
  {
    for (idx = START_SIZE - 1;
         idx >= 0 && pool_sizes[idx] >= initial_size;
         --idx)
      ;
    ++idx;
  }
  else
  {
    for (idx = START_SIZE + 1;
         idx < PJ_CACHING_POOL_ARRAY_SIZE &&
         pool_sizes[idx] < initial_size;
         ++idx)
      ;
  }

  /* Check whether there's a pool in the list. */
  /**
  * 如果initial_size>65536即idx==16,或者idx<16并且free_list[idx]为空时进入
  * 就是此时空闲池list中没有空闲的内存，所以要创建一个
  */
  if (idx == PJ_CACHING_POOL_ARRAY_SIZE || pj_list_empty(&cp->free_list[idx]))
  {
    /* No pool is available. */
    /* Set minimum size. */
    /**
    * 如果idx<16,将initial_size设置为推荐大小
    */
    if (idx < PJ_CACHING_POOL_ARRAY_SIZE)
      initial_size = pool_sizes[idx];

    /* Create new pool */
    pool = pj_pool_create_int(&cp->factory, name, initial_size,
                              increment_sz, callback);
    if (!pool)
    {
      pj_lock_release(cp->lock);
      return NULL;
    }
  }
  else
  {
    /**
    * 此时idx<16,并且free_list[idx]不为空时
    * 此时空闲池中存在空闲的内存
    * 直接将对应头节点的next节点给pool.
    */
    /* Get one pool from the list. */
    pool = (pj_pool_t *)cp->free_list[idx].next;
    /**
    * 将pool从free_list中移除
    */
    pj_list_erase(pool);

    /* Initialize the pool. */
    pj_pool_init_int(pool, name, increment_sz, callback);

    /* Update pool manager's free capacity. */
    // 因为空闲池被分配了，所以空闲池容量要减去被分配的容量
    cp->capacity -= pj_pool_get_capacity(pool);

    PJ_LOG(6, (pool->obj_name, "pool reused, size=%u", pool->capacity));
  }

  /* Put in used list. */
  // 将新分配的空闲池插入到used_list的最后
  pj_list_insert_before(&cp->used_list, pool);

  /* Mark factory data */
  pool->factory_data = (void *)(long)idx;

  /* Increment used count. */
  ++cp->used_count;

  // 释放锁	
  pj_lock_release(cp->lock);
  return pool;
}

pj_list_empty判断该节点是否为空：

/**
 * Check that the list is empty.
 *
 * @param node	The list head.
 *
 * @return Non-zero if the list is not-empty, or zero if it is empty.
 *
 */
PJ_INLINE(int) pj_list_empty(const pj_list_type * node)
{
    return ((pj_list*)node)->next == node;
}

这里判断node的下个节点是否指向自己，所以为空时应该返回true，但是这里注释说为空时返回0，应该是有问题的

上面的初始化池大小策略是：

PJ_DEF(pj_pool_t *) pj_pool_create_int(pj_pool_factory *f, const char *name,
                   pj_size_t initial_size,
                   pj_size_t increment_size,
                   pj_pool_callback *callback)
{
  pj_pool_t *pool;
  pj_pool_block *block;
  pj_uint8_t *buffer;

  PJ_CHECK_STACK();

  /* Size must be at least sizeof(pj_pool)+sizeof(pj_pool_block) */
  PJ_ASSERT_RETURN(initial_size >= sizeof(pj_pool_t) + sizeof(pj_pool_block),
                   NULL);

  /* If callback is NULL, set calback from the policy */
  if (callback == NULL)
    callback = f->policy.callback;

  /* Allocate initial block */
  buffer = (pj_uint8_t *)(*f->policy.block_alloc)(f, initial_size);
  if (!buffer)
    return NULL;

  /* Set pool administrative data. */
  pool = (pj_pool_t *)buffer;
  pj_bzero(pool, sizeof(*pool));

  pj_list_init(&pool->block_list);
  pool->factory = f;

  /* Create the first block from the memory. */
  block = (pj_pool_block *)(buffer + sizeof(*pool));
  block->cur = block->buf = ((unsigned char *)block) + sizeof(pj_pool_block);
  block->end = buffer + initial_size;
  // 将block插到block_list的后面
  pj_list_insert_after(&pool->block_list, block);

  pj_pool_init_int(pool, name, increment_size, callback);

  /* Pool initial capacity and used size */
  pool->capacity = initial_size;

  LOG((pool->obj_name, "pool created, size=%u", pool->capacity));
  return pool;
}

这里插入节点的函数实现：

PJ_IDEF(void) pj_list_insert_after(pj_list_type *pos, pj_list_type *node)
{
    ((pj_list*)node)->prev = pos;
    ((pj_list*)node)->next = ((pj_list*)pos)->next;
    ((pj_list*) ((pj_list*)pos)->next) ->prev = node;
    ((pj_list*)pos)->next = node;
}

分析其形成了循环链表，头指向尾指向头。

将分配的空间节点从空闲池中移除

/* Internal */
PJ_INLINE(void) pj_link_node(pj_list_type *prev, pj_list_type *next)
{
    ((pj_list*)prev)->next = next;
    ((pj_list*)next)->prev = prev;
}

PJ_IDEF(void) pj_list_erase(pj_list_type *node)
{
    pj_link_node( ((pj_list*)node)->prev, ((pj_list*)node)->next);

    /* It'll be safer to init the next/prev fields to itself, to
     * prevent multiple erase() from corrupting the list. See
     * ticket #520 for one sample bug.
     */
    pj_list_init(node);
}

实际上就是将头节点的next指向头节点的next的next，将头节点的next的next的pre指向头节点，然后让头节点的next的pre和next都指向自己，简而言之就是将头节点的next移出来，将其该节点孤立。

pj_list_insert_before(&cp->used_list, pool);

将分配的内存插入到used_list实现：

PJ_IDEF(void) pj_list_insert_before(pj_list_type *pos, pj_list_type *node)
{
    pj_list_insert_after(((pj_list*)pos)->prev, node);
}

这里pj_list_insert_after代码之前已经提及到，这里就是说将当前节点插入到used_list的最后末尾，也是一个循环双向链表。

pool_release_pool()

释放池pool_release_pool指向了cpool_release_pool.

static void cpool_release_pool(pj_pool_factory *pf, pj_pool_t *pool)
{
  pj_caching_pool *cp = (pj_caching_pool *)pf;
  unsigned pool_capacity;
  unsigned i;

  PJ_CHECK_STACK();

  PJ_ASSERT_ON_FAIL(pf && pool, return );

  pj_lock_acquire(cp->lock);

#if PJ_SAFE_POOL
  /* Make sure pool is still in our used list */
  if (pj_list_find_node(&cp->used_list, pool) != pool)
  {
    pj_assert(!"Attempt to destroy pool that has been destroyed before");
    return;
  }
#endif

  /* Erase from the used list. */
  pj_list_erase(pool);

  /* Decrement used count. */
  --cp->used_count;

  pool_capacity = pj_pool_get_capacity(pool);

  /* Destroy the pool if the size is greater than our size or if the total
     * capacity in our recycle list (plus the size of the pool) exceeds 
     * maximum capacity.
     * 当分配的这块内存大于之前预设内存大小最大值也就是大于pool_sizes[15] = 65536，
     * 或者空闲容量+当前释放的容量之和大于max空闲容量最大值时，直接销毁该内存池，
   . */
  if (pool_capacity > pool_sizes[PJ_CACHING_POOL_ARRAY_SIZE - 1] ||
      cp->capacity + pool_capacity > cp->max_capacity)
  {
    pj_pool_destroy_int(pool);
    pj_lock_release(cp->lock);
    return;
  }

  /* Reset pool. */
  PJ_LOG(6, (pool->obj_name, "recycle(): cap=%d, used=%d(%d%%)",
             pool_capacity, pj_pool_get_used_size(pool),
             pj_pool_get_used_size(pool) * 100 / pool_capacity));
  pj_pool_reset(pool);

  pool_capacity = pj_pool_get_capacity(pool);

  /*
     * Otherwise put the pool in our recycle list.
     */
  i = (unsigned)(unsigned long)pool->factory_data;

  pj_assert(i < PJ_CACHING_POOL_ARRAY_SIZE);
  if (i >= PJ_CACHING_POOL_ARRAY_SIZE)
  {
    /* Something has gone wrong with the pool. */
    pj_pool_destroy_int(pool);
    pj_lock_release(cp->lock);
    return;
  }
  // 将释放的放的内存是放到对应free_list对应大小的链表上
  pj_list_insert_after(&cp->free_list[i], pool);
  cp->capacity += pool_capacity;

  pj_lock_release(cp->lock);
}

查找该池是否在used_list里：

PJ_IDEF(pj_list_type*) pj_list_find_node(pj_list_type *list, pj_list_type *node)
{
    pj_list *p = (pj_list *) ((pj_list*)list)->next;
    while (p != list && p != node)
	p = (pj_list *) p->next;

    return p==node ? p : NULL;
}

因为是个双向循环链表，所以当p不等于头节点并且p不等于目标节点才进入循环，当循环退出，判断p是否等于目标节点即可。

销毁内存池pj_pool_destroy_int(pool):

PJ_DEF(void)
pj_pool_destroy_int(pj_pool_t *pool)
{
  pj_size_t initial_size;

  LOG((pool->obj_name, "destroy(): cap=%d, used=%d(%d%%), block0=%p-%p",
       pool->capacity, pj_pool_get_used_size(pool),
       pj_pool_get_used_size(pool) * 100 / pool->capacity,
       ((pj_pool_block *)pool->block_list.next)->buf,
       ((pj_pool_block *)pool->block_list.next)->end));
  // 将内存池重置会初始化的状态
  reset_pool(pool);
  initial_size = ((pj_pool_block *)pool->block_list.next)->end -
                 (unsigned char *)pool;
  // 将初始的内存释放
  if (pool->factory->policy.block_free)
    (*pool->factory->policy.block_free)(pool->factory, pool, initial_size);
}

重置内存池的实现：

/*
 * Reset the pool to the state when it was created.
 * All blocks will be deallocated except the first block. All memory areas
 * are marked as free.
 */
static void reset_pool(pj_pool_t *pool)
{
  pj_pool_block *block;

  PJ_CHECK_STACK();
  // 回到block_list的尾巴
  block = pool->block_list.prev;
  // 如果尾巴跟头是同一个就直接返回
  if (block == &pool->block_list)
    return;

  /* Skip the first block because it is occupying the same memory
       as the pool itself.
    */
  // 回到倒数第二个节点
  block = block->prev;

  while (block != &pool->block_list)
  {
    pj_pool_block *prev = block->prev;
    pj_list_erase(block);
    (*pool->factory->policy.block_free)(pool->factory, block,
                                        block->end - (unsigned char *)block);
    block = prev;
  }

  block = pool->block_list.next;
  block->cur = block->buf;
  pool->capacity = block->end - (unsigned char *)pool;
}

从上面可以看出重置的时候是将最后一个节点保留了下来，把之前的节点全部释放。

pj_pool_alloc()

分配内存

PJ_IDEF(void *)
pj_pool_alloc(pj_pool_t *pool, pj_size_t size)
{
  void *ptr = pj_pool_alloc_from_block(pool->block_list.next, size);
  if (!ptr)
    ptr = pj_pool_allocate_find(pool, size);
  return ptr;
}

首先会在该内存池中block_list后的第一块block中找是否有size的空间。如果有那么直接返回ptr，否则在后面的block寻找。

PJ_IDEF(void *)
pj_pool_alloc_from_block(pj_pool_block *block, pj_size_t size)
{
  /* The operation below is valid for size==0. 
     * When size==0, the function will return the pointer to the pool
     * memory address, but no memory will be allocated.
     */
  if (size & (PJ_POOL_ALIGNMENT - 1))
  {
    size = (size + PJ_POOL_ALIGNMENT) & ~(PJ_POOL_ALIGNMENT - 1);
  }
  if ((unsigned)(block->end - block->cur) >= size)
  {
    void *ptr = block->cur;
    block->cur += size;
    return ptr;
  }
  return NULL;
}

这里对size进行了变换，编程以4个字节的倍数大小size，因为整数类型会占到4个字节. 如果没有足够的空间则返回NULL，如果是0则不分配内存。

这里是对第一块没有足够空间的情况下：

/*
 * Allocate memory chunk for user from available blocks.
 * This will iterate through block list to find space to allocate the chunk.
 * If no space is available in all the blocks, a new block might be created
 * (depending on whether the pool is allowed to resize).
 */
PJ_DEF(void *)
pj_pool_allocate_find(pj_pool_t *pool, unsigned size)
{
  pj_pool_block *block = pool->block_list.next;
  void *p;
  unsigned block_size;

  PJ_CHECK_STACK();
  // 从第一块block遍历block_list寻找有足够大小的空间
  while (block != &pool->block_list)
  {
    p = pj_pool_alloc_from_block(block, size);
    if (p != NULL)
      return p;
    block = block->next;
  }
  /* No available space in all blocks. */
   // 如果所有的block都没有足够的空间
  /* If pool is configured NOT to expand, return error. */
  // 那么判断increment_size是否为0
  if (pool->increment_size == 0)
  {
    LOG((pool->obj_name, "Can't expand pool to allocate %u bytes "
                         "(used=%u, cap=%u)",
         size, pj_pool_get_used_size(pool), pool->capacity));
    (*pool->callback)(pool, size);
    return NULL;
  }

  /* If pool is configured to expand, but the increment size
     * is less than the required size, expand the pool by multiple
     * increment size
     */
  // 如果increment_size大于0，那么其是可支持扩展的
  // 这里是如果increment_size太小的情况，进行分块处理
  if (pool->increment_size < size + sizeof(pj_pool_block))
  {
    unsigned count;
    count = (size + pool->increment_size + sizeof(pj_pool_block)) /
            pool->increment_size;
    block_size = count * pool->increment_size;
  }
  else
  {
    block_size = pool->increment_size;
  }

  LOG((pool->obj_name,
       "%u bytes requested, resizing pool by %u bytes (used=%u, cap=%u)",
       size, block_size, pj_pool_get_used_size(pool), pool->capacity));

  // 
  block = pj_pool_create_block(pool, block_size);
  if (!block)
    return NULL;

  p = pj_pool_alloc_from_block(block, size);
  pj_assert(p != NULL);
#if PJ_DEBUG
  if (p == NULL)
  {
    p = p;
  }
#endif
  return p;
}

以上先遍历block_list的看是否有足够的空间，如果空间不足，则看是否可以扩展，如果可以扩展，那么看扩展block大小是否过小，如果过小要考虑分块存储，将分的块合并成一块，然后开始创建block.在从创建好的block寻找空间

这里又对第一块block也就是block_list.next 找了一遍实际上没有必要，因为之前已经找过一次了

/*
 * Create new block.
 * Create a new big chunk of memory block, from which user allocation will be
 * taken from.
 */
static pj_pool_block *pj_pool_create_block(pj_pool_t *pool, pj_size_t size)
{
  pj_pool_block *block;

  PJ_CHECK_STACK();
  pj_assert(size >= sizeof(pj_pool_block));

  LOG((pool->obj_name, "create_block(sz=%u), cur.cap=%u, cur.used=%u",
       size, pool->capacity, pj_pool_get_used_size(pool)));

  /* Request memory from allocator. */
  // 分配block
  block = (pj_pool_block *)(*pool->factory->policy.block_alloc)(pool->factory, size);
  if (block == NULL)// 异常处理回调
  {
    (*pool->callback)(pool, size);
    return NULL;
  }

  /* Add capacity. */
  pool->capacity += size;

  /* Set block attribytes. */
  block->cur = block->buf = ((unsigned char *)block) + sizeof(pj_pool_block);
  block->end = ((unsigned char *)block) + size;

  /* Insert in the front of the list. */
  pj_list_insert_after(&pool->block_list, block);

  LOG((pool->obj_name, " block created, buffer=%p-%p", block->buf, block->end));

  return block;
}

将创建好的block接在block_list的后面，然后返回该block指针。

pj_caching_pool_destroy()

销毁缓存池

PJ_DEF(void)
pj_caching_pool_destroy(pj_caching_pool *cp)
{
  int i;
  pj_pool_t *pool;

  PJ_CHECK_STACK();

  /* Delete all pool in free list */
  for (i = 0; i < PJ_CACHING_POOL_ARRAY_SIZE; ++i)
  {
    pj_pool_t *pool = (pj_pool_t *)cp->free_list[i].next;
    pj_pool_t *next;
    for (; pool != (void *)&cp->free_list[i]; pool = next)
    {
      next = pool->next;
      pj_list_erase(pool);
      pj_pool_destroy_int(pool);
    }
  }

  /* Delete all pools in used list */
  pool = (pj_pool_t *)cp->used_list.next;
  while (pool != (pj_pool_t *)&cp->used_list)
  {
    pj_pool_t *next = pool->next;
    pj_list_erase(pool);
    PJ_LOG(4, (pool->obj_name,
               "Pool is not released by application, releasing now"));
    pj_pool_destroy_int(pool);
    pool = next;
  }

  if (cp->lock)
  {
    pj_lock_destroy(cp->lock);
    pj_lock_create_null_mutex(NULL, "cachingpool", &cp->lock);
  }
}

会先遍历free_list销毁空闲内存池，然后遍历used_list销毁应用分配得内存池，然后将锁销毁。

dump_status()

在初始化时dump_status指向了cpool_dump_status

static void cpool_dump_status(pj_pool_factory *factory, pj_bool_t detail)
{
#if PJ_LOG_MAX_LEVEL >= 3
  pj_caching_pool *cp = (pj_caching_pool *)factory;

  pj_lock_acquire(cp->lock);

  PJ_LOG(3, ("cachpool", " Dumping caching pool:"));
  PJ_LOG(3, ("cachpool", "   Capacity=%u, max_capacity=%u, used_cnt=%u",
             cp->capacity, cp->max_capacity, cp->used_count));
  if (detail)
  {
    pj_pool_t *pool = (pj_pool_t *)cp->used_list.next;
    pj_uint32_t total_used = 0, total_capacity = 0;
    PJ_LOG(3, ("cachpool", "  Dumping all active pools:"));
    while (pool != (void *)&cp->used_list)
    {
      unsigned pool_capacity = pj_pool_get_capacity(pool);
      PJ_LOG(3, ("cachpool", "   %12s: %8d of %8d (%d%%) used",
                 pj_pool_getobjname(pool),
                 pj_pool_get_used_size(pool),
                 pool_capacity,
                 pj_pool_get_used_size(pool) * 100 / pool_capacity));
      total_used += pj_pool_get_used_size(pool);
      total_capacity += pool_capacity;
      pool = pool->next;
    }
    if (total_capacity)
    {
      PJ_LOG(3, ("cachpool", "  Total %9d of %9d (%d %%) used!",
                 total_used, total_capacity,
                 total_used * 100 / total_capacity));
    }
  }

  pj_lock_release(cp->lock);
#else
  PJ_UNUSED_ARG(factory);
  PJ_UNUSED_ARG(detail);
#endif
}

如果detail为false，就只会打印简要信息，会打印空闲容量的大小，和空闲容量的最大大小，以及应用持有的内存池数量。如果detail为true，那么还会打印应用持有的每个内存池的名称，已经内存池使用的大小，以及内存池容量，以及占用的百分比，还有应用全部持有的内存池大小，以及全部内存池的容量，以及其占用百分比。

定时器模块

pjlib定时器是从ACE网络库移植过来的。实现在timer.h和timer.c，定时器的原理是有个将来的超时时间，这个时间就是现在时间加上定时器时长。

源代码解析

struct pj_timer_entry

计时器项

/**
 * This structure represents an entry to the timer.
 */
struct pj_timer_entry
{
    /** 
     * User data to be associated with this entry. 
     * Applications normally will put the instance of object that
     * owns the timer entry in this field.
     */
    void *user_data;

    /** 
     * Arbitrary ID assigned by the user/owner of this entry. 
     * Applications can use this ID to distinguish multiple
     * timer entries that share the same callback and user_data.
     * [用户分配的id]
     */
    int id;

    /** 
     * Callback to be called when the timer expires. 
     * [计时器到期后的回调]
     */
    pj_timer_heap_callback *cb;

    /** 
     * Internal unique timer ID, which is assigned by the timer heap. 
     * Application should not touch this ID.
     * [计时器内部唯一id]
     */
    pj_timer_id_t _timer_id;

    /** 
     * The future time when the timer expires, which the value is updated
     * by timer heap when the timer is scheduled.
     * [过期时间]
     */
    pj_time_val _timer_value;
};

_timer_id就是指entry在timer_ids的下标即index。

struct pj_timer_heap_t

计时器堆

struct pj_timer_heap_t
{
    /** Pool from which the timer heap resize will get the storage from */
    // [计时器从该内存池中获取内存]
    pj_pool_t *pool;

    /** Maximum size of the heap. */
    // [堆的最大大小]
    pj_size_t max_size;

    /** Current size of the heap. */
    // [堆当前的大小]
    pj_size_t cur_size;

    /** Max timed out entries to process per poll. */
    // [每个轮询最多可处理的超时项]
    unsigned max_entries_per_poll;

    /** Lock object. */
    pj_lock_t *lock;

    /** Autodelete lock. */
    pj_bool_t auto_delete_lock;

    /**
     * Current contents of the Heap, which is organized as a "heap" of
     * pj_timer_entry *'s.  In this context, a heap is a "partially
     * ordered, almost complete" binary tree, which is stored in an
     * array.
     * [堆 近乎二叉树]
     */
    pj_timer_entry **heap;

    /**
     * An array of "pointers" that allows each pj_timer_entry in the
     * <heap_> to be located in O(1) time.  Basically, <timer_id_[i]>
     * contains the slot in the <heap_> array where an pj_timer_entry
     * with timer id <i> resides.  Thus, the timer id passed back from
     * <schedule_entry> is really an slot into the <timer_ids> array.  The
     * <timer_ids_> array serves two purposes: negative values are
     * treated as "pointers" for the <freelist_>, whereas positive
     * values are treated as "pointers" into the <heap_> array.
     * [计时项的指针数组 复杂度O(1)]
     */
    pj_timer_id_t *timer_ids;

    /**
     * "Pointer" to the first element in the freelist contained within
     * the <timer_ids_> array, which is organized as a stack.
     * [是空闲表中第一个元素，timer_ids的index]
     */
    pj_timer_id_t timer_ids_freelist;

    /** Callback to be called when a timer expires. */
    // [计时器过期时的回调]
    pj_timer_heap_callback *callback;

};

timer_ids 中的值表示entry在二叉树heap数组中的位置，负数是timer_ids初始状态，并且初始的状态的值是其timer_ids下标index的加一的相反数，也就是说是记录了自己下一位的index的相反数，timer_ids[0]不记录，timer_ids从1开始依次记录entry，free_list指向了还未被entry占位的timer_ids的下标index，所以每次加入entry时要将entry的_timer_id = free_list,然后让free_list向后移一位，也就是此时timer_ids的index的值的相反数。就是timer_ids跟heap相互记录了对方的位置，便于相互查询。

pj_timer_heap_create()

创建计时器堆

/**
 * Create a timer heap.
 *
 * @param pool      The pool where allocations in the timer heap will be 
 *                  allocated. The timer heap will dynamicly allocate 
 *                  more storate from the pool if the number of timer 
 *                  entries registered is more than the size originally 
 *                  requested when calling this function.[内存池]
 * @param count     The maximum number of timer entries to be supported 
 *                  initially. If the application registers more entries 
 *                  during runtime, then the timer heap will resize.
 *				     [计时器项的最大数量]
 * @param ht        Pointer to receive the created timer heap.
 *
 * @return          PJ_SUCCESS, or the appropriate error code.
 */
PJ_DEF(pj_status_t)
pj_timer_heap_create(pj_pool_t *pool,
                     pj_size_t size,
                     pj_timer_heap_t **p_heap)
{
  pj_timer_heap_t *ht;
  pj_size_t i;

  PJ_ASSERT_RETURN(pool && p_heap, PJ_EINVAL);

  *p_heap = NULL;

  /* Magic? */
  size += 2;

  /* Allocate timer heap data structure from the pool */
  // 分配heap数据结构体的内存
  ht = PJ_POOL_ALLOC_T(pool, pj_timer_heap_t);
  if (!ht)
    return PJ_ENOMEM;

  /* Initialize timer heap sizes */
  ht->max_size = size;
  ht->cur_size = 0;
  // 每次轮询最大超时项为64
  ht->max_entries_per_poll = DEFAULT_MAX_TIMED_OUT_PER_POLL;
  ht->timer_ids_freelist = 1;
  ht->pool = pool;

  /* Lock. */
  ht->lock = NULL;
  ht->auto_delete_lock = 0;

  // Create the heap array.
  // 分配堆内存
  ht->heap = (pj_timer_entry **)
      pj_pool_alloc(pool, sizeof(pj_timer_entry *) * size);
  if (!ht->heap)
    return PJ_ENOMEM;

  // Create the parallel
  // 
  ht->timer_ids = (pj_timer_id_t *)
      pj_pool_alloc(pool, sizeof(pj_timer_id_t) * size);
  if (!ht->timer_ids)
    return PJ_ENOMEM;

  // Initialize the "freelist," which uses negative values to
  // distinguish freelist elements from "pointers" into the <heap_>
  // array.
  for (i = 0; i < size; ++i)
    ht->timer_ids[i] = -((pj_timer_id_t)(i + 1));

  *p_heap = ht;
  return PJ_SUCCESS;
}

初始化状态，free_list=1,表示如果有entry加入进来，那么entry在heap堆的位置将记录在timer_ids[1]的位置。这里的lock并没有设置，所以可以为其配置lock.

PJ_DEF(void)
pj_timer_heap_set_lock(pj_timer_heap_t *ht,
                       pj_lock_t *lock,
                       pj_bool_t auto_del)
{
  if (ht->lock && ht->auto_delete_lock)
    pj_lock_destroy(ht->lock);

  ht->lock = lock;
  ht->auto_delete_lock = auto_del;
}

pj_timer_entry_init()

初始化entry。

PJ_DEF(pj_timer_entry *)
pj_timer_entry_init(pj_timer_entry *entry,
                    int id,
                    void *user_data,
                    pj_timer_heap_callback *cb)
{
  pj_assert(entry && cb);

  entry->_timer_id = -1;
  entry->id = id;
  entry->user_data = user_data;
  entry->cb = cb;

  return entry;
}

此时的_timer_id = -1，因为此时还没有插入到计时器堆里，所以设置为-1，其值代表该entry在timer_ids的下标位置。

pj_timer_heap_schedule()

调度计时器，即将entry加入到计时器堆里。

PJ_DEF(pj_status_t)
pj_timer_heap_schedule(pj_timer_heap_t *ht,
                       pj_timer_entry *entry,
                       const pj_time_val *delay)
{
  pj_status_t status;
  pj_time_val expires;

  PJ_ASSERT_RETURN(ht && entry && delay, PJ_EINVAL);
  PJ_ASSERT_RETURN(entry->cb != NULL, PJ_EINVAL);

  /* Prevent same entry from being scheduled more than once */
  PJ_ASSERT_RETURN(entry->_timer_id < 1, PJ_EINVALIDOP);

  pj_gettimeofday(&expires);
  PJ_TIME_VAL_ADD(expires, *delay);

  lock_timer_heap(ht);
  status = schedule_entry(ht, entry, &expires);
  unlock_timer_heap(ht);

  return status;
}

pj_gettimeofday获取现在的时间给expires，PJ_TIME_VAL_ADD是现在的时间向后加delay的时间。

static pj_status_t schedule_entry(pj_timer_heap_t *ht,
                                  pj_timer_entry *entry,
                                  const pj_time_val *future_time)
{
  if (ht->cur_size < ht->max_size)
  {
    // Obtain the next unique sequence number.
    // Set the entry
    entry->_timer_id = pop_freelist(ht);
    entry->_timer_value = *future_time;
    insert_node(ht, entry);
    return 0;
  }
  else
    return -1;
}
static pj_timer_id_t pop_freelist(pj_timer_heap_t *ht)
{
  // We need to truncate this to <int> for backwards compatibility.
  pj_timer_id_t new_id = ht->timer_ids_freelist;

  PJ_CHECK_STACK();

  // The freelist values in the <timer_ids_> are negative, so we need
  // to negate them to get the next freelist "pointer."
  ht->timer_ids_freelist =
      -ht->timer_ids[ht->timer_ids_freelist];

  return new_id;
}

这里会将free_list赋值给entry的_timer_id,然后free_list等于timer_ids[free_list]的相反数，就是将free_list向后移一位。然后才开始将entry插入到堆里。

#define HEAP_PARENT(X) (X == 0 ? 0 : (((X)-1) / 2))

static void insert_node(pj_timer_heap_t *ht, pj_timer_entry *new_node)
{
  if (ht->cur_size + 2 >= ht->max_size)
    grow_heap(ht);

  reheap_up(ht, new_node, ht->cur_size, HEAP_PARENT(ht->cur_size));
  ht->cur_size++;
}

如果堆大小不够了，那么将其扩展。

static void grow_heap(pj_timer_heap_t *ht)
{
  // All the containers will double in size from max_size_
  size_t new_size = ht->max_size * 2;
  pj_timer_id_t *new_timer_ids;
  pj_size_t i;

  // First grow the heap itself.

  pj_timer_entry **new_heap = 0;
  // 复制heap，到新的heap
  new_heap = (pj_timer_entry **)
      pj_pool_alloc(ht->pool, sizeof(pj_timer_entry *) * new_size);
  memcpy(new_heap, ht->heap, ht->max_size * sizeof(pj_timer_entry *));
  //delete [] this->heap_;
  // 将原来heap指针指向new_heap
  ht->heap = new_heap;

  // Grow the array of timer ids.
  // 复制timer_ids到新的tiemr_ids
  new_timer_ids = 0;
  new_timer_ids = (pj_timer_id_t *)
      pj_pool_alloc(ht->pool, new_size * sizeof(pj_timer_id_t));

  memcpy(new_timer_ids, ht->timer_ids, ht->max_size * sizeof(pj_timer_id_t));

  //delete [] timer_ids_;
  ht->timer_ids = new_timer_ids;

  // And add the new elements to the end of the "freelist".
  // 将新的timer_ids，从max_size初始化，设置为未分配的初始状态
  for (i = ht->max_size; i < new_size; i++)
    ht->timer_ids[i] = -((pj_timer_id_t)(i + 1));

  ht->max_size = new_size;
}

可以看出这里扩展堆是将堆大小扩展到了之前的大小的两倍。

这里仅仅只是将指针重新指向新的堆跟timer_ids，但是并没有将原来的内存释放掉。

如果堆大小足够，那么就开始插入操作，reheap_up代表从堆的底部开始插入，然后根据规则进行向上调整移动。

static void reheap_up(pj_timer_heap_t *ht, pj_timer_entry *moved_node,
                      size_t slot, size_t parent)
{
  // Restore the heap property after an insertion.

  while (slot > 0)
  {
    // If the parent node is greater than the <moved_node> we need
    // to copy it down.
    if (PJ_TIME_VAL_LT(moved_node->_timer_value, ht->heap[parent]->_timer_value))
    {
      copy_node(ht, slot, ht->heap[parent]);
      slot = parent;
      parent = HEAP_PARENT(slot);
    }
    else
      break;
  }

  // Insert the new node into its proper resting place in the heap and
  // update the corresponding slot in the parallel <timer_ids> array.
  copy_node(ht, slot, moved_node);
}

slot当前位置，parent代表父节点的位置，如果slot大于0意思就是当前的heap不为空那么进入循环，如果插入的entry的时间小于父节点，那么则跟父节点复制到slot的位置上，然后依次往上走，直到父节点的时间小于当前的entry，退出循环将entry复制到slot当前位置。

static void copy_node(pj_timer_heap_t *ht, int slot, pj_timer_entry *moved_node)
{
  PJ_CHECK_STACK();

  // Insert <moved_node> into its new location in the heap.
  ht->heap[slot] = moved_node;

  // Update the corresponding slot in the parallel <timer_ids_> array.
  ht->timer_ids[moved_node->_timer_id] = slot;
}

将这里将moved_node赋值给heap[slot],并且要更新timer_ids对entry的记录位置。

pj_timer_heap_poll()

轮询计时器堆并将过期的计时器移除，并进行回调，next_delay用来记录，移除后堆顶entry时间跟现在的时间差。

PJ_DEF(unsigned)
pj_timer_heap_poll(pj_timer_heap_t *ht,
                   pj_time_val *next_delay)
{
  pj_time_val now; // 记录当前时间
  unsigned count; // 过期entry的数量

  PJ_ASSERT_RETURN(ht, 0);

  if (!ht->cur_size && next_delay)
  {
    next_delay->sec = next_delay->msec = PJ_MAXINT32;
    return 0;
  }

  count = 0; // 初始化过期数量
  pj_gettimeofday(&now); // 设置当前时间

  lock_timer_heap(ht);
  while (ht->cur_size &&
         PJ_TIME_VAL_LTE(ht->heap[0]->_timer_value, now) &&
         count < ht->max_entries_per_poll)
  {
    pj_timer_entry *node = remove_node(ht, 0);
    ++count;

    unlock_timer_heap(ht);
    if (node->cb)
      (*node->cb)(ht, node);
    lock_timer_heap(ht);
  }
  if (ht->cur_size && next_delay)
  {
    *next_delay = ht->heap[0]->_timer_value;
    PJ_TIME_VAL_SUB(*next_delay, now);
    if (next_delay->sec < 0 || next_delay->msec < 0)
      next_delay->sec = next_delay->msec = 0;
  }
  else if (next_delay)
  {
    next_delay->sec = next_delay->msec = PJ_MAXINT32;
  }
  unlock_timer_heap(ht);

  return count;
}

这里移除entry，并进行了回调,这里next记录堆顶过期时间与现在的时间差。

这里计算next_delay时间的时候，会判断时间是这里之所以会出现next_delay->sec < 0 || next_delay->msec < 0，因为设定了max_entries_per_poll，当移除了这么多entry后，也会跳出循环。

static pj_timer_entry *remove_node(pj_timer_heap_t *ht, size_t slot)
{
  pj_timer_entry *removed_node = ht->heap[slot];

  // Return this timer id to the freelist.
  // 将freelist
  push_freelist(ht, removed_node->_timer_id);

  // Decrement the size of the heap by one since we're removing the
  // "slot"th node.
  // 当前大小减一
  ht->cur_size--;

  // Set the ID
  // 将entry的_timer_id重置
  removed_node->_timer_id = -1;

  // Only try to reheapify if we're not deleting the last entry.

  if (slot < ht->cur_size)
  {
    int parent;
    pj_timer_entry *moved_node = ht->heap[ht->cur_size];

    // Move the end node to the location being removed and update
    // the corresponding slot in the parallel <timer_ids> array.
    copy_node(ht, slot, moved_node);

    // If the <moved_node->time_value_> is great than or equal its
    // parent it needs be moved down the heap.
    parent = HEAP_PARENT(slot);

    if (PJ_TIME_VAL_GTE(moved_node->_timer_value, ht->heap[parent]->_timer_value))
      reheap_down(ht, moved_node, slot, HEAP_LEFT(slot));
    else
      reheap_up(ht, moved_node, slot, parent);
  }

  return removed_node;
}

这里将要移除的entry取出，然后将freelist的指向它并且将它的值设置为原free_list的相反数，这样下次加进来的entry会加入到该移除的位置，再下一个free_list又会回到原来的位置。

static void push_freelist(pj_timer_heap_t *ht, pj_timer_id_t old_id)
{
  PJ_CHECK_STACK();

  // The freelist values in the <timer_ids_> are negative, so we need
  // to negate them to get the next freelist "pointer."
  ht->timer_ids[old_id] = -ht->timer_ids_freelist;
  ht->timer_ids_freelist = old_id;
}

设置free_list之后，在将二叉树数组最后节点一个entry复制到该位置，然后开始移动根据父节点时间小于子节点时间的规则，如果该节点小于父节点，那么就往上移动，如果该节点大于父节点，那么该节点就往下判断跟自己的子节点比较，往下移动：

static void reheap_down(pj_timer_heap_t *ht, pj_timer_entry *moved_node,
                        size_t slot, size_t child)
{
  PJ_CHECK_STACK();

  // Restore the heap property after a deletion.

  while (child < ht->cur_size)
  {
    // Choose the smaller of the two children.
    if (child + 1 < ht->cur_size && PJ_TIME_VAL_LT(ht->heap[child + 1]->_timer_value, ht->heap[child]->_timer_value))
      child++;

    // Perform a <copy> if the child has a larger timeout value than
    // the <moved_node>.
    if (PJ_TIME_VAL_LT(ht->heap[child]->_timer_value, moved_node->_timer_value))
    {
      copy_node(ht, slot, ht->heap[child]);
      slot = child;
      child = HEAP_LEFT(child);
    }
    else
      // We've found our location in the heap.
      break;
  }

  copy_node(ht, slot, moved_node);
}

因为子节点有两个，所以先比较两个子节点的大小，小的那个替代父节点，这样依次往下移动。

pj_timer_heap_cancel()

取消计时器项，将其从计时器堆里移除

PJ_DEF(int) 
pj_timer_heap_cancel(pj_timer_heap_t *ht,
                     pj_timer_entry *entry)
{
  int count;

  PJ_ASSERT_RETURN(ht && entry, PJ_EINVAL);

  lock_timer_heap(ht);
  count = cancel(ht, entry, 1);
  unlock_timer_heap(ht);

  return count;
}

static int cancel(pj_timer_heap_t *ht,
                  pj_timer_entry *entry,
                  int dont_call)
{
  long timer_node_slot;

  PJ_CHECK_STACK();

  // Check to see if the timer_id is out of range
  if (entry->_timer_id < 0 || (pj_size_t)entry->_timer_id > ht->max_size)
    return 0;
  // 取出在heap的下标
  timer_node_slot = ht->timer_ids[entry->_timer_id];

  if (timer_node_slot < 0) // Check to see if timer_id is still valid.
    return 0;
  // 比较两个地址是否一致（验证）
  if (entry != ht->heap[timer_node_slot])
  {
    pj_assert(entry == ht->heap[timer_node_slot]);
    return 0;
  }
  else
  {
    remove_node(ht, timer_node_slot);

    if (dont_call == 0)
      // Call the close hook.
      (*ht->callback)(ht, entry);
    return 1;
  }
}

这里的dont_call==0，则执行回调函数，否则不执行。

pj_timer_heap_mem_size()

计算计时器堆的大小

/*
 * Calculate memory size required to create a timer heap.
 */
PJ_DEF(pj_size_t)
pj_timer_heap_mem_size(pj_size_t count)
{
  return /* size of the timer heap itself: */
      sizeof(pj_timer_heap_t) +
      /* size of each entry: */
      (count + 2) * (sizeof(pj_timer_entry *) + sizeof(pj_timer_id_t)) +
      /* lock, pool etc: */
      132;
}

结构体pj_timer_heap_t的大小，在加上(size+2)个entry指针的和timer_ids的大小，以及132用来lock等大小。

赏

谢谢你请我吃糖果

微信

• 本文作者： Veng
• 本文链接： http://veng0923.github.io/2020/09/02/pjlib-内存池-计时器解析/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！