public inbox for [email protected]help / color / mirror / Atom feed
[PATCH v46 1/7] sequential scan for dshash 3+ messages / 3 participants [nested] [flat]
* [PATCH v46 1/7] sequential scan for dshash @ 2020-03-13 07:58 Kyotaro Horiguchi <[email protected]> 0 siblings, 0 replies; 3+ 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(Thu_Jan_14_15_14_25_2021_903)-- Content-Type: Text/X-Patch; charset=us-ascii Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="v46-0002-Add-conditional-lock-feature-to-dshash.patch" ^ permalink raw reply [nested|flat] 3+ messages in thread
* Re: [BUG] psql: Make \copy from 'text' and 'csv' formats fail on NUL bytes @ 2024-11-10 22:14 Tom Lane <[email protected]> 0 siblings, 1 reply; 3+ messages in thread From: Tom Lane @ 2024-11-10 22:14 UTC (permalink / raw) To: Joel Jacobson <[email protected]>; +Cc: [email protected] "Joel Jacobson" <[email protected]> writes: > On Sun, Nov 10, 2024, at 22:37, Tom Lane wrote: >> That seems like a hack, as it also changes the behavior w.r.t. >> prompts and EOF-mark detection, neither for the better. > Hmm, in what way does it change the behavior? > I ran almost all the tests, including the TAP ones, and none of them failed with > this fix. Is there some behavior that is currently not covered by the test suite? Of course. (Our regression tests are very far from covering 100% of the behavioral space.) In the case at hand, this would break the expected line-by-line prompting for "\copy ... from '/dev/tty'". Playing with this just now, I notice that the prompt you get still claims that \. works to end input, although right now it does not: regression=# \copy int8_tbl from '/dev/tty' Enter data to be copied followed by a newline. End with a backslash and a period on a line by itself, or an EOF signal. >> 1 3 >> 5 6 >> \. >> ^D COPY 2 I'm inclined to think that the prompt still describes what should happen, at least in non-binary mode, although in binary mode we probably ought to just say (and do) "End with an EOF signal". So perhaps the if-test to choose the code path could be if ((isbinary || copystream != pset.cur_cmd_source) && !showprompt) which would allow dropping the vestigial prompt logic in the first path, and we would also need to change the test in the second path that decides if we should check for \. (Likely this should be refactored a bit to make it more understandable. An intermediate flag saying whether we intend to check for \. might help.) Anyway, my point is that we need to think through the desirable behavior for each possible combination of showprompt, isbinary, and copystream != pset.cur_cmd_source, because all 8 cases are reachable. regards, tom lane ^ permalink raw reply [nested|flat] 3+ messages in thread
* Re: [BUG] psql: Make \copy from 'text' and 'csv' formats fail on NUL bytes @ 2024-11-11 10:45 Joel Jacobson <[email protected]> parent: Tom Lane <[email protected]> 0 siblings, 0 replies; 3+ messages in thread From: Joel Jacobson @ 2024-11-11 10:45 UTC (permalink / raw) To: Tom Lane <[email protected]>; +Cc: [email protected] On Sun, Nov 10, 2024, at 23:14, Tom Lane wrote: > "Joel Jacobson" <[email protected]> writes: >> On Sun, Nov 10, 2024, at 22:37, Tom Lane wrote: >>> That seems like a hack, as it also changes the behavior w.r.t. >>> prompts and EOF-mark detection, neither for the better. > >> Hmm, in what way does it change the behavior? >> I ran almost all the tests, including the TAP ones, and none of them failed with >> this fix. Is there some behavior that is currently not covered by the test suite? > > Of course. (Our regression tests are very far from covering 100% of > the behavioral space.) > > In the case at hand, this would break the > expected line-by-line prompting for "\copy ... from '/dev/tty'". Yes, of course, just wondered what kind of behavior in this area that wasn't tested, thanks for explaining it. > Playing with this just now, I notice that the prompt you get > still claims that \. works to end input, although right now > it does not: > > regression=# \copy int8_tbl from '/dev/tty' > Enter data to be copied followed by a newline. > End with a backslash and a period on a line by itself, or an EOF signal. >>> 1 3 >>> 5 6 >>> \. >>> ^D > COPY 2 > > I'm inclined to think that the prompt still describes what should > happen, at least in non-binary mode, although in binary mode we > probably ought to just say (and do) "End with an EOF signal". > > So perhaps the if-test to choose the code path could be > > if ((isbinary || copystream != pset.cur_cmd_source) && !showprompt) Thanks for guidance, that seems to fix, for 6/8 cases I've figured out how to test. > which would allow dropping the vestigial prompt logic in the first > path, I assume you mean that due to "&& !showprompt" the "if (showprompt)" becomes unreachable and can therefore be dropped? > and we would also need to change the test in the second path > that decides if we should check for \. (Likely this should be > refactored a bit to make it more understandable. An intermediate > flag saying whether we intend to check for \. might help.) Maybe check_dot_command? const bool check_dot_command = (copystream == pset.cur_cmd_source); I haven't tried yet to refactor the code, except than replacing the two "copystream == pset.cur_cmd_source" occurrences with the new check_dot_command flag. First want to understand if the two remaining cases are valid, and if they can be tested: > Anyway, my point is that we need to think through the desirable > behavior for each possible combination of showprompt, isbinary, and > copystream != pset.cur_cmd_source, because all 8 cases are reachable. I guess these are the 8 cases? +--------+-------------+----------+------------------+ | CASE | showprompt | isbinary | check_dot_command | +--------+-------------+----------+------------------+ | 1 | false | false | false | | 2 | false | false | true | | 3 | false | true | false | | 4 | false | true | true | | 5 | true | false | false | | 6 | true | false | true | | 7* | true | true | false | | 8* | true | true | true | +--------+-------------+----------+------------------+ * Cases 7 and 8 not tested yet With the changed if-test, case 1-6 works, and for case 1, then binary mode branch is taken instead of the text mode branch, whereas cases 2-6 take the same branch as before. joel@Joels-MBP psql_tester % git diff --no-index -U100 /tmp/psql.log.HEAD /tmp/psql.log diff --git a/tmp/psql.log.HEAD b/tmp/psql.log index 5e44e30..1f48ac9 100644 --- a/tmp/psql.log.HEAD +++ b/tmp/psql.log @@ -1,6 +1,6 @@ -COPY case: 1 TEXT MODE +COPY case: 1 BINARY MODE COPY case: 2 TEXT MODE COPY case: 3 BINARY MODE COPY case: 4 BINARY MODE COPY case: 5 TEXT MODE COPY case: 6 TEXT MODE Here is how I tested each case: # CASE 1: # showprompt: false # isbinary: false # check_dot_command: false psql -c "\copy int8_tbl from '/tmp/int8_tbl.data'" # CASE 2: # showprompt: false # isbinary: false # check_dot_command: true psql -f /tmp/copy_stdin_text.sql # CASE 3: # showprompt: false # isbinary: true # check_dot_command: false psql -c "\copy int8_tbl from '/tmp/int8_tbl.bin' (format binary)" # CASE 4: # showprompt: false # isbinary: true # check_dot_command: true printf '\\copy int8_tbl from stdin (format binary)\n' >/tmp/copy_stdin_binary.sql cat /tmp/int8_tbl.bin >>/tmp/copy_stdin_binary.sql psql -f copy_stdin_binary.sql # CASE 5: # showprompt: true # isbinary: false # check_dot_command: false psql \copy int8_tbl from '/dev/tty' 17 18 19 20 \. # Send EOF (Ctrl+D) # CASE 6: # showprompt: true # isbinary: false # check_dot_command: true psql \copy int8_tbl from stdin 21 22 23 24 \. # CASE 7: # showprompt: true # isbinary: true # check_dot_command: false CASE 7 would be like CASE 5, with the addition of (format binary) that is: \copy int8_tbl from '/dev/tty' (format binary) but I wonder if this is a valid case? Could we really copy/paste or by some other means give psql binary data here? I tried to wrap psql and send the binary content of my '/tmp/int8_tbl.bin' file, and tried sending the EOF control code, and I see I get PGCOPY-message, but the txn isn't committed, so not sure what's happening. Before I continue trying to figure this one out, I just wanted to make sure this is a valid case, and how it is supposed to be used if so? # CASE 8: # showprompt: true # isbinary: true # check_dot_command: true CASE 8 would be like CASE 6, with the addition of (format binary) that is: \copy int8_tbl from stdin (format binary) I've had the same problem with this one, as with CASE 7. Many thanks for guidance. /Joel ^ permalink raw reply [nested|flat] 3+ messages in thread
end of thread, other threads:[~2024-11-11 10:45 UTC | newest] Thread overview: 3+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2020-03-13 07:58 [PATCH v46 1/7] sequential scan for dshash Kyotaro Horiguchi <[email protected]> 2024-11-10 22:14 Re: [BUG] psql: Make \copy from 'text' and 'csv' formats fail on NUL bytes Tom Lane <[email protected]> 2024-11-11 10:45 ` Re: [BUG] psql: Make \copy from 'text' and 'csv' formats fail on NUL bytes Joel Jacobson <[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