我们前面的讨论都是基于BDB2.7.7版本的,那时候的BDB已经是一个支持事务处理的相当复杂的模块了。现在让我们回过头来看一下BDB1.6版本的初始化过程,那时候的共享区域就只有MPOOL。

首先其入口函数是dbopen(…)函数:

DB * dbopen(fname, flags, mode, type, openinfo)
    const char *fname;
    int flags, mode;
    DBTYPE type;
    const void *openinfo;
{

#define    DB_FLAGS    (DB_LOCK | DB_SHMEM | DB_TXN)
#define    USE_OPEN_FLAGS                            \
    (O_CREAT | O_EXCL | O_EXLOCK | O_NONBLOCK | O_RDONLY |        \
    O_RDWR | O_SHLOCK | O_TRUNC)

    if ((flags & ~(USE_OPEN_FLAGS | DB_FLAGS)) == 0)
        switch (type) {
        case DB_BTREE:
            return (__bt_open(fname, flags & USE_OPEN_FLAGS,
                mode, openinfo, flags & DB_FLAGS));
        case DB_HASH:
            return (__hash_open(fname, flags & USE_OPEN_FLAGS,
                mode, openinfo, flags & DB_FLAGS));
        case DB_RECNO:
            return (__rec_open(fname, flags & USE_OPEN_FLAGS,
                mode, openinfo, flags & DB_FLAGS));
        }
    errno = EINVAL;
    return (NULL);
}

这个函数根据用户指定的DBTYPE参数调用相应的存取方法的打开函数,我们以B树存取方法为例: case DB_BTREE: return (__bt_open(fname, flags & USE_OPEN_FLAGS, mode, openinfo, flags & DB_FLAGS)); 具体代码如下:

