db/mork/src/morkZone.h

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-  */
   2 /* ***** BEGIN LICENSE BLOCK *****
   3  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   4  *
   5  * The contents of this file are subject to the Mozilla Public License Version
   6  * 1.1 (the "License"); you may not use this file except in compliance with
   7  * the License. You may obtain a copy of the License at
   8  * http://www.mozilla.org/MPL/
   9  *
  10  * Software distributed under the License is distributed on an "AS IS" basis,
  11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12  * for the specific language governing rights and limitations under the
  13  * License.
  14  *
  15  * The Original Code is mozilla.org code.
  16  *
  17  * The Initial Developer of the Original Code is
  18  * Netscape Communications Corporation.
  19  * Portions created by the Initial Developer are Copyright (C) 1999
  20  * the Initial Developer. All Rights Reserved.
  21  *
  22  * Contributor(s):
  23  *
  24  * Alternatively, the contents of this file may be used under the terms of
  25  * either of the GNU General Public License Version 2 or later (the "GPL"),
  26  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  27  * in which case the provisions of the GPL or the LGPL are applicable instead
  28  * of those above. If you wish to allow use of your version of this file only
  29  * under the terms of either the GPL or the LGPL, and not to allow others to
  30  * use your version of this file under the terms of the MPL, indicate your
  31  * decision by deleting the provisions above and replace them with the notice
  32  * and other provisions required by the GPL or the LGPL. If you do not delete
  33  * the provisions above, a recipient may use your version of this file under
  34  * the terms of any one of the MPL, the GPL or the LGPL.
  35  *
  36  * ***** END LICENSE BLOCK ***** */
  37
  38 #ifndef _MORKZONE_
  39 #define _MORKZONE_ 1
  40
  41 #ifndef _MORK_
  42 #include "mork.h"
  43 #endif
  44
  45 #ifndef _MORKNODE_
  46 #include "morkNode.h"
  47 #endif
  48
  49 #ifndef _MORKDEQUE_
  50 #include "morkDeque.h"
  51 #endif
  52
  53 //3456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789
  54
  55 /*| CONFIG_DEBUG: do paranoid debug checks if defined.
  56 |*/
  57 #ifdef MORK_DEBUG
  58 #define morkZone_CONFIG_DEBUG 1 /* debug paranoid if defined */
  59 #endif /*MORK_DEBUG*/
  60
  61 /*| CONFIG_STATS: keep volume and usage statistics.
  62 |*/
  63 #define morkZone_CONFIG_VOL_STATS 1 /* count space used by zone instance */
  64
  65 /*| CONFIG_ARENA: if this is defined, then the morkZone class will alloc big
  66 **| blocks from the zone's heap, and suballocate from these.  If undefined,
  67 **| then morkZone will just pass all calls through to the zone's heap.
  68 |*/
  69 #ifdef MORK_ENABLE_ZONE_ARENAS
  70 #define morkZone_CONFIG_ARENA 1 /* be arena, if defined; otherwise no-op */
  71 #endif /*MORK_ENABLE_ZONE_ARENAS*/
  72
  73 /*| CONFIG_ALIGN_8: if this is defined, then the morkZone class will give
  74 **| blocks 8 byte alignment instead of only 4 byte alignment.
  75 |*/
  76 #ifdef MORK_CONFIG_ALIGN_8
  77 #define morkZone_CONFIG_ALIGN_8 1 /* ifdef: align to 8 bytes, otherwise 4 */
  78 #endif /*MORK_CONFIG_ALIGN_8*/
  79
  80 /*| CONFIG_PTR_SIZE_4: if this is defined, then the morkZone class will
  81 **| assume sizeof(void*) == 4, so a tag slot for padding is needed.
  82 |*/
  83 #ifdef MORK_CONFIG_PTR_SIZE_4
  84 #define morkZone_CONFIG_PTR_SIZE_4 1 /* ifdef: sizeof(void*) == 4 */
  85 #endif /*MORK_CONFIG_PTR_SIZE_4*/
  86
  87 /*| morkZone_USE_TAG_SLOT: if this is defined, then define slot mRun_Tag
  88 **| in order to achieve eight byte alignment after the mRun_Next slot.
  89 |*/
  90 #if defined(morkZone_CONFIG_ALIGN_8) && defined(morkZone_CONFIG_PTR_SIZE_4)
  91 #define morkRun_USE_TAG_SLOT 1  /* need mRun_Tag slot inside morkRun */
  92 #define morkHunk_USE_TAG_SLOT 1 /* need mHunk_Tag slot inside morkHunk */
  93 #endif
  94
  95 //3456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789
  96
  97 #define morkRun_kTag ((mork_u4) 0x6D52754E ) /* ascii 'mRuN' */
  98
  99 /*| morkRun: structure used by morkZone for sized blocks
 100 |*/
 101 class morkRun {
 102
 103 protected: // member variable slots
 104 #ifdef morkRun_USE_TAG_SLOT
 105   mork_u4   mRun_Tag; // force 8 byte alignment after mRun_Next
 106 #endif /* morkRun_USE_TAG_SLOT */
 107
 108   morkRun*  mRun_Next;
 109
 110 public: // pointer interpretation of mRun_Next (when inside a list):
 111   morkRun*   RunNext() const { return mRun_Next; }
 112   void       RunSetNext(morkRun* ioNext) { mRun_Next = ioNext; }
 113
 114 public: // size interpretation of mRun_Next (when not inside a list):
 115   mork_size  RunSize() const { return (mork_size) ((mork_ip) mRun_Next); }
 116   void       RunSetSize(mork_size inSize)
 117              { mRun_Next = (morkRun*) ((mork_ip) inSize); }
 118
 119 public: // maintenance and testing of optional tag magic signature slot:
 120 #ifdef morkRun_USE_TAG_SLOT
 121   void       RunInitTag() { mRun_Tag = morkRun_kTag; }
 122   mork_bool  RunGoodTag() { return ( mRun_Tag == morkRun_kTag ); }
 123 #endif /* morkRun_USE_TAG_SLOT */
 124
 125 public: // conversion back and forth to inline block following run instance:
 126   void* RunAsBlock() { return (((mork_u1*) this) + sizeof(morkRun)); }
 127
 128   static morkRun* BlockAsRun(void* ioBlock)
 129   { return (morkRun*) (((mork_u1*) ioBlock) - sizeof(morkRun)); }
 130
 131 public: // typing & errors
 132   static void BadRunTagError(morkEnv* ev);
 133   static void RunSizeAlignError(morkEnv* ev);
 134 };
 135
 136 //3456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789
 137
 138
 139 /*| morkOldRun: more space to record size when run is put into old free list
 140 |*/
 141 class morkOldRun : public morkRun {
 142
 143 protected: // need another size field when mRun_Next is used for linkage:
 144   mdb_size mOldRun_Size;
 145
 146 public: // size getter/setter
 147   mork_size  OldSize() const { return mOldRun_Size; }
 148   void       OldSetSize(mork_size inSize) { mOldRun_Size = inSize; }
 149
 150 };
 151
 152 //3456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789
 153
 154 #define morkHunk_kTag ((mork_u4) 0x68556E4B ) /* ascii 'hUnK' */
 155
 156 /*| morkHunk: structure used by morkZone for heap allocations.
 157 |*/
 158 class morkHunk {
 159
 160 protected: // member variable slots
 161
 162 #ifdef morkHunk_USE_TAG_SLOT
 163   mork_u4   mHunk_Tag; // force 8 byte alignment after mHunk_Next
 164 #endif /* morkHunk_USE_TAG_SLOT */
 165
 166   morkHunk* mHunk_Next;
 167
 168   morkRun   mHunk_Run;
 169
 170 public: // setters
 171   void      HunkSetNext(morkHunk* ioNext) { mHunk_Next = ioNext; }
 172
 173 public: // getters
 174   morkHunk* HunkNext() const { return mHunk_Next; }
 175
 176   morkRun*  HunkRun() { return &mHunk_Run; }
 177
 178 public: // maintenance and testing of optional tag magic signature slot:
 179 #ifdef morkHunk_USE_TAG_SLOT
 180   void       HunkInitTag() { mHunk_Tag = morkHunk_kTag; }
 181   mork_bool  HunkGoodTag() { return ( mHunk_Tag == morkHunk_kTag ); }
 182 #endif /* morkHunk_USE_TAG_SLOT */
 183
 184 public: // typing & errors
 185   static void BadHunkTagWarning(morkEnv* ev);
 186
 187 };
 188
 189 //3456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789
 190
 191 /*| kNewHunkSize: the default size for a hunk, assuming we must allocate
 192 **| a new one whenever the free hunk list does not already have.  Note this
 193 **| number should not be changed without also considering suitable changes
 194 **| in the related kMaxHunkWaste and kMinHunkSize constants.
 195 |*/
 196 #define morkZone_kNewHunkSize ((mork_size) (64 * 1024)) /* 64K per hunk */
 197
 198 /*| kMaxFreeVolume: some number of bytes of free space in the free hunk list
 199 **| over which we no longer want to add more free hunks to the list, for fear
 200 **| of accumulating too much unused, fragmented free space.  This should be a
 201 **| small multiple of kNewHunkSize, say about two to four times as great, to
 202 **| allow for no more free hunk space than fits in a handful of new hunks.
 203 **| This strategy will let us usefuly accumulate "some" free space in the
 204 **| free hunk list, but without accumulating "too much" free space that way.
 205 |*/
 206 #define morkZone_kMaxFreeVolume (morkZone_kNewHunkSize * 3)
 207
 208 /*| kMaxHunkWaste: if a current request is larger than this, and we cannot
 209 **| satisfy the request with the current hunk, then we just allocate the
 210 **| block from the heap without changing the current hunk.  Basically this
 211 **| number represents the largest amount of memory we are willing to waste,
 212 **| since a block request barely less than this can cause the current hunk
 213 **| to be retired (with any unused space wasted) as well get a new hunk.
 214 |*/
 215 #define morkZone_kMaxHunkWaste ((mork_size) 4096) /* 1/16 kNewHunkSize */
 216
 217 /*| kRound*: the algorithm for rounding up allocation sizes for caching
 218 **| in free lists works like the following.  We add kRoundAdd to any size
 219 **| requested, and then bitwise AND with kRoundMask, and this will give us
 220 **| the smallest multiple of kRoundSize that is at least as large as the
 221 **| requested size.  Then if we rightshift this number by kRoundBits, we
 222 **| will have the index into the mZone_FreeRuns array which will hold any
 223 **| cache runs of that size.  So 4 bits of shift gives us a granularity
 224 **| of 16 bytes, so that free lists will hold successive runs that are
 225 **| 16 bytes greater than the next smaller run size.  If we have 256 free
 226 **| lists of nonzero sized runs altogether, then the largest run that can
 227 **| be cached is 4096, or 4K (since 4096 == 16 * 256).  A larger run that
 228 **| gets freed will go in to the free hunk list (or back to the heap).
 229 |*/
 230 #define morkZone_kRoundBits 4 /* bits to round-up size for free lists */
 231 #define morkZone_kRoundSize (1 << morkZone_kRoundBits)
 232 #define morkZone_kRoundAdd ((1 << morkZone_kRoundBits) - 1)
 233 #define morkZone_kRoundMask (~ ((mork_ip) morkZone_kRoundAdd))
 234
 235 #define morkZone_kBuckets 256 /* number of distinct free lists */
 236
 237 /*| kMaxCachedRun: the largest run that will be stored inside a free
 238 **| list of old zapped runs.  A run larger than this cannot be put in
 239 **| a free list, and must be allocated from the heap at need, and put
 240 **| into the free hunk list when discarded.
 241 |*/
 242 #define morkZone_kMaxCachedRun (morkZone_kBuckets * morkZone_kRoundSize)
 243
 244 #define morkDerived_kZone     /*i*/ 0x5A6E /* ascii 'Zn' */
 245
 246 /*| morkZone: a pooled memory allocator like an NSPR arena.  The term 'zone'
 247 **| is roughly synonymous with 'heap'.  I avoid calling this class a "heap"
 248 **| to avoid any confusion with nsIMdbHeap, and I avoid calling this class
 249 **| an arean to avoid confusion with NSPR usage.
 250 |*/
 251 class morkZone : public morkNode, public nsIMdbHeap {
 252
 253 // public: // slots inherited from morkNode (meant to inform only)
 254   // nsIMdbHeap*       mNode_Heap;
 255
 256   // mork_base      mNode_Base;     // must equal morkBase_kNode
 257   // mork_derived   mNode_Derived;  // depends on specific node subclass
 258
 259   // mork_access    mNode_Access;   // kOpen, kClosing, kShut, or kDead
 260   // mork_usage     mNode_Usage;    // kHeap, kStack, kMember, kGlobal, kNone
 261   // mork_able      mNode_Mutable;  // can this node be modified?
 262   // mork_load      mNode_Load;     // is this node clean or dirty?
 263
 264   // mork_uses      mNode_Uses;     // refcount for strong refs
 265   // mork_refs      mNode_Refs;     // refcount for strong refs + weak refs
 266
 267 public: // state is public because the entire Mork system is private
 268
 269   nsIMdbHeap*  mZone_Heap; // strong ref to heap allocating all space
 270
 271   mork_size    mZone_HeapVolume;  // total bytes allocated from heap
 272   mork_size    mZone_BlockVolume; // total bytes in all zone blocks
 273   mork_size    mZone_RunVolume;   // total bytes in all zone runs
 274   mork_size    mZone_ChipVolume;  // total bytes in all zone chips
 275
 276   mork_size    mZone_FreeOldRunVolume; // total bytes in all used hunks
 277
 278   mork_count   mZone_HunkCount;        // total number of used hunks
 279   mork_count   mZone_FreeOldRunCount;  // total free old runs
 280
 281   morkHunk*    mZone_HunkList;       // linked list of all used hunks
 282   morkRun*     mZone_FreeOldRunList; // linked list of free old runs
 283
 284   // note mZone_At is a byte pointer for single byte address arithmetic:
 285   mork_u1*     mZone_At;     // current position in most recent hunk
 286   mork_size    mZone_AtSize; // number of bytes remaining in this hunk
 287
 288   // kBuckets+1 so indexes zero through kBuckets are all okay to use:
 289
 290   morkRun*     mZone_FreeRuns[ morkZone_kBuckets + 1 ];
 291   // Each piece of memory stored in list mZone_FreeRuns[ i ] has an
 292   // allocation size equal to sizeof(morkRun) + (i * kRoundSize), so
 293   // that callers can be given a piece of memory with (i * kRoundSize)
 294   // bytes of writeable space while reserving the first sizeof(morkRun)
 295   // bytes to keep track of size information for later re-use.  Note
 296   // that mZone_FreeRuns[ 0 ] is unused because no run will be zero
 297   // bytes in size (and morkZone plans to complain about zero sizes).
 298
 299 protected: // zone utilities
 300
 301   mork_size zone_grow_at(morkEnv* ev, mork_size inNeededSize);
 302
 303   void*     zone_new_chip(morkEnv* ev, mdb_size inSize); // alloc
 304   morkHunk* zone_new_hunk(morkEnv* ev, mdb_size inRunSize); // alloc
 305
 306 // { ===== begin nsIMdbHeap methods =====
 307 public:
 308   NS_IMETHOD Alloc(nsIMdbEnv* ev, // allocate a piece of memory
 309     mdb_size inSize,   // requested size of new memory block
 310     void** outBlock);  // memory block of inSize bytes, or nil
 311
 312   NS_IMETHOD Free(nsIMdbEnv* ev, // free block allocated earlier by Alloc()
 313     void* inBlock);
 314
 315   NS_IMETHOD HeapAddStrongRef(nsIMdbEnv* ev); // does nothing
 316   NS_IMETHOD HeapCutStrongRef(nsIMdbEnv* ev); // does nothing
 317 // } ===== end nsIMdbHeap methods =====
 318
 319 // { ===== begin morkNode interface =====
 320 public: // morkNode virtual methods
 321   virtual void CloseMorkNode(morkEnv* ev); // CloseZone() only if open
 322   virtual ~morkZone(); // assert that CloseMap() executed earlier
 323
 324 public: // morkMap construction & destruction
 325   morkZone(morkEnv* ev, const morkUsage& inUsage, nsIMdbHeap* ioNodeHeap,
 326     nsIMdbHeap* ioZoneHeap);
 327
 328   void CloseZone(morkEnv* ev); // called by CloseMorkNode()
 329
 330 public: // dynamic type identification
 331   mork_bool IsZone() const
 332   { return IsNode() && mNode_Derived == morkDerived_kZone; }
 333 // } ===== end morkNode methods =====
 334
 335 // { ===== begin morkZone methods =====
 336 public: // chips do not know how big they are...
 337   void* ZoneNewChip(morkEnv* ev, mdb_size inSize); // alloc
 338
 339 public: // ...but runs do indeed know how big they are
 340   void* ZoneNewRun(morkEnv* ev, mdb_size inSize); // alloc
 341   void  ZoneZapRun(morkEnv* ev, void* ioRunBody); // free
 342   void* ZoneGrowRun(morkEnv* ev, void* ioRunBody, mdb_size inSize); // realloc
 343
 344 // } ===== end morkZone methods =====
 345
 346 public: // typing & errors
 347   static void NonZoneTypeError(morkEnv* ev);
 348   static void NilZoneHeapError(morkEnv* ev);
 349   static void BadZoneTagError(morkEnv* ev);
 350 };
 351
 352 //3456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789
 353
 354 #endif /* _MORKZONE_ */