PostgreSQL Source Code  git master
freepage.h File Reference
#include "storage/lwlock.h"
#include "utils/relptr.h"
Include dependency graph for freepage.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  FreePageManager
 

Macros

#define FPM_PAGE_SIZE   4096
 
#define FPM_NUM_FREELISTS   129
 
#define fpm_page_to_pointer(base, page)
 
#define fpm_pointer_to_page(base, ptr)   (((Size) (((char *) (ptr)) - (base))) / FPM_PAGE_SIZE)
 
#define fpm_size_to_pages(sz)   (((sz) + FPM_PAGE_SIZE - 1) / FPM_PAGE_SIZE)
 
#define fpm_pointer_is_page_aligned(base, ptr)   (((Size) (((char *) (ptr)) - (base))) % FPM_PAGE_SIZE == 0)
 
#define fpm_relptr_is_page_aligned(base, relptr)   ((relptr).relptr_off % FPM_PAGE_SIZE == 0)
 
#define fpm_segment_base(fpm)   (((char *) fpm) - fpm->self.relptr_off)
 
#define fpm_largest(fpm)   (fpm->contiguous_pages)
 

Typedefs

typedef struct FreePageSpanLeader FreePageSpanLeader
 
typedef struct FreePageBtree FreePageBtree
 
typedef struct FreePageManager FreePageManager
 

Functions

 relptr_declare (FreePageBtree, RelptrFreePageBtree)
 
 relptr_declare (FreePageManager, RelptrFreePageManager)
 
 relptr_declare (FreePageSpanLeader, RelptrFreePageSpanLeader)
 
void FreePageManagerInitialize (FreePageManager *fpm, char *base)
 
bool FreePageManagerGet (FreePageManager *fpm, Size npages, Size *first_page)
 
void FreePageManagerPut (FreePageManager *fpm, Size first_page, Size npages)
 
char * FreePageManagerDump (FreePageManager *fpm)
 

Macro Definition Documentation

◆ fpm_largest

#define fpm_largest (   fpm)    (fpm->contiguous_pages)

Definition at line 88 of file freepage.h.

Referenced by destroy_superblock(), dsa_dump(), and get_best_segment().

◆ FPM_NUM_FREELISTS

◆ FPM_PAGE_SIZE

◆ fpm_page_to_pointer

#define fpm_page_to_pointer (   base,
  page 
)
Value:
(base) + FPM_PAGE_SIZE * (page))
#define AssertVariableIsOfTypeMacro(varname, typename)
Definition: c.h:782
#define FPM_PAGE_SIZE
Definition: freepage.h:30
size_t Size
Definition: c.h:404

Definition at line 67 of file freepage.h.

Referenced by FreePageBtreeRecycle(), FreePageManagerPutInternal(), FreePagePopSpanLeader(), and FreePagePushSpanLeader().

◆ fpm_pointer_is_page_aligned

#define fpm_pointer_is_page_aligned (   base,
  ptr 
)    (((Size) (((char *) (ptr)) - (base))) % FPM_PAGE_SIZE == 0)

Definition at line 78 of file freepage.h.

Referenced by FreePageBtreeGetRecycled().

◆ fpm_pointer_to_page

#define fpm_pointer_to_page (   base,
  ptr 
)    (((Size) (((char *) (ptr)) - (base))) / FPM_PAGE_SIZE)

◆ fpm_relptr_is_page_aligned

#define fpm_relptr_is_page_aligned (   base,
  relptr 
)    ((relptr).relptr_off % FPM_PAGE_SIZE == 0)

Definition at line 80 of file freepage.h.

◆ fpm_segment_base

◆ fpm_size_to_pages

#define fpm_size_to_pages (   sz)    (((sz) + FPM_PAGE_SIZE - 1) / FPM_PAGE_SIZE)

Definition at line 74 of file freepage.h.

Referenced by dsa_allocate_extended().

Typedef Documentation

◆ FreePageBtree

Definition at line 22 of file freepage.h.

◆ FreePageManager

Definition at line 23 of file freepage.h.

◆ FreePageSpanLeader

Definition at line 21 of file freepage.h.

