dshash.c File Reference

#include "postgres.h"
#include <limits.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_item *	find_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_item *	insert_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_table *	dshash_create (dsa_area *area, const dshash_parameters *params, void *arg)
dshash_table *	dshash_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, \
           DSHASH_NUM_PARTITIONS, sizeof(dshash_partition)))

Definition at line 197 of file dshash.c.

{
    dshash_table *hash_table;
    dsa_pointer control;
 
    /* Allocate the backend-local object representing the hash table. */
    hash_table = palloc_object(dshash_table);
 
    /* Allocate the control object in shared memory. */
    control = dsa_allocate(area, sizeof(dshash_table_control));
 
    /* Set up the local and shared hash table structs. */
    hash_table->area = area;
    hash_table->params = *params;
    hash_table->arg = arg;
    hash_table->control = dsa_get_address(area, control);
    hash_table->control->handle = control;
    hash_table->control->magic = DSHASH_MAGIC;
    hash_table->control->lwlock_tranche_id = params->tranche_id;
 
    /* Set up the array of lock partitions. */
    {
        dshash_partition *partitions = hash_table->control->partitions;
        int         tranche_id = hash_table->control->lwlock_tranche_id;
        int         i;
 
        for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
        {
            LWLockInitialize(&partitions[i].lock, tranche_id);
            partitions[i].count = 0;
        }
    }
 
    /*
     * Set up the initial array of buckets.  Our initial size is the same as
     * the number of partitions.
     */
    hash_table->control->size_log2 = DSHASH_NUM_PARTITIONS_LOG2;
    hash_table->control->buckets =
        dsa_allocate_extended(area,
                              sizeof(dsa_pointer) * DSHASH_NUM_PARTITIONS,
                              DSA_ALLOC_NO_OOM | DSA_ALLOC_ZERO);
    if (!DsaPointerIsValid(hash_table->control->buckets))
    {
        dsa_free(area, control);
        ereport(ERROR,
                (errcode(ERRCODE_OUT_OF_MEMORY),
                 errmsg("out of memory"),
                 errdetail("Failed on DSA request of size %zu.",
                           sizeof(dsa_pointer) * DSHASH_NUM_PARTITIONS)));
    }
    hash_table->buckets = dsa_get_address(area,
                                          hash_table->control->buckets);
    hash_table->size_log2 = hash_table->control->size_log2;
 
    return hash_table;
}
 
/*
 * Attach to an existing hash table using a handle.  The returned object is
 * allocated in backend-local memory using the current MemoryContext.  'arg'
 * will be passed through to the compare and hash functions.
 */
dshash_table *
dshash_attach(dsa_area *area, const dshash_parameters *params,
              dshash_table_handle handle, void *arg)
{
    dshash_table *hash_table;
    dsa_pointer control;
 
    /* Allocate the backend-local object representing the hash table. */
    hash_table = palloc_object(dshash_table);
 
    /* Find the control object in shared memory. */
    control = handle;
 
    /* Set up the local hash table struct. */
    hash_table->area = area;
    hash_table->params = *params;
    hash_table->arg = arg;
    hash_table->control = dsa_get_address(area, control);
    Assert(hash_table->control->magic == DSHASH_MAGIC);
 
    /*
     * These will later be set to the correct values by
     * ensure_valid_bucket_pointers(), at which time we'll be holding a
     * partition lock for interlocking against concurrent resizing.
     */
    hash_table->buckets = NULL;
    hash_table->size_log2 = 0;
 
    return hash_table;
}
 
/*
 * Detach from a hash table.  This frees backend-local resources associated
 * with the hash table, but the hash table will continue to exist until it is
 * either explicitly destroyed (by a backend that is still attached to it), or
 * the area that backs it is returned to the operating system.
 */
void
dshash_detach(dshash_table *hash_table)
{
    ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
 
    /* The hash table may have been destroyed.  Just free local memory. */
    pfree(hash_table);
}
 
/*
 * Destroy a hash table, returning all memory to the area.  The caller must be
 * certain that no other backend will attempt to access the hash table before
 * calling this function.  Other backend must explicitly call dshash_detach to
 * free up backend-local memory associated with the hash table.  The backend
 * that calls dshash_destroy must not call dshash_detach.
 */
void
dshash_destroy(dshash_table *hash_table)
{
    size_t      size;
    size_t      i;
 
    Assert(hash_table->control->magic == DSHASH_MAGIC);
    ensure_valid_bucket_pointers(hash_table);
 
    /* Free all the entries. */
    size = NUM_BUCKETS(hash_table->size_log2);
    for (i = 0; i < size; ++i)
    {
        dsa_pointer item_pointer = hash_table->buckets[i];
 
        while (DsaPointerIsValid(item_pointer))
        {
            dshash_table_item *item;
            dsa_pointer next_item_pointer;
 
            item = dsa_get_address(hash_table->area, item_pointer);
            next_item_pointer = item->next;
            dsa_free(hash_table->area, item_pointer);
            item_pointer = next_item_pointer;
        }
    }
 
    /*
     * Vandalize the control block to help catch programming errors where
     * other backends access the memory formerly occupied by this hash table.
     */
    hash_table->control->magic = 0;
 
    /* Free the active table and control object. */
    dsa_free(hash_table->area, hash_table->control->buckets);
    dsa_free(hash_table->area, hash_table->control->handle);
 
    pfree(hash_table);
}
 
/*
 * Get a handle that can be used by other processes to attach to this hash
 * table.
 */
dshash_table_handle
dshash_get_hash_table_handle(dshash_table *hash_table)
{
    Assert(hash_table->control->magic == DSHASH_MAGIC);
 
    return hash_table->control->handle;
}
 
/*
 * Look up an entry, given a key.  Returns a pointer to an entry if one can be
 * found with the given key.  Returns NULL if the key is not found.  If a
 * non-NULL value is returned, the entry is locked and must be released by
 * calling dshash_release_lock.  If an error is raised before
 * dshash_release_lock is called, the lock will be released automatically, but
 * the caller must take care to ensure that the entry is not left corrupted.
 * The lock mode is either shared or exclusive depending on 'exclusive'.
 *
 * The caller must not hold a lock already.
 *
 * Note that the lock held is in fact an LWLock, so interrupts will be held on
 * return from this function, and not resumed until dshash_release_lock is
 * called.  It is a very good idea for the caller to release the lock quickly.
 */
