src/backend/storage/freespace/freespace.c

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