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