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-2003, 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.31 2004/06/05 19:48:08 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) 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  * XXX when we implement tablespaces, target Oid will need to be tablespace
 663  * ID not database ID.
 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.tblNode == 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         /* Copy other stats before dropping lock */
 703         numRels = FreeSpaceMap->numRels;
 704         sumRequests = FreeSpaceMap->sumRequests;
 705         LWLockRelease(FreeSpaceLock);
 706
 707         /* Convert stats to actual number of page slots needed */
 708         needed = (sumRequests + numRels) * CHUNKPAGES;
 709
 710         ereport(elevel,
 711                         (errmsg("free space map: %d relations, %d pages stored; %.0f total pages needed",
 712                                         numRels, storedPages, needed),
 713                          errdetail("Allocated FSM size: %d relations + %d pages = %.0f kB shared memory.",
 714                                            MaxFSMRelations, MaxFSMPages,
 715                                            (double) FreeSpaceShmemSize() / 1024.0)));
 716 }
 717
 718 /*
 719  * DumpFreeSpaceMap - dump contents of FSM into a disk file for later reload
 720  *
 721  * This is expected to be called during database shutdown, after updates to
 722  * the FSM have stopped.  We lock the FreeSpaceLock but that's purely pro
 723  * forma --- if anyone else is still accessing FSM, there's a problem.
 724  */
 725 void
 726 DumpFreeSpaceMap(int code, Datum arg)
 727 {
 728         FILE       *fp;
 729         char            cachefilename[MAXPGPATH];
 730         FsmCacheFileHeader header;
 731         FSMRelation *fsmrel;
 732
 733         /* Try to create file */
 734         snprintf(cachefilename, sizeof(cachefilename), "%s/%s",
 735                          DataDir, FSM_CACHE_FILENAME);
 736
 737         unlink(cachefilename);          /* in case it exists w/wrong permissions */
 738
 739         fp = AllocateFile(cachefilename, PG_BINARY_W);
 740         if (fp == NULL)
 741         {
 742                 elog(LOG, "could not write \"%s\": %m", cachefilename);
 743                 return;
 744         }
 745
 746         LWLockAcquire(FreeSpaceLock, LW_EXCLUSIVE);
 747
 748         /* Write file header */
 749         MemSet(&header, 0, sizeof(header));
 750         strcpy(header.label, FSM_CACHE_LABEL);
 751         header.endian = FSM_CACHE_ENDIAN;
 752         header.version = FSM_CACHE_VERSION;
 753         header.numRels = FreeSpaceMap->numRels;
 754         if (fwrite(&header, 1, sizeof(header), fp) != sizeof(header))
 755                 goto write_failed;
 756
 757         /* For each relation, in order from least to most recently used... */
 758         for (fsmrel = FreeSpaceMap->usageListTail;
 759                  fsmrel != NULL;
 760                  fsmrel = fsmrel->priorUsage)
 761         {
 762                 FsmCacheRelHeader relheader;
 763                 int                     nPages;
 764
 765                 /* Write relation header */
 766                 MemSet(&relheader, 0, sizeof(relheader));
 767                 relheader.key = fsmrel->key;
 768                 relheader.isIndex = fsmrel->isIndex;
 769                 relheader.avgRequest = fsmrel->avgRequest;
 770                 relheader.lastPageCount = fsmrel->lastPageCount;
 771                 relheader.storedPages = fsmrel->storedPages;
 772                 if (fwrite(&relheader, 1, sizeof(relheader), fp) != sizeof(relheader))
 773                         goto write_failed;
 774
 775                 /* Write the per-page data directly from the arena */
 776                 nPages = fsmrel->storedPages;
 777                 if (nPages > 0)
 778                 {
 779                         Size            len;
 780                         char       *data;
 781
 782                         if (fsmrel->isIndex)
 783                                 len = nPages * sizeof(IndexFSMPageData);
 784                         else
 785                                 len = nPages * sizeof(FSMPageData);
 786                         data = (char *)
 787                                 (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
 788                         if (fwrite(data, 1, len, fp) != len)
 789                                 goto write_failed;
 790                 }
 791         }
 792
 793         /* Clean up */
 794         LWLockRelease(FreeSpaceLock);
 795
 796         if (FreeFile(fp))
 797         {
 798                 elog(LOG, "could not write \"%s\": %m", cachefilename);
 799                 /* Remove busted cache file */
 800                 unlink(cachefilename);
 801         }
 802
 803         return;
 804
 805 write_failed:
 806         elog(LOG, "could not write \"%s\": %m", cachefilename);
 807
 808         /* Clean up */
 809         LWLockRelease(FreeSpaceLock);
 810
 811         FreeFile(fp);
 812
 813         /* Remove busted cache file */
 814         unlink(cachefilename);
 815 }
 816
 817 /*
 818  * LoadFreeSpaceMap - load contents of FSM from a disk file
 819  *
 820  * This is expected to be called during database startup, before any FSM
 821  * updates begin.  We lock the FreeSpaceLock but that's purely pro
 822  * forma --- if anyone else is accessing FSM yet, there's a problem.
 823  *
 824  * Notes: no complaint is issued if no cache file is found.  If the file is
 825  * found, it is deleted after reading.  Thus, if we crash without a clean
 826  * shutdown, the next cycle of life starts with no FSM data.  To do otherwise,
 827  * we'd need to do significantly more validation in this routine, because of
 828  * the likelihood that what is in the dump file would be out-of-date, eg
 829  * there might be entries for deleted or truncated rels.
 830  */
 831 void
 832 LoadFreeSpaceMap(void)
 833 {
 834         FILE       *fp;
 835         char            cachefilename[MAXPGPATH];
 836         FsmCacheFileHeader header;
 837         int                     relno;
 838
 839         /* Try to open file */
 840         snprintf(cachefilename, sizeof(cachefilename), "%s/%s",
 841                          DataDir, FSM_CACHE_FILENAME);
 842
 843         fp = AllocateFile(cachefilename, PG_BINARY_R);
 844         if (fp == NULL)
 845         {
 846                 if (errno != ENOENT)
 847                         elog(LOG, "could not read \"%s\": %m", cachefilename);
 848                 return;
 849         }
 850
 851         LWLockAcquire(FreeSpaceLock, LW_EXCLUSIVE);
 852
 853         /* Read and verify file header */
 854         if (fread(&header, 1, sizeof(header), fp) != sizeof(header) ||
 855                 strcmp(header.label, FSM_CACHE_LABEL) != 0 ||
 856                 header.endian != FSM_CACHE_ENDIAN ||
 857                 header.version != FSM_CACHE_VERSION ||
 858                 header.numRels < 0)
 859         {
 860                 elog(LOG, "bogus file header in \"%s\"", cachefilename);
 861                 goto read_failed;
 862         }
 863
 864         /* For each relation, in order from least to most recently used... */
 865         for (relno = 0; relno < header.numRels; relno++)
 866         {
 867                 FsmCacheRelHeader relheader;
 868                 Size            len;
 869                 char       *data;
 870                 FSMRelation *fsmrel;
 871                 int                     nPages;
 872                 int                     curAlloc;
 873                 int                     curAllocPages;
 874
 875                 /* Read and verify relation header, as best we can */
 876                 if (fread(&relheader, 1, sizeof(relheader), fp) != sizeof(relheader) ||
 877                         (relheader.isIndex != false && relheader.isIndex != true) ||
 878                         relheader.avgRequest >= BLCKSZ ||
 879                         relheader.lastPageCount < 0 ||
 880                         relheader.storedPages < 0)
 881                 {
 882                         elog(LOG, "bogus rel header in \"%s\"", cachefilename);
 883                         goto read_failed;
 884                 }
 885
 886                 /* Make sure lastPageCount doesn't exceed current MaxFSMPages */
 887                 if (relheader.lastPageCount > MaxFSMPages)
 888                         relheader.lastPageCount = MaxFSMPages;
 889
 890                 /* Read the per-page data */
 891                 nPages = relheader.storedPages;
 892                 if (relheader.isIndex)
 893                         len = nPages * sizeof(IndexFSMPageData);
 894                 else
 895                         len = nPages * sizeof(FSMPageData);
 896                 data = (char *) palloc(len);
 897                 if (fread(data, 1, len, fp) != len)
 898                 {
 899                         elog(LOG, "premature EOF in \"%s\"", cachefilename);
 900                         pfree(data);
 901                         goto read_failed;
 902                 }
 903
 904                 /*
 905                  * Okay, create the FSM entry and insert data into it.  Since the
 906                  * rels were stored in reverse usage order, at the end of the loop
 907                  * they will be correctly usage-ordered in memory; and if
 908                  * MaxFSMRelations is less than it used to be, we will correctly
 909                  * drop the least recently used ones.
 910                  */
 911                 fsmrel = create_fsm_rel(&relheader.key);
 912                 fsmrel->avgRequest = relheader.avgRequest;
 913
 914                 curAlloc = realloc_fsm_rel(fsmrel, relheader.lastPageCount,
 915                                                                    relheader.isIndex);
 916                 if (relheader.isIndex)
 917                 {
 918                         IndexFSMPageData *newLocation;
 919
 920                         curAllocPages = curAlloc * INDEXCHUNKPAGES;
 921
 922                         /*
 923                          * If the data fits in our current allocation, just copy it;
 924                          * otherwise must compress.  But compression is easy: we
 925                          * merely forget extra pages.
 926                          */
 927                         newLocation = (IndexFSMPageData *)
 928                                 (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
 929                         if (nPages > curAllocPages)
 930                                 nPages = curAllocPages;
 931                         memcpy(newLocation, data, nPages * sizeof(IndexFSMPageData));
 932                         fsmrel->storedPages = nPages;
 933                 }
 934                 else
 935                 {
 936                         FSMPageData *newLocation;
 937
 938                         curAllocPages = curAlloc * CHUNKPAGES;
 939
 940                         /*
 941                          * If the data fits in our current allocation, just copy it;
 942                          * otherwise must compress.
 943                          */
 944                         newLocation = (FSMPageData *)
 945                                 (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
 946                         if (nPages <= curAllocPages)
 947                         {
 948                                 memcpy(newLocation, data, nPages * sizeof(FSMPageData));
 949                                 fsmrel->storedPages = nPages;
 950                         }
 951                         else
 952                         {
 953                                 pack_existing_pages(newLocation, curAllocPages,
 954                                                                         (FSMPageData *) data, nPages);
 955                                 fsmrel->storedPages = curAllocPages;
 956                         }
 957                 }
 958
 959                 pfree(data);
 960         }
 961
 962 read_failed:
 963
 964         /* Clean up */
 965         LWLockRelease(FreeSpaceLock);
 966
 967         FreeFile(fp);
 968
 969         /* Remove cache file before it can become stale; see notes above */
 970         unlink(cachefilename);
 971 }
 972
 973
 974 /*
 975  * Internal routines.  These all assume the caller holds the FreeSpaceLock.
 976  */
 977
 978 /*
 979  * Lookup a relation in the hash table.  If not present, return NULL.
 980  *
 981  * The relation's position in the LRU list is not changed.
 982  */
 983 static FSMRelation *
 984 lookup_fsm_rel(RelFileNode *rel)
 985 {
 986         FSMRelation *fsmrel;
 987
 988         fsmrel = (FSMRelation *) hash_search(FreeSpaceMapRelHash,
 989                                                                                  (void *) rel,
 990                                                                                  HASH_FIND,
 991                                                                                  NULL);
 992         if (!fsmrel)
 993                 return NULL;
 994
 995         return fsmrel;
 996 }
 997
 998 /*
 999  * Lookup a relation in the hash table, creating an entry if not present.
1000  *
1001  * On successful lookup, the relation is moved to the front of the LRU list.
1002  */
1003 static FSMRelation *
1004 create_fsm_rel(RelFileNode *rel)
1005 {
1006         FSMRelation *fsmrel;
1007         bool            found;
1008
1009         fsmrel = (FSMRelation *) hash_search(FreeSpaceMapRelHash,
1010                                                                                  (void *) rel,
1011                                                                                  HASH_ENTER,
1012                                                                                  &found);
1013         if (!fsmrel)
1014                 ereport(ERROR,
1015                                 (errcode(ERRCODE_OUT_OF_MEMORY),
1016                                  errmsg("out of shared memory")));
1017
1018         if (!found)
1019         {
1020                 /* New hashtable entry, initialize it (hash_search set the key) */
1021                 fsmrel->isIndex = false;        /* until we learn different */
1022                 fsmrel->avgRequest = INITIAL_AVERAGE;
1023                 fsmrel->lastPageCount = 0;
1024                 fsmrel->firstChunk = -1;        /* no space allocated */
1025                 fsmrel->storedPages = 0;
1026                 fsmrel->nextPage = 0;
1027
1028                 /* Discard lowest-priority existing rel, if we are over limit */
1029                 if (FreeSpaceMap->numRels >= MaxFSMRelations)
1030                         delete_fsm_rel(FreeSpaceMap->usageListTail);
1031
1032                 /* Add new entry at front of LRU list */
1033                 link_fsm_rel_usage(fsmrel);
1034                 fsmrel->nextPhysical = NULL;    /* not in physical-storage list */
1035                 fsmrel->priorPhysical = NULL;
1036                 FreeSpaceMap->numRels++;
1037                 /* sumRequests is unchanged because request must be zero */
1038         }
1039         else
1040         {
1041                 /* Existing entry, move to front of LRU list */
1042                 if (fsmrel->priorUsage != NULL)
1043                 {
1044                         unlink_fsm_rel_usage(fsmrel);
1045                         link_fsm_rel_usage(fsmrel);
1046                 }
1047         }
1048
1049         return fsmrel;
1050 }
1051
1052 /*
1053  * Remove an existing FSMRelation entry.
1054  */
1055 static void
1056 delete_fsm_rel(FSMRelation *fsmrel)
1057 {
1058         FSMRelation *result;
1059
1060         FreeSpaceMap->sumRequests -= fsm_calc_request(fsmrel);
1061         unlink_fsm_rel_usage(fsmrel);
1062         unlink_fsm_rel_storage(fsmrel);
1063         FreeSpaceMap->numRels--;
1064         result = (FSMRelation *) hash_search(FreeSpaceMapRelHash,
1065                                                                                  (void *) &(fsmrel->key),
1066                                                                                  HASH_REMOVE,
1067                                                                                  NULL);
1068         if (!result)
1069                 elog(ERROR, "FreeSpaceMap hashtable corrupted");
1070 }
1071
1072 /*
1073  * Reallocate space for a FSMRelation.
1074  *
1075  * This is shared code for RecordRelationFreeSpace and RecordIndexFreeSpace.
1076  * The return value is the actual new allocation, in chunks.
1077  */
1078 static int
1079 realloc_fsm_rel(FSMRelation *fsmrel, int nPages, bool isIndex)
1080 {
1081         int                     myRequest;
1082         int                     myAlloc;
1083         int                     curAlloc;
1084
1085         /*
1086          * Delete any existing entries, and update request status.
1087          */
1088         fsmrel->storedPages = 0;
1089         FreeSpaceMap->sumRequests -= fsm_calc_request(fsmrel);
1090         fsmrel->lastPageCount = nPages;
1091         fsmrel->isIndex = isIndex;
1092         myRequest = fsm_calc_request(fsmrel);
1093         FreeSpaceMap->sumRequests += myRequest;
1094         myAlloc = fsm_calc_target_allocation(myRequest);
1095
1096         /*
1097          * Need to reallocate space if (a) my target allocation is more than
1098          * my current allocation, AND (b) my actual immediate need
1099          * (myRequest+1 chunks) is more than my current allocation. Otherwise
1100          * just store the new data in-place.
1101          */
1102         curAlloc = fsm_current_allocation(fsmrel);
1103         if (myAlloc > curAlloc && (myRequest + 1) > curAlloc && nPages > 0)
1104         {
1105                 /* Remove entry from storage list, and compact */
1106                 unlink_fsm_rel_storage(fsmrel);
1107                 compact_fsm_storage();
1108                 /* Reattach to end of storage list */
1109                 link_fsm_rel_storage(fsmrel);
1110                 /* And allocate storage */
1111                 fsmrel->firstChunk = FreeSpaceMap->usedChunks;
1112                 FreeSpaceMap->usedChunks += myAlloc;
1113                 curAlloc = myAlloc;
1114                 /* Watch out for roundoff error */
1115                 if (FreeSpaceMap->usedChunks > FreeSpaceMap->totalChunks)
1116                 {
1117                         FreeSpaceMap->usedChunks = FreeSpaceMap->totalChunks;
1118                         curAlloc = FreeSpaceMap->totalChunks - fsmrel->firstChunk;
1119                 }
1120         }
1121         return curAlloc;
1122 }
1123
1124 /*
1125  * Link a FSMRelation into the LRU list (always at the head).
1126  */
1127 static void
1128 link_fsm_rel_usage(FSMRelation *fsmrel)
1129 {
1130         fsmrel->priorUsage = NULL;
1131         fsmrel->nextUsage = FreeSpaceMap->usageList;
1132         FreeSpaceMap->usageList = fsmrel;
1133         if (fsmrel->nextUsage != NULL)
1134                 fsmrel->nextUsage->priorUsage = fsmrel;
1135         else
1136                 FreeSpaceMap->usageListTail = fsmrel;
1137 }
1138
1139 /*
1140  * Delink a FSMRelation from the LRU list.
1141  */
1142 static void
1143 unlink_fsm_rel_usage(FSMRelation *fsmrel)
1144 {
1145         if (fsmrel->priorUsage != NULL)
1146                 fsmrel->priorUsage->nextUsage = fsmrel->nextUsage;
1147         else
1148                 FreeSpaceMap->usageList = fsmrel->nextUsage;
1149         if (fsmrel->nextUsage != NULL)
1150                 fsmrel->nextUsage->priorUsage = fsmrel->priorUsage;
1151         else
1152                 FreeSpaceMap->usageListTail = fsmrel->priorUsage;
1153
1154         /*
1155          * We don't bother resetting fsmrel's links, since it's about to be
1156          * deleted or relinked at the head.
1157          */
1158 }
1159
1160 /*
1161  * Link a FSMRelation into the storage-order list (always at the tail).
1162  */
1163 static void
1164 link_fsm_rel_storage(FSMRelation *fsmrel)
1165 {
1166         fsmrel->nextPhysical = NULL;
1167         fsmrel->priorPhysical = FreeSpaceMap->lastRel;
1168         if (FreeSpaceMap->lastRel != NULL)
1169                 FreeSpaceMap->lastRel->nextPhysical = fsmrel;
1170         else
1171                 FreeSpaceMap->firstRel = fsmrel;
1172         FreeSpaceMap->lastRel = fsmrel;
1173 }
1174
1175 /*
1176  * Delink a FSMRelation from the storage-order list, if it's in it.
1177  */
1178 static void
1179 unlink_fsm_rel_storage(FSMRelation *fsmrel)
1180 {
1181         if (fsmrel->priorPhysical != NULL || FreeSpaceMap->firstRel == fsmrel)
1182         {
1183                 if (fsmrel->priorPhysical != NULL)
1184                         fsmrel->priorPhysical->nextPhysical = fsmrel->nextPhysical;
1185                 else
1186                         FreeSpaceMap->firstRel = fsmrel->nextPhysical;
1187                 if (fsmrel->nextPhysical != NULL)
1188                         fsmrel->nextPhysical->priorPhysical = fsmrel->priorPhysical;
1189                 else
1190                         FreeSpaceMap->lastRel = fsmrel->priorPhysical;
1191         }
1192         /* mark as not in list, since we may not put it back immediately */
1193         fsmrel->nextPhysical = NULL;
1194         fsmrel->priorPhysical = NULL;
1195         /* Also mark it as having no storage */
1196         fsmrel->firstChunk = -1;
1197         fsmrel->storedPages = 0;
1198 }
1199
1200 /*
1201  * Look to see if a page with at least the specified amount of space is
1202  * available in the given FSMRelation.  If so, return its page number,
1203  * and advance the nextPage counter so that the next inquiry will return
1204  * a different page if possible; also update the entry to show that the
1205  * requested space is not available anymore.  Return InvalidBlockNumber
1206  * if no success.
1207  */
1208 static BlockNumber
1209 find_free_space(FSMRelation *fsmrel, Size spaceNeeded)
1210 {
1211         FSMPageData *info;
1212         int                     pagesToCheck,   /* outer loop counter */
1213                                 pageIndex;              /* current page index */
1214
1215         if (fsmrel->isIndex)
1216                 elog(ERROR, "find_free_space called for an index relation");
1217         info = (FSMPageData *)
1218                 (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
1219         pageIndex = fsmrel->nextPage;
1220         /* Last operation may have left nextPage pointing past end */
1221         if (pageIndex >= fsmrel->storedPages)
1222                 pageIndex = 0;
1223
1224         for (pagesToCheck = fsmrel->storedPages; pagesToCheck > 0; pagesToCheck--)
1225         {
1226                 FSMPageData *page = info + pageIndex;
1227                 Size            spaceAvail = FSMPageGetSpace(page);
1228
1229                 /* Check this page */
1230                 if (spaceAvail >= spaceNeeded)
1231                 {
1232                         /*
1233                          * Found what we want --- adjust the entry, and update
1234                          * nextPage.
1235                          */
1236                         FSMPageSetSpace(page, spaceAvail - spaceNeeded);
1237                         fsmrel->nextPage = pageIndex + 1;
1238                         return FSMPageGetPageNum(page);
1239                 }
1240                 /* Advance pageIndex, wrapping around if needed */
1241                 if (++pageIndex >= fsmrel->storedPages)
1242                         pageIndex = 0;
1243         }
1244
1245         return InvalidBlockNumber;      /* nothing found */
1246 }
1247
1248 /*
1249  * As above, but for index case --- we only deal in whole pages.
1250  */
1251 static BlockNumber
1252 find_index_free_space(FSMRelation *fsmrel)
1253 {
1254         IndexFSMPageData *info;
1255         BlockNumber result;
1256
1257         /*
1258          * If isIndex isn't set, it could be that RecordIndexFreeSpace() has
1259          * never yet been called on this relation, and we're still looking at
1260          * the default setting from create_fsm_rel().  If so, just act as
1261          * though there's no space.
1262          */
1263         if (!fsmrel->isIndex)
1264         {
1265                 if (fsmrel->storedPages == 0)
1266                         return InvalidBlockNumber;
1267                 elog(ERROR, "find_index_free_space called for a non-index relation");
1268         }
1269
1270         /*
1271          * For indexes, there's no need for the nextPage state variable; we
1272          * just remove and return the first available page.  (We could save
1273          * cycles here by returning the last page, but it seems better to
1274          * encourage re-use of lower-numbered pages.)
1275          */
1276         if (fsmrel->storedPages <= 0)
1277                 return InvalidBlockNumber;              /* no pages available */
1278         info = (IndexFSMPageData *)
1279                 (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
1280         result = IndexFSMPageGetPageNum(info);
1281         fsmrel->storedPages--;
1282         memmove(info, info + 1, fsmrel->storedPages * sizeof(IndexFSMPageData));
1283         return result;
1284 }
1285
1286 /*
1287  * fsm_record_free_space - guts of RecordFreeSpace operation (now only
1288  * provided as part of RecordAndGetPageWithFreeSpace).
1289  */
1290 static void
1291 fsm_record_free_space(FSMRelation *fsmrel, BlockNumber page, Size spaceAvail)
1292 {
1293         int                     pageIndex;
1294
1295         if (fsmrel->isIndex)
1296                 elog(ERROR, "fsm_record_free_space called for an index relation");
1297         if (lookup_fsm_page_entry(fsmrel, page, &pageIndex))
1298         {
1299                 /* Found an existing entry for page; update it */
1300                 FSMPageData *info;
1301
1302                 info = (FSMPageData *)
1303                         (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
1304                 info += pageIndex;
1305                 FSMPageSetSpace(info, spaceAvail);
1306         }
1307         else
1308         {
1309                 /*
1310                  * No existing entry; ignore the call.  We used to add the page to
1311                  * the FSM --- but in practice, if the page hasn't got enough
1312                  * space to satisfy the caller who's kicking it back to us, then
1313                  * it's probably uninteresting to everyone else as well.
1314                  */
1315         }
1316 }
1317
1318 /*
1319  * Look for an entry for a specific page (block number) in a FSMRelation.
1320  * Returns TRUE if a matching entry exists, else FALSE.
1321  *
1322  * The output argument *outPageIndex is set to indicate where the entry exists
1323  * (if TRUE result) or could be inserted (if FALSE result).
1324  */
1325 static bool
1326 lookup_fsm_page_entry(FSMRelation *fsmrel, BlockNumber page,
1327                                           int *outPageIndex)
1328 {
1329         /* Check for empty relation */
1330         if (fsmrel->storedPages <= 0)
1331         {
1332                 *outPageIndex = 0;
1333                 return false;
1334         }
1335
1336         /* Do binary search */
1337         if (fsmrel->isIndex)
1338         {
1339                 IndexFSMPageData *info;
1340                 int                     low,
1341                                         high;
1342
1343                 info = (IndexFSMPageData *)
1344                         (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
1345                 low = 0;
1346                 high = fsmrel->storedPages - 1;
1347                 while (low <= high)
1348                 {
1349                         int                     middle;
1350                         BlockNumber probe;
1351
1352                         middle = low + (high - low) / 2;
1353                         probe = IndexFSMPageGetPageNum(info + middle);
1354                         if (probe == page)
1355                         {
1356                                 *outPageIndex = middle;
1357                                 return true;
1358                         }
1359                         else if (probe < page)
1360                                 low = middle + 1;
1361                         else
1362                                 high = middle - 1;
1363                 }
1364                 *outPageIndex = low;
1365                 return false;
1366         }
1367         else
1368         {
1369                 FSMPageData *info;
1370                 int                     low,
1371                                         high;
1372
1373                 info = (FSMPageData *)
1374                         (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
1375                 low = 0;
1376                 high = fsmrel->storedPages - 1;
1377                 while (low <= high)
1378                 {
1379                         int                     middle;
1380                         BlockNumber probe;
1381
1382                         middle = low + (high - low) / 2;
1383                         probe = FSMPageGetPageNum(info + middle);
1384                         if (probe == page)
1385                         {
1386                                 *outPageIndex = middle;
1387                                 return true;
1388                         }
1389                         else if (probe < page)
1390                                 low = middle + 1;
1391                         else
1392                                 high = middle - 1;
1393                 }
1394                 *outPageIndex = low;
1395                 return false;
1396         }
1397 }
1398
1399 /*
1400  * Re-pack the FSM storage arena, dropping data if necessary to meet the
1401  * current allocation target for each relation.  At conclusion, all available
1402  * space in the arena will be coalesced at the end.
1403  */
1404 static void
1405 compact_fsm_storage(void)
1406 {
1407         int                     nextChunkIndex = 0;
1408         bool            did_push = false;
1409         FSMRelation *fsmrel;
1410
1411         for (fsmrel = FreeSpaceMap->firstRel;
1412                  fsmrel != NULL;
1413                  fsmrel = fsmrel->nextPhysical)
1414         {
1415                 int                     newAlloc;
1416                 int                     newAllocPages;
1417                 int                     newChunkIndex;
1418                 int                     oldChunkIndex;
1419                 int                     curChunks;
1420                 char       *newLocation;
1421                 char       *oldLocation;
1422
1423                 /*
1424                  * Calculate target allocation, make sure we don't overrun due to
1425                  * roundoff error
1426                  */
1427                 newAlloc = fsm_calc_target_allocation(fsm_calc_request(fsmrel));
1428                 if (newAlloc > FreeSpaceMap->totalChunks - nextChunkIndex)
1429                         newAlloc = FreeSpaceMap->totalChunks - nextChunkIndex;
1430                 if (fsmrel->isIndex)
1431                         newAllocPages = newAlloc * INDEXCHUNKPAGES;
1432                 else
1433                         newAllocPages = newAlloc * CHUNKPAGES;
1434
1435                 /*
1436                  * Determine current size, current and new locations
1437                  */
1438                 curChunks = fsm_current_chunks(fsmrel);
1439                 oldChunkIndex = fsmrel->firstChunk;
1440                 oldLocation = FreeSpaceMap->arena + oldChunkIndex * CHUNKBYTES;
1441                 newChunkIndex = nextChunkIndex;
1442                 newLocation = FreeSpaceMap->arena + newChunkIndex * CHUNKBYTES;
1443
1444                 /*
1445                  * It's possible that we have to move data down, not up, if the
1446                  * allocations of previous rels expanded.  This normally means that
1447                  * our allocation expanded too (or at least got no worse), and
1448                  * ditto for later rels.  So there should be room to move all our
1449                  * data down without dropping any --- but we might have to push down
1450                  * following rels to acquire the room.  We don't want to do the push
1451                  * more than once, so pack everything against the end of the arena
1452                  * if so.
1453                  *
1454                  * In corner cases where we are on the short end of a roundoff choice
1455                  * that we were formerly on the long end of, it's possible that we
1456                  * have to move down and compress our data too.  In fact, even after
1457                  * pushing down the following rels, there might not be as much space
1458                  * as we computed for this rel above --- that would imply that some
1459                  * following rel(s) are also on the losing end of roundoff choices.
1460                  * We could handle this fairly by doing the per-rel compactions
1461                  * out-of-order, but that seems like way too much complexity to deal
1462                  * with a very infrequent corner case.  Instead, we simply drop pages
1463                  * from the end of the current rel's data until it fits.
1464                  */
1465                 if (newChunkIndex > oldChunkIndex)
1466                 {
1467                         int                     limitChunkIndex;
1468
1469                         if (newAllocPages < fsmrel->storedPages)
1470                         {
1471                                 /* move and compress --- just drop excess pages */
1472                                 fsmrel->storedPages = newAllocPages;
1473                                 curChunks = fsm_current_chunks(fsmrel);
1474                         }
1475                         /* is there enough space? */
1476                         if (fsmrel->nextPhysical != NULL)
1477                                 limitChunkIndex = fsmrel->nextPhysical->firstChunk;
1478                         else
1479                                 limitChunkIndex = FreeSpaceMap->totalChunks;
1480                         if (newChunkIndex + curChunks > limitChunkIndex)
1481                         {
1482                                 /* not enough space, push down following rels */
1483                                 if (!did_push)
1484                                 {
1485                                         push_fsm_rels_after(fsmrel);
1486                                         did_push = true;
1487                                 }
1488                                 /* now is there enough space? */
1489                                 if (fsmrel->nextPhysical != NULL)
1490                                         limitChunkIndex = fsmrel->nextPhysical->firstChunk;
1491                                 else
1492                                         limitChunkIndex = FreeSpaceMap->totalChunks;
1493                                 if (newChunkIndex + curChunks > limitChunkIndex)
1494                                 {
1495                                         /* uh-oh, forcibly cut the allocation to fit */
1496                                         newAlloc = limitChunkIndex - newChunkIndex;
1497                                         /*
1498                                          * If newAlloc < 0 at this point, we are moving the rel's
1499                                          * firstChunk into territory currently assigned to a later
1500                                          * rel.  This is okay so long as we do not copy any data.
1501                                          * The rels will be back in nondecreasing firstChunk order
1502                                          * at completion of the compaction pass.
1503                                          */
1504                                         if (newAlloc < 0)
1505                                                 newAlloc = 0;
1506                                         if (fsmrel->isIndex)
1507                                                 newAllocPages = newAlloc * INDEXCHUNKPAGES;
1508                                         else
1509                                                 newAllocPages = newAlloc * CHUNKPAGES;
1510                                         fsmrel->storedPages = newAllocPages;
1511                                         curChunks = fsm_current_chunks(fsmrel);
1512                                 }
1513                         }
1514                         memmove(newLocation, oldLocation, curChunks * CHUNKBYTES);
1515                 }
1516                 else if (newAllocPages < fsmrel->storedPages)
1517                 {
1518                         /*
1519                          * Need to compress the page data.      For an index,
1520                          * "compression" just means dropping excess pages; otherwise
1521                          * we try to keep the ones with the most space.
1522                          */
1523                         if (fsmrel->isIndex)
1524                         {
1525                                 fsmrel->storedPages = newAllocPages;
1526                                 /* may need to move data */
1527                                 if (newChunkIndex != oldChunkIndex)
1528                                         memmove(newLocation, oldLocation, newAlloc * CHUNKBYTES);
1529                         }
1530                         else
1531                         {
1532                                 pack_existing_pages((FSMPageData *) newLocation,
1533                                                                         newAllocPages,
1534                                                                         (FSMPageData *) oldLocation,
1535                                                                         fsmrel->storedPages);
1536                                 fsmrel->storedPages = newAllocPages;
1537                         }
1538                 }
1539                 else if (newChunkIndex != oldChunkIndex)
1540                 {
1541                         /*
1542                          * No compression needed, but must copy the data up
1543                          */
1544                         memmove(newLocation, oldLocation, curChunks * CHUNKBYTES);
1545                 }
1546                 fsmrel->firstChunk = newChunkIndex;
1547                 nextChunkIndex += newAlloc;
1548         }
1549         Assert(nextChunkIndex <= FreeSpaceMap->totalChunks);
1550         FreeSpaceMap->usedChunks = nextChunkIndex;
1551 }
1552
1553 /*
1554  * Push all FSMRels physically after afterRel to the end of the storage arena.
1555  *
1556  * We sometimes have to do this when deletion or truncation of a relation
1557  * causes the allocations of remaining rels to expand markedly.  We must
1558  * temporarily push existing data down to the end so that we can move it
1559  * back up in an orderly fashion.
1560  */
1561 static void
1562 push_fsm_rels_after(FSMRelation *afterRel)
1563 {
1564         int                     nextChunkIndex = FreeSpaceMap->totalChunks;
1565         FSMRelation *fsmrel;
1566
1567         FreeSpaceMap->usedChunks = FreeSpaceMap->totalChunks;
1568
1569         for (fsmrel = FreeSpaceMap->lastRel;
1570                  fsmrel != NULL;
1571                  fsmrel = fsmrel->priorPhysical)
1572         {
1573                 int                     chunkCount;
1574                 int                     newChunkIndex;
1575                 int                     oldChunkIndex;
1576                 char       *newLocation;
1577                 char       *oldLocation;
1578
1579                 if (fsmrel == afterRel)
1580                         break;
1581
1582                 chunkCount = fsm_current_chunks(fsmrel);
1583                 nextChunkIndex -= chunkCount;
1584                 newChunkIndex = nextChunkIndex;
1585                 oldChunkIndex = fsmrel->firstChunk;
1586                 if (newChunkIndex < oldChunkIndex)
1587                 {
1588                         /* we're pushing down, how can it move up? */
1589                         elog(PANIC, "inconsistent entry sizes in FSM");
1590                 }
1591                 else if (newChunkIndex > oldChunkIndex)
1592                 {
1593                         /* need to move it */
1594                         newLocation = FreeSpaceMap->arena + newChunkIndex * CHUNKBYTES;
1595                         oldLocation = FreeSpaceMap->arena + oldChunkIndex * CHUNKBYTES;
1596                         memmove(newLocation, oldLocation, chunkCount * CHUNKBYTES);
1597                         fsmrel->firstChunk = newChunkIndex;
1598                 }
1599         }
1600         Assert(nextChunkIndex >= 0);
1601 }
1602
1603 /*
1604  * Pack a set of per-page freespace data into a smaller amount of space.
1605  *
1606  * The method is to compute a low-resolution histogram of the free space
1607  * amounts, then determine which histogram bin contains the break point.
1608  * We then keep all pages above that bin, none below it, and just enough
1609  * of the pages in that bin to fill the output area exactly.
1610  */
1611 #define HISTOGRAM_BINS  64
1612
1613 static void
1614 pack_incoming_pages(FSMPageData *newLocation, int newPages,
1615                                         PageFreeSpaceInfo *pageSpaces, int nPages)
1616 {
1617         int                     histogram[HISTOGRAM_BINS];
1618         int                     above,
1619                                 binct,
1620                                 i;
1621         Size            thresholdL,
1622                                 thresholdU;
1623
1624         Assert(newPages < nPages);      /* else I shouldn't have been called */
1625         /* Build histogram */
1626         MemSet(histogram, 0, sizeof(histogram));
1627         for (i = 0; i < nPages; i++)
1628         {
1629                 Size            avail = pageSpaces[i].avail;
1630
1631                 if (avail >= BLCKSZ)
1632                         elog(ERROR, "bogus freespace amount");
1633                 avail /= (BLCKSZ / HISTOGRAM_BINS);
1634                 histogram[avail]++;
1635         }
1636         /* Find the breakpoint bin */
1637         above = 0;
1638         for (i = HISTOGRAM_BINS - 1; i >= 0; i--)
1639         {
1640                 int                     sum = above + histogram[i];
1641
1642                 if (sum > newPages)
1643                         break;
1644                 above = sum;
1645         }
1646         Assert(i >= 0);
1647         thresholdL = i * BLCKSZ / HISTOGRAM_BINS;       /* low bound of bp bin */
1648         thresholdU = (i + 1) * BLCKSZ / HISTOGRAM_BINS;         /* hi bound */
1649         binct = newPages - above;       /* number to take from bp bin */
1650         /* And copy the appropriate data */
1651         for (i = 0; i < nPages; i++)
1652         {
1653                 BlockNumber page = pageSpaces[i].blkno;
1654                 Size            avail = pageSpaces[i].avail;
1655
1656                 /* Check caller provides sorted data */
1657                 if (i > 0 && page <= pageSpaces[i - 1].blkno)
1658                         elog(ERROR, "free-space data is not in page order");
1659                 /* Save this page? */
1660                 if (avail >= thresholdU ||
1661                         (avail >= thresholdL && (--binct >= 0)))
1662                 {
1663                         FSMPageSetPageNum(newLocation, page);
1664                         FSMPageSetSpace(newLocation, avail);
1665                         newLocation++;
1666                         newPages--;
1667                 }
1668         }
1669         Assert(newPages == 0);
1670 }
1671
1672 /*
1673  * Pack a set of per-page freespace data into a smaller amount of space.
1674  *
1675  * This is algorithmically identical to pack_incoming_pages(), but accepts
1676  * a different input representation.  Also, we assume the input data has
1677  * previously been checked for validity (size in bounds, pages in order).
1678  *
1679  * Note: it is possible for the source and destination arrays to overlap.
1680  * The caller is responsible for making sure newLocation is at lower addresses
1681  * so that we can copy data moving forward in the arrays without problem.
1682  */
1683 static void
1684 pack_existing_pages(FSMPageData *newLocation, int newPages,
1685                                         FSMPageData *oldLocation, int oldPages)
1686 {
1687         int                     histogram[HISTOGRAM_BINS];
1688         int                     above,
1689                                 binct,
1690                                 i;
1691         Size            thresholdL,
1692                                 thresholdU;
1693
1694         Assert(newPages < oldPages);    /* else I shouldn't have been called */
1695         /* Build histogram */
1696         MemSet(histogram, 0, sizeof(histogram));
1697         for (i = 0; i < oldPages; i++)
1698         {
1699                 Size            avail = FSMPageGetSpace(oldLocation + i);
1700
1701                 /* Shouldn't happen, but test to protect against stack clobber */
1702                 if (avail >= BLCKSZ)
1703                         elog(ERROR, "bogus freespace amount");
1704                 avail /= (BLCKSZ / HISTOGRAM_BINS);
1705                 histogram[avail]++;
1706         }
1707         /* Find the breakpoint bin */
1708         above = 0;
1709         for (i = HISTOGRAM_BINS - 1; i >= 0; i--)
1710         {
1711                 int                     sum = above + histogram[i];
1712
1713                 if (sum > newPages)
1714                         break;
1715                 above = sum;
1716         }
1717         Assert(i >= 0);
1718         thresholdL = i * BLCKSZ / HISTOGRAM_BINS;       /* low bound of bp bin */
1719         thresholdU = (i + 1) * BLCKSZ / HISTOGRAM_BINS;         /* hi bound */
1720         binct = newPages - above;       /* number to take from bp bin */
1721         /* And copy the appropriate data */
1722         for (i = 0; i < oldPages; i++)
1723         {
1724                 BlockNumber page = FSMPageGetPageNum(oldLocation + i);
1725                 Size            avail = FSMPageGetSpace(oldLocation + i);
1726
1727                 /* Save this page? */
1728                 if (avail >= thresholdU ||
1729                         (avail >= thresholdL && (--binct >= 0)))
1730                 {
1731                         FSMPageSetPageNum(newLocation, page);
1732                         FSMPageSetSpace(newLocation, avail);
1733                         newLocation++;
1734                         newPages--;
1735                 }
1736         }
1737         Assert(newPages == 0);
1738 }
1739
1740 /*
1741  * Calculate number of chunks "requested" by a rel.
1742  *
1743  * Rel's lastPageCount and isIndex settings must be up-to-date when called.
1744  *
1745  * See notes at top of file for details.
1746  */
1747 static int
1748 fsm_calc_request(FSMRelation *fsmrel)
1749 {
1750         int                     chunkCount;
1751
1752         /* Convert page count to chunk count */
1753         if (fsmrel->isIndex)
1754                 chunkCount = (fsmrel->lastPageCount - 1) / INDEXCHUNKPAGES + 1;
1755         else
1756                 chunkCount = (fsmrel->lastPageCount - 1) / CHUNKPAGES + 1;
1757         /* "Request" is anything beyond our one guaranteed chunk */
1758         if (chunkCount <= 0)
1759                 return 0;
1760         else
1761                 return chunkCount - 1;
1762 }
1763
1764 /*
1765  * Calculate target allocation (number of chunks) for a rel
1766  *
1767  * Parameter is the result from fsm_calc_request().  The global sumRequests
1768  * and numRels totals must be up-to-date already.
1769  *
1770  * See notes at top of file for details.
1771  */
1772 static int
1773 fsm_calc_target_allocation(int myRequest)
1774 {
1775         double          spareChunks;
1776         int                     extra;
1777
1778         spareChunks = FreeSpaceMap->totalChunks - FreeSpaceMap->numRels;
1779         Assert(spareChunks > 0);
1780         if (spareChunks >= FreeSpaceMap->sumRequests)
1781         {
1782                 /* We aren't oversubscribed, so allocate exactly the request */
1783                 extra = myRequest;
1784         }
1785         else
1786         {
1787                 extra = (int) rint(spareChunks * myRequest / FreeSpaceMap->sumRequests);
1788                 if (extra < 0)                  /* shouldn't happen, but make sure */
1789                         extra = 0;
1790         }
1791         return 1 + extra;
1792 }
1793
1794 /*
1795  * Calculate number of chunks actually used to store current data
1796  */
1797 static int
1798 fsm_current_chunks(FSMRelation *fsmrel)
1799 {
1800         int                     chunkCount;
1801
1802         /* Make sure storedPages==0 produces right answer */
1803         if (fsmrel->storedPages <= 0)
1804                 return 0;
1805         /* Convert page count to chunk count */
1806         if (fsmrel->isIndex)
1807                 chunkCount = (fsmrel->storedPages - 1) / INDEXCHUNKPAGES + 1;
1808         else
1809                 chunkCount = (fsmrel->storedPages - 1) / CHUNKPAGES + 1;
1810         return chunkCount;
1811 }
1812
1813 /*
1814  * Calculate current actual allocation (number of chunks) for a rel
1815  */
1816 static int
1817 fsm_current_allocation(FSMRelation *fsmrel)
1818 {
1819         if (fsmrel->nextPhysical != NULL)
1820                 return fsmrel->nextPhysical->firstChunk - fsmrel->firstChunk;
1821         else if (fsmrel == FreeSpaceMap->lastRel)
1822                 return FreeSpaceMap->usedChunks - fsmrel->firstChunk;
1823         else
1824         {
1825                 /* it's not in the storage-order list */
1826                 Assert(fsmrel->firstChunk < 0 && fsmrel->storedPages == 0);
1827                 return 0;
1828         }
1829 }
1830
1831
1832 #ifdef FREESPACE_DEBUG
1833 /*
1834  * Dump contents of freespace map for debugging.
1835  *
1836  * We assume caller holds the FreeSpaceLock, or is otherwise unconcerned
1837  * about other processes.
1838  */
1839 void
1840 DumpFreeSpace(void)
1841 {
1842         FSMRelation *fsmrel;
1843         FSMRelation *prevrel = NULL;
1844         int                     relNum = 0;
1845         int                     nPages;
1846
1847         for (fsmrel = FreeSpaceMap->usageList; fsmrel; fsmrel = fsmrel->nextUsage)
1848         {
1849                 relNum++;
1850                 fprintf(stderr, "Map %d: rel %u/%u isIndex %d avgRequest %u lastPageCount %d nextPage %d\nMap= ",
1851                                 relNum, fsmrel->key.tblNode, fsmrel->key.relNode,
1852                                 (int) fsmrel->isIndex, fsmrel->avgRequest,
1853                                 fsmrel->lastPageCount, fsmrel->nextPage);
1854                 if (fsmrel->isIndex)
1855                 {
1856                         IndexFSMPageData *page;
1857
1858                         page = (IndexFSMPageData *)
1859                                 (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
1860                         for (nPages = 0; nPages < fsmrel->storedPages; nPages++)
1861                         {
1862                                 fprintf(stderr, " %u",
1863                                                 IndexFSMPageGetPageNum(page));
1864                                 page++;
1865                         }
1866                 }
1867                 else
1868                 {
1869                         FSMPageData *page;
1870
1871                         page = (FSMPageData *)
1872                                 (FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
1873                         for (nPages = 0; nPages < fsmrel->storedPages; nPages++)
1874                         {
1875                                 fprintf(stderr, " %u:%u",
1876                                                 FSMPageGetPageNum(page),
1877                                                 FSMPageGetSpace(page));
1878                                 page++;
1879                         }
1880                 }
1881                 fprintf(stderr, "\n");
1882                 /* Cross-check list links */
1883                 if (prevrel != fsmrel->priorUsage)
1884                         fprintf(stderr, "DumpFreeSpace: broken list links\n");
1885                 prevrel = fsmrel;
1886         }
1887         if (prevrel != FreeSpaceMap->usageListTail)
1888                 fprintf(stderr, "DumpFreeSpace: broken list links\n");
1889         /* Cross-check global counters */
1890         if (relNum != FreeSpaceMap->numRels)
1891                 fprintf(stderr, "DumpFreeSpace: %d rels in list, but numRels = %d\n",
1892                                 relNum, FreeSpaceMap->numRels);
1893 }
1894
1895 #endif   /* FREESPACE_DEBUG */