1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/gc_implementation/concurrentMarkSweep/freeBlockDictionary.hpp Sat Dec 01 00:00:00 2007 +0000
1.3 @@ -0,0 +1,171 @@
1.4 +/*
1.5 + * Copyright 2001-2005 Sun Microsystems, Inc. All Rights Reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
1.23 + * CA 95054 USA or visit www.sun.com if you need additional information or
1.24 + * have any questions.
1.25 + *
1.26 + */
1.27 +
1.28 +//
1.29 +// Free block maintenance for Concurrent Mark Sweep Generation
1.30 +//
1.31 +// The main data structure for free blocks are
1.32 +// . an indexed array of small free blocks, and
1.33 +// . a dictionary of large free blocks
1.34 +//
1.35 +
1.36 +// No virtuals in FreeChunk (don't want any vtables).
1.37 +
1.38 +// A FreeChunk is merely a chunk that can be in a doubly linked list
1.39 +// and has a size field. NOTE: FreeChunks are distinguished from allocated
1.40 +// objects in two ways (by the sweeper). The second word (prev) has the
1.41 +// LSB set to indicate a free chunk; allocated objects' klass() pointers
1.42 +// don't have their LSB set. The corresponding bit in the CMSBitMap is
1.43 +// set when the chunk is allocated. There are also blocks that "look free"
1.44 +// but are not part of the free list and should not be coalesced into larger
1.45 +// free blocks. These free blocks have their two LSB's set.
1.46 +
1.47 +class FreeChunk VALUE_OBJ_CLASS_SPEC {
1.48 + friend class VMStructs;
1.49 + FreeChunk* _next;
1.50 + FreeChunk* _prev;
1.51 + size_t _size;
1.52 +
1.53 + public:
1.54 + NOT_PRODUCT(static const size_t header_size();)
1.55 + // Returns "true" if the "wrd", which is required to be the second word
1.56 + // of a block, indicates that the block represents a free chunk.
1.57 + static bool secondWordIndicatesFreeChunk(intptr_t wrd) {
1.58 + return (wrd & 0x1) == 0x1;
1.59 + }
1.60 + bool isFree() const {
1.61 + return secondWordIndicatesFreeChunk((intptr_t)_prev);
1.62 + }
1.63 + bool cantCoalesce() const { return (((intptr_t)_prev) & 0x3) == 0x3; }
1.64 + FreeChunk* next() const { return _next; }
1.65 + FreeChunk* prev() const { return (FreeChunk*)(((intptr_t)_prev) & ~(0x3)); }
1.66 + debug_only(void* prev_addr() const { return (void*)&_prev; })
1.67 +
1.68 + void linkAfter(FreeChunk* ptr) {
1.69 + linkNext(ptr);
1.70 + if (ptr != NULL) ptr->linkPrev(this);
1.71 + }
1.72 + void linkAfterNonNull(FreeChunk* ptr) {
1.73 + assert(ptr != NULL, "precondition violation");
1.74 + linkNext(ptr);
1.75 + ptr->linkPrev(this);
1.76 + }
1.77 + void linkNext(FreeChunk* ptr) { _next = ptr; }
1.78 + void linkPrev(FreeChunk* ptr) { _prev = (FreeChunk*)((intptr_t)ptr | 0x1); }
1.79 + void clearPrev() { _prev = NULL; }
1.80 + void clearNext() { _next = NULL; }
1.81 + void dontCoalesce() {
1.82 + // the block should be free
1.83 + assert(isFree(), "Should look like a free block");
1.84 + _prev = (FreeChunk*)(((intptr_t)_prev) | 0x2);
1.85 + }
1.86 + void markFree() { _prev = (FreeChunk*)((intptr_t)_prev | 0x1); }
1.87 + void markNotFree() { _prev = NULL; }
1.88 +
1.89 + size_t size() const { return _size; }
1.90 + void setSize(size_t size) { _size = size; }
1.91 +
1.92 + // For volatile reads:
1.93 + size_t* size_addr() { return &_size; }
1.94 +
1.95 + // Return the address past the end of this chunk
1.96 + HeapWord* end() const { return ((HeapWord*) this) + _size; }
1.97 +
1.98 + // debugging
1.99 + void verify() const PRODUCT_RETURN;
1.100 + void verifyList() const PRODUCT_RETURN;
1.101 + void mangleAllocated(size_t size) PRODUCT_RETURN;
1.102 + void mangleFreed(size_t size) PRODUCT_RETURN;
1.103 +};
1.104 +
1.105 +// Alignment helpers etc.
1.106 +#define numQuanta(x,y) ((x+y-1)/y)
1.107 +enum AlignmentConstants {
1.108 + MinChunkSize = numQuanta(sizeof(FreeChunk), MinObjAlignmentInBytes) * MinObjAlignment
1.109 +};
1.110 +
1.111 +// A FreeBlockDictionary is an abstract superclass that will allow
1.112 +// a number of alternative implementations in the future.
1.113 +class FreeBlockDictionary: public CHeapObj {
1.114 + public:
1.115 + enum Dither {
1.116 + atLeast,
1.117 + exactly,
1.118 + roughly
1.119 + };
1.120 + enum DictionaryChoice {
1.121 + dictionaryBinaryTree = 0,
1.122 + dictionarySplayTree = 1,
1.123 + dictionarySkipList = 2
1.124 + };
1.125 +
1.126 + private:
1.127 + NOT_PRODUCT(Mutex* _lock;)
1.128 +
1.129 + public:
1.130 + virtual void removeChunk(FreeChunk* fc) = 0;
1.131 + virtual FreeChunk* getChunk(size_t size, Dither dither = atLeast) = 0;
1.132 + virtual void returnChunk(FreeChunk* chunk) = 0;
1.133 + virtual size_t totalChunkSize(debug_only(const Mutex* lock)) const = 0;
1.134 + virtual size_t maxChunkSize() const = 0;
1.135 + virtual size_t minSize() const = 0;
1.136 + // Reset the dictionary to the initial conditions for a single
1.137 + // block.
1.138 + virtual void reset(HeapWord* addr, size_t size) = 0;
1.139 + virtual void reset() = 0;
1.140 +
1.141 + virtual void dictCensusUpdate(size_t size, bool split, bool birth) = 0;
1.142 + virtual bool coalDictOverPopulated(size_t size) = 0;
1.143 + virtual void beginSweepDictCensus(double coalSurplusPercent,
1.144 + float sweep_current, float sweep_ewstimate) = 0;
1.145 + virtual void endSweepDictCensus(double splitSurplusPercent) = 0;
1.146 + virtual FreeChunk* findLargestDict() const = 0;
1.147 + // verify that the given chunk is in the dictionary.
1.148 + virtual bool verifyChunkInFreeLists(FreeChunk* tc) const = 0;
1.149 +
1.150 + // Sigma_{all_free_blocks} (block_size^2)
1.151 + virtual double sum_of_squared_block_sizes() const = 0;
1.152 +
1.153 + virtual FreeChunk* find_chunk_ends_at(HeapWord* target) const = 0;
1.154 + virtual void inc_totalSize(size_t v) = 0;
1.155 + virtual void dec_totalSize(size_t v) = 0;
1.156 +
1.157 + NOT_PRODUCT (
1.158 + virtual size_t sumDictReturnedBytes() = 0;
1.159 + virtual void initializeDictReturnedBytes() = 0;
1.160 + virtual size_t totalCount() = 0;
1.161 + )
1.162 +
1.163 + virtual void reportStatistics() const {
1.164 + gclog_or_tty->print("No statistics available");
1.165 + }
1.166 +
1.167 + virtual void printDictCensus() const = 0;
1.168 +
1.169 + virtual void verify() const = 0;
1.170 +
1.171 + Mutex* par_lock() const PRODUCT_RETURN0;
1.172 + void set_par_lock(Mutex* lock) PRODUCT_RETURN;
1.173 + void verify_par_locked() const PRODUCT_RETURN;
1.174 +};
