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