PostgreSQL Source Code  git master
dshash.c File Reference
#include "postgres.h"
#include "common/hashfn.h"
#include "lib/dshash.h"
#include "storage/lwlock.h"
#include "utils/dsa.h"
Include dependency graph for dshash.c:

Go to the source code of this file.

Data Structures

struct  dshash_table_item
 
struct  dshash_partition
 
struct  dshash_table_control
 
struct  dshash_table
 

Macros

#define DSHASH_NUM_PARTITIONS_LOG2   7
 
#define DSHASH_NUM_PARTITIONS   (1 << DSHASH_NUM_PARTITIONS_LOG2)
 
#define DSHASH_MAGIC   0x75ff6a20
 
#define ENTRY_FROM_ITEM(item)    ((char *)(item) + MAXALIGN(sizeof(dshash_table_item)))
 
#define ITEM_FROM_ENTRY(entry)
 
#define NUM_SPLITS(size_log2)    (size_log2 - DSHASH_NUM_PARTITIONS_LOG2)
 
#define NUM_BUCKETS(size_log2)    (((size_t) 1) << (size_log2))
 
#define BUCKETS_PER_PARTITION(size_log2)    (((size_t) 1) << NUM_SPLITS(size_log2))
 
#define MAX_COUNT_PER_PARTITION(hash_table)
 
#define PARTITION_FOR_HASH(hash)    (hash >> ((sizeof(dshash_hash) * CHAR_BIT) - DSHASH_NUM_PARTITIONS_LOG2))
 
#define BUCKET_INDEX_FOR_HASH_AND_SIZE(hash, size_log2)    (hash >> ((sizeof(dshash_hash) * CHAR_BIT) - (size_log2)))
 
#define BUCKET_INDEX_FOR_PARTITION(partition, size_log2)    ((partition) << NUM_SPLITS(size_log2))
 
#define PARTITION_FOR_BUCKET_INDEX(bucket_idx, size_log2)    ((bucket_idx) >> NUM_SPLITS(size_log2))
 
#define BUCKET_FOR_HASH(hash_table, hash)
 
#define PARTITION_LOCK(hash_table, i)    (&(hash_table)->control->partitions[(i)].lock)
 
#define ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table)
 

Typedefs

typedef struct dshash_partition dshash_partition
 
typedef struct dshash_table_control dshash_table_control
 

Functions

static void delete_item (dshash_table *hash_table, dshash_table_item *item)
 
static void resize (dshash_table *hash_table, size_t new_size_log2)
 
static void ensure_valid_bucket_pointers (dshash_table *hash_table)
 
static dshash_table_itemfind_in_bucket (dshash_table *hash_table, const void *key, dsa_pointer item_pointer)
 
static void insert_item_into_bucket (dshash_table *hash_table, dsa_pointer item_pointer, dshash_table_item *item, dsa_pointer *bucket)
 
static dshash_table_iteminsert_into_bucket (dshash_table *hash_table, const void *key, dsa_pointer *bucket)
 
static bool delete_key_from_bucket (dshash_table *hash_table, const void *key, dsa_pointer *bucket_head)
 
static bool delete_item_from_bucket (dshash_table *hash_table, dshash_table_item *item, dsa_pointer *bucket_head)
 
static dshash_hash hash_key (dshash_table *hash_table, const void *key)
 
static bool equal_keys (dshash_table *hash_table, const void *a, const void *b)
 
static void copy_key (dshash_table *hash_table, void *dest, const void *src)
 
dshash_tabledshash_create (dsa_area *area, const dshash_parameters *params, void *arg)
 
dshash_tabledshash_attach (dsa_area *area, const dshash_parameters *params, dshash_table_handle handle, void *arg)
 
void dshash_detach (dshash_table *hash_table)
 
void dshash_destroy (dshash_table *hash_table)
 
dshash_table_handle dshash_get_hash_table_handle (dshash_table *hash_table)
 
void * dshash_find (dshash_table *hash_table, const void *key, bool exclusive)
 
void * dshash_find_or_insert (dshash_table *hash_table, const void *key, bool *found)
 
bool dshash_delete_key (dshash_table *hash_table, const void *key)
 
void dshash_delete_entry (dshash_table *hash_table, void *entry)
 
void dshash_release_lock (dshash_table *hash_table, void *entry)
 
int dshash_memcmp (const void *a, const void *b, size_t size, void *arg)
 
dshash_hash dshash_memhash (const void *v, size_t size, void *arg)
 
void dshash_memcpy (void *dest, const void *src, size_t size, void *arg)
 
int dshash_strcmp (const void *a, const void *b, size_t size, void *arg)
 
dshash_hash dshash_strhash (const void *v, size_t size, void *arg)
 
void dshash_strcpy (void *dest, const void *src, size_t size, void *arg)
 
void dshash_seq_init (dshash_seq_status *status, dshash_table *hash_table, bool exclusive)
 
void * dshash_seq_next (dshash_seq_status *status)
 
void dshash_seq_term (dshash_seq_status *status)
 
void dshash_delete_current (dshash_seq_status *status)
 
void dshash_dump (dshash_table *hash_table)
 

Macro Definition Documentation

◆ ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME

#define ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME (   hash_table)
Value:
Assert(!LWLockAnyHeldByMe(&(hash_table)->control->partitions[0].lock, \
#define Assert(condition)
Definition: c.h:858
#define DSHASH_NUM_PARTITIONS
Definition: dshash.c:60
bool LWLockAnyHeldByMe(LWLock *lock, int nlocks, size_t stride)
Definition: lwlock.c:1913

Definition at line 195 of file dshash.c.

◆ BUCKET_FOR_HASH

#define BUCKET_FOR_HASH (   hash_table,
  hash 
)
Value:
(hash_table->buckets[ \
BUCKET_INDEX_FOR_HASH_AND_SIZE(hash, \
hash_table->size_log2)])
static unsigned hash(unsigned *uv, int n)
Definition: rege_dfa.c:715

Definition at line 161 of file dshash.c.

◆ BUCKET_INDEX_FOR_HASH_AND_SIZE

#define BUCKET_INDEX_FOR_HASH_AND_SIZE (   hash,
  size_log2 
)     (hash >> ((sizeof(dshash_hash) * CHAR_BIT) - (size_log2)))

