学步园

myicq 1.0中实现了一个内存池的模型，可以自动分配和回收对象内存。下面看下其实现方式。

首先内存池使用了双向链表来链接的，链表的实现也就是linux中常见的list_head形式，不过是其自己实现的。

有点不解的是，既然用list_head，如果是在linux实现，可以自己调用linux里内建好的list_head，而且还是C的呢，而不是myicq里自己实现的还是类的形式的。又如果如果说是在windows下，那windows下的vc也有类似的形式如：FILED_OFFSET宏就是这样。

感觉在这里用刻意使用list_head，而又是以类的形式使用，我感觉还不如直接使用stl来得方便，或者说代码阅读性好很多。

不多说了，看代码。

myicq里的ListHead

list.h

/***************************************************************************<br /> * *<br /> * This program is free software; you can redistribute it and/or modify *<br /> * it under the terms of the GNU General Public License as published by *<br /> * the Free Software Foundation; either version 2 of the License, or *<br /> * (at your option) any later version. *<br /> * *<br /> * copyright : (C) 2002 by Zhang Yong *<br /> * email : z-yong163@163.com *<br /> ***************************************************************************/<br /> #ifndef _LIST_H_<br /> #define _LIST_H_<br /> #include "icqtypes.h"<br /> #define LIST_ENTRY(ptr, type, member) /<br /> ((type *) ((char *) (ptr) - (unsigned long) (&((type *) 0)->member)))<br /> #define LIST_FOR_EACH(pos, head) /<br /> for (pos = (head)->next; pos != (head); pos = pos->next)<br /> /*<br /> * 这是一个循环链表<br /> */<br /> class ListHead {<br /> public:<br /> ListHead() {<br /> prev = next = this;<br /> }<br /> bool isEmpty() {<br /> return (next == this);<br /> }<br /> ListHead *removeHead();<br /> void add(ListHead *item);<br /> void addHead(ListHead *item);<br /> void remove();<br /> ListHead *prev, *next;<br /> };<br /> #endif

list.cpp

/***************************************************************************<br /> * *<br /> * This program is free software; you can redistribute it and/or modify *<br /> * it under the terms of the GNU General Public License as published by *<br /> * the Free Software Foundation; either version 2 of the License, or *<br /> * (at your option) any later version. *<br /> * *<br /> * copyright : (C) 2002 by Zhang Yong *<br /> * email : z-yong163@163.com *<br /> ***************************************************************************/<br /> #include "list.h"<br /> /*<br /> * 让this节点孤立起来<br /> */<br /> void ListHead::remove()<br /> {<br /> prev->next = next;<br /> next->prev = prev;<br /> prev = next = this;<br /> }<br /> /*<br /> * 将this后面的节点孤立起来，并返回这个节点<br /> */<br /> ListHead *ListHead::removeHead()<br /> {<br /> ListHead *t = next;<br /> next->remove();<br /> return t;<br /> }<br /> /*<br /> * 在this前加入item<br /> */<br /> void ListHead::add(ListHead *item)<br /> {<br /> item->prev = prev;<br /> item->next = this;<br /> prev->next = item;<br /> prev = item;<br /> }<br /> /*<br /> * 在this后面加入节点item<br /> */<br /> void ListHead::addHead(ListHead *item)<br /> {<br /> item->prev = this;<br /> item->next = next;<br /> next->prev = item;<br /> next = item;<br /> }

这样就实现了一个简单的双向链表，如果对list_head机制不熟的可以看我的文章《深入浅出linux内核源代码之双向链表list_head(上)》
和《
深入浅出linux内核源代码之双向链表list_head(下)
》。

下面是一个内存池的实现方式：

slab.h