/***************** bt_open.c ********************/
/*
* __BT_OPEN -- Open a btree.
*
* Creates and fills a DB struct, and calls the routine that actually
* opens the btree.
*
* Parameters:
*    fname:    filename (NULL for in-memory trees)
*    flags:    open flag bits
*    mode:    open permission bits
*    b:    BTREEINFO pointer
*
* Returns:
*    NULL on failure, pointer to DB on success.
*
*/
DB *
__bt_open(fname, flags, mode, openinfo, dflags)
    const char *fname;
    int flags, mode, dflags;
    const BTREEINFO *openinfo;
{
    struct stat sb;
    BTMETA m;
    BTREE *t;
    BTREEINFO b;
    DB *dbp;
    pgno_t ncache;
    ssize_t nr;
    int machine_lorder;

    t = NULL;

    /*
    * Intention is to make sure all of the user's selections are okay
    * here and then use them without checking.  Can't be complete, since
    * we don't know the right page size, lorder or flags until the backing
    * file is opened.  Also, the file's page size can cause the cachesize
    * to change.
    */
    machine_lorder = byteorder();
    if (openinfo) {
        b = *openinfo;

        /* Flags: R_DUP. */
        if (b.flags & ~(R_DUP))
            goto einval;

        /*
        * Page size must be indx_t aligned and >= MINPSIZE.  Default
        * page size is set farther on, based on the underlying file
        * transfer size.
        */
        if (b.psize &&
            (b.psize < MINPSIZE || b.psize > MAX_PAGE_OFFSET + 1 ||
            b.psize & sizeof(indx_t) - 1))
            goto einval;

        /* Minimum number of keys per page; absolute minimum is 2. */
        if (b.minkeypage) {
            if (b.minkeypage < 2)
                goto einval;
        } else
            b.minkeypage = DEFMINKEYPAGE;

        /* If no comparison, use default comparison and prefix. */
        if (b.compare == NULL) {
            b.compare = __bt_defcmp;
            if (b.prefix == NULL)
                b.prefix = __bt_defpfx;
        }

        if (b.lorder == 0)
            b.lorder = machine_lorder;
    } else {
        b.compare = __bt_defcmp;
        b.cachesize = 0;
        b.flags = 0;
        b.lorder = machine_lorder;
        b.minkeypage = DEFMINKEYPAGE;
        b.prefix = __bt_defpfx;
        b.psize = 0;
    }

    /* Check for the ubiquitous PDP-11. */
    if (b.lorder != BIG_ENDIAN && b.lorder != LITTLE_ENDIAN)
        goto einval;

/* 创建并初始化DB{}和BTREE{}结构,这两者是继承的关系,具体参见笔记*/
    /* Allocate and initialize DB and BTREE structures. */
    if ((t = (BTREE *)malloc(sizeof(BTREE))) == NULL)
        goto err;
    memset(t, 0, sizeof(BTREE));
    t->bt_fd = -1;            /* Don't close unopened fd on error. */
    t->bt_lorder = b.lorder;
    t->bt_order = NOT;
    t->bt_cmp = b.compare;
    t->bt_pfx = b.prefix;
    t->bt_rfd = -1;

    if ((t->bt_dbp = dbp = (DB *)malloc(sizeof(DB))) == NULL)
        goto err;
    memset(t->bt_dbp, 0, sizeof(DB));
    if (t->bt_lorder != machine_lorder)
        F_SET(t, B_NEEDSWAP);

    dbp->type = DB_BTREE;
    dbp->internal = t;
    dbp->close = __bt_close;
    dbp->del = __bt_delete;
    dbp->fd = __bt_fd;
    dbp->get = __bt_get;
    dbp->put = __bt_put;
    dbp->seq = __bt_seq;
    dbp->sync = __bt_sync;

    /*
    * If no file name was supplied, this is an in-memory btree and we
    * open a backing temporary file.  Otherwise, it's a disk-based tree.
    */
    if (fname) {
        switch (flags & O_ACCMODE) {
        case O_RDONLY:
            F_SET(t, B_RDONLY);
            break;
        case O_RDWR:
            break;
        case O_WRONLY:
        default:
            goto einval;
        }
        打开数据库文件
        if ((t->bt_fd = open(fname, flags, mode)) < 0)
            goto err;

    } else {
        if ((flags & O_ACCMODE) != O_RDWR)
            goto einval;
        if ((t->bt_fd = tmp()) == -1)
            goto err;
        F_SET(t, B_INMEM);
    }

    if (fcntl(t->bt_fd, F_SETFD, 1) == -1)
        goto err;

    if (fstat(t->bt_fd, &sb))
        goto err;
    if (sb.st_size) {
        if ((nr = read(t->bt_fd, &m, sizeof(BTMETA))) < 0)
            goto err;
        if (nr != sizeof(BTMETA))
            goto eftype;

    /** 读入元数据,根据里面的信息(如页面大小等)建立缓冲区共享区域 **/
        /*
        * Read in the meta-data.  This can change the notion of what
        * the lorder, page size and flags are, and, when the page size
        * changes, the cachesize value can change too.  If the user
        * specified the wrong byte order for an existing database, we
        * don't bother to return an error, we just clear the NEEDSWAP
        * bit.
        */
        if (m.magic == BTREEMAGIC)
            F_CLR(t, B_NEEDSWAP);
        else {
            F_SET(t, B_NEEDSWAP);
            M_32_SWAP(m.magic);
            M_32_SWAP(m.version);
            M_32_SWAP(m.psize);
            M_32_SWAP(m.free);
            M_32_SWAP(m.nrecs);
            M_32_SWAP(m.flags);
        }
        if (m.magic != BTREEMAGIC || m.version != BTREEVERSION)
            goto eftype;
        if (m.psize < MINPSIZE || m.psize > MAX_PAGE_OFFSET + 1 ||
            m.psize & sizeof(indx_t) - 1)
            goto eftype;
        if (m.flags & ~SAVEMETA)
            goto eftype;
        b.psize = m.psize;
        F_SET(t, m.flags);
        t->bt_free = m.free;
        t->bt_nrecs = m.nrecs;
    } else {
        /*
        * Set the page size to the best value for I/O to this file.
        * Don't overflow the page offset type.
        */
        if (b.psize == 0) {
            b.psize = sb.st_blksize;
            if (b.psize < MINPSIZE)
                b.psize = MINPSIZE;
            if (b.psize > MAX_PAGE_OFFSET + 1)
                b.psize = MAX_PAGE_OFFSET + 1;
        }

        /* Set flag if duplicates permitted. */
        if (!(b.flags & R_DUP))
            F_SET(t, B_NODUPS);

        t->bt_free = P_INVALID;
        t->bt_nrecs = 0;
        F_SET(t, B_METADIRTY);
    }

    t->bt_psize = b.psize;

    /* Set the cache size; must be a multiple of the page size. */
    if (b.cachesize && b.cachesize & b.psize - 1)
        b.cachesize += (~b.cachesize & b.psize - 1) + 1;
    if (b.cachesize < b.psize * MINCACHE)
        b.cachesize = b.psize * MINCACHE;

    /* Calculate number of pages to cache. */
    ncache = (b.cachesize + t->bt_psize - 1) / t->bt_psize;

    /*
    * The btree data structure requires that at least two keys can fit on
    * a page, but other than that there's no fixed requirement.  The user
    * specified a minimum number per page, and we translated that into the
    * number of bytes a key/data pair can use before being placed on an
    * overflow page.  This calculation includes the page header, the size
    * of the index referencing the leaf item and the size of the leaf item
    * structure.  Also, don't let the user specify a minkeypage such that
    * a key/data pair won't fit even if both key and data are on overflow
    * pages.
    */
    t->bt_ovflsize = (t->bt_psize - BTDATAOFF) / b.minkeypage -
        (sizeof(indx_t) + NBLEAFDBT(0, 0));
    if (t->bt_ovflsize < NBLEAFDBT(NOVFLSIZE, NOVFLSIZE) + sizeof(indx_t))
        t->bt_ovflsize =
            NBLEAFDBT(NOVFLSIZE, NOVFLSIZE) + sizeof(indx_t);

    /*** 现在可以更加提取到的元数据创建缓冲区共享区域了 ***/
    /* Initialize the buffer pool. */
    if ((t->bt_mp =
        mpool_open(NULL, t->bt_fd, t->bt_psize, ncache)) == NULL)
        goto err;
    if (!F_ISSET(t, B_INMEM))
        mpool_filter(t->bt_mp, __bt_pgin, __bt_pgout, t);

    /* Create a root page if new tree. */
    if (nroot(t) == RET_ERROR)
        goto err;

    /* Global flags. */
    if (dflags & DB_LOCK)
        F_SET(t, B_DB_LOCK);
    if (dflags & DB_SHMEM)
        F_SET(t, B_DB_SHMEM);
    if (dflags & DB_TXN)
        F_SET(t, B_DB_TXN);

    return (dbp);

einval:    errno = EINVAL;
    goto err;

eftype:    errno = EFTYPE;
    goto err;

err:    if (t) {
        if (t->bt_dbp)
            free(t->bt_dbp);
        if (t->bt_fd != -1)
            (void)close(t->bt_fd);
        free(t);
    }
    return (NULL);
}

