public inbox for [email protected]help / color / mirror / Atom feed
[PATCH v45 1/7] sequential scan for dshash 5+ messages / 3 participants [nested] [flat]
* [PATCH v45 1/7] sequential scan for dshash @ 2020-03-13 07:58 Kyotaro Horiguchi <[email protected]> 0 siblings, 0 replies; 5+ messages in thread From: Kyotaro Horiguchi @ 2020-03-13 07:58 UTC (permalink / raw) Dshash did not allow scan the all entries sequentially. This adds the functionality. The interface is similar but a bit different both from that of dynahash and simple dshash search functions. One of the most significant differences is the sequential scan interface of dshash always needs a call to dshash_seq_term when scan ends. Another is locking. Dshash holds partition lock when returning an entry, dshash_seq_next() also holds lock when returning an entry but callers shouldn't release it, since the lock is essential to continue a scan. The seqscan interface allows entry deletion while a scan. The in-scan deletion should be performed by dshash_delete_current(). --- src/backend/lib/dshash.c | 160 ++++++++++++++++++++++++++++++++++++++- src/include/lib/dshash.h | 22 ++++++ 2 files changed, 181 insertions(+), 1 deletion(-) diff --git a/src/backend/lib/dshash.c b/src/backend/lib/dshash.c index e0c763be32..520bfa0979 100644 --- a/src/backend/lib/dshash.c +++ b/src/backend/lib/dshash.c @@ -127,6 +127,10 @@ struct dshash_table #define NUM_SPLITS(size_log2) \ (size_log2 - DSHASH_NUM_PARTITIONS_LOG2) +/* How many buckets are there in a given size? */ +#define NUM_BUCKETS(size_log2) \ + (((size_t) 1) << (size_log2)) + /* How many buckets are there in each partition at a given size? */ #define BUCKETS_PER_PARTITION(size_log2) \ (((size_t) 1) << NUM_SPLITS(size_log2)) @@ -153,6 +157,10 @@ struct dshash_table #define BUCKET_INDEX_FOR_PARTITION(partition, size_log2) \ ((partition) << NUM_SPLITS(size_log2)) +/* Choose partition based on bucket index. */ +#define PARTITION_FOR_BUCKET_INDEX(bucket_idx, size_log2) \ + ((bucket_idx) >> NUM_SPLITS(size_log2)) + /* The head of the active bucket for a given hash value (lvalue). */ #define BUCKET_FOR_HASH(hash_table, hash) \ (hash_table->buckets[ \ @@ -324,7 +332,7 @@ dshash_destroy(dshash_table *hash_table) ensure_valid_bucket_pointers(hash_table); /* Free all the entries. */ - size = ((size_t) 1) << hash_table->size_log2; + size = NUM_BUCKETS(hash_table->size_log2); for (i = 0; i < size; ++i) { dsa_pointer item_pointer = hash_table->buckets[i]; @@ -592,6 +600,156 @@ dshash_memhash(const void *v, size_t size, void *arg) return tag_hash(v, size); } +/* + * dshash_seq_init/_next/_term + * Sequentially scan through dshash table and return all the + * elements one by one, return NULL when no more. + * + * dshash_seq_term should always be called when a scan finished. + * The caller may delete returned elements midst of a scan by using + * dshash_delete_current(). exclusive must be true to delete elements. + */ +void +dshash_seq_init(dshash_seq_status *status, dshash_table *hash_table, + bool exclusive) +{ + status->hash_table = hash_table; + status->curbucket = 0; + status->nbuckets = 0; + status->curitem = NULL; + status->pnextitem = InvalidDsaPointer; + status->curpartition = -1; + status->exclusive = exclusive; +} + +/* + * Returns the next element. + * + * Returned elements are locked and the caller must not explicitly release + * it. It is released at the next call to dshash_next(). + */ +void * +dshash_seq_next(dshash_seq_status *status) +{ + dsa_pointer next_item_pointer; + + if (status->curitem == NULL) + { + int partition; + + Assert(status->curbucket == 0); + Assert(!status->hash_table->find_locked); + + /* first shot. grab the first item. */ + partition = + PARTITION_FOR_BUCKET_INDEX(status->curbucket, + status->hash_table->size_log2); + LWLockAcquire(PARTITION_LOCK(status->hash_table, partition), + status->exclusive ? LW_EXCLUSIVE : LW_SHARED); + status->curpartition = partition; + + /* resize doesn't happen from now until seq scan ends */ + status->nbuckets = + NUM_BUCKETS(status->hash_table->control->size_log2); + ensure_valid_bucket_pointers(status->hash_table); + + next_item_pointer = status->hash_table->buckets[status->curbucket]; + } + else + next_item_pointer = status->pnextitem; + + Assert(LWLockHeldByMeInMode(PARTITION_LOCK(status->hash_table, + status->curpartition), + status->exclusive ? LW_EXCLUSIVE : LW_SHARED)); + + /* Move to the next bucket if we finished the current bucket */ + while (!DsaPointerIsValid(next_item_pointer)) + { + int next_partition; + + if (++status->curbucket >= status->nbuckets) + { + /* all buckets have been scanned. finish. */ + return NULL; + } + + /* Check if move to the next partition */ + next_partition = + PARTITION_FOR_BUCKET_INDEX(status->curbucket, + status->hash_table->size_log2); + + if (status->curpartition != next_partition) + { + /* + * Move to the next partition. Lock the next partition then release + * the current, not in the reverse order to avoid concurrent + * resizing. Avoid dead lock by taking lock in the same order + * with resize(). + */ + LWLockAcquire(PARTITION_LOCK(status->hash_table, + next_partition), + status->exclusive ? LW_EXCLUSIVE : LW_SHARED); + LWLockRelease(PARTITION_LOCK(status->hash_table, + status->curpartition)); + status->curpartition = next_partition; + } + + next_item_pointer = status->hash_table->buckets[status->curbucket]; + } + + status->curitem = + dsa_get_address(status->hash_table->area, next_item_pointer); + status->hash_table->find_locked = true; + status->hash_table->find_exclusively_locked = status->exclusive; + + /* + * The caller may delete the item. Store the next item in case of deletion. + */ + status->pnextitem = status->curitem->next; + + return ENTRY_FROM_ITEM(status->curitem); +} + +/* + * Terminates the seqscan and release all locks. + * + * Should be always called when finishing or exiting a seqscan. + */ +void +dshash_seq_term(dshash_seq_status *status) +{ + status->hash_table->find_locked = false; + status->hash_table->find_exclusively_locked = false; + + if (status->curpartition >= 0) + LWLockRelease(PARTITION_LOCK(status->hash_table, status->curpartition)); +} + +/* Remove the current entry while a seq scan. */ +void +dshash_delete_current(dshash_seq_status *status) +{ + dshash_table *hash_table = status->hash_table; + dshash_table_item *item = status->curitem; + size_t partition = PARTITION_FOR_HASH(item->hash); + + Assert(status->exclusive); + Assert(hash_table->control->magic == DSHASH_MAGIC); + Assert(hash_table->find_locked); + Assert(hash_table->find_exclusively_locked); + Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition), + LW_EXCLUSIVE)); + + delete_item(hash_table, item); +} + +/* Get the current entry while a seq scan. */ +void * +dshash_get_current(dshash_seq_status *status) +{ + return ENTRY_FROM_ITEM(status->curitem); +} + /* * Print debugging information about the internal state of the hash table to * stderr. The caller must hold no partition locks. diff --git a/src/include/lib/dshash.h b/src/include/lib/dshash.h index c069ec9de7..a6ea377173 100644 --- a/src/include/lib/dshash.h +++ b/src/include/lib/dshash.h @@ -59,6 +59,21 @@ typedef struct dshash_parameters struct dshash_table_item; typedef struct dshash_table_item dshash_table_item; +/* + * Sequential scan state. The detail is exposed to let users know the storage + * size but it should be considered as an opaque type by callers. + */ +typedef struct dshash_seq_status +{ + dshash_table *hash_table; /* dshash table working on */ + int curbucket; /* bucket number we are at */ + int nbuckets; /* total number of buckets in the dshash */ + dshash_table_item *curitem; /* item we are currently at */ + dsa_pointer pnextitem; /* dsa-pointer to the next item */ + int curpartition; /* partition number we are at */ + bool exclusive; /* locking mode */ +} dshash_seq_status; + /* Creating, sharing and destroying from hash tables. */ extern dshash_table *dshash_create(dsa_area *area, const dshash_parameters *params, @@ -80,6 +95,13 @@ extern bool dshash_delete_key(dshash_table *hash_table, const void *key); extern void dshash_delete_entry(dshash_table *hash_table, void *entry); extern void dshash_release_lock(dshash_table *hash_table, void *entry); +/* seq scan support */ +extern void dshash_seq_init(dshash_seq_status *status, dshash_table *hash_table, + bool exclusive); +extern void *dshash_seq_next(dshash_seq_status *status); +extern void dshash_seq_term(dshash_seq_status *status); +extern void dshash_delete_current(dshash_seq_status *status); +extern void *dshash_get_current(dshash_seq_status *status); /* Convenience hash and compare functions wrapping memcmp and tag_hash. */ extern int dshash_memcmp(const void *a, const void *b, size_t size, void *arg); extern dshash_hash dshash_memhash(const void *v, size_t size, void *arg); -- 2.27.0 ----Next_Part(Fri_Jan__8_10_24_34_2021_185)-- Content-Type: Text/X-Patch; charset=us-ascii Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="v45-0002-Add-conditional-lock-feature-to-dshash.patch" ^ permalink raw reply [nested|flat] 5+ messages in thread
* Fix possible dereference null pointer (src/backend/replication/logical/reorderbuffer.c) @ 2024-04-10 18:07 Ranier Vilela <[email protected]> 0 siblings, 1 reply; 5+ messages in thread From: Ranier Vilela @ 2024-04-10 18:07 UTC (permalink / raw) To: pgsql-hackers Hi, Per Coverity. The function ReorderBufferTXNByXid, can return NULL when the parameter *create* is false. In the functions ReorderBufferSetBaseSnapshot and ReorderBufferXidHasBaseSnapshot, the second call to ReorderBufferTXNByXid, pass false to *create* argument. In the function ReorderBufferSetBaseSnapshot, fixed passing true as argument to always return a valid ReorderBufferTXN pointer. In the function ReorderBufferXidHasBaseSnapshot, fixed by checking if the pointer is NULL. best regards, Ranier Vilela Attachments: [application/octet-stream] fix-possible-dereference-null-pointer-reorderbuffer.patch (1.1K, ../../CAEudQApm0Kffq4GKLdyogyW1tVbkHOOqWTWg169OTsm1W=FUHg@mail.gmail.com/3-fix-possible-dereference-null-pointer-reorderbuffer.patch) download | inline diff: diff --git a/src/backend/replication/logical/reorderbuffer.c b/src/backend/replication/logical/reorderbuffer.c index 5cf28d4df4..95e1db2fcd 100644 --- a/src/backend/replication/logical/reorderbuffer.c +++ b/src/backend/replication/logical/reorderbuffer.c @@ -3188,8 +3188,8 @@ ReorderBufferSetBaseSnapshot(ReorderBuffer *rb, TransactionId xid, */ txn = ReorderBufferTXNByXid(rb, xid, true, &is_new, lsn, true); if (rbtxn_is_known_subxact(txn)) - txn = ReorderBufferTXNByXid(rb, txn->toplevel_xid, false, - NULL, InvalidXLogRecPtr, false); + txn = ReorderBufferTXNByXid(rb, txn->toplevel_xid, true, + NULL, InvalidXLogRecPtr, true); Assert(txn->base_snapshot == NULL); txn->base_snapshot = snap; @@ -3521,8 +3521,12 @@ ReorderBufferXidHasBaseSnapshot(ReorderBuffer *rb, TransactionId xid) /* a known subtxn? operate on top-level txn instead */ if (rbtxn_is_known_subxact(txn)) + { txn = ReorderBufferTXNByXid(rb, txn->toplevel_xid, false, NULL, InvalidXLogRecPtr, false); + if (txn == NULL) + return false; + } return txn->base_snapshot != NULL; } ^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Fix possible dereference null pointer (src/backend/replication/logical/reorderbuffer.c) @ 2024-04-10 21:28 Heikki Linnakangas <[email protected]> parent: Ranier Vilela <[email protected]> 0 siblings, 1 reply; 5+ messages in thread From: Heikki Linnakangas @ 2024-04-10 21:28 UTC (permalink / raw) To: Ranier Vilela <[email protected]>; pgsql-hackers On 10/04/2024 21:07, Ranier Vilela wrote: > Hi, > > Per Coverity. > > The function ReorderBufferTXNByXid, > can return NULL when the parameter *create* is false. > > In the functions ReorderBufferSetBaseSnapshot > and ReorderBufferXidHasBaseSnapshot, > the second call to ReorderBufferTXNByXid, > pass false to *create* argument. > > In the function ReorderBufferSetBaseSnapshot, > fixed passing true as argument to always return > a valid ReorderBufferTXN pointer. > > In the function ReorderBufferXidHasBaseSnapshot, > fixed by checking if the pointer is NULL. If it's a "known subxid", the top-level XID should already have its ReorderBufferTXN entry, so ReorderBufferTXN() should never return NULL. It's not surprising if Coverity doesn't understand that, but setting the 'create' flag doesn't seem like the right fix. If we add "Assert(txn != NULL)", does that silence it? -- Heikki Linnakangas Neon (https://neon.tech) ^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Fix possible dereference null pointer (src/backend/replication/logical/reorderbuffer.c) @ 2024-04-11 12:03 Ranier Vilela <[email protected]> parent: Heikki Linnakangas <[email protected]> 0 siblings, 1 reply; 5+ messages in thread From: Ranier Vilela @ 2024-04-11 12:03 UTC (permalink / raw) To: Heikki Linnakangas <[email protected]>; +Cc: pgsql-hackers Em qua., 10 de abr. de 2024 às 18:28, Heikki Linnakangas <[email protected]> escreveu: > On 10/04/2024 21:07, Ranier Vilela wrote: > > Hi, > > > > Per Coverity. > > > > The function ReorderBufferTXNByXid, > > can return NULL when the parameter *create* is false. > > > > In the functions ReorderBufferSetBaseSnapshot > > and ReorderBufferXidHasBaseSnapshot, > > the second call to ReorderBufferTXNByXid, > > pass false to *create* argument. > > > > In the function ReorderBufferSetBaseSnapshot, > > fixed passing true as argument to always return > > a valid ReorderBufferTXN pointer. > > > > In the function ReorderBufferXidHasBaseSnapshot, > > fixed by checking if the pointer is NULL. > > If it's a "known subxid", the top-level XID should already have its > ReorderBufferTXN entry, so ReorderBufferTXN() should never return NULL. > There are several conditions to not return NULL, I think trusting never is insecure. It's not surprising if Coverity doesn't understand that, but setting the > 'create' flag doesn't seem like the right fix. ReorderBufferSetBaseSnapshot always expects that *txn* exists. If a second call fails, the only solution is to create a new one, no? > If we add "Assert(txn != > NULL)", does that silence it? > I think no. I always compile it as a release to send to Coverity. best regards, Ranier Vilela ^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Fix possible dereference null pointer (src/backend/replication/logical/reorderbuffer.c) @ 2024-04-11 12:54 Heikki Linnakangas <[email protected]> parent: Ranier Vilela <[email protected]> 0 siblings, 0 replies; 5+ messages in thread From: Heikki Linnakangas @ 2024-04-11 12:54 UTC (permalink / raw) To: Ranier Vilela <[email protected]>; +Cc: pgsql-hackers On 11/04/2024 15:03, Ranier Vilela wrote: > Em qua., 10 de abr. de 2024 às 18:28, Heikki Linnakangas > <[email protected] <mailto:[email protected]>> escreveu: > > On 10/04/2024 21:07, Ranier Vilela wrote: > > Hi, > > > > Per Coverity. > > > > The function ReorderBufferTXNByXid, > > can return NULL when the parameter *create* is false. > > > > In the functions ReorderBufferSetBaseSnapshot > > and ReorderBufferXidHasBaseSnapshot, > > the second call to ReorderBufferTXNByXid, > > pass false to *create* argument. > > > > In the function ReorderBufferSetBaseSnapshot, > > fixed passing true as argument to always return > > a valid ReorderBufferTXN pointer. > > > > In the function ReorderBufferXidHasBaseSnapshot, > > fixed by checking if the pointer is NULL. > > If it's a "known subxid", the top-level XID should already have its > ReorderBufferTXN entry, so ReorderBufferTXN() should never return NULL. > > There are several conditions to not return NULL, > I think trusting never is insecure. Well, you could make it an elog(ERROR, ..) instead. But the point is that it should not happen, and if it does for some reason, that's very suprpising and there is a bug somewhere. In that case, we should *not* just blindly create it and proceed as if everything was OK. -- Heikki Linnakangas Neon (https://neon.tech) ^ permalink raw reply [nested|flat] 5+ messages in thread
end of thread, other threads:[~2024-04-11 12:54 UTC | newest] Thread overview: 5+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2020-03-13 07:58 [PATCH v45 1/7] sequential scan for dshash Kyotaro Horiguchi <[email protected]> 2024-04-10 18:07 Fix possible dereference null pointer (src/backend/replication/logical/reorderbuffer.c) Ranier Vilela <[email protected]> 2024-04-10 21:28 ` Re: Fix possible dereference null pointer (src/backend/replication/logical/reorderbuffer.c) Heikki Linnakangas <[email protected]> 2024-04-11 12:03 ` Re: Fix possible dereference null pointer (src/backend/replication/logical/reorderbuffer.c) Ranier Vilela <[email protected]> 2024-04-11 12:54 ` Re: Fix possible dereference null pointer (src/backend/replication/logical/reorderbuffer.c) Heikki Linnakangas <[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