void *
dshash_find(dshash_table *hash_table, const void *key, bool exclusive)
{
    dshash_hash hash;
    size_t      partition;
    dshash_table_item *item;
 
    hash = hash_key(hash_table, key);
    partition = PARTITION_FOR_HASH(hash);
 
    Assert(hash_table->control->magic == DSHASH_MAGIC);
    ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
 
    LWLockAcquire(PARTITION_LOCK(hash_table, partition),
                  exclusive ? LW_EXCLUSIVE : LW_SHARED);
    ensure_valid_bucket_pointers(hash_table);
 
    /* Search the active bucket. */
    item = find_in_bucket(hash_table, key, BUCKET_FOR_HASH(hash_table, hash));
 
    if (!item)
    {
        /* Not found. */
        LWLockRelease(PARTITION_LOCK(hash_table, partition));
        return NULL;
    }
    else
    {
        /* The caller will free the lock by calling dshash_release_lock. */
        return ENTRY_FROM_ITEM(item);
    }
}
 
/*
 * Returns a pointer to an exclusively locked item which must be released with
 * dshash_release_lock.  If the key is found in the hash table, 'found' is set
 * to true and a pointer to the existing entry is returned.  If the key is not
 * found, 'found' is set to false, and a pointer to a newly created entry is
 * returned.
 *
 * Notes above dshash_find() regarding locking and error handling equally
 * apply here.
 */
void *
dshash_find_or_insert(dshash_table *hash_table,
                      const void *key,
                      bool *found)
{
    dshash_hash hash;
    size_t      partition_index;
    dshash_partition *partition;
    dshash_table_item *item;
 
    hash = hash_key(hash_table, key);
    partition_index = PARTITION_FOR_HASH(hash);
    partition = &hash_table->control->partitions[partition_index];
 
    Assert(hash_table->control->magic == DSHASH_MAGIC);
    ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
 
restart:
    LWLockAcquire(PARTITION_LOCK(hash_table, partition_index),
                  LW_EXCLUSIVE);
    ensure_valid_bucket_pointers(hash_table);
 
    /* Search the active bucket. */
    item = find_in_bucket(hash_table, key, BUCKET_FOR_HASH(hash_table, hash));
 
    if (item)
        *found = true;
    else
    {
        *found = false;
 
        /* Check if we are getting too full. */
        if (partition->count > MAX_COUNT_PER_PARTITION(hash_table))
        {
            /*
             * The load factor (= keys / buckets) for all buckets protected by
             * this partition is > 0.75.  Presumably the same applies
             * generally across the whole hash table (though we don't attempt
             * to track that directly to avoid contention on some kind of
             * central counter; we just assume that this partition is
             * representative).  This is a good time to resize.
             *
             * Give up our existing lock first, because resizing needs to
             * reacquire all the locks in the right order to avoid deadlocks.
             */
            LWLockRelease(PARTITION_LOCK(hash_table, partition_index));
            resize(hash_table, hash_table->size_log2 + 1);
 
            goto restart;
        }
 
        /* Finally we can try to insert the new item. */
        item = insert_into_bucket(hash_table, key,
                                  &BUCKET_FOR_HASH(hash_table, hash));
        item->hash = hash;
        /* Adjust per-lock-partition counter for load factor knowledge. */
        ++partition->count;
    }
 
    /* The caller must release the lock with dshash_release_lock. */
    return ENTRY_FROM_ITEM(item);
}
 
/*
 * Remove an entry by key.  Returns true if the key was found and the
 * corresponding entry was removed.
 *
 * To delete an entry that you already have a pointer to, see
 * dshash_delete_entry.
 */
bool
dshash_delete_key(dshash_table *hash_table, const void *key)
{
    dshash_hash hash;
    size_t      partition;
    bool        found;
 
    Assert(hash_table->control->magic == DSHASH_MAGIC);
    ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
 
    hash = hash_key(hash_table, key);
    partition = PARTITION_FOR_HASH(hash);
 
    LWLockAcquire(PARTITION_LOCK(hash_table, partition), LW_EXCLUSIVE);
    ensure_valid_bucket_pointers(hash_table);
 
    if (delete_key_from_bucket(hash_table, key,
                               &BUCKET_FOR_HASH(hash_table, hash)))
    {
        Assert(hash_table->control->partitions[partition].count > 0);
        found = true;
        --hash_table->control->partitions[partition].count;
    }
    else
        found = false;
 
    LWLockRelease(PARTITION_LOCK(hash_table, partition));
 
    return found;
}
 
/*
 * Remove an entry.  The entry must already be exclusively locked, and must
 * have been obtained by dshash_find or dshash_find_or_insert.  Note that this
 * function releases the lock just like dshash_release_lock.
 *
 * To delete an entry by key, see dshash_delete_key.
 */
void
dshash_delete_entry(dshash_table *hash_table, void *entry)
{
    dshash_table_item *item = ITEM_FROM_ENTRY(entry);
    size_t      partition = PARTITION_FOR_HASH(item->hash);
 
    Assert(hash_table->control->magic == DSHASH_MAGIC);
    Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition),
                                LW_EXCLUSIVE));
 
    delete_item(hash_table, item);
    LWLockRelease(PARTITION_LOCK(hash_table, partition));
}
 
/*
 * Unlock an entry which was locked by dshash_find or dshash_find_or_insert.
 */
void
dshash_release_lock(dshash_table *hash_table, void *entry)
{
    dshash_table_item *item = ITEM_FROM_ENTRY(entry);
    size_t      partition_index = PARTITION_FOR_HASH(item->hash);
 
    Assert(hash_table->control->magic == DSHASH_MAGIC);
 
    LWLockRelease(PARTITION_LOCK(hash_table, partition_index));
}
 
/*
 * A compare function that forwards to memcmp.
 */
int
dshash_memcmp(const void *a, const void *b, size_t size, void *arg)
{
    return memcmp(a, b, size);
}
 
/*
 * A hash function that forwards to tag_hash.
 */
dshash_hash
dshash_memhash(const void *v, size_t size, void *arg)
{
    return tag_hash(v, size);
}
 
/*
 * A copy function that forwards to memcpy.
 */
void
dshash_memcpy(void *dest, const void *src, size_t size, void *arg)
{
    (void) memcpy(dest, src, size);
}
 
/*
 * A compare function that forwards to strcmp.
 */
int
dshash_strcmp(const void *a, const void *b, size_t size, void *arg)
{
    Assert(strlen((const char *) a) < size);
    Assert(strlen((const char *) b) < size);
 
    return strcmp((const char *) a, (const char *) b);
}
 
/*
 * A hash function that forwards to string_hash.
 */
dshash_hash
dshash_strhash(const void *v, size_t size, void *arg)
{
    Assert(strlen((const char *) v) < size);
 
    return string_hash((const char *) v, size);
}
 
/*
 * A copy function that forwards to strcpy.
 */
void
dshash_strcpy(void *dest, const void *src, size_t size, void *arg)
{
    Assert(strlen((const char *) src) < size);
 
    (void) strcpy((char *) dest, (const char *) src);
}
 
/*
 * Sequentially scan through dshash table and return all the elements one by
 * one, return NULL when all elements have been returned.
 *
 * dshash_seq_term needs to be called when a scan finished.  The caller may
 * delete returned elements midst of a scan by using dshash_delete_current()
 * if exclusive = true.
 */
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 may not release the lock. It is
 * released by future calls to dshash_seq_next() or dshash_seq_term().
 */
void *
dshash_seq_next(dshash_seq_status *status)
{
    dsa_pointer next_item_pointer;
 
    /*
     * Not yet holding any partition locks. Need to determine the size of the
     * hash table, it could have been resized since we were looking last.
     * Since we iterate in partition order, we can start by unconditionally
     * lock partition 0.
     *
     * Once we hold the lock, no resizing can happen until the scan ends. So
     * we don't need to repeatedly call ensure_valid_bucket_pointers().
     */
    if (status->curpartition == -1)
    {
        Assert(status->curbucket == 0);
        ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(status->hash_table);
 
        status->curpartition = 0;
 
        LWLockAcquire(PARTITION_LOCK(status->hash_table,
                                     status->curpartition),
                      status->exclusive ? LW_EXCLUSIVE : LW_SHARED);
 
        ensure_valid_bucket_pointers(status->hash_table);
 
        status->nbuckets =
            NUM_BUCKETS(status->hash_table->control->size_log2);
        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);
 
    /*
     * 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.
 *
 * Needs to be called after finishing or when exiting a seqscan.
 */
void
dshash_seq_term(dshash_seq_status *status)
{
    if (status->curpartition >= 0)
        LWLockRelease(PARTITION_LOCK(status->hash_table, status->curpartition));
}
 
/*
 * Remove the current entry of the 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 PG_USED_FOR_ASSERTS_ONLY;
 
    partition = PARTITION_FOR_HASH(item->hash);
 
    Assert(status->exclusive);
    Assert(hash_table->control->magic == DSHASH_MAGIC);
    Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition),
                                LW_EXCLUSIVE));
 
    delete_item(hash_table, item);
}
 
/*
 * Print debugging information about the internal state of the hash table to
 * stderr.  The caller must hold no partition locks.
 */
void
dshash_dump(dshash_table *hash_table)
{
    size_t      i;
    size_t      j;
 
    Assert(hash_table->control->magic == DSHASH_MAGIC);
    ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
 
    for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
    {
        Assert(!LWLockHeldByMe(PARTITION_LOCK(hash_table, i)));
        LWLockAcquire(PARTITION_LOCK(hash_table, i), LW_SHARED);
    }
 
    ensure_valid_bucket_pointers(hash_table);
 
    fprintf(stderr,
            "hash table size = %zu\n", (size_t) 1 << hash_table->size_log2);
    for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
    {
        dshash_partition *partition = &hash_table->control->partitions[i];
        size_t      begin = BUCKET_INDEX_FOR_PARTITION(i, hash_table->size_log2);
        size_t      end = BUCKET_INDEX_FOR_PARTITION(i + 1, hash_table->size_log2);
 
        fprintf(stderr, "  partition %zu\n", i);
        fprintf(stderr,
                "    active buckets (key count = %zu)\n", partition->count);
 
        for (j = begin; j < end; ++j)
        {
            size_t      count = 0;
            dsa_pointer bucket = hash_table->buckets[j];
 
            while (DsaPointerIsValid(bucket))
            {
                dshash_table_item *item;
 
                item = dsa_get_address(hash_table->area, bucket);
 
                bucket = item->next;
                ++count;
            }
            fprintf(stderr, "      bucket %zu (key count = %zu)\n", j, count);
        }
    }
 
    for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
        LWLockRelease(PARTITION_LOCK(hash_table, i));
}
 
/*
 * Delete a locked item to which we have a pointer.
 */
static void
delete_item(dshash_table *hash_table, dshash_table_item *item)
{
    size_t      hash = item->hash;
    size_t      partition = PARTITION_FOR_HASH(hash);
 
    Assert(LWLockHeldByMe(PARTITION_LOCK(hash_table, partition)));
 
    if (delete_item_from_bucket(hash_table, item,
                                &BUCKET_FOR_HASH(hash_table, hash)))
    {
        Assert(hash_table->control->partitions[partition].count > 0);
        --hash_table->control->partitions[partition].count;
    }
    else
    {
        Assert(false);
    }
}
 
/*
 * Grow the hash table if necessary to the requested number of buckets.  The
 * requested size must be double some previously observed size.
 *
 * Must be called without any partition lock held.
 */
static void
resize(dshash_table *hash_table, size_t new_size_log2)
{
    dsa_pointer old_buckets;
    dsa_pointer new_buckets_shared;
    dsa_pointer *new_buckets;
    size_t      size;
    size_t      new_size = ((size_t) 1) << new_size_log2;
    size_t      i;
 
    /*
     * Acquire the locks for all lock partitions.  This is expensive, but we
     * shouldn't have to do it many times.
     */
    for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
    {
        Assert(!LWLockHeldByMe(PARTITION_LOCK(hash_table, i)));
 
        LWLockAcquire(PARTITION_LOCK(hash_table, i), LW_EXCLUSIVE);
        if (i == 0 && hash_table->control->size_log2 >= new_size_log2)
        {
            /*
             * Another backend has already increased the size; we can avoid
             * obtaining all the locks and return early.
             */
            LWLockRelease(PARTITION_LOCK(hash_table, 0));
            return;
        }
    }
 
    Assert(new_size_log2 == hash_table->control->size_log2 + 1);
 
    /* Allocate the space for the new table. */
    new_buckets_shared =
        dsa_allocate_extended(hash_table->area,
                              sizeof(dsa_pointer) * new_size,
                              DSA_ALLOC_HUGE | DSA_ALLOC_ZERO);
    new_buckets = dsa_get_address(hash_table->area, new_buckets_shared);
 
    /*
     * We've allocated the new bucket array; all that remains to do now is to
     * reinsert all items, which amounts to adjusting all the pointers.
     */
    size = ((size_t) 1) << hash_table->control->size_log2;
    for (i = 0; i < size; ++i)
    {
        dsa_pointer item_pointer = hash_table->buckets[i];
 
        while (DsaPointerIsValid(item_pointer))
        {
            dshash_table_item *item;
            dsa_pointer next_item_pointer;
 
            item = dsa_get_address(hash_table->area, item_pointer);
            next_item_pointer = item->next;
            insert_item_into_bucket(hash_table, item_pointer, item,
                                    &new_buckets[BUCKET_INDEX_FOR_HASH_AND_SIZE(item->hash,
                                                                                new_size_log2)]);
            item_pointer = next_item_pointer;
        }
    }
 
    /* Swap the hash table into place and free the old one. */
    old_buckets = hash_table->control->buckets;
    hash_table->control->buckets = new_buckets_shared;
    hash_table->control->size_log2 = new_size_log2;
    hash_table->buckets = new_buckets;
    dsa_free(hash_table->area, old_buckets);
 
    /* Release all the locks. */
    for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
        LWLockRelease(PARTITION_LOCK(hash_table, i));
}
 
/*
 * Make sure that our backend-local bucket pointers are up to date.  The
 * caller must have locked one lock partition, which prevents resize() from
 * running concurrently.
 */
static inline void
ensure_valid_bucket_pointers(dshash_table *hash_table)
{
    if (hash_table->size_log2 != hash_table->control->size_log2)
    {
        hash_table->buckets = dsa_get_address(hash_table->area,
                                              hash_table->control->buckets);
        hash_table->size_log2 = hash_table->control->size_log2;
    }
}
 
/*
 * Scan a locked bucket for a match, using the provided compare function.
 */
static inline dshash_table_item *
find_in_bucket(dshash_table *hash_table, const void *key,
               dsa_pointer item_pointer)
{
    while (DsaPointerIsValid(item_pointer))
    {
        dshash_table_item *item;
 
        item = dsa_get_address(hash_table->area, item_pointer);
        if (equal_keys(hash_table, key, ENTRY_FROM_ITEM(item)))
            return item;
        item_pointer = item->next;
    }
    return NULL;
}
 
/*
 * Insert an already-allocated item into a bucket.
 */
static void
insert_item_into_bucket(dshash_table *hash_table,
                        dsa_pointer item_pointer,
                        dshash_table_item *item,
                        dsa_pointer *bucket)
{
    Assert(item == dsa_get_address(hash_table->area, item_pointer));
 
    item->next = *bucket;
    *bucket = item_pointer;
}
 
/*
 * Allocate space for an entry with the given key and insert it into the
 * provided bucket.
 */
static dshash_table_item *
insert_into_bucket(dshash_table *hash_table,
                   const void *key,
                   dsa_pointer *bucket)
{
    dsa_pointer item_pointer;
    dshash_table_item *item;
 
    item_pointer = dsa_allocate(hash_table->area,
                                hash_table->params.entry_size +
                                MAXALIGN(sizeof(dshash_table_item)));
    item = dsa_get_address(hash_table->area, item_pointer);
    copy_key(hash_table, ENTRY_FROM_ITEM(item), key);
    insert_item_into_bucket(hash_table, item_pointer, item, bucket);
    return item;
}
 
/*
 * Search a bucket for a matching key and delete it.
 */
static bool
delete_key_from_bucket(dshash_table *hash_table,
                       const void *key,
                       dsa_pointer *bucket_head)
{
    while (DsaPointerIsValid(*bucket_head))
    {
        dshash_table_item *item;
 
        item = dsa_get_address(hash_table->area, *bucket_head);
 
        if (equal_keys(hash_table, key, ENTRY_FROM_ITEM(item)))
        {
            dsa_pointer next;
 
            next = item->next;
            dsa_free(hash_table->area, *bucket_head);
            *bucket_head = next;
 
            return true;
        }
        bucket_head = &item->next;
    }
    return false;
}
 
/*
 * Delete the specified item from the bucket.
 */
static bool
delete_item_from_bucket(dshash_table *hash_table,
                        dshash_table_item *item,
                        dsa_pointer *bucket_head)
{
    while (DsaPointerIsValid(*bucket_head))
    {
        dshash_table_item *bucket_item;
 
        bucket_item = dsa_get_address(hash_table->area, *bucket_head);
 
        if (bucket_item == item)
        {
            dsa_pointer next;
 
            next = item->next;
            dsa_free(hash_table->area, *bucket_head);
            *bucket_head = next;
            return true;
        }
        bucket_head = &bucket_item->next;
    }
    return false;
}
 
/*
 * Compute the hash value for a key.
 */
static inline dshash_hash
hash_key(dshash_table *hash_table, const void *key)
{
    return hash_table->params.hash_function(key,
                                            hash_table->params.key_size,
                                            hash_table->arg);
}
 
/*
 * Check whether two keys compare equal.
 */
static inline bool
equal_keys(dshash_table *hash_table, const void *a, const void *b)
{
    return hash_table->params.compare_function(a, b,
                                               hash_table->params.key_size,
                                               hash_table->arg) == 0;
}
 
/*
 * Copy a key.
 */
static inline void
copy_key(dshash_table *hash_table, void *dest, const void *src)
{
    hash_table->params.copy_function(dest, src,
                                     hash_table->params.key_size,
                                     hash_table->arg);
}

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

Definition at line 163 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 151 of file dshash.c.

BUCKET_INDEX_FOR_PARTITION

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

Definition at line 155 of file dshash.c.

BUCKETS_PER_PARTITION

#define BUCKETS_PER_PARTITION

(

size_log2

)

(((size_t) 1) << NUM_SPLITS(size_log2))

Definition at line 133 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 116 of file dshash.c.

ITEM_FROM_ENTRY

#define ITEM_FROM_ENTRY

(

entry

)

Value:

    ((dshash_table_item *)((char *)(entry) -                            \
                             MAXALIGN(sizeof(dshash_table_item))))

Definition at line 120 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)

Definition at line 137 of file dshash.c.

NUM_BUCKETS

#define NUM_BUCKETS

(

size_log2

)

(((size_t) 1) << (size_log2))

Definition at line 129 of file dshash.c.

NUM_SPLITS

#define NUM_SPLITS

(

size_log2

)

(size_log2 - DSHASH_NUM_PARTITIONS_LOG2)

Definition at line 125 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 159 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 142 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

typedef struct dshash_partition dshash_partition

dshash_table_control

typedef struct dshash_table_control dshash_table_control

Function Documentation

copy_key()

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

inlinestatic

Definition at line 1087 of file dshash.c.

{
    hash_table->params.copy_function(dest, src,
                                     hash_table->params.key_size,
                                     hash_table->arg);
}

References dshash_table::arg, dshash_parameters::copy_function, 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 834 of file dshash.c.

{
    size_t      hash = item->hash;
    size_t      partition = PARTITION_FOR_HASH(hash);
 
    Assert(LWLockHeldByMe(PARTITION_LOCK(hash_table, partition)));
 
    if (delete_item_from_bucket(hash_table, item,
                                &BUCKET_FOR_HASH(hash_table, hash)))
    {
        Assert(hash_table->control->partitions[partition].count > 0);
        --hash_table->control->partitions[partition].count;
    }
    else
    {
        Assert(false);
    }
}