我们看到B树的打开方法现分配DB{}和BTREE{}数据结构并初始化它们(这两者是抽象与具体的继承关系)。然后它打开指定的数据库文件,读进元数据,根据这些元数据提供的信息创建MPOOL共享区域。

/*
* mpool_open --
*    Initialize a memory pool.
*/
MPOOL *
mpool_open(key, fd, pagesize, maxcache)
    void *key;
    int fd;
    pgno_t pagesize, maxcache;
{
    struct stat sb;
    MPOOL *mp;
    int entry;

    /*
    * Get information about the file.
    *
    * XXX
    * We don't currently handle pipes, although we should.
    */
    if (fstat(fd, &sb))
        return (NULL);
    if (!S_ISREG(sb.st_mode)) {
        errno = ESPIPE;
        return (NULL);
    }

    /* Allocate and initialize the MPOOL cookie. */
    if ((mp = (MPOOL *)calloc(1, sizeof(MPOOL))) == NULL)
        return (NULL);
    CIRCLEQ_INIT(&mp->lqh);
    for (entry = 0; entry < HASHSIZE; ++entry)
        CIRCLEQ_INIT(&mp->hqh[entry]);
    mp->maxcache = maxcache;
    mp->npages = sb.st_size / pagesize;
    mp->pagesize = pagesize;
    mp->fd = fd;
    return (mp);
}

从这里我们可以看到不像2.7.7,这里MPOOL{}数据结构并不是共享内存区域,而是每一个进程私有的内存空间,因为它是通过calloc分配的。

