pager.c

sourceforge历史版本完整下载: http://sourceforge.net/project/showfiles.php?group_id=202044 提供了基于b树索引算法的文件数据数据

/**
 * @file page.c page cache management 2008-1-29 23:59
 *
 * @author lin shao chuan (email:[e-mail], msn:[e-mail])
 *
 * @brief if it works, it was written by lin shao chuan, if not, i don't know who wrote it. 
 *        负责缓存page管理,journal机制保证数据的完整性, 外存空闲页管理
 *
 * 外存页文件格式描述
 * 第一页
 *  offset bytes        des
 *  0      16           格式版本
 *  16     4            页大小
 *  20     4            第一个空闲页
 *  24     40           保留
 *  64   pg_sz - 64     用户数据     
 *
 * 空闲页:
 * 第一个空闲页
 * offset bytes   des
 * 0      4       总的空闲页数
 * 4      4       空闲页"链表"的下一个空闲页号
 * 8      4       当前页里记载了多少的空闲页号
 * 12             空闲数组开始,每4个字节表示一个空闲页号
 * 非第一个空闲页
 * 0      4       无意义
 * 4      4       空闲页"链表"的下一个空闲页号
 * 8      4       当前页里记载了多少的空闲页号
 * 12             空闲数组开始,每4个字节表示一个空闲页号
 *
 * 页:
 * offset bytes      des
 * 0      1          1:表示此页被使用,0:表示此页空闲
 * 1      3          保留
 * 4      pg_sz - 4  供用户使用的空间
 *
 * journal日志文件头定义
 * offset bytes          des
 * 0      4              头的大小hd_sz
 * 4      16             格式版本
 * 20     4              日志里备份了几页
 * 24     4              校验和初始随机值
 * 28     4              备份日志前页文件的大小
 * 32     hd_sz-24       保留
 * 
 * journal记录:
 * <页内容 + 页号 + 校验和>
 *
 * 验证:os是否是按块写文件,sync时是否安脏块同步,
 * seek:win的seek一般会成功,即使是seek的位置超过了文件的大小,在写入时,如果磁盘空间不够(seek的位置太大了),则会提示磁盘空间不足(errcode = 112)
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  lin shao chuan makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 * see the GNU General Public License  for more detail.
 */
#include "pager.h"

#include <stdio.h>
#include <string.h>
#include <assert.h>

#include "mybuffer.h"
#include "myhashtable.h"
#include "mylog.h"
#include "myrand.h"
#include "MyAlgorithm.h"

#include "OsFile.h"


#ifdef WIN32
#pragma warning(disable:4312)
#endif


/* 默认的日志文件附加 */
#define JOURNAL "-journal"

/* 页文件格式版本 */
#define VERSION "Rhapsody V0.1.7\000"

/* 最小以及最大的页文件大小 */
#define	MIN_PAGE_SIZE 64
#define MAX_PAGE_SIZE 32768

/* 默认的页缓存上限 */
#define DEFAULT_CACHE_PAGES_COUNT 8

/* 日志版本长度 */
#define JOURNAL_MAGIC_STRING "1234567890123456"

/* 页文件的第一页 */
#define PAGER_FIRST_PAGE_NO 1


/**
 * 外存页文件格式描述
 * 第一页
 *  offset bytes        des
 *  0      16           格式版本
 *  16     4            页大小
 *  20     4            第一个空闲页
 *  24     40           保留
 *  64   pg_sz - 64     用户数据
 */
typedef struct __unused_pager_info_
{
	unsigned char ver[16];
	unsigned char page_size[4];
	unsigned char first_free[4];
	unsigned char reserve[40];
}unused_pager_info;

