PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
fsmpage.c File Reference
#include "postgres.h"
#include "storage/bufmgr.h"
#include "storage/fsm_internals.h"
Include dependency graph for fsmpage.c:

Go to the source code of this file.

Macros

#define leftchild(x)   (2 * (x) + 1)
 
#define rightchild(x)   (2 * (x) + 2)
 
#define parentof(x)   (((x) - 1) / 2)
 

Functions

static int rightneighbor (int x)
 
bool fsm_set_avail (Page page, int slot, uint8 value)
 
uint8 fsm_get_avail (Page page, int slot)
 
uint8 fsm_get_max_avail (Page page)
 
int fsm_search_avail (Buffer buf, uint8 minvalue, bool advancenext, bool exclusive_lock_held)
 
bool fsm_truncate_avail (Page page, int nslots)
 
bool fsm_rebuild_page (Page page)
 

Macro Definition Documentation

◆ leftchild

#define leftchild (   x)    (2 * (x) + 1)

Definition at line 29 of file fsmpage.c.

◆ parentof

#define parentof (   x)    (((x) - 1) / 2)

Definition at line 31 of file fsmpage.c.

◆ rightchild

#define rightchild (   x)    (2 * (x) + 2)

Definition at line 30 of file fsmpage.c.

Function Documentation

◆ fsm_get_avail()

uint8 fsm_get_avail ( Page  page,
int  slot 
)

Definition at line 122 of file fsmpage.c.

123{
124 FSMPage fsmpage = (FSMPage) PageGetContents(page);
125
126 Assert(slot < LeafNodesPerPage);
127
128 return fsmpage->fp_nodes[NonLeafNodesPerPage + slot];
129}
static char * PageGetContents(Page page)
Definition: bufpage.h:258
#define Assert(condition)
Definition: c.h:815
FSMPageData * FSMPage
Definition: fsm_internals.h:45
#define NonLeafNodesPerPage
Definition: fsm_internals.h:54
#define LeafNodesPerPage
Definition: fsm_internals.h:55
uint8 fp_nodes[FLEXIBLE_ARRAY_MEMBER]
Definition: fsm_internals.h:42

References Assert, FSMPageData::fp_nodes, LeafNodesPerPage, NonLeafNodesPerPage, and PageGetContents().

Referenced by fsm_vacuum_page(), and GetRecordedFreeSpace().

◆ fsm_get_max_avail()

uint8 fsm_get_max_avail ( Page  page)

Definition at line 138 of file fsmpage.c.

139{
140 FSMPage fsmpage = (FSMPage) PageGetContents(page);
141
142 return fsmpage->fp_nodes[0];
143}

References FSMPageData::fp_nodes, and PageGetContents().

Referenced by fsm_search(), and fsm_vacuum_page().

◆ fsm_rebuild_page()

bool fsm_rebuild_page ( Page  page)

Definition at line 342 of file fsmpage.c.

343{
344 FSMPage fsmpage = (FSMPage) PageGetContents(page);
345 bool changed = false;
346 int nodeno;
347
348 /*
349 * Start from the lowest non-leaf level, at last node, working our way
350 * backwards, through all non-leaf nodes at all levels, up to the root.
351 */
352 for (nodeno = NonLeafNodesPerPage - 1; nodeno >= 0; nodeno--)
353 {
354 int lchild = leftchild(nodeno);
355 int rchild = lchild + 1;
356 uint8 newvalue = 0;
357
358 /* The first few nodes we examine might have zero or one child. */
359 if (lchild < NodesPerPage)
360 newvalue = fsmpage->fp_nodes[lchild];
361
362 if (rchild < NodesPerPage)
363 newvalue = Max(newvalue,
364 fsmpage->fp_nodes[rchild]);
365
366 if (fsmpage->fp_nodes[nodeno] != newvalue)
367 {
368 fsmpage->fp_nodes[nodeno] = newvalue;
369 changed = true;
370 }
371 }
372
373 return changed;
374}
uint8_t uint8
Definition: c.h:486
#define Max(x, y)
Definition: c.h:955
#define NodesPerPage
Definition: fsm_internals.h:51
#define leftchild(x)
Definition: fsmpage.c:29