Definition at line 149 of file dshash.c.

◆ BUCKET_INDEX_FOR_PARTITION

#define BUCKET_INDEX_FOR_PARTITION (   partition,
  size_log2 
)     ((partition) << NUM_SPLITS(size_log2))

Definition at line 153 of file dshash.c.

◆ BUCKETS_PER_PARTITION

#define BUCKETS_PER_PARTITION (   size_log2)     (((size_t) 1) << NUM_SPLITS(size_log2))

Definition at line 131 of file dshash.c.

◆ DSHASH_MAGIC

#define DSHASH_MAGIC   0x75ff6a20

Definition at line 63 of file dshash.c.

◆ DSHASH_NUM_PARTITIONS

#define DSHASH_NUM_PARTITIONS   (1 << DSHASH_NUM_PARTITIONS_LOG2)

Definition at line 60 of file dshash.c.

◆ DSHASH_NUM_PARTITIONS_LOG2

#define DSHASH_NUM_PARTITIONS_LOG2   7

Definition at line 59 of file dshash.c.

◆ ENTRY_FROM_ITEM

#define ENTRY_FROM_ITEM (   item)     ((char *)(item) + MAXALIGN(sizeof(dshash_table_item)))

Definition at line 114 of file dshash.c.

◆ ITEM_FROM_ENTRY

#define ITEM_FROM_ENTRY (   entry)
Value:
((dshash_table_item *)((char *)(entry) - \
#define MAXALIGN(LEN)
Definition: c.h:811

Definition at line 118 of file dshash.c.

◆ MAX_COUNT_PER_PARTITION

#define MAX_COUNT_PER_PARTITION (   hash_table)
Value:
(BUCKETS_PER_PARTITION(hash_table->size_log2) / 2 + \
BUCKETS_PER_PARTITION(hash_table->size_log2) / 4)
#define BUCKETS_PER_PARTITION(size_log2)
Definition: dshash.c:131

Definition at line 135 of file dshash.c.

◆ NUM_BUCKETS

#define NUM_BUCKETS (   size_log2)     (((size_t) 1) << (size_log2))

Definition at line 127 of file dshash.c.

◆ NUM_SPLITS

#define NUM_SPLITS (   size_log2)     (size_log2 - DSHASH_NUM_PARTITIONS_LOG2)

Definition at line 123 of file dshash.c.

◆ PARTITION_FOR_BUCKET_INDEX

#define PARTITION_FOR_BUCKET_INDEX (   bucket_idx,
  size_log2 
)     ((bucket_idx) >> NUM_SPLITS(size_log2))

Definition at line 157 of file dshash.c.

◆ PARTITION_FOR_HASH

#define PARTITION_FOR_HASH (   hash)     (hash >> ((sizeof(dshash_hash) * CHAR_BIT) - DSHASH_NUM_PARTITIONS_LOG2))

Definition at line 140 of file dshash.c.

◆ PARTITION_LOCK

#define PARTITION_LOCK (   hash_table,
  i 
)     (&(hash_table)->control->partitions[(i)].lock)

Definition at line 192 of file dshash.c.

Typedef Documentation

◆ dshash_partition

◆ dshash_table_control

Function Documentation

◆ copy_key()

static void copy_key ( dshash_table hash_table,
void *  dest,
const void *  src 
)
inlinestatic

Definition at line 1083 of file dshash.c.

1084 {
1085  hash_table->params.copy_function(dest, src,
1086  hash_table->params.key_size,
1087  hash_table->arg);
1088 }
size_t key_size
Definition: dshash.h:56
dshash_copy_function copy_function
Definition: dshash.h:60
dshash_parameters params
Definition: dshash.c:106
void * arg
Definition: dshash.c:107

References dshash_table::arg, dshash_parameters::copy_function, generate_unaccent_rules::dest, dshash_parameters::key_size, and dshash_table::params.

Referenced by insert_into_bucket().

◆ delete_item()

static void delete_item ( dshash_table hash_table,
dshash_table_item item 
)
static

Definition at line 832 of file dshash.c.

833 {
834  size_t hash = item->hash;
835  size_t partition = PARTITION_FOR_HASH(hash);
836 
837  Assert(LWLockHeldByMe(PARTITION_LOCK(hash_table, partition)));
838 
839  if (delete_item_from_bucket(hash_table, item,
840  &BUCKET_FOR_HASH(hash_table, hash)))
841  {
842  Assert(hash_table->control->partitions[partition].count > 0);
843  --hash_table->control->partitions[partition].count;
844  }
845  else
846  {
847  Assert(false);
848  }
849 }
#define PARTITION_LOCK(hash_table, i)
Definition: dshash.c:192
static bool delete_item_from_bucket(dshash_table *hash_table, dshash_table_item *item, dsa_pointer *bucket_head)
Definition: dshash.c:1033
#define PARTITION_FOR_HASH(hash)
Definition: dshash.c:140
#define BUCKET_FOR_HASH(hash_table, hash)
Definition: dshash.c:161
bool LWLockHeldByMe(LWLock *lock)
Definition: lwlock.c:1895
size_t count
Definition: dshash.c:76
dshash_partition partitions[DSHASH_NUM_PARTITIONS]
Definition: dshash.c:87
dshash_hash hash
Definition: dshash.c:49
dshash_table_control * control
Definition: dshash.c:108

References Assert, BUCKET_FOR_HASH, dshash_table::control, dshash_partition::count, delete_item_from_bucket(), dshash_table_item::hash, hash(), LWLockHeldByMe(), PARTITION_FOR_HASH, PARTITION_LOCK, and dshash_table_control::partitions.

Referenced by dshash_delete_current(), and dshash_delete_entry().

◆ delete_item_from_bucket()

static bool delete_item_from_bucket ( dshash_table hash_table,
dshash_table_item item,
dsa_pointer bucket_head 
)
static

Definition at line 1033 of file dshash.c.

