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-2002, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  * IDENTIFICATION
  11  *        $Header: /cvsroot/pgsql/src/backend/storage/freespace/freespace.c,v 1.12 2002/06/20 20:29:34 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 frequently used relation.      A previously-unknown relation is always
  24  * entered into the map with useCount 1 on first reference, even if this
  25  * causes an existing entry with higher useCount to be discarded.  This may
  26  * cause a little bit of thrashing among the bottom entries in the list,
  27  * but if we didn't do it then there'd be no way for a relation not in the
  28  * map to get in once the map is full.  Note we allow a relation to be in the
  29  * map even if no pages are currently stored for it: this allows us to track
  30  * its useCount & threshold, which may eventually go high enough to give it
  31  * priority for page storage.
  32  *
  33  * The total number of pages tracked is also set by a configuration variable
  34  * (MaxFSMPages).  We allocate these dynamically among the known relations,
  35  * giving preference to the more-frequently-referenced relations and those
  36  * with smaller tuples.  This is done by a thresholding mechanism: for each
  37  * relation we keep track of a current target threshold, and allow only pages
  38  * with free space >= threshold to be stored in the map.  The threshold starts
  39  * at BLCKSZ/2 (a somewhat arbitrary choice) for a newly entered relation.
  40  * On each GetFreeSpace reference, the threshold is moved towards the
  41  * request size using a slow exponential moving average; this means that
  42  * for heavily used relations, the threshold will approach the average
  43  * freespace request size (average tuple size).  Whenever we run out of
  44  * storage space in the map, we double the threshold of all existing relations
  45  * (but not to more than BLCKSZ, so as to prevent runaway thresholds).
  46  * Infrequently used relations will thus tend to have large thresholds.
  47  *
  48  * XXX this thresholding mechanism is experimental; need to see how well
  49  * it works in practice.
  50  *
  51  *-------------------------------------------------------------------------
  52  */
  53 #include "postgres.h"
  54
  55 #include <limits.h>
  56
  57 #include "storage/freespace.h"
  58 #include "storage/itemid.h"
  59 #include "storage/lwlock.h"
  60 #include "storage/shmem.h"
  61
  62
  63 /*
  64  * Shared free-space-map objects
  65  *
  66  * Note: we handle pointers to these items as pointers, not as SHMEM_OFFSETs.
  67  * This assumes that all processes accessing the map will have the shared
  68  * memory segment mapped at the same place in their address space.
  69  */
  70 typedef struct FSMHeader FSMHeader;
  71 typedef struct FSMRelation FSMRelation;
  72 typedef struct FSMChunk FSMChunk;
  73
  74 /* Header for whole map */
  75 struct FSMHeader
  76 {
  77         HTAB       *relHash;            /* hashtable of FSMRelation entries */
  78         FSMRelation *relList;           /* FSMRelations in useCount order */
  79         FSMRelation *relListTail;       /* tail of FSMRelation list */
  80         int                     numRels;                /* number of FSMRelations now in use */
  81         FSMChunk   *freeChunks;         /* linked list of currently-free chunks */
  82         int                     numFreeChunks;  /* number of free chunks */
  83 };
  84
  85 /*
  86  * Per-relation struct --- this is an entry in the shared hash table.
  87  * The hash key is the RelFileNode value (hence, we look at the physical
  88  * relation ID, not the logical ID, which is appropriate).
  89  */
  90 struct FSMRelation
  91 {
  92         RelFileNode key;                        /* hash key (must be first) */
  93         FSMRelation *nextRel;           /* next rel in useCount order */
  94         FSMRelation *priorRel;          /* prior rel in useCount order */
  95         int                     useCount;               /* use count for prioritizing rels */
  96         Size            threshold;              /* minimum amount of free space to keep */
  97         int                     nextPage;               /* index (from 0) to start next search at */
  98         int                     numPages;               /* total number of pages we have info
  99                                                                  * about */
 100         int                     numChunks;              /* number of FSMChunks allocated to rel */
 101         FSMChunk   *relChunks;          /* linked list of page info chunks */
 102 };
 103
 104 /*
 105  * Info about individual pages in a relation is stored in chunks to reduce
 106  * allocation overhead.  Note that we allow any chunk of a relation's list
 107  * to be partly full, not only the last chunk; this speeds deletion of
 108  * individual page entries.  When the total number of unused slots reaches
 109  * CHUNKPAGES, we compact out the unused slots so that we can return a chunk
 110  * to the freelist; but there's no point in doing the compaction before that.
 111  */
 112
 113 #define CHUNKPAGES      32                      /* each chunk can store this many pages */
 114
 115 struct FSMChunk
 116 {
 117         FSMChunk   *next;                       /* linked-list link */
 118         int                     numPages;               /* number of pages described here */
 119         BlockNumber pages[CHUNKPAGES];          /* page numbers within relation */
 120         ItemLength      bytes[CHUNKPAGES];              /* free space available on each
 121                                                                                  * page */
 122 };
 123
 124
 125 int                     MaxFSMRelations;        /* these are set by guc.c */
 126 int                     MaxFSMPages;
 127
 128 static FSMHeader *FreeSpaceMap; /* points to FSMHeader in shared memory */
 129
 130
 131 static FSMRelation *lookup_fsm_rel(RelFileNode *rel);
 132 static FSMRelation *create_fsm_rel(RelFileNode *rel);
 133 static void delete_fsm_rel(FSMRelation *fsmrel);
 134 static void link_fsm_rel_after(FSMRelation *fsmrel, FSMRelation *oldrel);
 135 static void unlink_fsm_rel(FSMRelation *fsmrel);
 136 static void free_chunk_chain(FSMChunk *fchunk);
 137 static BlockNumber find_free_space(FSMRelation *fsmrel, Size spaceNeeded);
 138 static void fsm_record_free_space(FSMRelation *fsmrel, BlockNumber page,
 139                                           Size spaceAvail);
 140 static bool lookup_fsm_page_entry(FSMRelation *fsmrel, BlockNumber page,
 141                                           FSMChunk **outChunk, int *outChunkRelIndex);
 142 static bool insert_fsm_page_entry(FSMRelation *fsmrel,
 143                                           BlockNumber page, Size spaceAvail,
 144                                           FSMChunk *chunk, int chunkRelIndex);
 145 static bool push_fsm_page_entry(BlockNumber page, Size spaceAvail,
 146                                         FSMChunk *chunk, int chunkRelIndex);
 147 static void delete_fsm_page_entry(FSMRelation *fsmrel, FSMChunk *chunk,
 148                                           int chunkRelIndex);
 149 static void compact_fsm_page_list(FSMRelation *fsmrel);
 150 static void acquire_fsm_free_space(void);
 151
 152
 153 /*
 154  * Exported routines
 155  */
 156
 157
 158 /*
 159  * InitFreeSpaceMap -- Initialize the freespace module.
 160  *
 161  * This must be called once during shared memory initialization.
 162  * It builds the empty free space map table.  FreeSpaceLock must also be
 163  * initialized at some point, but is not touched here --- we assume there is
 164  * no need for locking, since only the calling process can be accessing shared
 165  * memory as yet.
 166  */
 167 void
 168 InitFreeSpaceMap(void)
 169 {
 170         HASHCTL         info;
 171         FSMChunk   *chunks,
 172                            *prevchunk;
 173         int                     nchunks;
 174
 175         /* Create table header */
 176         FreeSpaceMap = (FSMHeader *) ShmemAlloc(sizeof(FSMHeader));
 177         if (FreeSpaceMap == NULL)
 178                 elog(FATAL, "Insufficient shared memory for free space map");
 179         MemSet(FreeSpaceMap, 0, sizeof(FSMHeader));
 180
 181         /* Create hashtable for FSMRelations */
 182         info.keysize = sizeof(RelFileNode);
 183         info.entrysize = sizeof(FSMRelation);
 184         info.hash = tag_hash;
 185
 186         FreeSpaceMap->relHash = ShmemInitHash("Free Space Map Hash",
 187                                                                                   MaxFSMRelations / 10,
 188                                                                                   MaxFSMRelations,
 189                                                                                   &info,
 190                                                                                   (HASH_ELEM | HASH_FUNCTION));
 191
 192         if (!FreeSpaceMap->relHash)
 193                 elog(FATAL, "Insufficient shared memory for free space map");
 194
 195         /* Allocate FSMChunks and fill up the free-chunks list */
 196         nchunks = (MaxFSMPages - 1) / CHUNKPAGES + 1;
 197         FreeSpaceMap->numFreeChunks = nchunks;
 198
 199         chunks = (FSMChunk *) ShmemAlloc(nchunks * sizeof(FSMChunk));
 200         if (chunks == NULL)
 201                 elog(FATAL, "Insufficient shared memory for free space map");
 202
 203         prevchunk = NULL;
 204         while (nchunks-- > 0)
 205         {
 206                 chunks->next = prevchunk;
 207                 prevchunk = chunks;
 208                 chunks++;
 209         }
 210         FreeSpaceMap->freeChunks = prevchunk;
 211 }
 212
 213 /*
 214  * Estimate amount of shmem space needed for FSM.
 215  */
 216 int
 217 FreeSpaceShmemSize(void)
 218 {
 219         int                     size;
 220         int                     nchunks;
 221
 222         /* table header */
 223         size = MAXALIGN(sizeof(FSMHeader));
 224
 225         /* hash table, including the FSMRelation objects */
 226         size += hash_estimate_size(MaxFSMRelations, sizeof(FSMRelation));
 227
 228         /* FSMChunk objects */
 229         nchunks = (MaxFSMPages - 1) / CHUNKPAGES + 1;
 230
 231         size += MAXALIGN(nchunks * sizeof(FSMChunk));
 232
 233         return size;
 234 }
 235
 236 /*
 237  * GetPageWithFreeSpace - try to find a page in the given relation with
 238  *              at least the specified amount of free space.
 239  *
 240  * If successful, return the block number; if not, return InvalidBlockNumber.
 241  *
 242  * The caller must be prepared for the possibility that the returned page
 243  * will turn out to have too little space available by the time the caller
 244  * gets a lock on it.  In that case, the caller should report the actual
 245  * amount of free space available on that page (via RecordFreeSpace) and
 246  * then try again.      If InvalidBlockNumber is returned, extend the relation.
 247  */
 248 BlockNumber
 249 GetPageWithFreeSpace(RelFileNode *rel, Size spaceNeeded)
 250 {
 251         FSMRelation *fsmrel;
 252         BlockNumber freepage;
 253
 254         LWLockAcquire(FreeSpaceLock, LW_EXCLUSIVE);
 255
 256         /*
 257          * We always add a rel to the hashtable when it is inquired about.
 258          */
 259         fsmrel = create_fsm_rel(rel);
 260
 261         /*
 262          * Adjust the threshold towards the space request.      This essentially
 263          * implements an exponential moving average with an equivalent period
 264          * of about 63 requests.  Ignore silly requests, however, to ensure
 265          * that the average stays in bounds.
 266          *
 267          * In theory, if the threshold increases here we should immediately
 268          * delete any pages that fall below the new threshold.  In practice it
 269          * seems OK to wait until we have a need to compact space.
 270          */
 271         if (spaceNeeded > 0 && spaceNeeded < BLCKSZ)
 272         {
 273                 int                     cur_avg = (int) fsmrel->threshold;
 274
 275                 cur_avg += ((int) spaceNeeded - cur_avg) / 32;
 276                 fsmrel->threshold = (Size) cur_avg;
 277         }
 278         freepage = find_free_space(fsmrel, spaceNeeded);
 279         LWLockRelease(FreeSpaceLock);
 280         return freepage;
 281 }
 282
 283 /*
 284  * RecordFreeSpace - record the amount of free space available on a page.
 285  *
 286  * The FSM is at liberty to forget about the page instead, if the amount of
 287  * free space is too small to be interesting.  The only guarantee is that
 288  * a subsequent request to get a page with more than spaceAvail space free
 289  * will not return this page.
 290  */
 291 void
 292 RecordFreeSpace(RelFileNode *rel, BlockNumber page, Size spaceAvail)
 293 {
 294         FSMRelation *fsmrel;
 295
 296         /* Sanity check: ensure spaceAvail will fit into ItemLength */
 297         AssertArg(spaceAvail < BLCKSZ);
 298
 299         LWLockAcquire(FreeSpaceLock, LW_EXCLUSIVE);
 300
 301         /*
 302          * We choose not to add rels to the hashtable unless they've been
 303          * inquired about with GetPageWithFreeSpace.  Also, a Record operation
 304          * does not increase the useCount or change threshold, only Get does.
 305          */
 306         fsmrel = lookup_fsm_rel(rel);
 307         if (fsmrel)
 308                 fsm_record_free_space(fsmrel, page, spaceAvail);
 309         LWLockRelease(FreeSpaceLock);
 310 }
 311
 312 /*
 313  * RecordAndGetPageWithFreeSpace - combo form to save one lock and
 314  *              hash table lookup cycle.
 315  */
 316 BlockNumber
 317 RecordAndGetPageWithFreeSpace(RelFileNode *rel,
 318                                                           BlockNumber oldPage,
 319                                                           Size oldSpaceAvail,
 320                                                           Size spaceNeeded)
 321 {
 322         FSMRelation *fsmrel;
 323         BlockNumber freepage;
 324
 325         /* Sanity check: ensure spaceAvail will fit into ItemLength */
 326         AssertArg(oldSpaceAvail < BLCKSZ);
 327
 328         LWLockAcquire(FreeSpaceLock, LW_EXCLUSIVE);
 329
 330         /*
 331          * We always add a rel to the hashtable when it is inquired about.
 332          */
 333         fsmrel = create_fsm_rel(rel);
 334
 335         /*
 336          * Adjust the threshold towards the space request, same as in
 337          * GetPageWithFreeSpace.
 338          *
 339          * Note that we do this before storing data for oldPage, which means this
 340          * isn't exactly equivalent to Record followed by Get; but it seems
 341          * appropriate to adjust the threshold first.
 342          */
 343         if (spaceNeeded > 0 && spaceNeeded < BLCKSZ)
 344         {
 345                 int                     cur_avg = (int) fsmrel->threshold;
 346
 347                 cur_avg += ((int) spaceNeeded - cur_avg) / 32;
 348                 fsmrel->threshold = (Size) cur_avg;
 349         }
 350         /* Do the Record */
 351         fsm_record_free_space(fsmrel, oldPage, oldSpaceAvail);
 352         /* Do the Get */
 353         freepage = find_free_space(fsmrel, spaceNeeded);
 354         LWLockRelease(FreeSpaceLock);
 355         return freepage;
 356 }
 357
 358 /*
 359  * MultiRecordFreeSpace - record available-space info about multiple pages
 360  *              of a relation in one call.
 361  *
 362  * First, if minPage <= maxPage, the FSM must discard any entries it has for
 363  * pages in that page number range (inclusive).  This allows obsolete info
 364  * to be discarded.  Second, if nPages > 0, record the page numbers and free
 365  * space amounts in the given arrays.  As with RecordFreeSpace, the FSM is at
 366  * liberty to discard some of the information.  However, it *must* discard
 367  * previously stored info in the minPage..maxPage range (for example, this
 368  * case is used to remove info about deleted pages during relation truncation).
 369  */
 370 void
 371 MultiRecordFreeSpace(RelFileNode *rel,
 372                                          BlockNumber minPage,
 373                                          BlockNumber maxPage,
 374                                          int nPages,
 375                                          BlockNumber *pages,
 376                                          Size *spaceAvail)
 377 {
 378         FSMRelation *fsmrel;
 379         int                     i;
 380
 381         LWLockAcquire(FreeSpaceLock, LW_EXCLUSIVE);
 382         fsmrel = lookup_fsm_rel(rel);
 383         if (fsmrel)
 384         {
 385                 /*
 386                  * Remove entries in specified range
 387                  */
 388                 if (minPage <= maxPage)
 389                 {
 390                         FSMChunk   *chunk;
 391                         int                     chunkRelIndex;
 392                         bool            done;
 393
 394                         /* Use lookup to locate first entry >= minPage */
 395                         lookup_fsm_page_entry(fsmrel, minPage, &chunk, &chunkRelIndex);
 396                         /* Set free space to 0 for each page within range */
 397                         done = false;
 398                         while (chunk && !done)
 399                         {
 400                                 int                     numPages = chunk->numPages;
 401
 402                                 for (; chunkRelIndex < numPages; chunkRelIndex++)
 403                                 {
 404                                         if (chunk->pages[chunkRelIndex] > maxPage)
 405                                         {
 406                                                 done = true;
 407                                                 break;
 408                                         }
 409                                         chunk->bytes[chunkRelIndex] = 0;
 410                                 }
 411                                 chunk = chunk->next;
 412                                 chunkRelIndex = 0;
 413                         }
 414                         /* Now compact out the zeroed entries */
 415                         compact_fsm_page_list(fsmrel);
 416                 }
 417
 418                 /*
 419                  * Add new entries, if appropriate.
 420                  *
 421                  * XXX we could probably be smarter about this than doing it
 422                  * completely separately for each one.  FIXME later.
 423                  *
 424                  * One thing we can do is short-circuit the process entirely if a
 425                  * page (a) has too little free space to be recorded, and (b) is
 426                  * within the minPage..maxPage range --- then we deleted any old
 427                  * entry above, and we aren't going to make a new one. This is
 428                  * particularly useful since in most cases, all the passed pages
 429                  * will in fact be in the minPage..maxPage range.
 430                  */
 431                 for (i = 0; i < nPages; i++)
 432                 {
 433                         BlockNumber page = pages[i];
 434                         Size            avail = spaceAvail[i];
 435
 436                         if (avail >= fsmrel->threshold ||
 437                                 page < minPage || page > maxPage)
 438                                 fsm_record_free_space(fsmrel, page, avail);
 439                 }
 440         }
 441         LWLockRelease(FreeSpaceLock);
 442 }
 443
 444 /*
 445  * FreeSpaceMapForgetRel - forget all about a relation.
 446  *
 447  * This is called when a relation is deleted.  Although we could just let
 448  * the rel age out of the map, it's better to reclaim and reuse the space
 449  * sooner.
 450  */
 451 void
 452 FreeSpaceMapForgetRel(RelFileNode *rel)
 453 {
 454         FSMRelation *fsmrel;
 455
 456         LWLockAcquire(FreeSpaceLock, LW_EXCLUSIVE);
 457         fsmrel = lookup_fsm_rel(rel);
 458         if (fsmrel)
 459                 delete_fsm_rel(fsmrel);
 460         LWLockRelease(FreeSpaceLock);
 461 }
 462
 463 /*
 464  * FreeSpaceMapForgetDatabase - forget all relations of a database.
 465  *
 466  * This is called during DROP DATABASE.  As above, might as well reclaim
 467  * map space sooner instead of later.
 468  *
 469  * XXX when we implement tablespaces, target Oid will need to be tablespace
 470  * ID not database ID.
 471  */
 472 void
 473 FreeSpaceMapForgetDatabase(Oid dbid)
 474 {
 475         FSMRelation *fsmrel,
 476                            *nextrel;
 477
 478         LWLockAcquire(FreeSpaceLock, LW_EXCLUSIVE);
 479         for (fsmrel = FreeSpaceMap->relList; fsmrel; fsmrel = nextrel)
 480         {
 481                 nextrel = fsmrel->nextRel;              /* in case we delete it */
 482                 if (fsmrel->key.tblNode == dbid)
 483                         delete_fsm_rel(fsmrel);
 484         }
 485         LWLockRelease(FreeSpaceLock);
 486 }
 487
 488
 489 /*
 490  * Internal routines.  These all assume the caller holds the FreeSpaceLock.
 491  */
 492
 493 /*
 494  * Lookup a relation in the hash table.  If not present, return NULL.
 495  * The relation's useCount is not changed.
 496  */
 497 static FSMRelation *
 498 lookup_fsm_rel(RelFileNode *rel)
 499 {
 500         FSMRelation *fsmrel;
 501
 502         fsmrel = (FSMRelation *) hash_search(FreeSpaceMap->relHash,
 503                                                                                  (void *) rel,
 504                                                                                  HASH_FIND,
 505                                                                                  NULL);
 506         if (!fsmrel)
 507                 return NULL;
 508
 509         return fsmrel;
 510 }
 511
 512 /*
 513  * Lookup a relation in the hash table, creating an entry if not present.
 514  *
 515  * On successful lookup, the relation's useCount is incremented, possibly
 516  * causing it to move up in the priority list.
 517  */
 518 static FSMRelation *
 519 create_fsm_rel(RelFileNode *rel)
 520 {
 521         FSMRelation *fsmrel,
 522                            *oldrel;
 523         bool            found;
 524
 525         fsmrel = (FSMRelation *) hash_search(FreeSpaceMap->relHash,
 526                                                                                  (void *) rel,
 527                                                                                  HASH_ENTER,
 528                                                                                  &found);
 529         if (!fsmrel)
 530                 elog(ERROR, "FreeSpaceMap hashtable out of memory");
 531
 532         if (!found)
 533         {
 534                 /* New hashtable entry, initialize it (hash_search set the key) */
 535                 fsmrel->useCount = 1;
 536                 fsmrel->threshold = BLCKSZ / 2; /* starting point for new entry */
 537                 fsmrel->nextPage = 0;
 538                 fsmrel->numPages = 0;
 539                 fsmrel->numChunks = 0;
 540                 fsmrel->relChunks = NULL;
 541                 /* Discard lowest-priority existing rel, if we are over limit */
 542                 if (FreeSpaceMap->numRels >= MaxFSMRelations)
 543                         delete_fsm_rel(FreeSpaceMap->relListTail);
 544
 545                 /*
 546                  * Add new entry in front of any others with useCount 1 (since it
 547                  * is more recently used than them).
 548                  */
 549                 oldrel = FreeSpaceMap->relListTail;
 550                 while (oldrel && oldrel->useCount <= 1)
 551                         oldrel = oldrel->priorRel;
 552                 link_fsm_rel_after(fsmrel, oldrel);
 553                 FreeSpaceMap->numRels++;
 554         }
 555         else
 556         {
 557                 int                     myCount;
 558
 559                 /* Existing entry, advance its useCount */
 560                 if (++(fsmrel->useCount) >= INT_MAX / 2)
 561                 {
 562                         /* When useCounts threaten to overflow, reduce 'em all 2X */
 563                         for (oldrel = FreeSpaceMap->relList;
 564                                  oldrel != NULL;
 565                                  oldrel = oldrel->nextRel)
 566                                 oldrel->useCount >>= 1;
 567                 }
 568                 /* If warranted, move it up the priority list */
 569                 oldrel = fsmrel->priorRel;
 570                 myCount = fsmrel->useCount;
 571                 if (oldrel && oldrel->useCount <= myCount)
 572                 {
 573                         unlink_fsm_rel(fsmrel);
 574                         while (oldrel && oldrel->useCount <= myCount)
 575                                 oldrel = oldrel->priorRel;
 576                         link_fsm_rel_after(fsmrel, oldrel);
 577                 }
 578         }
 579
 580         return fsmrel;
 581 }
 582
 583 /*
 584  * Remove an existing FSMRelation entry.
 585  */
 586 static void
 587 delete_fsm_rel(FSMRelation *fsmrel)
 588 {
 589         FSMRelation *result;
 590
 591         free_chunk_chain(fsmrel->relChunks);
 592         unlink_fsm_rel(fsmrel);
 593         FreeSpaceMap->numRels--;
 594         result = (FSMRelation *) hash_search(FreeSpaceMap->relHash,
 595                                                                                  (void *) &(fsmrel->key),
 596                                                                                  HASH_REMOVE,
 597                                                                                  NULL);
 598         if (!result)
 599                 elog(ERROR, "FreeSpaceMap hashtable corrupted");
 600 }
 601
 602 /*
 603  * Link a FSMRelation into the priority list just after the given existing
 604  * entry (or at the head of the list, if oldrel is NULL).
 605  */
 606 static void
 607 link_fsm_rel_after(FSMRelation *fsmrel, FSMRelation *oldrel)
 608 {
 609         if (oldrel == NULL)
 610         {
 611                 /* insert at head */
 612                 fsmrel->priorRel = NULL;
 613                 fsmrel->nextRel = FreeSpaceMap->relList;
 614                 FreeSpaceMap->relList = fsmrel;
 615                 if (fsmrel->nextRel != NULL)
 616                         fsmrel->nextRel->priorRel = fsmrel;
 617                 else
 618                         FreeSpaceMap->relListTail = fsmrel;
 619         }
 620         else
 621         {
 622                 /* insert after oldrel */
 623                 fsmrel->priorRel = oldrel;
 624                 fsmrel->nextRel = oldrel->nextRel;
 625                 oldrel->nextRel = fsmrel;
 626                 if (fsmrel->nextRel != NULL)
 627                         fsmrel->nextRel->priorRel = fsmrel;
 628                 else
 629                         FreeSpaceMap->relListTail = fsmrel;
 630         }
 631 }
 632
 633 /*
 634  * Delink a FSMRelation from the priority list.
 635  */
 636 static void
 637 unlink_fsm_rel(FSMRelation *fsmrel)
 638 {
 639         if (fsmrel->priorRel != NULL)
 640                 fsmrel->priorRel->nextRel = fsmrel->nextRel;
 641         else
 642                 FreeSpaceMap->relList = fsmrel->nextRel;
 643         if (fsmrel->nextRel != NULL)
 644                 fsmrel->nextRel->priorRel = fsmrel->priorRel;
 645         else
 646                 FreeSpaceMap->relListTail = fsmrel->priorRel;
 647 }
 648
 649 /*
 650  * Return all the FSMChunks in the chain starting at fchunk to the freelist.
 651  * (Caller must handle unlinking them from wherever they were.)
 652  */
 653 static void
 654 free_chunk_chain(FSMChunk *fchunk)
 655 {
 656         int                     nchunks;
 657         FSMChunk   *lchunk;
 658
 659         if (fchunk == NULL)
 660                 return;
 661         nchunks = 1;
 662         lchunk = fchunk;
 663         while (lchunk->next != NULL)
 664         {
 665                 nchunks++;
 666                 lchunk = lchunk->next;
 667         }
 668         lchunk->next = FreeSpaceMap->freeChunks;
 669         FreeSpaceMap->freeChunks = fchunk;
 670         FreeSpaceMap->numFreeChunks += nchunks;
 671 }
 672
 673 /*
 674  * Look to see if a page with at least the specified amount of space is
 675  * available in the given FSMRelation.  If so, return its page number,
 676  * and advance the nextPage counter so that the next inquiry will return
 677  * a different page if possible.  Return InvalidBlockNumber if no success.
 678  */
 679 static BlockNumber
 680 find_free_space(FSMRelation *fsmrel, Size spaceNeeded)
 681 {
 682         int                     pagesToCheck,   /* outer loop counter */
 683                                 pageIndex,              /* current page index relative to relation */
 684                                 chunkRelIndex;  /* current page index relative to curChunk */
 685         FSMChunk   *curChunk;
 686
 687         pageIndex = fsmrel->nextPage;
 688         /* Last operation may have left nextPage pointing past end */
 689         if (pageIndex >= fsmrel->numPages)
 690                 pageIndex = 0;
 691         curChunk = fsmrel->relChunks;
 692         chunkRelIndex = pageIndex;
 693
 694         for (pagesToCheck = fsmrel->numPages; pagesToCheck > 0; pagesToCheck--)
 695         {
 696                 /*
 697                  * Make sure we are in the right chunk.  First time through, we
 698                  * may have to advance through multiple chunks; subsequent loops
 699                  * should do this at most once.
 700                  */
 701                 while (chunkRelIndex >= curChunk->numPages)
 702                 {
 703                         chunkRelIndex -= curChunk->numPages;
 704                         curChunk = curChunk->next;
 705                 }
 706                 /* Check the next page */
 707                 if ((Size) curChunk->bytes[chunkRelIndex] >= spaceNeeded)
 708                 {
 709                         fsmrel->nextPage = pageIndex + 1;
 710                         return curChunk->pages[chunkRelIndex];
 711                 }
 712                 /* Advance pageIndex and chunkRelIndex, wrapping around if needed */
 713                 if (++pageIndex >= fsmrel->numPages)
 714                 {
 715                         pageIndex = 0;
 716                         curChunk = fsmrel->relChunks;
 717                         chunkRelIndex = 0;
 718                 }
 719                 else
 720                         chunkRelIndex++;
 721         }
 722
 723         return InvalidBlockNumber;      /* nothing found */
 724 }
 725
 726 /*
 727  * fsm_record_free_space - guts of RecordFreeSpace, which is also used by
 728  * RecordAndGetPageWithFreeSpace.
 729  */
 730 static void
 731 fsm_record_free_space(FSMRelation *fsmrel, BlockNumber page, Size spaceAvail)
 732 {
 733         FSMChunk   *chunk;
 734         int                     chunkRelIndex;
 735
 736         if (lookup_fsm_page_entry(fsmrel, page, &chunk, &chunkRelIndex))
 737         {
 738                 /* Found an existing entry for page; update or delete it */
 739                 if (spaceAvail >= fsmrel->threshold)
 740                         chunk->bytes[chunkRelIndex] = (ItemLength) spaceAvail;
 741                 else
 742                         delete_fsm_page_entry(fsmrel, chunk, chunkRelIndex);
 743         }
 744         else
 745         {
 746                 /*
 747                  * No existing entry; add one if spaceAvail exceeds threshold.
 748                  *
 749                  * CORNER CASE: if we have to do acquire_fsm_free_space then our own
 750                  * threshold will increase, possibly meaning that we shouldn't
 751                  * store the page after all.  Loop to redo the test if that
 752                  * happens.  The loop also covers the possibility that
 753                  * acquire_fsm_free_space must be executed more than once to free
 754                  * any space (ie, thresholds must be more than doubled).
 755                  */
 756                 while (spaceAvail >= fsmrel->threshold)
 757                 {
 758                         if (insert_fsm_page_entry(fsmrel, page, spaceAvail,
 759                                                                           chunk, chunkRelIndex))
 760                                 break;
 761                         /* No space, acquire some and recheck threshold */
 762                         acquire_fsm_free_space();
 763                         if (spaceAvail < fsmrel->threshold)
 764                                 break;
 765
 766                         /*
 767                          * Need to redo the lookup since our own page list may well
 768                          * have lost entries, so position is not correct anymore.
 769                          */
 770                         if (lookup_fsm_page_entry(fsmrel, page,
 771                                                                           &chunk, &chunkRelIndex))
 772                                 elog(ERROR, "fsm_record_free_space: unexpected match");
 773                 }
 774         }
 775 }
 776
 777 /*
 778  * Look for an entry for a specific page (block number) in a FSMRelation.
 779  * Returns TRUE if a matching entry exists, else FALSE.
 780  *
 781  * The output arguments *outChunk, *outChunkRelIndex are set to indicate where
 782  * the entry exists (if TRUE result) or could be inserted (if FALSE result).
 783  * *chunk is set to NULL if there is no place to insert, ie, the entry would
 784  * need to be added to a new chunk.
 785  */
 786 static bool
 787 lookup_fsm_page_entry(FSMRelation *fsmrel, BlockNumber page,
 788                                           FSMChunk **outChunk, int *outChunkRelIndex)
 789 {
 790         FSMChunk   *chunk;
 791         int                     chunkRelIndex;
 792
 793         for (chunk = fsmrel->relChunks; chunk; chunk = chunk->next)
 794         {
 795                 int                     numPages = chunk->numPages;
 796
 797                 /* Can skip the chunk quickly if page must be after last in chunk */
 798                 if (numPages > 0 && page <= chunk->pages[numPages - 1])
 799                 {
 800                         for (chunkRelIndex = 0; chunkRelIndex < numPages; chunkRelIndex++)
 801                         {
 802                                 if (page <= chunk->pages[chunkRelIndex])
 803                                 {
 804                                         *outChunk = chunk;
 805                                         *outChunkRelIndex = chunkRelIndex;
 806                                         return (page == chunk->pages[chunkRelIndex]);
 807                                 }
 808                         }
 809                         /* Should not get here, given above test */
 810                         Assert(false);
 811                 }
 812
 813                 /*
 814                  * If we are about to fall off the end, and there's space
 815                  * available in the end chunk, return a pointer to it.
 816                  */
 817                 if (chunk->next == NULL && numPages < CHUNKPAGES)
 818                 {
 819                         *outChunk = chunk;
 820                         *outChunkRelIndex = numPages;
 821                         return false;
 822                 }
 823         }
 824
 825         /*
 826          * Adding the page would require a new chunk (or, perhaps, compaction
 827          * of available free space --- not my problem here).
 828          */
 829         *outChunk = NULL;
 830         *outChunkRelIndex = 0;
 831         return false;
 832 }
 833
 834 /*
 835  * Insert a new page entry into a FSMRelation's list at given position
 836  * (chunk == NULL implies at end).
 837  *
 838  * If there is no space available to insert the entry, return FALSE.
 839  */
 840 static bool
 841 insert_fsm_page_entry(FSMRelation *fsmrel, BlockNumber page, Size spaceAvail,
 842                                           FSMChunk *chunk, int chunkRelIndex)
 843 {
 844         /* Outer loop handles retry after compacting rel's page list */
 845         for (;;)
 846         {
 847                 if (fsmrel->numPages >= fsmrel->numChunks * CHUNKPAGES)
 848                 {
 849                         /* No free space within chunk list, so need another chunk */
 850                         FSMChunk   *newChunk;
 851
 852                         if ((newChunk = FreeSpaceMap->freeChunks) == NULL)
 853                                 return false;           /* can't do it */
 854                         FreeSpaceMap->freeChunks = newChunk->next;
 855                         FreeSpaceMap->numFreeChunks--;
 856                         newChunk->next = NULL;
 857                         newChunk->numPages = 0;
 858                         if (fsmrel->relChunks == NULL)
 859                                 fsmrel->relChunks = newChunk;
 860                         else
 861                         {
 862                                 FSMChunk   *priorChunk = fsmrel->relChunks;
 863
 864                                 while (priorChunk->next != NULL)
 865                                         priorChunk = priorChunk->next;
 866                                 priorChunk->next = newChunk;
 867                         }
 868                         fsmrel->numChunks++;
 869                         if (chunk == NULL)
 870                         {
 871                                 /* Original search found that new page belongs at end */
 872                                 chunk = newChunk;
 873                                 chunkRelIndex = 0;
 874                         }
 875                 }
 876
 877                 /* Try to insert it the easy way, ie, just move down subsequent data */
 878                 if (chunk &&
 879                         push_fsm_page_entry(page, spaceAvail, chunk, chunkRelIndex))
 880                 {
 881                         fsmrel->numPages++;
 882                         fsmrel->nextPage++;             /* don't return same page twice running */
 883                         return true;
 884                 }
 885
 886                 /*
 887                  * There is space available, but evidently it's before the place where
 888                  * the page entry needs to go.  Compact the list and try again. This
 889                  * will require us to redo the search for the appropriate place.
 890                  * Furthermore, compact_fsm_page_list deletes empty end chunks, so
 891                  * we may need to repeat the action of grabbing a new end chunk.
 892                  */
 893                 compact_fsm_page_list(fsmrel);
 894                 if (lookup_fsm_page_entry(fsmrel, page, &chunk, &chunkRelIndex))
 895                         elog(ERROR, "insert_fsm_page_entry: entry already exists!");
 896         }
 897 }
 898
 899 /*
 900  * Auxiliary routine for insert_fsm_page_entry: try to push entries to the
 901  * right to insert at chunk/chunkRelIndex.      Return TRUE if successful.
 902  * Note that the FSMRelation's own fields are not updated.
 903  */
 904 static bool
 905 push_fsm_page_entry(BlockNumber page, Size spaceAvail,
 906                                         FSMChunk *chunk, int chunkRelIndex)
 907 {
 908         int                     i;
 909
 910         if (chunk->numPages >= CHUNKPAGES)
 911         {
 912                 if (chunk->next == NULL)
 913                         return false;           /* no space */
 914                 /* try to push chunk's last item to next chunk */
 915                 if (!push_fsm_page_entry(chunk->pages[CHUNKPAGES - 1],
 916                                                                  chunk->bytes[CHUNKPAGES - 1],
 917                                                                  chunk->next, 0))
 918                         return false;
 919                 /* successfully pushed it */
 920                 chunk->numPages--;
 921         }
 922         for (i = chunk->numPages; i > chunkRelIndex; i--)
 923         {
 924                 chunk->pages[i] = chunk->pages[i - 1];
 925                 chunk->bytes[i] = chunk->bytes[i - 1];
 926         }
 927         chunk->numPages++;
 928         chunk->pages[chunkRelIndex] = page;
 929         chunk->bytes[chunkRelIndex] = (ItemLength) spaceAvail;
 930         return true;
 931 }
 932
 933 /*
 934  * Delete one page entry from a FSMRelation's list.  Compact free space
 935  * in the list, but only if a chunk can be returned to the freelist.
 936  */
 937 static void
 938 delete_fsm_page_entry(FSMRelation *fsmrel, FSMChunk *chunk, int chunkRelIndex)
 939 {
 940         int                     i,
 941                                 lim;
 942
 943         Assert(chunk && chunkRelIndex >= 0 && chunkRelIndex < chunk->numPages);
 944         /* Compact out space in this chunk */
 945         lim = --chunk->numPages;
 946         for (i = chunkRelIndex; i < lim; i++)
 947         {
 948                 chunk->pages[i] = chunk->pages[i + 1];
 949                 chunk->bytes[i] = chunk->bytes[i + 1];
 950         }
 951         /* Compact the whole list if a chunk can be freed */
 952         fsmrel->numPages--;
 953         if (fsmrel->numPages <= (fsmrel->numChunks - 1) * CHUNKPAGES)
 954                 compact_fsm_page_list(fsmrel);
 955 }
 956
 957 /*
 958  * Remove any pages with free space less than the current threshold for the
 959  * FSMRelation, compact out free slots in non-last chunks, and return any
 960  * completely freed chunks to the freelist.
 961  */
 962 static void
 963 compact_fsm_page_list(FSMRelation *fsmrel)
 964 {
 965         Size            threshold = fsmrel->threshold;
 966         FSMChunk   *srcChunk,
 967                            *dstChunk;
 968         int                     srcIndex,
 969                                 dstIndex,
 970                                 dstPages,
 971                                 dstChunkCnt;
 972
 973         srcChunk = dstChunk = fsmrel->relChunks;
 974         srcIndex = dstIndex = 0;
 975         dstPages = 0;                           /* total pages kept */
 976         dstChunkCnt = 1;                        /* includes current dstChunk */
 977
 978         while (srcChunk != NULL)
 979         {
 980                 int                     srcPages = srcChunk->numPages;
 981
 982                 while (srcIndex < srcPages)
 983                 {
 984                         if ((Size) srcChunk->bytes[srcIndex] >= threshold)
 985                         {
 986                                 if (dstIndex >= CHUNKPAGES)
 987                                 {
 988                                         /*
 989                                          * At this point srcChunk must be pointing to a later
 990                                          * chunk, so it's OK to overwrite dstChunk->numPages.
 991                                          */
 992                                         dstChunk->numPages = dstIndex;
 993                                         dstChunk = dstChunk->next;
 994                                         dstChunkCnt++;
 995                                         dstIndex = 0;
 996                                 }
 997                                 dstChunk->pages[dstIndex] = srcChunk->pages[srcIndex];
 998                                 dstChunk->bytes[dstIndex] = srcChunk->bytes[srcIndex];
 999                                 dstIndex++;
1000                                 dstPages++;
1001                         }
1002                         srcIndex++;
1003                 }
1004                 srcChunk = srcChunk->next;
1005                 srcIndex = 0;
1006         }
1007
1008         if (dstPages == 0)
1009         {
1010                 /* No chunks to be kept at all */
1011                 fsmrel->nextPage = 0;
1012                 fsmrel->numPages = 0;
1013                 fsmrel->numChunks = 0;
1014                 fsmrel->relChunks = NULL;
1015                 free_chunk_chain(dstChunk);
1016         }
1017         else
1018         {
1019                 /* we deliberately don't change nextPage here */
1020                 fsmrel->numPages = dstPages;
1021                 fsmrel->numChunks = dstChunkCnt;
1022                 dstChunk->numPages = dstIndex;
1023                 free_chunk_chain(dstChunk->next);
1024                 dstChunk->next = NULL;
1025         }
1026 }
1027
1028 /*
1029  * Acquire some free space by raising the thresholds of all FSMRelations.
1030  *
1031  * Note there is no guarantee as to how much space will be freed by a single
1032  * invocation; caller may repeat if necessary.
1033  */
1034 static void
1035 acquire_fsm_free_space(void)
1036 {
1037         FSMRelation *fsmrel;
1038
1039         for (fsmrel = FreeSpaceMap->relList; fsmrel; fsmrel = fsmrel->nextRel)
1040         {
1041                 fsmrel->threshold *= 2;
1042                 /* Limit thresholds to BLCKSZ so they can't get ridiculously large */
1043                 if (fsmrel->threshold > BLCKSZ)
1044                         fsmrel->threshold = BLCKSZ;
1045                 /* Release any pages that don't meet the new threshold */
1046                 compact_fsm_page_list(fsmrel);
1047         }
1048 }
1049
1050
1051 #ifdef FREESPACE_DEBUG
1052 /*
1053  * Dump contents of freespace map for debugging.
1054  *
1055  * We assume caller holds the FreeSpaceLock, or is otherwise unconcerned
1056  * about other processes.
1057  */
1058 void
1059 DumpFreeSpace(void)
1060 {
1061         FSMRelation *fsmrel;
1062         FSMRelation *prevrel = NULL;
1063         int                     relNum = 0;
1064         FSMChunk   *chunk;
1065         int                     chunkRelIndex;
1066         int                     nChunks;
1067         int                     nPages;
1068
1069         for (fsmrel = FreeSpaceMap->relList; fsmrel; fsmrel = fsmrel->nextRel)
1070         {
1071                 relNum++;
1072                 fprintf(stderr, "Map %d: rel %u/%u useCount %d threshold %u nextPage %d\nMap= ",
1073                                 relNum, fsmrel->key.tblNode, fsmrel->key.relNode,
1074                                 fsmrel->useCount, fsmrel->threshold, fsmrel->nextPage);
1075                 nChunks = nPages = 0;
1076                 for (chunk = fsmrel->relChunks; chunk; chunk = chunk->next)
1077                 {
1078                         int                     numPages = chunk->numPages;
1079
1080                         nChunks++;
1081                         for (chunkRelIndex = 0; chunkRelIndex < numPages; chunkRelIndex++)
1082                         {
1083                                 nPages++;
1084                                 fprintf(stderr, " %u:%u",
1085                                                 chunk->pages[chunkRelIndex],
1086                                                 chunk->bytes[chunkRelIndex]);
1087                         }
1088                 }
1089                 fprintf(stderr, "\n");
1090                 /* Cross-check local counters and list links */
1091                 if (nPages != fsmrel->numPages)
1092                         fprintf(stderr, "DumpFreeSpace: %d pages in rel, but numPages = %d\n",
1093                                         nPages, fsmrel->numPages);
1094                 if (nChunks != fsmrel->numChunks)
1095                         fprintf(stderr, "DumpFreeSpace: %d chunks in rel, but numChunks = %d\n",
1096                                         nChunks, fsmrel->numChunks);
1097                 if (prevrel != fsmrel->priorRel)
1098                         fprintf(stderr, "DumpFreeSpace: broken list links\n");
1099                 prevrel = fsmrel;
1100         }
1101         if (prevrel != FreeSpaceMap->relListTail)
1102                 fprintf(stderr, "DumpFreeSpace: broken list links\n");
1103         /* Cross-check global counters */
1104         if (relNum != FreeSpaceMap->numRels)
1105                 fprintf(stderr, "DumpFreeSpace: %d rels in list, but numRels = %d\n",
1106                                 relNum, FreeSpaceMap->numRels);
1107         nChunks = 0;
1108         for (chunk = FreeSpaceMap->freeChunks; chunk; chunk = chunk->next)
1109                 nChunks++;
1110         if (nChunks != FreeSpaceMap->numFreeChunks)
1111                 fprintf(stderr, "DumpFreeSpace: %d chunks in list, but numFreeChunks = %d\n",
1112                                 nChunks, FreeSpaceMap->numFreeChunks);
1113 }
1114
1115 #endif   /* FREESPACE_DEBUG */