/* 记录ver的偏移 */
#define PAGER_HDR_VER_OFFSET (((unused_pager_info *)0)->ver - (unsigned char *)0)
/* 记录ver的大小 */
#define PAGER_HDR_VER_LEN (sizeof(((unused_pager_info *)0)->ver))
/* page_size的偏移 */
#define PAGER_HDR_PAGE_SIZE_OFFSET (((unused_pager_info *)0)->page_size - (unsigned char *)0)
/* 记录第一个空闲页页号的偏移量 */
#define PAGER_HDR_FIRST_FREE_OFFSET (((unused_pager_info *)0)->first_free - (unsigned char *)0)
/* 记录第一个空闲页页号的外存空间长度 */
#define PAGER_HDR_FIRST_FREE_LEN (sizeof(((unused_pager_info *)0)->first_free))

/**
 * 判断这个主空闲页是否包含有子空闲页
 *
 * 空闲页:
 * 第一个空闲页
 * offset bytes   des
 * 0      4       总的空闲页数
 * 4      4       空闲页"链表"的下一个空闲页号
 * 8      4       当前页里记载了多少的空闲页号
 * 12             空闲数组开始,每4个字节表示一个空闲页号
 * 非第一个空闲页
 * 0      4       无意义
 * 4      4       空闲页"链表"的下一个空闲页号
 * 8      4       当前页里记载了多少的空闲页号
 * 12             空闲数组开始,每4个字节表示一个空闲页号
 */
typedef struct __unused_free_page_
{
	unsigned char total_free_count[4];
	unsigned char next_free_link[4];
	unsigned char free_count[4];
	unsigned char free_pgno_array[1];
}unused_free_page;

/* 存储总页数的偏移 */
#define PAGER_FREE_TOTAL_FREE_COUNT_OFFSET (((unused_free_page *)NULL)->total_free_count - (unsigned char *)NULL)
/* 下一个空闲页数组链接的偏移 */
#define PAGER_FREE_NEXT_FREE_LINK_OFFSET (((unused_free_page *)NULL)->next_free_link - (unsigned char *)NULL)
/* 存储本页空闲页数的偏移 */
#define PAGER_FREE_FREE_COUNT_OFFSET (((unused_free_page *)NULL)->free_count - (unsigned char *)NULL)
/* 空闲页数组的偏移 */
#define PAGER_FREE_FREE_PGNO_ARRAY_OFFSET (((unused_free_page *)NULL)->free_pgno_array - (unsigned char *)NULL)

/**
 * 每页用于管理的空间偏移定义
 * 0      1          1:表示此页被使用,0:表示此页空闲
 * 1      3          保留
 * 4      pg_sz - 4  供用户使用的空间
 */
typedef struct __unused_page_
{
	unsigned char in_user[1];
	unsigned char reserve[3];
}unused_page;

/* 每一页为了管理而预留的字节 */
#define BYTE_RESERVE_PER_PAGE sizeof(unused_page)
#define PAGER_PAGE_USER_SIZE(__pgr) (__pgr->page_size - BYTE_RESERVE_PER_PAGE)
/* 标识页处于使用中的变量位置偏移 */
#define PAGER_PAGE_IN_USE_OFFSET (((unused_page*)NULL)->in_user - (unsigned char *)NULL)

/**
 * journal日志文件头定义
 * offset bytes          des
 * 0      4              头的大小hd_sz
 * 4      16             格式版本
 * 20     4              日志里备份了几页
 * 24     4              校验和初始随机值
 * 28     4              备份日志前页文件的大小
 * 32     hd_sz-24       保留
 */
typedef struct __unused_journal_hdr_
{
	unsigned char sector_size[4];
	unsigned char magic[16];
	unsigned char rec_count[4];
	unsigned char cksum_init[4];
	unsigned char orig_page_count[4];
	unsigned char reserve[32];
}unused_journal_hdr;

/* 默认的扇区大小 */
#define PAGER_MIN_SECTOR_SIZE (sizeof(unused_journal_hdr))
#define JOURNAL_MAGIC_LEN (sizeof(((unused_journal_hdr *)0)->magic))
#define PAGER_JOURNAL_REC_COUNT_OFFSET (((unused_journal_hdr *)0)->rec_count - (unsigned char *)0)
#define PAGER_JOURNAL_REC_COUNT_LEN (sizeof(((unused_journal_hdr *)0)->rec_count))