Function Documentation

◆ FreePageManagerDump()

char* FreePageManagerDump ( FreePageManager fpm)

Definition at line 424 of file freepage.c.

References appendStringInfo(), appendStringInfoString(), FreePageManager::btree_depth, FreePageManager::btree_recycle, FreePageManager::btree_root, buf, FreePageManager::contiguous_pages, StringInfoData::data, FPM_NUM_FREELISTS, fpm_segment_base, FreePageManager::freelist, FreePageManagerDumpBtree(), FreePageManagerDumpSpans(), initStringInfo(), relptr_access, relptr_is_null, FreePageManager::self, FreePageManager::singleton_first_page, and FreePageManager::singleton_npages.

425 {
426  char *base = fpm_segment_base(fpm);
428  FreePageSpanLeader *recycle;
429  bool dumped_any_freelist = false;
430  Size f;
431 
432  /* Initialize output buffer. */
433  initStringInfo(&buf);
434 
435  /* Dump general stuff. */
436  appendStringInfo(&buf, "metadata: self %zu max contiguous pages = %zu\n",
437  fpm->self.relptr_off, fpm->contiguous_pages);
438 
439  /* Dump btree. */
440  if (fpm->btree_depth > 0)
441  {
442  FreePageBtree *root;
443 
444  appendStringInfo(&buf, "btree depth %u:\n", fpm->btree_depth);
445  root = relptr_access(base, fpm->btree_root);
446  FreePageManagerDumpBtree(fpm, root, NULL, 0, &buf);
447  }
448  else if (fpm->singleton_npages > 0)
449  {
450  appendStringInfo(&buf, "singleton: %zu(%zu)\n",
452  }
453 
454  /* Dump btree recycle list. */
455  recycle = relptr_access(base, fpm->btree_recycle);
456  if (recycle != NULL)
457  {
458  appendStringInfoString(&buf, "btree recycle:");
459  FreePageManagerDumpSpans(fpm, recycle, 1, &buf);
460  }
461 
462  /* Dump free lists. */
463  for (f = 0; f < FPM_NUM_FREELISTS; ++f)
464  {
465  FreePageSpanLeader *span;
466 
467  if (relptr_is_null(fpm->freelist[f]))
468  continue;
469  if (!dumped_any_freelist)
470  {
471  appendStringInfoString(&buf, "freelists:\n");
472  dumped_any_freelist = true;
473  }
474  appendStringInfo(&buf, " %zu:", f + 1);
475  span = relptr_access(base, fpm->freelist[f]);
476  FreePageManagerDumpSpans(fpm, span, f + 1, &buf);
477  }
478 
479  /* And return result to caller. */
480  return buf.data;
481 }
#define relptr_is_null(rp)
Definition: relptr.h:56
RelptrFreePageBtree btree_root
Definition: freepage.h:51
RelptrFreePageSpanLeader btree_recycle
Definition: freepage.h:52
Size singleton_npages
Definition: freepage.h:56
Size contiguous_pages
Definition: freepage.h:57
Size singleton_first_page
Definition: freepage.h:55
void appendStringInfo(StringInfo str, const char *fmt,...)
Definition: stringinfo.c:78
#define relptr_access(base, rp)
Definition: relptr.h:51
#define FPM_NUM_FREELISTS
Definition: freepage.h:40
void appendStringInfoString(StringInfo str, const char *s)
Definition: stringinfo.c:157
static char * buf
Definition: pg_test_fsync.c:67
static void FreePageManagerDumpBtree(FreePageManager *fpm, FreePageBtree *btp, FreePageBtree *parent, int level, StringInfo buf)
Definition: freepage.c:1250
unsigned btree_depth
Definition: freepage.h:53
void initStringInfo(StringInfo str)
Definition: stringinfo.c:46
RelptrFreePageManager self
Definition: freepage.h:50
RelptrFreePageSpanLeader freelist[FPM_NUM_FREELISTS]
Definition: freepage.h:59
size_t Size
Definition: c.h:404
static void FreePageManagerDumpSpans(FreePageManager *fpm, FreePageSpanLeader *span, Size expected_pages, StringInfo buf)
Definition: freepage.c:1296
#define fpm_segment_base(fpm)
Definition: freepage.h:84

◆ FreePageManagerGet()

bool FreePageManagerGet ( FreePageManager fpm,
Size  npages,
Size first_page 
)

Definition at line 210 of file freepage.c.

References Assert, FreePageManager::btree_depth, FreePageManager::btree_recycle, FreePageManager::btree_root, FreePageBtreeInternalKey::child, FreePageManager::contiguous_pages, FPM_NUM_FREELISTS, fpm_segment_base, FREE_PAGE_INTERNAL_MAGIC, FREE_PAGE_LEAF_MAGIC, FreePageManager::freelist, FreePageBtreeCleanup(), FreePageManagerGetInternal(), FreePageManagerLargestContiguous(), FreePageManagerUpdateLargest(), FreePageBtree::hdr, FreePageBtree::internal_key, sort-test::list, FreePageBtreeHeader::magic, FreePageSpanLeader::next, FreePageSpanLeader::npages, FreePageBtreeHeader::nused, relptr_access, relptr_is_null, and FreePageBtree::u.

Referenced by dsa_allocate_extended(), and ensure_active_superblock().

211 {
212  bool result;
213  Size contiguous_pages;
214 
215  result = FreePageManagerGetInternal(fpm, npages, first_page);
216 
217  /*
218  * It's a bit counterintuitive, but allocating pages can actually create
219  * opportunities for cleanup that create larger ranges. We might pull a
220  * key out of the btree that enables the item at the head of the btree
221  * recycle list to be inserted; and then if there are more items behind it
222  * one of those might cause two currently-separated ranges to merge,
223  * creating a single range of contiguous pages larger than any that
224  * existed previously. It might be worth trying to improve the cleanup
225  * algorithm to avoid such corner cases, but for now we just notice the
226  * condition and do the appropriate reporting.
227  */
228  contiguous_pages = FreePageBtreeCleanup(fpm);
229  if (fpm->contiguous_pages < contiguous_pages)
230  fpm->contiguous_pages = contiguous_pages;
231 
232  /*
233  * FreePageManagerGetInternal may have set contiguous_pages_dirty.
234  * Recompute contigous_pages if so.
235  */
237 
238 #ifdef FPM_EXTRA_ASSERTS
239  if (result)
240  {
241  Assert(fpm->free_pages >= npages);
242  fpm->free_pages -= npages;
243  }
244  Assert(fpm->free_pages == sum_free_pages(fpm));
246 #endif
247  return result;
248 }
static Size FreePageManagerLargestContiguous(FreePageManager *fpm)
Definition: freepage.c:324
static void FreePageManagerUpdateLargest(FreePageManager *fpm)
Definition: freepage.c:366
Size contiguous_pages
Definition: freepage.h:57
static Size FreePageBtreeCleanup(FreePageManager *fpm)
Definition: freepage.c:580
static bool FreePageManagerGetInternal(FreePageManager *fpm, Size npages, Size *first_page)
Definition: freepage.c:1319
#define Assert(condition)
Definition: c.h:670
size_t Size
Definition: c.h:404

◆ FreePageManagerInitialize()

void FreePageManagerInitialize ( FreePageManager fpm,
char *  base 
)

Definition at line 183 of file freepage.c.

References FreePageManager::btree_depth, FreePageManager::btree_recycle, FreePageManager::btree_recycle_count, FreePageManager::btree_root, FreePageManager::contiguous_pages, FreePageManager::contiguous_pages_dirty, FPM_NUM_FREELISTS, FreePageManager::freelist, relptr_store, FreePageManager::self, FreePageManager::singleton_first_page, and FreePageManager::singleton_npages.

Referenced by create_internal(), and make_new_segment().

184 {
185  Size f;
186 
187  relptr_store(base, fpm->self, fpm);
188  relptr_store(base, fpm->btree_root, (FreePageBtree *) NULL);
189  relptr_store(base, fpm->btree_recycle, (FreePageSpanLeader *) NULL);
190  fpm->btree_depth = 0;
191  fpm->btree_recycle_count = 0;
192  fpm->singleton_first_page = 0;
193  fpm->singleton_npages = 0;
194  fpm->contiguous_pages = 0;
195  fpm->contiguous_pages_dirty = true;
196 #ifdef FPM_EXTRA_ASSERTS
197  fpm->free_pages = 0;
198 #endif
199 
200  for (f = 0; f < FPM_NUM_FREELISTS; f++)
201  relptr_store(base, fpm->freelist[f], (FreePageSpanLeader *) NULL);
202 }
#define relptr_store(base, rp, val)
Definition: relptr.h:69
RelptrFreePageBtree btree_root
Definition: freepage.h:51
RelptrFreePageSpanLeader btree_recycle
Definition: freepage.h:52
Size singleton_npages
Definition: freepage.h:56
Size contiguous_pages
Definition: freepage.h:57
Size singleton_first_page
Definition: freepage.h:55
#define FPM_NUM_FREELISTS
Definition: freepage.h:40
unsigned btree_depth
Definition: freepage.h:53
bool contiguous_pages_dirty
Definition: freepage.h:58
RelptrFreePageManager self
Definition: freepage.h:50
RelptrFreePageSpanLeader freelist[FPM_NUM_FREELISTS]
Definition: freepage.h:59
size_t Size
Definition: c.h:404
unsigned btree_recycle_count
Definition: freepage.h:54

◆ FreePageManagerPut()

void FreePageManagerPut ( FreePageManager fpm,
Size  first_page,
Size  npages 
)

Definition at line 379 of file freepage.c.

References Assert, FreePageManager::contiguous_pages, FreePageBtreeCleanup(), FreePageManagerLargestContiguous(), FreePageManagerPutInternal(), FreePageManagerUpdateLargest(), and FreePageSpanLeader::npages.

Referenced by create_internal(), destroy_superblock(), dsa_free(), and make_new_segment().

380 {
381  Size contiguous_pages;
382 
383  Assert(npages > 0);
384 
385  /* Record the new pages. */
386  contiguous_pages =
387  FreePageManagerPutInternal(fpm, first_page, npages, false);
388 
389  /*
390  * If the new range we inserted into the page manager was contiguous with
391  * an existing range, it may have opened up cleanup opportunities.
392  */
393  if (contiguous_pages > npages)
394  {
395  Size cleanup_contiguous_pages;
396 
397  cleanup_contiguous_pages = FreePageBtreeCleanup(fpm);
398  if (cleanup_contiguous_pages > contiguous_pages)
399  contiguous_pages = cleanup_contiguous_pages;
400  }
401 
402  /* See if we now have a new largest chunk. */
403  if (fpm->contiguous_pages < contiguous_pages)
404  fpm->contiguous_pages = contiguous_pages;
405 
406  /*
407  * The earlier call to FreePageManagerPutInternal may have set
408  * contiguous_pages_dirty if it needed to allocate internal pages, so
409  * recompute contiguous_pages if necessary.
410  */
412 
413 #ifdef FPM_EXTRA_ASSERTS
414  fpm->free_pages += npages;
415  Assert(fpm->free_pages == sum_free_pages(fpm));
417 #endif
418 }
static Size FreePageManagerLargestContiguous(FreePageManager *fpm)
Definition: freepage.c:324
static void FreePageManagerUpdateLargest(FreePageManager *fpm)
Definition: freepage.c:366
static Size FreePageManagerPutInternal(FreePageManager *fpm, Size first_page, Size npages, bool soft)
Definition: freepage.c:1478
Size contiguous_pages
Definition: freepage.h:57
static Size FreePageBtreeCleanup(FreePageManager *fpm)
Definition: freepage.c:580
#define Assert(condition)
Definition: c.h:670
size_t Size
Definition: c.h:404

◆ relptr_declare() [1/3]

relptr_declare ( FreePageBtree  ,
RelptrFreePageBtree   
)

◆ relptr_declare() [2/3]

relptr_declare ( FreePageManager  ,
RelptrFreePageManager   
)

◆ relptr_declare() [3/3]

relptr_declare ( FreePageSpanLeader  ,
RelptrFreePageSpanLeader   
)