PostgreSQL中hash_search_with_hash_value函数有什么作用

本篇内容主要讲解“postgresql中hash_search_with_hash_value函数有什么作用”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“Postgresql中hash_search_with_hash_value函数有什么作用”吧!

一、数据结构

BufferDesc
共享缓冲区的共享描述符(状态)数据

//buffer header锁定
#define BM_LOCKED               (1U << 22)  
//数据需要写入(标记为DIRTY)
#define BM_DIRTY                (1U << 23)  
//数据是有效的
#define BM_VALID                (1U << 24)  
//已分配buffer tag
#define BM_TAG_VALID            (1U << 25)  
//正在R/W
#define BM_io_IN_PROGRESS       (1U << 26)  
//上一个I/O出现错误
#define BM_IO_ERROR             (1U << 27)  
//开始写则变DIRTY
#define BM_JUST_DIRTIED         (1U << 28)  
//存在等待sole pin的其他进程
#define BM_PIN_COUNT_WaiTER     (1U << 29)  
//checkpoint发生,必须刷到磁盘上
#define BM_CHECKPOINT_NEEDED    (1U << 30)  
//持久化buffer(不是unlogged或者初始化fork)
#define BM_PERMANENT            (1U << 31)  

typedef struct BufferDesc
{
    //buffer tag
    BufferTag   tag;            
    //buffer索引编号(0开始),指向相应的buffer pool slot
    int         buf_id;         
    
    //tag状态,包括flags/refcount和usagecount
    pg_atomic_uint32 state;
    //pin-count等待进程ID
    int         wait_backend_pid;   
    //空闲链表链中下一个空闲的buffer
    int         freeNext;       
    //缓冲区内容锁
    LWLock      content_lock;   
} BufferDesc;

BufferTag
Buffer tag标记了buffer存储的是磁盘中哪个block

typedef struct buftag
{
    //物理relation标识符
    RelFilenode rnode;          
    ForkNumber  forkNum;
    //相对于relation起始的块号
    BlockNumber blockNum;       
} BufferTag;

HTAB
哈希表的顶层控制结构.

struct HTAB
{
    //指向共享的控制信息
    HASHHDR    *hctl;           
    //段开始目录
    HASHSEGMENT *dir;           
    //哈希函数
    HashValueFunc hash;         
    //哈希键比较函数
    HashCompareFunc match;      
    //哈希键拷贝函数
    HashCopyFunc keycopy;       
    //内存分配器
    HashAllocFunc alloc;        
    //内存上下文
    MemoryContext hcxt;         
    //表名(用于错误信息)
    char       *tabname;        
    //如在共享内存中,则为T
    bool        isshared;       
    //如为T,则固定大小不能扩展
    bool        isfixed;        
    
    //不允许冻结共享表,因此这里会保存相关状态
    bool        frozen;         
    
    //保存这些固定值的本地拷贝,以减少冲突
    //哈希键长度(以字节为单位)
    Size        keysize;        
    //段大小,必须为2的幂
    long        ssize;          
    //段偏移,ssize的对数
    int         sshift;         
};

struct HASHHDR
{
    
    FreeListData freeList[NUM_FREELISTS];
    
    //这些域字段可以改变,但不适用于分区表
    
    //同时,就算是非分区表,共享表的dsize也不能改变
    //目录大小
    long        dsize;          
    //已分配的段大小(<= dbsize)
    long        nsegs;          
    //正在使用的最大桶ID
    uint32      max_bucket;     
    //进入整个哈希表的模掩码
    uint32      high_mask;      
    //进入低于半个哈希表的模掩码
    uint32      low_mask;       
    