1036 {
1037  while (DsaPointerIsValid(*bucket_head))
1038  {
1039  dshash_table_item *bucket_item;
1040 
1041  bucket_item = dsa_get_address(hash_table->area, *bucket_head);
1042 
1043  if (bucket_item == item)
1044  {
1045  dsa_pointer next;
1046 
1047  next = item->next;
1048  dsa_free(hash_table->area, *bucket_head);
1049  *bucket_head = next;
1050  return true;
1051  }
1052  bucket_head = &bucket_item->next;
1053  }
1054  return false;
1055 }
static int32 next
Definition: blutils.c:221
void * dsa_get_address(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:942
void dsa_free(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:826
uint64 dsa_pointer
Definition: dsa.h:62
#define DsaPointerIsValid(x)
Definition: dsa.h:106
dsa_pointer next
Definition: dshash.c:47
dsa_area * area
Definition: dshash.c:105

References dshash_table::area, dsa_free(), dsa_get_address(), DsaPointerIsValid, next, and dshash_table_item::next.

Referenced by delete_item().

◆ delete_key_from_bucket()

static bool delete_key_from_bucket ( dshash_table hash_table,
const void *  key,
dsa_pointer bucket_head 
)
static

Definition at line 1004 of file dshash.c.

1007 {
1008  while (DsaPointerIsValid(*bucket_head))
1009  {
1010  dshash_table_item *item;
1011 
1012  item = dsa_get_address(hash_table->area, *bucket_head);
1013 
1014  if (equal_keys(hash_table, key, ENTRY_FROM_ITEM(item)))
1015  {
1016  dsa_pointer next;
1017 
1018  next = item->next;
1019  dsa_free(hash_table->area, *bucket_head);
1020  *bucket_head = next;
1021 
1022  return true;
1023  }
1024  bucket_head = &item->next;
1025  }
1026  return false;
1027 }
static bool equal_keys(dshash_table *hash_table, const void *a, const void *b)
Definition: dshash.c:1072
#define ENTRY_FROM_ITEM(item)
Definition: dshash.c:114

References dshash_table::area, dsa_free(), dsa_get_address(), DsaPointerIsValid, ENTRY_FROM_ITEM, equal_keys(), sort-test::key, next, and dshash_table_item::next.

Referenced by dshash_delete_key().

◆ dshash_attach()

dshash_table* dshash_attach ( dsa_area area,
const dshash_parameters params,
dshash_table_handle  handle,
void *  arg 
)

Definition at line 270 of file dshash.c.

272 {
273  dshash_table *hash_table;
274  dsa_pointer control;
275 
276  /* Allocate the backend-local object representing the hash table. */
277  hash_table = palloc(sizeof(dshash_table));
278 
279  /* Find the control object in shared memory. */
280  control = handle;
281 
282  /* Set up the local hash table struct. */
283  hash_table->area = area;
284  hash_table->params = *params;
285  hash_table->arg = arg;
286  hash_table->control = dsa_get_address(area, control);
287  Assert(hash_table->control->magic == DSHASH_MAGIC);
288 
289  /*
290  * These will later be set to the correct values by
291  * ensure_valid_bucket_pointers(), at which time we'll be holding a
292  * partition lock for interlocking against concurrent resizing.
293  */
294  hash_table->buckets = NULL;
295  hash_table->size_log2 = 0;
296 
297  return hash_table;
298 }
#define DSHASH_MAGIC
Definition: dshash.c:63
void * palloc(Size size)
Definition: mcxt.c:1316
void * arg
dsa_pointer * buckets
Definition: dshash.c:109
size_t size_log2
Definition: dshash.c:110

References dshash_table::area, dshash_table::arg, arg, Assert, dshash_table::buckets, dshash_table::control, dsa_get_address(), DSHASH_MAGIC, dshash_table_control::magic, palloc(), dshash_table::params, and dshash_table::size_log2.

Referenced by init_dsm_registry(), logicalrep_launcher_attach_dshmem(), pgstat_attach_shmem(), and SharedRecordTypmodRegistryAttach().

◆ dshash_create()

dshash_table* dshash_create ( dsa_area area,
const dshash_parameters params,
void *  arg 
)

Definition at line 206 of file dshash.c.

207 {
208  dshash_table *hash_table;
209  dsa_pointer control;
210 
211  /* Allocate the backend-local object representing the hash table. */
212  hash_table = palloc(sizeof(dshash_table));
213 
214  /* Allocate the control object in shared memory. */
215  control = dsa_allocate(area, sizeof(dshash_table_control));
216 
217  /* Set up the local and shared hash table structs. */
218  hash_table->area = area;
219  hash_table->params = *params;
220  hash_table->arg = arg;
221  hash_table->control = dsa_get_address(area, control);
222  hash_table->control->handle = control;
223  hash_table->control->magic = DSHASH_MAGIC;
224  hash_table->control->lwlock_tranche_id = params->tranche_id;
225 
226  /* Set up the array of lock partitions. */
227  {
229  int tranche_id = hash_table->control->lwlock_tranche_id;
230  int i;
231 
232  for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
233  {
234  LWLockInitialize(&partitions[i].lock, tranche_id);
235  partitions[i].count = 0;
236  }
237  }
238 
239  /*
240  * Set up the initial array of buckets. Our initial size is the same as
241  * the number of partitions.
242  */
244  hash_table->control->buckets =
248  if (!DsaPointerIsValid(hash_table->control->buckets))
249  {
250  dsa_free(area, control);
251  ereport(ERROR,
252  (errcode(ERRCODE_OUT_OF_MEMORY),
253  errmsg("out of memory"),
254  errdetail("Failed on DSA request of size %zu.",
255  sizeof(dsa_pointer) * DSHASH_NUM_PARTITIONS)));
256  }
257  hash_table->buckets = dsa_get_address(area,
258  hash_table->control->buckets);
259  hash_table->size_log2 = hash_table->control->size_log2;
260 
261  return hash_table;
262 }
dsa_pointer dsa_allocate_extended(dsa_area *area, size_t size, int flags)
Definition: dsa.c:671
#define dsa_allocate(area, size)
Definition: dsa.h:109
#define DSA_ALLOC_NO_OOM
Definition: dsa.h:74
#define DSA_ALLOC_ZERO
Definition: dsa.h:75
#define DSHASH_NUM_PARTITIONS_LOG2
Definition: dshash.c:59
int errdetail(const char *fmt,...)
Definition: elog.c:1203
int errcode(int sqlerrcode)
Definition: elog.c:857
int errmsg(const char *fmt,...)
Definition: elog.c:1070
#define ERROR
Definition: elog.h:39
#define ereport(elevel,...)
Definition: elog.h:149
int i
Definition: isn.c:73
void LWLockInitialize(LWLock *lock, int tranche_id)
Definition: lwlock.c:709
static int partitions
Definition: pgbench.c:223
size_t size_log2
Definition: dshash.c:96
dshash_table_handle handle
Definition: dshash.c:85
dsa_pointer buckets
Definition: dshash.c:97

References dshash_table::area, dshash_table::arg, arg, dshash_table_control::buckets, dshash_table::buckets, dshash_table::control, DSA_ALLOC_NO_OOM, DSA_ALLOC_ZERO, dsa_allocate, dsa_allocate_extended(), dsa_free(), dsa_get_address(), DsaPointerIsValid, DSHASH_MAGIC, DSHASH_NUM_PARTITIONS, DSHASH_NUM_PARTITIONS_LOG2, ereport, errcode(), errdetail(), errmsg(), ERROR, dshash_table_control::handle, i, dshash_table_control::lwlock_tranche_id, LWLockInitialize(), dshash_table_control::magic, palloc(), dshash_table::params, dshash_table_control::partitions, partitions, dshash_table_control::size_log2, dshash_table::size_log2, and dshash_parameters::tranche_id.

Referenced by init_dsm_registry(), logicalrep_launcher_attach_dshmem(), SharedRecordTypmodRegistryInit(), and StatsShmemInit().

◆ dshash_delete_current()

void dshash_delete_current ( dshash_seq_status status)

Definition at line 757 of file dshash.c.

758 {
759  dshash_table *hash_table = status->hash_table;
760  dshash_table_item *item = status->curitem;
761  size_t partition PG_USED_FOR_ASSERTS_ONLY;
762 
763  partition = PARTITION_FOR_HASH(item->hash);
764 
765  Assert(status->exclusive);
766  Assert(hash_table->control->magic == DSHASH_MAGIC);
767  Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition),
768  LW_EXCLUSIVE));
769 
770  delete_item(hash_table, item);
771 }
#define PG_USED_FOR_ASSERTS_ONLY
Definition: c.h:182
static void delete_item(dshash_table *hash_table, dshash_table_item *item)
Definition: dshash.c:832
bool LWLockHeldByMeInMode(LWLock *lock, LWLockMode mode)
Definition: lwlock.c:1939
@ LW_EXCLUSIVE
Definition: lwlock.h:114
bool exclusive
Definition: dshash.h:80
dshash_table_item * curitem
Definition: dshash.h:77
dshash_table * hash_table
Definition: dshash.h:74

References Assert, dshash_table::control, dshash_seq_status::curitem, delete_item(), DSHASH_MAGIC, dshash_seq_status::exclusive, dshash_table_item::hash, dshash_seq_status::hash_table, LW_EXCLUSIVE, LWLockHeldByMeInMode(), dshash_table_control::magic, PARTITION_FOR_HASH, PARTITION_LOCK, and PG_USED_FOR_ASSERTS_ONLY.

Referenced by pgstat_free_entry().

◆ dshash_delete_entry()

void dshash_delete_entry ( dshash_table hash_table,
void *  entry 
)

Definition at line 541 of file dshash.c.

542 {
543  dshash_table_item *item = ITEM_FROM_ENTRY(entry);
544  size_t partition = PARTITION_FOR_HASH(item->hash);
545 
546  Assert(hash_table->control->magic == DSHASH_MAGIC);
547  Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition),
548  LW_EXCLUSIVE));
549 
550  delete_item(hash_table, item);
551  LWLockRelease(PARTITION_LOCK(hash_table, partition));
552 }
#define ITEM_FROM_ENTRY(entry)
Definition: dshash.c:118
void LWLockRelease(LWLock *lock)
Definition: lwlock.c:1783

References Assert, dshash_table::control, delete_item(), DSHASH_MAGIC, dshash_table_item::hash, ITEM_FROM_ENTRY, LW_EXCLUSIVE, LWLockHeldByMeInMode(), LWLockRelease(), dshash_table_control::magic, PARTITION_FOR_HASH, and PARTITION_LOCK.

Referenced by pgstat_free_entry().

◆ dshash_delete_key()

bool dshash_delete_key ( dshash_table hash_table,
const void *  key 
)

Definition at line 503 of file dshash.c.

504 {
506  size_t partition;
507  bool found;
508 
509  Assert(hash_table->control->magic == DSHASH_MAGIC);
511 
512  hash = hash_key(hash_table, key);
513  partition = PARTITION_FOR_HASH(hash);
514 
515  LWLockAcquire(PARTITION_LOCK(hash_table, partition), LW_EXCLUSIVE);
516  ensure_valid_bucket_pointers(hash_table);
517 
518  if (delete_key_from_bucket(hash_table, key,
519  &BUCKET_FOR_HASH(hash_table, hash)))
520  {
521  Assert(hash_table->control->partitions[partition].count > 0);
522  found = true;
523  --hash_table->control->partitions[partition].count;
524  }
525  else
526  found = false;
527 
528  LWLockRelease(PARTITION_LOCK(hash_table, partition));
529 
530  return found;
531 }
static bool delete_key_from_bucket(dshash_table *hash_table, const void *key, dsa_pointer *bucket_head)
Definition: dshash.c:1004
static dshash_hash hash_key(dshash_table *hash_table, const void *key)
Definition: dshash.c:1061
#define ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table)
Definition: dshash.c:195
static void ensure_valid_bucket_pointers(dshash_table *hash_table)
Definition: dshash.c:935
uint32 dshash_hash
Definition: dshash.h:30
bool LWLockAcquire(LWLock *lock, LWLockMode mode)
Definition: lwlock.c:1170

References Assert, ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME, BUCKET_FOR_HASH, dshash_table::control, dshash_partition::count, delete_key_from_bucket(), DSHASH_MAGIC, ensure_valid_bucket_pointers(), hash(), hash_key(), sort-test::key, LW_EXCLUSIVE, LWLockAcquire(), LWLockRelease(), dshash_table_control::magic, PARTITION_FOR_HASH, PARTITION_LOCK, and dshash_table_control::partitions.

Referenced by ApplyLauncherForgetWorkerStartTime(), and find_or_make_matching_shared_tupledesc().

◆ dshash_destroy()

void dshash_destroy ( dshash_table hash_table)

Definition at line 323 of file dshash.c.

324 {
325  size_t size;
326  size_t i;
327 
328  Assert(hash_table->control->magic == DSHASH_MAGIC);
329  ensure_valid_bucket_pointers(hash_table);
330 
331  /* Free all the entries. */
332  size = NUM_BUCKETS(hash_table->size_log2);
333  for (i = 0; i < size; ++i)
334  {
335  dsa_pointer item_pointer = hash_table->buckets[i];
336 
337  while (DsaPointerIsValid(item_pointer))
338  {
339  dshash_table_item *item;
340  dsa_pointer next_item_pointer;
341 
342  item = dsa_get_address(hash_table->area, item_pointer);
343  next_item_pointer = item->next;
344  dsa_free(hash_table->area, item_pointer);
345  item_pointer = next_item_pointer;
346  }
347  }
348 
349  /*
350  * Vandalize the control block to help catch programming errors where
351  * other backends access the memory formerly occupied by this hash table.
352  */
353  hash_table->control->magic = 0;
354 
355  /* Free the active table and control object. */
356  dsa_free(hash_table->area, hash_table->control->buckets);
357  dsa_free(hash_table->area, hash_table->control->handle);
358 
359  pfree(hash_table);
360 }
#define NUM_BUCKETS(size_log2)
Definition: dshash.c:127
void pfree(void *pointer)
Definition: mcxt.c:1520
static pg_noinline void Size size
Definition: slab.c:607

References dshash_table::area, Assert, dshash_table_control::buckets, dshash_table::buckets, dshash_table::control, dsa_free(), dsa_get_address(), DsaPointerIsValid, DSHASH_MAGIC, ensure_valid_bucket_pointers(), dshash_table_control::handle, i, dshash_table_control::magic, dshash_table_item::next, NUM_BUCKETS, pfree(), size, and dshash_table::size_log2.

◆ dshash_detach()

void dshash_detach ( dshash_table hash_table)

Definition at line 307 of file dshash.c.

308 {
310 
311  /* The hash table may have been destroyed. Just free local memory. */
312  pfree(hash_table);
313 }

References ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME, and pfree().

Referenced by pgstat_detach_shmem(), shared_record_typmod_registry_detach(), and StatsShmemInit().

◆ dshash_dump()

void dshash_dump ( dshash_table hash_table)

Definition at line 778 of file dshash.c.

779 {
780  size_t i;
781  size_t j;
782 
783  Assert(hash_table->control->magic == DSHASH_MAGIC);
785 
786  for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
787  {
788  Assert(!LWLockHeldByMe(PARTITION_LOCK(hash_table, i)));
789  LWLockAcquire(PARTITION_LOCK(hash_table, i), LW_SHARED);
790  }
791 
792  ensure_valid_bucket_pointers(hash_table);
793 
794  fprintf(stderr,
795  "hash table size = %zu\n", (size_t) 1 << hash_table->size_log2);
796  for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
797  {
798  dshash_partition *partition = &hash_table->control->partitions[i];
799  size_t begin = BUCKET_INDEX_FOR_PARTITION(i, hash_table->size_log2);
800  size_t end = BUCKET_INDEX_FOR_PARTITION(i + 1, hash_table->size_log2);
801 
802  fprintf(stderr, " partition %zu\n", i);
803  fprintf(stderr,
804  " active buckets (key count = %zu)\n", partition->count);
805 
806  for (j = begin; j < end; ++j)
807  {
808  size_t count = 0;
809  dsa_pointer bucket = hash_table->buckets[j];
810 
811  while (DsaPointerIsValid(bucket))
812  {
813  dshash_table_item *item;
814 
815  item = dsa_get_address(hash_table->area, bucket);
816 
817  bucket = item->next;
818  ++count;
819  }
820  fprintf(stderr, " bucket %zu (key count = %zu)\n", j, count);
821  }
822  }
823 
824  for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
825  LWLockRelease(PARTITION_LOCK(hash_table, i));
826 }
#define BUCKET_INDEX_FOR_PARTITION(partition, size_log2)
Definition: dshash.c:153
int j
Definition: isn.c:74
@ LW_SHARED
Definition: lwlock.h:115
#define fprintf
Definition: port.h:242

References dshash_table::area, Assert, ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME, BUCKET_INDEX_FOR_PARTITION, dshash_table::buckets, dshash_table::control, dshash_partition::count, dsa_get_address(), DsaPointerIsValid, DSHASH_MAGIC, DSHASH_NUM_PARTITIONS, ensure_valid_bucket_pointers(), fprintf, i, j, LW_SHARED, LWLockAcquire(), LWLockHeldByMe(), LWLockRelease(), dshash_table_control::magic, dshash_table_item::next, PARTITION_LOCK, dshash_table_control::partitions, and dshash_table::size_log2.

◆ dshash_find()

void* dshash_find ( dshash_table hash_table,
const void *  key,
bool  exclusive 
)

Definition at line 390 of file dshash.c.

391 {
393  size_t partition;
394  dshash_table_item *item;
395 
396  hash = hash_key(hash_table, key);
397  partition = PARTITION_FOR_HASH(hash);
398 
399  Assert(hash_table->control->magic == DSHASH_MAGIC);
401 
402  LWLockAcquire(PARTITION_LOCK(hash_table, partition),
403  exclusive ? LW_EXCLUSIVE : LW_SHARED);
404  ensure_valid_bucket_pointers(hash_table);
405 
406  /* Search the active bucket. */
407  item = find_in_bucket(hash_table, key, BUCKET_FOR_HASH(hash_table, hash));
408 
409  if (!item)
410  {
411  /* Not found. */
412  LWLockRelease(PARTITION_LOCK(hash_table, partition));
413  return NULL;
414  }
415  else
416  {
417  /* The caller will free the lock by calling dshash_release_lock. */
418  return ENTRY_FROM_ITEM(item);
419  }
420 }
static dshash_table_item * find_in_bucket(dshash_table *hash_table, const void *key, dsa_pointer item_pointer)
Definition: dshash.c:949

References Assert, ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME, BUCKET_FOR_HASH, dshash_table::control, DSHASH_MAGIC, ensure_valid_bucket_pointers(), ENTRY_FROM_ITEM, find_in_bucket(), hash(), hash_key(), sort-test::key, LW_EXCLUSIVE, LW_SHARED, LWLockAcquire(), LWLockRelease(), dshash_table_control::magic, PARTITION_FOR_HASH, and PARTITION_LOCK.

Referenced by ApplyLauncherGetWorkerStartTime(), find_or_make_matching_shared_tupledesc(), lookup_rowtype_tupdesc_internal(), pgstat_drop_entry(), pgstat_get_entry_ref(), and pgstat_release_entry_ref().

◆ dshash_find_or_insert()

void* dshash_find_or_insert ( dshash_table hash_table,
const void *  key,
bool found 
)

Definition at line 433 of file dshash.c.

436 {
438  size_t partition_index;
439  dshash_partition *partition;
440  dshash_table_item *item;
441 
442  hash = hash_key(hash_table, key);
443  partition_index = PARTITION_FOR_HASH(hash);
444  partition = &hash_table->control->partitions[partition_index];
445 
446  Assert(hash_table->control->magic == DSHASH_MAGIC);
448 
449 restart:
450  LWLockAcquire(PARTITION_LOCK(hash_table, partition_index),
451  LW_EXCLUSIVE);
452  ensure_valid_bucket_pointers(hash_table);
453 
454  /* Search the active bucket. */
455  item = find_in_bucket(hash_table, key, BUCKET_FOR_HASH(hash_table, hash));
456 
457  if (item)
458  *found = true;
459  else
460  {
461  *found = false;
462 
463  /* Check if we are getting too full. */
464  if (partition->count > MAX_COUNT_PER_PARTITION(hash_table))
465  {
466  /*
467  * The load factor (= keys / buckets) for all buckets protected by
468  * this partition is > 0.75. Presumably the same applies
469  * generally across the whole hash table (though we don't attempt
470  * to track that directly to avoid contention on some kind of
471  * central counter; we just assume that this partition is
472  * representative). This is a good time to resize.
473  *
474  * Give up our existing lock first, because resizing needs to
475  * reacquire all the locks in the right order to avoid deadlocks.
476  */
477  LWLockRelease(PARTITION_LOCK(hash_table, partition_index));
478  resize(hash_table, hash_table->size_log2 + 1);
479 
480  goto restart;
481  }
482 
483  /* Finally we can try to insert the new item. */
484  item = insert_into_bucket(hash_table, key,
485  &BUCKET_FOR_HASH(hash_table, hash));
486  item->hash = hash;
487  /* Adjust per-lock-partition counter for load factor knowledge. */
488  ++partition->count;
489  }
490 
491  /* The caller must release the lock with dshash_release_lock. */
492  return ENTRY_FROM_ITEM(item);
493 }
static dshash_table_item * insert_into_bucket(dshash_table *hash_table, const void *key, dsa_pointer *bucket)
Definition: dshash.c:984
#define MAX_COUNT_PER_PARTITION(hash_table)
Definition: dshash.c:135
static void resize(dshash_table *hash_table, size_t new_size_log2)
Definition: dshash.c:858

References Assert, ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME, BUCKET_FOR_HASH, dshash_table::control, dshash_partition::count, DSHASH_MAGIC, ensure_valid_bucket_pointers(), ENTRY_FROM_ITEM, find_in_bucket(), dshash_table_item::hash, hash(), hash_key(), insert_into_bucket(), sort-test::key, LW_EXCLUSIVE, LWLockAcquire(), LWLockRelease(), dshash_table_control::magic, MAX_COUNT_PER_PARTITION, PARTITION_FOR_HASH, PARTITION_LOCK, dshash_table_control::partitions, resize(), and dshash_table::size_log2.

Referenced by ApplyLauncherSetWorkerStartTime(), find_or_make_matching_shared_tupledesc(), GetNamedDSMSegment(), pgstat_get_entry_ref(), pgstat_read_statsfile(), and SharedRecordTypmodRegistryInit().

◆ dshash_get_hash_table_handle()

dshash_table_handle dshash_get_hash_table_handle ( dshash_table hash_table)

◆ dshash_memcmp()

int dshash_memcmp ( const void *  a,
const void *  b,
size_t  size,
void *  arg 
)

Definition at line 572 of file dshash.c.

573 {
574  return memcmp(a, b, size);
575 }
int b
Definition: isn.c:70
int a
Definition: isn.c:69

References a, b, and size.

◆ dshash_memcpy()

void dshash_memcpy ( void *  dest,
const void *  src,
size_t  size,
void *  arg 
)

Definition at line 590 of file dshash.c.

591 {
592  (void) memcpy(dest, src, size);
593 }

References generate_unaccent_rules::dest, and size.

◆ dshash_memhash()

dshash_hash dshash_memhash ( const void *  v,
size_t  size,
void *  arg 
)

Definition at line 581 of file dshash.c.

582 {
583  return tag_hash(v, size);
584 }
uint32 tag_hash(const void *key, Size keysize)
Definition: hashfn.c:677

References size, and tag_hash().

◆ dshash_release_lock()

◆ dshash_seq_init()

void dshash_seq_init ( dshash_seq_status status,
dshash_table hash_table,
bool  exclusive 
)

◆ dshash_seq_next()

void* dshash_seq_next ( dshash_seq_status status)

Definition at line 657 of file dshash.c.

658 {
659  dsa_pointer next_item_pointer;
660 
661  /*
662  * Not yet holding any partition locks. Need to determine the size of the
663  * hash table, it could have been resized since we were looking last.
664  * Since we iterate in partition order, we can start by unconditionally
665  * lock partition 0.
666  *
667  * Once we hold the lock, no resizing can happen until the scan ends. So
668  * we don't need to repeatedly call ensure_valid_bucket_pointers().
669  */
670  if (status->curpartition == -1)
671  {
672  Assert(status->curbucket == 0);
674 
675  status->curpartition = 0;
676 
678  status->curpartition),
679  status->exclusive ? LW_EXCLUSIVE : LW_SHARED);
680 
682 
683  status->nbuckets =
685  next_item_pointer = status->hash_table->buckets[status->curbucket];
686  }
687  else
688  next_item_pointer = status->pnextitem;
689 
691  status->curpartition),
692  status->exclusive ? LW_EXCLUSIVE : LW_SHARED));
693 
694  /* Move to the next bucket if we finished the current bucket */
695  while (!DsaPointerIsValid(next_item_pointer))
696  {
697  int next_partition;
698 
699  if (++status->curbucket >= status->nbuckets)
700  {
701  /* all buckets have been scanned. finish. */
702  return NULL;
703  }
704 
705  /* Check if move to the next partition */
706  next_partition =
708  status->hash_table->size_log2);
709 
710  if (status->curpartition != next_partition)
711  {
712  /*
713  * Move to the next partition. Lock the next partition then
714  * release the current, not in the reverse order to avoid
715  * concurrent resizing. Avoid dead lock by taking lock in the
716  * same order with resize().
717  */
719  next_partition),
720  status->exclusive ? LW_EXCLUSIVE : LW_SHARED);
722  status->curpartition));
723  status->curpartition = next_partition;
724  }
725 
726  next_item_pointer = status->hash_table->buckets[status->curbucket];
727  }
728 
729  status->curitem =
730  dsa_get_address(status->hash_table->area, next_item_pointer);
731 
732  /*
733  * The caller may delete the item. Store the next item in case of
734  * deletion.
735  */
736  status->pnextitem = status->curitem->next;
737 
738  return ENTRY_FROM_ITEM(status->curitem);
739 }
#define PARTITION_FOR_BUCKET_INDEX(bucket_idx, size_log2)
Definition: dshash.c:157

References dshash_table::area, Assert, ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME, dshash_table::buckets, dshash_table::control, dshash_seq_status::curbucket, dshash_seq_status::curitem, dshash_seq_status::curpartition, dsa_get_address(), DsaPointerIsValid, ensure_valid_bucket_pointers(), ENTRY_FROM_ITEM, dshash_seq_status::exclusive, dshash_seq_status::hash_table, LW_EXCLUSIVE, LW_SHARED, LWLockAcquire(), LWLockHeldByMeInMode(), LWLockRelease(), dshash_seq_status::nbuckets, dshash_table_item::next, NUM_BUCKETS, PARTITION_FOR_BUCKET_INDEX, PARTITION_LOCK, dshash_seq_status::pnextitem, dshash_table_control::size_log2, and dshash_table::size_log2.

Referenced by pgstat_build_snapshot(), pgstat_drop_all_entries(), pgstat_drop_database_and_contents(), pgstat_reset_matching_entries(), and pgstat_write_statsfile().

◆ dshash_seq_term()

◆ dshash_strcmp()

int dshash_strcmp ( const void *  a,
const void *  b,
size_t  size,
void *  arg 
)

Definition at line 599 of file dshash.c.

600 {
601  Assert(strlen((const char *) a) < size);
602  Assert(strlen((const char *) b) < size);
603 
604  return strcmp((const char *) a, (const char *) b);
605 }

References a, Assert, b, and size.

◆ dshash_strcpy()

void dshash_strcpy ( void *  dest,
const void *  src,
size_t  size,
void *  arg 
)

Definition at line 622 of file dshash.c.

623 {
624  Assert(strlen((const char *) src) < size);
625 
626  (void) strcpy((char *) dest, (const char *) src);
627 }

References Assert, generate_unaccent_rules::dest, and size.

◆ dshash_strhash()

dshash_hash dshash_strhash ( const void *  v,
size_t  size,
void *  arg 
)

Definition at line 611 of file dshash.c.

612 {
613  Assert(strlen((const char *) v) < size);
614 
615  return string_hash((const char *) v, size);
616 }
uint32 string_hash(const void *key, Size keysize)
Definition: hashfn.c:660

References Assert, size, and string_hash().

◆ ensure_valid_bucket_pointers()

static void ensure_valid_bucket_pointers ( dshash_table hash_table)
inlinestatic

Definition at line 935 of file dshash.c.

936 {
937  if (hash_table->size_log2 != hash_table->control->size_log2)
938  {
939  hash_table->buckets = dsa_get_address(hash_table->area,
940  hash_table->control->buckets);
941  hash_table->size_log2 = hash_table->control->size_log2;
942  }
943 }

References dshash_table::area, dshash_table_control::buckets, dshash_table::buckets, dshash_table::control, dsa_get_address(), dshash_table_control::size_log2, and dshash_table::size_log2.

Referenced by dshash_delete_key(), dshash_destroy(), dshash_dump(), dshash_find(), dshash_find_or_insert(), and dshash_seq_next().

◆ equal_keys()

static bool equal_keys ( dshash_table hash_table,
const void *  a,
const void *  b 
)
inlinestatic

Definition at line 1072 of file dshash.c.

1073 {
1074  return hash_table->params.compare_function(a, b,
1075  hash_table->params.key_size,
1076  hash_table->arg) == 0;
1077 }
dshash_compare_function compare_function
Definition: dshash.h:58

References a, dshash_table::arg, b, dshash_parameters::compare_function, dshash_parameters::key_size, and dshash_table::params.

Referenced by delete_key_from_bucket(), and find_in_bucket().

◆ find_in_bucket()

static dshash_table_item * find_in_bucket ( dshash_table hash_table,
const void *  key,
dsa_pointer  item_pointer 
)
inlinestatic

Definition at line 949 of file dshash.c.

951 {
952  while (DsaPointerIsValid(item_pointer))
953  {
954  dshash_table_item *item;
955 
956  item = dsa_get_address(hash_table->area, item_pointer);
957  if (equal_keys(hash_table, key, ENTRY_FROM_ITEM(item)))
958  return item;
959  item_pointer = item->next;
960  }
961  return NULL;
962 }

References dshash_table::area, dsa_get_address(), DsaPointerIsValid, ENTRY_FROM_ITEM, equal_keys(), sort-test::key, and dshash_table_item::next.

Referenced by dshash_find(), and dshash_find_or_insert().

◆ hash_key()

static dshash_hash hash_key ( dshash_table hash_table,
const void *  key 
)
inlinestatic

Definition at line 1061 of file dshash.c.

1062 {
1063  return hash_table->params.hash_function(key,
1064  hash_table->params.key_size,
1065  hash_table->arg);
1066 }
dshash_hash_function hash_function
Definition: dshash.h:59

References dshash_table::arg, dshash_parameters::hash_function, sort-test::key, dshash_parameters::key_size, and dshash_table::params.

Referenced by compute_tsvector_stats(), dshash_delete_key(), dshash_find(), and dshash_find_or_insert().

◆ insert_into_bucket()

static dshash_table_item * insert_into_bucket ( dshash_table hash_table,
const void *  key,
dsa_pointer bucket 
)
static

Definition at line 984 of file dshash.c.

987 {
988  dsa_pointer item_pointer;
989  dshash_table_item *item;
990 
991  item_pointer = dsa_allocate(hash_table->area,
992  hash_table->params.entry_size +
993  MAXALIGN(sizeof(dshash_table_item)));
994  item = dsa_get_address(hash_table->area, item_pointer);
995  copy_key(hash_table, ENTRY_FROM_ITEM(item), key);
996  insert_item_into_bucket(hash_table, item_pointer, item, bucket);
997  return item;
998 }
static void insert_item_into_bucket(dshash_table *hash_table, dsa_pointer item_pointer, dshash_table_item *item, dsa_pointer *bucket)
Definition: dshash.c:968
static void copy_key(dshash_table *hash_table, void *dest, const void *src)
Definition: dshash.c:1083
size_t entry_size
Definition: dshash.h:57

References dshash_table::area, copy_key(), dsa_allocate, dsa_get_address(), ENTRY_FROM_ITEM, dshash_parameters::entry_size, insert_item_into_bucket(), sort-test::key, MAXALIGN, and dshash_table::params.

Referenced by dshash_find_or_insert().

◆ insert_item_into_bucket()

static void insert_item_into_bucket ( dshash_table hash_table,
dsa_pointer  item_pointer,
dshash_table_item item,
dsa_pointer bucket 
)
static

Definition at line 968 of file dshash.c.

972 {
973  Assert(item == dsa_get_address(hash_table->area, item_pointer));
974 
975  item->next = *bucket;
976  *bucket = item_pointer;
977 }

References dshash_table::area, Assert, dsa_get_address(), and dshash_table_item::next.

Referenced by insert_into_bucket(), and resize().

◆ resize()

static void resize ( dshash_table hash_table,
size_t  new_size_log2 
)
static

Definition at line 858 of file dshash.c.

859 {
860  dsa_pointer old_buckets;
861  dsa_pointer new_buckets_shared;
862  dsa_pointer *new_buckets;
863  size_t size;
864  size_t new_size = ((size_t) 1) << new_size_log2;
865  size_t i;
866 
867  /*
868  * Acquire the locks for all lock partitions. This is expensive, but we
869  * shouldn't have to do it many times.
870  */
871  for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
872  {
873  Assert(!LWLockHeldByMe(PARTITION_LOCK(hash_table, i)));
874 
876  if (i == 0 && hash_table->control->size_log2 >= new_size_log2)
877  {
878  /*
879  * Another backend has already increased the size; we can avoid
880  * obtaining all the locks and return early.
881  */
882  LWLockRelease(PARTITION_LOCK(hash_table, 0));
883  return;
884  }
885  }
886 
887  Assert(new_size_log2 == hash_table->control->size_log2 + 1);
888 
889  /* Allocate the space for the new table. */
890  new_buckets_shared = dsa_allocate0(hash_table->area,
891  sizeof(dsa_pointer) * new_size);
892  new_buckets = dsa_get_address(hash_table->area, new_buckets_shared);
893 
894  /*
895  * We've allocated the new bucket array; all that remains to do now is to
896  * reinsert all items, which amounts to adjusting all the pointers.
897  */
898  size = ((size_t) 1) << hash_table->control->size_log2;
899  for (i = 0; i < size; ++i)
900  {
901  dsa_pointer item_pointer = hash_table->buckets[i];
902 
903  while (DsaPointerIsValid(item_pointer))
904  {
905  dshash_table_item *item;
906  dsa_pointer next_item_pointer;
907 
908  item = dsa_get_address(hash_table->area, item_pointer);
909  next_item_pointer = item->next;
910  insert_item_into_bucket(hash_table, item_pointer, item,
911  &new_buckets[BUCKET_INDEX_FOR_HASH_AND_SIZE(item->hash,
912  new_size_log2)]);
913  item_pointer = next_item_pointer;
914  }
915  }
916 
917  /* Swap the hash table into place and free the old one. */
918  old_buckets = hash_table->control->buckets;
919  hash_table->control->buckets = new_buckets_shared;
920  hash_table->control->size_log2 = new_size_log2;
921  hash_table->buckets = new_buckets;
922  dsa_free(hash_table->area, old_buckets);
923 
924  /* Release all the locks. */
925  for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
926  LWLockRelease(PARTITION_LOCK(hash_table, i));
927 }
#define dsa_allocate0(area, size)
Definition: dsa.h:113
#define BUCKET_INDEX_FOR_HASH_AND_SIZE(hash, size_log2)
Definition: dshash.c:149

References dshash_table::area, Assert, BUCKET_INDEX_FOR_HASH_AND_SIZE, dshash_table_control::buckets, dshash_table::buckets, dshash_table::control, dsa_allocate0, dsa_free(), dsa_get_address(), DsaPointerIsValid, DSHASH_NUM_PARTITIONS, dshash_table_item::hash, i, insert_item_into_bucket(), LW_EXCLUSIVE, LWLockAcquire(), LWLockHeldByMe(), LWLockRelease(), dshash_table_item::next, PARTITION_LOCK, size, and dshash_table_control::size_log2.

Referenced by dshash_find_or_insert().