References Assert, BUCKET_FOR_HASH, dshash_table::control, dshash_partition::count, delete_item_from_bucket(), fb(), 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 1037 of file dshash.c.

{
    while (DsaPointerIsValid(*bucket_head))
    {
        dshash_table_item *bucket_item;
 
        bucket_item = dsa_get_address(hash_table->area, *bucket_head);
 
        if (bucket_item == item)
        {
            dsa_pointer next;
 
            next = item->next;
            dsa_free(hash_table->area, *bucket_head);
            *bucket_head = next;
            return true;
        }
        bucket_head = &bucket_item->next;
    }
    return false;
}

References dshash_table::area, dsa_free(), dsa_get_address(), DsaPointerIsValid, fb(), 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 1008 of file dshash.c.

{
    while (DsaPointerIsValid(*bucket_head))
    {
        dshash_table_item *item;
 
        item = dsa_get_address(hash_table->area, *bucket_head);
 
        if (equal_keys(hash_table, key, ENTRY_FROM_ITEM(item)))
        {
            dsa_pointer next;
 
            next = item->next;
            dsa_free(hash_table->area, *bucket_head);
            *bucket_head = next;
 
            return true;
        }
        bucket_head = &item->next;
    }
    return false;
}

References dshash_table::area, dsa_free(), dsa_get_address(), DsaPointerIsValid, ENTRY_FROM_ITEM, equal_keys(), fb(), 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 272 of file dshash.c.

{
    dshash_table *hash_table;
    dsa_pointer control;
 
    /* Allocate the backend-local object representing the hash table. */
    hash_table = palloc_object(dshash_table);
 
    /* Find the control object in shared memory. */
    control = handle;
 
    /* Set up the local hash table struct. */
    hash_table->area = area;
    hash_table->params = *params;
    hash_table->arg = arg;
    hash_table->control = dsa_get_address(area, control);
    Assert(hash_table->control->magic == DSHASH_MAGIC);
 
    /*
     * These will later be set to the correct values by
     * ensure_valid_bucket_pointers(), at which time we'll be holding a
     * partition lock for interlocking against concurrent resizing.
     */
    hash_table->buckets = NULL;
    hash_table->size_log2 = 0;
 
    return hash_table;
}

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

Referenced by GetNamedDSHash(), init_dsm_registry(), initGlobalChannelTable(), 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 208 of file dshash.c.

{
    dshash_table *hash_table;
    dsa_pointer control;
 
    /* Allocate the backend-local object representing the hash table. */
    hash_table = palloc_object(dshash_table);
 
    /* Allocate the control object in shared memory. */
    control = dsa_allocate(area, sizeof(dshash_table_control));
 
    /* Set up the local and shared hash table structs. */
    hash_table->area = area;
    hash_table->params = *params;
    hash_table->arg = arg;
    hash_table->control = dsa_get_address(area, control);
    hash_table->control->handle = control;
    hash_table->control->magic = DSHASH_MAGIC;
    hash_table->control->lwlock_tranche_id = params->tranche_id;
 
    /* Set up the array of lock partitions. */
    {
        dshash_partition *partitions = hash_table->control->partitions;
        int         tranche_id = hash_table->control->lwlock_tranche_id;
        int         i;
 
        for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
        {
            LWLockInitialize(&partitions[i].lock, tranche_id);
            partitions[i].count = 0;
        }
    }
 
    /*
     * Set up the initial array of buckets.  Our initial size is the same as
     * the number of partitions.
     */
    hash_table->control->size_log2 = DSHASH_NUM_PARTITIONS_LOG2;
    hash_table->control->buckets =
        dsa_allocate_extended(area,
                              sizeof(dsa_pointer) * DSHASH_NUM_PARTITIONS,
                              DSA_ALLOC_NO_OOM | DSA_ALLOC_ZERO);
    if (!DsaPointerIsValid(hash_table->control->buckets))
    {
        dsa_free(area, control);
        ereport(ERROR,
                (errcode(ERRCODE_OUT_OF_MEMORY),
                 errmsg("out of memory"),
                 errdetail("Failed on DSA request of size %zu.",
                           sizeof(dsa_pointer) * DSHASH_NUM_PARTITIONS)));
    }
    hash_table->buckets = dsa_get_address(area,
                                          hash_table->control->buckets);
    hash_table->size_log2 = hash_table->control->size_log2;
 
    return hash_table;
}

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, fb(), dshash_table_control::handle, i, dshash_table_control::lwlock_tranche_id, LWLockInitialize(), dshash_table_control::magic, palloc_object, dshash_table::params, dshash_table_control::partitions, partitions, dshash_table_control::size_log2, dshash_table::size_log2, and dshash_parameters::tranche_id.

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

dshash_delete_current()

void dshash_delete_current

(

dshash_seq_status *

status

)

Definition at line 759 of file dshash.c.

{
    dshash_table *hash_table = status->hash_table;
    dshash_table_item *item = status->curitem;
    size_t      partition PG_USED_FOR_ASSERTS_ONLY;
 
    partition = PARTITION_FOR_HASH(item->hash);
 
    Assert(status->exclusive);
    Assert(hash_table->control->magic == DSHASH_MAGIC);
    Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition),
                                LW_EXCLUSIVE));
 
    delete_item(hash_table, item);
}

References Assert, dshash_table::control, dshash_seq_status::curitem, delete_item(), DSHASH_MAGIC, dshash_seq_status::exclusive, fb(), 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 CleanupListenersOnExit(), and pgstat_free_entry().

dshash_delete_entry()

void dshash_delete_entry	(	dshash_table *	hash_table,
		void *	entry
	)

Definition at line 543 of file dshash.c.

{
    dshash_table_item *item = ITEM_FROM_ENTRY(entry);
    size_t      partition = PARTITION_FOR_HASH(item->hash);
 
    Assert(hash_table->control->magic == DSHASH_MAGIC);
    Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition),
                                LW_EXCLUSIVE));
 
    delete_item(hash_table, item);
    LWLockRelease(PARTITION_LOCK(hash_table, partition));
}

References Assert, dshash_table::control, delete_item(), DSHASH_MAGIC, fb(), 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(), pgstat_get_entry_ref(), and RemoveListenerFromChannel().

dshash_delete_key()

bool dshash_delete_key	(	dshash_table *	hash_table,
		const void *	key
	)

Definition at line 505 of file dshash.c.

{
    dshash_hash hash;
    size_t      partition;
    bool        found;
 
    Assert(hash_table->control->magic == DSHASH_MAGIC);
    ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
 
    hash = hash_key(hash_table, key);
    partition = PARTITION_FOR_HASH(hash);
 
    LWLockAcquire(PARTITION_LOCK(hash_table, partition), LW_EXCLUSIVE);
    ensure_valid_bucket_pointers(hash_table);
 
    if (delete_key_from_bucket(hash_table, key,
                               &BUCKET_FOR_HASH(hash_table, hash)))
    {
        Assert(hash_table->control->partitions[partition].count > 0);
        found = true;
        --hash_table->control->partitions[partition].count;
    }
    else
        found = false;
 
    LWLockRelease(PARTITION_LOCK(hash_table, partition));
 
    return found;
}

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(), fb(), hash(), hash_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 325 of file dshash.c.

{
    size_t      size;
    size_t      i;
 
    Assert(hash_table->control->magic == DSHASH_MAGIC);
    ensure_valid_bucket_pointers(hash_table);
 
    /* Free all the entries. */
    size = NUM_BUCKETS(hash_table->size_log2);
    for (i = 0; i < size; ++i)
    {
        dsa_pointer item_pointer = hash_table->buckets[i];
 
        while (DsaPointerIsValid(item_pointer))
        {
            dshash_table_item *item;
            dsa_pointer next_item_pointer;
 
            item = dsa_get_address(hash_table->area, item_pointer);
            next_item_pointer = item->next;
            dsa_free(hash_table->area, item_pointer);
            item_pointer = next_item_pointer;
        }
    }
 
    /*
     * Vandalize the control block to help catch programming errors where
     * other backends access the memory formerly occupied by this hash table.
     */
    hash_table->control->magic = 0;
 
    /* Free the active table and control object. */
    dsa_free(hash_table->area, hash_table->control->buckets);
    dsa_free(hash_table->area, hash_table->control->handle);
 
    pfree(hash_table);
}

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(), fb(), 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 309 of file dshash.c.

{
    ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
 
    /* The hash table may have been destroyed.  Just free local memory. */
    pfree(hash_table);
}

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

{
    size_t      i;
    size_t      j;
 
    Assert(hash_table->control->magic == DSHASH_MAGIC);
    ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
 
    for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
    {
        Assert(!LWLockHeldByMe(PARTITION_LOCK(hash_table, i)));
        LWLockAcquire(PARTITION_LOCK(hash_table, i), LW_SHARED);
    }
 
    ensure_valid_bucket_pointers(hash_table);
 
    fprintf(stderr,
            "hash table size = %zu\n", (size_t) 1 << hash_table->size_log2);
    for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
    {
        dshash_partition *partition = &hash_table->control->partitions[i];
        size_t      begin = BUCKET_INDEX_FOR_PARTITION(i, hash_table->size_log2);
        size_t      end = BUCKET_INDEX_FOR_PARTITION(i + 1, hash_table->size_log2);
 
        fprintf(stderr, "  partition %zu\n", i);
        fprintf(stderr,
                "    active buckets (key count = %zu)\n", partition->count);
 
        for (j = begin; j < end; ++j)
        {
            size_t      count = 0;
            dsa_pointer bucket = hash_table->buckets[j];
 
            while (DsaPointerIsValid(bucket))
            {
                dshash_table_item *item;
 
                item = dsa_get_address(hash_table->area, bucket);
 
                bucket = item->next;
                ++count;
            }
            fprintf(stderr, "      bucket %zu (key count = %zu)\n", j, count);
        }
    }
 
    for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
        LWLockRelease(PARTITION_LOCK(hash_table, i));
}

References dshash_table::area, Assert, ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME, BUCKET_INDEX_FOR_PARTITION, dshash_table::buckets, dshash_table::control, dsa_get_address(), DsaPointerIsValid, DSHASH_MAGIC, DSHASH_NUM_PARTITIONS, ensure_valid_bucket_pointers(), fb(), 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 392 of file dshash.c.

{
    dshash_hash hash;
    size_t      partition;
    dshash_table_item *item;
 
    hash = hash_key(hash_table, key);
    partition = PARTITION_FOR_HASH(hash);
 
    Assert(hash_table->control->magic == DSHASH_MAGIC);
    ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
 
    LWLockAcquire(PARTITION_LOCK(hash_table, partition),
                  exclusive ? LW_EXCLUSIVE : LW_SHARED);
    ensure_valid_bucket_pointers(hash_table);
 
    /* Search the active bucket. */
    item = find_in_bucket(hash_table, key, BUCKET_FOR_HASH(hash_table, hash));
 
    if (!item)
    {
        /* Not found. */
        LWLockRelease(PARTITION_LOCK(hash_table, partition));
        return NULL;
    }
    else
    {
        /* The caller will free the lock by calling dshash_release_lock. */
        return ENTRY_FROM_ITEM(item);
    }
}

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

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

dshash_find_or_insert()

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

Definition at line 435 of file dshash.c.

{
    dshash_hash hash;
    size_t      partition_index;
    dshash_partition *partition;
    dshash_table_item *item;
 
    hash = hash_key(hash_table, key);
    partition_index = PARTITION_FOR_HASH(hash);
    partition = &hash_table->control->partitions[partition_index];
 
    Assert(hash_table->control->magic == DSHASH_MAGIC);
    ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table);
 