References FSMPageData::fp_nodes, leftchild, Max, NodesPerPage, NonLeafNodesPerPage, and PageGetContents().

Referenced by fsm_search_avail(), fsm_set_avail(), and fsm_truncate_avail().

◆ fsm_search_avail()

int fsm_search_avail ( Buffer  buf,
uint8  minvalue,
bool  advancenext,
bool  exclusive_lock_held 
)

Definition at line 158 of file fsmpage.c.

160{
161 Page page = BufferGetPage(buf);
162 FSMPage fsmpage = (FSMPage) PageGetContents(page);
163 int nodeno;
164 int target;
165 uint16 slot;
166
167restart:
168
169 /*
170 * Check the root first, and exit quickly if there's no leaf with enough
171 * free space
172 */
173 if (fsmpage->fp_nodes[0] < minvalue)
174 return -1;
175
176 /*
177 * Start search using fp_next_slot. It's just a hint, so check that it's
178 * sane. (This also handles wrapping around when the prior call returned
179 * the last slot on the page.)
180 */
181 target = fsmpage->fp_next_slot;
182 if (target < 0 || target >= LeafNodesPerPage)
183 target = 0;
184 target += NonLeafNodesPerPage;
185
186 /*----------
187 * Start the search from the target slot. At every step, move one
188 * node to the right, then climb up to the parent. Stop when we reach
189 * a node with enough free space (as we must, since the root has enough
190 * space).
191 *
192 * The idea is to gradually expand our "search triangle", that is, all
193 * nodes covered by the current node, and to be sure we search to the
194 * right from the start point. At the first step, only the target slot
195 * is examined. When we move up from a left child to its parent, we are
196 * adding the right-hand subtree of that parent to the search triangle.
197 * When we move right then up from a right child, we are dropping the
198 * current search triangle (which we know doesn't contain any suitable
199 * page) and instead looking at the next-larger-size triangle to its
200 * right. So we never look left from our original start point, and at
201 * each step the size of the search triangle doubles, ensuring it takes
202 * only log2(N) work to search N pages.
203 *
204 * The "move right" operation will wrap around if it hits the right edge
205 * of the tree, so the behavior is still good if we start near the right.
206 * Note also that the move-and-climb behavior ensures that we can't end
207 * up on one of the missing nodes at the right of the leaf level.
208 *
209 * For example, consider this tree:
210 *
211 * 7
212 * 7 6
213 * 5 7 6 5
214 * 4 5 5 7 2 6 5 2
215 * T
216 *
217 * Assume that the target node is the node indicated by the letter T,
218 * and we're searching for a node with value of 6 or higher. The search
219 * begins at T. At the first iteration, we move to the right, then to the
220 * parent, arriving at the rightmost 5. At the second iteration, we move
221 * to the right, wrapping around, then climb up, arriving at the 7 on the
222 * third level. 7 satisfies our search, so we descend down to the bottom,
223 * following the path of sevens. This is in fact the first suitable page
224 * to the right of (allowing for wraparound) our start point.
225 *----------
226 */
227 nodeno = target;
228 while (nodeno > 0)
229 {
230 if (fsmpage->fp_nodes[nodeno] >= minvalue)
231 break;
232
233 /*
234 * Move to the right, wrapping around on same level if necessary, then
235 * climb up.
236 */
237 nodeno = parentof(rightneighbor(nodeno));
238 }
239
240 /*
241 * We're now at a node with enough free space, somewhere in the middle of
242 * the tree. Descend to the bottom, following a path with enough free
243 * space, preferring to move left if there's a choice.
244 */
245 while (nodeno < NonLeafNodesPerPage)
246 {
247 int childnodeno = leftchild(nodeno);
248
249 if (childnodeno < NodesPerPage &&
250 fsmpage->fp_nodes[childnodeno] >= minvalue)
251 {
252 nodeno = childnodeno;
253 continue;
254 }
255 childnodeno++; /* point to right child */
256 if (childnodeno < NodesPerPage &&
257 fsmpage->fp_nodes[childnodeno] >= minvalue)
258 {
259 nodeno = childnodeno;
260 }
261 else
262 {
263 /*
264 * Oops. The parent node promised that either left or right child
265 * has enough space, but neither actually did. This can happen in
266 * case of a "torn page", IOW if we crashed earlier while writing
267 * the page to disk, and only part of the page made it to disk.
268 *
269 * Fix the corruption and restart.
270 */
271 RelFileLocator rlocator;
272 ForkNumber forknum;
273 BlockNumber blknum;
274
275 BufferGetTag(buf, &rlocator, &forknum, &blknum);
276 elog(DEBUG1, "fixing corrupt FSM block %u, relation %u/%u/%u",
277 blknum, rlocator.spcOid, rlocator.dbOid, rlocator.relNumber);
278
279 /* make sure we hold an exclusive lock */
280 if (!exclusive_lock_held)
281 {
284 exclusive_lock_held = true;
285 }
286 fsm_rebuild_page(page);
287 MarkBufferDirtyHint(buf, false);
288 goto restart;
289 }
290 }
291
292 /* We're now at the bottom level, at a node with enough space. */
293 slot = nodeno - NonLeafNodesPerPage;
294
295 /*
296 * Update the next-target pointer. Note that we do this even if we're only
297 * holding a shared lock, on the grounds that it's better to use a shared
298 * lock and get a garbled next pointer every now and then, than take the
299 * concurrency hit of an exclusive lock.
300 *
301 * Wrap-around is handled at the beginning of this function.
302 */
303 fsmpage->fp_next_slot = slot + (advancenext ? 1 : 0);
304
305 return slot;
306}
uint32 BlockNumber
Definition: block.h:31
void BufferGetTag(Buffer buffer, RelFileLocator *rlocator, ForkNumber *forknum, BlockNumber *blknum)
Definition: bufmgr.c:3745
void LockBuffer(Buffer buffer, int mode)
Definition: bufmgr.c:5100
void MarkBufferDirtyHint(Buffer buffer, bool buffer_std)
Definition: bufmgr.c:4930
#define BUFFER_LOCK_UNLOCK
Definition: bufmgr.h:189
static Page BufferGetPage(Buffer buffer)
Definition: bufmgr.h:396
#define BUFFER_LOCK_EXCLUSIVE
Definition: bufmgr.h:191
PageData * Page
Definition: bufpage.h:82
uint16_t uint16
Definition: c.h:487
#define DEBUG1
Definition: elog.h:30
#define elog(elevel,...)
Definition: elog.h:225
static int rightneighbor(int x)
Definition: fsmpage.c:37
bool fsm_rebuild_page(Page page)
Definition: fsmpage.c:342
#define parentof(x)
Definition: fsmpage.c:31
static char * buf
Definition: pg_test_fsync.c:72
ForkNumber
Definition: relpath.h:56
RelFileNumber relNumber

