src/backend/storage/freespace/freespace.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * freespace.c
   4  *        POSTGRES free space map for quickly finding free space in relations
   5  *
   6  *
   7  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  * IDENTIFICATION
  11  *        $PostgreSQL: pgsql/src/backend/storage/freespace/freespace.c,v 1.45 2005/05/29 04:23:04 tgl Exp $
  12  *
  13  *
  14  * NOTES:
  15  *
  16  * The only really interesting aspect of this code is the heuristics for
  17  * deciding how much information we can afford to keep about each relation,
  18  * given that we have a limited amount of workspace in shared memory.
  19  * These currently work as follows:
  20  *
  21  * The number of distinct relations tracked is limited by a configuration
  22  * variable (MaxFSMRelations).  When this would be exceeded, we discard the
  23  * least recently used relation.  A doubly-linked list with move-to-front
  24  * behavior keeps track of which relation is least recently used.
  25  *
  26  * For each known relation, we track the average request size given to
  27  * GetPageWithFreeSpace() as well as the most recent number of pages given
  28  * to RecordRelationFreeSpace().  The average request size is not directly
  29  * used in this module, but we expect VACUUM to use it to filter out
  30  * uninteresting amounts of space before calling RecordRelationFreeSpace().
  31  * The sum of the RRFS page counts is thus the total number of "interesting"
  32  * pages that we would like to track; this is called DesiredFSMPages.
  33  *
  34  * The number of pages actually tracked is limited by a configuration variable
  35  * (MaxFSMPages).  When this is less than DesiredFSMPages, each relation
  36  * gets to keep a fraction MaxFSMPages/DesiredFSMPages of its free pages.
  37  * We discard pages with less free space to reach this target.
  38  *
  39  * Actually, our space allocation is done in "chunks" of CHUNKPAGES pages,
  40  * with each relation guaranteed at least one chunk.  This reduces thrashing
  41  * of the storage allocations when there are small changes in the RRFS page
  42  * counts from one VACUUM to the next.  (XXX it might also be worthwhile to
  43  * impose some kind of moving-average smoothing on the RRFS page counts?)
  44  *
  45  * So the actual arithmetic is: for each relation compute myRequest as the
  46  * number of chunks needed to hold its RRFS page count (not counting the
  47  * first, guaranteed chunk); compute sumRequests as the sum of these values
  48  * over all relations; then for each relation figure its target allocation
  49  * as
  50  *                      1 + round(spareChunks * myRequest / sumRequests)
  51  * where spareChunks = totalChunks - numRels is the number of chunks we have
  52  * a choice what to do with.  We round off these numbers because truncating
  53  * all of them would waste significant space.  But because of roundoff, it's
  54  * possible for the last few relations to get less space than they should;
  55  * the target allocation must be checked against remaining available space.
  56  *
  57  *-------------------------------------------------------------------------
  58  */
  59 #include "postgres.h"
  60
  61 #include <errno.h>
  62 #include <limits.h>
  63 #include <math.h>
  64 #include <unistd.h>
  65
  66 #include "miscadmin.h"
  67 #include "storage/fd.h"
  68 #include "storage/freespace.h"
  69 #include "storage/itemptr.h"
  70 #include "storage/lwlock.h"
  71 #include "storage/shmem.h"
  72
  73
  74 /* Initial value for average-request moving average */
  75 #define INITIAL_AVERAGE ((Size) (BLCKSZ / 32))
  76
  77 /*
  78  * Number of pages and bytes per allocation chunk.      Indexes can squeeze 50%
  79  * more pages into the same space because they don't need to remember how much
  80  * free space on each page.  The nominal number of pages, CHUNKPAGES, is for
  81  * regular rels, and INDEXCHUNKPAGES is for indexes.  CHUNKPAGES should be
  82  * even so that no space is wasted in the index case.
  83  */
  84 #define CHUNKPAGES      16
  85 #define CHUNKBYTES      (CHUNKPAGES * sizeof(FSMPageData))
  86 #define INDEXCHUNKPAGES ((int) (CHUNKBYTES / sizeof(IndexFSMPageData)))
  87
  88
  89 /*
  90  * Typedefs and macros for items in the page-storage arena.  We use the
  91  * existing ItemPointer and BlockId data structures, which are designed
  92  * to pack well (they should be 6 and 4 bytes apiece regardless of machine
  93  * alignment issues).  Unfortunately we can't use the ItemPointer access
  94  * macros, because they include Asserts insisting that ip_posid != 0.
  95  */
  96 typedef ItemPointerData FSMPageData;
  97 typedef BlockIdData IndexFSMPageData;
  98
  99 #define FSMPageGetPageNum(ptr)  \
 100         BlockIdGetBlockNumber(&(ptr)->ip_blkid)
 101 #define FSMPageGetSpace(ptr)    \
 102         ((Size) (ptr)->ip_posid)
 103 #define FSMPageSetPageNum(ptr, pg)      \
 104         BlockIdSet(&(ptr)->ip_blkid, pg)
 105 #define FSMPageSetSpace(ptr, sz)        \
 106         ((ptr)->ip_posid = (OffsetNumber) (sz))
 107 #define IndexFSMPageGetPageNum(ptr) \
 108         BlockIdGetBlockNumber(ptr)
 109 #define IndexFSMPageSetPageNum(ptr, pg) \
 110         BlockIdSet(ptr, pg)
 111
 112 /*----------
 113  * During database shutdown, we store the contents of FSM into a disk file,
 114  * which is re-read during startup.  This way we don't have a startup
 115  * transient condition where FSM isn't really functioning.
 116  *
 117  * The file format is:
 118  *              label                   "FSM\0"
 119  *              endian                  constant 0x01020304 for detecting endianness problems
 120  *              version#
 121  *              numRels
 122  *      -- for each rel, in *reverse* usage order:
 123  *              relfilenode
 124  *              isIndex
 125  *              avgRequest
 126  *              lastPageCount
 127  *              storedPages
 128  *              arena data              array of storedPages FSMPageData or IndexFSMPageData
 129  *----------
 130  */
 131
 132 /* Name of FSM cache file (relative to $PGDATA) */
 133 #define FSM_CACHE_FILENAME      "global/pg_fsm.cache"
 134
 135 /* Fixed values in header */
 136 #define FSM_CACHE_LABEL         "FSM"
 137 #define FSM_CACHE_ENDIAN        0x01020304
 138 #define FSM_CACHE_VERSION       20030305
 139
 140 /* File header layout */
 141 typedef struct FsmCacheFileHeader
 142 {
 143         char            label[4];
 144         uint32          endian;
 145         uint32          version;
 146         int32           numRels;
 147 } FsmCacheFileHeader;
 148
 149 /* Per-relation header */
 150 typedef struct FsmCacheRelHeader
 151 {
 152         RelFileNode key;                        /* hash key (must be first) */
 153         bool            isIndex;                /* if true, we store only page numbers */
 154         uint32          avgRequest;             /* moving average of space requests */
 155         int32           lastPageCount;  /* pages passed to RecordRelationFreeSpace */
 156         int32           storedPages;    /* # of pages stored in arena */
 157 } FsmCacheRelHeader;
 158
 159
 160 /*
 161  * Shared free-space-map objects
 162  *
 163  * The per-relation objects are indexed by a hash table, and are also members
 164  * of two linked lists: one ordered by recency of usage (most recent first),
 165  * and the other ordered by physical location of the associated storage in
 166  * the page-info arena.
 167  *
 168  * Each relation owns one or more chunks of per-page storage in the "arena".
 169  * The chunks for each relation are always consecutive, so that it can treat
 170  * its page storage as a simple array.  We further insist that its page data
 171  * be ordered by block number, so that binary search is possible.
 172  *
 173  * Note: we handle pointers to these items as pointers, not as SHMEM_OFFSETs.
 174  * This assumes that all processes accessing the map will have the shared
 175  * memory segment mapped at the same place in their address space.
 176  */
 177 typedef struct FSMHeader FSMHeader;
 178 typedef struct FSMRelation FSMRelation;
 179
 180 /* Header for whole map */
 181 struct FSMHeader
 182 {
 183         FSMRelation *usageList;         /* FSMRelations in usage-recency order */
 184         FSMRelation *usageListTail; /* tail of usage-recency list */
 185         FSMRelation *firstRel;          /* FSMRelations in arena storage order */
 186         FSMRelation *lastRel;           /* tail of storage-order list */
 187         int                     numRels;                /* number of FSMRelations now in use */
 188         double          sumRequests;    /* sum of requested chunks over all rels */
 189         char       *arena;                      /* arena for page-info storage */
 190         int                     totalChunks;    /* total size of arena, in chunks */
 191         int                     usedChunks;             /* # of chunks assigned */
 192         /* NB: there are totalChunks - usedChunks free chunks at end of arena */
 193 };
 194
 195 /*
 196  * Per-relation struct --- this is an entry in the shared hash table.
 197  * The hash key is the RelFileNode value (hence, we look at the physical
 198  * relation ID, not the logical ID, which is appropriate).
 199  */
 200 struct FSMRelation
 201 {
 202         RelFileNode key;                        /* hash key (must be first) */
 203         FSMRelation *nextUsage;         /* next rel in usage-recency order */
 204         FSMRelation *priorUsage;        /* prior rel in usage-recency order */
 205         FSMRelation *nextPhysical;      /* next rel in arena-storage order */
 206         FSMRelation *priorPhysical; /* prior rel in arena-storage order */
 207         bool            isIndex;                /* if true, we store only page numbers */
 208         Size            avgRequest;             /* moving average of space requests */
 209         int                     lastPageCount;  /* pages passed to RecordRelationFreeSpace */
 210         int                     firstChunk;             /* chunk # of my first chunk in arena */
 211         int                     storedPages;    /* # of pages stored in arena */
 212         int                     nextPage;               /* index (from 0) to start next search at */
 213 };
 214
 215
 216 int                     MaxFSMRelations;        /* these are set by guc.c */
 217 int                     MaxFSMPages;
 218
 219 static FSMHeader *FreeSpaceMap; /* points to FSMHeader in shared memory */
 220 static HTAB *FreeSpaceMapRelHash;               /* points to (what used to be)
 221                                                                                  * FSMHeader->relHash */
 222
 223
 224 static void CheckFreeSpaceMapStatistics(int elevel, int numRels,
 225                                                 double needed);
 226 static FSMRelation *lookup_fsm_rel(RelFileNode *rel);
 227 static FSMRelation *create_fsm_rel(RelFileNode *rel);
 228 static void delete_fsm_rel(FSMRelation *fsmrel);
 229 static int      realloc_fsm_rel(FSMRelation *fsmrel, int nPages, bool isIndex);
 230 static void link_fsm_rel_usage(FSMRelation *fsmrel);
 231 static void unlink_fsm_rel_usage(FSMRelation *fsmrel);
 232 static void link_fsm_rel_storage(FSMRelation *fsmrel);
 233 static void unlink_fsm_rel_storage(FSMRelation *fsmrel);
 234 static BlockNumber find_free_space(FSMRelation *fsmrel, Size spaceNeeded);
 235 static BlockNumber find_index_free_space(FSMRelation *fsmrel);
 236 static void fsm_record_free_space(FSMRelation *fsmrel, BlockNumber page,
 237                                           Size spaceAvail);
 238 static bool lookup_fsm_page_entry(FSMRelation *fsmrel, BlockNumber page,
 239                                           int *outPageIndex);
 240 static void compact_fsm_storage(void);
 241 static void push_fsm_rels_after(FSMRelation *afterRel);
 242 static void pack_incoming_pages(FSMPageData *newLocation, int newPages,
 243                                         PageFreeSpaceInfo *pageSpaces, int nPages);
 244 static void pack_existing_pages(FSMPageData *newLocation, int newPages,
 245                                         FSMPageData *oldLocation, int oldPages);
 246 static int      fsm_calc_request(FSMRelation *fsmrel);
 247 static int      fsm_calc_target_allocation(int myRequest);
 248 static int      fsm_current_chunks(FSMRelation *fsmrel);
 249 static int      fsm_current_allocation(FSMRelation *fsmrel);
 250
 251
 252 /*
 253  * Exported routines
 254  */
 255
 256
 257 /*
 258  * InitFreeSpaceMap -- Initialize the freespace module.
 259  *
 260  * This must be called once during shared memory initialization.
 261  * It builds the empty free space map table.  FreeSpaceLock must also be
 262  * initialized at some point, but is not touched here --- we assume there is
 263  * no need for locking, since only the calling process can be accessing shared
 264  * memory as yet.
 265  */
 266 void
 267 InitFreeSpaceMap(void)
 268 {
 269         HASHCTL         info;
 270         int                     nchunks;
 271         bool            found;
 272
 273         /* Create table header */
 274         FreeSpaceMap = (FSMHeader *) ShmemInitStruct("Free Space Map Header", sizeof(FSMHeader), &found);
 275         if (FreeSpaceMap == NULL)
 276                 ereport(FATAL,
 277                                 (errcode(ERRCODE_OUT_OF_MEMORY),
 278                            errmsg("insufficient shared memory for free space map")));
 279         if (!found)
 280                 MemSet(FreeSpaceMap, 0, sizeof(FSMHeader));
 281
 282         /* Create hashtable for FSMRelations */
 283         info.keysize = sizeof(RelFileNode);
 284         info.entrysize = sizeof(FSMRelation);
 285         info.hash = tag_hash;
 286
 287         FreeSpaceMapRelHash = ShmemInitHash("Free Space Map Hash",
 288                                                                                 MaxFSMRelations + 1,
 289                                                                                 MaxFSMRelations + 1,
 290                                                                                 &info,
 291                                                                                 (HASH_ELEM | HASH_FUNCTION));
 292
 293         if (!FreeSpaceMapRelHash)
 294                 ereport(FATAL,
 295                                 (errcode(ERRCODE_OUT_OF_MEMORY),
 296                            errmsg("insufficient shared memory for free space map")));
 297
 298         if (found)
 299                 return;
 300
 301
 302         /* Allocate page-storage arena */
 303         nchunks = (MaxFSMPages - 1) / CHUNKPAGES + 1;
 304         /* This check ensures spareChunks will be greater than zero */
 305         if (nchunks <= MaxFSMRelations)
 306                 ereport(FATAL,
 307                                 (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
 308                            errmsg("max_fsm_pages must exceed max_fsm_relations * %d",
 309                                           CHUNKPAGES)));
 310
 311         FreeSpaceMap->arena = (char *) ShmemAlloc(nchunks * CHUNKBYTES);
 312         if (FreeSpaceMap->arena == NULL)
 313                 ereport(FATAL,
 314                                 (errcode(ERRCODE_OUT_OF_MEMORY),
 315                            errmsg("insufficient shared memory for free space map")));
 316
 317         FreeSpaceMap->totalChunks = nchunks;
 318         FreeSpaceMap->usedChunks = 0;
 319         FreeSpaceMap->sumRequests = 0;
 320 }
 321
 322 /*
 323  * Estimate amount of shmem space needed for FSM.
 324  */
 325 int
 326 FreeSpaceShmemSize(void)
 327 {
 328         int                     size;
 329         int                     nchunks;
 330
 331         /* table header */
 332         size = MAXALIGN(sizeof(FSMHeader));
 333
 334         /* hash table, including the FSMRelation objects */
 335         size += hash_estimate_size(MaxFSMRelations + 1, sizeof(FSMRelation));
 336
 337         /* page-storage arena */
 338         nchunks = (MaxFSMPages - 1) / CHUNKPAGES + 1;
 339
 340         if (nchunks >= (INT_MAX / CHUNKBYTES))
 341                 ereport(FATAL,
 342                                 (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
 343                                  errmsg("max_fsm_pages is too large")));
 344
 345         size += MAXALIGN(nchunks * CHUNKBYTES);
 346
 347         return size;
 348 }
 349
 350 /*
 351  * GetPageWithFreeSpace - try to find a page in the given relation with
 352  *              at least the specified amount of free space.
 353  *
 354  * If successful, return the block number; if not, return InvalidBlockNumber.
 355  *
 356  * The caller must be prepared for the possibility that the returned page
 357  * will turn out to have too little space available by the time the caller
 358  * gets a lock on it.  In that case, the caller should report the actual
 359  * amount of free space available on that page and then try again (see
 360  * RecordAndGetPageWithFreeSpace).      If InvalidBlockNumber is returned,
 361  * extend the relation.
 362  */
 363 BlockNumber
 364 GetPageWithFreeSpace(RelFileNode *rel, Size spaceNeeded)
 365 {
 366         FSMRelation *fsmrel;
 367         BlockNumber freepage;
 368
 369         LWLockAcquire(FreeSpaceLock, LW_EXCLUSIVE);
 370
 371         /*
 372          * We always add a rel to the hashtable when it is inquired about.
 373          */
 374         fsmrel = create_fsm_rel(rel);
 375
 376         /*
 377          * Update the moving average of space requests.  This code implements
 378          * an exponential moving average with an equivalent period of about 63
 379          * requests.  Ignore silly requests, however, to ensure that the
 380          * average stays sane.
 381          */
 382         if (spaceNeeded > 0 && spaceNeeded < BLCKSZ)
 383         {
 384                 int                     cur_avg = (int) fsmrel->avgRequest;
 385
 386                 cur_avg += ((int) spaceNeeded - cur_avg) / 32;
 387                 fsmrel->avgRequest = (Size) cur_avg;
 388         }
 389         freepage = find_free_space(fsmrel, spaceNeeded);
 390         LWLockRelease(FreeSpaceLock);
 391         return freepage;
 392 }
 393
 394 /*
 395  * RecordAndGetPageWithFreeSpace - update info about a page and try again.
 396  *
 397  * We provide this combo form, instead of a separate Record operation,
 398  * to save one lock and hash table lookup cycle.
 399  */
 400 BlockNumber
 401 RecordAndGetPageWithFreeSpace(RelFileNode *rel,
 402                                                           BlockNumber oldPage,
 403                                                           Size oldSpaceAvail,
 404                                                           Size spaceNeeded)
 405 {
 406         FSMRelation *fsmrel;
 407         BlockNumber freepage;
 408
 409         /* Sanity check: ensure spaceAvail will fit into OffsetNumber */
 410         AssertArg(oldSpaceAvail < BLCKSZ);
 411
 412         LWLockAcquire(FreeSpaceLock, LW_EXCLUSIVE);
 413
 414         /*
 415          * We always add a rel to the hashtable when it is inquired about.
 416          */
 417         fsmrel = create_fsm_rel(rel);
 418
 419         /* Do the Record */
 420         fsm_record_free_space(fsmrel, oldPage, oldSpaceAvail);
 421
 422         /*
 423          * Update the moving average of space requests, same as in
 424          * GetPageWithFreeSpace.
 425          */
 426         if (spaceNeeded > 0 && spaceNeeded < BLCKSZ)
 427         {
 428                 int                     cur_avg = (int) fsmrel->avgRequest;
 429
 430                 cur_avg += ((int) spaceNeeded - cur_avg) / 32;
 431                 fsmrel->avgRequest = (Size) cur_avg;
 432         }
 433         /* Do the Get */
 434         freepage = find_free_space(fsmrel, spaceNeeded);
 435         LWLockRelease(FreeSpaceLock);
 436         return freepage;
 437 }
 438
 439 /*
 440  * GetAvgFSMRequestSize - get average FSM request size for a relation.
 441  *
 442  * If the relation is not known to FSM, return a default value.
 443  */
 444 Size
 445 GetAvgFSMRequestSize(RelFileNode *rel)
 446 {
 447         Size            result;
 448         FSMRelation *fsmrel;
 449
 450         LWLockAcquire(FreeSpaceLock, LW_EXCLUSIVE);
 451         fsmrel = lookup_fsm_rel(rel);
 452         if (fsmrel)
 453                 result = fsmrel->avgRequest;
 454         else
 455                 result = INITIAL_AVERAGE;
 456         LWLockRelease(FreeSpaceLock);
 457         return result;
 458 }
 459
 460 /*
 461  * RecordRelationFreeSpace - record available-space info about a relation.
 462  *
 463  * Any pre-existing info about the relation is assumed obsolete and discarded.
 464  *
 465  * The given pageSpaces[] array must be sorted in order by blkno.  Note that
 466  * the FSM is at liberty to discard some or all of the data.
 467  */
 468 void
 469 RecordRelationFreeSpace(RelFileNode *rel,
 470                                                 int nPages,
 471                                                 PageFreeSpaceInfo *pageSpaces)
 472 {
 473         FSMRelation *fsmrel;
 474
 475         /* Limit nPages to something sane */
 476         if (nPages < 0)
 477                 nPages = 0;
 478         else if (nPages > MaxFSMPages)
 479                 nPages = MaxFSMPages;
 480
 481         LWLockAcquire(FreeSpaceLock, LW_EXCLUSIVE);
 482
 483         /*
 484          * Note we don't record info about a relation unless there's already
 485          * an FSM entry for it, implying someone has done GetPageWithFreeSpace
 486          * for it.      Inactive rels thus will not clutter the map simply by
 487          * being vacuumed.
 488          */
 489         fsmrel = lookup_fsm_rel(rel);
 490         if (fsmrel)
 491         {
 492                 int                     curAlloc;
 493                 int                     curAllocPages;
 494                 FSMPageData *newLocation;
 495
 496                 curAlloc = realloc_fsm_rel(fsmrel, nPages, false);
 497                 curAllocPages = curAlloc * CHUNKPAGES;
 498
 499                 /*
 500                  * If the data fits in our current allocation, just copy it;
 501                  * otherwise must compress.
 502                  */
 503                 newLocation = (FSMPageData *)
 504                         (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
 505                 if (nPages <= curAllocPages)
 506                 {
 507                         int                     i;
 508
 509                         for (i = 0; i < nPages; i++)
 510                         {
 511                                 BlockNumber page = pageSpaces[i].blkno;
 512                                 Size            avail = pageSpaces[i].avail;
 513
 514                                 /* Check caller provides sorted data */
 515                                 if (i > 0 && page <= pageSpaces[i - 1].blkno)
 516                                         elog(ERROR, "free-space data is not in page order");
 517                                 FSMPageSetPageNum(newLocation, page);
 518                                 FSMPageSetSpace(newLocation, avail);
 519                                 newLocation++;
 520                         }
 521                         fsmrel->storedPages = nPages;
 522                 }
 523                 else
 524                 {
 525                         pack_incoming_pages(newLocation, curAllocPages,
 526                                                                 pageSpaces, nPages);
 527                         fsmrel->storedPages = curAllocPages;
 528                 }
 529         }
 530         LWLockRelease(FreeSpaceLock);
 531 }
 532
 533 /*
 534  * GetFreeIndexPage - like GetPageWithFreeSpace, but for indexes
 535  */
 536 BlockNumber
 537 GetFreeIndexPage(RelFileNode *rel)
 538 {
 539         FSMRelation *fsmrel;
 540         BlockNumber freepage;
 541
 542         LWLockAcquire(FreeSpaceLock, LW_EXCLUSIVE);
 543
 544         /*
 545          * We always add a rel to the hashtable when it is inquired about.
 546          */
 547         fsmrel = create_fsm_rel(rel);
 548
 549         freepage = find_index_free_space(fsmrel);
 550         LWLockRelease(FreeSpaceLock);
 551         return freepage;
 552 }
 553
 554 /*
 555  * RecordIndexFreeSpace - like RecordRelationFreeSpace, but for indexes
 556  */
 557 void
 558 RecordIndexFreeSpace(RelFileNode *rel,
 559                                          int nPages,
 560                                          BlockNumber *pages)
 561 {
 562         FSMRelation *fsmrel;
 563
 564         /* Limit nPages to something sane */
 565         if (nPages < 0)
 566                 nPages = 0;
 567         else if (nPages > MaxFSMPages)
 568                 nPages = MaxFSMPages;
 569
 570         LWLockAcquire(FreeSpaceLock, LW_EXCLUSIVE);
 571
 572         /*
 573          * Note we don't record info about a relation unless there's already
 574          * an FSM entry for it, implying someone has done GetFreeIndexPage for
 575          * it.  Inactive rels thus will not clutter the map simply by being
 576          * vacuumed.
 577          */
 578         fsmrel = lookup_fsm_rel(rel);
 579         if (fsmrel)
 580         {
 581                 int                     curAlloc;
 582                 int                     curAllocPages;
 583                 int                     i;
 584                 IndexFSMPageData *newLocation;
 585
 586                 curAlloc = realloc_fsm_rel(fsmrel, nPages, true);
 587                 curAllocPages = curAlloc * INDEXCHUNKPAGES;
 588
 589                 /*
 590                  * If the data fits in our current allocation, just copy it;
 591                  * otherwise must compress.  But compression is easy: we merely
 592                  * forget extra pages.
 593                  */
 594                 newLocation = (IndexFSMPageData *)
 595                         (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
 596                 if (nPages > curAllocPages)
 597                         nPages = curAllocPages;
 598
 599                 for (i = 0; i < nPages; i++)
 600                 {
 601                         BlockNumber page = pages[i];
 602
 603                         /* Check caller provides sorted data */
 604                         if (i > 0 && page <= pages[i - 1])
 605                                 elog(ERROR, "free-space data is not in page order");
 606                         IndexFSMPageSetPageNum(newLocation, page);
 607                         newLocation++;
 608                 }
 609                 fsmrel->storedPages = nPages;
 610         }
 611         LWLockRelease(FreeSpaceLock);
 612 }
 613
 614 /*
 615  * FreeSpaceMapTruncateRel - adjust for truncation of a relation.
 616  *
 617  * We need to delete any stored data past the new relation length, so that
 618  * we don't bogusly return removed block numbers.
 619  */
 620 void
 621 FreeSpaceMapTruncateRel(RelFileNode *rel, BlockNumber nblocks)
 622 {
 623         FSMRelation *fsmrel;
 624
 625         LWLockAcquire(FreeSpaceLock, LW_EXCLUSIVE);
 626         fsmrel = lookup_fsm_rel(rel);
 627         if (fsmrel)
 628         {
 629                 int                     pageIndex;
 630
 631                 /* Use lookup to locate first entry >= nblocks */
 632                 (void) lookup_fsm_page_entry(fsmrel, nblocks, &pageIndex);
 633                 /* Delete all such entries */
 634                 fsmrel->storedPages = pageIndex;
 635                 /* XXX should we adjust rel's lastPageCount and sumRequests? */
 636         }
 637         LWLockRelease(FreeSpaceLock);
 638 }
 639
 640 /*
 641  * FreeSpaceMapForgetRel - forget all about a relation.
 642  *
 643  * This is called when a relation is deleted.  Although we could just let
 644  * the rel age out of the map, it's better to reclaim and reuse the space
 645  * sooner.
 646  */
 647 void
 648 FreeSpaceMapForgetRel(RelFileNode *rel)
 649 {
 650         FSMRelation *fsmrel;
 651
 652         LWLockAcquire(FreeSpaceLock, LW_EXCLUSIVE);
 653         fsmrel = lookup_fsm_rel(rel);
 654         if (fsmrel)
 655                 delete_fsm_rel(fsmrel);
 656         LWLockRelease(FreeSpaceLock);
 657 }
 658
 659 /*
 660  * FreeSpaceMapForgetDatabase - forget all relations of a database.
 661  *
 662  * This is called during DROP DATABASE.  As above, might as well reclaim
 663  * map space sooner instead of later.
 664  */
 665 void
 666 FreeSpaceMapForgetDatabase(Oid dbid)
 667 {
 668         FSMRelation *fsmrel,
 669                            *nextrel;
 670
 671         LWLockAcquire(FreeSpaceLock, LW_EXCLUSIVE);
 672         for (fsmrel = FreeSpaceMap->usageList; fsmrel; fsmrel = nextrel)
 673         {
 674                 nextrel = fsmrel->nextUsage;    /* in case we delete it */
 675                 if (fsmrel->key.dbNode == dbid)
 676                         delete_fsm_rel(fsmrel);
 677         }
 678         LWLockRelease(FreeSpaceLock);
 679 }
 680
 681 /*
 682  * PrintFreeSpaceMapStatistics - print statistics about FSM contents
 683  *
 684  * The info is sent to ereport() with the specified message level.      This is
 685  * intended for use during VACUUM.
 686  */
 687 void
 688 PrintFreeSpaceMapStatistics(int elevel)
 689 {
 690         FSMRelation *fsmrel;
 691         int                     storedPages = 0;
 692         int                     numRels;
 693         double          sumRequests;
 694         double          needed;
 695
 696         LWLockAcquire(FreeSpaceLock, LW_EXCLUSIVE);
 697         /* Count total space used --- tedious, but seems useful */
 698         for (fsmrel = FreeSpaceMap->firstRel;
 699                  fsmrel != NULL;
 700                  fsmrel = fsmrel->nextPhysical)
 701                 storedPages += fsmrel->storedPages;
 702
 703         /* Copy other stats before dropping lock */
 704         numRels = FreeSpaceMap->numRels;
 705         sumRequests = FreeSpaceMap->sumRequests;
 706         LWLockRelease(FreeSpaceLock);
 707
 708         /* Convert stats to actual number of page slots needed */
 709         needed = (sumRequests + numRels) * CHUNKPAGES;
 710
 711         ereport(elevel,
 712                         (errmsg("free space map contains %d pages in %d relations",
 713                                         storedPages, numRels),
 714                          errdetail("A total of %.0f page slots are in use (including overhead).\n"
 715                                         "%.0f page slots are required to track all free space.\n"
 716                                         "Current limits are:  %d page slots, %d relations, using %.0f KB.",
 717                                         Min(needed, MaxFSMPages),
 718                                         needed, MaxFSMPages, MaxFSMRelations,
 719                                     (double) FreeSpaceShmemSize() / 1024.0)));
 720
 721         CheckFreeSpaceMapStatistics(NOTICE, numRels, needed);
 722         /* Print to server logs too because is deals with a config variable. */
 723         CheckFreeSpaceMapStatistics(LOG, numRels, needed);
 724 }
 725
 726 static void
 727 CheckFreeSpaceMapStatistics(int elevel, int numRels, double needed)
 728 {
 729         if (numRels == MaxFSMRelations)
 730                 ereport(elevel,
 731                         (errmsg("max_fsm_relations(%d) equals the number of relations checked",
 732                          MaxFSMRelations),
 733                          errhint("You have >= %d relations.\n"
 734                                          "Consider increasing the configuration parameter \"max_fsm_relations\".",
 735                                          numRels)));
 736         else if (needed > MaxFSMPages)
 737                 ereport(elevel,
 738                         (errmsg("the number of page slots needed (%.0f) exceeds max_fsm_pages (%d)",
 739                          needed,MaxFSMPages),
 740                          errhint("Consider increasing the configuration parameter \"max_fsm_relations\"\n"
 741                                          "to a value over %.0f.", needed)));
 742 }
 743
 744 /*
 745  * DumpFreeSpaceMap - dump contents of FSM into a disk file for later reload
 746  *
 747  * This is expected to be called during database shutdown, after updates to
 748  * the FSM have stopped.  We lock the FreeSpaceLock but that's purely pro
 749  * forma --- if anyone else is still accessing FSM, there's a problem.
 750  */
 751 void
 752 DumpFreeSpaceMap(int code, Datum arg)
 753 {
 754         FILE       *fp;
 755         char            cachefilename[MAXPGPATH];
 756         FsmCacheFileHeader header;
 757         FSMRelation *fsmrel;
 758
 759         /* Try to create file */
 760         snprintf(cachefilename, sizeof(cachefilename), "%s/%s",
 761                          DataDir, FSM_CACHE_FILENAME);
 762
 763         unlink(cachefilename);          /* in case it exists w/wrong permissions */
 764
 765         fp = AllocateFile(cachefilename, PG_BINARY_W);
 766         if (fp == NULL)
 767         {
 768                 elog(LOG, "could not write \"%s\": %m", cachefilename);
 769                 return;
 770         }
 771
 772         LWLockAcquire(FreeSpaceLock, LW_EXCLUSIVE);
 773
 774         /* Write file header */
 775         MemSet(&header, 0, sizeof(header));
 776         strcpy(header.label, FSM_CACHE_LABEL);
 777         header.endian = FSM_CACHE_ENDIAN;
 778         header.version = FSM_CACHE_VERSION;
 779         header.numRels = FreeSpaceMap->numRels;
 780         if (fwrite(&header, 1, sizeof(header), fp) != sizeof(header))
 781                 goto write_failed;
 782
 783         /* For each relation, in order from least to most recently used... */
 784         for (fsmrel = FreeSpaceMap->usageListTail;
 785                  fsmrel != NULL;
 786                  fsmrel = fsmrel->priorUsage)
 787         {
 788                 FsmCacheRelHeader relheader;
 789                 int                     nPages;
 790
 791                 /* Write relation header */
 792                 MemSet(&relheader, 0, sizeof(relheader));
 793                 relheader.key = fsmrel->key;
 794                 relheader.isIndex = fsmrel->isIndex;
 795                 relheader.avgRequest = fsmrel->avgRequest;
 796                 relheader.lastPageCount = fsmrel->lastPageCount;
 797                 relheader.storedPages = fsmrel->storedPages;
 798                 if (fwrite(&relheader, 1, sizeof(relheader), fp) != sizeof(relheader))
 799                         goto write_failed;
 800
 801                 /* Write the per-page data directly from the arena */
 802                 nPages = fsmrel->storedPages;
 803                 if (nPages > 0)
 804                 {
 805                         Size            len;
 806                         char       *data;
 807
 808                         if (fsmrel->isIndex)
 809                                 len = nPages * sizeof(IndexFSMPageData);
 810                         else
 811                                 len = nPages * sizeof(FSMPageData);
 812                         data = (char *)
 813                                 (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
 814                         if (fwrite(data, 1, len, fp) != len)
 815                                 goto write_failed;
 816                 }
 817         }
 818
 819         /* Clean up */
 820         LWLockRelease(FreeSpaceLock);
 821
 822         if (FreeFile(fp))
 823         {
 824                 elog(LOG, "could not write \"%s\": %m", cachefilename);
 825                 /* Remove busted cache file */
 826                 unlink(cachefilename);
 827         }
 828
 829         return;
 830
 831 write_failed:
 832         elog(LOG, "could not write \"%s\": %m", cachefilename);
 833
 834         /* Clean up */
 835         LWLockRelease(FreeSpaceLock);
 836
 837         FreeFile(fp);
 838
 839         /* Remove busted cache file */
 840         unlink(cachefilename);
 841 }
 842
 843 /*
 844  * LoadFreeSpaceMap - load contents of FSM from a disk file
 845  *
 846  * This is expected to be called during database startup, before any FSM
 847  * updates begin.  We lock the FreeSpaceLock but that's purely pro
 848  * forma --- if anyone else is accessing FSM yet, there's a problem.
 849  *
 850  * Notes: no complaint is issued if no cache file is found.  If the file is
 851  * found, it is deleted after reading.  Thus, if we crash without a clean
 852  * shutdown, the next cycle of life starts with no FSM data.  To do otherwise,
 853  * we'd need to do significantly more validation in this routine, because of
 854  * the likelihood that what is in the dump file would be out-of-date, eg
 855  * there might be entries for deleted or truncated rels.
 856  */
 857 void
 858 LoadFreeSpaceMap(void)
 859 {
 860         FILE       *fp;
 861         char            cachefilename[MAXPGPATH];
 862         FsmCacheFileHeader header;
 863         int                     relno;
 864
 865         /* Try to open file */
 866         snprintf(cachefilename, sizeof(cachefilename), "%s/%s",
 867                          DataDir, FSM_CACHE_FILENAME);
 868
 869         fp = AllocateFile(cachefilename, PG_BINARY_R);
 870         if (fp == NULL)
 871         {
 872                 if (errno != ENOENT)
 873                         elog(LOG, "could not read \"%s\": %m", cachefilename);
 874                 return;
 875         }
 876
 877         LWLockAcquire(FreeSpaceLock, LW_EXCLUSIVE);
 878
 879         /* Read and verify file header */
 880         if (fread(&header, 1, sizeof(header), fp) != sizeof(header) ||
 881                 strcmp(header.label, FSM_CACHE_LABEL) != 0 ||
 882                 header.endian != FSM_CACHE_ENDIAN ||
 883                 header.version != FSM_CACHE_VERSION ||
 884                 header.numRels < 0)
 885         {
 886                 elog(LOG, "bogus file header in \"%s\"", cachefilename);
 887                 goto read_failed;
 888         }
 889
 890         /* For each relation, in order from least to most recently used... */
 891         for (relno = 0; relno < header.numRels; relno++)
 892         {
 893                 FsmCacheRelHeader relheader;
 894                 Size            len;
 895                 char       *data;
 896                 FSMRelation *fsmrel;
 897                 int                     nPages;
 898                 int                     curAlloc;
 899                 int                     curAllocPages;
 900
 901                 /* Read and verify relation header, as best we can */
 902                 if (fread(&relheader, 1, sizeof(relheader), fp) != sizeof(relheader) ||
 903                         (relheader.isIndex != false && relheader.isIndex != true) ||
 904                         relheader.avgRequest >= BLCKSZ ||
 905                         relheader.lastPageCount < 0 ||
 906                         relheader.storedPages < 0)
 907                 {
 908                         elog(LOG, "bogus rel header in \"%s\"", cachefilename);
 909                         goto read_failed;
 910                 }
 911
 912                 /* Make sure lastPageCount doesn't exceed current MaxFSMPages */
 913                 if (relheader.lastPageCount > MaxFSMPages)
 914                         relheader.lastPageCount = MaxFSMPages;
 915
 916                 /* Read the per-page data */
 917                 nPages = relheader.storedPages;
 918                 if (relheader.isIndex)
 919                         len = nPages * sizeof(IndexFSMPageData);
 920                 else
 921                         len = nPages * sizeof(FSMPageData);
 922                 data = (char *) palloc(len);
 923                 if (fread(data, 1, len, fp) != len)
 924                 {
 925                         elog(LOG, "premature EOF in \"%s\"", cachefilename);
 926                         pfree(data);
 927                         goto read_failed;
 928                 }
 929
 930                 /*
 931                  * Okay, create the FSM entry and insert data into it.  Since the
 932                  * rels were stored in reverse usage order, at the end of the loop
 933                  * they will be correctly usage-ordered in memory; and if
 934                  * MaxFSMRelations is less than it used to be, we will correctly
 935                  * drop the least recently used ones.
 936                  */
 937                 fsmrel = create_fsm_rel(&relheader.key);
 938                 fsmrel->avgRequest = relheader.avgRequest;
 939
 940                 curAlloc = realloc_fsm_rel(fsmrel, relheader.lastPageCount,
 941                                                                    relheader.isIndex);
 942                 if (relheader.isIndex)
 943                 {
 944                         IndexFSMPageData *newLocation;
 945
 946                         curAllocPages = curAlloc * INDEXCHUNKPAGES;
 947
 948                         /*
 949                          * If the data fits in our current allocation, just copy it;
 950                          * otherwise must compress.  But compression is easy: we
 951                          * merely forget extra pages.
 952                          */
 953                         newLocation = (IndexFSMPageData *)
 954                                 (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
 955                         if (nPages > curAllocPages)
 956                                 nPages = curAllocPages;
 957                         memcpy(newLocation, data, nPages * sizeof(IndexFSMPageData));
 958                         fsmrel->storedPages = nPages;
 959                 }
 960                 else
 961                 {
 962                         FSMPageData *newLocation;
 963
 964                         curAllocPages = curAlloc * CHUNKPAGES;
 965
 966                         /*
 967                          * If the data fits in our current allocation, just copy it;
 968                          * otherwise must compress.
 969                          */
 970                         newLocation = (FSMPageData *)
 971                                 (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
 972                         if (nPages <= curAllocPages)
 973                         {
 974                                 memcpy(newLocation, data, nPages * sizeof(FSMPageData));
 975                                 fsmrel->storedPages = nPages;
 976                         }
 977                         else
 978                         {
 979                                 pack_existing_pages(newLocation, curAllocPages,
 980                                                                         (FSMPageData *) data, nPages);
 981                                 fsmrel->storedPages = curAllocPages;
 982                         }
 983                 }
 984
 985                 pfree(data);
 986         }
 987
 988 read_failed:
 989
 990         /* Clean up */
 991         LWLockRelease(FreeSpaceLock);
 992
 993         FreeFile(fp);
 994
 995         /* Remove cache file before it can become stale; see notes above */
 996         unlink(cachefilename);
 997 }
 998
 999
1000 /*
1001  * Internal routines.  These all assume the caller holds the FreeSpaceLock.
1002  */
1003
1004 /*
1005  * Lookup a relation in the hash table.  If not present, return NULL.
1006  *
1007  * The relation's position in the LRU list is not changed.
1008  */
1009 static FSMRelation *
1010 lookup_fsm_rel(RelFileNode *rel)
1011 {
1012         FSMRelation *fsmrel;
1013
1014         fsmrel = (FSMRelation *) hash_search(FreeSpaceMapRelHash,
1015                                                                                  (void *) rel,
1016                                                                                  HASH_FIND,
1017                                                                                  NULL);
1018         if (!fsmrel)
1019                 return NULL;
1020
1021         return fsmrel;
1022 }
1023
1024 /*
1025  * Lookup a relation in the hash table, creating an entry if not present.
1026  *
1027  * On successful lookup, the relation is moved to the front of the LRU list.
1028  */
1029 static FSMRelation *
1030 create_fsm_rel(RelFileNode *rel)
1031 {
1032         FSMRelation *fsmrel;
1033         bool            found;
1034
1035         fsmrel = (FSMRelation *) hash_search(FreeSpaceMapRelHash,
1036                                                                                  (void *) rel,
1037                                                                                  HASH_ENTER,
1038                                                                                  &found);
1039
1040         if (!found)
1041         {
1042                 /* New hashtable entry, initialize it (hash_search set the key) */
1043                 fsmrel->isIndex = false;        /* until we learn different */
1044                 fsmrel->avgRequest = INITIAL_AVERAGE;
1045                 fsmrel->lastPageCount = 0;
1046                 fsmrel->firstChunk = -1;        /* no space allocated */
1047                 fsmrel->storedPages = 0;
1048                 fsmrel->nextPage = 0;
1049
1050                 /* Discard lowest-priority existing rel, if we are over limit */
1051                 if (FreeSpaceMap->numRels >= MaxFSMRelations)
1052                         delete_fsm_rel(FreeSpaceMap->usageListTail);
1053
1054                 /* Add new entry at front of LRU list */
1055                 link_fsm_rel_usage(fsmrel);
1056                 fsmrel->nextPhysical = NULL;    /* not in physical-storage list */
1057                 fsmrel->priorPhysical = NULL;
1058                 FreeSpaceMap->numRels++;
1059                 /* sumRequests is unchanged because request must be zero */
1060         }
1061         else
1062         {
1063                 /* Existing entry, move to front of LRU list */
1064                 if (fsmrel->priorUsage != NULL)
1065                 {
1066                         unlink_fsm_rel_usage(fsmrel);
1067                         link_fsm_rel_usage(fsmrel);
1068                 }
1069         }
1070
1071         return fsmrel;
1072 }
1073
1074 /*
1075  * Remove an existing FSMRelation entry.
1076  */
1077 static void
1078 delete_fsm_rel(FSMRelation *fsmrel)
1079 {
1080         FSMRelation *result;
1081
1082         FreeSpaceMap->sumRequests -= fsm_calc_request(fsmrel);
1083         unlink_fsm_rel_usage(fsmrel);
1084         unlink_fsm_rel_storage(fsmrel);
1085         FreeSpaceMap->numRels--;
1086         result = (FSMRelation *) hash_search(FreeSpaceMapRelHash,
1087                                                                                  (void *) &(fsmrel->key),
1088                                                                                  HASH_REMOVE,
1089                                                                                  NULL);
1090         if (!result)
1091                 elog(ERROR, "FreeSpaceMap hashtable corrupted");
1092 }
1093
1094 /*
1095  * Reallocate space for a FSMRelation.
1096  *
1097  * This is shared code for RecordRelationFreeSpace and RecordIndexFreeSpace.
1098  * The return value is the actual new allocation, in chunks.
1099  */
1100 static int
1101 realloc_fsm_rel(FSMRelation *fsmrel, int nPages, bool isIndex)
1102 {
1103         int                     myRequest;
1104         int                     myAlloc;
1105         int                     curAlloc;
1106
1107         /*
1108          * Delete any existing entries, and update request status.
1109          */
1110         fsmrel->storedPages = 0;
1111         FreeSpaceMap->sumRequests -= fsm_calc_request(fsmrel);
1112         fsmrel->lastPageCount = nPages;
1113         fsmrel->isIndex = isIndex;
1114         myRequest = fsm_calc_request(fsmrel);
1115         FreeSpaceMap->sumRequests += myRequest;
1116         myAlloc = fsm_calc_target_allocation(myRequest);
1117
1118         /*
1119          * Need to reallocate space if (a) my target allocation is more than
1120          * my current allocation, AND (b) my actual immediate need
1121          * (myRequest+1 chunks) is more than my current allocation. Otherwise
1122          * just store the new data in-place.
1123          */
1124         curAlloc = fsm_current_allocation(fsmrel);
1125         if (myAlloc > curAlloc && (myRequest + 1) > curAlloc && nPages > 0)
1126         {
1127                 /* Remove entry from storage list, and compact */
1128                 unlink_fsm_rel_storage(fsmrel);
1129                 compact_fsm_storage();
1130                 /* Reattach to end of storage list */
1131                 link_fsm_rel_storage(fsmrel);
1132                 /* And allocate storage */
1133                 fsmrel->firstChunk = FreeSpaceMap->usedChunks;
1134                 FreeSpaceMap->usedChunks += myAlloc;
1135                 curAlloc = myAlloc;
1136                 /* Watch out for roundoff error */
1137                 if (FreeSpaceMap->usedChunks > FreeSpaceMap->totalChunks)
1138                 {
1139                         FreeSpaceMap->usedChunks = FreeSpaceMap->totalChunks;
1140                         curAlloc = FreeSpaceMap->totalChunks - fsmrel->firstChunk;
1141                 }
1142         }
1143         return curAlloc;
1144 }
1145
1146 /*
1147  * Link a FSMRelation into the LRU list (always at the head).
1148  */
1149 static void
1150 link_fsm_rel_usage(FSMRelation *fsmrel)
1151 {
1152         fsmrel->priorUsage = NULL;
1153         fsmrel->nextUsage = FreeSpaceMap->usageList;
1154         FreeSpaceMap->usageList = fsmrel;
1155         if (fsmrel->nextUsage != NULL)
1156                 fsmrel->nextUsage->priorUsage = fsmrel;
1157         else
1158                 FreeSpaceMap->usageListTail = fsmrel;
1159 }
1160
1161 /*
1162  * Delink a FSMRelation from the LRU list.
1163  */
1164 static void
1165 unlink_fsm_rel_usage(FSMRelation *fsmrel)
1166 {
1167         if (fsmrel->priorUsage != NULL)
1168                 fsmrel->priorUsage->nextUsage = fsmrel->nextUsage;
1169         else
1170                 FreeSpaceMap->usageList = fsmrel->nextUsage;
1171         if (fsmrel->nextUsage != NULL)
1172                 fsmrel->nextUsage->priorUsage = fsmrel->priorUsage;
1173         else
1174                 FreeSpaceMap->usageListTail = fsmrel->priorUsage;
1175
1176         /*
1177          * We don't bother resetting fsmrel's links, since it's about to be
1178          * deleted or relinked at the head.
1179          */
1180 }
1181
1182 /*
1183  * Link a FSMRelation into the storage-order list (always at the tail).
1184  */
1185 static void
1186 link_fsm_rel_storage(FSMRelation *fsmrel)
1187 {
1188         fsmrel->nextPhysical = NULL;
1189         fsmrel->priorPhysical = FreeSpaceMap->lastRel;
1190         if (FreeSpaceMap->lastRel != NULL)
1191                 FreeSpaceMap->lastRel->nextPhysical = fsmrel;
1192         else
1193                 FreeSpaceMap->firstRel = fsmrel;
1194         FreeSpaceMap->lastRel = fsmrel;
1195 }
1196
1197 /*
1198  * Delink a FSMRelation from the storage-order list, if it's in it.
1199  */
1200 static void
1201 unlink_fsm_rel_storage(FSMRelation *fsmrel)
1202 {
1203         if (fsmrel->priorPhysical != NULL || FreeSpaceMap->firstRel == fsmrel)
1204         {
1205                 if (fsmrel->priorPhysical != NULL)
1206                         fsmrel->priorPhysical->nextPhysical = fsmrel->nextPhysical;
1207                 else
1208                         FreeSpaceMap->firstRel = fsmrel->nextPhysical;
1209                 if (fsmrel->nextPhysical != NULL)
1210                         fsmrel->nextPhysical->priorPhysical = fsmrel->priorPhysical;
1211                 else
1212                         FreeSpaceMap->lastRel = fsmrel->priorPhysical;
1213         }
1214         /* mark as not in list, since we may not put it back immediately */
1215         fsmrel->nextPhysical = NULL;
1216         fsmrel->priorPhysical = NULL;
1217         /* Also mark it as having no storage */
1218         fsmrel->firstChunk = -1;
1219         fsmrel->storedPages = 0;
1220 }
1221
1222 /*
1223  * Look to see if a page with at least the specified amount of space is
1224  * available in the given FSMRelation.  If so, return its page number,
1225  * and advance the nextPage counter so that the next inquiry will return
1226  * a different page if possible; also update the entry to show that the
1227  * requested space is not available anymore.  Return InvalidBlockNumber
1228  * if no success.
1229  */
1230 static BlockNumber
1231 find_free_space(FSMRelation *fsmrel, Size spaceNeeded)
1232 {
1233         FSMPageData *info;
1234         int                     pagesToCheck,   /* outer loop counter */
1235                                 pageIndex;              /* current page index */
1236
1237         if (fsmrel->isIndex)
1238                 elog(ERROR, "find_free_space called for an index relation");
1239         info = (FSMPageData *)
1240                 (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
1241         pageIndex = fsmrel->nextPage;
1242         /* Last operation may have left nextPage pointing past end */
1243         if (pageIndex >= fsmrel->storedPages)
1244                 pageIndex = 0;
1245
1246         for (pagesToCheck = fsmrel->storedPages; pagesToCheck > 0; pagesToCheck--)
1247         {
1248                 FSMPageData *page = info + pageIndex;
1249                 Size            spaceAvail = FSMPageGetSpace(page);
1250
1251                 /* Check this page */
1252                 if (spaceAvail >= spaceNeeded)
1253                 {
1254                         /*
1255                          * Found what we want --- adjust the entry, and update
1256                          * nextPage.
1257                          */
1258                         FSMPageSetSpace(page, spaceAvail - spaceNeeded);
1259                         fsmrel->nextPage = pageIndex + 1;
1260                         return FSMPageGetPageNum(page);
1261                 }
1262                 /* Advance pageIndex, wrapping around if needed */
1263                 if (++pageIndex >= fsmrel->storedPages)
1264                         pageIndex = 0;
1265         }
1266
1267         return InvalidBlockNumber;      /* nothing found */
1268 }
1269
1270 /*
1271  * As above, but for index case --- we only deal in whole pages.
1272  */
1273 static BlockNumber
1274 find_index_free_space(FSMRelation *fsmrel)
1275 {
1276         IndexFSMPageData *info;
1277         BlockNumber result;
1278
1279         /*
1280          * If isIndex isn't set, it could be that RecordIndexFreeSpace() has
1281          * never yet been called on this relation, and we're still looking at
1282          * the default setting from create_fsm_rel().  If so, just act as
1283          * though there's no space.
1284          */
1285         if (!fsmrel->isIndex)
1286         {
1287                 if (fsmrel->storedPages == 0)
1288                         return InvalidBlockNumber;
1289                 elog(ERROR, "find_index_free_space called for a non-index relation");
1290         }
1291
1292         /*
1293          * For indexes, there's no need for the nextPage state variable; we
1294          * just remove and return the first available page.  (We could save
1295          * cycles here by returning the last page, but it seems better to
1296          * encourage re-use of lower-numbered pages.)
1297          */
1298         if (fsmrel->storedPages <= 0)
1299                 return InvalidBlockNumber;              /* no pages available */
1300         info = (IndexFSMPageData *)
1301                 (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
1302         result = IndexFSMPageGetPageNum(info);
1303         fsmrel->storedPages--;
1304         memmove(info, info + 1, fsmrel->storedPages * sizeof(IndexFSMPageData));
1305         return result;
1306 }
1307
1308 /*
1309  * fsm_record_free_space - guts of RecordFreeSpace operation (now only
1310  * provided as part of RecordAndGetPageWithFreeSpace).
1311  */
1312 static void
1313 fsm_record_free_space(FSMRelation *fsmrel, BlockNumber page, Size spaceAvail)
1314 {
1315         int                     pageIndex;
1316
1317         if (fsmrel->isIndex)
1318                 elog(ERROR, "fsm_record_free_space called for an index relation");
1319         if (lookup_fsm_page_entry(fsmrel, page, &pageIndex))
1320         {
1321                 /* Found an existing entry for page; update it */
1322                 FSMPageData *info;
1323
1324                 info = (FSMPageData *)
1325                         (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
1326                 info += pageIndex;
1327                 FSMPageSetSpace(info, spaceAvail);
1328         }
1329         else
1330         {
1331                 /*
1332                  * No existing entry; ignore the call.  We used to add the page to
1333                  * the FSM --- but in practice, if the page hasn't got enough
1334                  * space to satisfy the caller who's kicking it back to us, then
1335                  * it's probably uninteresting to everyone else as well.
1336                  */
1337         }
1338 }
1339
1340 /*
1341  * Look for an entry for a specific page (block number) in a FSMRelation.
1342  * Returns TRUE if a matching entry exists, else FALSE.
1343  *
1344  * The output argument *outPageIndex is set to indicate where the entry exists
1345  * (if TRUE result) or could be inserted (if FALSE result).
1346  */
1347 static bool
1348 lookup_fsm_page_entry(FSMRelation *fsmrel, BlockNumber page,
1349                                           int *outPageIndex)
1350 {
1351         /* Check for empty relation */
1352         if (fsmrel->storedPages <= 0)
1353         {
1354                 *outPageIndex = 0;
1355                 return false;
1356         }
1357
1358         /* Do binary search */
1359         if (fsmrel->isIndex)
1360         {
1361                 IndexFSMPageData *info;
1362                 int                     low,
1363                                         high;
1364
1365                 info = (IndexFSMPageData *)
1366                         (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
1367                 low = 0;
1368                 high = fsmrel->storedPages - 1;
1369                 while (low <= high)
1370                 {
1371                         int                     middle;
1372                         BlockNumber probe;
1373
1374                         middle = low + (high - low) / 2;
1375                         probe = IndexFSMPageGetPageNum(info + middle);
1376                         if (probe == page)
1377                         {
1378                                 *outPageIndex = middle;
1379                                 return true;
1380                         }
1381                         else if (probe < page)
1382                                 low = middle + 1;
1383                         else
1384                                 high = middle - 1;
1385                 }
1386                 *outPageIndex = low;
1387                 return false;
1388         }
1389         else
1390         {
1391                 FSMPageData *info;
1392                 int                     low,
1393                                         high;
1394
1395                 info = (FSMPageData *)
1396                         (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
1397                 low = 0;
1398                 high = fsmrel->storedPages - 1;
1399                 while (low <= high)
1400                 {
1401                         int                     middle;
1402                         BlockNumber probe;
1403
1404                         middle = low + (high - low) / 2;
1405                         probe = FSMPageGetPageNum(info + middle);
1406                         if (probe == page)
1407                         {
1408                                 *outPageIndex = middle;
1409                                 return true;
1410                         }
1411                         else if (probe < page)
1412                                 low = middle + 1;
1413                         else
1414                                 high = middle - 1;
1415                 }
1416                 *outPageIndex = low;
1417                 return false;
1418         }
1419 }
1420
1421 /*
1422  * Re-pack the FSM storage arena, dropping data if necessary to meet the
1423  * current allocation target for each relation.  At conclusion, all available
1424  * space in the arena will be coalesced at the end.
1425  */
1426 static void
1427 compact_fsm_storage(void)
1428 {
1429         int                     nextChunkIndex = 0;
1430         bool            did_push = false;
1431         FSMRelation *fsmrel;
1432
1433         for (fsmrel = FreeSpaceMap->firstRel;
1434                  fsmrel != NULL;
1435                  fsmrel = fsmrel->nextPhysical)
1436         {
1437                 int                     newAlloc;
1438                 int                     newAllocPages;
1439                 int                     newChunkIndex;
1440                 int                     oldChunkIndex;
1441                 int                     curChunks;
1442                 char       *newLocation;
1443                 char       *oldLocation;
1444
1445                 /*
1446                  * Calculate target allocation, make sure we don't overrun due to
1447                  * roundoff error
1448                  */
1449                 newAlloc = fsm_calc_target_allocation(fsm_calc_request(fsmrel));
1450                 if (newAlloc > FreeSpaceMap->totalChunks - nextChunkIndex)
1451                         newAlloc = FreeSpaceMap->totalChunks - nextChunkIndex;
1452                 if (fsmrel->isIndex)
1453                         newAllocPages = newAlloc * INDEXCHUNKPAGES;
1454                 else
1455                         newAllocPages = newAlloc * CHUNKPAGES;
1456
1457                 /*
1458                  * Determine current size, current and new locations
1459                  */
1460                 curChunks = fsm_current_chunks(fsmrel);
1461                 oldChunkIndex = fsmrel->firstChunk;
1462                 oldLocation = FreeSpaceMap->arena + oldChunkIndex * CHUNKBYTES;
1463                 newChunkIndex = nextChunkIndex;
1464                 newLocation = FreeSpaceMap->arena + newChunkIndex * CHUNKBYTES;
1465
1466                 /*
1467                  * It's possible that we have to move data down, not up, if the
1468                  * allocations of previous rels expanded.  This normally means
1469                  * that our allocation expanded too (or at least got no worse),
1470                  * and ditto for later rels.  So there should be room to move all
1471                  * our data down without dropping any --- but we might have to
1472                  * push down following rels to acquire the room.  We don't want to
1473                  * do the push more than once, so pack everything against the end
1474                  * of the arena if so.
1475                  *
1476                  * In corner cases where we are on the short end of a roundoff choice
1477                  * that we were formerly on the long end of, it's possible that we
1478                  * have to move down and compress our data too.  In fact, even
1479                  * after pushing down the following rels, there might not be as
1480                  * much space as we computed for this rel above --- that would
1481                  * imply that some following rel(s) are also on the losing end of
1482                  * roundoff choices. We could handle this fairly by doing the
1483                  * per-rel compactions out-of-order, but that seems like way too
1484                  * much complexity to deal with a very infrequent corner case.
1485                  * Instead, we simply drop pages from the end of the current rel's
1486                  * data until it fits.
1487                  */
1488                 if (newChunkIndex > oldChunkIndex)
1489                 {
1490                         int                     limitChunkIndex;
1491
1492                         if (newAllocPages < fsmrel->storedPages)
1493                         {
1494                                 /* move and compress --- just drop excess pages */
1495                                 fsmrel->storedPages = newAllocPages;
1496                                 curChunks = fsm_current_chunks(fsmrel);
1497                         }
1498                         /* is there enough space? */
1499                         if (fsmrel->nextPhysical != NULL)
1500                                 limitChunkIndex = fsmrel->nextPhysical->firstChunk;
1501                         else
1502                                 limitChunkIndex = FreeSpaceMap->totalChunks;
1503                         if (newChunkIndex + curChunks > limitChunkIndex)
1504                         {
1505                                 /* not enough space, push down following rels */
1506                                 if (!did_push)
1507                                 {
1508                                         push_fsm_rels_after(fsmrel);
1509                                         did_push = true;
1510                                 }
1511                                 /* now is there enough space? */
1512                                 if (fsmrel->nextPhysical != NULL)
1513                                         limitChunkIndex = fsmrel->nextPhysical->firstChunk;
1514                                 else
1515                                         limitChunkIndex = FreeSpaceMap->totalChunks;
1516                                 if (newChunkIndex + curChunks > limitChunkIndex)
1517                                 {
1518                                         /* uh-oh, forcibly cut the allocation to fit */
1519                                         newAlloc = limitChunkIndex - newChunkIndex;
1520
1521                                         /*
1522                                          * If newAlloc < 0 at this point, we are moving the
1523                                          * rel's firstChunk into territory currently assigned
1524                                          * to a later rel.      This is okay so long as we do not
1525                                          * copy any data. The rels will be back in
1526                                          * nondecreasing firstChunk order at completion of the
1527                                          * compaction pass.
1528                                          */
1529                                         if (newAlloc < 0)
1530                                                 newAlloc = 0;
1531                                         if (fsmrel->isIndex)
1532                                                 newAllocPages = newAlloc * INDEXCHUNKPAGES;
1533                                         else
1534                                                 newAllocPages = newAlloc * CHUNKPAGES;
1535                                         fsmrel->storedPages = newAllocPages;
1536                                         curChunks = fsm_current_chunks(fsmrel);
1537                                 }
1538                         }
1539                         memmove(newLocation, oldLocation, curChunks * CHUNKBYTES);
1540                 }
1541                 else if (newAllocPages < fsmrel->storedPages)
1542                 {
1543                         /*
1544                          * Need to compress the page data.      For an index,
1545                          * "compression" just means dropping excess pages; otherwise
1546                          * we try to keep the ones with the most space.
1547                          */
1548                         if (fsmrel->isIndex)
1549                         {
1550                                 fsmrel->storedPages = newAllocPages;
1551                                 /* may need to move data */
1552                                 if (newChunkIndex != oldChunkIndex)
1553                                         memmove(newLocation, oldLocation, newAlloc * CHUNKBYTES);
1554                         }
1555                         else
1556                         {
1557                                 pack_existing_pages((FSMPageData *) newLocation,
1558                                                                         newAllocPages,
1559                                                                         (FSMPageData *) oldLocation,
1560                                                                         fsmrel->storedPages);
1561                                 fsmrel->storedPages = newAllocPages;
1562                         }
1563                 }
1564                 else if (newChunkIndex != oldChunkIndex)
1565                 {
1566                         /*
1567                          * No compression needed, but must copy the data up
1568                          */
1569                         memmove(newLocation, oldLocation, curChunks * CHUNKBYTES);
1570                 }
1571                 fsmrel->firstChunk = newChunkIndex;
1572                 nextChunkIndex += newAlloc;
1573         }
1574         Assert(nextChunkIndex <= FreeSpaceMap->totalChunks);
1575         FreeSpaceMap->usedChunks = nextChunkIndex;
1576 }
1577
1578 /*
1579  * Push all FSMRels physically after afterRel to the end of the storage arena.
1580  *
1581  * We sometimes have to do this when deletion or truncation of a relation
1582  * causes the allocations of remaining rels to expand markedly.  We must
1583  * temporarily push existing data down to the end so that we can move it
1584  * back up in an orderly fashion.
1585  */
1586 static void
1587 push_fsm_rels_after(FSMRelation *afterRel)
1588 {
1589         int                     nextChunkIndex = FreeSpaceMap->totalChunks;
1590         FSMRelation *fsmrel;
1591
1592         FreeSpaceMap->usedChunks = FreeSpaceMap->totalChunks;
1593
1594         for (fsmrel = FreeSpaceMap->lastRel;
1595                  fsmrel != NULL;
1596                  fsmrel = fsmrel->priorPhysical)
1597         {
1598                 int                     chunkCount;
1599                 int                     newChunkIndex;
1600                 int                     oldChunkIndex;
1601                 char       *newLocation;
1602                 char       *oldLocation;
1603
1604                 if (fsmrel == afterRel)
1605                         break;
1606
1607                 chunkCount = fsm_current_chunks(fsmrel);
1608                 nextChunkIndex -= chunkCount;
1609                 newChunkIndex = nextChunkIndex;
1610                 oldChunkIndex = fsmrel->firstChunk;
1611                 if (newChunkIndex < oldChunkIndex)
1612                 {
1613                         /* we're pushing down, how can it move up? */
1614                         elog(PANIC, "inconsistent entry sizes in FSM");
1615                 }
1616                 else if (newChunkIndex > oldChunkIndex)
1617                 {
1618                         /* need to move it */
1619                         newLocation = FreeSpaceMap->arena + newChunkIndex * CHUNKBYTES;
1620                         oldLocation = FreeSpaceMap->arena + oldChunkIndex * CHUNKBYTES;
1621                         memmove(newLocation, oldLocation, chunkCount * CHUNKBYTES);
1622                         fsmrel->firstChunk = newChunkIndex;
1623                 }
1624         }
1625         Assert(nextChunkIndex >= 0);
1626 }
1627
1628 /*
1629  * Pack a set of per-page freespace data into a smaller amount of space.
1630  *
1631  * The method is to compute a low-resolution histogram of the free space
1632  * amounts, then determine which histogram bin contains the break point.
1633  * We then keep all pages above that bin, none below it, and just enough
1634  * of the pages in that bin to fill the output area exactly.
1635  */
1636 #define HISTOGRAM_BINS  64
1637
1638 static void
1639 pack_incoming_pages(FSMPageData *newLocation, int newPages,
1640                                         PageFreeSpaceInfo *pageSpaces, int nPages)
1641 {
1642         int                     histogram[HISTOGRAM_BINS];
1643         int                     above,
1644                                 binct,
1645                                 i;
1646         Size            thresholdL,
1647                                 thresholdU;
1648
1649         Assert(newPages < nPages);      /* else I shouldn't have been called */
1650         /* Build histogram */
1651         MemSet(histogram, 0, sizeof(histogram));
1652         for (i = 0; i < nPages; i++)
1653         {
1654                 Size            avail = pageSpaces[i].avail;
1655
1656                 if (avail >= BLCKSZ)
1657                         elog(ERROR, "bogus freespace amount");
1658                 avail /= (BLCKSZ / HISTOGRAM_BINS);
1659                 histogram[avail]++;
1660         }
1661         /* Find the breakpoint bin */
1662         above = 0;
1663         for (i = HISTOGRAM_BINS - 1; i >= 0; i--)
1664         {
1665                 int                     sum = above + histogram[i];
1666
1667                 if (sum > newPages)
1668                         break;
1669                 above = sum;
1670         }
1671         Assert(i >= 0);
1672         thresholdL = i * BLCKSZ / HISTOGRAM_BINS;       /* low bound of bp bin */
1673         thresholdU = (i + 1) * BLCKSZ / HISTOGRAM_BINS;         /* hi bound */
1674         binct = newPages - above;       /* number to take from bp bin */
1675         /* And copy the appropriate data */
1676         for (i = 0; i < nPages; i++)
1677         {
1678                 BlockNumber page = pageSpaces[i].blkno;
1679                 Size            avail = pageSpaces[i].avail;
1680
1681                 /* Check caller provides sorted data */
1682                 if (i > 0 && page <= pageSpaces[i - 1].blkno)
1683                         elog(ERROR, "free-space data is not in page order");
1684                 /* Save this page? */
1685                 if (avail >= thresholdU ||
1686                         (avail >= thresholdL && (--binct >= 0)))
1687                 {
1688                         FSMPageSetPageNum(newLocation, page);
1689                         FSMPageSetSpace(newLocation, avail);
1690                         newLocation++;
1691                         newPages--;
1692                 }
1693         }
1694         Assert(newPages == 0);
1695 }
1696
1697 /*
1698  * Pack a set of per-page freespace data into a smaller amount of space.
1699  *
1700  * This is algorithmically identical to pack_incoming_pages(), but accepts
1701  * a different input representation.  Also, we assume the input data has
1702  * previously been checked for validity (size in bounds, pages in order).
1703  *
1704  * Note: it is possible for the source and destination arrays to overlap.
1705  * The caller is responsible for making sure newLocation is at lower addresses
1706  * so that we can copy data moving forward in the arrays without problem.
1707  */
1708 static void
1709 pack_existing_pages(FSMPageData *newLocation, int newPages,
1710                                         FSMPageData *oldLocation, int oldPages)
1711 {
1712         int                     histogram[HISTOGRAM_BINS];
1713         int                     above,
1714                                 binct,
1715                                 i;
1716         Size            thresholdL,
1717                                 thresholdU;
1718
1719         Assert(newPages < oldPages);    /* else I shouldn't have been called */
1720         /* Build histogram */
1721         MemSet(histogram, 0, sizeof(histogram));
1722         for (i = 0; i < oldPages; i++)
1723         {
1724                 Size            avail = FSMPageGetSpace(oldLocation + i);
1725
1726                 /* Shouldn't happen, but test to protect against stack clobber */
1727                 if (avail >= BLCKSZ)
1728                         elog(ERROR, "bogus freespace amount");
1729                 avail /= (BLCKSZ / HISTOGRAM_BINS);
1730                 histogram[avail]++;
1731         }
1732         /* Find the breakpoint bin */
1733         above = 0;
1734         for (i = HISTOGRAM_BINS - 1; i >= 0; i--)
1735         {
1736                 int                     sum = above + histogram[i];
1737
1738                 if (sum > newPages)
1739                         break;
1740                 above = sum;
1741         }
1742         Assert(i >= 0);
1743         thresholdL = i * BLCKSZ / HISTOGRAM_BINS;       /* low bound of bp bin */
1744         thresholdU = (i + 1) * BLCKSZ / HISTOGRAM_BINS;         /* hi bound */
1745         binct = newPages - above;       /* number to take from bp bin */
1746         /* And copy the appropriate data */
1747         for (i = 0; i < oldPages; i++)
1748         {
1749                 BlockNumber page = FSMPageGetPageNum(oldLocation + i);
1750                 Size            avail = FSMPageGetSpace(oldLocation + i);
1751
1752                 /* Save this page? */
1753                 if (avail >= thresholdU ||
1754                         (avail >= thresholdL && (--binct >= 0)))
1755                 {
1756                         FSMPageSetPageNum(newLocation, page);
1757                         FSMPageSetSpace(newLocation, avail);
1758                         newLocation++;
1759                         newPages--;
1760                 }
1761         }
1762         Assert(newPages == 0);
1763 }
1764
1765 /*
1766  * Calculate number of chunks "requested" by a rel.
1767  *
1768  * Rel's lastPageCount and isIndex settings must be up-to-date when called.
1769  *
1770  * See notes at top of file for details.
1771  */
1772 static int
1773 fsm_calc_request(FSMRelation *fsmrel)
1774 {
1775         int                     chunkCount;
1776
1777         /* Convert page count to chunk count */
1778         if (fsmrel->isIndex)
1779                 chunkCount = (fsmrel->lastPageCount - 1) / INDEXCHUNKPAGES + 1;
1780         else
1781                 chunkCount = (fsmrel->lastPageCount - 1) / CHUNKPAGES + 1;
1782         /* "Request" is anything beyond our one guaranteed chunk */
1783         if (chunkCount <= 0)
1784                 return 0;
1785         else
1786                 return chunkCount - 1;
1787 }
1788
1789 /*
1790  * Calculate target allocation (number of chunks) for a rel
1791  *
1792  * Parameter is the result from fsm_calc_request().  The global sumRequests
1793  * and numRels totals must be up-to-date already.
1794  *
1795  * See notes at top of file for details.
1796  */
1797 static int
1798 fsm_calc_target_allocation(int myRequest)
1799 {
1800         double          spareChunks;
1801         int                     extra;
1802
1803         spareChunks = FreeSpaceMap->totalChunks - FreeSpaceMap->numRels;
1804         Assert(spareChunks > 0);
1805         if (spareChunks >= FreeSpaceMap->sumRequests)
1806         {
1807                 /* We aren't oversubscribed, so allocate exactly the request */
1808                 extra = myRequest;
1809         }
1810         else
1811         {
1812                 extra = (int) rint(spareChunks * myRequest / FreeSpaceMap->sumRequests);
1813                 if (extra < 0)                  /* shouldn't happen, but make sure */
1814                         extra = 0;
1815         }
1816         return 1 + extra;
1817 }
1818
1819 /*
1820  * Calculate number of chunks actually used to store current data
1821  */
1822 static int
1823 fsm_current_chunks(FSMRelation *fsmrel)
1824 {
1825         int                     chunkCount;
1826
1827         /* Make sure storedPages==0 produces right answer */
1828         if (fsmrel->storedPages <= 0)
1829                 return 0;
1830         /* Convert page count to chunk count */
1831         if (fsmrel->isIndex)
1832                 chunkCount = (fsmrel->storedPages - 1) / INDEXCHUNKPAGES + 1;
1833         else
1834                 chunkCount = (fsmrel->storedPages - 1) / CHUNKPAGES + 1;
1835         return chunkCount;
1836 }
1837
1838 /*
1839  * Calculate current actual allocation (number of chunks) for a rel
1840  */
1841 static int
1842 fsm_current_allocation(FSMRelation *fsmrel)
1843 {
1844         if (fsmrel->nextPhysical != NULL)
1845                 return fsmrel->nextPhysical->firstChunk - fsmrel->firstChunk;
1846         else if (fsmrel == FreeSpaceMap->lastRel)
1847                 return FreeSpaceMap->usedChunks - fsmrel->firstChunk;
1848         else
1849         {
1850                 /* it's not in the storage-order list */
1851                 Assert(fsmrel->firstChunk < 0 && fsmrel->storedPages == 0);
1852                 return 0;
1853         }
1854 }
1855
1856
1857 #ifdef FREESPACE_DEBUG
1858 /*
1859  * Dump contents of freespace map for debugging.
1860  *
1861  * We assume caller holds the FreeSpaceLock, or is otherwise unconcerned
1862  * about other processes.
1863  */
1864 void
1865 DumpFreeSpace(void)
1866 {
1867         FSMRelation *fsmrel;
1868         FSMRelation *prevrel = NULL;
1869         int                     relNum = 0;
1870         int                     nPages;
1871
1872         for (fsmrel = FreeSpaceMap->usageList; fsmrel; fsmrel = fsmrel->nextUsage)
1873         {
1874                 relNum++;
1875                 fprintf(stderr, "Map %d: rel %u/%u/%u isIndex %d avgRequest %u lastPageCount %d nextPage %d\nMap= ",
1876                                 relNum,
1877                         fsmrel->key.spcNode, fsmrel->key.dbNode, fsmrel->key.relNode,
1878                                 (int) fsmrel->isIndex, fsmrel->avgRequest,
1879                                 fsmrel->lastPageCount, fsmrel->nextPage);
1880                 if (fsmrel->isIndex)
1881                 {
1882                         IndexFSMPageData *page;
1883
1884                         page = (IndexFSMPageData *)
1885                                 (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
1886                         for (nPages = 0; nPages < fsmrel->storedPages; nPages++)
1887                         {
1888                                 fprintf(stderr, " %u",
1889                                                 IndexFSMPageGetPageNum(page));
1890                                 page++;
1891                         }
1892                 }
1893                 else
1894                 {
1895                         FSMPageData *page;
1896
1897                         page = (FSMPageData *)
1898                                 (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
1899                         for (nPages = 0; nPages < fsmrel->storedPages; nPages++)
1900                         {
1901                                 fprintf(stderr, " %u:%u",
1902                                                 FSMPageGetPageNum(page),
1903                                                 FSMPageGetSpace(page));
1904                                 page++;
1905                         }
1906                 }
1907                 fprintf(stderr, "\n");
1908                 /* Cross-check list links */
1909                 if (prevrel != fsmrel->priorUsage)
1910                         fprintf(stderr, "DumpFreeSpace: broken list links\n");
1911                 prevrel = fsmrel;
1912         }
1913         if (prevrel != FreeSpaceMap->usageListTail)
1914                 fprintf(stderr, "DumpFreeSpace: broken list links\n");
1915         /* Cross-check global counters */
1916         if (relNum != FreeSpaceMap->numRels)
1917                 fprintf(stderr, "DumpFreeSpace: %d rels in list, but numRels = %d\n",
1918                                 relNum, FreeSpaceMap->numRels);
1919 }
1920
1921 #endif   /* FREESPACE_DEBUG */