struct __pghd_t_;

typedef struct __pager_t_
{
	/* 内存池句柄 */
	HMYMEMPOOL hm;

	/* 辅存文件名 */
	HMYBUFFER hb_file_name;
	/* 辅存的页文件句柄 */
	HOSFILE hf;
	/* 页文件的数据是否完整 */
	int page_file_is_integrity;
	/* 这个pager缓存管理被引用的次数 */
	unsigned int ref_count;

	/* journal文件名 */
	HMYBUFFER hb_jf_name;
	/* journal 文件句柄 */
	HOSFILE hjf;
	/* 当前日志文件的尾部 */
	int64 journal_end;
	/* 当前日志文件的最后一个头偏移(还未同步) */
	int64 jouranl_prev_hdr;
	/*
	* 校验和初始化的随机数
	* 每一个备份日志头,都记录一个随机数,用于计算对应于这个头的页的检验和
	* 防止因为断电出现垃圾数据
	* (垃圾数据有可能是一个被删除的正确的journal文件,这样,即使文件是错误的,但校验和却有可能是正确的)
	* 加上这个随机因子,降低这种情况带来的风险
	* 每个jf头的校验和初始随机值都是不一样的.
	*/
	unsigned int cur_cksum_init;
	/* 随机数发生器 */
	HMYRAND hrand;

	/* 记录空闲页链表,回收此链表里的页时,首先同步jfd,以保证数据的完整性 */
	struct __pghd_t_ * pg_free_first, * pg_free_last;

	/*
	* 记录已经同步过jf的空闲页链表,回收时,优先回收这个链表里的页 
	* 当获取空头页缓存时,如果该页处在这个链表里头,则应从链表里头将此页脱链
	*/
	struct __pghd_t_ * pg_syncjf_first, * pg_syncjf_last;

	/* 是否需要做了jfd同步的操作,重置时需要此标识置成0 */
	int need_sync_journal;
	/*
	* 是否已经做过jf同步操作
	* 用于判断当出现超出原始大小页写入情况时,是否需要做同步jf的操作
	* 如果同步jf的操作已经做过了,则此时不用再做了
	*/
	int bsync_journal_has_done;

	/* 记录有多少页进入jfd备份,即尚未同步jf的脏页 */
	unsigned int in_journal_pages_count;

	/* 记录页是否处journal状态的位着色表 */
	HMYHASHTABLE hash_pgno_journal;

	/* 记录所有的页 */
	struct __pghd_t_ * pg_all;

	/* 记录脏页,同步时,将这些页先同步至jfd,然后写入fd并同步 */
	struct __pghd_t_ * pg_dirty;

	/* 文件页号与页面缓存的哈希映射表 <pgno> - <pghd_t *> */
	HMYHASHTABLE hash_page;

	/* 记录外存文件有多少页 */
	unsigned int total_page_count;
	/* 记录开始备份jf时页文件有多少页 */
	unsigned int orig_pages_count;

	/* 缓存中的最大页数 */
	unsigned int max_cache_pages;

	/* 每页大小 */
	unsigned int page_size;

	/*
	* 所用系统的扇区大小,用于jf头的大小
	* 如果做过回滚操作,这个值将被修正
	*/
	unsigned int sector_size;

	/* 每页附加的用户扩展数据大小 */
	unsigned int extra_size;

	/* 页的加载与取消引用以及移动时的回调函数 */
	PAGE_RELEASE page_release_cb;
	PAGE_RELOAD page_reload_cb;
}pager_t;

