src/Spaces.h
author David Anderson <dvander@alliedmods.net>
Sun Jan 06 13:52:21 2013 -0800 (2013-01-06)
changeset 256 3c184218462d
parent 91 5f4402180204
child 262 c4b1341297e5
permissions -rw-r--r--
Initial implementation of module imports.
[email protected]
     1
/* vim: set ts=4 sw=4 tw=99 et:
[email protected]
     2
 *
[email protected]
     3
 * Copyright (C) 2012 David Anderson
[email protected]
     4
 *
[email protected]
     5
 * This file is part of JITCraft.
[email protected]
     6
 *
[email protected]
     7
 * JITCraft is free software: you can redistribute it and/or modify it under
[email protected]
     8
 * the terms of the GNU General Public License as published by the Free
[email protected]
     9
 * Software Foundation, either version 3 of the License, or (at your option)
[email protected]
    10
 * any later version.
[email protected]
    11
 * 
[email protected]
    12
 * Foobar is distributed in the hope that it will be useful, but WITHOUT ANY
[email protected]
    13
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
[email protected]
    14
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
[email protected]
    15
 *
[email protected]
    16
 * You should have received a copy of the GNU General Public License along with
[email protected]
    17
 * JITCraft. If not, see http://www.gnu.org/licenses/.
[email protected]
    18
 */
[email protected]
    19
#ifndef _include_jitcraft_spaces_h_
[email protected]
    20
#define _include_jitcraft_spaces_h_
[email protected]
    21
[email protected]
    22
#include <limits.h>
[email protected]
    23
#include "Utility.h"
[email protected]
    24
#include "Platform.h"
[email protected]
    25
[email protected]
    26