typedef struct MPOOL {
    CIRCLEQ_HEAD(_lqh, _bkt) lqh;    /* lru queue head */
                    /* hash queue array */
    CIRCLEQ_HEAD(_hqh, _bkt) hqh[HASHSIZE];
    pgno_t    curcache;        /* current number of cached pages */
    pgno_t    maxcache;        /* max number of cached pages */
    pgno_t    npages;            /* number of pages in the file */
    u_long    pagesize;        /* file page size */
    int    fd;            /* file descriptor */
                    /* page in conversion routine */
    void    (*pgin) __P((void *, pgno_t, void *));
                    /* page out conversion routine */
    void    (*pgout) __P((void *, pgno_t, void *));
    void    *pgcookie;        /* cookie for page in/out routines */
#ifdef STATISTICS
    u_long    cachehit;
    u_long    cachemiss;
    u_long    pagealloc;
    u_long    pageflush;
    u_long    pageget;
    u_long    pagenew;
    u_long    pageput;
    u_long    pageread;
    u_long    pagewrite;
#endif
} MPOOL;

MPOOL{}结构中有个rlu队列:

CIRCLEQ_HEAD(_lqh, _bkt) lqh;

其中CIRCLEQ_HEAD宏定义如下: /* * Circular queue definitions. / #define CIRCLEQ_HEAD(name, type) \ struct name { \ struct type *cqh_first; / first element / \ struct type *cqh_last; / last element */ \ }

替换成:

struct _lqh{
    struct _bkt * cqh_first;
    struct _bkt* cqh_last;
}

可见它是含有一个指向结构_bkt{}的头部和尾部指针的结构。

还有一个散列表:

CIRCLEQ_HEAD(_hqh, _bkt) hqh[HASHSIZE];

展开成:

struct _hqh{
    struct _bkt* cqh_first;
    struct _bkt* cqh_last;
}hqh[HASHSIZE]; 即是一个有HASHSIZE个指向_bkt{}结构的数组。

也就是说这里MPOOL的双向队列中每一个元素都是一个桶_bkt{}结构,定义如下(在mpool.h文件中): /* * The memory pool scheme is a simple one. Each in-memory page is referenced * by a bucket which is threaded in up to two of three ways. All active pages * are threaded on a hash chain (hashed by page number) and an lru chain. * Inactive pages are threaded on a free chain. Each reference to a memory * pool is handed an opaque MPOOL cookie which stores all of this information. */ #define HASHSIZE 128 #define HASHKEY(pgno) ((pgno - 1 + HASHSIZE) % HASHSIZE)

/* The BKT structures are the elements of the queues. */
typedef struct _bkt {
    CIRCLEQ_ENTRY(_bkt) hq;        /* hash queue */
    CIRCLEQ_ENTRY(_bkt) q;        /* lru queue */
    void    *page;            /* page */
    pgno_t   pgno;            /* page number */

#define    MPOOL_DIRTY    0x01        /* page needs to be written */
#define    MPOOL_PINNED    0x02        /* page is pinned into memory */
#define    MPOOL_INUSE    0x04        /* page address is valid */
    u_int8_t flags;            /* flags */
} BKT;

可以看到每个_bkt{}结构中包含如下元素:

用于散列表开环的指针hq,指向下一个_bkt元素:

CIRCLEQ_ENTRY(_bkt) hq;        /* hash queue */

和用于lru队列的指针q,指向lru队列中的下一个元素:

CIRCLEQ_ENTRY(_bkt) q;        /* lru queue */

其中CIRCLEQ_ENTRY宏定义如下:

#define CIRCLEQ_ENTRY(type)                        \
struct {                                \
    struct type *cqe_next;        /* next element */        \
    struct type *cqe_prev;        /* previous element */        \
}

这些是双向列表的要求,这里由于一个_bkt{}元素可以(往往)既是属于rlu队列,又属于hash队列,所以需要两个指针字段。

下面的字段是真正用于缓存的字段:

一个指向页面数据的指针:

void* page;  /* page */

和该页面的页面编号:

pgno_t pgno;  /* page number */

我们在后面会看到页面有自己的结构定义,其中就包含了页面编号pgno,这里包含页面编号的原因在于通过pgno的散列并不是一一映射的,所以需要开环散列,需要沿着开环链比较下去。