typedef struct __pghd_t_
{
	/* which pager this page belong to */
	pager_t * pager;

	/* 页号 */
	unsigned int page_num;

	/* 页缓存引用记数 */
	unsigned int ref_count;

	/* 记录当前页缓存的状态 */
	int pg_state;

	/* 前一个与后一个空闲页,当页的引用计数为0时,应加入这个链表 */
	struct __pghd_t_ * pg_free_prev, * pg_free_next;

	/*
	* 记录已经同步过jf的空闲页链表,回收时,优先回收这个链表里的页 
	* 当获取空头页缓存时,如果该页处在这个链表里头,则应从链表里头将此页脱链
	* 当页的引用计数为零时,并且已经同步了hjf,应加入此链表
	*/
	struct __pghd_t_ * pg_syncjf_prev, * pg_syncjf_next;

	/* 后一个脏页,构成一个脏页缓冲链表 */
	struct __pghd_t_ * pg_dirty_prev, * pg_dirty_next;

	/* 后一个页,构成一个所有页的链表 */
	struct __pghd_t_ * pg_all_prev, * pg_all_next;

	/*
	* 用于页管理而预留的一些字节
	* 第一个字节表示该页是否为空闲页
	*/
	unsigned char pg_buf_start[BYTE_RESERVE_PER_PAGE];
}pghd_t;

typedef enum __page_event_
{
	/* 更改了页缓存,并在jf里做备份 */
	PAGE_EVT_WRITE_BUF_BK,

	/* 页缓存被写回,并同步了jf */
	PAGE_EVT_WRITE_BACK_SYNCJF,

	/* 页缓存被同步了 */
	PAGE_EVT_SYNC,

	/* 页缓存回滚了 */
	PAGE_EVT_ROLL_BACK,

	/* jf文件被同步了 */
	PAGE_EVT_SYNC_JOURNAL,

	/* jf文件被删除 */
	PAGE_EVT_DEL_JOURNAL,

	EVENT_END,
}PAGE_EVENT;

typedef enum __page_state_
{
	/* 页缓存被读出,但没有对页缓存做任何修改 */
	PAGE_CLEAN,

	/* 对页缓存做了修改,并在jf做了备份,但没有写入页文件 */
	PAGE_DIRTY_NO_SYNC_JF,

	/* 对页缓存的做改已经写回页文件,在jf里备份已经做了 */
	PAGE_CLEAN_SYNC,

	/* 页缓存写加页文件后,又对页缓存进行了修改,jf里的备份已经做了 */
	PAGE_DIRTY_SYNC_JF,

	/* 页处于一个错误的状态 */
	PAGE_STATE_ERR,
}PAGE_STATE;

/**
 * @brief 将某一个页缓存置成非dirty状态,并从dirty链表中脱离
 *
 * 页缓存状态变迁表
 *---------------------------------------------------------------------------------------------------------------------------------------------------------------------
 *| 状态\事件            |PAGE_EVT_WRITE_BUF_BK  |PAGE_EVT_WRITE_BACK_SYNCJF | PAGE_EVT_SYNC       | PAGE_EVT_ROLL_BACK | PAGE_EVT_SYNC_JOURNAL| PAGE_EVT_DEL_JOURNAL |
 *|----------------------|-----------------------|---------------------------|---------------------|--------------------|----------------------|----------------------|
 *| PAGE_CLEAN           |PAGE_DIRTY_NO_SYNC_JF  |    X                      |    X                | X                  | X                    |        X             |
 *|                      |                       |                           |                     |                    |                      |                      |
 *| PAGE_DIRTY_NO_SYNC_JF| X                     |  PAGE_CLEAN_SYNC          |  PAGE_CLEAN         | PAGE_CLEAN         | PAGE_DIRTY_SYNC_JF   |        X             |
 *|                      |                       |                           |                     |                    |                      |                      |
 *| PAGE_CLEAN_SYNC      |PAGE_DIRTY_SYNC_JF     |   X                       |  PAGE_CLEAN         | PAGE_CLEAN_SYNC    | X                    |PAGE_CLEAN            |
 *|                      |                       |                           |                     |                    |                      |                      |
 *| PAGE_DIRTY_SYNC_JF   | X                     |  PAGE_CLEAN_SYNC          |  PAGE_CLEAN         | PAGE_CLEAN_SYNC    | X                    |        X             |
 *---------------------------------------------------------------------------------------------------------------------------------------------------------------------
 *
 * 页缓存状态机变迁图              
 *                          syn/roll back                    syn jf
 *                       ___________________     ________________________________________________________________
 *              初态  <-/                   \   /                                                                \->
 *               PAGE_CLEAN ---write buf--> PAGE_DIRTY_NO_SYNC_JF --write back--> PAGE_CLEAN_SYNC --write buf--> PAGE_DIRTY_SYNC_JF
 *                 <-\   <-\______________________________________________________/   <-\_________________________/   /
 *                    \                 roll back                                             write back             /
 *                     \____________________________________________________________________________________________/
 *                                               sync / roll back
 */                      