namespace ke {
[email protected]
    27
[email protected]
    28
class Zone;
[email protected]
    29
class Object;
[email protected]
    30
class Map;
[email protected]
    31
[email protected]
    32
static const size_t kObjectAlignment = sizeof(Object *);
[email protected]
    33
static const size_t kMinObjectSize   = sizeof(Object *) * 2;
[email protected]
    34
[email protected]
    35
// Every object gets two successive mark bits. These bits represent various
[email protected]
    36
// states during garbage collection:
[email protected]
    37
//
[email protected]
    38
//  WHITE (00): The object is dead or unmarked.
[email protected]
    39
//  GREY  (11): The object is live but its children have not been marked.
[email protected]
    40
//  BLACK (10): The object and all its children have been marked.
[email protected]
    41
//
[email protected]
    42
// These colors assist in maintaining the "tri-color invariant", explained
[email protected]
    43
// in Heap.h. The bits are organized such that transitioning an object from
[email protected]
    44
// White to Black requires one bit change, and Black to Grey requires another.
[email protected]
    45
class MarkBit
[email protected]
    46
{
[email protected]
    47
    uint32 *word_;
[email protected]
    48
    uint32 bit_;
[email protected]
    49
[email protected]
    50
  public:
[email protected]
    51
    MarkBit(uint32 *word, uint32 bit)
[email protected]
    52
      : word_(word),
[email protected]
    53
        bit_(bit)
[email protected]
    54
    {
[email protected]
    55
        assert(bit_ < sizeof(*word_) * 8);
[email protected]
    56
    }
[email protected]
    57
[email protected]
    58
    bool isSet() const {
[email protected]
    59
        return !!(*word_ & (1 << bit_));
[email protected]
    60
    }
[email protected]
    61
    void set() {
[email protected]
    62
        *word_ |= (1 << bit_);
[email protected]
    63
    }
[email protected]
    64
    void unset() {
[email protected]
    65
        *word_ &= ~(1 << bit_);
[email protected]
    66
    }
[email protected]
    67
    uint32 *word() {
[email protected]
    68
        return word_;
[email protected]
    69
    }
[email protected]
    70
    MarkBit next() const {
[email protected]
    71
        if (bit_ == (sizeof(*word_) * 8) - 1)
[email protected]
    72
            return MarkBit(word_ + 1, 0);
[email protected]
    73
        return MarkBit(word_, bit_ + 1);
[email protected]
    74
    }
[email protected]
    75
};
[email protected]
    76
[email protected]
    77
class HeapChunk
[email protected]
    78
{
[email protected]
    79
    HeapChunk *next_;
[email protected]
    80
[email protected]
    81
    // Base address, from OS::AlignableMapping.
[email protected]
    82
    Address base_;
[email protected]
    83
[email protected]
    84
    // End of the allocated region.
[email protected]
    85
    Address end_;
[email protected]
    86
[email protected]
    87
    uintptr_t flags_;
[email protected]
    88
[email protected]
    89
  public:
[email protected]
    90
    enum Flag {
[email protected]
    91
        HAS_OVERFLOWED_OBJECT = (1 << 0),
[email protected]
    92
        EMPTY = (1 << 1)
[email protected]
    93
    };
[email protected]
    94
[email protected]
    95
  public:
[email protected]
    96
    static const size_t kDefaultSize = 1 * kMB;
[email protected]
    97
    static const size_t kAlignment = 1 * kMB;
[email protected]
    98
[email protected]
    99
    // Maximum size of an object that will fit in a page. We limit this
[email protected]
   100
    // specifically to help JITs: the computation of a[i] has a special
[email protected]
   101
    // instruction form on most CPUs, but the index might not be sign-
[email protected]
   102
    // extended on 64-bit architectures. We limit the size such that:
[email protected]
   103
    //
[email protected]
   104
    //    index * sizeof(Object *)
[email protected]
   105
    //
[email protected]
   106
    // Is guaranteed to not overflow a signed 32-bit integer.
[email protected]
   107
    static const size_t kMaxObjectSize = INT_MAX / sizeof(Object *);
[email protected]
   108
[email protected]
   109
    // Size of a HeapChunk header.
[email protected]
   110
    static const size_t kHeaderSize =
[email protected]
   111
        sizeof(HeapChunk *) +
[email protected]
   112
        sizeof(Address) +
[email protected]
   113
        sizeof(Address) +
[email protected]
   114
        sizeof(Address);
[email protected]
   115
[email protected]
   116
    // All objects must be allocated in the first kAlignment bytes of the
[email protected]
   117
    // chunk. We need two mark bits for every allocatable object, since there
[email protected]
   118
    // are three possible states: White (00), Black (11), and Grey (10). These
[email protected]
   119
    // bits are stored immediately after the HeapChunk header, and before the
[email protected]
   120
    // first allocatable object.
[email protected]
   121
    //
[email protected]
   122
    // Although object alignment is only at word boundaries, we guarantee that
[email protected]
   123
    // every object is at least two words. This means we don't need to reserve
[email protected]
   124
    // two mark bits for every object, just one mark bit for every allocatable
[email protected]
   125
    // address. That also means a pair of mark bits can cross a byte boundary.
[email protected]
   126
    //
[email protected]
   127
    // --- Math ---
[email protected]
   128
    //
[email protected]
   129
    // The number of mark bits needed is:
[email protected]
   130
    //
[email protected]
   131
    // MaxObjectsPerChunk = (kAlignment / kObjectAlignment)
[email protected]
   132
    //                    -> 256KB (128KB on 64-bit)
[email protected]
   133
    //
[email protected]
   134
    // The number of bytes needed for these mark bits is:
[email protected]
   135
    //
[email protected]
   136
    // NumMarkBytes       = MaxObjectsPerChunk / 8
[email protected]
   137
    //                    = 32KB (16KB on 64-bit)
[email protected]
   138
    //
[email protected]
   139
    // The number of uint32s needed to store these bytes is:
[email protected]
   140
    //
[email protected]
   141
    // NumMarkWords       = NumMarkBytes / sizeof(uint32)
[email protected]
   142
    //                    = 8KB (4KB on 64-bit)
[email protected]
   143
    //
[email protected]
   144
    static const size_t kMaxObjectsPerChunk = kAlignment / kObjectAlignment;
[email protected]
   145
    static const size_t kMarkBits = kMaxObjectsPerChunk;
[email protected]
   146
    static const size_t kMarkBytes = kMarkBits / 8;
[email protected]
   147
    static const size_t kMarkWords = kMarkBytes / sizeof(uint32);
[email protected]
   148
    static const size_t kMarkBitsPerWord = sizeof(uint32) * 8;
[email protected]
   149
[email protected]
   150
    static const size_t kMarkBitsOffset = kHeaderSize;
[email protected]
   151
    static const size_t kFirstObject = kMarkBitsOffset + kMarkBytes;
[email protected]
   152
[email protected]
   153
    // Threshold for allocating an object in the large object space.
[email protected]
   154
    static const size_t kLargeObjectThreshold = kAlignment - kFirstObject;
[email protected]
   155
[email protected]
   156
    static inline void StaticAsserts() {
[email protected]
   157
        STATIC_ASSERT(kHeaderSize == sizeof(HeapChunk));
[email protected]
   158
        STATIC_ASSERT(IS_ALIGNED(kHeaderSize, kObjectAlignment));
[email protected]
   159
        STATIC_ASSERT(IS_ALIGNED(kFirstObject, kObjectAlignment));
[email protected]
   160
    }
[email protected]
   161
[email protected]
   162
  public:
[email protected]
   163
    static HeapChunk *New(HeapChunk *prev, size_t size);
[email protected]
   164
    static void Destroy(HeapChunk *chunk);
[email protected]
   165
[email protected]
   166
  public:
[email protected]
   167
    HeapChunk *next() {
[email protected]
   168
        return next_;
[email protected]
   169
    }
[email protected]
   170
    Address base() {
[email protected]
   171
        return base_;
[email protected]
   172
    }
[email protected]
   173
    Address address() {
[email protected]
   174
        return reinterpret_cast<Address>(this);
[email protected]
   175
    }
[email protected]
   176
    Address end() {
[email protected]
   177
        return end_;
[email protected]
   178
    }
[email protected]
   179
    size_t size() {
[email protected]
   180
        return end() - base();
[email protected]
   181
    }
[email protected]
   182
    Address first() {
[email protected]
   183
        return reinterpret_cast<Address>(this) + kFirstObject;
[email protected]
   184
    }
[email protected]
   185
    HeapChunk **nextp() {
[email protected]
   186
        return &next_;
[email protected]
   187
    }
[email protected]
   188
    uint32 *markBits() {
[email protected]
   189
        return reinterpret_cast<uint32 *>(reinterpret_cast<Address>(this) + kMarkBitsOffset);
[email protected]
   190
    }
[email protected]
   191
    void resetMarkBits();
[email protected]
   192
[email protected]
   193
    // Marking functions.
[email protected]
   194
    static inline MarkBit GetMarkBit(Object *obj) {
[email protected]
   195
        uintptr_t address = reinterpret_cast<uintptr_t>(obj);
[email protected]
   196
[email protected]
   197
        HeapChunk *chunk = reinterpret_cast<HeapChunk *>(address & ~(kAlignment - 1));
[email protected]
   198
        assert(Address(obj) >= chunk->first() && Address(obj) < chunk->end());
[email protected]
   199
[email protected]
   200
        size_t index = (address & (kAlignment - 1)) / kObjectAlignment;
[email protected]
   201
        assert(index < kMaxObjectsPerChunk);
[email protected]
   202
[email protected]
   203
        uint32 *word = chunk->markBits() + (index / kMarkBitsPerWord);
[email protected]
   204
        uint32 bit = index & (kMarkBitsPerWord - 1);
[email protected]
   205
        return MarkBit(word, bit);
[email protected]
   206
    }
[email protected]
   207
    static inline Address FromMarkBit(HeapChunk *chunk, uint32 *word, uint32 bit) {
[email protected]
   208
        // word = bits + (index / kMarkBitsPerWord)
[email protected]
   209
        // word - bits = index / kMarkBitsPerWord
[email protected]
   210
        // (word - bits) * kMarkBitsPerWord = index
[email protected]
   211
        assert(word >= chunk->markBits() && word < chunk->markBits() + kMarkWords);
[email protected]
   212
        size_t index = ((word - chunk->markBits()) * kMarkBitsPerWord) + bit;
[email protected]
   213
        return chunk->address() + (index * kObjectAlignment);
[email protected]
   214
    }
[email protected]
   215
    static inline bool IsWhite(const MarkBit &bit) {
[email protected]
   216
        assert(bit.isSet() || !bit.next().isSet());
[email protected]
   217
        return !bit.isSet();
[email protected]
   218
    }
[email protected]
   219
    static inline bool IsBlack(const MarkBit &bit) {
[email protected]
   220
        return bit.isSet() && !bit.next().isSet();
[email protected]
   221
    }
[email protected]
   222
    static inline bool IsGrey(const MarkBit &bit) {
[email protected]
   223
        return bit.isSet() && bit.next().isSet();
[email protected]
   224
    }
[email protected]
   225
    static inline bool IsBlackOrGrey(const MarkBit &bit) {
[email protected]
   226
        return bit.isSet();
[email protected]
   227
    }
[email protected]
   228
    static inline void WhiteToBlack(MarkBit &bit) {
[email protected]
   229
        assert(IsWhite(bit));
[email protected]
   230
        bit.set();
[email protected]
   231
    }
[email protected]
   232
    static inline void BlackToGrey(MarkBit &bit) {
[email protected]
   233
        assert(IsBlack(bit));
[email protected]
   234
        bit.next().set();
[email protected]
   235
    }
[email protected]
   236
    static inline void GreyToBlack(MarkBit &bit) {
[email protected]
   237
        assert(IsGrey(bit));
[email protected]
   238
        bit.next().unset();
[email protected]
   239
    }
[email protected]
   240
    static inline void Clear(MarkBit &bit) {
[email protected]
   241
        bit.unset();
[email protected]
   242
        bit.next().unset();
[email protected]
   243
    }
[email protected]
   244
[email protected]
   245
    bool hasOverflowedObject() {
[email protected]
   246
        return !!(flags_ & HAS_OVERFLOWED_OBJECT);
[email protected]
   247
    }
[email protected]
   248
    void setHasOverflowedObject() {
[email protected]
   249
        flags_ |= HAS_OVERFLOWED_OBJECT;
[email protected]
   250
    }
[email protected]
   251
    bool isEmpty() {
[email protected]
   252
        return !!(flags_ & EMPTY);
[email protected]
   253
    }
[email protected]
   254
    void setEmpty() {
[email protected]
   255
        flags_ |= EMPTY;
[email protected]
   256
    }
[email protected]
   257
};
[email protected]
   258
[email protected]
   259
template <typename SizeEvaluator>
[email protected]
   260
class ChunkObjectIteratorBase
[email protected]
   261
{
[email protected]
   262
    HeapChunk *chunk_;
[email protected]
   263
    Address top_;
[email protected]
   264
    SizeEvaluator evaluator_;
[email protected]
   265
    Address current_;
[email protected]
   266
[email protected]
   267
  public:
[email protected]
   268
    ChunkObjectIteratorBase(HeapChunk *start, Address top, const SizeEvaluator &evaluator)
[email protected]
   269
      : chunk_(start),
[email protected]
   270
        top_(top),
[email protected]
   271
        evaluator_(evaluator),
[email protected]
   272
        current_(start ? start->first() : NULL)
[email protected]
   273
    {
[email protected]
   274
    }
[email protected]
   275
[email protected]
   276
    Object *next();
[email protected]
   277
};
[email protected]
   278
[email protected]
   279
class FreedObject
[email protected]
   280
{
[email protected]
   281
    Map *map_;
[email protected]
   282
    size_t bytes_;
[email protected]
   283
    FreedObject *next_;
[email protected]
   284
[email protected]
   285
  public:
[email protected]
   286
    FreedObject(Map *map, size_t bytes)
[email protected]
   287
      : map_(map),
[email protected]
   288
        bytes_(bytes)
[email protected]
   289
    {
[email protected]
   290
        assert(bytes_ >= sizeof(Map *) + sizeof(size_t));
[email protected]
   291
        if (bytes_ >= sizeof(FreedObject))
[email protected]
   292
            next_ = NULL;
[email protected]
   293
    }
[email protected]
   294
[email protected]
   295
    void setNext(FreedObject *obj) {
[email protected]
   296
        assert(bytes_ >= sizeof(FreedObject));
[email protected]
   297
        next_ = obj;
[email protected]
   298
    }
[email protected]
   299
    FreedObject *next() {
[email protected]
   300
        assert(bytes_ >= sizeof(FreedObject));
[email protected]
   301
        return next_;
[email protected]
   302
    }
[email protected]
   303
    size_t size() {
[email protected]
   304
        return bytes_;
[email protected]
   305
    }
[email protected]
   306
};
[email protected]
   307
[email protected]
   308
// Free-region list used in old spaces. Based on V8's. Each object pool
[email protected]
   309
// is used to allocate objects of the previous pool's size. For example,
[email protected]
   310
// the medium object pool is used to allocate small objects.
[email protected]
   311
class FreeList
[email protected]
   312
{
[email protected]
   313
  private:
[email protected]
   314
    static const size_t kMinObjectSize = 32;
[email protected]
   315
    static const size_t kMaxSmallObject = 255;
[email protected]
   316
    static const size_t kMaxMediumObject = (2 * kKB) - 1;
[email protected]
   317
    static const size_t kMaxLargeObject = (16 * kKB) - 1;
[email protected]
   318
[email protected]
   319
  public:
[email protected]
   320
    FreeList();
[email protected]
   321
[email protected]
   322
  public:
[email protected]
   323
    void add(FreedObject *obj);
[email protected]
   324
    FreedObject *pick(size_t size);
[email protected]
   325
    void reset();
[email protected]
   326
[email protected]
   327
  private:
[email protected]
   328
    FreedObject *small_objects_;
[email protected]
   329
    FreedObject *medium_objects_;
[email protected]
   330
    FreedObject *large_objects_;
[email protected]
   331
    FreedObject *huge_objects_;
[email protected]
   332
};
[email protected]
   333
[email protected]
   334
// The heap stack is designed for structures which are known to not escape the
[email protected]
   335
// program stack, and can thus be quickly allocated in a LIFO manner.
[email protected]
   336
// 
[email protected]
   337
class HeapStack
[email protected]
   338
{
[email protected]
   339
    OS::AlignableMapping map_;
[email protected]
   340
    HeapChunk *chunk_;
[email protected]
   341
    Address cursor_;
[email protected]
   342
    uintptr_t mask_;
[email protected]
   343
[email protected]
   344
  private:
[email protected]
   345
    static const size_t kStackSize = 1024 * 1024;
[email protected]
   346
[email protected]
   347
  public:
[email protected]
   348
    HeapStack();
[email protected]
   349
    ~HeapStack();
[email protected]
   350
    bool initialize();
[email protected]
   351
[email protected]
   352
  public:
[email protected]
   353
    Address position() const {
[email protected]
   354
        return cursor_;
[email protected]
   355
    }
[email protected]
   356
    inline Address allocate(size_t nbytes);
[email protected]
   357
    inline void unwind(Address to);
[email protected]
   358
[email protected]
   359
    inline bool contains(Object *obj) {
[email protected]
   360
        return (reinterpret_cast<uintptr_t>(obj) & mask_) == reinterpret_cast<uintptr_t>(chunk_);
[email protected]
   361
    }
[email protected]
   362
[email protected]
   363
    template <typename Evaluator>
[email protected]
   364
    ChunkObjectIteratorBase<Evaluator> begin(const Evaluator &evaluator) {
[email protected]
   365
        return ChunkObjectIteratorBase<Evaluator>(chunk_, cursor_, evaluator);
[email protected]
   366
    }
[email protected]
   367
};
[email protected]
   368
[email protected]
   369
class OldSpace
[email protected]
   370
{
[email protected]
   371
    Zone *zone_;
[email protected]
   372
    HeapChunk *first_;
[email protected]
   373
    HeapChunk *last_;
[email protected]
   374
    Address cursor_;
[email protected]
   375
    FreeList freelist_;
[email protected]
   376
[email protected]
   377
  public:
[email protected]
   378
    OldSpace(Zone *zone);
[email protected]
   379
    ~OldSpace();
[email protected]
   380
[email protected]
   381
    bool initialize();
[email protected]
   382
[email protected]
   383
  public:
[email protected]
   384
    inline Address allocate(size_t nbytes);
[email protected]
   385
    Address allocateSlow(size_t nbytes);
[email protected]
   386
    void markRegionFree(Address start, size_t size);
[email protected]
   387
    void freeUnusedPages();
[email protected]
   388
[email protected]
   389
    template <typename Evaluator>
[email protected]
   390
    ChunkObjectIteratorBase<Evaluator> begin(const Evaluator &evaluator) {
[email protected]
   391
        return ChunkObjectIteratorBase<Evaluator>(first_, cursor_, evaluator);
[email protected]
   392
    }
[email protected]
   393
[email protected]
   394
    HeapChunk *first() {
[email protected]
   395
        return first_;
[email protected]
   396
    }
[email protected]
   397
    void resetFreeList();
[email protected]
   398
};
[email protected]
   399
[email protected]
   400
class LargeObjectSpace
[email protected]
   401
{
[email protected]
   402
    HeapChunk *first_;
[email protected]
   403
    HeapChunk *last_;
[email protected]
   404
dvand[email protected]
   405
  public:
[email protected]
   406
    LargeObjectSpace();
[email protected]
   407
    ~LargeObjectSpace();
[email protected]
   408
[email protected]
   409
    bool initialize();
[email protected]
   410
[email protected]
   411
  public:
[email protected]
   412
    Address allocate(size_t nbytes);
[email protected]
   413
[email protected]
   414
    HeapChunk *first() {
[email protected]
   415
        return first_;
[email protected]
   416
    }
[email protected]
   417
    void sweep();
[email protected]
   418
};
[email protected]
   419
[email protected]
   420
}
[email protected]
   421
[email protected]
   422
#endif // _include_jitcraft_spaces_h_