另外,我们也可以看到这里的_bkt{}结构就好像页面的控制块信息,它建立起页面编号与页面地址的关系以用于页面查找,并且用于决定页面替换策略。这个实现与UNIX的文件系统缓冲区实现是十分类型的。 真正的页面空间在page指向的内存区域,这个内存区域是在mpool_bkt(…)函数中创建的:

new:    if ((bp = (BKT *)malloc(sizeof(BKT) + mp->pagesize)) == NULL)
        return (NULL);

并且在创建后有这么一句:

bp->page = (char *)bp + sizeof(BKT);

这显示了作为页面控制块的BKT{}结构和其控制的页面在内存上的布局是紧挨着的,就像头部(header)和实体(body)一样。

说明:为什么采用这种内存布局方式,而不是将头部控制块信息与页面数据信息分别分配呢,既然前者是MPOOL模块内部使用,而后者是分配给用户的缓冲区区域?答案是为了保持用户的使用透明性。如果我们仅仅将分配的页面缓冲区地址返回给用户,那么当用户返回该缓冲区给MPOOL的时候,由于该缓冲区是void* ,由用户自由填充,MPOOL无法找到其相应的控制块,这样就没有办法回收了。但是如果采用控制块与缓冲区页面紧挨的做法,那么MPOOL在收到一个缓冲区起始地址时,它只要向前移动sizeof(BKT)就可以找到该页面的控制块信息了。事实上,这种做法正是libc中malloc的实现。采用这种实现,用户对于控制块完全透明。因此接口为:

void    *mpool_new __P((MPOOL *, pgno_t *, u_int));
void    *mpool_get __P((MPOOL *, pgno_t, u_int));
int     mpool_delete __P((MPOOL *, void *));
int     mpool_put __P((MPOOL *, void *, u_int));

而在Gray中不是采用这种做法,所以它的释放页面缓冲区的接口与申请页面缓冲区接口一样,都要将页面编号进行散列比较得到相应的页面控制块,才能释放该页面:

typedef struct{
    PAGEID pageid;
    PAGEPTR pageaddress;
    int index;
    semaphore* sme;
    Boolean modifies;
    Boolean invalid;
}BUFFER_ACC_CB;

Boolean bufferunfix(BUFFER_ACC_CBP);

整个mpool_bkt()函数是关键,所以将其实现完整地列在下面: /* * mpool_bkt * Get a page from the cache (or create one). */ static BKT * mpool_bkt(mp) MPOOL *mp; { struct _hqh *head; BKT *bp;

    /* If under the max cached, always create a new page. */
    if (mp->curcache < mp->maxcache)
        goto new;

    /*
    * If the cache is max'd out, walk the lru list for a buffer we
    * can flush.  If we find one, write it (if necessary) and take it
    * off any lists.  If we don't find anything we grow the cache anyway.
    * The cache never shrinks.
    */
    for (bp = mp->lqh.cqh_first;
        bp != (void *)&mp->lqh; bp = bp->q.cqe_next)
        if (!(bp->flags & MPOOL_PINNED)) {
            /* Flush if dirty. */
            if (bp->flags & MPOOL_DIRTY &&
                mpool_write(mp, bp) == RET_ERROR)
                return (NULL);
#ifdef STATISTICS
            ++mp->pageflush;
#endif
            /* Remove from the hash and lru queues. */
            head = &mp->hqh[HASHKEY(bp->pgno)];
            CIRCLEQ_REMOVE(head, bp, hq);
            CIRCLEQ_REMOVE(&mp->lqh, bp, q);
#ifdef DEBUG
            { void *spage;
                spage = bp->page;
                memset(bp, 0xff, sizeof(BKT) + mp->pagesize);
                bp->page = spage;
            }
#endif
            bp->flags = 0;
            return (bp);
        }

new:    if ((bp = (BKT *)malloc(sizeof(BKT) + mp->pagesize)) == NULL)
        return (NULL);
#ifdef STATISTICS
    ++mp->pagealloc;
#endif
#if defined(DEBUG) || defined(PURIFY)
    memset(bp, 0xff, sizeof(BKT) + mp->pagesize);
#endif
    bp->page = (char *)bp + sizeof(BKT);
    bp->flags = 0;
    ++mp->curcache;
    return (bp);
}

