Back to index

lightning-sunbird  0.9+nobinonly
morkZone.h
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-  */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is mozilla.org code.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1999
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *
00024  * Alternatively, the contents of this file may be used under the terms of
00025  * either of the GNU General Public License Version 2 or later (the "GPL"),
00026  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00027  * in which case the provisions of the GPL or the LGPL are applicable instead
00028  * of those above. If you wish to allow use of your version of this file only
00029  * under the terms of either the GPL or the LGPL, and not to allow others to
00030  * use your version of this file under the terms of the MPL, indicate your
00031  * decision by deleting the provisions above and replace them with the notice
00032  * and other provisions required by the GPL or the LGPL. If you do not delete
00033  * the provisions above, a recipient may use your version of this file under
00034  * the terms of any one of the MPL, the GPL or the LGPL.
00035  *
00036  * ***** END LICENSE BLOCK ***** */
00037 
00038 #ifndef _MORKZONE_
00039 #define _MORKZONE_ 1
00040 
00041 #ifndef _MORK_
00042 #include "mork.h"
00043 #endif
00044 
00045 #ifndef _MORKNODE_
00046 #include "morkNode.h"
00047 #endif
00048 
00049 #ifndef _MORKDEQUE_
00050 #include "morkDeque.h"
00051 #endif
00052 
00053 //3456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789
00054 
00055 /*| CONFIG_DEBUG: do paranoid debug checks if defined.
00056 |*/
00057 #ifdef MORK_DEBUG
00058 #define morkZone_CONFIG_DEBUG 1 /* debug paranoid if defined */
00059 #endif /*MORK_DEBUG*/
00060 
00061 /*| CONFIG_STATS: keep volume and usage statistics.
00062 |*/
00063 #define morkZone_CONFIG_VOL_STATS 1 /* count space used by zone instance */
00064 
00065 /*| CONFIG_ARENA: if this is defined, then the morkZone class will alloc big
00066 **| blocks from the zone's heap, and suballocate from these.  If undefined,
00067 **| then morkZone will just pass all calls through to the zone's heap.
00068 |*/
00069 #ifdef MORK_ENABLE_ZONE_ARENAS
00070 #define morkZone_CONFIG_ARENA 1 /* be arena, if defined; otherwise no-op */
00071 #endif /*MORK_ENABLE_ZONE_ARENAS*/
00072 
00073 /*| CONFIG_ALIGN_8: if this is defined, then the morkZone class will give
00074 **| blocks 8 byte alignment instead of only 4 byte alignment.
00075 |*/
00076 #ifdef MORK_CONFIG_ALIGN_8
00077 #define morkZone_CONFIG_ALIGN_8 1 /* ifdef: align to 8 bytes, otherwise 4 */
00078 #endif /*MORK_CONFIG_ALIGN_8*/
00079 
00080 /*| CONFIG_PTR_SIZE_4: if this is defined, then the morkZone class will
00081 **| assume sizeof(void*) == 4, so a tag slot for padding is needed.
00082 |*/
00083 #ifdef MORK_CONFIG_PTR_SIZE_4
00084 #define morkZone_CONFIG_PTR_SIZE_4 1 /* ifdef: sizeof(void*) == 4 */
00085 #endif /*MORK_CONFIG_PTR_SIZE_4*/
00086 
00087 /*| morkZone_USE_TAG_SLOT: if this is defined, then define slot mRun_Tag
00088 **| in order to achieve eight byte alignment after the mRun_Next slot.
00089 |*/
00090 #if defined(morkZone_CONFIG_ALIGN_8) && defined(morkZone_CONFIG_PTR_SIZE_4)
00091 #define morkRun_USE_TAG_SLOT 1  /* need mRun_Tag slot inside morkRun */
00092 #define morkHunk_USE_TAG_SLOT 1 /* need mHunk_Tag slot inside morkHunk */
00093 #endif
00094 
00095 //3456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789
00096 
00097 #define morkRun_kTag ((mork_u4) 0x6D52754E ) /* ascii 'mRuN' */
00098 
00099 /*| morkRun: structure used by morkZone for sized blocks
00100 |*/
00101 class morkRun {
00102 
00103 protected: // member variable slots
00104 #ifdef morkRun_USE_TAG_SLOT
00105   mork_u4   mRun_Tag; // force 8 byte alignment after mRun_Next
00106 #endif /* morkRun_USE_TAG_SLOT */
00107 
00108   morkRun*  mRun_Next;
00109   
00110 public: // pointer interpretation of mRun_Next (when inside a list):
00111   morkRun*   RunNext() const { return mRun_Next; }
00112   void       RunSetNext(morkRun* ioNext) { mRun_Next = ioNext; }
00113   
00114 public: // size interpretation of mRun_Next (when not inside a list):
00115   mork_size  RunSize() const { return (mork_size) ((mork_ip) mRun_Next); }
00116   void       RunSetSize(mork_size inSize)
00117              { mRun_Next = (morkRun*) ((mork_ip) inSize); }
00118   
00119 public: // maintenance and testing of optional tag magic signature slot:
00120 #ifdef morkRun_USE_TAG_SLOT
00121   void       RunInitTag() { mRun_Tag = morkRun_kTag; }
00122   mork_bool  RunGoodTag() { return ( mRun_Tag == morkRun_kTag ); }
00123 #endif /* morkRun_USE_TAG_SLOT */
00124   
00125 public: // conversion back and forth to inline block following run instance:
00126   void* RunAsBlock() { return (((mork_u1*) this) + sizeof(morkRun)); }
00127   
00128   static morkRun* BlockAsRun(void* ioBlock)
00129   { return (morkRun*) (((mork_u1*) ioBlock) - sizeof(morkRun)); }
00130 
00131 public: // typing & errors
00132   static void BadRunTagError(morkEnv* ev);
00133   static void RunSizeAlignError(morkEnv* ev);
00134 };
00135 
00136 //3456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789
00137 
00138 
00139 /*| morkOldRun: more space to record size when run is put into old free list
00140 |*/
00141 class morkOldRun : public morkRun {
00142 
00143 protected: // need another size field when mRun_Next is used for linkage:
00144   mdb_size mOldRun_Size;
00145   
00146 public: // size getter/setter
00147   mork_size  OldSize() const { return mOldRun_Size; }
00148   void       OldSetSize(mork_size inSize) { mOldRun_Size = inSize; }
00149   
00150 };
00151 
00152 //3456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789
00153 
00154 #define morkHunk_kTag ((mork_u4) 0x68556E4B ) /* ascii 'hUnK' */
00155 
00156 /*| morkHunk: structure used by morkZone for heap allocations.
00157 |*/
00158 class morkHunk {
00159 
00160 protected: // member variable slots
00161 
00162 #ifdef morkHunk_USE_TAG_SLOT
00163   mork_u4   mHunk_Tag; // force 8 byte alignment after mHunk_Next
00164 #endif /* morkHunk_USE_TAG_SLOT */
00165 
00166   morkHunk* mHunk_Next;
00167   
00168   morkRun   mHunk_Run;
00169   
00170 public: // setters
00171   void      HunkSetNext(morkHunk* ioNext) { mHunk_Next = ioNext; }
00172   
00173 public: // getters
00174   morkHunk* HunkNext() const { return mHunk_Next; }
00175 
00176   morkRun*  HunkRun() { return &mHunk_Run; }
00177   
00178 public: // maintenance and testing of optional tag magic signature slot:
00179 #ifdef morkHunk_USE_TAG_SLOT
00180   void       HunkInitTag() { mHunk_Tag = morkHunk_kTag; }
00181   mork_bool  HunkGoodTag() { return ( mHunk_Tag == morkHunk_kTag ); }
00182 #endif /* morkHunk_USE_TAG_SLOT */
00183 
00184 public: // typing & errors
00185   static void BadHunkTagWarning(morkEnv* ev);
00186   
00187 };
00188 
00189 //3456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789
00190 
00191 /*| kNewHunkSize: the default size for a hunk, assuming we must allocate
00192 **| a new one whenever the free hunk list does not already have.  Note this
00193 **| number should not be changed without also considering suitable changes
00194 **| in the related kMaxHunkWaste and kMinHunkSize constants. 
00195 |*/
00196 #define morkZone_kNewHunkSize ((mork_size) (64 * 1024)) /* 64K per hunk */
00197 
00198 /*| kMaxFreeVolume: some number of bytes of free space in the free hunk list
00199 **| over which we no longer want to add more free hunks to the list, for fear
00200 **| of accumulating too much unused, fragmented free space.  This should be a
00201 **| small multiple of kNewHunkSize, say about two to four times as great, to
00202 **| allow for no more free hunk space than fits in a handful of new hunks.
00203 **| This strategy will let us usefuly accumulate "some" free space in the
00204 **| free hunk list, but without accumulating "too much" free space that way.
00205 |*/
00206 #define morkZone_kMaxFreeVolume (morkZone_kNewHunkSize * 3)
00207 
00208 /*| kMaxHunkWaste: if a current request is larger than this, and we cannot
00209 **| satisfy the request with the current hunk, then we just allocate the
00210 **| block from the heap without changing the current hunk.  Basically this
00211 **| number represents the largest amount of memory we are willing to waste,
00212 **| since a block request barely less than this can cause the current hunk
00213 **| to be retired (with any unused space wasted) as well get a new hunk.
00214 |*/
00215 #define morkZone_kMaxHunkWaste ((mork_size) 4096) /* 1/16 kNewHunkSize */
00216 
00217 /*| kRound*: the algorithm for rounding up allocation sizes for caching
00218 **| in free lists works like the following.  We add kRoundAdd to any size
00219 **| requested, and then bitwise AND with kRoundMask, and this will give us
00220 **| the smallest multiple of kRoundSize that is at least as large as the
00221 **| requested size.  Then if we rightshift this number by kRoundBits, we
00222 **| will have the index into the mZone_FreeRuns array which will hold any
00223 **| cache runs of that size.  So 4 bits of shift gives us a granularity
00224 **| of 16 bytes, so that free lists will hold successive runs that are
00225 **| 16 bytes greater than the next smaller run size.  If we have 256 free
00226 **| lists of nonzero sized runs altogether, then the largest run that can
00227 **| be cached is 4096, or 4K (since 4096 == 16 * 256).  A larger run that
00228 **| gets freed will go in to the free hunk list (or back to the heap).
00229 |*/
00230 #define morkZone_kRoundBits 4 /* bits to round-up size for free lists */
00231 #define morkZone_kRoundSize (1 << morkZone_kRoundBits)
00232 #define morkZone_kRoundAdd ((1 << morkZone_kRoundBits) - 1)
00233 #define morkZone_kRoundMask (~ ((mork_ip) morkZone_kRoundAdd))
00234 
00235 #define morkZone_kBuckets 256 /* number of distinct free lists */
00236 
00237 /*| kMaxCachedRun: the largest run that will be stored inside a free
00238 **| list of old zapped runs.  A run larger than this cannot be put in
00239 **| a free list, and must be allocated from the heap at need, and put
00240 **| into the free hunk list when discarded.
00241 |*/
00242 #define morkZone_kMaxCachedRun (morkZone_kBuckets * morkZone_kRoundSize)
00243 
00244 #define morkDerived_kZone     /*i*/ 0x5A6E /* ascii 'Zn' */
00245 
00246 /*| morkZone: a pooled memory allocator like an NSPR arena.  The term 'zone'
00247 **| is roughly synonymous with 'heap'.  I avoid calling this class a "heap"
00248 **| to avoid any confusion with nsIMdbHeap, and I avoid calling this class
00249 **| an arean to avoid confusion with NSPR usage.
00250 |*/
00251 class morkZone : public morkNode, public nsIMdbHeap {
00252 
00253 // public: // slots inherited from morkNode (meant to inform only)
00254   // nsIMdbHeap*       mNode_Heap;
00255 
00256   // mork_base      mNode_Base;     // must equal morkBase_kNode
00257   // mork_derived   mNode_Derived;  // depends on specific node subclass
00258   
00259   // mork_access    mNode_Access;   // kOpen, kClosing, kShut, or kDead
00260   // mork_usage     mNode_Usage;    // kHeap, kStack, kMember, kGlobal, kNone
00261   // mork_able      mNode_Mutable;  // can this node be modified?
00262   // mork_load      mNode_Load;     // is this node clean or dirty?
00263   
00264   // mork_uses      mNode_Uses;     // refcount for strong refs
00265   // mork_refs      mNode_Refs;     // refcount for strong refs + weak refs
00266 
00267 public: // state is public because the entire Mork system is private
00268 
00269   nsIMdbHeap*  mZone_Heap; // strong ref to heap allocating all space
00270   
00271   mork_size    mZone_HeapVolume;  // total bytes allocated from heap
00272   mork_size    mZone_BlockVolume; // total bytes in all zone blocks
00273   mork_size    mZone_RunVolume;   // total bytes in all zone runs
00274   mork_size    mZone_ChipVolume;  // total bytes in all zone chips
00275   
00276   mork_size    mZone_FreeOldRunVolume; // total bytes in all used hunks
00277   
00278   mork_count   mZone_HunkCount;        // total number of used hunks
00279   mork_count   mZone_FreeOldRunCount;  // total free old runs
00280 
00281   morkHunk*    mZone_HunkList;       // linked list of all used hunks  
00282   morkRun*     mZone_FreeOldRunList; // linked list of free old runs
00283   
00284   // note mZone_At is a byte pointer for single byte address arithmetic:
00285   mork_u1*     mZone_At;     // current position in most recent hunk
00286   mork_size    mZone_AtSize; // number of bytes remaining in this hunk
00287   
00288   // kBuckets+1 so indexes zero through kBuckets are all okay to use:
00289   
00290   morkRun*     mZone_FreeRuns[ morkZone_kBuckets + 1 ];
00291   // Each piece of memory stored in list mZone_FreeRuns[ i ] has an
00292   // allocation size equal to sizeof(morkRun) + (i * kRoundSize), so
00293   // that callers can be given a piece of memory with (i * kRoundSize)
00294   // bytes of writeable space while reserving the first sizeof(morkRun)
00295   // bytes to keep track of size information for later re-use.  Note
00296   // that mZone_FreeRuns[ 0 ] is unused because no run will be zero
00297   // bytes in size (and morkZone plans to complain about zero sizes). 
00298 
00299 protected: // zone utilities
00300   
00301   mork_size zone_grow_at(morkEnv* ev, mork_size inNeededSize);
00302 
00303   void*     zone_new_chip(morkEnv* ev, mdb_size inSize); // alloc  
00304   morkHunk* zone_new_hunk(morkEnv* ev, mdb_size inRunSize); // alloc  
00305 
00306 // { ===== begin nsIMdbHeap methods =====
00307 public:
00308   NS_IMETHOD Alloc(nsIMdbEnv* ev, // allocate a piece of memory
00309     mdb_size inSize,   // requested size of new memory block 
00310     void** outBlock);  // memory block of inSize bytes, or nil
00311     
00312   NS_IMETHOD Free(nsIMdbEnv* ev, // free block allocated earlier by Alloc()
00313     void* inBlock);
00314     
00315   NS_IMETHOD HeapAddStrongRef(nsIMdbEnv* ev); // does nothing
00316   NS_IMETHOD HeapCutStrongRef(nsIMdbEnv* ev); // does nothing
00317 // } ===== end nsIMdbHeap methods =====
00318   
00319 // { ===== begin morkNode interface =====
00320 public: // morkNode virtual methods
00321   virtual void CloseMorkNode(morkEnv* ev); // CloseZone() only if open
00322   virtual ~morkZone(); // assert that CloseMap() executed earlier
00323   
00324 public: // morkMap construction & destruction
00325   morkZone(morkEnv* ev, const morkUsage& inUsage, nsIMdbHeap* ioNodeHeap, 
00326     nsIMdbHeap* ioZoneHeap);
00327   
00328   void CloseZone(morkEnv* ev); // called by CloseMorkNode()
00329   
00330 public: // dynamic type identification
00331   mork_bool IsZone() const
00332   { return IsNode() && mNode_Derived == morkDerived_kZone; }
00333 // } ===== end morkNode methods =====
00334 
00335 // { ===== begin morkZone methods =====
00336 public: // chips do not know how big they are...
00337   void* ZoneNewChip(morkEnv* ev, mdb_size inSize); // alloc  
00338     
00339 public: // ...but runs do indeed know how big they are
00340   void* ZoneNewRun(morkEnv* ev, mdb_size inSize); // alloc  
00341   void  ZoneZapRun(morkEnv* ev, void* ioRunBody); // free
00342   void* ZoneGrowRun(morkEnv* ev, void* ioRunBody, mdb_size inSize); // realloc
00343     
00344 // } ===== end morkZone methods =====
00345 
00346 public: // typing & errors
00347   static void NonZoneTypeError(morkEnv* ev);
00348   static void NilZoneHeapError(morkEnv* ev);
00349   static void BadZoneTagError(morkEnv* ev);
00350 };
00351 
00352 //3456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789
00353 
00354 #endif /* _MORKZONE_ */