/***************************************************************************<br /> * *<br /> * This program is free software; you can redistribute it and/or modify *<br /> * it under the terms of the GNU General Public License as published by *<br /> * the Free Software Foundation; either version 2 of the License, or *<br /> * (at your option) any later version. *<br /> * *<br /> * copyright : (C) 2002 by Zhang Yong *<br /> * email : z-yong163@163.com *<br /> ***************************************************************************/<br /> #ifndef _SLAB_H<br /> #define _SLAB_H<br /> #include "list.h"<br /> #include <stdio.h><br /> struct SLAB;<br /> struct OBJ {<br /> OBJ *next;<br /> SLAB *slab;<br /> };<br /> struct SLAB {<br /> ListHead item;<br /> int inuse;<br /> OBJ *free;<br /> };<br /> class Cache {<br /> public:<br /> Cache(int size, int n);<br /> ~Cache();<br /> void *allocObj();<br /> void freeObj(void *p);<br /> static int reclaimAll();<br /> private:<br /> SLAB *newSlab();<br /> int reclaim(int n = 0xffff);<br /> Cache *nextCache;<br /> ListHead slabList;<br /> ListHead *firstNotFull;<br /> int objSize;<br /> int numObjs;<br /> int numFreeSlabs;<br /> int slabSize;<br /> static Cache *cacheList;<br /> };<br /> #define DECLARE_SLAB(type) /<br /> private: /<br /> static Cache type##_cache; /<br /> public: /<br /> void *operator new(size_t) { /<br /> return type##_cache.allocObj(); /<br /> } /<br /> void operator delete(void *p) { /<br /> type##_cache.freeObj(p); /<br /> }<br /> #define IMPLEMENT_SLAB(type, num) /<br /> Cache type::type##_cache(sizeof(type), num);<br /> #endif

slab.cpp

