From 107aa2af2966c10ce750e6b410ae570462423aab Mon Sep 17 00:00:00 2001 From: Masahiko Sawada Date: Wed, 22 Feb 2023 14:43:15 +0900 Subject: [PATCH v29 11/11] Debug TIDStore. --- src/backend/access/common/tidstore.c | 242 ++++++++++++++++++++++++++- 1 file changed, 238 insertions(+), 4 deletions(-) diff --git a/src/backend/access/common/tidstore.c b/src/backend/access/common/tidstore.c index 9360520482..438bf0c800 100644 --- a/src/backend/access/common/tidstore.c +++ b/src/backend/access/common/tidstore.c @@ -28,12 +28,20 @@ #include "postgres.h" #include "access/tidstore.h" +#include "catalog/index.h" #include "miscadmin.h" #include "port/pg_bitutils.h" #include "storage/lwlock.h" #include "utils/dsa.h" #include "utils/memutils.h" +#define TIDSTORE_DEBUG + +/* Enable TidStore debugging only when USE_ASSERT_CHECKING */ +#if defined(TIDSTORE_DEBUG) && !defined(USE_ASSERT_CHECKING) +#undef TIDSTORE_DEBUG +#endif + /* * For encoding purposes, a tid is represented as a pair of 64-bit key and * 64-bit value. @@ -115,6 +123,12 @@ typedef struct TidStoreControl /* handles for TidStore and radix tree */ TidStoreHandle handle; shared_rt_handle tree_handle; + +#ifdef TIDSTORE_DEBUG + dsm_handle tids_handle; + int64 max_tids; + bool tids_unordered; +#endif } TidStoreControl; /* Per-backend state for a TidStore */ @@ -135,6 +149,11 @@ struct TidStore /* DSA area for TidStore if used */ dsa_area *area; + +#ifdef TIDSTORE_DEBUG + dsm_segment *tids_seg; + ItemPointerData *tids; +#endif }; #define TidStoreIsShared(ts) ((ts)->area != NULL) @@ -157,6 +176,11 @@ typedef struct TidStoreIter tidkey next_tidkey; offsetbm next_off_bitmap; +#ifdef TIDSTORE_DEBUG + /* iterator index for the ts->tids array */ + int64 tids_idx; +#endif + /* * output for the caller. Must be last because variable-size. */ @@ -169,6 +193,15 @@ static inline tidkey encode_blk_off(TidStore *ts, BlockNumber block, OffsetNumber offset, offsetbm *off_bit); static inline tidkey encode_tid(TidStore *ts, ItemPointer tid, offsetbm *off_bit); +/* debug functions available only when TIDSTORE_DEBUG */ +#ifdef TIDSTORE_DEBUG +static void ts_debug_set_block_offsets(TidStore *ts, BlockNumber blkno, OffsetNumber *offsets, + int num_offsets); +static void ts_debug_iter_check_tids(TidStoreIter *iter); +static bool ts_debug_is_member(TidStore *ts, ItemPointer tid); +static int itemptr_cmp(const void *left, const void *right); +#endif + /* * Create a TidStore. The returned object is allocated in backend-local memory. * The radix tree for storage is allocated in DSA area is 'area' is non-NULL. @@ -237,6 +270,26 @@ TidStoreCreate(size_t max_bytes, int max_off, dsa_area *area) ts->control->upper_off_nbits = ts->control->max_off_nbits - LOWER_OFFSET_NBITS; +#ifdef TIDSTORE_DEBUG + { + int64 max_tids = max_bytes / sizeof(ItemPointerData); + + /* Allocate the array of tids too */ + if (TidStoreIsShared(ts)) + { + ts->tids_seg = dsm_create(sizeof(ItemPointerData) * max_tids, 0); + ts->tids = dsm_segment_address(ts->tids_seg); + ts->control->tids_handle = dsm_segment_handle(ts->tids_seg); + ts->control->max_tids = max_tids; + } + else + { + ts->tids = palloc(sizeof(ItemPointerData) * max_tids); + ts->control->max_tids = max_tids; + } + } +#endif + return ts; } @@ -266,6 +319,11 @@ TidStoreAttach(dsa_area *area, TidStoreHandle handle) ts->tree.shared = shared_rt_attach(area, ts->control->tree_handle); ts->area = area; +#ifdef TIDSTORE_DEBUG + ts->tids_seg = dsm_attach(ts->control->tids_handle); + ts->tids = (ItemPointer) dsm_segment_address(ts->tids_seg); +#endif + return ts; } @@ -280,6 +338,11 @@ TidStoreDetach(TidStore *ts) { Assert(TidStoreIsShared(ts) && ts->control->magic == TIDSTORE_MAGIC); +#ifdef TIDSTORE_DEBUG + if (TidStoreIsShared(ts)) + dsm_detach(ts->tids_seg); +#endif + shared_rt_detach(ts->tree.shared); pfree(ts); } @@ -315,6 +378,13 @@ TidStoreDestroy(TidStore *ts) local_rt_free(ts->tree.local); } +#ifdef TIDSTORE_DEBUG + if (TidStoreIsShared(ts)) + dsm_detach(ts->tids_seg); + else + pfree(ts->tids); +#endif + pfree(ts); } @@ -434,6 +504,11 @@ TidStoreSetBlockOffsets(TidStore *ts, BlockNumber blkno, OffsetNumber *offsets, } } +#ifdef TIDSTORE_DEBUG + /* Insert tids into the tid array too */ + ts_debug_set_block_offsets(ts, blkno, offsets, num_offsets); +#endif + /* update statistics */ ts->control->num_tids += num_offsets; @@ -451,6 +526,11 @@ TidStoreIsMember(TidStore *ts, ItemPointer tid) offsetbm off_bitmap = 0; offsetbm off_bit; bool found; + bool ret; + +#ifdef TIDSTORE_DEBUG + bool ret_debug = ts_debug_is_member(ts, tid); +#endif key = encode_tid(ts, tid, &off_bit); @@ -460,9 +540,20 @@ TidStoreIsMember(TidStore *ts, ItemPointer tid) found = local_rt_search(ts->tree.local, key, &off_bitmap); if (!found) + { +#ifdef TIDSTORE_DEBUG + Assert(!ret_debug); +#endif return false; + } + + ret = (off_bitmap & off_bit) != 0; - return (off_bitmap & off_bit) != 0; +#ifdef TIDSTORE_DEBUG + Assert(ret == ret_debug); +#endif + + return ret; } /* @@ -494,6 +585,10 @@ TidStoreBeginIterate(TidStore *ts) if (TidStoreNumTids(ts) == 0) iter->finished = true; +#ifdef TIDSTORE_DEBUG + iter->tids_idx = 0; +#endif + return iter; } @@ -515,6 +610,7 @@ TidStoreIterResult * TidStoreIterateNext(TidStoreIter *iter) { tidkey key; + bool iter_found; offsetbm off_bitmap = 0; TidStoreIterResult *output = &(iter->output); @@ -532,7 +628,7 @@ TidStoreIterateNext(TidStoreIter *iter) if (iter->next_off_bitmap > 0) iter_decode_key_off(iter, iter->next_tidkey, iter->next_off_bitmap); - while (tidstore_iter(iter, &key, &off_bitmap)) + while ((iter_found = tidstore_iter(iter, &key, &off_bitmap))) { BlockNumber blkno = key_get_blkno(iter->ts, key); @@ -545,14 +641,20 @@ TidStoreIterateNext(TidStoreIter *iter) */ iter->next_tidkey = key; iter->next_off_bitmap = off_bitmap; - return output; + break; } /* Collect tids decoded from the key and offset bitmap */ iter_decode_key_off(iter, key, off_bitmap); } - iter->finished = true; + if (!iter_found) + iter->finished = true; + +#ifdef TIDSTORE_DEBUG + ts_debug_iter_check_tids(iter); +#endif + return output; } @@ -699,3 +801,135 @@ encode_blk_off(TidStore *ts, BlockNumber block, OffsetNumber offset, return key; } + +#ifdef TIDSTORE_DEBUG +/* Comparator routines for ItemPointer */ +static int +itemptr_cmp(const void *left, const void *right) +{ + BlockNumber lblk, + rblk; + OffsetNumber loff, + roff; + + lblk = ItemPointerGetBlockNumber((ItemPointer) left); + rblk = ItemPointerGetBlockNumber((ItemPointer) right); + + if (lblk < rblk) + return -1; + if (lblk > rblk) + return 1; + + loff = ItemPointerGetOffsetNumber((ItemPointer) left); + roff = ItemPointerGetOffsetNumber((ItemPointer) right); + + if (loff < roff) + return -1; + if (loff > roff) + return 1; + + return 0; +} + +/* Insert tids to the tid array for debugging */ +static void +ts_debug_set_block_offsets(TidStore *ts, BlockNumber blkno, OffsetNumber *offsets, + int num_offsets) +{ + if (ts->control->num_tids > 0 && + blkno < ItemPointerGetBlockNumber(&(ts->tids[ts->control->num_tids - 1]))) + { + /* The array will be sorted at ts_debug_is_member() */ + ts->control->tids_unordered = true; + } + + for (int i = 0; i < num_offsets; i++) + { + ItemPointer tid; + int idx = ts->control->num_tids + i; + + /* Enlarge the tid array if necessary */ + if (idx >= ts->control->max_tids) + { + ts->control->max_tids *= 2; + + if (TidStoreIsShared(ts)) + { + dsm_segment *new_seg = + dsm_create(sizeof(ItemPointerData) * ts->control->max_tids, 0); + ItemPointer new_tids = dsm_segment_address(new_seg); + + /* copy tids from old to new array */ + memcpy(new_tids, ts->tids, + sizeof(ItemPointerData) * (ts->control->max_tids / 2)); + + dsm_detach(ts->tids_seg); + ts->tids = new_tids; + } + else + ts->tids = repalloc(ts->tids, + sizeof(ItemPointerData) * ts->control->max_tids); + } + + tid = &(ts->tids[idx]); + ItemPointerSetBlockNumber(tid, blkno); + ItemPointerSetOffsetNumber(tid, offsets[i]); + } +} + +/* Return true if the given tid is present in the tid array */ +static bool +ts_debug_is_member(TidStore *ts, ItemPointer tid) +{ + int64 litem, + ritem, + item; + ItemPointer res; + + if (ts->control->num_tids == 0) + return false; + + /* Make sure the tid array is sorted */ + if (ts->control->tids_unordered) + { + qsort(ts->tids, ts->control->num_tids, sizeof(ItemPointerData), itemptr_cmp); + ts->control->tids_unordered = false; + } + + litem = itemptr_encode(&ts->tids[0]); + ritem = itemptr_encode(&ts->tids[ts->control->num_tids - 1]); + item = itemptr_encode(tid); + + /* + * Doing a simple bound check before bsearch() is useful to avoid the + * extra cost of bsearch(), especially if dead items on the heap are + * concentrated in a certain range. Since this function is called for + * every index tuple, it pays to be really fast. + */ + if (item < litem || item > ritem) + return false; + + res = bsearch(tid, ts->tids, ts->control->num_tids, sizeof(ItemPointerData), + itemptr_cmp); + + return (res != NULL); +} + +/* Verify if the iterator output matches the tids in the array for debugging */ +static void +ts_debug_iter_check_tids(TidStoreIter *iter) +{ + BlockNumber blkno = iter->output.blkno; + + for (int i = 0; i < iter->output.num_offsets; i++) + { + ItemPointer tid = &(iter->ts->tids[iter->tids_idx + i]); + + Assert((iter->tids_idx + i) < iter->ts->control->max_tids); + Assert(ItemPointerGetBlockNumber(tid) == blkno); + Assert(ItemPointerGetOffsetNumber(tid) == iter->output.offsets[i]); + } + + iter->tids_idx += iter->output.num_offsets; +} +#endif -- 2.31.1