src/backend/storage/freespace/freespace.c

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