restart:
    LWLockAcquire(PARTITION_LOCK(hash_table, partition_index),
                  LW_EXCLUSIVE);
    ensure_valid_bucket_pointers(hash_table);
 
    /* Search the active bucket. */
    item = find_in_bucket(hash_table, key, BUCKET_FOR_HASH(hash_table, hash));
 
    if (item)
        *found = true;
    else
    {
        *found = false;
 
        /* Check if we are getting too full. */
        if (partition->count > MAX_COUNT_PER_PARTITION(hash_table))
        {
            /*
             * The load factor (= keys / buckets) for all buckets protected by
             * this partition is > 0.75.  Presumably the same applies
             * generally across the whole hash table (though we don't attempt
             * to track that directly to avoid contention on some kind of
             * central counter; we just assume that this partition is
             * representative).  This is a good time to resize.
             *
             * Give up our existing lock first, because resizing needs to
             * reacquire all the locks in the right order to avoid deadlocks.
             */
            LWLockRelease(PARTITION_LOCK(hash_table, partition_index));
            resize(hash_table, hash_table->size_log2 + 1);
 
            goto restart;
        }
 
        /* Finally we can try to insert the new item. */
        item = insert_into_bucket(hash_table, key,
                                  &BUCKET_FOR_HASH(hash_table, hash));
        item->hash = hash;
        /* Adjust per-lock-partition counter for load factor knowledge. */
        ++partition->count;
    }
 
    /* The caller must release the lock with dshash_release_lock. */
    return ENTRY_FROM_ITEM(item);
}

References Assert, ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME, BUCKET_FOR_HASH, dshash_table::control, DSHASH_MAGIC, ensure_valid_bucket_pointers(), ENTRY_FROM_ITEM, fb(), find_in_bucket(), dshash_table_item::hash, hash(), hash_key(), insert_into_bucket(), 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(), GetNamedDSA(), GetNamedDSHash(), GetNamedDSMSegment(), pgstat_get_entry_ref(), pgstat_read_statsfile(), PrepareTableEntriesForListen(), set_val_in_hash(), and SharedRecordTypmodRegistryInit().

dshash_get_hash_table_handle()

dshash_table_handle dshash_get_hash_table_handle

(

dshash_table *

hash_table

)

Definition at line 369 of file dshash.c.

{
    Assert(hash_table->control->magic == DSHASH_MAGIC);
 
    return hash_table->control->handle;
}

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

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

dshash_memcmp()

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

Definition at line 574 of file dshash.c.

{
    return memcmp(a, b, size);
}

References a, b, and fb().

dshash_memcpy()

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

Definition at line 592 of file dshash.c.

{
    (void) memcpy(dest, src, size);
}

References fb().

dshash_memhash()

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

Definition at line 583 of file dshash.c.

{
    return tag_hash(v, size);
}

References tag_hash().

dshash_release_lock()

void dshash_release_lock	(	dshash_table *	hash_table,
		void *	entry
	)

Definition at line 560 of file dshash.c.

{
    dshash_table_item *item = ITEM_FROM_ENTRY(entry);
    size_t      partition_index = PARTITION_FOR_HASH(item->hash);
 
    Assert(hash_table->control->magic == DSHASH_MAGIC);
 
    LWLockRelease(PARTITION_LOCK(hash_table, partition_index));
}

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

Referenced by ApplyLauncherGetWorkerStartTime(), ApplyLauncherSetWorkerStartTime(), ApplyPendingListenActions(), find_or_make_matching_shared_tupledesc(), get_val_in_hash(), GetNamedDSA(), GetNamedDSHash(), GetNamedDSMSegment(), lookup_rowtype_tupdesc_internal(), pgstat_acquire_entry_ref(), pgstat_drop_entry_internal(), pgstat_get_entry_ref(), pgstat_read_statsfile(), pgstat_release_entry_ref(), PrepareTableEntriesForListen(), set_val_in_hash(), SharedRecordTypmodRegistryInit(), and SignalBackends().

dshash_seq_init()

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

Definition at line 640 of file dshash.c.

{
    status->hash_table = hash_table;
    status->curbucket = 0;
    status->nbuckets = 0;
    status->curitem = NULL;
    status->pnextitem = InvalidDsaPointer;
    status->curpartition = -1;
    status->exclusive = exclusive;
}

References dshash_seq_status::curbucket, dshash_seq_status::curitem, dshash_seq_status::curpartition, dshash_seq_status::exclusive, fb(), dshash_seq_status::hash_table, InvalidDsaPointer, dshash_seq_status::nbuckets, and dshash_seq_status::pnextitem.

Referenced by CleanupListenersOnExit(), pg_get_dsm_registry_allocations(), pgstat_build_snapshot(), pgstat_drop_database_and_contents(), pgstat_drop_matching_entries(), pgstat_reset_matching_entries(), and pgstat_write_statsfile().

dshash_seq_next()

void * dshash_seq_next

(

dshash_seq_status *

status

)

Definition at line 659 of file dshash.c.