static __INLINE__ int pager_change_page_state(pghd_t * pg, PAGE_EVENT evt)
{
#define X PAGE_STATE_ERR

	static PAGE_STATE __page_state_machine[PAGE_STATE_ERR][EVENT_END] = {
		{PAGE_DIRTY_NO_SYNC_JF, X,               X,              X         ,      X                 , X         },
		{X,                     PAGE_CLEAN_SYNC, PAGE_CLEAN,     PAGE_CLEAN,      PAGE_DIRTY_SYNC_JF, X         },
		{PAGE_DIRTY_SYNC_JF,    X,               PAGE_CLEAN,     PAGE_CLEAN_SYNC, X                 , PAGE_CLEAN},
		{X,                     PAGE_CLEAN_SYNC, PAGE_CLEAN,     PAGE_CLEAN_SYNC, X                 , X         },
	};

	assert(evt < (sizeof(__page_state_machine[0]) / sizeof(__page_state_machine[0][0])));
	assert(pg->pg_state < (sizeof(__page_state_machine) / sizeof(__page_state_machine[0])));

	pg->pg_state = __page_state_machine[pg->pg_state][evt];

	assert(PAGE_STATE_ERR != pg->pg_state);

	return 0;

#undef X
}

/**
 * @brief 判断一个页是否处在journal备份之中
 */
static __INLINE__ int pager_page_in_journal(pager_t * pager, unsigned int pgno)
{
	assert(pager && pager->hash_pgno_journal);

	if(MyHashTableSearch(pager->hash_pgno_journal, (void *)pgno))
		return 1;

	return 0;
}

/**
 * @brief 判断某一个是否为脏
 */
#define pager_page_is_dirty(__pg) (PAGE_DIRTY_SYNC_JF == __pg->pg_state || PAGE_DIRTY_NO_SYNC_JF == __pg->pg_state)

/**
 * @brief 是否在journal里做了备份
 */
#define pager_page_is_in_journal(__pg) (assert(pager_page_in_journal(__pg->pager, __pg->page_num) || PAGE_CLEAN == __pg->pg_state), PAGE_CLEAN != __pg->pg_state)

/**
 * @brief 是否做了journal同步
 */
#define pager_page_is_sync_journal(__pg) (PAGE_CLEAN_SYNC == __pg->pg_state || PAGE_DIRTY_SYNC_JF == __pg->pg_state)

/**
 * @brief 判断页缓存是否在提交前写回了页文件
 */
#define pager_page_is_written_before_page_sync(__pg) pager_page_is_sync_journal(__pg)

/**
 * @brief 判断页缓存是否在提交前写回了页文件
 */
#define pager_page_is_clean_not_in_jf(__pg) (PAGE_CLEAN == __pg->pg_state)

/**
 * @brief 获取有多少页被缓存
 */
#define pager_get_cached_pages_count(__pgr) MyHashTableGetElementCount(__pgr->hash_page)