Header And Logo

PostgreSQL
| The world's most advanced open source database.

aset.c

Go to the documentation of this file.
00001 /*-------------------------------------------------------------------------
00002  *
00003  * aset.c
00004  *    Allocation set definitions.
00005  *
00006  * AllocSet is our standard implementation of the abstract MemoryContext
00007  * type.
00008  *
00009  *
00010  * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
00011  * Portions Copyright (c) 1994, Regents of the University of California
00012  *
00013  * IDENTIFICATION
00014  *    src/backend/utils/mmgr/aset.c
00015  *
00016  * NOTE:
00017  *  This is a new (Feb. 05, 1999) implementation of the allocation set
00018  *  routines. AllocSet...() does not use OrderedSet...() any more.
00019  *  Instead it manages allocations in a block pool by itself, combining
00020  *  many small allocations in a few bigger blocks. AllocSetFree() normally
00021  *  doesn't free() memory really. It just add's the free'd area to some
00022  *  list for later reuse by AllocSetAlloc(). All memory blocks are free()'d
00023  *  at once on AllocSetReset(), which happens when the memory context gets
00024  *  destroyed.
00025  *              Jan Wieck
00026  *
00027  *  Performance improvement from Tom Lane, 8/99: for extremely large request
00028  *  sizes, we do want to be able to give the memory back to free() as soon
00029  *  as it is pfree()'d.  Otherwise we risk tying up a lot of memory in
00030  *  freelist entries that might never be usable.  This is specially needed
00031  *  when the caller is repeatedly repalloc()'ing a block bigger and bigger;
00032  *  the previous instances of the block were guaranteed to be wasted until
00033  *  AllocSetReset() under the old way.
00034  *
00035  *  Further improvement 12/00: as the code stood, request sizes in the
00036  *  midrange between "small" and "large" were handled very inefficiently,
00037  *  because any sufficiently large free chunk would be used to satisfy a
00038  *  request, even if it was much larger than necessary.  This led to more
00039  *  and more wasted space in allocated chunks over time.  To fix, get rid
00040  *  of the midrange behavior: we now handle only "small" power-of-2-size
00041  *  chunks as chunks.  Anything "large" is passed off to malloc().  Change
00042  *  the number of freelists to change the small/large boundary.
00043  *
00044  *
00045  *  About CLOBBER_FREED_MEMORY:
00046  *
00047  *  If this symbol is defined, all freed memory is overwritten with 0x7F's.
00048  *  This is useful for catching places that reference already-freed memory.
00049  *
00050  *  About MEMORY_CONTEXT_CHECKING:
00051  *
00052  *  Since we usually round request sizes up to the next power of 2, there
00053  *  is often some unused space immediately after a requested data area.
00054  *  Thus, if someone makes the common error of writing past what they've
00055  *  requested, the problem is likely to go unnoticed ... until the day when
00056  *  there *isn't* any wasted space, perhaps because of different memory
00057  *  alignment on a new platform, or some other effect.  To catch this sort
00058  *  of problem, the MEMORY_CONTEXT_CHECKING option stores 0x7E just beyond
00059  *  the requested space whenever the request is less than the actual chunk
00060  *  size, and verifies that the byte is undamaged when the chunk is freed.
00061  *
00062  *-------------------------------------------------------------------------
00063  */
00064 
00065 #include "postgres.h"
00066 
00067 #include "utils/memutils.h"
00068 
00069 /* Define this to detail debug alloc information */
00070 /* #define HAVE_ALLOCINFO */
00071 
00072 /*--------------------
00073  * Chunk freelist k holds chunks of size 1 << (k + ALLOC_MINBITS),
00074  * for k = 0 .. ALLOCSET_NUM_FREELISTS-1.
00075  *
00076  * Note that all chunks in the freelists have power-of-2 sizes.  This
00077  * improves recyclability: we may waste some space, but the wasted space
00078  * should stay pretty constant as requests are made and released.
00079  *
00080  * A request too large for the last freelist is handled by allocating a
00081  * dedicated block from malloc().  The block still has a block header and
00082  * chunk header, but when the chunk is freed we'll return the whole block
00083  * to malloc(), not put it on our freelists.
00084  *
00085  * CAUTION: ALLOC_MINBITS must be large enough so that
00086  * 1<<ALLOC_MINBITS is at least MAXALIGN,
00087  * or we may fail to align the smallest chunks adequately.
00088  * 8-byte alignment is enough on all currently known machines.
00089  *
00090  * With the current parameters, request sizes up to 8K are treated as chunks,
00091  * larger requests go into dedicated blocks.  Change ALLOCSET_NUM_FREELISTS
00092  * to adjust the boundary point.  (But in contexts with small maxBlockSize,
00093  * we may set the allocChunkLimit to less than 8K, so as to avoid space
00094  * wastage.)
00095  *--------------------
00096  */
00097 
00098 #define ALLOC_MINBITS       3   /* smallest chunk size is 8 bytes */
00099 #define ALLOCSET_NUM_FREELISTS  11
00100 #define ALLOC_CHUNK_LIMIT   (1 << (ALLOCSET_NUM_FREELISTS-1+ALLOC_MINBITS))
00101 /* Size of largest chunk that we use a fixed size for */
00102 #define ALLOC_CHUNK_FRACTION    4
00103 /* We allow chunks to be at most 1/4 of maxBlockSize (less overhead) */
00104 
00105 /*--------------------
00106  * The first block allocated for an allocset has size initBlockSize.
00107  * Each time we have to allocate another block, we double the block size
00108  * (if possible, and without exceeding maxBlockSize), so as to reduce
00109  * the bookkeeping load on malloc().
00110  *
00111  * Blocks allocated to hold oversize chunks do not follow this rule, however;
00112  * they are just however big they need to be to hold that single chunk.
00113  *--------------------
00114  */
00115 
00116 #define ALLOC_BLOCKHDRSZ    MAXALIGN(sizeof(AllocBlockData))
00117 #define ALLOC_CHUNKHDRSZ    MAXALIGN(sizeof(AllocChunkData))
00118 
00119 typedef struct AllocBlockData *AllocBlock;      /* forward reference */
00120 typedef struct AllocChunkData *AllocChunk;
00121 
00122 /*
00123  * AllocPointer
00124  *      Aligned pointer which may be a member of an allocation set.
00125  */
00126 typedef void *AllocPointer;
00127 
00128 /*
00129  * AllocSetContext is our standard implementation of MemoryContext.
00130  *
00131  * Note: header.isReset means there is nothing for AllocSetReset to do.
00132  * This is different from the aset being physically empty (empty blocks list)
00133  * because we may still have a keeper block.  It's also different from the set
00134  * being logically empty, because we don't attempt to detect pfree'ing the
00135  * last active chunk.
00136  */
00137 typedef struct AllocSetContext
00138 {
00139     MemoryContextData header;   /* Standard memory-context fields */
00140     /* Info about storage allocated in this context: */
00141     AllocBlock  blocks;         /* head of list of blocks in this set */
00142     AllocChunk  freelist[ALLOCSET_NUM_FREELISTS];       /* free chunk lists */
00143     /* Allocation parameters for this context: */
00144     Size        initBlockSize;  /* initial block size */
00145     Size        maxBlockSize;   /* maximum block size */
00146     Size        nextBlockSize;  /* next block size to allocate */
00147     Size        allocChunkLimit;    /* effective chunk size limit */
00148     AllocBlock  keeper;         /* if not NULL, keep this block over resets */
00149 } AllocSetContext;
00150 
00151 typedef AllocSetContext *AllocSet;
00152 
00153 /*
00154  * AllocBlock
00155  *      An AllocBlock is the unit of memory that is obtained by aset.c
00156  *      from malloc().  It contains one or more AllocChunks, which are
00157  *      the units requested by palloc() and freed by pfree().  AllocChunks
00158  *      cannot be returned to malloc() individually, instead they are put
00159  *      on freelists by pfree() and re-used by the next palloc() that has
00160  *      a matching request size.
00161  *
00162  *      AllocBlockData is the header data for a block --- the usable space
00163  *      within the block begins at the next alignment boundary.
00164  */
00165 typedef struct AllocBlockData
00166 {
00167     AllocSet    aset;           /* aset that owns this block */
00168     AllocBlock  next;           /* next block in aset's blocks list */
00169     char       *freeptr;        /* start of free space in this block */
00170     char       *endptr;         /* end of space in this block */
00171 }   AllocBlockData;
00172 
00173 /*
00174  * AllocChunk
00175  *      The prefix of each piece of memory in an AllocBlock
00176  *
00177  * NB: this MUST match StandardChunkHeader as defined by utils/memutils.h.
00178  */
00179 typedef struct AllocChunkData
00180 {
00181     /* aset is the owning aset if allocated, or the freelist link if free */
00182     void       *aset;
00183     /* size is always the size of the usable space in the chunk */
00184     Size        size;
00185 #ifdef MEMORY_CONTEXT_CHECKING
00186     /* when debugging memory usage, also store actual requested size */
00187     /* this is zero in a free chunk */
00188     Size        requested_size;
00189 #endif
00190 }   AllocChunkData;
00191 
00192 /*
00193  * AllocPointerIsValid
00194  *      True iff pointer is valid allocation pointer.
00195  */
00196 #define AllocPointerIsValid(pointer) PointerIsValid(pointer)
00197 
00198 /*
00199  * AllocSetIsValid
00200  *      True iff set is valid allocation set.
00201  */
00202 #define AllocSetIsValid(set) PointerIsValid(set)
00203 
00204 #define AllocPointerGetChunk(ptr)   \
00205                     ((AllocChunk)(((char *)(ptr)) - ALLOC_CHUNKHDRSZ))
00206 #define AllocChunkGetPointer(chk)   \
00207                     ((AllocPointer)(((char *)(chk)) + ALLOC_CHUNKHDRSZ))
00208 
00209 /*
00210  * These functions implement the MemoryContext API for AllocSet contexts.
00211  */
00212 static void *AllocSetAlloc(MemoryContext context, Size size);
00213 static void AllocSetFree(MemoryContext context, void *pointer);
00214 static void *AllocSetRealloc(MemoryContext context, void *pointer, Size size);
00215 static void AllocSetInit(MemoryContext context);
00216 static void AllocSetReset(MemoryContext context);
00217 static void AllocSetDelete(MemoryContext context);
00218 static Size AllocSetGetChunkSpace(MemoryContext context, void *pointer);
00219 static bool AllocSetIsEmpty(MemoryContext context);
00220 static void AllocSetStats(MemoryContext context, int level);
00221 
00222 #ifdef MEMORY_CONTEXT_CHECKING
00223 static void AllocSetCheck(MemoryContext context);
00224 #endif
00225 
00226 /*
00227  * This is the virtual function table for AllocSet contexts.
00228  */
00229 static MemoryContextMethods AllocSetMethods = {
00230     AllocSetAlloc,
00231     AllocSetFree,
00232     AllocSetRealloc,
00233     AllocSetInit,
00234     AllocSetReset,
00235     AllocSetDelete,
00236     AllocSetGetChunkSpace,
00237     AllocSetIsEmpty,
00238     AllocSetStats
00239 #ifdef MEMORY_CONTEXT_CHECKING
00240     ,AllocSetCheck
00241 #endif
00242 };
00243 
00244 /*
00245  * Table for AllocSetFreeIndex
00246  */
00247 #define LT16(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
00248 
00249 static const unsigned char LogTable256[256] =
00250 {
00251     0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
00252     LT16(5), LT16(6), LT16(6), LT16(7), LT16(7), LT16(7), LT16(7),
00253     LT16(8), LT16(8), LT16(8), LT16(8), LT16(8), LT16(8), LT16(8), LT16(8)
00254 };
00255 
00256 /* ----------
00257  * Debug macros
00258  * ----------
00259  */
00260 #ifdef HAVE_ALLOCINFO
00261 #define AllocFreeInfo(_cxt, _chunk) \
00262             fprintf(stderr, "AllocFree: %s: %p, %d\n", \
00263                 (_cxt)->header.name, (_chunk), (_chunk)->size)
00264 #define AllocAllocInfo(_cxt, _chunk) \
00265             fprintf(stderr, "AllocAlloc: %s: %p, %d\n", \
00266                 (_cxt)->header.name, (_chunk), (_chunk)->size)
00267 #else
00268 #define AllocFreeInfo(_cxt, _chunk)
00269 #define AllocAllocInfo(_cxt, _chunk)
00270 #endif
00271 
00272 /* ----------
00273  * AllocSetFreeIndex -
00274  *
00275  *      Depending on the size of an allocation compute which freechunk
00276  *      list of the alloc set it belongs to.  Caller must have verified
00277  *      that size <= ALLOC_CHUNK_LIMIT.
00278  * ----------
00279  */
00280 static inline int
00281 AllocSetFreeIndex(Size size)
00282 {
00283     int         idx;
00284     unsigned int t,
00285                 tsize;
00286 
00287     if (size > (1 << ALLOC_MINBITS))
00288     {
00289         tsize = (size - 1) >> ALLOC_MINBITS;
00290 
00291         /*
00292          * At this point we need to obtain log2(tsize)+1, ie, the number of
00293          * not-all-zero bits at the right.  We used to do this with a
00294          * shift-and-count loop, but this function is enough of a hotspot to
00295          * justify micro-optimization effort.  The best approach seems to be
00296          * to use a lookup table.  Note that this code assumes that
00297          * ALLOCSET_NUM_FREELISTS <= 17, since we only cope with two bytes of
00298          * the tsize value.
00299          */
00300         t = tsize >> 8;
00301         idx = t ? LogTable256[t] + 8 : LogTable256[tsize];
00302 
00303         Assert(idx < ALLOCSET_NUM_FREELISTS);
00304     }
00305     else
00306         idx = 0;
00307 
00308     return idx;
00309 }
00310 
00311 #ifdef RANDOMIZE_ALLOCATED_MEMORY
00312 
00313 /*
00314  * Fill a just-allocated piece of memory with "random" data.  It's not really
00315  * very random, just a repeating sequence with a length that's prime.  What
00316  * we mainly want out of it is to have a good probability that two palloc's
00317  * of the same number of bytes start out containing different data.
00318  */
00319 static void
00320 randomize_mem(char *ptr, size_t size)
00321 {
00322     static int  save_ctr = 1;
00323     int         ctr;
00324 
00325     ctr = save_ctr;
00326     while (size-- > 0)
00327     {
00328         *ptr++ = ctr;
00329         if (++ctr > 251)
00330             ctr = 1;
00331     }
00332     save_ctr = ctr;
00333 }
00334 #endif   /* RANDOMIZE_ALLOCATED_MEMORY */
00335 
00336 
00337 /*
00338  * Public routines
00339  */
00340 
00341 
00342 /*
00343  * AllocSetContextCreate
00344  *      Create a new AllocSet context.
00345  *
00346  * parent: parent context, or NULL if top-level context
00347  * name: name of context (for debugging --- string will be copied)
00348  * minContextSize: minimum context size
00349  * initBlockSize: initial allocation block size
00350  * maxBlockSize: maximum allocation block size
00351  */
00352 MemoryContext
00353 AllocSetContextCreate(MemoryContext parent,
00354                       const char *name,
00355                       Size minContextSize,
00356                       Size initBlockSize,
00357                       Size maxBlockSize)
00358 {
00359     AllocSet    context;
00360 
00361     /* Do the type-independent part of context creation */
00362     context = (AllocSet) MemoryContextCreate(T_AllocSetContext,
00363                                              sizeof(AllocSetContext),
00364                                              &AllocSetMethods,
00365                                              parent,
00366                                              name);
00367 
00368     /*
00369      * Make sure alloc parameters are reasonable, and save them.
00370      *
00371      * We somewhat arbitrarily enforce a minimum 1K block size.
00372      */
00373     initBlockSize = MAXALIGN(initBlockSize);
00374     if (initBlockSize < 1024)
00375         initBlockSize = 1024;
00376     maxBlockSize = MAXALIGN(maxBlockSize);
00377     if (maxBlockSize < initBlockSize)
00378         maxBlockSize = initBlockSize;
00379     context->initBlockSize = initBlockSize;
00380     context->maxBlockSize = maxBlockSize;
00381     context->nextBlockSize = initBlockSize;
00382 
00383     /*
00384      * Compute the allocation chunk size limit for this context.  It can't be
00385      * more than ALLOC_CHUNK_LIMIT because of the fixed number of freelists.
00386      * If maxBlockSize is small then requests exceeding the maxBlockSize, or
00387      * even a significant fraction of it, should be treated as large chunks
00388      * too.  For the typical case of maxBlockSize a power of 2, the chunk size
00389      * limit will be at most 1/8th maxBlockSize, so that given a stream of
00390      * requests that are all the maximum chunk size we will waste at most
00391      * 1/8th of the allocated space.
00392      *
00393      * We have to have allocChunkLimit a power of two, because the requested
00394      * and actually-allocated sizes of any chunk must be on the same side of
00395      * the limit, else we get confused about whether the chunk is "big".
00396      */
00397     context->allocChunkLimit = ALLOC_CHUNK_LIMIT;
00398     while ((Size) (context->allocChunkLimit + ALLOC_CHUNKHDRSZ) >
00399            (Size) ((maxBlockSize - ALLOC_BLOCKHDRSZ) / ALLOC_CHUNK_FRACTION))
00400         context->allocChunkLimit >>= 1;
00401 
00402     /*
00403      * Grab always-allocated space, if requested
00404      */
00405     if (minContextSize > ALLOC_BLOCKHDRSZ + ALLOC_CHUNKHDRSZ)
00406     {
00407         Size        blksize = MAXALIGN(minContextSize);
00408         AllocBlock  block;
00409 
00410         block = (AllocBlock) malloc(blksize);
00411         if (block == NULL)
00412         {
00413             MemoryContextStats(TopMemoryContext);
00414             ereport(ERROR,
00415                     (errcode(ERRCODE_OUT_OF_MEMORY),
00416                      errmsg("out of memory"),
00417                      errdetail("Failed while creating memory context \"%s\".",
00418                                name)));
00419         }
00420         block->aset = context;
00421         block->freeptr = ((char *) block) + ALLOC_BLOCKHDRSZ;
00422         block->endptr = ((char *) block) + blksize;
00423         block->next = context->blocks;
00424         context->blocks = block;
00425         /* Mark block as not to be released at reset time */
00426         context->keeper = block;
00427     }
00428 
00429     return (MemoryContext) context;
00430 }
00431 
00432 /*
00433  * AllocSetInit
00434  *      Context-type-specific initialization routine.
00435  *
00436  * This is called by MemoryContextCreate() after setting up the
00437  * generic MemoryContext fields and before linking the new context
00438  * into the context tree.  We must do whatever is needed to make the
00439  * new context minimally valid for deletion.  We must *not* risk
00440  * failure --- thus, for example, allocating more memory is not cool.
00441  * (AllocSetContextCreate can allocate memory when it gets control
00442  * back, however.)
00443  */
00444 static void
00445 AllocSetInit(MemoryContext context)
00446 {
00447     /*
00448      * Since MemoryContextCreate already zeroed the context node, we don't
00449      * have to do anything here: it's already OK.
00450      */
00451 }
00452 
00453 /*
00454  * AllocSetReset
00455  *      Frees all memory which is allocated in the given set.
00456  *
00457  * Actually, this routine has some discretion about what to do.
00458  * It should mark all allocated chunks freed, but it need not necessarily
00459  * give back all the resources the set owns.  Our actual implementation is
00460  * that we hang onto any "keeper" block specified for the set.  In this way,
00461  * we don't thrash malloc() when a context is repeatedly reset after small
00462  * allocations, which is typical behavior for per-tuple contexts.
00463  */
00464 static void
00465 AllocSetReset(MemoryContext context)
00466 {
00467     AllocSet    set = (AllocSet) context;
00468     AllocBlock  block;
00469 
00470     AssertArg(AllocSetIsValid(set));
00471 
00472 #ifdef MEMORY_CONTEXT_CHECKING
00473     /* Check for corruption and leaks before freeing */
00474     AllocSetCheck(context);
00475 #endif
00476 
00477     /* Clear chunk freelists */
00478     MemSetAligned(set->freelist, 0, sizeof(set->freelist));
00479 
00480     block = set->blocks;
00481 
00482     /* New blocks list is either empty or just the keeper block */
00483     set->blocks = set->keeper;
00484 
00485     while (block != NULL)
00486     {
00487         AllocBlock  next = block->next;
00488 
00489         if (block == set->keeper)
00490         {
00491             /* Reset the block, but don't return it to malloc */
00492             char       *datastart = ((char *) block) + ALLOC_BLOCKHDRSZ;
00493 
00494 #ifdef CLOBBER_FREED_MEMORY
00495             /* Wipe freed memory for debugging purposes */
00496             memset(datastart, 0x7F, block->freeptr - datastart);
00497 #endif
00498             block->freeptr = datastart;
00499             block->next = NULL;
00500         }
00501         else
00502         {
00503             /* Normal case, release the block */
00504 #ifdef CLOBBER_FREED_MEMORY
00505             /* Wipe freed memory for debugging purposes */
00506             memset(block, 0x7F, block->freeptr - ((char *) block));
00507 #endif
00508             free(block);
00509         }
00510         block = next;
00511     }
00512 
00513     /* Reset block size allocation sequence, too */
00514     set->nextBlockSize = set->initBlockSize;
00515 }
00516 
00517 /*
00518  * AllocSetDelete
00519  *      Frees all memory which is allocated in the given set,
00520  *      in preparation for deletion of the set.
00521  *
00522  * Unlike AllocSetReset, this *must* free all resources of the set.
00523  * But note we are not responsible for deleting the context node itself.
00524  */
00525 static void
00526 AllocSetDelete(MemoryContext context)
00527 {
00528     AllocSet    set = (AllocSet) context;
00529     AllocBlock  block = set->blocks;
00530 
00531     AssertArg(AllocSetIsValid(set));
00532 
00533 #ifdef MEMORY_CONTEXT_CHECKING
00534     /* Check for corruption and leaks before freeing */
00535     AllocSetCheck(context);
00536 #endif
00537 
00538     /* Make it look empty, just in case... */
00539     MemSetAligned(set->freelist, 0, sizeof(set->freelist));
00540     set->blocks = NULL;
00541     set->keeper = NULL;
00542 
00543     while (block != NULL)
00544     {
00545         AllocBlock  next = block->next;
00546 
00547 #ifdef CLOBBER_FREED_MEMORY
00548         /* Wipe freed memory for debugging purposes */
00549         memset(block, 0x7F, block->freeptr - ((char *) block));
00550 #endif
00551         free(block);
00552         block = next;
00553     }
00554 }
00555 
00556 /*
00557  * AllocSetAlloc
00558  *      Returns pointer to allocated memory of given size; memory is added
00559  *      to the set.
00560  */
00561 static void *
00562 AllocSetAlloc(MemoryContext context, Size size)
00563 {
00564     AllocSet    set = (AllocSet) context;
00565     AllocBlock  block;
00566     AllocChunk  chunk;
00567     int         fidx;
00568     Size        chunk_size;
00569     Size        blksize;
00570 
00571     AssertArg(AllocSetIsValid(set));
00572 
00573     /*
00574      * If requested size exceeds maximum for chunks, allocate an entire block
00575      * for this request.
00576      */
00577     if (size > set->allocChunkLimit)
00578     {
00579         chunk_size = MAXALIGN(size);
00580         blksize = chunk_size + ALLOC_BLOCKHDRSZ + ALLOC_CHUNKHDRSZ;
00581         block = (AllocBlock) malloc(blksize);
00582         if (block == NULL)
00583         {
00584             MemoryContextStats(TopMemoryContext);
00585             ereport(ERROR,
00586                     (errcode(ERRCODE_OUT_OF_MEMORY),
00587                      errmsg("out of memory"),
00588                      errdetail("Failed on request of size %lu.",
00589                                (unsigned long) size)));
00590         }
00591         block->aset = set;
00592         block->freeptr = block->endptr = ((char *) block) + blksize;
00593 
00594         chunk = (AllocChunk) (((char *) block) + ALLOC_BLOCKHDRSZ);
00595         chunk->aset = set;
00596         chunk->size = chunk_size;
00597 #ifdef MEMORY_CONTEXT_CHECKING
00598         chunk->requested_size = size;
00599         /* set mark to catch clobber of "unused" space */
00600         if (size < chunk_size)
00601             ((char *) AllocChunkGetPointer(chunk))[size] = 0x7E;
00602 #endif
00603 #ifdef RANDOMIZE_ALLOCATED_MEMORY
00604         /* fill the allocated space with junk */
00605         randomize_mem((char *) AllocChunkGetPointer(chunk), size);
00606 #endif
00607 
00608         /*
00609          * Stick the new block underneath the active allocation block, so that
00610          * we don't lose the use of the space remaining therein.
00611          */
00612         if (set->blocks != NULL)
00613         {
00614             block->next = set->blocks->next;
00615             set->blocks->next = block;
00616         }
00617         else
00618         {
00619             block->next = NULL;
00620             set->blocks = block;
00621         }
00622 
00623         AllocAllocInfo(set, chunk);
00624         return AllocChunkGetPointer(chunk);
00625     }
00626 
00627     /*
00628      * Request is small enough to be treated as a chunk.  Look in the
00629      * corresponding free list to see if there is a free chunk we could reuse.
00630      * If one is found, remove it from the free list, make it again a member
00631      * of the alloc set and return its data address.
00632      */
00633     fidx = AllocSetFreeIndex(size);
00634     chunk = set->freelist[fidx];
00635     if (chunk != NULL)
00636     {
00637         Assert(chunk->size >= size);
00638 
00639         set->freelist[fidx] = (AllocChunk) chunk->aset;
00640 
00641         chunk->aset = (void *) set;
00642 
00643 #ifdef MEMORY_CONTEXT_CHECKING
00644         chunk->requested_size = size;
00645         /* set mark to catch clobber of "unused" space */
00646         if (size < chunk->size)
00647             ((char *) AllocChunkGetPointer(chunk))[size] = 0x7E;
00648 #endif
00649 #ifdef RANDOMIZE_ALLOCATED_MEMORY
00650         /* fill the allocated space with junk */
00651         randomize_mem((char *) AllocChunkGetPointer(chunk), size);
00652 #endif
00653 
00654         AllocAllocInfo(set, chunk);
00655         return AllocChunkGetPointer(chunk);
00656     }
00657 
00658     /*
00659      * Choose the actual chunk size to allocate.
00660      */
00661     chunk_size = (1 << ALLOC_MINBITS) << fidx;
00662     Assert(chunk_size >= size);
00663 
00664     /*
00665      * If there is enough room in the active allocation block, we will put the
00666      * chunk into that block.  Else must start a new one.
00667      */
00668     if ((block = set->blocks) != NULL)
00669     {
00670         Size        availspace = block->endptr - block->freeptr;
00671 
00672         if (availspace < (chunk_size + ALLOC_CHUNKHDRSZ))
00673         {
00674             /*
00675              * The existing active (top) block does not have enough room for
00676              * the requested allocation, but it might still have a useful
00677              * amount of space in it.  Once we push it down in the block list,
00678              * we'll never try to allocate more space from it. So, before we
00679              * do that, carve up its free space into chunks that we can put on
00680              * the set's freelists.
00681              *
00682              * Because we can only get here when there's less than
00683              * ALLOC_CHUNK_LIMIT left in the block, this loop cannot iterate
00684              * more than ALLOCSET_NUM_FREELISTS-1 times.
00685              */
00686             while (availspace >= ((1 << ALLOC_MINBITS) + ALLOC_CHUNKHDRSZ))
00687             {
00688                 Size        availchunk = availspace - ALLOC_CHUNKHDRSZ;
00689                 int         a_fidx = AllocSetFreeIndex(availchunk);
00690 
00691                 /*
00692                  * In most cases, we'll get back the index of the next larger
00693                  * freelist than the one we need to put this chunk on.  The
00694                  * exception is when availchunk is exactly a power of 2.
00695                  */
00696                 if (availchunk != ((Size) 1 << (a_fidx + ALLOC_MINBITS)))
00697                 {
00698                     a_fidx--;
00699                     Assert(a_fidx >= 0);
00700                     availchunk = ((Size) 1 << (a_fidx + ALLOC_MINBITS));
00701                 }
00702 
00703                 chunk = (AllocChunk) (block->freeptr);
00704 
00705                 block->freeptr += (availchunk + ALLOC_CHUNKHDRSZ);
00706                 availspace -= (availchunk + ALLOC_CHUNKHDRSZ);
00707 
00708                 chunk->size = availchunk;
00709 #ifdef MEMORY_CONTEXT_CHECKING
00710                 chunk->requested_size = 0;      /* mark it free */
00711 #endif
00712                 chunk->aset = (void *) set->freelist[a_fidx];
00713                 set->freelist[a_fidx] = chunk;
00714             }
00715 
00716             /* Mark that we need to create a new block */
00717             block = NULL;
00718         }
00719     }
00720 
00721     /*
00722      * Time to create a new regular (multi-chunk) block?
00723      */
00724     if (block == NULL)
00725     {
00726         Size        required_size;
00727 
00728         /*
00729          * The first such block has size initBlockSize, and we double the
00730          * space in each succeeding block, but not more than maxBlockSize.
00731          */
00732         blksize = set->nextBlockSize;
00733         set->nextBlockSize <<= 1;
00734         if (set->nextBlockSize > set->maxBlockSize)
00735             set->nextBlockSize = set->maxBlockSize;
00736 
00737         /*
00738          * If initBlockSize is less than ALLOC_CHUNK_LIMIT, we could need more
00739          * space... but try to keep it a power of 2.
00740          */
00741         required_size = chunk_size + ALLOC_BLOCKHDRSZ + ALLOC_CHUNKHDRSZ;
00742         while (blksize < required_size)
00743             blksize <<= 1;
00744 
00745         /* Try to allocate it */
00746         block = (AllocBlock) malloc(blksize);
00747 
00748         /*
00749          * We could be asking for pretty big blocks here, so cope if malloc
00750          * fails.  But give up if there's less than a meg or so available...
00751          */
00752         while (block == NULL && blksize > 1024 * 1024)
00753         {
00754             blksize >>= 1;
00755             if (blksize < required_size)
00756                 break;
00757             block = (AllocBlock) malloc(blksize);
00758         }
00759 
00760         if (block == NULL)
00761         {
00762             MemoryContextStats(TopMemoryContext);
00763             ereport(ERROR,
00764                     (errcode(ERRCODE_OUT_OF_MEMORY),
00765                      errmsg("out of memory"),
00766                      errdetail("Failed on request of size %lu.",
00767                                (unsigned long) size)));
00768         }
00769 
00770         block->aset = set;
00771         block->freeptr = ((char *) block) + ALLOC_BLOCKHDRSZ;
00772         block->endptr = ((char *) block) + blksize;
00773 
00774         /*
00775          * If this is the first block of the set, make it the "keeper" block.
00776          * Formerly, a keeper block could only be created during context
00777          * creation, but allowing it to happen here lets us have fast reset
00778          * cycling even for contexts created with minContextSize = 0; that way
00779          * we don't have to force space to be allocated in contexts that might
00780          * never need any space.  Don't mark an oversize block as a keeper,
00781          * however.
00782          */
00783         if (set->keeper == NULL && blksize == set->initBlockSize)
00784             set->keeper = block;
00785 
00786         block->next = set->blocks;
00787         set->blocks = block;
00788     }
00789 
00790     /*
00791      * OK, do the allocation
00792      */
00793     chunk = (AllocChunk) (block->freeptr);
00794 
00795     block->freeptr += (chunk_size + ALLOC_CHUNKHDRSZ);
00796     Assert(block->freeptr <= block->endptr);
00797 
00798     chunk->aset = (void *) set;
00799     chunk->size = chunk_size;
00800 #ifdef MEMORY_CONTEXT_CHECKING
00801     chunk->requested_size = size;
00802     /* set mark to catch clobber of "unused" space */
00803     if (size < chunk->size)
00804         ((char *) AllocChunkGetPointer(chunk))[size] = 0x7E;
00805 #endif
00806 #ifdef RANDOMIZE_ALLOCATED_MEMORY
00807     /* fill the allocated space with junk */
00808     randomize_mem((char *) AllocChunkGetPointer(chunk), size);
00809 #endif
00810 
00811     AllocAllocInfo(set, chunk);
00812     return AllocChunkGetPointer(chunk);
00813 }
00814 
00815 /*
00816  * AllocSetFree
00817  *      Frees allocated memory; memory is removed from the set.
00818  */
00819 static void
00820 AllocSetFree(MemoryContext context, void *pointer)
00821 {
00822     AllocSet    set = (AllocSet) context;
00823     AllocChunk  chunk = AllocPointerGetChunk(pointer);
00824 
00825     AllocFreeInfo(set, chunk);
00826 
00827 #ifdef MEMORY_CONTEXT_CHECKING
00828     /* Test for someone scribbling on unused space in chunk */
00829     if (chunk->requested_size < chunk->size)
00830         if (((char *) pointer)[chunk->requested_size] != 0x7E)
00831             elog(WARNING, "detected write past chunk end in %s %p",
00832                  set->header.name, chunk);
00833 #endif
00834 
00835     if (chunk->size > set->allocChunkLimit)
00836     {
00837         /*
00838          * Big chunks are certain to have been allocated as single-chunk
00839          * blocks.  Find the containing block and return it to malloc().
00840          */
00841         AllocBlock  block = set->blocks;
00842         AllocBlock  prevblock = NULL;
00843 
00844         while (block != NULL)
00845         {
00846             if (chunk == (AllocChunk) (((char *) block) + ALLOC_BLOCKHDRSZ))
00847                 break;
00848             prevblock = block;
00849             block = block->next;
00850         }
00851         if (block == NULL)
00852             elog(ERROR, "could not find block containing chunk %p", chunk);
00853         /* let's just make sure chunk is the only one in the block */
00854         Assert(block->freeptr == ((char *) block) +
00855                (chunk->size + ALLOC_BLOCKHDRSZ + ALLOC_CHUNKHDRSZ));
00856 
00857         /* OK, remove block from aset's list and free it */
00858         if (prevblock == NULL)
00859             set->blocks = block->next;
00860         else
00861             prevblock->next = block->next;
00862 #ifdef CLOBBER_FREED_MEMORY
00863         /* Wipe freed memory for debugging purposes */
00864         memset(block, 0x7F, block->freeptr - ((char *) block));
00865 #endif
00866         free(block);
00867     }
00868     else
00869     {
00870         /* Normal case, put the chunk into appropriate freelist */
00871         int         fidx = AllocSetFreeIndex(chunk->size);
00872 
00873         chunk->aset = (void *) set->freelist[fidx];
00874 
00875 #ifdef CLOBBER_FREED_MEMORY
00876         /* Wipe freed memory for debugging purposes */
00877         memset(pointer, 0x7F, chunk->size);
00878 #endif
00879 
00880 #ifdef MEMORY_CONTEXT_CHECKING
00881         /* Reset requested_size to 0 in chunks that are on freelist */
00882         chunk->requested_size = 0;
00883 #endif
00884         set->freelist[fidx] = chunk;
00885     }
00886 }
00887 
00888 /*
00889  * AllocSetRealloc
00890  *      Returns new pointer to allocated memory of given size; this memory
00891  *      is added to the set.  Memory associated with given pointer is copied
00892  *      into the new memory, and the old memory is freed.
00893  */
00894 static void *
00895 AllocSetRealloc(MemoryContext context, void *pointer, Size size)
00896 {
00897     AllocSet    set = (AllocSet) context;
00898     AllocChunk  chunk = AllocPointerGetChunk(pointer);
00899     Size        oldsize = chunk->size;
00900 
00901 #ifdef MEMORY_CONTEXT_CHECKING
00902     /* Test for someone scribbling on unused space in chunk */
00903     if (chunk->requested_size < oldsize)
00904         if (((char *) pointer)[chunk->requested_size] != 0x7E)
00905             elog(WARNING, "detected write past chunk end in %s %p",
00906                  set->header.name, chunk);
00907 #endif
00908 
00909     /*
00910      * Chunk sizes are aligned to power of 2 in AllocSetAlloc(). Maybe the
00911      * allocated area already is >= the new size.  (In particular, we always
00912      * fall out here if the requested size is a decrease.)
00913      */
00914     if (oldsize >= size)
00915     {
00916 #ifdef MEMORY_CONTEXT_CHECKING
00917 #ifdef RANDOMIZE_ALLOCATED_MEMORY
00918         /* We can only fill the extra space if we know the prior request */
00919         if (size > chunk->requested_size)
00920             randomize_mem((char *) AllocChunkGetPointer(chunk) + chunk->requested_size,
00921                           size - chunk->requested_size);
00922 #endif
00923 
00924         chunk->requested_size = size;
00925         /* set mark to catch clobber of "unused" space */
00926         if (size < oldsize)
00927             ((char *) pointer)[size] = 0x7E;
00928 #endif
00929         return pointer;
00930     }
00931 
00932     if (oldsize > set->allocChunkLimit)
00933     {
00934         /*
00935          * The chunk must have been allocated as a single-chunk block.  Find
00936          * the containing block and use realloc() to make it bigger with
00937          * minimum space wastage.
00938          */
00939         AllocBlock  block = set->blocks;
00940         AllocBlock  prevblock = NULL;
00941         Size        chksize;
00942         Size        blksize;
00943 
00944         while (block != NULL)
00945         {
00946             if (chunk == (AllocChunk) (((char *) block) + ALLOC_BLOCKHDRSZ))
00947                 break;
00948             prevblock = block;
00949             block = block->next;
00950         }
00951         if (block == NULL)
00952             elog(ERROR, "could not find block containing chunk %p", chunk);
00953         /* let's just make sure chunk is the only one in the block */
00954         Assert(block->freeptr == ((char *) block) +
00955                (chunk->size + ALLOC_BLOCKHDRSZ + ALLOC_CHUNKHDRSZ));
00956 
00957         /* Do the realloc */
00958         chksize = MAXALIGN(size);
00959         blksize = chksize + ALLOC_BLOCKHDRSZ + ALLOC_CHUNKHDRSZ;
00960         block = (AllocBlock) realloc(block, blksize);
00961         if (block == NULL)
00962         {
00963             MemoryContextStats(TopMemoryContext);
00964             ereport(ERROR,
00965                     (errcode(ERRCODE_OUT_OF_MEMORY),
00966                      errmsg("out of memory"),
00967                      errdetail("Failed on request of size %lu.",
00968                                (unsigned long) size)));
00969         }
00970         block->freeptr = block->endptr = ((char *) block) + blksize;
00971 
00972         /* Update pointers since block has likely been moved */
00973         chunk = (AllocChunk) (((char *) block) + ALLOC_BLOCKHDRSZ);
00974         if (prevblock == NULL)
00975             set->blocks = block;
00976         else
00977             prevblock->next = block;
00978         chunk->size = chksize;
00979 
00980 #ifdef MEMORY_CONTEXT_CHECKING
00981 #ifdef RANDOMIZE_ALLOCATED_MEMORY
00982         /* We can only fill the extra space if we know the prior request */
00983         randomize_mem((char *) AllocChunkGetPointer(chunk) + chunk->requested_size,
00984                       size - chunk->requested_size);
00985 #endif
00986 
00987         chunk->requested_size = size;
00988         /* set mark to catch clobber of "unused" space */
00989         if (size < chunk->size)
00990             ((char *) AllocChunkGetPointer(chunk))[size] = 0x7E;
00991 #endif
00992 
00993         return AllocChunkGetPointer(chunk);
00994     }
00995     else
00996     {
00997         /*
00998          * Small-chunk case.  We just do this by brute force, ie, allocate a
00999          * new chunk and copy the data.  Since we know the existing data isn't
01000          * huge, this won't involve any great memcpy expense, so it's not
01001          * worth being smarter.  (At one time we tried to avoid memcpy when it
01002          * was possible to enlarge the chunk in-place, but that turns out to
01003          * misbehave unpleasantly for repeated cycles of
01004          * palloc/repalloc/pfree: the eventually freed chunks go into the
01005          * wrong freelist for the next initial palloc request, and so we leak
01006          * memory indefinitely.  See pgsql-hackers archives for 2007-08-11.)
01007          */
01008         AllocPointer newPointer;
01009 
01010         /* allocate new chunk */
01011         newPointer = AllocSetAlloc((MemoryContext) set, size);
01012 
01013         /* transfer existing data (certain to fit) */
01014         memcpy(newPointer, pointer, oldsize);
01015 
01016         /* free old chunk */
01017         AllocSetFree((MemoryContext) set, pointer);
01018 
01019         return newPointer;
01020     }
01021 }
01022 
01023 /*
01024  * AllocSetGetChunkSpace
01025  *      Given a currently-allocated chunk, determine the total space
01026  *      it occupies (including all memory-allocation overhead).
01027  */
01028 static Size
01029 AllocSetGetChunkSpace(MemoryContext context, void *pointer)
01030 {
01031     AllocChunk  chunk = AllocPointerGetChunk(pointer);
01032 
01033     return chunk->size + ALLOC_CHUNKHDRSZ;
01034 }
01035 
01036 /*
01037  * AllocSetIsEmpty
01038  *      Is an allocset empty of any allocated space?
01039  */
01040 static bool
01041 AllocSetIsEmpty(MemoryContext context)
01042 {
01043     /*
01044      * For now, we say "empty" only if the context is new or just reset. We
01045      * could examine the freelists to determine if all space has been freed,
01046      * but it's not really worth the trouble for present uses of this
01047      * functionality.
01048      */
01049     if (context->isReset)
01050         return true;
01051     return false;
01052 }
01053 
01054 /*
01055  * AllocSetStats
01056  *      Displays stats about memory consumption of an allocset.
01057  */
01058 static void
01059 AllocSetStats(MemoryContext context, int level)
01060 {
01061     AllocSet    set = (AllocSet) context;
01062     long        nblocks = 0;
01063     long        nchunks = 0;
01064     long        totalspace = 0;
01065     long        freespace = 0;
01066     AllocBlock  block;
01067     AllocChunk  chunk;
01068     int         fidx;
01069     int         i;
01070 
01071     for (block = set->blocks; block != NULL; block = block->next)
01072     {
01073         nblocks++;
01074         totalspace += block->endptr - ((char *) block);
01075         freespace += block->endptr - block->freeptr;
01076     }
01077     for (fidx = 0; fidx < ALLOCSET_NUM_FREELISTS; fidx++)
01078     {
01079         for (chunk = set->freelist[fidx]; chunk != NULL;
01080              chunk = (AllocChunk) chunk->aset)
01081         {
01082             nchunks++;
01083             freespace += chunk->size + ALLOC_CHUNKHDRSZ;
01084         }
01085     }
01086 
01087     for (i = 0; i < level; i++)
01088         fprintf(stderr, "  ");
01089 
01090     fprintf(stderr,
01091             "%s: %lu total in %ld blocks; %lu free (%ld chunks); %lu used\n",
01092             set->header.name, totalspace, nblocks, freespace, nchunks,
01093             totalspace - freespace);
01094 }
01095 
01096 
01097 #ifdef MEMORY_CONTEXT_CHECKING
01098 
01099 /*
01100  * AllocSetCheck
01101  *      Walk through chunks and check consistency of memory.
01102  *
01103  * NOTE: report errors as WARNING, *not* ERROR or FATAL.  Otherwise you'll
01104  * find yourself in an infinite loop when trouble occurs, because this
01105  * routine will be entered again when elog cleanup tries to release memory!
01106  */
01107 static void
01108 AllocSetCheck(MemoryContext context)
01109 {
01110     AllocSet    set = (AllocSet) context;
01111     char       *name = set->header.name;
01112     AllocBlock  block;
01113 
01114     for (block = set->blocks; block != NULL; block = block->next)
01115     {
01116         char       *bpoz = ((char *) block) + ALLOC_BLOCKHDRSZ;
01117         long        blk_used = block->freeptr - bpoz;
01118         long        blk_data = 0;
01119         long        nchunks = 0;
01120 
01121         /*
01122          * Empty block - empty can be keeper-block only
01123          */
01124         if (!blk_used)
01125         {
01126             if (set->keeper != block)
01127                 elog(WARNING, "problem in alloc set %s: empty block %p",
01128                      name, block);
01129         }
01130 
01131         /*
01132          * Chunk walker
01133          */
01134         while (bpoz < block->freeptr)
01135         {
01136             AllocChunk  chunk = (AllocChunk) bpoz;
01137             Size        chsize,
01138                         dsize;
01139             char       *chdata_end;
01140 
01141             chsize = chunk->size;       /* aligned chunk size */
01142             dsize = chunk->requested_size;      /* real data */
01143             chdata_end = ((char *) chunk) + (ALLOC_CHUNKHDRSZ + dsize);
01144 
01145             /*
01146              * Check chunk size
01147              */
01148             if (dsize > chsize)
01149                 elog(WARNING, "problem in alloc set %s: req size > alloc size for chunk %p in block %p",
01150                      name, chunk, block);
01151             if (chsize < (1 << ALLOC_MINBITS))
01152                 elog(WARNING, "problem in alloc set %s: bad size %lu for chunk %p in block %p",
01153                      name, (unsigned long) chsize, chunk, block);
01154 
01155             /* single-chunk block? */
01156             if (chsize > set->allocChunkLimit &&
01157                 chsize + ALLOC_CHUNKHDRSZ != blk_used)
01158                 elog(WARNING, "problem in alloc set %s: bad single-chunk %p in block %p",
01159                      name, chunk, block);
01160 
01161             /*
01162              * If chunk is allocated, check for correct aset pointer. (If it's
01163              * free, the aset is the freelist pointer, which we can't check as
01164              * easily...)
01165              */
01166             if (dsize > 0 && chunk->aset != (void *) set)
01167                 elog(WARNING, "problem in alloc set %s: bogus aset link in block %p, chunk %p",
01168                      name, block, chunk);
01169 
01170             /*
01171              * Check for overwrite of "unallocated" space in chunk
01172              */
01173             if (dsize > 0 && dsize < chsize && *chdata_end != 0x7E)
01174                 elog(WARNING, "problem in alloc set %s: detected write past chunk end in block %p, chunk %p",
01175                      name, block, chunk);
01176 
01177             blk_data += chsize;
01178             nchunks++;
01179 
01180             bpoz += ALLOC_CHUNKHDRSZ + chsize;
01181         }
01182 
01183         if ((blk_data + (nchunks * ALLOC_CHUNKHDRSZ)) != blk_used)
01184             elog(WARNING, "problem in alloc set %s: found inconsistent memory block %p",
01185                  name, block);
01186     }
01187 }
01188 
01189 #endif   /* MEMORY_CONTEXT_CHECKING */