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