最后,让我们看一下作为实体的页面是怎样定义的:显然这跟存取路径与文件组织有关,对于B树它需要存放B树节点,而且每一个节点就是一个页面。我们仍然以B树为例:

在btree.h文件中有如下每个页面的页头数据结构PAGE{}定义:

/*
* Page 0 of a btree file contains a copy of the meta-data.  This page is also
* used as an out-of-band page, i.e. page pointers that point to nowhere point
* to page 0.  Page 1 is the root of the btree.
*/
#define    P_INVALID     0        /* Invalid tree page number. */
#define    P_META         0        /* Tree metadata page number. */
#define    P_ROOT         1        /* Tree root page number. */

/*
* There are five page layouts in the btree: btree internal pages (BINTERNAL),
* btree leaf pages (BLEAF), recno internal pages (RINTERNAL), recno leaf pages
* (RLEAF) and overflow pages.  All five page types have a page header (PAGE).
* This implementation requires that values within structures NOT be padded.
* (ANSI C permits random padding.)  If your compiler pads randomly you'll have
* to do some work to get this package to run.
*/
typedef struct _page {
    pgno_t    pgno;            /* this page's page number */
    pgno_t    prevpg;            /* left sibling */
    pgno_t    nextpg;            /* right sibling */

#define    P_BINTERNAL    0x01        /* btree internal page */
#define    P_BLEAF        0x02        /* leaf page */
#define    P_OVERFLOW    0x04        /* overflow page */
#define    P_RINTERNAL    0x08        /* recno internal page */
#define    P_RLEAF        0x10        /* leaf page */
#define P_TYPE        0x1f        /* type mask */
#define    P_PRESERVE    0x20        /* never delete this chain of pages */
    u_int32_t flags;

    indx_t    lower;            /* lower bound of free space on page */
    indx_t    upper;            /* upper bound of free space on page */
    indx_t    linp[1];        /* indx_t-aligned VAR. LENGTH DATA */
} PAGE;

页面中的记录的格式又根据B树节点类型不同而不同。这里说有5中节点类型,但是其中有两种是recno存取方法的。我们对此不与理会。

首先是B树内部节点记录定义:

/*
* For the btree internal pages, the item is a key.  BINTERNALs are {key, pgno}
* pairs, such that the key compares less than or equal to all of the records
* on that page.  For a tree without duplicate keys, an internal page with two
* consecutive keys, a and b, will have all records greater than or equal to a
* and less than b stored on the page associated with a.  Duplicate keys are
* somewhat special and can cause duplicate internal and leaf page records and
* some minor modifications of the above rule.
*/
typedef struct _binternal {
    u_int32_t ksize;        /* key size */
    pgno_t    pgno;            /* page number stored on */
#define    P_BIGDATA    0x01        /* overflow data */
#define    P_BIGKEY    0x02        /* overflow key */
    u_char    flags;
    char    bytes[1];        /* data */
} BINTERNAL;

然后是叶子节点记录定义:

/* For the btree leaf pages, the item is a key and data pair. */
typedef struct _bleaf {
    u_int32_t    ksize;        /* size of key */
    u_int32_t    dsize;        /* size of data */
    u_char    flags;            /* P_BIGDATA, P_BIGKEY */
    char    bytes[1];        /* data */
} BLEAF;

最后是一种特殊的页面:溢出页(overflow page),是一个只有页头(PAGE{})的页面。

说明:如果将元数据的存放页面也算进B树的页面的话,那么还有一个BTMETA{}结构:

typedef struct _btmeta{
    u_int32_t magic;
    u_int32_t version;
    u_int32_t psize;
    u_int32_t free;
    u_int32_t flags;
}BTMETA;

其中最重要的两个字段是free和psize。

一个用于使用自由链表管理磁盘的自由空间,一个是确定这个B树文件组织的数据文件的缓冲区大小。

总结: 每个缓冲区页面有一个缓冲区控制块(_bkt{}),其后紧跟着缓冲区页面(void* page),每个缓冲区页面有一个页头(PAGE{}),页头之后又紧紧跟着页面数据信息,也就是记录的存放空间(由页头中的slinp[]指向)。记录的具体格式由存取方法和文件组织决定,比如B树的记录格式就与Hash记录不同,另外B树本身也有多种记录格式。