agora inbox for [email protected]
help / color / mirror / Atom feedamcheck verification for GiST
12+ messages / 7 participants
[nested] [flat]
* amcheck verification for GiST
@ 2018-09-23 10:15 Andrey Borodin <[email protected]>
0 siblings, 1 reply; 12+ messages in thread
From: Andrey Borodin @ 2018-09-23 10:15 UTC (permalink / raw)
To: pgsql-hackers
Hi, hackers!
Here's the patch with amcheck functionality for GiST.
It basically checks two invariants:
1. Every internal tuple need no adjustment by tuples of referenced page
2. Internal page reference or only leaf pages or only internal pages
We actually cannot check all balanced tree invariants due to concurrency reasons some concurrent splits will be visible as temporary balance violations.
Are there any other invariants that we can check?
I'd be happy to hear any thought about this.
Best regards, Andrey Borodin.
Attachments:
[application/octet-stream] 0001-GiST-verification-function-for-amcheck.patch (12.6K, ../../[email protected]/2-0001-GiST-verification-function-for-amcheck.patch)
download | inline diff:
From 6e50f29e7a040c8caef07d3b8b68d9333e7e1401 Mon Sep 17 00:00:00 2001
From: Andrey Borodin <[email protected]>
Date: Sun, 23 Sep 2018 14:59:54 +0500
Subject: [PATCH] GiST verification function for amcheck
Function gist_index_check() verifies that in target GiST every internal tuple need no extension by underlying subtree tuples and page graph respects balanced-tree invariants.
---
contrib/amcheck/Makefile | 6 +-
contrib/amcheck/amcheck--1.1--1.2.sql | 14 ++
contrib/amcheck/amcheck.control | 2 +-
contrib/amcheck/expected/check_gist.out | 9 +
contrib/amcheck/sql/check_gist.sql | 4 +
contrib/amcheck/verify_gist.c | 272 ++++++++++++++++++++++++
doc/src/sgml/amcheck.sgml | 19 ++
7 files changed, 322 insertions(+), 4 deletions(-)
create mode 100644 contrib/amcheck/amcheck--1.1--1.2.sql
create mode 100644 contrib/amcheck/expected/check_gist.out
create mode 100644 contrib/amcheck/sql/check_gist.sql
create mode 100644 contrib/amcheck/verify_gist.c
diff --git a/contrib/amcheck/Makefile b/contrib/amcheck/Makefile
index c5764b544f..dd9b5ecf92 100644
--- a/contrib/amcheck/Makefile
+++ b/contrib/amcheck/Makefile
@@ -1,13 +1,13 @@
# contrib/amcheck/Makefile
MODULE_big = amcheck
-OBJS = verify_nbtree.o $(WIN32RES)
+OBJS = verify_nbtree.o verify_gist.o $(WIN32RES)
EXTENSION = amcheck
-DATA = amcheck--1.0--1.1.sql amcheck--1.0.sql
+DATA = amcheck--1.1--1.2.sql amcheck--1.0--1.1.sql amcheck--1.0.sql
PGFILEDESC = "amcheck - function for verifying relation integrity"
-REGRESS = check check_btree
+REGRESS = check check_btree check_gist
ifdef USE_PGXS
PG_CONFIG = pg_config
diff --git a/contrib/amcheck/amcheck--1.1--1.2.sql b/contrib/amcheck/amcheck--1.1--1.2.sql
new file mode 100644
index 0000000000..6888900303
--- /dev/null
+++ b/contrib/amcheck/amcheck--1.1--1.2.sql
@@ -0,0 +1,14 @@
+/* amcheck--1.1--1.2.sql */
+
+-- complain if script is sourced in psql, rather than via CREATE EXTENSION
+\echo Use "ALTER EXTENSION amcheck UPDATE TO '1.2'" to load this file. \quit
+
+--
+-- gist_index_check()
+--
+CREATE FUNCTION gist_index_check(index regclass)
+RETURNS VOID
+AS 'MODULE_PATHNAME', 'gist_index_check'
+LANGUAGE C STRICT;
+
+REVOKE ALL ON FUNCTION gist_index_check(regclass) FROM PUBLIC;
diff --git a/contrib/amcheck/amcheck.control b/contrib/amcheck/amcheck.control
index 469048403d..c6e310046d 100644
--- a/contrib/amcheck/amcheck.control
+++ b/contrib/amcheck/amcheck.control
@@ -1,5 +1,5 @@
# amcheck extension
comment = 'functions for verifying relation integrity'
-default_version = '1.1'
+default_version = '1.2'
module_pathname = '$libdir/amcheck'
relocatable = true
diff --git a/contrib/amcheck/expected/check_gist.out b/contrib/amcheck/expected/check_gist.out
new file mode 100644
index 0000000000..d8ad66805b
--- /dev/null
+++ b/contrib/amcheck/expected/check_gist.out
@@ -0,0 +1,9 @@
+-- minimal test, basically just verifying that amcheck works with GiST
+CREATE TABLE gist_check AS SELECT point(s,1) c FROM generate_series(1,10000) s;
+CREATE INDEX gist_check_idx ON gist_check USING gist(c);
+SELECT gist_index_check('gist_check_idx');
+ gist_index_check
+------------------
+
+(1 row)
+
diff --git a/contrib/amcheck/sql/check_gist.sql b/contrib/amcheck/sql/check_gist.sql
new file mode 100644
index 0000000000..585c455ca5
--- /dev/null
+++ b/contrib/amcheck/sql/check_gist.sql
@@ -0,0 +1,4 @@
+-- minimal test, basically just verifying that amcheck works with GiST
+CREATE TABLE gist_check AS SELECT point(s,1) c FROM generate_series(1,10000) s;
+CREATE INDEX gist_check_idx ON gist_check USING gist(c);
+SELECT gist_index_check('gist_check_idx');
diff --git a/contrib/amcheck/verify_gist.c b/contrib/amcheck/verify_gist.c
new file mode 100644
index 0000000000..c5287ec57c
--- /dev/null
+++ b/contrib/amcheck/verify_gist.c
@@ -0,0 +1,272 @@
+/*-------------------------------------------------------------------------
+ *
+ * verify_nbtree.c
+ * Verifies the integrity of GiST indexes based on invariants.
+ *
+ * Verification checks that all paths in GiST graph are contatining
+ * consisnent keys: tuples on parent pages consistently include tuples
+ * from children pages. Also, verification checks graph invariants:
+ * internal page must have at least one downlinks, internal page can
+ * reference either only leaf pages or only internal pages.
+ *
+ *
+ * Copyright (c) 2017-2018, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ * contrib/amcheck/verify_gist.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "access/gist_private.h"
+#include "access/htup_details.h"
+#include "access/transam.h"
+#include "catalog/index.h"
+#include "catalog/pg_am.h"
+#include "commands/tablecmds.h"
+#include "miscadmin.h"
+#include "storage/lmgr.h"
+#include "utils/memutils.h"
+#include "utils/snapmgr.h"
+
+typedef struct GistScanItem
+{
+ GistNSN parentlsn;
+ BlockNumber blkno;
+ struct GistScanItem *next;
+} GistScanItem;
+
+/*
+ * For every tuple on page check if it is contained by tuple on parent page
+ */
+static inline void
+gist_check_page_keys(Relation rel, Page parentpage, Page page, IndexTuple parent, GISTSTATE *state)
+{
+ OffsetNumber i,
+ maxoff = PageGetMaxOffsetNumber(page);
+
+ for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
+ {
+ ItemId iid = PageGetItemId(page, i);
+ IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
+
+ if (GistTupleIsInvalid(idxtuple))
+ ereport(LOG,
+ (errmsg("index \"%s\" contains an inner tuple marked as invalid",
+ RelationGetRelationName(rel)),
+ errdetail("This is caused by an incomplete page split at crash recovery before upgrading to PostgreSQL 9.1."),
+ errhint("Please REINDEX it.")));
+
+ /*
+ * Tree is inconsistent if adjustement is necessary for any parent tuple
+ */
+ if (gistgetadjusted(rel, parent, idxtuple, state))
+ ereport(ERROR,
+ (errcode(ERRCODE_INDEX_CORRUPTED),
+ errmsg("index \"%s\" has inconsistent records",
+ RelationGetRelationName(rel))));
+ }
+}
+
+/* Check of an internal page. Hold locks on two pages at a time (parent+child). */
+static inline bool
+gist_check_internal_page(Relation rel, Page page, BufferAccessStrategy strategy, GISTSTATE *state)
+{
+ bool has_leafs = false;
+ bool has_internals = false;
+ OffsetNumber i,
+ maxoff = PageGetMaxOffsetNumber(page);
+
+ for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
+ {
+ ItemId iid = PageGetItemId(page, i);
+ IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
+
+ BlockNumber child_blkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
+ Buffer buffer;
+ Page child_page;
+
+ if (GistTupleIsInvalid(idxtuple))
+ ereport(LOG,
+ (errmsg("index \"%s\" contains an inner tuple marked as invalid",
+ RelationGetRelationName(rel)),
+ errdetail("This is caused by an incomplete page split at crash recovery before upgrading to PostgreSQL 9.1."),
+ errhint("Please REINDEX it.")));
+
+ buffer = ReadBufferExtended(rel, MAIN_FORKNUM, child_blkno,
+ RBM_NORMAL, strategy);
+
+ LockBuffer(buffer, GIST_SHARE);
+ gistcheckpage(rel, buffer);
+ child_page = (Page) BufferGetPage(buffer);
+
+ has_leafs = has_leafs || GistPageIsLeaf(child_page);
+ has_internals = has_internals || !GistPageIsLeaf(child_page);
+ gist_check_page_keys(rel, page, child_page, idxtuple, state);
+
+ UnlockReleaseBuffer(buffer);
+ }
+
+ if (!(has_leafs || has_internals))
+ ereport(ERROR,
+ (errcode(ERRCODE_INDEX_CORRUPTED),
+ errmsg("index \"%s\" internal page has no downlink references",
+ RelationGetRelationName(rel))));
+
+
+ if (has_leafs == has_internals)
+ ereport(ERROR,
+ (errcode(ERRCODE_INDEX_CORRUPTED),
+ errmsg("index \"%s\" page references both internal and leaf pages",
+ RelationGetRelationName(rel))));
+
+ return has_internals;
+}
+
+/* add pages with unfinished split to scan */
+static void
+pushStackIfSplited(Page page, GistScanItem *stack)
+{
+ GISTPageOpaque opaque = GistPageGetOpaque(page);
+
+ if (stack->blkno != GIST_ROOT_BLKNO && !XLogRecPtrIsInvalid(stack->parentlsn) &&
+ (GistFollowRight(page) || stack->parentlsn < GistPageGetNSN(page)) &&
+ opaque->rightlink != InvalidBlockNumber /* sanity check */ )
+ {
+ /* split page detected, install right link to the stack */
+
+ GistScanItem *ptr = (GistScanItem *) palloc(sizeof(GistScanItem));
+
+ ptr->blkno = opaque->rightlink;
+ ptr->parentlsn = stack->parentlsn;
+ ptr->next = stack->next;
+ stack->next = ptr;
+ }
+}
+
+/*
+ * Main entry point for GiST check. Allocates memory context and scans
+ * through GiST graph.
+ */
+static inline void
+gist_check_keys_consistency(Relation rel)
+{
+ GistScanItem *stack,
+ *ptr;
+
+ BufferAccessStrategy strategy = GetAccessStrategy(BAS_BULKREAD);
+
+ MemoryContext mctx = AllocSetContextCreate(CurrentMemoryContext,
+ "amcheck context",
+#if PG_VERSION_NUM >= 110000
+ ALLOCSET_DEFAULT_SIZES);
+#else
+ ALLOCSET_DEFAULT_MINSIZE,
+ ALLOCSET_DEFAULT_INITSIZE,
+ ALLOCSET_DEFAULT_MAXSIZE);
+#endif
+
+ MemoryContext oldcontext = MemoryContextSwitchTo(mctx);
+ GISTSTATE *state = initGISTstate(rel);
+
+ stack = (GistScanItem *) palloc0(sizeof(GistScanItem));
+ stack->blkno = GIST_ROOT_BLKNO;
+
+ while (stack)
+ {
+ Buffer buffer;
+ Page page;
+ OffsetNumber i,
+ maxoff;
+ IndexTuple idxtuple;
+ ItemId iid;
+
+ buffer = ReadBufferExtended(rel, MAIN_FORKNUM, stack->blkno,
+ RBM_NORMAL, strategy);
+ LockBuffer(buffer, GIST_SHARE);
+ gistcheckpage(rel, buffer);
+ page = (Page) BufferGetPage(buffer);
+
+ if (GistPageIsLeaf(page))
+ {
+ /* should never happen unless it is root */
+ Assert(stack->blkno == GIST_ROOT_BLKNO);
+ }
+ else
+ {
+ /* check for split proceeded after look at parent */
+ pushStackIfSplited(page, stack);
+
+ maxoff = PageGetMaxOffsetNumber(page);
+
+ if (gist_check_internal_page(rel, page, strategy, state))
+ {
+ for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
+ {
+ iid = PageGetItemId(page, i);
+ idxtuple = (IndexTuple) PageGetItem(page, iid);
+
+ ptr = (GistScanItem *) palloc(sizeof(GistScanItem));
+ ptr->blkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
+ ptr->parentlsn = BufferGetLSNAtomic(buffer);
+ ptr->next = stack->next;
+ stack->next = ptr;
+ }
+ }
+ }
+
+ UnlockReleaseBuffer(buffer);
+
+ ptr = stack->next;
+ pfree(stack);
+ stack = ptr;
+ }
+
+ MemoryContextSwitchTo(oldcontext);
+ MemoryContextDelete(mctx);
+}
+
+/* Check that relation is eligible for GiST verification */
+static inline void
+gist_index_checkable(Relation rel)
+{
+ if (rel->rd_rel->relkind != RELKIND_INDEX ||
+ rel->rd_rel->relam != GIST_AM_OID)
+ ereport(ERROR,
+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ errmsg("only GiST indexes are supported as targets for this verification"),
+ errdetail("Relation \"%s\" is not a GiST index.",
+ RelationGetRelationName(rel))));
+
+ if (RELATION_IS_OTHER_TEMP(rel))
+ ereport(ERROR,
+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ errmsg("cannot access temporary tables of other sessions"),
+ errdetail("Index \"%s\" is associated with temporary relation.",
+ RelationGetRelationName(rel))));
+
+ if (!IndexIsValid(rel->rd_index))
+ ereport(ERROR,
+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ errmsg("cannot check index \"%s\"",
+ RelationGetRelationName(rel)),
+ errdetail("Index is not valid")));
+}
+
+PG_FUNCTION_INFO_V1(gist_index_check);
+
+Datum
+gist_index_check(PG_FUNCTION_ARGS)
+{
+ Oid indrelid = PG_GETARG_OID(0);
+ Relation indrel;
+ indrel = index_open(indrelid, ShareLock);
+
+ gist_index_checkable(indrel);
+ gist_check_keys_consistency(indrel);
+
+ index_close(indrel, ShareLock);
+
+ PG_RETURN_VOID();
+}
diff --git a/doc/src/sgml/amcheck.sgml b/doc/src/sgml/amcheck.sgml
index 66a0232e24..621aeb881d 100644
--- a/doc/src/sgml/amcheck.sgml
+++ b/doc/src/sgml/amcheck.sgml
@@ -163,6 +163,25 @@ ORDER BY c.relpages DESC LIMIT 10;
</para>
</listitem>
</varlistentry>
+
+ <varlistentry>
+ <term>
+ <function>gist_index_check(index regclass) returns void</function>
+ <indexterm>
+ <primary>gist_index_check</primary>
+ </indexterm>
+ </term>
+
+ <listitem>
+ <para>
+ <function>gist_index_check</function> tests that its target GiST
+ has consistent parent-child tuples relations (no parent tuples
+ require tuple adjustement) and page graph respects balanced-tree
+ invariants (internal pages reference only leaf page or only internal
+ pages).
+ </para>
+ </listitem>
+ </varlistentry>
</variablelist>
</sect2>
--
2.17.1 (Apple Git-112)
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: amcheck verification for GiST
@ 2018-09-24 03:29 Thomas Munro <[email protected]>
parent: Andrey Borodin <[email protected]>
0 siblings, 2 replies; 12+ messages in thread
From: Thomas Munro @ 2018-09-24 03:29 UTC (permalink / raw)
To: Andrey Borodin <[email protected]>; +Cc: pgsql-hackers
On Sun, Sep 23, 2018 at 10:15 PM Andrey Borodin <[email protected]> wrote:
> Here's the patch with amcheck functionality for GiST.
Hi Andrey,
Windows doesn't like it[1]:
contrib/amcheck/verify_gist.c(163): error C2121: '#' : invalid
character : possibly the result of a macro expansion
[C:\projects\postgresql\amcheck.vcxproj]
That's:
+ MemoryContext mctx = AllocSetContextCreate(CurrentMemoryContext,
+ "amcheck context",
+#if PG_VERSION_NUM >= 110000
+ ALLOCSET_DEFAULT_SIZES);
+#else
+ ALLOCSET_DEFAULT_MINSIZE,
+ ALLOCSET_DEFAULT_INITSIZE,
+ ALLOCSET_DEFAULT_MAXSIZE);
+#endif
Not sure what's gong on there... perhaps it doesn't like you to do
that in the middle of a function-like-macro invocation
(AllocSetContextCreate)?
[1] https://ci.appveyor.com/project/postgresql-cfbot/postgresql/build/1.0.14056
--
Thomas Munro
http://www.enterprisedb.com
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: amcheck verification for GiST
@ 2018-09-24 03:34 Andres Freund <[email protected]>
parent: Thomas Munro <[email protected]>
1 sibling, 0 replies; 12+ messages in thread
From: Andres Freund @ 2018-09-24 03:34 UTC (permalink / raw)
To: Thomas Munro <[email protected]>; +Cc: Andrey Borodin <[email protected]>; pgsql-hackers
On 2018-09-24 15:29:38 +1200, Thomas Munro wrote:
> On Sun, Sep 23, 2018 at 10:15 PM Andrey Borodin <[email protected]> wrote:
> > Here's the patch with amcheck functionality for GiST.
>
> Hi Andrey,
>
> Windows doesn't like it[1]:
>
> contrib/amcheck/verify_gist.c(163): error C2121: '#' : invalid
> character : possibly the result of a macro expansion
> [C:\projects\postgresql\amcheck.vcxproj]
>
> That's:
>
> + MemoryContext mctx = AllocSetContextCreate(CurrentMemoryContext,
> + "amcheck context",
> +#if PG_VERSION_NUM >= 110000
> + ALLOCSET_DEFAULT_SIZES);
> +#else
> + ALLOCSET_DEFAULT_MINSIZE,
> + ALLOCSET_DEFAULT_INITSIZE,
> + ALLOCSET_DEFAULT_MAXSIZE);
> +#endif
>
> Not sure what's gong on there... perhaps it doesn't like you to do
> that in the middle of a function-like-macro invocation
> (AllocSetContextCreate)?
But note that the version dependent code shouldn't be present in
/contrib anyway.
Greetings,
Andres Freund
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: amcheck verification for GiST
@ 2018-09-24 05:12 Andrey Borodin <[email protected]>
parent: Thomas Munro <[email protected]>
1 sibling, 0 replies; 12+ messages in thread
From: Andrey Borodin @ 2018-09-24 05:12 UTC (permalink / raw)
To: Thomas Munro <[email protected]>; +Cc: pgsql-hackers
Hi!
> 24 сент. 2018 г., в 8:29, Thomas Munro <[email protected]> написал(а):
>
> On Sun, Sep 23, 2018 at 10:15 PM Andrey Borodin <[email protected]> wrote:
>> Here's the patch with amcheck functionality for GiST.
>
> Hi Andrey,
>
> Windows doesn't like it[1]:
Thanks, Thomas! Yes, I've missed that version-dependent macro. Surely, it's redundant.
Best regards, Andrey Borodin.
Attachments:
[application/octet-stream] 0001-GiST-verification-function-for-amcheck-v2.patch (12.4K, ../../[email protected]/2-0001-GiST-verification-function-for-amcheck-v2.patch)
download | inline diff:
From 62c425583deed26e72540a820310258d17961515 Mon Sep 17 00:00:00 2001
From: Andrey Borodin <[email protected]>
Date: Sun, 23 Sep 2018 14:59:54 +0500
Subject: [PATCH] GiST verification function for amcheck v2
Function gist_index_check() verifies that in target GiST every internal tuple need no extension by underlying subtree tuples and page graph respects balanced-tree invariants.
---
contrib/amcheck/Makefile | 6 +-
contrib/amcheck/amcheck--1.1--1.2.sql | 14 ++
contrib/amcheck/amcheck.control | 2 +-
contrib/amcheck/expected/check_gist.out | 9 +
contrib/amcheck/sql/check_gist.sql | 4 +
contrib/amcheck/verify_gist.c | 266 ++++++++++++++++++++++++
doc/src/sgml/amcheck.sgml | 19 ++
7 files changed, 316 insertions(+), 4 deletions(-)
create mode 100644 contrib/amcheck/amcheck--1.1--1.2.sql
create mode 100644 contrib/amcheck/expected/check_gist.out
create mode 100644 contrib/amcheck/sql/check_gist.sql
create mode 100644 contrib/amcheck/verify_gist.c
diff --git a/contrib/amcheck/Makefile b/contrib/amcheck/Makefile
index c5764b544f..dd9b5ecf92 100644
--- a/contrib/amcheck/Makefile
+++ b/contrib/amcheck/Makefile
@@ -1,13 +1,13 @@
# contrib/amcheck/Makefile
MODULE_big = amcheck
-OBJS = verify_nbtree.o $(WIN32RES)
+OBJS = verify_nbtree.o verify_gist.o $(WIN32RES)
EXTENSION = amcheck
-DATA = amcheck--1.0--1.1.sql amcheck--1.0.sql
+DATA = amcheck--1.1--1.2.sql amcheck--1.0--1.1.sql amcheck--1.0.sql
PGFILEDESC = "amcheck - function for verifying relation integrity"
-REGRESS = check check_btree
+REGRESS = check check_btree check_gist
ifdef USE_PGXS
PG_CONFIG = pg_config
diff --git a/contrib/amcheck/amcheck--1.1--1.2.sql b/contrib/amcheck/amcheck--1.1--1.2.sql
new file mode 100644
index 0000000000..6888900303
--- /dev/null
+++ b/contrib/amcheck/amcheck--1.1--1.2.sql
@@ -0,0 +1,14 @@
+/* amcheck--1.1--1.2.sql */
+
+-- complain if script is sourced in psql, rather than via CREATE EXTENSION
+\echo Use "ALTER EXTENSION amcheck UPDATE TO '1.2'" to load this file. \quit
+
+--
+-- gist_index_check()
+--
+CREATE FUNCTION gist_index_check(index regclass)
+RETURNS VOID
+AS 'MODULE_PATHNAME', 'gist_index_check'
+LANGUAGE C STRICT;
+
+REVOKE ALL ON FUNCTION gist_index_check(regclass) FROM PUBLIC;
diff --git a/contrib/amcheck/amcheck.control b/contrib/amcheck/amcheck.control
index 469048403d..c6e310046d 100644
--- a/contrib/amcheck/amcheck.control
+++ b/contrib/amcheck/amcheck.control
@@ -1,5 +1,5 @@
# amcheck extension
comment = 'functions for verifying relation integrity'
-default_version = '1.1'
+default_version = '1.2'
module_pathname = '$libdir/amcheck'
relocatable = true
diff --git a/contrib/amcheck/expected/check_gist.out b/contrib/amcheck/expected/check_gist.out
new file mode 100644
index 0000000000..d8ad66805b
--- /dev/null
+++ b/contrib/amcheck/expected/check_gist.out
@@ -0,0 +1,9 @@
+-- minimal test, basically just verifying that amcheck works with GiST
+CREATE TABLE gist_check AS SELECT point(s,1) c FROM generate_series(1,10000) s;
+CREATE INDEX gist_check_idx ON gist_check USING gist(c);
+SELECT gist_index_check('gist_check_idx');
+ gist_index_check
+------------------
+
+(1 row)
+
diff --git a/contrib/amcheck/sql/check_gist.sql b/contrib/amcheck/sql/check_gist.sql
new file mode 100644
index 0000000000..585c455ca5
--- /dev/null
+++ b/contrib/amcheck/sql/check_gist.sql
@@ -0,0 +1,4 @@
+-- minimal test, basically just verifying that amcheck works with GiST
+CREATE TABLE gist_check AS SELECT point(s,1) c FROM generate_series(1,10000) s;
+CREATE INDEX gist_check_idx ON gist_check USING gist(c);
+SELECT gist_index_check('gist_check_idx');
diff --git a/contrib/amcheck/verify_gist.c b/contrib/amcheck/verify_gist.c
new file mode 100644
index 0000000000..8fcf7b9c0b
--- /dev/null
+++ b/contrib/amcheck/verify_gist.c
@@ -0,0 +1,266 @@
+/*-------------------------------------------------------------------------
+ *
+ * verify_nbtree.c
+ * Verifies the integrity of GiST indexes based on invariants.
+ *
+ * Verification checks that all paths in GiST graph are contatining
+ * consisnent keys: tuples on parent pages consistently include tuples
+ * from children pages. Also, verification checks graph invariants:
+ * internal page must have at least one downlinks, internal page can
+ * reference either only leaf pages or only internal pages.
+ *
+ *
+ * Copyright (c) 2017-2018, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ * contrib/amcheck/verify_gist.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "access/gist_private.h"
+#include "access/htup_details.h"
+#include "access/transam.h"
+#include "catalog/index.h"
+#include "catalog/pg_am.h"
+#include "commands/tablecmds.h"
+#include "miscadmin.h"
+#include "storage/lmgr.h"
+#include "utils/memutils.h"
+#include "utils/snapmgr.h"
+
+typedef struct GistScanItem
+{
+ GistNSN parentlsn;
+ BlockNumber blkno;
+ struct GistScanItem *next;
+} GistScanItem;
+
+/*
+ * For every tuple on page check if it is contained by tuple on parent page
+ */
+static inline void
+gist_check_page_keys(Relation rel, Page parentpage, Page page, IndexTuple parent, GISTSTATE *state)
+{
+ OffsetNumber i,
+ maxoff = PageGetMaxOffsetNumber(page);
+
+ for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
+ {
+ ItemId iid = PageGetItemId(page, i);
+ IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
+
+ if (GistTupleIsInvalid(idxtuple))
+ ereport(LOG,
+ (errmsg("index \"%s\" contains an inner tuple marked as invalid",
+ RelationGetRelationName(rel)),
+ errdetail("This is caused by an incomplete page split at crash recovery before upgrading to PostgreSQL 9.1."),
+ errhint("Please REINDEX it.")));
+
+ /*
+ * Tree is inconsistent if adjustement is necessary for any parent tuple
+ */
+ if (gistgetadjusted(rel, parent, idxtuple, state))
+ ereport(ERROR,
+ (errcode(ERRCODE_INDEX_CORRUPTED),
+ errmsg("index \"%s\" has inconsistent records",
+ RelationGetRelationName(rel))));
+ }
+}
+
+/* Check of an internal page. Hold locks on two pages at a time (parent+child). */
+static inline bool
+gist_check_internal_page(Relation rel, Page page, BufferAccessStrategy strategy, GISTSTATE *state)
+{
+ bool has_leafs = false;
+ bool has_internals = false;
+ OffsetNumber i,
+ maxoff = PageGetMaxOffsetNumber(page);
+
+ for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
+ {
+ ItemId iid = PageGetItemId(page, i);
+ IndexTuple idxtuple = (IndexTuple) PageGetItem(page, iid);
+
+ BlockNumber child_blkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
+ Buffer buffer;
+ Page child_page;
+
+ if (GistTupleIsInvalid(idxtuple))
+ ereport(LOG,
+ (errmsg("index \"%s\" contains an inner tuple marked as invalid",
+ RelationGetRelationName(rel)),
+ errdetail("This is caused by an incomplete page split at crash recovery before upgrading to PostgreSQL 9.1."),
+ errhint("Please REINDEX it.")));
+
+ buffer = ReadBufferExtended(rel, MAIN_FORKNUM, child_blkno,
+ RBM_NORMAL, strategy);
+
+ LockBuffer(buffer, GIST_SHARE);
+ gistcheckpage(rel, buffer);
+ child_page = (Page) BufferGetPage(buffer);
+
+ has_leafs = has_leafs || GistPageIsLeaf(child_page);
+ has_internals = has_internals || !GistPageIsLeaf(child_page);
+ gist_check_page_keys(rel, page, child_page, idxtuple, state);
+
+ UnlockReleaseBuffer(buffer);
+ }
+
+ if (!(has_leafs || has_internals))
+ ereport(ERROR,
+ (errcode(ERRCODE_INDEX_CORRUPTED),
+ errmsg("index \"%s\" internal page has no downlink references",
+ RelationGetRelationName(rel))));
+
+
+ if (has_leafs == has_internals)
+ ereport(ERROR,
+ (errcode(ERRCODE_INDEX_CORRUPTED),
+ errmsg("index \"%s\" page references both internal and leaf pages",
+ RelationGetRelationName(rel))));
+
+ return has_internals;
+}
+
+/* add pages with unfinished split to scan */
+static void
+pushStackIfSplited(Page page, GistScanItem *stack)
+{
+ GISTPageOpaque opaque = GistPageGetOpaque(page);
+
+ if (stack->blkno != GIST_ROOT_BLKNO && !XLogRecPtrIsInvalid(stack->parentlsn) &&
+ (GistFollowRight(page) || stack->parentlsn < GistPageGetNSN(page)) &&
+ opaque->rightlink != InvalidBlockNumber /* sanity check */ )
+ {
+ /* split page detected, install right link to the stack */
+
+ GistScanItem *ptr = (GistScanItem *) palloc(sizeof(GistScanItem));
+
+ ptr->blkno = opaque->rightlink;
+ ptr->parentlsn = stack->parentlsn;
+ ptr->next = stack->next;
+ stack->next = ptr;
+ }
+}
+
+/*
+ * Main entry point for GiST check. Allocates memory context and scans
+ * through GiST graph.
+ */
+static inline void
+gist_check_keys_consistency(Relation rel)
+{
+ GistScanItem *stack,
+ *ptr;
+
+ BufferAccessStrategy strategy = GetAccessStrategy(BAS_BULKREAD);
+
+ MemoryContext mctx = AllocSetContextCreate(CurrentMemoryContext,
+ "amcheck context",
+ ALLOCSET_DEFAULT_SIZES);
+
+ MemoryContext oldcontext = MemoryContextSwitchTo(mctx);
+ GISTSTATE *state = initGISTstate(rel);
+
+ stack = (GistScanItem *) palloc0(sizeof(GistScanItem));
+ stack->blkno = GIST_ROOT_BLKNO;
+
+ while (stack)
+ {
+ Buffer buffer;
+ Page page;
+ OffsetNumber i,
+ maxoff;
+ IndexTuple idxtuple;
+ ItemId iid;
+
+ buffer = ReadBufferExtended(rel, MAIN_FORKNUM, stack->blkno,
+ RBM_NORMAL, strategy);
+ LockBuffer(buffer, GIST_SHARE);
+ gistcheckpage(rel, buffer);
+ page = (Page) BufferGetPage(buffer);
+
+ if (GistPageIsLeaf(page))
+ {
+ /* should never happen unless it is root */
+ Assert(stack->blkno == GIST_ROOT_BLKNO);
+ }
+ else
+ {
+ /* check for split proceeded after look at parent */
+ pushStackIfSplited(page, stack);
+
+ maxoff = PageGetMaxOffsetNumber(page);
+
+ if (gist_check_internal_page(rel, page, strategy, state))
+ {
+ for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
+ {
+ iid = PageGetItemId(page, i);
+ idxtuple = (IndexTuple) PageGetItem(page, iid);
+
+ ptr = (GistScanItem *) palloc(sizeof(GistScanItem));
+ ptr->blkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid));
+ ptr->parentlsn = BufferGetLSNAtomic(buffer);
+ ptr->next = stack->next;
+ stack->next = ptr;
+ }
+ }
+ }
+
+ UnlockReleaseBuffer(buffer);
+
+ ptr = stack->next;
+ pfree(stack);
+ stack = ptr;
+ }
+
+ MemoryContextSwitchTo(oldcontext);
+ MemoryContextDelete(mctx);
+}
+
+/* Check that relation is eligible for GiST verification */
+static inline void
+gist_index_checkable(Relation rel)
+{
+ if (rel->rd_rel->relkind != RELKIND_INDEX ||
+ rel->rd_rel->relam != GIST_AM_OID)
+ ereport(ERROR,
+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ errmsg("only GiST indexes are supported as targets for this verification"),
+ errdetail("Relation \"%s\" is not a GiST index.",
+ RelationGetRelationName(rel))));
+
+ if (RELATION_IS_OTHER_TEMP(rel))
+ ereport(ERROR,
+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ errmsg("cannot access temporary tables of other sessions"),
+ errdetail("Index \"%s\" is associated with temporary relation.",
+ RelationGetRelationName(rel))));
+
+ if (!IndexIsValid(rel->rd_index))
+ ereport(ERROR,
+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ errmsg("cannot check index \"%s\"",
+ RelationGetRelationName(rel)),
+ errdetail("Index is not valid")));
+}
+
+PG_FUNCTION_INFO_V1(gist_index_check);
+
+Datum
+gist_index_check(PG_FUNCTION_ARGS)
+{
+ Oid indrelid = PG_GETARG_OID(0);
+ Relation indrel;
+ indrel = index_open(indrelid, ShareLock);
+
+ gist_index_checkable(indrel);
+ gist_check_keys_consistency(indrel);
+
+ index_close(indrel, ShareLock);
+
+ PG_RETURN_VOID();
+}
diff --git a/doc/src/sgml/amcheck.sgml b/doc/src/sgml/amcheck.sgml
index 66a0232e24..621aeb881d 100644
--- a/doc/src/sgml/amcheck.sgml
+++ b/doc/src/sgml/amcheck.sgml
@@ -163,6 +163,25 @@ ORDER BY c.relpages DESC LIMIT 10;
</para>
</listitem>
</varlistentry>
+
+ <varlistentry>
+ <term>
+ <function>gist_index_check(index regclass) returns void</function>
+ <indexterm>
+ <primary>gist_index_check</primary>
+ </indexterm>
+ </term>
+
+ <listitem>
+ <para>
+ <function>gist_index_check</function> tests that its target GiST
+ has consistent parent-child tuples relations (no parent tuples
+ require tuple adjustement) and page graph respects balanced-tree
+ invariants (internal pages reference only leaf page or only internal
+ pages).
+ </para>
+ </listitem>
+ </varlistentry>
</variablelist>
</sect2>
--
2.17.1 (Apple Git-112)
^ permalink raw reply [nested|flat] 12+ messages in thread
* [PATCH 01/10] Define macros to make XLogReadRecord a state machine
@ 2019-04-18 01:22 Kyotaro Horiguchi <[email protected]>
0 siblings, 0 replies; 12+ messages in thread
From: Kyotaro Horiguchi @ 2019-04-18 01:22 UTC (permalink / raw)
To minimize apparent imapct on code, use some macros as syntax sugar. This is a similar stuff with ExecInterpExpr but a bit different. The most significant difference is that this stuff allows some functions are leaved midst of their work then continue. Roughly speaking this is used as the follows.
enum retval
some_func()
{
static .. internal_variables;
XLR_SWITCH();
...
XLR_LEAVE(STATUS1, RETVAL_CONTINUE);
...
XLR_LEAVE(STATUS2, RETVAL_CONTINUE2);
...
XLR_SWITCH_END();
XLR_RETURN(RETVAL_FINISH);
}
The caller uses the function as follows:
while (some_func() != RETVAL_FINISH)
{
<do some work>;
}
---
src/backend/access/transam/xlogreader.c | 63 +++++++++++++++++++++++++++++++++
src/include/access/xlogreader.h | 3 ++
2 files changed, 66 insertions(+)
diff --git a/src/backend/access/transam/xlogreader.c b/src/backend/access/transam/xlogreader.c
index 9196aa3aae..5299765040 100644
--- a/src/backend/access/transam/xlogreader.c
+++ b/src/backend/access/transam/xlogreader.c
@@ -29,6 +29,69 @@
#include "utils/memutils.h"
#endif
+/*
+ * Use computed-goto-based opcode dispatch when computed gotos are available.
+ * But use a separate symbol so that it's easy to adjust locally in this file
+ * for development and testing.
+ */
+#ifdef HAVE_COMPUTED_GOTO
+#define XLR_USE_COMPUTED_GOTO
+#endif /* HAVE_COMPUTED_GOTO */
+
+/*
+ * Macros for opcode dispatch.
+ *
+ * XLR_SWITCH - just hides the switch if not in use.
+ * XLR_CASE - labels the implementation of named expression step type.
+ * XLR_DISPATCH - jump to the implementation of the step type for 'op'.
+ * XLR_LEAVE - leave the function and return here at the next call.
+ * XLR_RETURN - return from the function and set state to initial state.
+ * XLR_END - just hides the closing brace if not in use.
+ */
+#if defined(XLR_USE_COMPUTED_GOTO)
+#define XLR_SWITCH() \
+ /* Don't call duplicatedly */ \
+ static int callcnt = 0 PG_USED_FOR_ASSERTS_ONLY; \
+ do { \
+ if ((XLR_STATE).j) \
+ goto *((void *) (XLR_STATE).j); \
+ XLR_CASE(XLR_INIT_STATE); \
+ Assert(++callcnt == 1); \
+ } while (0)
+#define XLR_CASE(name) name:
+#define XLR_DISPATCH() goto *((void *) (XLR_STATE).j)
+#define XLR_LEAVE(name, code) do { \
+ (XLR_STATE).j = (&&name); return (code); \
+ XLR_CASE(name); \
+ } while (0)
+#define XLR_RETURN(code) \
+ do { \
+ Assert(--callcnt == 0); \
+ (XLR_STATE).j = (&&XLR_INIT_STATE); return (code); \
+ } while (0)
+#define XLR_SWITCH_END()
+#else /* !XLR_USE_COMPUTED_GOTO */
+#define XLR_SWITCH() \
+ /* Don't call duplicatedly */ \
+ static int callcnt = 0 PG_USED_FOR_ASSERTS_ONLY; \
+ switch ((XLR_STATE).c) { \
+ XLR_CASE(XLR_INIT_STATE); \
+ Assert(++callcnt == 1); \
+#define XLR_CASE(name) case name:
+#define XLR_DISPATCH() goto starteval
+#define XLR_LEAVE(name, code) \
+ do { \
+ (XLR_STATE).c = (name); return (code); \
+ XLR_CASE(name); \
+ } while (0)
+#define XLR_RETURN(code) \
+ do { \
+ Assert(--callcnt == 0); \
+ (XLR_STATE).c = (XLR_INIT_STATE); return (code); \
+ } while (0)
+#define XLR_SWITCH_END() }
+#endif /* XLR_USE_COMPUTED_GOTO */
+
static bool allocate_recordbuf(XLogReaderState *state, uint32 reclength);
static bool ValidXLogRecordHeader(XLogReaderState *state, XLogRecPtr RecPtr,
diff --git a/src/include/access/xlogreader.h b/src/include/access/xlogreader.h
index f3bae0bf49..30500c35c7 100644
--- a/src/include/access/xlogreader.h
+++ b/src/include/access/xlogreader.h
@@ -240,6 +240,9 @@ extern bool DecodeXLogRecord(XLogReaderState *state, XLogRecord *record,
#define XLogRecBlockImageApply(decoder, block_id) \
((decoder)->blocks[block_id].apply_image)
+/* Reset the reader state */
+#define XLREAD_RESET(state) ((state)->xlnd_state.j = (state)->xlread_state.j = 0)
+
extern bool RestoreBlockImage(XLogReaderState *recoder, uint8 block_id, char *dst);
extern char *XLogRecGetBlockData(XLogReaderState *record, uint8 block_id, Size *len);
extern bool XLogRecGetBlockTag(XLogReaderState *record, uint8 block_id,
--
2.16.3
----Next_Part(Thu_Apr_18_21_02_57_2019_406)--
Content-Type: Text/X-Patch; charset=us-ascii
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="0002-Make-ReadPageInternal-a-state-machine.patch"
^ permalink raw reply [nested|flat] 12+ messages in thread
* [PATCH 01/10] Define macros to make XLogReadRecord a state machine
@ 2019-04-18 01:22 Kyotaro Horiguchi <[email protected]>
0 siblings, 0 replies; 12+ messages in thread
From: Kyotaro Horiguchi @ 2019-04-18 01:22 UTC (permalink / raw)
To minimize apparent impact on code, use some macros as syntax
sugar. This is a similar stuff with ExecInterpExpr but a bit
different. The most significant difference is that this stuff allows
some functions are leaved midst of their work then continue. Roughly
speaking this is used as the follows.
enum retval
some_func()
{
static .. internal_variables;
XLR_SWITCH(INITIAL_STATUS);
...
XLR_LEAVE(STATUS1, RETVAL_CONTINUE);
...
XLR_LEAVE(STATUS2, RETVAL_CONTINUE2);
...
XLR_SWITCH_END();
XLR_RETURN(RETVAL_FINISH);
}
The caller uses the function as follows:
while (some_func() != RETVAL_FINISH)
{
<do some work>;
}
---
src/backend/access/transam/xlogreader.c | 83 +++++++++++++++++++++++++++++++++
1 file changed, 83 insertions(+)
diff --git a/src/backend/access/transam/xlogreader.c b/src/backend/access/transam/xlogreader.c
index 41dae916b4..69d20e1f2f 100644
--- a/src/backend/access/transam/xlogreader.c
+++ b/src/backend/access/transam/xlogreader.c
@@ -29,6 +29,89 @@
#include "utils/memutils.h"
#endif
+/*
+ * Use computed-goto-based state dispatch when computed gotos are available.
+ * But use a separate symbol so that it's easy to adjust locally in this file
+ * for development and testing.
+ */
+#ifdef HAVE_COMPUTED_GOTO
+#define XLR_USE_COMPUTED_GOTO
+#endif /* HAVE_COMPUTED_GOTO */
+
+/*
+ * The state machine functions relies on static local variables. They cannot
+ * be reentered after non-local exit using ereport/elog for consistency. The
+ * assertion macros protect the functions from reenter after non-local exit.
+ */
+#ifdef USE_ASSERT_CHECKING
+#define XLR_REENT_PROTECT_ENTER() \
+ do { Assert(!__xlr_running); __xlr_running = true; } while (0)
+#define XLR_REENT_PROTECT_LEAVE()\
+ do { __xlr_running = false; } while (0)
+#else
+#define XLR_REENT_PROTECT_ENTER()
+#define XLR_REENT_PROTECT_LEAVE()
+#endif
+
+/*
+ * Macros for state dispatch.
+ *
+ * XLR_SWITCH - prologue code for state machine including switch itself.
+ * XLR_CASE - labels the implementation of named state.
+ * XLR_LEAVE - leave the function and return here at the next call.
+ * XLR_RETURN - return from the function and set state to initial state.
+ * XLR_END - just hides the closing brace if not in use.
+ */
+#if defined(XLR_USE_COMPUTED_GOTO)
+#define XLR_SWITCH(name) \
+ static bool __xlr_running PG_USED_FOR_ASSERTS_ONLY = false; \
+ static void *__xlr_init_state = &&name; \
+ static void *__xlr_state = &&name; \
+ do { \
+ XLR_REENT_PROTECT_ENTER(); \
+ goto *__xlr_state; \
+ XLR_CASE(name); \
+ } while (0)
+#define XLR_CASE(name) name:
+#define XLR_LEAVE(name, code) \
+ do { \
+ __xlr_state = (&&name); \
+ XLR_REENT_PROTECT_LEAVE(); \
+ return (code); \
+ XLR_CASE(name); \
+ } while (0)
+#define XLR_RETURN(code) \
+ do { \
+ __xlr_state = __xlr_init_state; \
+ XLR_REENT_PROTECT_LEAVE(); \
+ return (code); \
+ } while (0)
+#define XLR_SWITCH_END()
+#else /* !XLR_USE_COMPUTED_GOTO */
+#define XLR_SWITCH(name) \
+ static bool __xlr_running = false PG_USED_FOR_ASSERTS_ONLY; \
+ static int __xlr_init_state = name; \
+ static int __xlr_state = name; \
+ XLR_REENT_PROTECT_ENTER(); \
+ switch (__xlr_state) { \
+ XLR_CASE(name)
+#define XLR_CASE(name) case name:
+#define XLR_LEAVE(name, code) \
+ do { \
+ __xlr_state = (name); \
+ XLR_REENT_PROTECT_LEAVE(); \
+ return (code); \
+ XLR_CASE(name); \
+ } while (0)
+#define XLR_RETURN(code) \
+ do { \
+ __xlr_state = __xlr_init_state; \
+ XLR_REENT_PROTECT_LEAVE(); \
+ return (code); \
+ } while (0)
+#define XLR_SWITCH_END() }
+#endif /* XLR_USE_COMPUTED_GOTO */
+
static bool allocate_recordbuf(XLogReaderState *state, uint32 reclength);
static bool ValidXLogRecordHeader(XLogReaderState *state, XLogRecPtr RecPtr,
--
2.16.3
----Next_Part(Wed_Jul_10_13_18_10_2019_842)--
Content-Type: Text/X-Patch; charset=us-ascii
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="v4-0002-Make-ReadPageInternal-a-state-machine.patch"
^ permalink raw reply [nested|flat] 12+ messages in thread
* [PATCH 01/10] Define macros to make XLogReadRecord a state machine
@ 2019-04-18 01:22 Kyotaro Horiguchi <[email protected]>
0 siblings, 0 replies; 12+ messages in thread
From: Kyotaro Horiguchi @ 2019-04-18 01:22 UTC (permalink / raw)
To minimize apparent imapct on code, use some macros as syntax sugar. This is a similar stuff with ExecInterpExpr but a bit different. The most significant difference is that this stuff allows some functions are leaved midst of their work then continue. Roughly speaking this is used as the follows.
enum retval
some_func()
{
static .. internal_variables;
XLR_SWITCH();
...
XLR_LEAVE(STATUS1, RETVAL_CONTINUE);
...
XLR_LEAVE(STATUS2, RETVAL_CONTINUE2);
...
XLR_SWITCH_END();
XLR_RETURN(RETVAL_FINISH);
}
The caller uses the function as follows:
while (some_func() != RETVAL_FINISH)
{
<do some work>;
}
---
src/backend/access/transam/xlogreader.c | 53 +++++++++++++++++++++++++++++++++
src/include/access/xlogreader.h | 3 ++
2 files changed, 56 insertions(+)
diff --git a/src/backend/access/transam/xlogreader.c b/src/backend/access/transam/xlogreader.c
index 9196aa3aae..0e49ea6ab7 100644
--- a/src/backend/access/transam/xlogreader.c
+++ b/src/backend/access/transam/xlogreader.c
@@ -29,6 +29,59 @@
#include "utils/memutils.h"
#endif
+/*
+ * Use computed-goto-based state dispatch when computed gotos are available.
+ * But use a separate symbol so that it's easy to adjust locally in this file
+ * for development and testing.
+ */
+#ifdef HAVE_COMPUTED_GOTO
+#define XLR_USE_COMPUTED_GOTO
+#endif /* HAVE_COMPUTED_GOTO */
+
+/*
+ * Macros for state dispatch.
+ *
+ * XLR_SWITCH - just hides the switch if not in use.
+ * XLR_CASE - labels the implementation of named state.
+ * XLR_LEAVE - leave the function and return here at the next call.
+ * XLR_RETURN - return from the function and set state to initial state.
+ * XLR_END - just hides the closing brace if not in use.
+ */
+#if defined(XLR_USE_COMPUTED_GOTO)
+#define XLR_SWITCH() \
+ do { \
+ if ((XLR_STATE).j) \
+ goto *((void *) (XLR_STATE).j); \
+ XLR_CASE(XLR_INIT_STATE); \
+ } while (0)
+#define XLR_CASE(name) name:
+#define XLR_LEAVE(name, code) do { \
+ (XLR_STATE).j = (&&name); return (code); \
+ XLR_CASE(name); \
+ } while (0)
+#define XLR_RETURN(code) \
+ do { \
+ (XLR_STATE).j = (&&XLR_INIT_STATE); return (code); \
+ } while (0)
+#define XLR_SWITCH_END()
+#else /* !XLR_USE_COMPUTED_GOTO */
+#define XLR_SWITCH() \
+ /* Don't call duplicatedly */ \
+ switch ((XLR_STATE).c) { \
+ XLR_CASE(XLR_INIT_STATE); \
+#define XLR_CASE(name) case name:
+#define XLR_LEAVE(name, code) \
+ do { \
+ (XLR_STATE).c = (name); return (code); \
+ XLR_CASE(name); \
+ } while (0)
+#define XLR_RETURN(code) \
+ do { \
+ (XLR_STATE).c = (XLR_INIT_STATE); return (code); \
+ } while (0)
+#define XLR_SWITCH_END() }
+#endif /* XLR_USE_COMPUTED_GOTO */
+
static bool allocate_recordbuf(XLogReaderState *state, uint32 reclength);
static bool ValidXLogRecordHeader(XLogReaderState *state, XLogRecPtr RecPtr,
diff --git a/src/include/access/xlogreader.h b/src/include/access/xlogreader.h
index f3bae0bf49..30500c35c7 100644
--- a/src/include/access/xlogreader.h
+++ b/src/include/access/xlogreader.h
@@ -240,6 +240,9 @@ extern bool DecodeXLogRecord(XLogReaderState *state, XLogRecord *record,
#define XLogRecBlockImageApply(decoder, block_id) \
((decoder)->blocks[block_id].apply_image)
+/* Reset the reader state */
+#define XLREAD_RESET(state) ((state)->xlnd_state.j = (state)->xlread_state.j = 0)
+
extern bool RestoreBlockImage(XLogReaderState *recoder, uint8 block_id, char *dst);
extern char *XLogRecGetBlockData(XLogReaderState *record, uint8 block_id, Size *len);
extern bool XLogRecGetBlockTag(XLogReaderState *record, uint8 block_id,
--
2.16.3
----Next_Part(Fri_Apr_26_17_40_34_2019_888)--
Content-Type: Text/X-Patch; charset=us-ascii
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="v2-0002-Make-ReadPageInternal-a-state-machine.patch"
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: Maybe we should reduce SKIP_PAGES_THRESHOLD a bit?
@ 2024-12-17 17:06 Melanie Plageman <[email protected]>
0 siblings, 2 replies; 12+ messages in thread
From: Melanie Plageman @ 2024-12-17 17:06 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; +Cc: Peter Geoghegan <[email protected]>; pgsql-hackers
On Tue, Dec 17, 2024 at 9:11 AM Tomas Vondra <[email protected]> wrote:
>
>
>
> On 12/16/24 19:49, Melanie Plageman wrote:
>
> > No, I'm talking about the behavior of causing small pockets of
> > all-frozen pages which end up being smaller than SKIP_PAGES_THRESHOLD
> > and are then scanned (even though they are already frozen). What I
> > describe in that email I cited is that because we freeze
> > opportunistically when we have or will emit an FPI, and bgwriter will
> > write out blocks in clocksweep order, we end up with random pockets of
> > pages getting frozen during/after a checkpoint. Then in the next
> > vacuum, we end up scanning those all-frozen pages again because the
> > ranges of frozen pages are smaller than SKIP_PAGES_THRESHOLD. This is
> > mostly going to happen for an insert-only workload. I'm not saying
> > freezing the pages is bad, I'm saying that causing these pockets of
> > frozen pages leads to scanning all-frozen pages on future vacuums.
> >
>
> Yeah, this interaction between the components is not great :-( But can
> we think of a way to reduce the fragmentation? What would need to change?
Well reducing SKIP_PAGES_THRESHOLD would help. And unfortunately we do
not know if the skippable pages are all-frozen without extra
visibilitymap_get_status() calls -- so we can't decide to avoid
scanning ranges of skippable pages because they are frozen.
> I don't think bgwriter can help much - it's mostly oblivious to the
> contents of the buffer, I don't think it could consider stuff like this
> when deciding what to evict.
Agreed.
> Maybe the freezing code could check how many of the nearby pages are
> frozen, and consider that together with the FPI write?
That's an interesting idea. We wouldn't have any guaranteed info
because we only have a lock on the page we are considering freezing.
But we could keep track of the length of a run of pages we are
freezing and opportunistically freeze pages that don't require
freezing if they follow one or more pages requiring freezing. But I
don't know how much more this buys us than removing
SKIP_PAGES_THRESHOLD. Since it would "fix" the fragmentation, perhaps
it makes larger future vacuum reads possible. But I wonder how much
benefit it would be vs complexity.
> >>> However, we are not close to coming up with a
> >>> replacement heuristic, so removing SKIP_PAGES_THRESHOLD would help.
> >>> This wouldn't have affected your results, but it is worth considering
> >>> more generally.
> >>
> >> One of the reasons why we have SKIP_PAGES_THRESHOLD is that it makes
> >> it more likely that non-aggressive VACUUMs will advance relfrozenxid.
> >> Granted, it's probably not doing a particularly good job at that right
> >> now. But any effort to replace it should account for that.
> >>
>
> I don't follow. How could non-aggressive VACUUM advance relfrozenxid,
> ever? I mean, if it doesn't guarantee freezing all pages, how could it?
It may, coincidentally, not skip any all-visible pages. Peter points
out that this happens all the time for small tables, but wouldn't the
overhead of an aggressive vacuum be barely noticeable for small
tables? It seems like there is little cost to waiting.
> >> This is possible by making VACUUM consider the cost of scanning extra
> >> heap pages up-front. If the number of "extra heap pages to be scanned"
> >> to advance relfrozenxid happens to not be very high (or not so high
> >> *relative to the current age(relfrozenxid)*), then pay that cost now,
> >> in the current VACUUM operation. Even if age(relfrozenxid) is pretty
> >> far from the threshold for aggressive mode, if the added cost of
> >> advancing relfrozenxid is still not too high, why wouldn't we just do
> >> it?
> >
> > That's an interesting idea. And it seems like a much more effective
> > way of getting some relfrozenxid advancement than hoping that the
> > pages you scan due to SKIP_PAGES_THRESHOLD end up being enough to have
> > scanned all unfrozen tuples.
> >
>
> I agree it might be useful to formulate this as a "costing" problem, not
> just in the context of a single vacuum, but for the overall maintenance
> overhead - essentially accepting the vacuum gets slower, in exchange for
> lower cost of maintenance later.
Yes, that costing sounds like a big research and benchmarking project
on its own.
> But I think that (a) is going to be fairly complex, because how do you
> cost the future vacuum?, and (b) is somewhat misses my point that on
> modern NVMe SSD storage (SKIP_PAGES_THRESHOLD > 1) doesn't seem to be a
> win *ever*.
>
> So why shouldn't we reduce the SKIP_PAGES_THRESHOLD value (or perhaps
> make it configurable)? We can still do the other stuff (decide how
> aggressively to free stuff etc.) independently of that.
I think your tests show SKIP_PAGES_THRESHOLD has dubious if any
benefit related to readahead. But the question is if we care about it
for advancing relfrozenxid for small tables.
- Melanie
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: Maybe we should reduce SKIP_PAGES_THRESHOLD a bit?
@ 2024-12-17 17:52 Robert Haas <[email protected]>
parent: Melanie Plageman <[email protected]>
1 sibling, 1 reply; 12+ messages in thread
From: Robert Haas @ 2024-12-17 17:52 UTC (permalink / raw)
To: Melanie Plageman <[email protected]>; +Cc: Tomas Vondra <[email protected]>; Peter Geoghegan <[email protected]>; pgsql-hackers
On Tue, Dec 17, 2024 at 12:06 PM Melanie Plageman
<[email protected]> wrote:
> I think your tests show SKIP_PAGES_THRESHOLD has dubious if any
> benefit related to readahead. But the question is if we care about it
> for advancing relfrozenxid for small tables.
It seems like relfrozenxid advancement is really only a problem for
big tables. If the table is small, the eventual aggressive vacuum
doesn't cost that much.
--
Robert Haas
EDB: http://www.enterprisedb.com
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: Maybe we should reduce SKIP_PAGES_THRESHOLD a bit?
@ 2024-12-17 18:46 Tomas Vondra <[email protected]>
parent: Melanie Plageman <[email protected]>
1 sibling, 1 reply; 12+ messages in thread
From: Tomas Vondra @ 2024-12-17 18:46 UTC (permalink / raw)
To: Melanie Plageman <[email protected]>; +Cc: Peter Geoghegan <[email protected]>; pgsql-hackers
On 12/17/24 18:06, Melanie Plageman wrote:
> On Tue, Dec 17, 2024 at 9:11 AM Tomas Vondra <[email protected]> wrote:
>>
>>
>>
>> On 12/16/24 19:49, Melanie Plageman wrote:
>>
>>> No, I'm talking about the behavior of causing small pockets of
>>> all-frozen pages which end up being smaller than SKIP_PAGES_THRESHOLD
>>> and are then scanned (even though they are already frozen). What I
>>> describe in that email I cited is that because we freeze
>>> opportunistically when we have or will emit an FPI, and bgwriter will
>>> write out blocks in clocksweep order, we end up with random pockets of
>>> pages getting frozen during/after a checkpoint. Then in the next
>>> vacuum, we end up scanning those all-frozen pages again because the
>>> ranges of frozen pages are smaller than SKIP_PAGES_THRESHOLD. This is
>>> mostly going to happen for an insert-only workload. I'm not saying
>>> freezing the pages is bad, I'm saying that causing these pockets of
>>> frozen pages leads to scanning all-frozen pages on future vacuums.
>>>
>>
>> Yeah, this interaction between the components is not great :-( But can
>> we think of a way to reduce the fragmentation? What would need to change?
>
> Well reducing SKIP_PAGES_THRESHOLD would help.
How does SKIP_PAGES_THRESHOLD change the fragmentation? I think that's
the side that's affected by the fragmentation, but it's really due to
the eager freezing / bgwriter evictions, etc. If the threshold is set to
1 (i.e. to always skip), that just lowers the impact, but the relation
is still as fragmented as before, no?
> And unfortunately we do
> not know if the skippable pages are all-frozen without extra
> visibilitymap_get_status() calls -- so we can't decide to avoid
> scanning ranges of skippable pages because they are frozen.
>
I may be missing something, but doesn't find_next_unskippable_block()
already get those bits? In fact, it even checks VISIBILITYMAP_ALL_FROZEN
but only for aggressive vacuum. But even if that wasn't the case, isn't
checking the VM likely much cheaper than vacuuming the heap page?
Also, I don't quite see why would this information help with reducing
the fragmentation? Can you explain?
>> I don't think bgwriter can help much - it's mostly oblivious to the
>> contents of the buffer, I don't think it could consider stuff like this
>> when deciding what to evict.
>
> Agreed.
>
>> Maybe the freezing code could check how many of the nearby pages are
>> frozen, and consider that together with the FPI write?
>
> That's an interesting idea. We wouldn't have any guaranteed info
> because we only have a lock on the page we are considering freezing.
> But we could keep track of the length of a run of pages we are
> freezing and opportunistically freeze pages that don't require
> freezing if they follow one or more pages requiring freezing.
I don't think we need a "guaranteed" information - a heuristics that's
correct most of the time (say, >90%?) ought to be good enough. I mean,
it has to be, because we'll never get a rule that's correct 100%. So
even just looking at a batch of pages in VM should be enough, no?
> But I don't know how much more this buys us than removing
> SKIP_PAGES_THRESHOLD. Since it would "fix" the fragmentation, perhaps
> it makes larger future vacuum reads possible. But I wonder how much
> benefit it would be vs complexity.
>
I think that depends on which cost we're talking about. If we only talk
about the efficiency of a single vacuum, then it probably does not help
very much. I mean, if we assume the relation is already fragmented, then
it seems to be cheaper to vacuum just the pages that need it (as if with
SKIP_PAGES_THRESHOLD=1).
But if we're talking about long-time benefits, in reducing the amount of
freezing needed overall, maybe it'd be a win? I don't know.
>>>>> However, we are not close to coming up with a
>>>>> replacement heuristic, so removing SKIP_PAGES_THRESHOLD would help.
>>>>> This wouldn't have affected your results, but it is worth considering
>>>>> more generally.
>>>>
>>>> One of the reasons why we have SKIP_PAGES_THRESHOLD is that it makes
>>>> it more likely that non-aggressive VACUUMs will advance relfrozenxid.
>>>> Granted, it's probably not doing a particularly good job at that right
>>>> now. But any effort to replace it should account for that.
>>>>
>>
>> I don't follow. How could non-aggressive VACUUM advance relfrozenxid,
>> ever? I mean, if it doesn't guarantee freezing all pages, how could it?
>
> It may, coincidentally, not skip any all-visible pages. Peter points
> out that this happens all the time for small tables, but wouldn't the
> overhead of an aggressive vacuum be barely noticeable for small
> tables? It seems like there is little cost to waiting.
>
Yeah, that's kinda my point / confusion. For it to help we would have to
not skip any pages, but for large tables that seems quite unlikely
(because it only takes one table that gets skipped, and there are many
opportunities). And for small tables, I think it doesn't matter that
much, because even aggressive vacuum is cheap.
>>>> This is possible by making VACUUM consider the cost of scanning extra
>>>> heap pages up-front. If the number of "extra heap pages to be scanned"
>>>> to advance relfrozenxid happens to not be very high (or not so high
>>>> *relative to the current age(relfrozenxid)*), then pay that cost now,
>>>> in the current VACUUM operation. Even if age(relfrozenxid) is pretty
>>>> far from the threshold for aggressive mode, if the added cost of
>>>> advancing relfrozenxid is still not too high, why wouldn't we just do
>>>> it?
>>>
>>> That's an interesting idea. And it seems like a much more effective
>>> way of getting some relfrozenxid advancement than hoping that the
>>> pages you scan due to SKIP_PAGES_THRESHOLD end up being enough to have
>>> scanned all unfrozen tuples.
>>>
>>
>> I agree it might be useful to formulate this as a "costing" problem, not
>> just in the context of a single vacuum, but for the overall maintenance
>> overhead - essentially accepting the vacuum gets slower, in exchange for
>> lower cost of maintenance later.
>
> Yes, that costing sounds like a big research and benchmarking project
> on its own.
>
True. I don't know if it makes sense to try to construct a detailed /
accurate cost model for this. I meant more of a general model showing
the general relationship between the amount of work that has to happen
in different places.
regards
--
Tomas Vondra
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: Maybe we should reduce SKIP_PAGES_THRESHOLD a bit?
@ 2024-12-17 18:50 Tomas Vondra <[email protected]>
parent: Robert Haas <[email protected]>
0 siblings, 0 replies; 12+ messages in thread
From: Tomas Vondra @ 2024-12-17 18:50 UTC (permalink / raw)
To: Robert Haas <[email protected]>; Melanie Plageman <[email protected]>; +Cc: Peter Geoghegan <[email protected]>; pgsql-hackers
On 12/17/24 18:52, Robert Haas wrote:
> On Tue, Dec 17, 2024 at 12:06 PM Melanie Plageman
> <[email protected]> wrote:
>> I think your tests show SKIP_PAGES_THRESHOLD has dubious if any
>> benefit related to readahead. But the question is if we care about it
>> for advancing relfrozenxid for small tables.
Yeah, although I'm a bit hesitant to draw such clear conclusion from one
set of benchmarks on one machine (or two, but both with flash). I would
not be surprised if the results were less clear on other types of
storage (say, something like EBS).
>
> It seems like relfrozenxid advancement is really only a problem for
> big tables. If the table is small, the eventual aggressive vacuum
> doesn't cost that much.
>
Yeah, I agree with this.
regards
--
Tomas Vondra
^ permalink raw reply [nested|flat] 12+ messages in thread
* Re: Maybe we should reduce SKIP_PAGES_THRESHOLD a bit?
@ 2024-12-17 19:49 Melanie Plageman <[email protected]>
parent: Tomas Vondra <[email protected]>
0 siblings, 0 replies; 12+ messages in thread
From: Melanie Plageman @ 2024-12-17 19:49 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; +Cc: Peter Geoghegan <[email protected]>; pgsql-hackers
On Tue, Dec 17, 2024 at 1:46 PM Tomas Vondra <[email protected]> wrote:
>
> On 12/17/24 18:06, Melanie Plageman wrote:
> > On Tue, Dec 17, 2024 at 9:11 AM Tomas Vondra <[email protected]> wrote:
> >>
> >>
> >>
> >> On 12/16/24 19:49, Melanie Plageman wrote:
> >>
> >>> No, I'm talking about the behavior of causing small pockets of
> >>> all-frozen pages which end up being smaller than SKIP_PAGES_THRESHOLD
> >>> and are then scanned (even though they are already frozen). What I
> >>> describe in that email I cited is that because we freeze
> >>> opportunistically when we have or will emit an FPI, and bgwriter will
> >>> write out blocks in clocksweep order, we end up with random pockets of
> >>> pages getting frozen during/after a checkpoint. Then in the next
> >>> vacuum, we end up scanning those all-frozen pages again because the
> >>> ranges of frozen pages are smaller than SKIP_PAGES_THRESHOLD. This is
> >>> mostly going to happen for an insert-only workload. I'm not saying
> >>> freezing the pages is bad, I'm saying that causing these pockets of
> >>> frozen pages leads to scanning all-frozen pages on future vacuums.
> >>>
> >>
> >> Yeah, this interaction between the components is not great :-( But can
> >> we think of a way to reduce the fragmentation? What would need to change?
> >
> > Well reducing SKIP_PAGES_THRESHOLD would help.
>
> How does SKIP_PAGES_THRESHOLD change the fragmentation? I think that's
> the side that's affected by the fragmentation, but it's really due to
> the eager freezing / bgwriter evictions, etc. If the threshold is set to
> 1 (i.e. to always skip), that just lowers the impact, but the relation
> is still as fragmented as before, no?
Yep, exactly. It doesn't help with fragmentation. It just helps us not
scan all-frozen pages. The question is whether or not the
fragmentation on its own matters. I think it would be better if we
didn't have it -- we could potentially do larger reads, for example,
if we have one continuous block of pages that are not all-frozen (most
likely when using the read stream API).
> > And unfortunately we do
> > not know if the skippable pages are all-frozen without extra
> > visibilitymap_get_status() calls -- so we can't decide to avoid
> > scanning ranges of skippable pages because they are frozen.
> >
>
> I may be missing something, but doesn't find_next_unskippable_block()
> already get those bits? In fact, it even checks VISIBILITYMAP_ALL_FROZEN
> but only for aggressive vacuum. But even if that wasn't the case, isn't
> checking the VM likely much cheaper than vacuuming the heap page?
find_next_unskippable_block() has them, but then if we do decide to
skip a range of pages, back in heap_vac_scan_next_block() where we
decide whether or not to skip a range using SKIP_PAGES_THRESHOLD, we
know that the pages in the range are all-visible (otherwise they
wouldn't be skippable) but we no longer know which of them were
all-frozen.
> >> Maybe the freezing code could check how many of the nearby pages are
> >> frozen, and consider that together with the FPI write?
> >
> > That's an interesting idea. We wouldn't have any guaranteed info
> > because we only have a lock on the page we are considering freezing.
> > But we could keep track of the length of a run of pages we are
> > freezing and opportunistically freeze pages that don't require
> > freezing if they follow one or more pages requiring freezing.
>
> I don't think we need a "guaranteed" information - a heuristics that's
> correct most of the time (say, >90%?) ought to be good enough. I mean,
> it has to be, because we'll never get a rule that's correct 100%. So
> even just looking at a batch of pages in VM should be enough, no?
>
> > But I don't know how much more this buys us than removing
> > SKIP_PAGES_THRESHOLD. Since it would "fix" the fragmentation, perhaps
> > it makes larger future vacuum reads possible. But I wonder how much
> > benefit it would be vs complexity.
> >
>
> I think that depends on which cost we're talking about. If we only talk
> about the efficiency of a single vacuum, then it probably does not help
> very much. I mean, if we assume the relation is already fragmented, then
> it seems to be cheaper to vacuum just the pages that need it (as if with
> SKIP_PAGES_THRESHOLD=1).
>
> But if we're talking about long-time benefits, in reducing the amount of
> freezing needed overall, maybe it'd be a win? I don't know.
Yea, it just depends on whether or not the pages we freeze for this
reason are likely to stay frozen.
I think I misspoke in saying we want to freeze pages next to pages
requiring freezing. What we really want to do is freeze pages next to
pages that are being opportunistically frozen -- because those are the
ones that are creating the fragmentation. But, then where do you draw
the line? You won't know if you are creating lots of random holes
until after you've skipped opportunistically freezing some pages --
and by then it's too late.
- Melanie
^ permalink raw reply [nested|flat] 12+ messages in thread
end of thread, other threads:[~2024-12-17 19:49 UTC | newest]
Thread overview: 12+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2018-09-23 10:15 amcheck verification for GiST Andrey Borodin <[email protected]>
2018-09-24 03:29 ` Thomas Munro <[email protected]>
2018-09-24 03:34 ` Andres Freund <[email protected]>
2018-09-24 05:12 ` Andrey Borodin <[email protected]>
2019-04-18 01:22 [PATCH 01/10] Define macros to make XLogReadRecord a state machine Kyotaro Horiguchi <[email protected]>
2019-04-18 01:22 [PATCH 01/10] Define macros to make XLogReadRecord a state machine Kyotaro Horiguchi <[email protected]>
2019-04-18 01:22 [PATCH 01/10] Define macros to make XLogReadRecord a state machine Kyotaro Horiguchi <[email protected]>
2024-12-17 17:06 Re: Maybe we should reduce SKIP_PAGES_THRESHOLD a bit? Melanie Plageman <[email protected]>
2024-12-17 17:52 ` Re: Maybe we should reduce SKIP_PAGES_THRESHOLD a bit? Robert Haas <[email protected]>
2024-12-17 18:50 ` Re: Maybe we should reduce SKIP_PAGES_THRESHOLD a bit? Tomas Vondra <[email protected]>
2024-12-17 18:46 ` Re: Maybe we should reduce SKIP_PAGES_THRESHOLD a bit? Tomas Vondra <[email protected]>
2024-12-17 19:49 ` Re: Maybe we should reduce SKIP_PAGES_THRESHOLD a bit? Melanie Plageman <[email protected]>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox