PostgreSQL Source Code  git master
dshash.c File Reference
#include "postgres.h"
#include "common/hashfn.h"
#include "lib/dshash.h"
#include "storage/ipc.h"
#include "storage/lwlock.h"
#include "utils/dsa.h"
#include "utils/memutils.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)
 

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)
 
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)
 
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_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

◆ 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 165 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 153 of file dshash.c.

◆ BUCKET_INDEX_FOR_PARTITION

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

Definition at line 157 of file dshash.c.

◆ BUCKETS_PER_PARTITION

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

Definition at line 135 of file dshash.c.

◆ DSHASH_MAGIC

#define DSHASH_MAGIC   0x75ff6a20

Definition at line 65 of file dshash.c.

◆ DSHASH_NUM_PARTITIONS

#define DSHASH_NUM_PARTITIONS   (1 << DSHASH_NUM_PARTITIONS_LOG2)

Definition at line 62 of file dshash.c.

◆ DSHASH_NUM_PARTITIONS_LOG2

#define DSHASH_NUM_PARTITIONS_LOG2   7

Definition at line 61 of file dshash.c.

◆ ENTRY_FROM_ITEM

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

Definition at line 118 of file dshash.c.

◆ ITEM_FROM_ENTRY

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

Definition at line 122 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:135

Definition at line 139 of file dshash.c.

◆ NUM_BUCKETS

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

Definition at line 131 of file dshash.c.

◆ NUM_SPLITS

#define NUM_SPLITS (   size_log2)     (size_log2 - DSHASH_NUM_PARTITIONS_LOG2)

Definition at line 127 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 161 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 144 of file dshash.c.

◆ PARTITION_LOCK

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

Definition at line 194 of file dshash.c.

Typedef Documentation

◆ dshash_partition

◆ dshash_table_control

Function Documentation

◆ delete_item()

static void delete_item ( dshash_table hash_table,
dshash_table_item item 
)
static

Definition at line 813 of file dshash.c.

814 {
815  size_t hash = item->hash;
816  size_t partition = PARTITION_FOR_HASH(hash);
817 
818  Assert(LWLockHeldByMe(PARTITION_LOCK(hash_table, partition)));
819 
820  if (delete_item_from_bucket(hash_table, item,
821  &BUCKET_FOR_HASH(hash_table, hash)))
822  {
823  Assert(hash_table->control->partitions[partition].count > 0);
824  --hash_table->control->partitions[partition].count;
825  }
826  else
827  {
828  Assert(false);
829  }
830 }
#define PARTITION_LOCK(hash_table, i)
Definition: dshash.c:194
static bool delete_item_from_bucket(dshash_table *hash_table, dshash_table_item *item, dsa_pointer *bucket_head)
Definition: dshash.c:1014
#define PARTITION_FOR_HASH(hash)
Definition: dshash.c:144
#define BUCKET_FOR_HASH(hash_table, hash)
Definition: dshash.c:165
Assert(fmt[strlen(fmt) - 1] !='\n')
bool LWLockHeldByMe(LWLock *l)
Definition: lwlock.c:1916
size_t count
Definition: dshash.c:78
dshash_partition partitions[DSHASH_NUM_PARTITIONS]
Definition: dshash.c:89
dshash_hash hash
Definition: dshash.c:51
dshash_table_control * control
Definition: dshash.c:110

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 1014 of file dshash.c.

1017 {
1018  while (DsaPointerIsValid(*bucket_head))
1019  {
1020  dshash_table_item *bucket_item;
1021 
1022  bucket_item = dsa_get_address(hash_table->area, *bucket_head);
1023 
1024  if (bucket_item == item)
1025  {
1026  dsa_pointer next;
1027 
1028  next = item->next;
1029  dsa_free(hash_table->area, *bucket_head);
1030  *bucket_head = next;
1031  return true;
1032  }
1033  bucket_head = &bucket_item->next;
1034  }
1035  return false;
1036 }
static int32 next
Definition: blutils.c:219
void * dsa_get_address(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:932
void dsa_free(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:820
uint64 dsa_pointer
Definition: dsa.h:62
#define DsaPointerIsValid(x)
Definition: dsa.h:81
dsa_pointer next
Definition: dshash.c:49
dsa_area * area
Definition: dshash.c:107

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 985 of file dshash.c.

988 {
989  while (DsaPointerIsValid(*bucket_head))
990  {
991  dshash_table_item *item;
992 
993  item = dsa_get_address(hash_table->area, *bucket_head);
994 
995  if (equal_keys(hash_table, key, ENTRY_FROM_ITEM(item)))
996  {
998 
999  next = item->next;
1000  dsa_free(hash_table->area, *bucket_head);
1001  *bucket_head = next;
1002 
1003  return true;
1004  }
1005  bucket_head = &item->next;
1006  }
1007  return false;
1008 }
static bool equal_keys(dshash_table *hash_table, const void *a, const void *b)
Definition: dshash.c:1053
#define ENTRY_FROM_ITEM(item)
Definition: dshash.c:118

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 271 of file dshash.c.

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

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

Referenced by pgstat_attach_shmem(), and SharedRecordTypmodRegistryAttach().

◆ dshash_create()

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

Definition at line 204 of file dshash.c.

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

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::find_exclusively_locked, dshash_table::find_locked, 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 SharedRecordTypmodRegistryInit(), and StatsShmemInit().

◆ dshash_delete_current()

void dshash_delete_current ( dshash_seq_status status)

Definition at line 736 of file dshash.c.

737 {
738  dshash_table *hash_table = status->hash_table;
739  dshash_table_item *item = status->curitem;
740  size_t partition PG_USED_FOR_ASSERTS_ONLY;
741 
742  partition = PARTITION_FOR_HASH(item->hash);
743 
744  Assert(status->exclusive);
745  Assert(hash_table->control->magic == DSHASH_MAGIC);
746  Assert(hash_table->find_locked);
747  Assert(hash_table->find_exclusively_locked);
748  Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition),
749  LW_EXCLUSIVE));
750 
751  delete_item(hash_table, item);
752 }
#define PG_USED_FOR_ASSERTS_ONLY
Definition: c.h:155
static void delete_item(dshash_table *hash_table, dshash_table_item *item)
Definition: dshash.c:813
bool LWLockHeldByMeInMode(LWLock *l, LWLockMode mode)
Definition: lwlock.c:1934
@ LW_EXCLUSIVE
Definition: lwlock.h:104
static void static void status(const char *fmt,...) pg_attribute_printf(1
Definition: pg_regress.c:229

References Assert(), dshash_table::control, delete_item(), DSHASH_MAGIC, dshash_table::find_exclusively_locked, dshash_table::find_locked, dshash_table_item::hash, LW_EXCLUSIVE, LWLockHeldByMeInMode(), dshash_table_control::magic, PARTITION_FOR_HASH, PARTITION_LOCK, PG_USED_FOR_ASSERTS_ONLY, and status().

Referenced by pgstat_free_entry().

◆ dshash_delete_entry()

void dshash_delete_entry ( dshash_table hash_table,
void *  entry 
)

Definition at line 548 of file dshash.c.

549 {
550  dshash_table_item *item = ITEM_FROM_ENTRY(entry);
551  size_t partition = PARTITION_FOR_HASH(item->hash);
552 
553  Assert(hash_table->control->magic == DSHASH_MAGIC);
554  Assert(hash_table->find_locked);
555  Assert(hash_table->find_exclusively_locked);
556  Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition),
557  LW_EXCLUSIVE));
558 
559  delete_item(hash_table, item);
560  hash_table->find_locked = false;
561  hash_table->find_exclusively_locked = false;
562  LWLockRelease(PARTITION_LOCK(hash_table, partition));
563 }
#define ITEM_FROM_ENTRY(entry)
Definition: dshash.c:122
void LWLockRelease(LWLock *lock)
Definition: lwlock.c:1800

References Assert(), dshash_table::control, delete_item(), DSHASH_MAGIC, dshash_table::find_exclusively_locked, dshash_table::find_locked, 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 510 of file dshash.c.

511 {
513  size_t partition;
514  bool found;
515 
516  Assert(hash_table->control->magic == DSHASH_MAGIC);
517  Assert(!hash_table->find_locked);
518 
519  hash = hash_key(hash_table, key);
520  partition = PARTITION_FOR_HASH(hash);
521 
522  LWLockAcquire(PARTITION_LOCK(hash_table, partition), LW_EXCLUSIVE);
523  ensure_valid_bucket_pointers(hash_table);
524 
525  if (delete_key_from_bucket(hash_table, key,
526  &BUCKET_FOR_HASH(hash_table, hash)))
527  {
528  Assert(hash_table->control->partitions[partition].count > 0);
529  found = true;
530  --hash_table->control->partitions[partition].count;
531  }
532  else
533  found = false;
534 
535  LWLockRelease(PARTITION_LOCK(hash_table, partition));
536 
537  return found;
538 }
static bool delete_key_from_bucket(dshash_table *hash_table, const void *key, dsa_pointer *bucket_head)
Definition: dshash.c:985
static dshash_hash hash_key(dshash_table *hash_table, const void *key)
Definition: dshash.c:1042
static void ensure_valid_bucket_pointers(dshash_table *hash_table)
Definition: dshash.c:916
uint32 dshash_hash
Definition: dshash.h:27
bool LWLockAcquire(LWLock *lock, LWLockMode mode)
Definition: lwlock.c:1196

References Assert(), BUCKET_FOR_HASH, dshash_table::control, dshash_partition::count, delete_key_from_bucket(), DSHASH_MAGIC, ensure_valid_bucket_pointers(), dshash_table::find_locked, 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 find_or_make_matching_shared_tupledesc().

◆ dshash_destroy()

void dshash_destroy ( dshash_table hash_table)

Definition at line 326 of file dshash.c.

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

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(), and dshash_table::size_log2.

◆ dshash_detach()

void dshash_detach ( dshash_table hash_table)

Definition at line 310 of file dshash.c.

311 {
312  Assert(!hash_table->find_locked);
313 
314  /* The hash table may have been destroyed. Just free local memory. */
315  pfree(hash_table);
316 }

References Assert(), dshash_table::find_locked, 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 759 of file dshash.c.

760 {
761  size_t i;
762  size_t j;
763 
764  Assert(hash_table->control->magic == DSHASH_MAGIC);
765  Assert(!hash_table->find_locked);
766 
767  for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
768  {
769  Assert(!LWLockHeldByMe(PARTITION_LOCK(hash_table, i)));
770  LWLockAcquire(PARTITION_LOCK(hash_table, i), LW_SHARED);
771  }
772 
773  ensure_valid_bucket_pointers(hash_table);
774 
775  fprintf(stderr,
776  "hash table size = %zu\n", (size_t) 1 << hash_table->size_log2);
777  for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
778  {
779  dshash_partition *partition = &hash_table->control->partitions[i];
780  size_t begin = BUCKET_INDEX_FOR_PARTITION(i, hash_table->size_log2);
781  size_t end = BUCKET_INDEX_FOR_PARTITION(i + 1, hash_table->size_log2);
782 
783  fprintf(stderr, " partition %zu\n", i);
784  fprintf(stderr,
785  " active buckets (key count = %zu)\n", partition->count);
786 
787  for (j = begin; j < end; ++j)
788  {
789  size_t count = 0;
790  dsa_pointer bucket = hash_table->buckets[j];
791 
792  while (DsaPointerIsValid(bucket))
793  {
794  dshash_table_item *item;
795 
796  item = dsa_get_address(hash_table->area, bucket);
797 
798  bucket = item->next;
799  ++count;
800  }
801  fprintf(stderr, " bucket %zu (key count = %zu)\n", j, count);
802  }
803  }
804 
805  for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
806  LWLockRelease(PARTITION_LOCK(hash_table, i));
807 }
#define BUCKET_INDEX_FOR_PARTITION(partition, size_log2)
Definition: dshash.c:157
int j
Definition: isn.c:74
@ LW_SHARED
Definition: lwlock.h:105
#define fprintf
Definition: port.h:229

References dshash_table::area, Assert(), 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(), dshash_table::find_locked, 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 393 of file dshash.c.

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

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

Referenced by 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 438 of file dshash.c.

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

References Assert(), BUCKET_FOR_HASH, dshash_table::control, dshash_partition::count, DSHASH_MAGIC, ensure_valid_bucket_pointers(), ENTRY_FROM_ITEM, dshash_table::find_exclusively_locked, find_in_bucket(), dshash_table::find_locked, 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 find_or_make_matching_shared_tupledesc(), 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)

Definition at line 370 of file dshash.c.

371 {
372  Assert(hash_table->control->magic == DSHASH_MAGIC);
373 
374  return hash_table->control->handle;
375 }

References Assert(), dshash_table::control, DSHASH_MAGIC, dshash_table_control::handle, and dshash_table_control::magic.

Referenced by SharedRecordTypmodRegistryInit(), and StatsShmemInit().

◆ dshash_memcmp()

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

Definition at line 589 of file dshash.c.

590 {
591  return memcmp(a, b, size);
592 }
int b
Definition: isn.c:70
int a
Definition: isn.c:69

References a, and b.

◆ dshash_memhash()

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

Definition at line 598 of file dshash.c.

599 {
600  return tag_hash(v, size);
601 }
uint32 tag_hash(const void *key, Size keysize)
Definition: hashfn.c:677

References tag_hash().

◆ dshash_release_lock()

◆ dshash_seq_init()

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

Definition at line 612 of file dshash.c.

614 {
615  status->hash_table = hash_table;
616  status->curbucket = 0;
617  status->nbuckets = 0;
618  status->curitem = NULL;
619  status->pnextitem = InvalidDsaPointer;
620  status->curpartition = -1;
621  status->exclusive = exclusive;
622 }
#define InvalidDsaPointer
Definition: dsa.h:78

References InvalidDsaPointer, and status().

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

◆ dshash_seq_next()

void* dshash_seq_next ( dshash_seq_status status)

Definition at line 631 of file dshash.c.

632 {
633  dsa_pointer next_item_pointer;
634 
635  /*
636  * Not yet holding any partition locks. Need to determine the size of the
637  * hash table, it could have been resized since we were looking last.
638  * Since we iterate in partition order, we can start by unconditionally
639  * lock partition 0.
640  *
641  * Once we hold the lock, no resizing can happen until the scan ends. So
642  * we don't need to repeatedly call ensure_valid_bucket_pointers().
643  */
644  if (status->curpartition == -1)
645  {
646  Assert(status->curbucket == 0);
647  Assert(!status->hash_table->find_locked);
648 
649  status->curpartition = 0;
650 
651  LWLockAcquire(PARTITION_LOCK(status->hash_table,
652  status->curpartition),
653  status->exclusive ? LW_EXCLUSIVE : LW_SHARED);
654 
656 
657  status->nbuckets =
658  NUM_BUCKETS(status->hash_table->control->size_log2);
659  next_item_pointer = status->hash_table->buckets[status->curbucket];
660  }
661  else
662  next_item_pointer = status->pnextitem;
663 
665  status->curpartition),
666  status->exclusive ? LW_EXCLUSIVE : LW_SHARED));
667 
668  /* Move to the next bucket if we finished the current bucket */
669  while (!DsaPointerIsValid(next_item_pointer))
670  {
671  int next_partition;
672 
673  if (++status->curbucket >= status->nbuckets)
674  {
675  /* all buckets have been scanned. finish. */
676  return NULL;
677  }
678 
679  /* Check if move to the next partition */
680  next_partition =
682  status->hash_table->size_log2);
683 
684  if (status->curpartition != next_partition)
685  {
686  /*
687  * Move to the next partition. Lock the next partition then
688  * release the current, not in the reverse order to avoid
689  * concurrent resizing. Avoid dead lock by taking lock in the
690  * same order with resize().
691  */
692  LWLockAcquire(PARTITION_LOCK(status->hash_table,
693  next_partition),
694  status->exclusive ? LW_EXCLUSIVE : LW_SHARED);
695  LWLockRelease(PARTITION_LOCK(status->hash_table,
696  status->curpartition));
697  status->curpartition = next_partition;
698  }
699 
700  next_item_pointer = status->hash_table->buckets[status->curbucket];
701  }
702 
703  status->curitem =
704  dsa_get_address(status->hash_table->area, next_item_pointer);
705  status->hash_table->find_locked = true;
706  status->hash_table->find_exclusively_locked = status->exclusive;
707 
708  /*
709  * The caller may delete the item. Store the next item in case of
710  * deletion.
711  */
712  status->pnextitem = status->curitem->next;
713 
714  return ENTRY_FROM_ITEM(status->curitem);
715 }
#define PARTITION_FOR_BUCKET_INDEX(bucket_idx, size_log2)
Definition: dshash.c:161

References Assert(), dsa_get_address(), DsaPointerIsValid, ensure_valid_bucket_pointers(), ENTRY_FROM_ITEM, LW_EXCLUSIVE, LW_SHARED, LWLockAcquire(), LWLockHeldByMeInMode(), LWLockRelease(), NUM_BUCKETS, PARTITION_FOR_BUCKET_INDEX, PARTITION_LOCK, and status().

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()

void dshash_seq_term ( dshash_seq_status status)

Definition at line 723 of file dshash.c.

724 {
725  status->hash_table->find_locked = false;
726  status->hash_table->find_exclusively_locked = false;
727 
728  if (status->curpartition >= 0)
729  LWLockRelease(PARTITION_LOCK(status->hash_table, status->curpartition));
730 }

References LWLockRelease(), PARTITION_LOCK, and status().

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

◆ ensure_valid_bucket_pointers()

static void ensure_valid_bucket_pointers ( dshash_table hash_table)
inlinestatic

Definition at line 916 of file dshash.c.

917 {
918  if (hash_table->size_log2 != hash_table->control->size_log2)
919  {
920  hash_table->buckets = dsa_get_address(hash_table->area,
921  hash_table->control->buckets);
922  hash_table->size_log2 = hash_table->control->size_log2;
923  }
924 }

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 1053 of file dshash.c.

1054 {
1055  return hash_table->params.compare_function(a, b,
1056  hash_table->params.key_size,
1057  hash_table->arg) == 0;
1058 }
size_t key_size
Definition: dshash.h:51
dshash_compare_function compare_function
Definition: dshash.h:53

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 930 of file dshash.c.

932 {
933  while (DsaPointerIsValid(item_pointer))
934  {
935  dshash_table_item *item;
936 
937  item = dsa_get_address(hash_table->area, item_pointer);
938  if (equal_keys(hash_table, key, ENTRY_FROM_ITEM(item)))
939  return item;
940  item_pointer = item->next;
941  }
942  return NULL;
943 }

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 1042 of file dshash.c.

1043 {
1044  return hash_table->params.hash_function(key,
1045  hash_table->params.key_size,
1046  hash_table->arg);
1047 }
dshash_hash_function hash_function
Definition: dshash.h:54

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 965 of file dshash.c.

968 {
969  dsa_pointer item_pointer;
970  dshash_table_item *item;
971 
972  item_pointer = dsa_allocate(hash_table->area,
973  hash_table->params.entry_size +
974  MAXALIGN(sizeof(dshash_table_item)));
975  item = dsa_get_address(hash_table->area, item_pointer);
976  memcpy(ENTRY_FROM_ITEM(item), key, hash_table->params.key_size);
977  insert_item_into_bucket(hash_table, item_pointer, item, bucket);
978  return item;
979 }
static void insert_item_into_bucket(dshash_table *hash_table, dsa_pointer item_pointer, dshash_table_item *item, dsa_pointer *bucket)
Definition: dshash.c:949
size_t entry_size
Definition: dshash.h:52

References dshash_table::area, dsa_allocate, dsa_get_address(), ENTRY_FROM_ITEM, dshash_parameters::entry_size, insert_item_into_bucket(), sort-test::key, dshash_parameters::key_size, 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 949 of file dshash.c.

953 {
954  Assert(item == dsa_get_address(hash_table->area, item_pointer));
955 
956  item->next = *bucket;
957  *bucket = item_pointer;
958 }

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 
)
static

Definition at line 839 of file dshash.c.

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

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, and dshash_table_control::size_log2.

Referenced by dshash_find_or_insert().