References buf, BUFFER_LOCK_EXCLUSIVE, BUFFER_LOCK_UNLOCK, BufferGetPage(), BufferGetTag(), RelFileLocator::dbOid, DEBUG1, elog, FSMPageData::fp_next_slot, FSMPageData::fp_nodes, fsm_rebuild_page(), LeafNodesPerPage, leftchild, LockBuffer(), MarkBufferDirtyHint(), NodesPerPage, NonLeafNodesPerPage, PageGetContents(), parentof, RelFileLocator::relNumber, rightneighbor(), and RelFileLocator::spcOid.

Referenced by fsm_search(), and fsm_set_and_search().

◆ fsm_set_avail()

bool fsm_set_avail ( Page  page,
int  slot,
uint8  value 
)

Definition at line 63 of file fsmpage.c.

64{
65 int nodeno = NonLeafNodesPerPage + slot;
66 FSMPage fsmpage = (FSMPage) PageGetContents(page);
67 uint8 oldvalue;
68
70
71 oldvalue = fsmpage->fp_nodes[nodeno];
72
73 /* If the value hasn't changed, we don't need to do anything */
74 if (oldvalue == value && value <= fsmpage->fp_nodes[0])
75 return false;
76
77 fsmpage->fp_nodes[nodeno] = value;
78
79 /*
80 * Propagate up, until we hit the root or a node that doesn't need to be
81 * updated.
82 */
83 do
84 {
85 uint8 newvalue = 0;
86 int lchild;
87 int rchild;
88
89 nodeno = parentof(nodeno);
90 lchild = leftchild(nodeno);
91 rchild = lchild + 1;
92
93 newvalue = fsmpage->fp_nodes[lchild];
94 if (rchild < NodesPerPage)
95 newvalue = Max(newvalue,
96 fsmpage->fp_nodes[rchild]);
97
98 oldvalue = fsmpage->fp_nodes[nodeno];
99 if (oldvalue == newvalue)
100 break;
101
102 fsmpage->fp_nodes[nodeno] = newvalue;
103 } while (nodeno > 0);
104
105 /*
106 * sanity check: if the new value is (still) higher than the value at the
107 * top, the tree is corrupt. If so, rebuild.
108 */
109 if (value > fsmpage->fp_nodes[0])
110 fsm_rebuild_page(page);
111
112 return true;
113}
static struct @162 value