    //下面这些字段在哈希表创建时已固定
    //哈希键大小(以字节为单位)
    Size        keysize;        
    //所有用户元素大小(以字节为单位)
    Size        entrysize;      
    //分区个数(2的幂),或者为0
    long        num_partitions; 
    //目标的填充因子
    long        ffactor;        
    //如目录是固定大小,则该值为dsize的上限值
    long        max_dsize;      
    //段大小,必须是2的幂
    long        ssize;          
    //端偏移,ssize的对数
    int         sshift;         
    //一次性分配的条目个数
    int         nelem_alloc;    
#ifdef HASH_STATISTICS
    
    long        accesses;
    long        collisions;
#endif
};

typedef struct HASHELEMENT
{
    //链接到相同桶中的下一个条目
    struct HASHELEMENT *link;   
    //该条目的哈希函数结果
    uint32      hashvalue;      
} HASHELEMENT;

//哈希表头部结构,非透明类型,用于dynahash.c
typedef struct HASHHDR HASHHDR;

//哈希表控制结构,非透明类型,用于dynahash.c
typedef struct HTAB HTAB;

//hash_create使用的参数数据结构

//根据hash_flags标记设置相应的字段
typedef struct HASHCTL
{
    //分区个数(必须是2的幂)
    long        num_partitions; 
    //段大小
    long        ssize;          
    //初始化目录大小
    long        dsize;          
    //dsize上限
    long        max_dsize;      
    //填充因子
    long        ffactor;        
    //哈希键大小(字节为单位)
    Size        keysize;        
    //参见上述数据结构注释
    Size        entrysize;      
    //
    HashValueFunc hash;         
    HashCompareFunc match;      
    HashCopyFunc keycopy;       
    HashAllocFunc alloc;        
    MemoryContext hcxt;         
    //共享内存中的哈希头部结构地址
    HASHHDR    *hctl;           
} HASHCTL;

//哈希桶是HASHELEMENTs链表
typedef HASHELEMENT *HASHBUCKET;

//hash segment是桶数组
typedef HASHBUCKET *HASHSEGMENT;

typedef uint32 (*HashValueFunc) (const void *key, Size keysize);
 
typedef int (*HashCompareFunc) (const void *key1, const void *key2,
 Size keysize);
 
typedef void *(*HashCopyFunc) (void *dest, const void *src, Size keysize);

typedef void *(*HashAllocFunc) (Size request);

FreeListData
在一个分区哈希表中,每一个空闲链表与特定的hashcodes集合相关,通过下面的FREELIST_IDX()宏进行定义.
nentries跟踪有这些hashcodes的仍存活的hashtable条目个数.

typedef struct
{
    //该空闲链表的自旋锁
    slock_t     mutex;          
    //相关桶中的条目个数
    long        nentries;       
    //空闲元素链
    HASHELEMENT *freeList;      
} FreeListData;

BufferLookupEnt

//检索hash表的条目
typedef struct
{
    //磁盘page的tag
    BufferTag   key;            
    //相关联的buffer ID
    int         id;             
} BufferLookupEnt;

二、源码解读

hash_search_with_hash_value函数,根据给定tag和buffer ID,插入到哈希表中,如该tag相应的条目已存在,则不处理.
其主要实现逻辑如下:
1.初始化相关变量,如根据hash值获取idx等
2.如action为插入,检查是否需要分裂哈希桶
3.执行相关初始化检索,计算桶号/段号/段内编号等
4.沿着哈希键冲突链搜索匹配键,根据搜索结果给foundPtr赋值
5.根据输入action执行相应的逻辑
5.1HASH_FIND,搜索
5.2HASH_REMOVE,移除
5.3HASH_ENTER_NULL,验证分配器,转至HASH_ENTER
5.4HASH_ENTER,如找到,则返回现存的元素,否则创建一个
6.找不到,则报错,返回NULL

void *
hash_search_with_hash_value(HTAB *hashp,
                            const void *keyPtr,
                            uint32 hashvalue,
                            HASHACTION action,
                            bool *foundPtr)
{
    HASHHDR    *hctl = hashp->hctl;//获取HASHHDR
    int         freelist_idx = FREELIST_IDX(hctl, hashvalue);//根据hash值获取idx
    Size        keysize;//键值大小
    uint32      bucket;//桶号
    long        segment_num;//段号
    long        segment_ndx;//
    HASHSEGMENT segp;//段
    HASHBUCKET  currBucket;//当前桶号
    HASHBUCKET *prevBucketPtr;//上一个桶号
    HashCompareFunc match;//是否match?
#if HASH_STATISTICS//统计信息
    hash_accesses++;
    hctl->accesses++;
#endif
    
    if (action == HASH_ENTER || action == HASH_ENTER_NULL)
    {
        
        if (!IS_PARTITIONED(hctl) && !hashp->frozen &&
            hctl->freeList[0].nentries / (long) (hctl->max_bucket + 1) >= hctl->ffactor &&
            !has_seq_scans(hashp))
            (void) expand_table(hashp);
    }
    
    //计算桶号
    bucket = calc_bucket(hctl, hashvalue);
    //计算段号和段内编号
    segment_num = bucket >> hashp->sshift;
    segment_ndx = MOD(bucket, hashp->ssize);
    //获取directory
    segp = hashp->dir[segment_num];
    if (segp == NULL)
        hash_corrupted(hashp);
    //记录桶号
    prevBucketPtr = &segp[segment_ndx];
    currBucket = *prevBucketPtr;
    
    //匹配函数
    match = hashp->match;       
    //键大小
    keysize = hashp->keysize;   
    while (currBucket != NULL)
    {
        if (currBucket->hashvalue == hashvalue &&
            match(ELEMENTKEY(currBucket), keyPtr, keysize) == 0)
            break;
        prevBucketPtr = &(currBucket->link);
        currBucket = *prevBucketPtr;
#if HASH_STATISTICS
        hash_collisions++;
        hctl->collisions++;
#endif
    }
    //结果赋值
    if (foundPtr)
        *foundPtr = (bool) (currBucket != NULL);
    
    switch (action)
    {
        case HASH_FIND:
            //搜索
            if (currBucket != NULL)
                return (void *) ELEMENTKEY(currBucket);
            return NULL;
        case HASH_REMOVE:
            //移除
            if (currBucket != NULL)
            {
                
                //如分区,在访问条目入口和空闲链表时必须先请求锁
                if (IS_PARTITIONED(hctl))
                    SpinLockAcquire(&(hctl->freeList[freelist_idx].mutex));
                
                //修改nentries计数器
                Assert(hctl->freeList[freelist_idx].nentries > 0);
                hctl->freeList[freelist_idx].nentries--;
                
                //在哈希桶中链中删除记录
                *prevBucketPtr = currBucket->link;
                
                //添加记录到正确的空闲链表上
                currBucket->link = hctl->freeList[freelist_idx].freeList;
                hctl->freeList[freelist_idx].freeList = currBucket;
                if (IS_PARTITIONED(hctl))
                    //释放锁
                    SpinLockRelease(&hctl->freeList[freelist_idx].mutex);
                
                return (void *) ELEMENTKEY(currBucket);
            }
            return NULL;
        case HASH_ENTER_NULL:
            
            //验证分配器
            Assert(hashp->alloc != DynaHashAlloc);
            
            //继续往下执行
        case HASH_ENTER:
            
            //如找到,则返回现存的元素,否则创建一个
            if (currBucket != NULL)
                return (void *) ELEMENTKEY(currBucket);
            
            //如冻结,则不允许插入,报错
            if (hashp->frozen)
                elog(ERROR, "cannot insert into frozen hashtable \"%s\"",
                     hashp->tabname);
            //获取当前桶
            currBucket = get_hash_entry(hashp, freelist_idx);
            if (currBucket == NULL)
            {
                //如为NULL
                
                //内存溢出
                if (action == HASH_ENTER_NULL)
                    return NULL;
                
                //报错
                if (hashp->isshared)
                    ereport(ERROR,
                            (errcode(ERRCODE_OUT_OF_MEMORY),
                             errmsg("out of shared memory")));
                else
                    ereport(ERROR,
                            (errcode(ERRCODE_OUT_OF_MEMORY),
                             errmsg("out of memory")));
            }
            //正常
            
            //连接到哈希桶链中
            *prevBucketPtr = currBucket;
            currBucket->link = NULL;
            
            //拷贝键到记录中
            currBucket->hashvalue = hashvalue;
            hashp->keycopy(ELEMENTKEY(currBucket), keyPtr, keysize);
            
            return (void *) ELEMENTKEY(currBucket);
    }
    //如执行到这里,那程序就有问题了.
    elog(ERROR, "unrecognized hash action code: %d", (int) action);
    //返回NULL,让编译器shut up
    return NULL;                
}