/***************************************************************************<br /> * *<br /> * This program is free software; you can redistribute it and/or modify *<br /> * it under the terms of the GNU General Public License as published by *<br /> * the Free Software Foundation; either version 2 of the License, or *<br /> * (at your option) any later version. *<br /> * *<br /> * copyright : (C) 2002 by Zhang Yong *<br /> * email : z-yong163@163.com *<br /> ***************************************************************************/<br /> #include "slab.h"<br /> #include <stdlib.h><br /> #include <memory.h><br /> #define MAX_FREE_SLABS 8<br /> Cache *Cache::cacheList = NULL;<br /> int Cache::reclaimAll()<br /> {<br /> int ret = 0;<br /> for (Cache *p = cacheList; p; p = p->nextCache)<br /> ret += p->reclaim();<br /> return ret;<br /> }<br /> Cache::Cache(int size, int n)<br /> {<br /> objSize = size + sizeof(OBJ);<br /> numObjs = n;<br /> numFreeSlabs = 0;<br /> firstNotFull = &slabList;<br /> slabSize = sizeof(SLAB) + objSize * n;<br /> // Add it to the cache chain<br /> nextCache = cacheList;<br /> cacheList = this;<br /> }<br /> Cache::~Cache()<br /> {<br /> while (!slabList.isEmpty()) {<br /> ListHead *pos = slabList.removeHead();<br /> SLAB *slab = LIST_ENTRY(pos, SLAB, item);<br /> free(slab);<br /> }<br /> }<br /> /*<br /> * Reclaim empty slabs in this cache<br /> */<br /> int Cache::reclaim(int n)<br /> {<br /> SLAB *slab;<br /> ListHead *pos, *t = firstNotFull;<br /> int i = 0;<br /> while (i < n && (pos = slabList.prev) != &slabList) {<br /> slab = LIST_ENTRY(pos, SLAB, item);<br /> if (slab->inuse)<br /> break;<br /> i++;<br /> if (firstNotFull == pos)<br /> firstNotFull = pos->prev;<br /> pos->remove();<br /> free(slab);<br /> }<br /> if (firstNotFull != t && firstNotFull != &slabList) {<br /> slab = LIST_ENTRY(firstNotFull, SLAB, item);<br /> if (slab->inuse == numObjs)<br /> firstNotFull = &slabList;<br /> }<br /> numFreeSlabs += i;<br /> return i;<br /> }<br /> /*<br /> * Alloc a new slab<br /> */<br /> SLAB *Cache::newSlab()<br /> {<br /> SLAB *slab = (SLAB *) malloc(slabSize);<br /> if (!slab) {<br /> if (reclaimAll() > 0) {<br /> slab = (SLAB *) malloc(slabSize);<br /> if (!slab)<br /> return NULL;<br /> }<br /> }<br /> slab->inuse = 0;<br /> OBJ *obj = (OBJ *) (slab + 1);<br /> slab->free = obj;<br /> for (int i = 0; i < numObjs - 1; ++i) {<br /> OBJ *next = (OBJ *) ((char *) obj + objSize);<br /> obj->next = next;<br /> obj->slab = slab;<br /> obj = next;<br /> }<br /> obj->next = NULL;<br /> obj->slab = slab;<br /> slabList.add(&slab->item);<br /> firstNotFull = &slab->item;<br /> return slab;<br /> }<br /> /*<br /> * Alloc an object from the cache<br /> */<br /> void *Cache::allocObj()<br /> {<br /> void *obj = NULL;<br /> SLAB *slab;<br /> if (firstNotFull == &slabList)<br /> slab = newSlab();<br /> else {<br /> slab = LIST_ENTRY(firstNotFull, SLAB, item);<br /> if (!slab->inuse)<br /> numFreeSlabs--;<br /> }<br /> if (slab) {<br /> slab->inuse++;<br /> obj = slab->free + 1;<br /> slab->free = slab->free->next;<br /> if (!slab->free)<br /> firstNotFull = slab->item.next;<br /> }<br /> return obj;<br /> }<br /> /*<br /> * Free an object in the cache<br /> */<br /> void Cache::freeObj(void *p)<br /> {<br /> #ifdef _DEBUG<br /> memset(p, 0xdd, objSize - sizeof(OBJ));<br /> #endif<br /> OBJ *obj = (OBJ *) p - 1;<br /> SLAB *slab = obj->slab;<br /> obj->next = slab->free;<br /> slab->free = obj;<br /> ListHead *pos;<br /> if (slab->inuse-- == numObjs) {<br /> ListHead *t = firstNotFull;<br /> pos = &slab->item;<br /> firstNotFull = pos;<br /> if (pos->next != t) {<br /> pos->remove();<br /> t->add(pos);<br /> }<br /> } else if (!slab->inuse) {<br /> int n = ++numFreeSlabs - MAX_FREE_SLABS;<br /> if (n > 0)<br /> reclaim(n);<br /> ListHead *t = firstNotFull->prev;<br /> pos = &slab->item;<br /> pos->remove();<br /> slabList.add(pos);<br /> if (firstNotFull == &slab->item)<br /> firstNotFull = t->next;<br /> }<br /> }

内存池是SLAB结构打头的一个大块内存，里面有多个对象内存快，这些内存快个数在下面的#define IMPLEMENT_SLAB(type, num) 宏中的num来指定个数，每个对象空间前面有个OBJ的结构头部。

SLAB后面是连续的OBJ内存快，SLAB结构里的free指向第一个可使用的对象内存快。在回收内存块时这个free指针会指向回收的这块内存，而这块内存会指向free指向的内存块，形成一个可用内存快链表。而内存快又是以next的形式链接在一起。这种实现形式和SGI的STL的内存池的实现非常相似，具体可以参考侯捷的《内存春秋》里说的，里面说得非常详细易懂！

cache类是一个以list_head来链接的双向链表，其链接的是SLAB结构的内存块。

#define DECLARE_SLAB(type) 宏用在类中声明一个静态变量static Cache type##_cache;并且里面重新定义了new和delete，以便从内存池中分配和销毁。

#define IMPLEMENT_SLAB(type, num) 宏用来类的定义出定义这个静态变量，type用于制定对象大小，num用于指定分配多少个快

下面是类DBRequest中使用了这个内存池：

