📄 pager.c
字号:
/**
* @file page.c page cache management 2008-1-29 23:59
*
* @author lin shao chuan (email:lsccsl@tom.com, msn:lsccsl@163.net)
*
* @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 *)NULL)->ver - NULL)
/* 记录ver的大小 */
#define PAGER_HDR_VER_LEN (sizeof(((unused_pager_info *)NULL)->ver))
/* page_size的偏移 */
#define PAGER_HDR_PAGE_SIZE_OFFSET (((unused_pager_info *)NULL)->page_size - NULL)
/* 记录第一个空闲页页号的偏移量 */
#define PAGER_HDR_FIRST_FREE_OFFSET (((unused_pager_info *)NULL)->first_free - NULL)
/* 记录第一个空闲页页号的外存空间长度 */
#define PAGER_HDR_FIRST_FREE_LEN (sizeof(((unused_pager_info *)NULL)->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 - 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 *)NULL)->rec_count - NULL)
#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)
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -