Mercurial > hg > truffle
annotate src/share/vm/libadt/vectset.cpp @ 1716:be3f9c242c9d
6948538: CMS: BOT walkers can fall into object allocation and initialization cracks
Summary: GC workers now recognize an intermediate transient state of blocks which are allocated but have not yet completed initialization. blk_start() calls do not attempt to determine the size of a block in the transient state, rather waiting for the block to become initialized so that it is safe to query its size. Audited and ensured the order of initialization of object fields (klass, free bit and size) to respect block state transition protocol. Also included some new assertion checking code enabled in debug mode.
Reviewed-by: chrisphi, johnc, poonam
| author | ysr |
|---|---|
| date | Mon, 16 Aug 2010 15:58:42 -0700 |
| parents | c18cbe5936b8 |
| children | f95d63e2154a |
| rev | line source |
|---|---|
| 0 | 1 /* |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
2 * Copyright (c) 1997, 2005, Oracle and/or its affiliates. All rights reserved. |
| 0 | 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| 4 * | |
| 5 * This code is free software; you can redistribute it and/or modify it | |
| 6 * under the terms of the GNU General Public License version 2 only, as | |
| 7 * published by the Free Software Foundation. | |
| 8 * | |
| 9 * This code is distributed in the hope that it will be useful, but WITHOUT | |
| 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 12 * version 2 for more details (a copy is included in the LICENSE file that | |
| 13 * accompanied this code). | |
| 14 * | |
| 15 * You should have received a copy of the GNU General Public License version | |
| 16 * 2 along with this work; if not, write to the Free Software Foundation, | |
| 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
| 18 * | |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
21 * questions. |
| 0 | 22 * |
| 23 */ | |
| 24 | |
| 25 // Vector Sets - An Abstract Data Type | |
| 26 | |
| 27 #include "incls/_precompiled.incl" | |
| 28 #include "incls/_vectset.cpp.incl" | |
| 29 | |
| 30 // %%%%% includes not needed with AVM framework - Ungar | |
| 31 // #include "port.hpp" | |
| 32 //IMPLEMENTATION | |
| 33 // #include "vectset.hpp" | |
| 34 | |
| 35 // BitsInByte is a lookup table which tells the number of bits that | |
| 36 // are in the looked-up number. It is very useful in VectorSet_Size. | |
| 37 | |
| 38 uint8 bitsInByte[256] = { | |
| 39 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, | |
| 40 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, | |
| 41 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, | |
| 42 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | |
| 43 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, | |
| 44 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | |
| 45 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | |
| 46 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, | |
| 47 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, | |
| 48 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | |
| 49 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | |
| 50 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, | |
| 51 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | |
| 52 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, | |
| 53 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, | |
| 54 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 | |
| 55 }; | |
| 56 | |
| 57 //------------------------------VectorSet-------------------------------------- | |
| 58 // Create a new, empty Set. | |
| 59 VectorSet::VectorSet(Arena *arena) : Set(arena) { | |
| 60 size = 2; // Small initial size | |
| 61 data = (uint32 *)_set_arena->Amalloc(size*sizeof(uint32)); | |
| 62 data[0] = 0; // No elements | |
| 63 data[1] = 0; | |
| 64 } | |
| 65 | |
| 66 //------------------------------Construct-------------------------------------- | |
| 67 Set &VectorSet_Construct(Arena *arena) | |
| 68 { | |
| 69 return *(new VectorSet(arena)); | |
| 70 } | |
| 71 | |
| 72 //------------------------------operator=-------------------------------------- | |
| 73 Set &VectorSet::operator = (const Set &set) | |
| 74 { | |
| 75 if( &set == this ) return *this; | |
| 76 FREE_FAST(data); | |
| 77 // The cast is a virtual function that checks that "set" is a VectorSet. | |
| 78 slamin(*(set.asVectorSet())); | |
| 79 return *this; | |
| 80 } | |
| 81 | |
| 82 //------------------------------slamin----------------------------------------- | |
| 83 // Initialize one set with another. No regard is made to the existing Set. | |
| 84 void VectorSet::slamin(const VectorSet& s) | |
| 85 { | |
| 86 size = s.size; // Use new size | |
| 87 data = (uint32*)s._set_arena->Amalloc(size*sizeof(uint32)); // Make array of required size | |
| 88 memcpy( data, s.data, size*sizeof(uint32) ); // Fill the array | |
| 89 } | |
| 90 | |
| 91 //------------------------------grow------------------------------------------- | |
| 92 // Expand the existing set to a bigger size | |
| 93 void VectorSet::grow( uint newsize ) | |
| 94 { | |
| 95 newsize = (newsize+31) >> 5; // Convert to longwords | |
| 96 uint x = size; | |
| 97 while( x < newsize ) x <<= 1; | |
| 98 data = (uint32 *)_set_arena->Arealloc(data, size*sizeof(uint32), x*sizeof(uint32)); | |
| 99 memset((char *)(data + size), 0, (x - size)*sizeof(uint32)); | |
| 100 size = x; | |
| 101 } | |
| 102 | |
| 103 //------------------------------operator<<=------------------------------------ | |
| 104 // Insert a member into an existing Set. | |
| 105 Set &VectorSet::operator <<= (uint elem) | |
| 106 { | |
| 107 register uint word = elem >> 5; // Get the longword offset | |
| 108 register uint32 mask = 1L << (elem & 31); // Get bit mask | |
| 109 | |
| 110 if( word >= size ) // Need to grow set? | |
| 111 grow(elem+1); // Then grow it | |
| 112 data[word] |= mask; // Set new bit | |
| 113 return *this; | |
| 114 } | |
| 115 | |
| 116 //------------------------------operator>>=------------------------------------ | |
| 117 // Delete a member from an existing Set. | |
| 118 Set &VectorSet::operator >>= (uint elem) | |
| 119 { | |
| 120 register uint word = elem >> 5; // Get the longword offset | |
| 121 if( word >= size ) // Beyond the last? | |
| 122 return *this; // Then it's clear & return clear | |
| 123 register uint32 mask = 1L << (elem & 31); // Get bit mask | |
| 124 data[word] &= ~mask; // Clear bit | |
| 125 return *this; | |
| 126 } | |
| 127 | |
| 128 //------------------------------operator&=------------------------------------- | |
| 129 // Intersect one set into another. | |
| 130 VectorSet &VectorSet::operator &= (const VectorSet &s) | |
| 131 { | |
| 132 // NOTE: The intersection is never any larger than the smallest set. | |
| 133 if( s.size < size ) size = s.size; // Get smaller size | |
| 134 register uint32 *u1 = data; // Pointer to the destination data | |
| 135 register uint32 *u2 = s.data; // Pointer to the source data | |
| 136 for( uint i=0; i<size; i++) // For data in set | |
| 137 *u1++ &= *u2++; // Copy and AND longwords | |
| 138 return *this; // Return set | |
| 139 } | |
| 140 | |
| 141 //------------------------------operator&=------------------------------------- | |
| 142 Set &VectorSet::operator &= (const Set &set) | |
| 143 { | |
| 144 // The cast is a virtual function that checks that "set" is a VectorSet. | |
| 145 return (*this) &= *(set.asVectorSet()); | |
| 146 } | |
| 147 | |
| 148 //------------------------------operator|=------------------------------------- | |
| 149 // Union one set into another. | |
| 150 VectorSet &VectorSet::operator |= (const VectorSet &s) | |
| 151 { | |
| 152 // This many words must be unioned | |
| 153 register uint cnt = ((size<s.size)?size:s.size); | |
| 154 register uint32 *u1 = data; // Pointer to the destination data | |
| 155 register uint32 *u2 = s.data; // Pointer to the source data | |
| 156 for( uint i=0; i<cnt; i++) // Copy and OR the two sets | |
| 157 *u1++ |= *u2++; | |
| 158 if( size < s.size ) { // Is set 2 larger than set 1? | |
| 159 // Extend result by larger set | |
| 160 grow(s.size*sizeof(uint32)*8); | |
| 161 memcpy(&data[cnt], u2, (s.size - cnt)*sizeof(uint32)); | |
| 162 } | |
| 163 return *this; // Return result set | |
| 164 } | |
| 165 | |
| 166 //------------------------------operator|=------------------------------------- | |
| 167 Set &VectorSet::operator |= (const Set &set) | |
| 168 { | |
| 169 // The cast is a virtual function that checks that "set" is a VectorSet. | |
| 170 return (*this) |= *(set.asVectorSet()); | |
| 171 } | |
| 172 | |
| 173 //------------------------------operator-=------------------------------------- | |
| 174 // Difference one set from another. | |
| 175 VectorSet &VectorSet::operator -= (const VectorSet &s) | |
| 176 { | |
| 177 // This many words must be unioned | |
| 178 register uint cnt = ((size<s.size)?size:s.size); | |
| 179 register uint32 *u1 = data; // Pointer to the destination data | |
| 180 register uint32 *u2 = s.data; // Pointer to the source data | |
| 181 for( uint i=0; i<cnt; i++ ) // For data in set | |
| 182 *u1++ &= ~(*u2++); // A <-- A & ~B with longwords | |
| 183 return *this; // Return new set | |
| 184 } | |
| 185 | |
| 186 //------------------------------operator-=------------------------------------- | |
| 187 Set &VectorSet::operator -= (const Set &set) | |
| 188 { | |
| 189 // The cast is a virtual function that checks that "set" is a VectorSet. | |
| 190 return (*this) -= *(set.asVectorSet()); | |
| 191 } | |
| 192 | |
| 193 //------------------------------compare---------------------------------------- | |
| 194 // Compute 2 booleans: bits in A not B, bits in B not A. | |
| 195 // Return X0 -- A is not a subset of B | |
| 196 // X1 -- A is a subset of B | |
| 197 // 0X -- B is not a subset of A | |
| 198 // 1X -- B is a subset of A | |
| 199 int VectorSet::compare (const VectorSet &s) const | |
| 200 { | |
| 201 register uint32 *u1 = data; // Pointer to the destination data | |
| 202 register uint32 *u2 = s.data; // Pointer to the source data | |
| 203 register uint32 AnotB = 0, BnotA = 0; | |
| 204 // This many words must be unioned | |
| 205 register uint cnt = ((size<s.size)?size:s.size); | |
| 206 | |
| 207 // Get bits for both sets | |
| 208 uint i; // Exit value of loop | |
| 209 for( i=0; i<cnt; i++ ) { // For data in BOTH sets | |
| 210 register uint32 A = *u1++; // Data from one guy | |
| 211 register uint32 B = *u2++; // Data from other guy | |
| 212 AnotB |= (A & ~B); // Compute bits in A not B | |
| 213 BnotA |= (B & ~A); // Compute bits in B not A | |
| 214 } | |
| 215 | |
| 216 // Get bits from bigger set | |
| 217 if( size < s.size ) { | |
| 218 for( ; i<s.size; i++ ) // For data in larger set | |
| 219 BnotA |= *u2++; // These bits are in B not A | |
| 220 } else { | |
| 221 for( ; i<size; i++ ) // For data in larger set | |
| 222 AnotB |= *u1++; // These bits are in A not B | |
| 223 } | |
| 224 | |
| 225 // Set & return boolean flags | |
| 226 return ((!BnotA)<<1) + (!AnotB); | |
| 227 } | |
| 228 | |
| 229 //------------------------------operator==------------------------------------- | |
| 230 // Test for set equality | |
| 231 int VectorSet::operator == (const VectorSet &s) const | |
| 232 { | |
| 233 return compare(s) == 3; // TRUE if A and B are mutual subsets | |
| 234 } | |
| 235 | |
| 236 //------------------------------operator==------------------------------------- | |
| 237 int VectorSet::operator == (const Set &set) const | |
| 238 { | |
| 239 // The cast is a virtual function that checks that "set" is a VectorSet. | |
| 240 return (*this) == *(set.asVectorSet()); | |
| 241 } | |
| 242 | |
| 243 //------------------------------disjoint--------------------------------------- | |
| 244 // Check for sets being disjoint. | |
| 245 int VectorSet::disjoint(const Set &set) const | |
| 246 { | |
| 247 // The cast is a virtual function that checks that "set" is a VectorSet. | |
| 248 const VectorSet &s = *(set.asVectorSet()); | |
| 249 | |
| 250 // NOTE: The intersection is never any larger than the smallest set. | |
| 251 register uint small = ((size<s.size)?size:s.size); | |
| 252 register uint32 *u1 = data; // Pointer to the destination data | |
| 253 register uint32 *u2 = s.data; // Pointer to the source data | |
| 254 for( uint i=0; i<small; i++) // For data in set | |
| 255 if( *u1++ & *u2++ ) // If any elements in common | |
| 256 return 0; // Then not disjoint | |
| 257 return 1; // Else disjoint | |
| 258 } | |
| 259 | |
| 260 //------------------------------operator<-------------------------------------- | |
| 261 // Test for strict subset | |
| 262 int VectorSet::operator < (const VectorSet &s) const | |
| 263 { | |
| 264 return compare(s) == 1; // A subset B, B not subset A | |
| 265 } | |
| 266 | |
| 267 //------------------------------operator<-------------------------------------- | |
| 268 int VectorSet::operator < (const Set &set) const | |
| 269 { | |
| 270 // The cast is a virtual function that checks that "set" is a VectorSet. | |
| 271 return (*this) < *(set.asVectorSet()); | |
| 272 } | |
| 273 | |
| 274 //------------------------------operator<=------------------------------------- | |
| 275 // Test for subset | |
| 276 int VectorSet::operator <= (const VectorSet &s) const | |
| 277 { | |
| 278 return compare(s) & 1; // A subset B | |
| 279 } | |
| 280 | |
| 281 //------------------------------operator<=------------------------------------- | |
| 282 int VectorSet::operator <= (const Set &set) const | |
| 283 { | |
| 284 // The cast is a virtual function that checks that "set" is a VectorSet. | |
| 285 return (*this) <= *(set.asVectorSet()); | |
| 286 } | |
| 287 | |
| 288 //------------------------------operator[]------------------------------------- | |
| 289 // Test for membership. A Zero/Non-Zero value is returned! | |
| 290 int VectorSet::operator[](uint elem) const | |
| 291 { | |
| 292 register uint word = elem >> 5; // Get the longword offset | |
| 293 if( word >= size ) // Beyond the last? | |
| 294 return 0; // Then it's clear | |
| 295 register uint32 mask = 1L << (elem & 31); // Get bit mask | |
| 296 return ((data[word] & mask))!=0; // Return the sense of the bit | |
| 297 } | |
| 298 | |
| 299 //------------------------------getelem---------------------------------------- | |
| 300 // Get any element from the set. | |
| 301 uint VectorSet::getelem(void) const | |
| 302 { | |
| 303 uint i; // Exit value of loop | |
| 304 for( i=0; i<size; i++ ) | |
| 305 if( data[i] ) | |
| 306 break; | |
| 307 uint32 word = data[i]; | |
| 308 int j; // Exit value of loop | |
| 309 for( j= -1; word; j++, word>>=1 ); | |
| 310 return (i<<5)+j; | |
| 311 } | |
| 312 | |
| 313 //------------------------------Clear------------------------------------------ | |
| 314 // Clear a set | |
| 315 void VectorSet::Clear(void) | |
| 316 { | |
| 317 if( size > 100 ) { // Reclaim storage only if huge | |
| 318 FREE_RESOURCE_ARRAY(uint32,data,size); | |
| 319 size = 2; // Small initial size | |
| 320 data = NEW_RESOURCE_ARRAY(uint32,size); | |
| 321 } | |
| 322 memset( data, 0, size*sizeof(uint32) ); | |
| 323 } | |
| 324 | |
| 325 //------------------------------Size------------------------------------------- | |
| 326 // Return number of elements in a Set | |
| 327 uint VectorSet::Size(void) const | |
| 328 { | |
| 329 uint sum = 0; // Cumulative size so far. | |
| 330 uint8 *currByte = (uint8*)data; | |
| 331 for( uint32 i = 0; i < (size<<2); i++) // While have bytes to process | |
| 332 sum += bitsInByte[*currByte++]; // Add bits in current byte to size. | |
| 333 return sum; | |
| 334 } | |
| 335 | |
| 336 //------------------------------Sort------------------------------------------- | |
| 337 // Sort the elements for the next forall statement | |
| 338 void VectorSet::Sort(void) | |
| 339 { | |
| 340 } | |
| 341 | |
| 342 //------------------------------hash------------------------------------------- | |
| 343 int VectorSet::hash() const | |
| 344 { | |
| 345 uint32 _xor = 0; | |
| 346 uint lim = ((size<4)?size:4); | |
| 347 for( uint i = 0; i < lim; i++ ) | |
| 348 _xor ^= data[i]; | |
| 349 return (int)_xor; | |
| 350 } | |
| 351 | |
| 352 //------------------------------iterate---------------------------------------- | |
| 353 SetI_ *VectorSet::iterate(uint &elem) const | |
| 354 { | |
| 355 VSetI_ *foo = (new(ResourceObj::C_HEAP) VSetI_(this)); | |
| 356 elem = foo->next(); | |
| 357 return foo; | |
| 358 } | |
| 359 | |
| 360 //============================================================================= | |
| 361 //------------------------------VSetI_----------------------------------------- | |
| 362 // Initialize the innards of a VectorSet iterator | |
| 363 VSetI_::VSetI_( const VectorSet *vset ) : s(vset) | |
| 364 { | |
| 365 i = (uint)-1L; | |
| 366 j = (uint)-1L; | |
| 367 mask = (unsigned)(1L<<31); | |
| 368 } | |
| 369 | |
| 370 //------------------------------next------------------------------------------- | |
| 371 // Find and return the next element of a vector set, or return garbage and | |
| 372 // make "VSetI_::test()" fail. | |
| 373 uint VSetI_::next(void) | |
| 374 { | |
| 375 j++; // Next element in word | |
| 376 mask = (mask & max_jint) << 1;// Next bit in word | |
| 377 do { // Do While still have words | |
| 378 while( mask ) { // While have bits in word | |
| 379 if( s->data[i] & mask ) { // If found a bit | |
| 380 return (i<<5)+j; // Return the bit address | |
| 381 } | |
| 382 j++; // Skip to next bit | |
| 383 mask = (mask & max_jint) << 1; | |
| 384 } | |
| 385 j = 0; // No more bits in word; setup for next word | |
| 386 mask = 1; | |
| 387 for( i++; (i<s->size) && (!s->data[i]); i++ ); // Skip to non-zero word | |
| 388 } while( i<s->size ); | |
| 389 return max_juint; // No element, iterated them all | |
| 390 } |