dbmanager.h

/***************************************************************************<br /> * *<br /> * This program is free software; you can redistribute it and/or modify *<br /> * it under the terms of the GNU General Public License as published by *<br /> * the Free Software Foundation; either version 2 of the License, or *<br /> * (at your option) any later version. *<br /> * *<br /> * copyright : (C) 2002 by Zhang Yong *<br /> * email : z-yong163@163.com *<br /> ***************************************************************************/<br /> #ifndef _DB_MANAGER_H<br /> #define _DB_MANAGER_H<br /> #include <mysql.h><br /> #include "myicq.h"<br /> #include "list.h"<br /> #include "slab.h"<br /> #define WRITE_STR(req, str) req->writeString(str, sizeof(str) - 1)<br /> #define MAX_SQL 4096<br /> extern MYSQL *mysqlWrite;<br /> char *conv10(uint32 num, char *bufEnd);<br /> class RefObject;<br /> class DBRequest;<br /> typedef void (*DB_CALLBACK)(DBRequest *req);<br /> enum {<br /> DBF_UPDATE = 0x01,<br /> DBF_INSERT = 0x02,<br /> };<br /> class DBRequest {<br /> friend class DBManager;<br /> public:<br /> DBRequest(uint8 flags, DB_CALLBACK cb = NULL, RefObject *obj = NULL, uint32 d = 0);<br /> void writeString(const char *text, int n) {<br /> if (cursor - sql + n <= MAX_SQL) {<br /> memcpy(cursor, text, n);<br /> cursor += n;<br /> }<br /> }<br /> DBRequest &operator <<(ICQ_STR &str) {<br /> if (cursor - sql + (str.len << 1) < MAX_SQL - 2) {<br /> *cursor++ = '/'';<br /> cursor += mysql_real_escape_string(mysqlWrite, cursor, str.text, str.len);<br /> *cursor++ = '/'';<br /> }<br /> return *this;<br /> }<br /> DBRequest &operator <<(char c) {<br /> if (cursor - sql <= (int) (MAX_SQL - sizeof(c)))<br /> *cursor++ = c;<br /> return *this;<br /> }<br /> DBRequest &operator <<(uint8 num) {<br /> *this << (uint32) num;<br /> return *this;<br /> }<br /> DBRequest &operator <<(uint16 num) {<br /> *this <<(uint32) num;<br /> return *this;<br /> }<br /> DBRequest &operator <<(uint32 num) {<br /> char buf[16];<br /> char *p = conv10(num, buf + sizeof(buf));<br /> writeString(p, buf + sizeof(buf) - p);<br /> return *this;<br /> }<br /> ListHead listItem;<br /> DB_CALLBACK callback;<br /> RefObject *refObj;<br /> uint32 data;<br /> union {<br /> MYSQL_RES *res;<br /> int ret;<br /> };<br /> uint32 lastInsertID;<br /> private:<br /> int sqlLen() {<br /> return cursor - sql;<br /> }<br /> uint8 flags;<br /> char sql[MAX_SQL];<br /> char *cursor;<br /> DECLARE_SLAB(DBRequest)<br /> };<br /> class DBManager {<br /> public:<br /> DBManager();<br /> ~DBManager();<br /> bool create(DB_INFO &dbSlave);<br /> void processQuery();<br /> static bool init(DB_INFO &dbMaster);<br /> static void destroy();<br /> static void query(DBRequest *req);<br /> static void processUpdate();<br /> static void dispatch();<br /> private:<br /> MYSQL *mysqlRead;<br /> };<br /> #endif

可以看到在类的最后使用了DECLARE_SLAB(DBRequest)来声明。

并且在dbmanager.cpp中调用IMPLEMENT_SLAB(DBRequest, 16)来实现，可以看到每次分配是16个对象。

如果使用满了，会在获取下一个空余对象空间时，自动在cache里在分配一个slab内存快，然后以list_head的双向链表形式链接起来。