//转换hash值为桶号
static inline uint32
calc_bucket(HASHHDR *hctl, uint32 hash_val)
{
    uint32      bucket;//桶号
    bucket = hash_val & hctl->high_mask;//执行&操作
    if (bucket > hctl->max_bucket)//大于最大桶号,则返回low_mask
        bucket = bucket & hctl->low_mask;
    return bucket;
}

static HASHBUCKET
get_hash_entry(HTAB *hashp, int freelist_idx)
{
    HASHHDR    *hctl = hashp->hctl;
    HASHBUCKET  newElement;
    for (;;)
    {
        //循环
        
        //如为分区哈希表,在访问条目和空闲链表时,必须锁定
        if (IS_PARTITIONED(hctl))
            SpinLockAcquire(&hctl->freeList[freelist_idx].mutex);
        
        //从空闲链表中尝试获取一个条目
        newElement = hctl->freeList[freelist_idx].freeList;
        if (newElement != NULL)
            break;
        if (IS_PARTITIONED(hctl))
            SpinLockRelease(&hctl->freeList[freelist_idx].mutex);
        
        if (!element_alloc(hashp, hctl->nelem_alloc, freelist_idx))
        {
            //本空闲链表不能分配内存
            int         borrow_from_idx;
            if (!IS_PARTITIONED(hctl))
                //非分区哈希表,返回NULL,意味着内存溢出了.
                return NULL;    
            
            //尝试从其他空闲链表浏览元素
            borrow_from_idx = freelist_idx;
            for (;;)
            {
                //------- 开始遍历其他空闲链表
                borrow_from_idx = (borrow_from_idx + 1) % NUM_FREELISTS;
                if (borrow_from_idx == freelist_idx)
                    //已经完成整个空闲链表的遍历,退出
                    break;      
                //获取自旋锁
                SpinLockAcquire(&(hctl->freeList[borrow_from_idx].mutex));
                newElement = hctl->freeList[borrow_from_idx].freeList;
                if (newElement != NULL)
                {
                    hctl->freeList[borrow_from_idx].freeList = newElement->link;
                    SpinLockRelease(&(hctl->freeList[borrow_from_idx].mutex));
                    
                    //小心:在合适的空闲链表上统计新的元素
                    SpinLockAcquire(&hctl->freeList[freelist_idx].mutex);
                    hctl->freeList[freelist_idx].nentries++;
                    SpinLockRelease(&hctl->freeList[freelist_idx].mutex);
                    return newElement;
                }
                SpinLockRelease(&(hctl->freeList[borrow_from_idx].mutex));
            }
            
            //已无元素,内存溢出
            return NULL;
        }
    }
    
    //从空闲链表中移除条目,bump nentries
    hctl->freeList[freelist_idx].freeList = newElement->link;
    hctl->freeList[freelist_idx].nentries++;
    if (IS_PARTITIONED(hctl))
        SpinLockRelease(&hctl->freeList[freelist_idx].mutex);
    return newElement;
}

三、跟踪分析

测试脚本

10:44:12 (xdb@[local]:5432)testdb=# select * from t1 limit 10;

设置断点,跟踪

