本篇内容主要讲解“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 = 164021.初始化相关变量,如根据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函数有什么作用”有了更深的了解，不妨来实际操作一番吧！这里是亿速云网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！