References Assert, FSMPageData::fp_nodes, fsm_rebuild_page(), LeafNodesPerPage, leftchild, Max, NodesPerPage, NonLeafNodesPerPage, PageGetContents(), parentof, and value.

Referenced by fsm_search(), fsm_set_and_search(), fsm_vacuum_page(), and XLogRecordPageWithFreeSpace().

◆ fsm_truncate_avail()

bool fsm_truncate_avail ( Page  page,
int  nslots 
)

Definition at line 313 of file fsmpage.c.

314{
315 FSMPage fsmpage = (FSMPage) PageGetContents(page);
316 uint8 *ptr;
317 bool changed = false;
318
319 Assert(nslots >= 0 && nslots < LeafNodesPerPage);
320
321 /* Clear all truncated leaf nodes */
322 ptr = &fsmpage->fp_nodes[NonLeafNodesPerPage + nslots];
323 for (; ptr < &fsmpage->fp_nodes[NodesPerPage]; ptr++)
324 {
325 if (*ptr != 0)
326 changed = true;
327 *ptr = 0;
328 }
329
330 /* Fix upper nodes. */
331 if (changed)
332 fsm_rebuild_page(page);
333
334 return changed;
335}

References Assert, FSMPageData::fp_nodes, fsm_rebuild_page(), LeafNodesPerPage, NodesPerPage, NonLeafNodesPerPage, and PageGetContents().

Referenced by FreeSpaceMapPrepareTruncateRel().

◆ rightneighbor()

static int rightneighbor ( int  x)
static

Definition at line 37 of file fsmpage.c.

38{
39 /*
40 * Move right. This might wrap around, stepping to the leftmost node at
41 * the next level.
42 */
43 x++;
44
45 /*
46 * Check if we stepped to the leftmost node at next level, and correct if
47 * so. The leftmost nodes at each level are numbered x = 2^level - 1, so
48 * check if (x + 1) is a power of two, using a standard
49 * twos-complement-arithmetic trick.
50 */
51 if (((x + 1) & x) == 0)
52 x = parentof(x);
53
54 return x;
55}
int x
Definition: isn.c:70

References parentof, and x.

Referenced by fsm_search_avail().