本節(jié)簡(jiǎn)單介紹了PostgreSQL在執(zhí)行插入過程中與存儲(chǔ)相關(guān)的函數(shù)RecordAndGetPageWithFreeSpace->fsm_set_and_search,該函數(shù)設(shè)置給定的FSM page的相應(yīng)值,并返回合適的slot。
成都創(chuàng)新互聯(lián)堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都做網(wǎng)站、網(wǎng)站設(shè)計(jì)、外貿(mào)營(yíng)銷網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的新洲網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！
FSMAddress
內(nèi)部的FSM處理過程以邏輯地址scheme的方式工作,樹的每一個(gè)層次都可以認(rèn)為是一個(gè)獨(dú)立的地址文件.
重慶分公司
重慶分公司
/*
* The internal FSM routines work on a logical addressing scheme. Each
* level of the tree can be thought of as a separately addressable file.
* 內(nèi)部的FSM處理過程工作在一個(gè)邏輯地址scheme上.
* 樹的每一個(gè)層次都可以認(rèn)為是一個(gè)獨(dú)立的地址文件.
*/
typedef struct
{
//層次
int level; /* level */
//該層次內(nèi)的頁(yè)編號(hào)
int logpageno; /* page number within the level */
} FSMAddress;
/* Address of the root page. */
//根頁(yè)地址
static const FSMAddress FSM_ROOT_ADDRESS = {FSM_ROOT_LEVEL, 0};
FSMPage
FSM page數(shù)據(jù)結(jié)構(gòu).詳細(xì)可參看src/backend/storage/freespace/README.
/*
* Structure of a FSM page. See src/backend/storage/freespace/README for
* details.
* FSM page數(shù)據(jù)結(jié)構(gòu).詳細(xì)可參看src/backend/storage/freespace/README.
*/
typedef struct
{
/*
* fsm_search_avail() tries to spread the load of multiple backends by
* returning different pages to different backends in a round-robin
* fashion. fp_next_slot points to the next slot to be returned (assuming
* there's enough space on it for the request). It's defined as an int,
* because it's updated without an exclusive lock. uint16 would be more
* appropriate, but int is more likely to be atomically
* fetchable/storable.
* fsm_search_avail()函數(shù)嘗試通過在一輪循環(huán)中返回不同的頁(yè)面到不同的后臺(tái)進(jìn)程,
* 從而分散在后臺(tái)進(jìn)程上分散負(fù)載.
* 該字段因?yàn)闊o需獨(dú)占鎖,因此定義為整型.
* unit16可能會(huì)更合適,但整型看起來更適合于原子提取和存儲(chǔ).
*/
int fp_next_slot;
/*
* fp_nodes contains the binary tree, stored in array. The first
* NonLeafNodesPerPage elements are upper nodes, and the following
* LeafNodesPerPage elements are leaf nodes. Unused nodes are zero.
* fp_nodes以數(shù)組的形式存儲(chǔ)二叉樹.
* 第一個(gè)NonLeafNodesPerPage元素是上一層的節(jié)點(diǎn),接下來的LeafNodesPerPage元素是葉子節(jié)點(diǎn).
* 未使用的節(jié)點(diǎn)為0.
*/
uint8 fp_nodes[FLEXIBLE_ARRAY_MEMBER];
} FSMPageData;
typedef FSMPageData *FSMPage;
FSMLocalMap
對(duì)于小表,不需要?jiǎng)?chuàng)建FSM來存儲(chǔ)空間信息,使用本地的內(nèi)存映射信息.
/* Either already tried, or beyond the end of the relation */
//已嘗試或者已在表的末尾之后
#define FSM_LOCAL_NOT_AVAIL 0x00
/* Available to try */
//可用于嘗試
#define FSM_LOCAL_AVAIL 0x01
/*
* For small relations, we don't create FSM to save space, instead we use
* local in-memory map of pages to try. To locate free space, we simply try
* pages directly without knowing ahead of time how much free space they have.
* 對(duì)于小表,不需要?jiǎng)?chuàng)建FSM來存儲(chǔ)空間信息,使用本地的內(nèi)存映射信息.
* 為了定位空閑空間,我們不需要知道他們有多少空閑空間而是直接簡(jiǎn)單的對(duì)page進(jìn)行嘗試.
*
* Note that this map is used to the find the block with required free space
* for any given relation. We clear this map when we have found a block with
* enough free space, when we extend the relation, or on transaction abort.
* See src/backend/storage/freespace/README for further details.
* 注意這個(gè)map用于搜索給定表的請(qǐng)求空閑空間.
* 在找到有足夠空閑空間的block/擴(kuò)展了relation/在事務(wù)回滾時(shí),則清除這個(gè)map的信息.
* 詳細(xì)可查看src/backend/storage/freespace/README.
*/
typedef struct
{
BlockNumber nblocks;//塊數(shù)
uint8 map[HEAP_FSM_CREATION_THRESHOLD];//數(shù)組
} FSMLocalMap;
static FSMLocalMap fsm_local_map =
{
0,
{
FSM_LOCAL_NOT_AVAIL
}
};
#define FSM_LOCAL_MAP_EXISTS (fsm_local_map.nblocks > 0)
fsm_set_and_search設(shè)置給定的FSM page的相應(yīng)值,并返回合適的slot.
主要處理邏輯如下:
1.初始化相關(guān)變量
2.設(shè)置相應(yīng)頁(yè)面的FSM可用標(biāo)記
3.如search_cat/minvalue(請(qǐng)求空間)不為0,則調(diào)用fsm_search_avail搜索slot
4.解鎖,返回
搜索樹的算法是逐漸擴(kuò)展”search triangle”(暫且稱為搜索三角),也就是說,被當(dāng)前節(jié)點(diǎn)所覆蓋的所有節(jié)點(diǎn),確保我們從開始點(diǎn)向右搜索.在第一步,只有目標(biāo)slot會(huì)被檢查.當(dāng)我們從左邊子節(jié)點(diǎn)往上移動(dòng)到父節(jié)點(diǎn)時(shí),我們同時(shí)添加了父節(jié)點(diǎn)的右子樹到搜索三角中.當(dāng)我們從右邊子節(jié)點(diǎn)往上移動(dòng)到父節(jié)點(diǎn)時(shí),我們同時(shí)刪除了當(dāng)前搜索三角(這時(shí)候已經(jīng)知道了沒有合適的page), 同時(shí)向右檢索下一個(gè)更大尺寸的三角.因此,我們不會(huì)從起點(diǎn)向左搜索,在每一步搜索三角的尺寸都會(huì)翻倍,確保只需要log2(N)步就可以搜索N個(gè)頁(yè)面.
例如,考慮下面這棵樹:
7
7 6
5 7 6 5
4 5 5 7 2 6 5 2
T
假定目標(biāo)節(jié)點(diǎn)是字母T指示的節(jié)點(diǎn),同時(shí)我們正在使用6或更大的數(shù)字搜索節(jié)點(diǎn).檢索從T開始.在第一輪迭代,移到右邊,然后到父節(jié)點(diǎn),到達(dá)最右邊的節(jié)點(diǎn) 5.在第二輪迭代,移到右邊,回卷,然后上溯,在第三個(gè)層次上到達(dá)節(jié)點(diǎn) 7這時(shí)候7滿足我們的搜索要求,因此我們沿著7這條路徑下降到底部.實(shí)際上,這是(考慮到回卷)起點(diǎn)右側(cè)第一個(gè)滿足條件的頁(yè)面.
/*
* Set value in given FSM page and slot.
* 設(shè)置給定的FSM page的相應(yīng)值,并返回合適的slot.
*
* If minValue > 0, the updated page is also searched for a page with at
* least minValue of free space. If one is found, its slot number is
* returned, -1 otherwise.
* 如minValue大于0,更新后的page還將搜索空閑空間只是為最小值的page.
* 如果找到了,返回slot編號(hào),否則返回-1.
*/
//search_slot = fsm_set_and_search(rel, addr, slot, old_cat, search_cat);
static int
fsm_set_and_search(Relation rel, FSMAddress addr, uint16 slot,
uint8 newValue, uint8 minValue)
{
Buffer buf;
Page page;
int newslot = -1;
//獲取FSM的buffer
buf = fsm_readbuf(rel, addr, true);
//鎖定
LockBuffer(buf, BUFFER_LOCK_EXCLUSIVE);
//獲取FSM的page
page = BufferGetPage(buf);
if (fsm_set_avail(page, slot, newValue))
MarkBufferDirtyHint(buf, false);
if (minValue != 0)
{
/* Search while we still hold the lock */
//搜索slot
newslot = fsm_search_avail(buf, minValue,
addr.level == FSM_BOTTOM_LEVEL,
true);
}
UnlockReleaseBuffer(buf);
return newslot;
}
/*
* Searches for a slot with category at least minvalue.
* Returns slot number, or -1 if none found.
* 搜索目錄至少為最小值的slot.
*
* The caller must hold at least a shared lock on the page, and this
* function can unlock and lock the page again in exclusive mode if it
* needs to be updated. exclusive_lock_held should be set to true if the
* caller is already holding an exclusive lock, to avoid extra work.
* 調(diào)用者必須持有page共享鎖,如page需要更新則該函數(shù)可能重新以獨(dú)占模式解鎖或鎖定page.
* 如調(diào)用者已持有獨(dú)占鎖exclusive_lock_held需設(shè)置為T,以避免額外的工作.
*
* If advancenext is false, fp_next_slot is set to point to the returned
* slot, and if it's true, to the slot after the returned slot.
* 如果advancenext是F,fp_next_slot被設(shè)置為指向返回的slot;
* 如為T,則指向返回的slot后的slot.
*/
//newslot = fsm_search_avail(buf, minValue, \
addr.level == FSM_BOTTOM_LEVEL, \
true);
int
fsm_search_avail(Buffer buf, uint8 minvalue, bool advancenext,
bool exclusive_lock_held)
{
Page page = BufferGetPage(buf);//獲取page
FSMPage fsmpage = (FSMPage) PageGetContents(page);//獲取FSMPage
int nodeno;
int target;
uint16 slot;
restart:
/*
* Check the root first, and exit quickly if there's no leaf with enough
* free space
* 首先檢查根節(jié)點(diǎn),如葉子節(jié)點(diǎn)無足夠的空閑空間則快速退出.
*/
if (fsmpage->fp_nodes[0] < minvalue)
return -1;
/*
* Start search using fp_next_slot. It's just a hint, so check that it's
* sane. (This also handles wrapping around when the prior call returned
* the last slot on the page.)
* 使用fp_next_slot開始搜索.
* 這個(gè)標(biāo)記只是一個(gè)提示而已,檢查它是否正常.
* (這同時(shí)處理了在上一次調(diào)用返回的頁(yè)面最后一個(gè)slot的回卷問題)
*/
//#define SlotsPerFSMPage LeafNodesPerPage
//#define LeafNodesPerPage (NodesPerPage - NonLeafNodesPerPage)
//#define NodesPerPage (BLCKSZ - MAXALIGN(SizeOfPageHeaderData) - \
offsetof(FSMPageData, fp_nodes))
//#define NonLeafNodesPerPage (BLCKSZ / 2 - 1) = 4095
target = fsmpage->fp_next_slot;
if (target < 0 || target >= LeafNodesPerPage)
target = 0;
target += NonLeafNodesPerPage;
/*----------
* Start the search from the target slot. At every step, move one
* node to the right, then climb up to the parent. Stop when we reach
* a node with enough free space (as we must, since the root has enough
* space).
* 從目標(biāo)slot開始檢索.每一步,把節(jié)點(diǎn)移到右邊,然后上溯父節(jié)點(diǎn).
* 在到達(dá)一個(gè)有足夠空閑空間的節(jié)點(diǎn)時(shí)停止(因?yàn)楦?jié)點(diǎn)有足夠的空間).
*
* The idea is to gradually expand our "search triangle", that is, all
* nodes covered by the current node, and to be sure we search to the
* right from the start point. At the first step, only the target slot
* is examined. When we move up from a left child to its parent, we are
* adding the right-hand subtree of that parent to the search triangle.
* When we move right then up from a right child, we are dropping the
* current search triangle (which we know doesn't contain any suitable
* page) and instead looking at the next-larger-size triangle to its
* right. So we never look left from our original start point, and at
* each step the size of the search triangle doubles, ensuring it takes
* only log2(N) work to search N pages.
* 算法思想是逐漸擴(kuò)展"search triangle 搜索三角",也就是說,
* 被當(dāng)前節(jié)點(diǎn)所覆蓋的所有節(jié)點(diǎn),確保我們從開始點(diǎn)向右搜索.
* 在第一步,只有目標(biāo)slot會(huì)被檢查.
* 當(dāng)我們從左邊子節(jié)點(diǎn)往上移動(dòng)到父節(jié)點(diǎn)時(shí),我們同時(shí)添加了父節(jié)點(diǎn)的右子樹到搜索三角中.
* 當(dāng)我們從右邊子節(jié)點(diǎn)往上移動(dòng)到父節(jié)點(diǎn)時(shí),我們同時(shí)刪除了當(dāng)前搜索三角(這時(shí)候已經(jīng)知道了沒有合適的page),
* 同時(shí)向右檢索下一個(gè)更大尺寸的三角.
* 因此,我們不會(huì)從起點(diǎn)向左搜索,在每一步搜索三角的尺寸都會(huì)翻倍,確保只需要log2(N)步就可以搜索N個(gè)頁(yè)面.
*
* The "move right" operation will wrap around if it hits the right edge
* of the tree, so the behavior is still good if we start near the right.
* Note also that the move-and-climb behavior ensures that we can't end
* up on one of the missing nodes at the right of the leaf level.
* "move right"操作會(huì)在觸碰到樹的右邊緣時(shí)回卷,因此在右邊鄰近開始搜索也是沒有問題的.
* 注意move-and-climb操作確保了我們不能在葉子層右邊的節(jié)點(diǎn)上結(jié)束.
*
* For example, consider this tree:
* 例如,考慮下面這棵樹:
*
* 7
* 7 6
* 5 7 6 5
* 4 5 5 7 2 6 5 2
* T
*
* Assume that the target node is the node indicated by the letter T,
* and we're searching for a node with value of 6 or higher. The search
* begins at T. At the first iteration, we move to the right, then to the
* parent, arriving at the rightmost 5. At the second iteration, we move
* to the right, wrapping around, then climb up, arriving at the 7 on the
* third level. 7 satisfies our search, so we descend down to the bottom,
* following the path of sevens. This is in fact the first suitable page
* to the right of (allowing for wraparound) our start point.
* 假定目標(biāo)節(jié)點(diǎn)是字母T指示的節(jié)點(diǎn),同時(shí)我們正在使用6或更大的數(shù)字搜索節(jié)點(diǎn).檢索從T開始.
* 在第一輪迭代,移到右邊,然后到父節(jié)點(diǎn),到達(dá)最右邊的節(jié)點(diǎn) 5.在第二輪迭代,移到右邊,回卷,
* 然后上溯,在第三個(gè)層次上到達(dá)節(jié)點(diǎn) 7這時(shí)候7滿足我們的搜索要求,
* 因此我們沿著7這條路徑下降到底部.
* 實(shí)際上,這是(考慮到回卷)起點(diǎn)右側(cè)第一個(gè)滿足條件的頁(yè)面.
*----------
*/
nodeno = target;
while (nodeno > 0)
{
if (fsmpage->fp_nodes[nodeno] >= minvalue)
break;
/*
* Move to the right, wrapping around on same level if necessary, then
* climb up.
* 移動(dòng)到右邊,如需要在同一層次上回卷,然后上溯.
*/
nodeno = parentof(rightneighbor(nodeno));
}
/*
* We're now at a node with enough free space, somewhere in the middle of
* the tree. Descend to the bottom, following a path with enough free
* space, preferring to move left if there's a choice.
* 現(xiàn)在已到達(dá)了有足夠空閑空間的節(jié)點(diǎn),樹中間的某個(gè)位置上面.
* 沿著有足夠空閑空間的路徑下降到底部,如有選擇,往左移動(dòng).
*/
while (nodeno < NonLeafNodesPerPage)
{
//左樹節(jié)點(diǎn)
int childnodeno = leftchild(nodeno);
if (childnodeno < NodesPerPage &&
fsmpage->fp_nodes[childnodeno] >= minvalue)
{
//如有機(jī)會(huì),往左移動(dòng)
nodeno = childnodeno;
continue;
}
//指向右樹節(jié)點(diǎn)
childnodeno++; /* point to right child */
if (childnodeno < NodesPerPage &&
fsmpage->fp_nodes[childnodeno] >= minvalue)
{
//相當(dāng)于下降了一層
nodeno = childnodeno;
}
else
{
/*
* Oops. The parent node promised that either left or right child
* has enough space, but neither actually did. This can happen in
* case of a "torn page", IOW if we crashed earlier while writing
* the page to disk, and only part of the page made it to disk.
* 父節(jié)點(diǎn)承諾了不是左樹就是右樹有足夠的空間,但實(shí)際上并不是這樣.
* 這會(huì)發(fā)生在"torn page"的情況下,在寫入page到磁盤上時(shí)系統(tǒng)崩潰,
* page只有一部分寫入到磁盤中.
*
* Fix the corruption and restart.
* 修復(fù)損壞并重啟.
*/
RelFileNode rnode;
ForkNumber forknum;
BlockNumber blknum;
//獲取tag
BufferGetTag(buf, &rnode, &forknum, &blknum);
elog(DEBUG1, "fixing corrupt FSM block %u, relation %u/%u/%u",
blknum, rnode.spcNode, rnode.dbNode, rnode.relNode);
/* make sure we hold an exclusive lock */
//確保持有獨(dú)占鎖
if (!exclusive_lock_held)
{
LockBuffer(buf, BUFFER_LOCK_UNLOCK);
LockBuffer(buf, BUFFER_LOCK_EXCLUSIVE);
exclusive_lock_held = true;
}
//重建FSM
fsm_rebuild_page(page);
MarkBufferDirtyHint(buf, false);
//重新搜索
goto restart;
}
}
/* We're now at the bottom level, at a node with enough space. */
//現(xiàn)在已到底層,在有足夠空間的節(jié)點(diǎn)上.
slot = nodeno - NonLeafNodesPerPage;
/*
* Update the next-target pointer. Note that we do this even if we're only
* holding a shared lock, on the grounds that it's better to use a shared
* lock and get a garbled next pointer every now and then, than take the
* concurrency hit of an exclusive lock.
* 更新下一個(gè)目標(biāo)塊指針.
* 注意:就算我們只持有共享鎖,也可以做這個(gè)事情,
* 基于這樣的理由,最好是使用共享鎖,時(shí)不時(shí)的獲取一個(gè)打亂的下一個(gè)指針,
* 這樣比持有獨(dú)占鎖要好.
*
* Wrap-around is handled at the beginning of this function.
* 在該函數(shù)的開始,回卷已處理.
*/
fsmpage->fp_next_slot = slot + (advancenext ? 1 : 0);
return slot;
}
測(cè)試腳本
15:54:13 (xdb@[local]:5432)testdb=# insert into t1 values (1,'1','1');
啟動(dòng)gdb,設(shè)置斷點(diǎn)
(gdb) b fsm_set_and_search
Breakpoint 1 at 0x888850: file freespace.c, line 676.
(gdb) c
Continuing.
Breakpoint 1, fsm_set_and_search (rel=0x7fd0d2f10788, addr=..., slot=5, newValue=0 '\000', minValue=1 '\001')
at freespace.c:676
676 int newslot = -1;
(gdb)
輸入?yún)?shù)
(gdb) p *rel
$1 = {rd_node = {spcNode = 1663, dbNode = 16402, relNode = 50820}, rd_smgr = 0x1233b00, rd_refcnt = 1, rd_backend = -1,
rd_islocaltemp = false, rd_isnailed = false, rd_isvalid = true, rd_indexvalid = 1 '\001', rd_statvalid = false,
rd_createSubid = 0, rd_newRelfilenodeSubid = 0, rd_rel = 0x7fd0d2f109a0, rd_att = 0x7fd0d2f10ab8, rd_id = 50820,
rd_lockInfo = {lockRelId = {relId = 50820, dbId = 16402}}, rd_rules = 0x0, rd_rulescxt = 0x0, trigdesc = 0x0,
rd_rsdesc = 0x0, rd_fkeylist = 0x0, rd_fkeyvalid = false, rd_partkeycxt = 0x0, rd_partkey = 0x0, rd_pdcxt = 0x0,
rd_partdesc = 0x0, rd_partcheck = 0x0, rd_indexlist = 0x7fd0d2f0f820, rd_oidindex = 0, rd_pkindex = 0,
rd_replidindex = 0, rd_statlist = 0x0, rd_indexattr = 0x0, rd_projindexattr = 0x0, rd_keyattr = 0x0, rd_pkattr = 0x0,
rd_idattr = 0x0, rd_projidx = 0x0, rd_pubactions = 0x0, rd_options = 0x0, rd_index = 0x0, rd_indextuple = 0x0,
rd_amhandler = 0, rd_indexcxt = 0x0, rd_amroutine = 0x0, rd_opfamily = 0x0, rd_opcintype = 0x0, rd_support = 0x0,
rd_supportinfo = 0x0, rd_indoption = 0x0, rd_indexprs = 0x0, rd_indpred = 0x0, rd_exclops = 0x0, rd_exclprocs = 0x0,
rd_exclstrats = 0x0, rd_amcache = 0x0, rd_indcollation = 0x0, rd_fdwroutine = 0x0, rd_toastoid = 0,
pgstat_info = 0x12275f0}
(gdb)
(gdb) p addr
$2 = {level = 0, logpageno = 0}
獲取buffere,并鎖定
(gdb) n
678 buf = fsm_readbuf(rel, addr, true);
(gdb)
679 LockBuffer(buf, BUFFER_LOCK_EXCLUSIVE);
(gdb) p buf
$3 = 105
(gdb)
獲取page
(gdb) p page
$4 = (Page) 0x7fd0bf41dc00 ""
(gdb) p *page
$5 = 0 '\000'
調(diào)用fsm_search_avail函數(shù),進(jìn)入fsm_search_avail
(gdb) n
684 MarkBufferDirtyHint(buf, false);
(gdb)
686 if (minValue != 0)
(gdb)
690 addr.level == FSM_BOTTOM_LEVEL,
(gdb) step
689 newslot = fsm_search_avail(buf, minValue,
(gdb)
fsm_search_avail (buf=105, minvalue=1 '\001', advancenext=true, exclusive_lock_held=true) at fsmpage.c:161
161 Page page = BufferGetPage(buf);
(gdb)
獲取FSMPage,fp_nodes數(shù)組,0表示未使用
(gdb) n
162 FSMPage fsmpage = (FSMPage) PageGetContents(page);
(gdb) p page
$6 = (Page) 0x7fd0bf41dc00 ""
(gdb) n
173 if (fsmpage->fp_nodes[0] < minvalue)
(gdb) p *fsmpage
$7 = {fp_next_slot = 6, fp_nodes = 0x7fd0bf41dc1c "{{"}
(gdb) p *fsmpage->fp_nodes
$8 = 123 '{'
(gdb) p fsmpage->fp_nodes[0]
$9 = 123 '{'
(gdb) p fsmpage->fp_nodes[1]
$10 = 123 '{'
(gdb) p fsmpage->fp_nodes[2]
$11 = 0 '\000'
(gdb) p fsmpage->fp_nodes[3]
$12 = 123 '{'
(gdb) p fsmpage->fp_nodes[4]
$13 = 0 '\000'
(gdb) p fsmpage->fp_nodes[5]
$14 = 0 '\000'
(gdb) p fsmpage->fp_nodes[6]
$15 = 0 '\000'
使用fp_next_slot開始搜索.
從目標(biāo)slot開始檢索.每一步,把節(jié)點(diǎn)移到右邊,然后上溯父節(jié)點(diǎn).
在到達(dá)一個(gè)有足夠空閑空間的節(jié)點(diǎn)時(shí)停止(因?yàn)楦?jié)點(diǎn)有足夠的空間).
(gdb) n
181 target = fsmpage->fp_next_slot;
(gdb)
182 if (target < 0 || target >= LeafNodesPerPage)
(gdb) p target
$16 = 6
(gdb) p LeafNodesPerPage
No symbol "__builtin_offsetof" in current context.
(gdb) n
184 target += NonLeafNodesPerPage;
(gdb)
227 nodeno = target;
(gdb) p target
$17 = 4101
(gdb)
循環(huán),直至找到滿足條件的節(jié)點(diǎn).
方法是移動(dòng)到右邊,如需要在同一層次上回卷,然后上溯.
(gdb) p fsmpage->fp_nodes[nodeno]
$19 = 0 '\000'
(gdb) p minvalue
$20 = 1 '\001'
(gdb) n
237 nodeno = parentof(rightneighbor(nodeno));
(gdb) n
228 while (nodeno > 0)
(gdb) p nodeno
$21 = 2050
(gdb) n
230 if (fsmpage->fp_nodes[nodeno] >= minvalue)
(gdb) fsmpage->fp_nodes[nodeno]
Undefined command: "fsmpage->fp_nodes". Try "help".
(gdb) p fsmpage->fp_nodes[nodeno]
$22 = 0 '\000'
(gdb) n
237 nodeno = parentof(rightneighbor(nodeno));
(gdb)
228 while (nodeno > 0)
(gdb)
230 if (fsmpage->fp_nodes[nodeno] >= minvalue)
(gdb) p nodeno
$23 = 1025
(gdb) n
231 break;
(gdb) p fsmpage->fp_nodes[nodeno]
$24 = 1 '\001'
(gdb)
現(xiàn)在已到達(dá)了有足夠空閑空間的節(jié)點(diǎn),樹中間的某個(gè)位置上面.
沿著有足夠空閑空間的路徑下降到底部.
如有選擇,往左移動(dòng).本例,往左移動(dòng)了.
(gdb) n
245 while (nodeno < NonLeafNodesPerPage)
(gdb) p nodeno
$25 = 1025
(gdb) n
247 int childnodeno = leftchild(nodeno);
(gdb)
249 if (childnodeno < NodesPerPage &&
(gdb) p childnodeno
$26 = 2051
(gdb) n
250 fsmpage->fp_nodes[childnodeno] >= minvalue)
(gdb) p fsmpage->fp_nodes[childnodeno]
$27 = 1 '\001'
(gdb) n
249 if (childnodeno < NodesPerPage &&
(gdb)
252 nodeno = childnodeno;
(gdb)
253 continue;
(gdb)
找到了相應(yīng)的葉子節(jié)點(diǎn)
(gdb)
245 while (nodeno < NonLeafNodesPerPage)
(gdb) n
247 int childnodeno = leftchild(nodeno);
(gdb)
249 if (childnodeno < NodesPerPage &&
(gdb)
250 fsmpage->fp_nodes[childnodeno] >= minvalue)
(gdb)
249 if (childnodeno < NodesPerPage &&
(gdb)
255 childnodeno++; /* point to right child */
(gdb)
256 if (childnodeno < NodesPerPage &&
(gdb) p childnodeno
$28 = 4104
(gdb) n
257 fsmpage->fp_nodes[childnodeno] >= minvalue)
(gdb)
256 if (childnodeno < NodesPerPage &&
(gdb)
259 nodeno = childnodeno;
(gdb) p childnodeno
$29 = 4104
(gdb) n
245 while (nodeno < NonLeafNodesPerPage)
(gdb)
現(xiàn)在已到底層,在有足夠空間的節(jié)點(diǎn)上.
同時(shí),更新下一個(gè)目標(biāo)塊指針.
(gdb)
293 slot = nodeno - NonLeafNodesPerPage;
(gdb) n
303 fsmpage->fp_next_slot = slot + (advancenext ? 1 : 0);
(gdb) p slot
$30 = 9
(gdb) p nodeno
$31 = 4104
(gdb) n
305 return slot;
(gdb)
306 }
(gdb)
回到fsm_set_and_search,返回slot
(gdb)
fsm_set_and_search (rel=0x7fd0d2f10788, addr=..., slot=5, newValue=0 '\000', minValue=1 '\001') at freespace.c:694
694 UnlockReleaseBuffer(buf);
(gdb)
696 return newslot;
(gdb)
(gdb) p newslot
$32 = 9
(gdb)
DONE!
PG Source Code
Database Cluster, Databases, and Tables