{
    dsa_pointer next_item_pointer;
 
    /*
     * Not yet holding any partition locks. Need to determine the size of the
     * hash table, it could have been resized since we were looking last.
     * Since we iterate in partition order, we can start by unconditionally
     * lock partition 0.
     *
     * Once we hold the lock, no resizing can happen until the scan ends. So
     * we don't need to repeatedly call ensure_valid_bucket_pointers().
     */
    if (status->curpartition == -1)
    {
        Assert(status->curbucket == 0);
        ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(status->hash_table);
 
        status->curpartition = 0;
 
        LWLockAcquire(PARTITION_LOCK(status->hash_table,
                                     status->curpartition),
                      status->exclusive ? LW_EXCLUSIVE : LW_SHARED);
 
        ensure_valid_bucket_pointers(status->hash_table);
 
        status->nbuckets =
            NUM_BUCKETS(status->hash_table->control->size_log2);
        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);
 
    /*
     * 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);
}

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, fb(), 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 CleanupListenersOnExit(), pg_get_dsm_registry_allocations(), pgstat_build_snapshot(), pgstat_drop_database_and_contents(), pgstat_drop_matching_entries(), pgstat_reset_matching_entries(), and pgstat_write_statsfile().

dshash_seq_term()

void dshash_seq_term

(

dshash_seq_status *

status

)

Definition at line 749 of file dshash.c.

{
    if (status->curpartition >= 0)
        LWLockRelease(PARTITION_LOCK(status->hash_table, status->curpartition));
}

References dshash_seq_status::curpartition, dshash_seq_status::hash_table, LWLockRelease(), and PARTITION_LOCK.

Referenced by CleanupListenersOnExit(), pg_get_dsm_registry_allocations(), pgstat_build_snapshot(), pgstat_drop_database_and_contents(), pgstat_drop_matching_entries(), pgstat_reset_matching_entries(), and pgstat_write_statsfile().

dshash_strcmp()

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

Definition at line 601 of file dshash.c.

{
    Assert(strlen((const char *) a) < size);
    Assert(strlen((const char *) b) < size);
 
    return strcmp((const char *) a, (const char *) b);
}

References a, Assert, b, and fb().

dshash_strcpy()

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

Definition at line 624 of file dshash.c.

{
    Assert(strlen((const char *) src) < size);
 
    (void) strcpy((char *) dest, (const char *) src);
}

References Assert, and fb().

dshash_strhash()

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

Definition at line 613 of file dshash.c.

{
    Assert(strlen((const char *) v) < size);
 
    return string_hash((const char *) v, size);
}

References Assert, fb(), and string_hash().

ensure_valid_bucket_pointers()

static void ensure_valid_bucket_pointers ( dshash_table *  hash_table )

inlinestatic

Definition at line 939 of file dshash.c.

{
    if (hash_table->size_log2 != hash_table->control->size_log2)
    {
        hash_table->buckets = dsa_get_address(hash_table->area,
                                              hash_table->control->buckets);
        hash_table->size_log2 = hash_table->control->size_log2;
    }
}

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

{
    return hash_table->params.compare_function(a, b,
                                               hash_table->params.key_size,
                                               hash_table->arg) == 0;
}

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

{
    while (DsaPointerIsValid(item_pointer))
    {
        dshash_table_item *item;
 
        item = dsa_get_address(hash_table->area, item_pointer);
        if (equal_keys(hash_table, key, ENTRY_FROM_ITEM(item)))
            return item;
        item_pointer = item->next;
    }
    return NULL;
}

References dshash_table::area, dsa_get_address(), DsaPointerIsValid, ENTRY_FROM_ITEM, equal_keys(), fb(), 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 1065 of file dshash.c.

{
    return hash_table->params.hash_function(key,
                                            hash_table->params.key_size,
                                            hash_table->arg);
}

References dshash_table::arg, dshash_parameters::hash_function, 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 988 of file dshash.c.

{
    dsa_pointer item_pointer;
    dshash_table_item *item;
 
    item_pointer = dsa_allocate(hash_table->area,
                                hash_table->params.entry_size +
                                MAXALIGN(sizeof(dshash_table_item)));
    item = dsa_get_address(hash_table->area, item_pointer);
    copy_key(hash_table, ENTRY_FROM_ITEM(item), key);
    insert_item_into_bucket(hash_table, item_pointer, item, bucket);
    return item;
}

References dshash_table::area, copy_key(), dsa_allocate, dsa_get_address(), ENTRY_FROM_ITEM, dshash_parameters::entry_size, fb(), insert_item_into_bucket(), 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 972 of file dshash.c.

{
    Assert(item == dsa_get_address(hash_table->area, item_pointer));
 
    item->next = *bucket;
    *bucket = item_pointer;
}

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

{
    dsa_pointer old_buckets;
    dsa_pointer new_buckets_shared;
    dsa_pointer *new_buckets;
    size_t      size;
    size_t      new_size = ((size_t) 1) << new_size_log2;
    size_t      i;
 
    /*
     * Acquire the locks for all lock partitions.  This is expensive, but we
     * shouldn't have to do it many times.
     */
    for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
    {
        Assert(!LWLockHeldByMe(PARTITION_LOCK(hash_table, i)));
 
        LWLockAcquire(PARTITION_LOCK(hash_table, i), LW_EXCLUSIVE);
        if (i == 0 && hash_table->control->size_log2 >= new_size_log2)
        {
            /*
             * Another backend has already increased the size; we can avoid
             * obtaining all the locks and return early.
             */
            LWLockRelease(PARTITION_LOCK(hash_table, 0));
            return;
        }
    }
 
    Assert(new_size_log2 == hash_table->control->size_log2 + 1);
 
    /* Allocate the space for the new table. */
    new_buckets_shared =
        dsa_allocate_extended(hash_table->area,
                              sizeof(dsa_pointer) * new_size,
                              DSA_ALLOC_HUGE | DSA_ALLOC_ZERO);
    new_buckets = dsa_get_address(hash_table->area, new_buckets_shared);
 
    /*
     * We've allocated the new bucket array; all that remains to do now is to
     * reinsert all items, which amounts to adjusting all the pointers.
     */
    size = ((size_t) 1) << hash_table->control->size_log2;
    for (i = 0; i < size; ++i)
    {
        dsa_pointer item_pointer = hash_table->buckets[i];
 
        while (DsaPointerIsValid(item_pointer))
        {
            dshash_table_item *item;
            dsa_pointer next_item_pointer;
 
            item = dsa_get_address(hash_table->area, item_pointer);
            next_item_pointer = item->next;
            insert_item_into_bucket(hash_table, item_pointer, item,
                                    &new_buckets[BUCKET_INDEX_FOR_HASH_AND_SIZE(item->hash,
                                                                                new_size_log2)]);
            item_pointer = next_item_pointer;
        }
    }
 
    /* Swap the hash table into place and free the old one. */
    old_buckets = hash_table->control->buckets;
    hash_table->control->buckets = new_buckets_shared;
    hash_table->control->size_log2 = new_size_log2;
    hash_table->buckets = new_buckets;
    dsa_free(hash_table->area, old_buckets);
 
    /* Release all the locks. */
    for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
        LWLockRelease(PARTITION_LOCK(hash_table, i));
}

References dshash_table::area, Assert, BUCKET_INDEX_FOR_HASH_AND_SIZE, dshash_table_control::buckets, dshash_table::buckets, dshash_table::control, DSA_ALLOC_HUGE, DSA_ALLOC_ZERO, dsa_allocate_extended(), dsa_free(), dsa_get_address(), DsaPointerIsValid, DSHASH_NUM_PARTITIONS, fb(), 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().