buffer manager refactoring to isolate ARC algorithm
I'm planning to apply the attached patch to hide the ARC-related data
structures in freelist.c. There are no data structure or algorithm
changes, just removal of ARC details from the shared header
buf_internals.h, plus minor refactoring to hide the knowledge that ARC
wants a twice-normal-size buffer lookup hashtable. This should allow us
to make the ARC-or-not changes within freelist.c only.
I did leave the "bufNext" fields of BufferDesc as-is. Strictly speaking
this list is an internal data structure of freelist.c, but moving these
fields out of BufferDesc would require a larger change than seems
worthwhile, especially seeing that an LRU algorithm could make use of
the same list.
Any objections?
regards, tom lane
*** src/backend/storage/buffer/buf_init.c.orig Fri Dec 31 17:46:08 2004
--- src/backend/storage/buffer/buf_init.c Thu Feb 3 14:51:18 2005
***************
*** 73,79 ****
* aborts, it should only unpin the buffers exactly the number of times it
* has pinned them, so that it will not blow away buffers of another
* backend.
- *
*/--- 73,78 ----
***************
*** 120,133 ****
block = BufferBlocks; /*
! * link the buffers into a single linked list. This will become
! * the LIFO list of unused buffers returned by
! * StrategyGetBuffer().
*/
for (i = 0; i < NBuffers; block += BLCKSZ, buf++, i++)
{
Assert(ShmemIsValid((unsigned long) block));
buf->bufNext = i + 1;
CLEAR_BUFFERTAG(buf->tag);
--- 119,135 ----
block = BufferBlocks; /*
! * Initialize all the buffer headers.
*/
for (i = 0; i < NBuffers; block += BLCKSZ, buf++, i++)
{
Assert(ShmemIsValid((unsigned long) block));
+ /*
+ * The bufNext fields link together all totally-unused buffers.
+ * Subsequent management of this list is done by
+ * StrategyGetBuffer().
+ */
buf->bufNext = i + 1; CLEAR_BUFFERTAG(buf->tag);
***************
*** 142,148 ****
buf->wait_backend_id = 0;
}
! /* Correct last entry */
BufferDescriptors[NBuffers - 1].bufNext = -1;
LWLockRelease(BufMgrLock);
--- 144,150 ----
buf->wait_backend_id = 0;
}! /* Correct last entry of linked list */
BufferDescriptors[NBuffers - 1].bufNext = -1;
LWLockRelease(BufMgrLock);
***************
*** 178,184 ****
/*
* Convert shmem offsets into addresses as seen by this process. This
! * is just to speed up the BufferGetBlock() macro.
*/
for (i = 0; i < NBuffers; i++)
BufferBlockPointers[i] = (Block) MAKE_PTR(BufferDescriptors[i].data);
--- 180,187 ---- /*
* Convert shmem offsets into addresses as seen by this process. This
! * is just to speed up the BufferGetBlock() macro. It is OK to do this
! * without any lock since the data pointers never change.
*/
for (i = 0; i < NBuffers; i++)
BufferBlockPointers[i] = (Block) MAKE_PTR(BufferDescriptors[i].data);
***************
*** 201,214 ****
/* size of data pages */
size += NBuffers * MAXALIGN(BLCKSZ);
! /* size of buffer hash table */
! size += hash_estimate_size(NBuffers * 2, sizeof(BufferLookupEnt));
!
! /* size of the shared replacement strategy control block */
! size += MAXALIGN(sizeof(BufferStrategyControl));
!
! /* size of the ARC directory blocks */
! size += MAXALIGN(NBuffers * 2 * sizeof(BufferStrategyCDB));
return size;
}
--- 204,211 ----
/* size of data pages */
size += NBuffers * MAXALIGN(BLCKSZ);! /* size of stuff controlled by freelist.c */
! size += StrategyShmemSize();
return size;
}
*** src/backend/storage/buffer/buf_table.c.orig Fri Dec 31 17:46:08 2004
--- src/backend/storage/buffer/buf_table.c Thu Feb 3 14:40:17 2005
***************
*** 1,11 ****
/*-------------------------------------------------------------------------
*
* buf_table.c
! * routines for finding buffers in the buffer pool.
*
! * NOTE: these days, what this table actually provides is a mapping from
! * BufferTags to CDB indexes, not directly to buffers. The function names
! * are thus slight misnomers.
*
* Note: all routines in this file assume that the BufMgrLock is held
* by the caller, so no synchronization is needed.
--- 1,11 ----
/*-------------------------------------------------------------------------
*
* buf_table.c
! * routines for mapping BufferTags to buffer indexes.
*
! * NOTE: this module is called only by freelist.c, and the "buffer IDs"
! * it deals with are whatever freelist.c needs them to be; they may not be
! * directly equivalent to Buffer numbers.
*
* Note: all routines in this file assume that the BufMgrLock is held
* by the caller, so no synchronization is needed.
***************
*** 26,37 ****
#include "storage/bufmgr.h"static HTAB *SharedBufHash;
/*
* Initialize shmem hash table for mapping buffers
! * size is the desired hash table size (2*NBuffers for ARC algorithm)
*/
void
InitBufTable(int size)
--- 26,54 ----
#include "storage/bufmgr.h"+ /* entry for buffer lookup hashtable */
+ typedef struct
+ {
+ BufferTag key; /* Tag of a disk page */
+ int id; /* Associated buffer ID */
+ } BufferLookupEnt;
+
static HTAB *SharedBufHash; /*
+ * Estimate space needed for mapping hashtable
+ * size is the desired hash table size (possibly more than NBuffers)
+ */
+ int
+ BufTableShmemSize(int size)
+ {
+ return hash_estimate_size(size, sizeof(BufferLookupEnt));
+ }
+
+ /*
* Initialize shmem hash table for mapping buffers
! * size is the desired hash table size (possibly more than NBuffers)
*/
void
InitBufTable(int size)
***************
*** 56,62 **** /*
* BufTableLookup
! * Lookup the given BufferTag; return CDB index, or -1 if not found
*/
int
BufTableLookup(BufferTag *tagPtr)
--- 73,79 ---- /*
* BufTableLookup
! * Lookup the given BufferTag; return buffer ID, or -1 if not found
*/
int
BufTableLookup(BufferTag *tagPtr)
***************
*** 76,85 ****
/*
* BufTableInsert
! * Insert a hashtable entry for given tag and CDB index
*/
void
! BufTableInsert(BufferTag *tagPtr, int cdb_id)
{
BufferLookupEnt *result;
bool found;
--- 93,102 ---- /*
* BufTableInsert
! * Insert a hashtable entry for given tag and buffer ID
*/
void
! BufTableInsert(BufferTag *tagPtr, int buf_id)
{
BufferLookupEnt *result;
bool found;
***************
*** 92,106 ****
(errcode(ERRCODE_OUT_OF_MEMORY),
errmsg("out of shared memory")));
! if (found) /* found something else in the table? */
elog(ERROR, "shared buffer hash table corrupted");
! result->id = cdb_id;
}
/*
* BufTableDelete
! * Delete the hashtable entry for given tag
*/
void
BufTableDelete(BufferTag *tagPtr)
--- 109,123 ----
(errcode(ERRCODE_OUT_OF_MEMORY),
errmsg("out of shared memory")));! if (found) /* found something already in the table? */
elog(ERROR, "shared buffer hash table corrupted");
! result->id = buf_id;
}
/*
* BufTableDelete
! * Delete the hashtable entry for given tag (which must exist)
*/
void
BufTableDelete(BufferTag *tagPtr)
*** src/backend/storage/buffer/freelist.c.orig Fri Dec 31 17:46:08 2004
--- src/backend/storage/buffer/freelist.c Thu Feb 3 14:45:50 2005
***************
*** 25,30 ****
--- 25,75 ----
#include "storage/bufmgr.h"+ /*
+ * Definitions for the buffer replacement strategy
+ */
+ #define STRAT_LIST_UNUSED (-1)
+ #define STRAT_LIST_B1 0
+ #define STRAT_LIST_T1 1
+ #define STRAT_LIST_T2 2
+ #define STRAT_LIST_B2 3
+ #define STRAT_NUM_LISTS 4
+
+ /*
+ * The Cache Directory Block (CDB) of the Adaptive Replacement Cache (ARC)
+ */
+ typedef struct
+ {
+ int prev; /* list links */
+ int next;
+ short list; /* ID of list it is currently in */
+ bool t1_vacuum; /* t => present only because of VACUUM */
+ TransactionId t1_xid; /* the xid this entry went onto T1 */
+ BufferTag buf_tag; /* page identifier */
+ int buf_id; /* currently assigned data buffer, or -1 */
+ } BufferStrategyCDB;
+
+ /*
+ * The shared ARC control information.
+ */
+ typedef struct
+ {
+ int target_T1_size; /* What T1 size are we aiming for */
+ int listUnusedCDB; /* All unused StrategyCDB */
+ int listHead[STRAT_NUM_LISTS]; /* ARC lists B1, T1, T2
+ * and B2 */
+ int listTail[STRAT_NUM_LISTS];
+ int listSize[STRAT_NUM_LISTS];
+ Buffer listFreeBuffers; /* List of unused buffers */
+
+ long num_lookup; /* Some hit statistics */
+ long num_hit[STRAT_NUM_LISTS];
+ time_t stat_report;
+
+ /* Array of CDB's starts here */
+ BufferStrategyCDB cdb[1]; /* VARIABLE SIZE ARRAY */
+ } BufferStrategyControl;
+
/* GUC variable: time in seconds between statistics reports */
int DebugSharedBuffers = 0;***************
*** 811,816 ****
--- 856,883 ----
return num_buffer_dirty;
}+
+ /*
+ * StrategyShmemSize
+ *
+ * estimate the size of shared memory used by the freelist-related structures.
+ */
+ int
+ StrategyShmemSize(void)
+ {
+ int size = 0;
+
+ /* size of CDB lookup hash table */
+ size += BufTableShmemSize(NBuffers * 2);
+
+ /* size of the shared replacement strategy control block */
+ size += MAXALIGN(sizeof(BufferStrategyControl));
+
+ /* size of the ARC directory blocks */
+ size += MAXALIGN(NBuffers * 2 * sizeof(BufferStrategyCDB));
+
+ return size;
+ } /*
* StrategyInitialize -- initialize the buffer cache replacement
*** src/include/storage/buf_internals.h.orig Fri Dec 31 17:47:02 2004
--- src/include/storage/buf_internals.h Thu Feb 3 14:51:11 2005
***************
*** 17,24 **** #include "storage/backendid.h"
#include "storage/buf.h"
- #include "storage/lmgr.h"
#include "storage/lwlock.h"
/*
--- 17,25 ---- #include "storage/backendid.h"
#include "storage/buf.h"
#include "storage/lwlock.h"
+ #include "storage/shmem.h"
+ #include "utils/rel.h"
/*
***************
*** 40,49 ****
* Buffer tag identifies which disk block the buffer contains.
*
* Note: the BufferTag data must be sufficient to determine where to write the
! * block, even during a "blind write" with no relcache entry. It's possible
! * that the backend flushing the buffer doesn't even believe the relation is
! * visible yet (its xact may have started before the xact that created the
! * rel). The storage manager must be able to cope anyway.
*
* Note: if there's any pad bytes in the struct, INIT_BUFFERTAG will have
* to be fixed to zero them, since this struct is used as a hash key.
--- 41,50 ----
* Buffer tag identifies which disk block the buffer contains.
*
* Note: the BufferTag data must be sufficient to determine where to write the
! * block, without reference to pg_class or pg_tablespace entries. It's
! * possible that the backend flushing the buffer doesn't even believe the
! * relation is visible yet (its xact may have started before the xact that
! * created the rel). The storage manager must be able to cope anyway.
*
* Note: if there's any pad bytes in the struct, INIT_BUFFERTAG will have
* to be fixed to zero them, since this struct is used as a hash key.
***************
*** 107,164 ****#define BufferDescriptorGetBuffer(bdesc) ((bdesc)->buf_id + 1)
- /* entry for buffer lookup hashtable */
- typedef struct
- {
- BufferTag key; /* Tag of a disk page */
- int id; /* CDB id of associated CDB */
- } BufferLookupEnt;
! /*
! * Definitions for the buffer replacement strategy
! */
! #define STRAT_LIST_UNUSED (-1)
! #define STRAT_LIST_B1 0
! #define STRAT_LIST_T1 1
! #define STRAT_LIST_T2 2
! #define STRAT_LIST_B2 3
! #define STRAT_NUM_LISTS 4
!
! /*
! * The Cache Directory Block (CDB) of the Adaptive Replacement Cache (ARC)
! */
! typedef struct
! {
! int prev; /* list links */
! int next;
! short list; /* ID of list it is currently in */
! bool t1_vacuum; /* t => present only because of VACUUM */
! TransactionId t1_xid; /* the xid this entry went onto T1 */
! BufferTag buf_tag; /* page identifier */
! int buf_id; /* currently assigned data buffer, or -1 */
! } BufferStrategyCDB;
!
! /*
! * The shared ARC control information.
! */
! typedef struct
! {
! int target_T1_size; /* What T1 size are we aiming for */
! int listUnusedCDB; /* All unused StrategyCDB */
! int listHead[STRAT_NUM_LISTS]; /* ARC lists B1, T1, T2
! * and B2 */
! int listTail[STRAT_NUM_LISTS];
! int listSize[STRAT_NUM_LISTS];
! Buffer listFreeBuffers; /* List of unused buffers */
!
! long num_lookup; /* Some hit statistics */
! long num_hit[STRAT_NUM_LISTS];
! time_t stat_report;
!
! /* Array of CDB's starts here */
! BufferStrategyCDB cdb[1]; /* VARIABLE SIZE ARRAY */
! } BufferStrategyControl;
/* counters in buf_init.c */
extern long int ReadBufferCount;
--- 108,119 ----#define BufferDescriptorGetBuffer(bdesc) ((bdesc)->buf_id + 1)
! /* in bufmgr.c */
! extern BufferDesc *BufferDescriptors;
+ /* in localbuf.c */
+ extern BufferDesc *LocalBufferDescriptors; /* counters in buf_init.c */
extern long int ReadBufferCount;
***************
*** 170,180 ****
/*
! * Bufmgr Interface:
*/
- /* Internal routines: only called by bufmgr */
-
/* freelist.c */
extern BufferDesc *StrategyBufferLookup(BufferTag *tagPtr, bool recheck,
int *cdb_found_index);
--- 125,133 ---- /*
! * Internal routines: only called by bufmgr
*/
/* freelist.c */
extern BufferDesc *StrategyBufferLookup(BufferTag *tagPtr, bool recheck,
int *cdb_found_index);
***************
*** 185,204 ****
extern void StrategyHintVacuum(bool vacuum_active);
extern int StrategyDirtyBufferList(BufferDesc **buffers, BufferTag *buftags,
int max_buffers);
extern void StrategyInitialize(bool init);
/* buf_table.c */
extern void InitBufTable(int size);
extern int BufTableLookup(BufferTag *tagPtr);
! extern void BufTableInsert(BufferTag *tagPtr, int cdb_id);
extern void BufTableDelete(BufferTag *tagPtr);
- /* bufmgr.c */
- extern BufferDesc *BufferDescriptors;
-
/* localbuf.c */
- extern BufferDesc *LocalBufferDescriptors;
-
extern BufferDesc *LocalBufferAlloc(Relation reln, BlockNumber blockNum,
bool *foundPtr);
extern void WriteLocalBuffer(Buffer buffer, bool release);
--- 138,154 ----
extern void StrategyHintVacuum(bool vacuum_active);
extern int StrategyDirtyBufferList(BufferDesc **buffers, BufferTag *buftags,
int max_buffers);
+ extern int StrategyShmemSize(void);
extern void StrategyInitialize(bool init); /* buf_table.c */
+ extern int BufTableShmemSize(int size);
extern void InitBufTable(int size);
extern int BufTableLookup(BufferTag *tagPtr);
! extern void BufTableInsert(BufferTag *tagPtr, int buf_id);
extern void BufTableDelete(BufferTag *tagPtr);
/* localbuf.c */
extern BufferDesc *LocalBufferAlloc(Relation reln, BlockNumber blockNum,
bool *foundPtr);
extern void WriteLocalBuffer(Buffer buffer, bool release);