简易分析myicq的内存池模型

长平狐 发布于 2013/01/11 10:33
阅读 106
收藏 0

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

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

 

list.cpp

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

 

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

 

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

slab.h

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

 

slab.cpp

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

 

内存池是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

 

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

 

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

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

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

 


原文链接:http://blog.csdn.net/fjb2080/article/details/6546858
加载中
返回顶部
顶部