(gdb) b hash_search_with_hash_value
Breakpoint 1 at 0xa3a4d7: file dynahash.c, line 925.
(gdb) c
Continuing.
Breakpoint 2, hash_search_with_hash_value (hashp=0x13af8f8, keyPtr=0x7ffdb7d63e40, hashvalue=3920871586, action=HASH_ENTER, 
    foundPtr=0x7ffdb7d63e3f) at dynahash.c:925
925     HASHHDR    *hctl = hashp->hctl;
(gdb)

输入参数

(gdb) p *hashp
$3 = {hctl = 0x13af990, dir = 0x13afda8, hash = 0xa3bf74 <tag_hash>, match = 0x4791a0 <memcmp@plt>, 
  keycopy = 0x479690 <memcpy@plt>, alloc = 0xa39589 <DynaHashAlloc>, hcxt = 0x13af7e0, 
  tabname = 0x13af958 "LOCALLOCK hash", isshared = false, isfixed = false, frozen = false, keysize = 20, ssize = 256, 
  sshift = 8}
(gdb) p *hashp->hctl
$4 = {freeList = {{mutex = 0 '\000', nentries = 0, freeList = 0x13b1378}, {mutex = 0 '\000', nentries = 0, 
      freeList = 0x0} <repeats 31 times>}, dsize = 256, nsegs = 1, max_bucket = 15, high_mask = 31, low_mask = 15, 
  keysize = 20, entrysize = 80, num_partitions = 0, ffactor = 1, max_dsize = -1, ssize = 256, sshift = 8, nelem_alloc = 42}
(gdb) p *(int *)keyPtr
$5 = 16402

1.初始化相关变量,如根据hash值获取idx等

(gdb) n
926     int         freelist_idx = FREELIST_IDX(hctl, hashvalue);
(gdb) 
949     if (action == HASH_ENTER || action == HASH_ENTER_NULL)
(gdb) p freelist_idx
$6 = 0
(gdb) p *hctl->freeList[0].freeList
$7 = {link = 0x13b1318, hashvalue = 3920871586}
(gdb) 
(gdb) p hctl->freeList[0]
$8 = {mutex = 0 '\000', nentries = 0, freeList = 0x13b1378}

2.如action为插入,检查是否需要分裂哈希桶

(gdb) n
956         if (!IS_PARTITIONED(hctl) && !hashp->frozen &&
(gdb) 
957             hctl->freeList[0].nentries / (long) (hctl->max_bucket + 1) >= hctl->ffactor &&
(gdb) 
956         if (!IS_PARTITIONED(hctl) && !hashp->frozen &&
(gdb)

3.执行相关初始化检索,计算桶号/段号/段内编号等

(gdb) p bucket
$9 = 2
(gdb) p segment_num
$10 = 0
(gdb) p segment_ndx
$11 = 2
(gdb) p segp
$12 = (HASHSEGMENT) 0x13b05c0
(gdb) p *segp
$13 = (HASHBUCKET) 0x0
(gdb) 
(gdb) n
975     prevBucketPtr = &segp[segment_ndx];
(gdb) 
976     currBucket = *prevBucketPtr;
(gdb) p
$14 = (HASHBUCKET) 0x0
(gdb) n
981     match = hashp->match;       
(gdb) p currBucket
$15 = (HASHBUCKET) 0x0
(gdb)

4.沿着哈希键冲突链搜索匹配键,根据搜索结果给foundPtr赋值

(gdb) n
982     keysize = hashp->keysize;   
(gdb) 
984     while (currBucket != NULL)
(gdb) p keysize
$16 = 20
(gdb) p match
$17 = (HashCompareFunc) 0x4791a0 <memcmp@plt>
(gdb) p currBucket
$18 = (HASHBUCKET) 0x0
(gdb) n
997     if (foundPtr)
(gdb) 
998         *foundPtr = (bool) (currBucket != NULL);
(gdb)

5.根据输入action执行相应的逻辑
5.1HASH_FIND,搜索
5.2HASH_REMOVE,移除
5.3HASH_ENTER_NULL,验证分配器,转至HASH_ENTER
5.4HASH_ENTER,如找到,则返回现存的元素,否则创建一个

(gdb) 
1003        switch (action)
(gdb) p action
$19 = HASH_ENTER
(gdb) n
1047                if (currBucket != NULL)
(gdb) 
1051                if (hashp->frozen)
(gdb) 
1055                currBucket = get_hash_entry(hashp, freelist_idx);
(gdb)

进入get_hash_entry,如可能,分配一个新的哈希表条目.如内存溢出则返回NULL.

1055                currBucket = get_hash_entry(hashp, freelist_idx);
(gdb) step
get_hash_entry (hashp=0x13af8f8, freelist_idx=0) at dynahash.c:1252
1252        HASHHDR    *hctl = hashp->hctl;
(gdb) 
(gdb) n
1258            if (IS_PARTITIONED(hctl))
(gdb) p *hctl
$20 = {freeList = {{mutex = 0 '\000', nentries = 0, freeList = 0x13b1378}, {mutex = 0 '\000', nentries = 0, 
      freeList = 0x0} <repeats 31 times>}, dsize = 256, nsegs = 1, max_bucket = 15, high_mask = 31, low_mask = 15, 
  keysize = 20, entrysize = 80, num_partitions = 0, ffactor = 1, max_dsize = -1, ssize = 256, sshift = 8, nelem_alloc = 42}
(gdb) n
1262            newElement = hctl->freeList[freelist_idx].freeList;
(gdb) 
1264            if (newElement != NULL)
(gdb) p newElement
$21 = (HASHBUCKET) 0x13b1378
(gdb) p *newElement
$22 = {link = 0x13b1318, hashvalue = 3920871586}
(gdb) n
1265                break;
(gdb) 
1322        hctl->freeList[freelist_idx].freeList = newElement->link;
(gdb) 
1323        hctl->freeList[freelist_idx].nentries++;
(gdb) 
1325        if (IS_PARTITIONED(hctl))
(gdb) p *newElement->link
$23 = {link = 0x13b12b8, hashvalue = 2593617408}
(gdb) n
1328        return newElement;
(gdb) 
1329    }
(gdb)

回到hash_search_with_hash_value

hash_search_with_hash_value (hashp=0x13af8f8, keyPtr=0x7ffdb7d63e40, hashvalue=3920871586, action=HASH_ENTER, 
    foundPtr=0x7ffdb7d63e3f) at dynahash.c:1056
1056                if (currBucket == NULL)
(gdb) n
1073                *prevBucketPtr = currBucket;
(gdb) p *currBucket
$24 = {link = 0x13b1318, hashvalue = 3920871586}
(gdb) n
1074                currBucket->link = NULL;
(gdb) 
1077                currBucket->hashvalue = hashvalue;
(gdb) 
1078                hashp->keycopy(ELEMENTKEY(currBucket), keyPtr, keysize);
(gdb) p *currBucket
$25 = {link = 0x0, hashvalue = 3920871586}
(gdb) p *prevBucketPtr
$26 = (HASHBUCKET) 0x13b1378
(gdb) p **prevBucketPtr
$27 = {link = 0x0, hashvalue = 3920871586}
(gdb) n
1087                return (void *) ELEMENTKEY(currBucket);
(gdb) p (void *) ELEMENTKEY(currBucket)
$28 = (void *) 0x13b1388

找到entry,返回

(gdb) n
1093    }
(gdb) 
hash_search (hashp=0x13af8f8, keyPtr=0x7ffdb7d63e40, action=HASH_ENTER, foundPtr=0x7ffdb7d63e3f) at dynahash.c:916
916 }
(gdb)

到此，相信大家对“PostgreSQL中hash_search_with_hash_value函数有什么作用”有了更深的了解，不妨来实际操作一番吧！这里是编程网网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！