< prev index next >

src/share/vm/gc/cms/parNewGeneration.cpp

Print this page
rev 11970 : imported patch overflow_list


1246 // In case we are using compressed oops, we need to be careful.
1247 // If the object being pushed is an object array, then its length
1248 // field keeps track of the "grey boundary" at which the next
1249 // incremental scan will be done (see ParGCArrayScanChunk).
1250 // When using compressed oops, this length field is kept in the
1251 // lower 32 bits of the erstwhile klass word and cannot be used
1252 // for the overflow chaining pointer (OCP below). As such the OCP
1253 // would itself need to be compressed into the top 32-bits in this
1254 // case. Unfortunately, see below, in the event that we have a
1255 // promotion failure, the node to be pushed on the list can be
1256 // outside of the Java heap, so the heap-based pointer compression
1257 // would not work (we would have potential aliasing between C-heap
1258 // and Java-heap pointers). For this reason, when using compressed
1259 // oops, we simply use a worker-thread-local, non-shared overflow
1260 // list in the form of a growable array, with a slightly different
1261 // overflow stack draining strategy. If/when we start using fat
1262 // stacks here, we can go back to using (fat) pointer chains
1263 // (although some performance comparisons would be useful since
1264 // single global lists have their own performance disadvantages
1265 // as we were made painfully aware not long ago, see 6786503).
1266 #define BUSY (cast_to_oop<intptr_t>(0x1aff1aff))
1267 void ParNewGeneration::push_on_overflow_list(oop from_space_obj, ParScanThreadState* par_scan_state) {
1268   assert(is_in_reserved(from_space_obj), "Should be from this generation");
1269   if (ParGCUseLocalOverflow) {
1270     // In the case of compressed oops, we use a private, not-shared
1271     // overflow stack.
1272     par_scan_state->push_on_overflow_stack(from_space_obj);
1273   } else {
1274     assert(!UseCompressedOops, "Error");
1275     // if the object has been forwarded to itself, then we cannot
1276     // use the klass pointer for the linked list.  Instead we have
1277     // to allocate an oopDesc in the C-Heap and use that for the linked list.
1278     // XXX This is horribly inefficient when a promotion failure occurs
1279     // and should be fixed. XXX FIX ME !!!
1280 #ifndef PRODUCT
1281     Atomic::inc_ptr(&_num_par_pushes);
1282     assert(_num_par_pushes > 0, "Tautology");
1283 #endif
1284     if (from_space_obj->forwardee() == from_space_obj) {
1285       oopDesc* listhead = NEW_C_HEAP_ARRAY(oopDesc, 1, mtGC);
1286       listhead->forward_to(from_space_obj);
1287       from_space_obj = listhead;
1288     }
1289     oop observed_overflow_list = _overflow_list;
1290     oop cur_overflow_list;
1291     do {
1292       cur_overflow_list = observed_overflow_list;
1293       if (cur_overflow_list != BUSY) {
1294         from_space_obj->set_klass_to_list_ptr(cur_overflow_list);
1295       } else {
1296         from_space_obj->set_klass_to_list_ptr(NULL);
1297       }
1298       observed_overflow_list =
1299         (oop)Atomic::cmpxchg_ptr(from_space_obj, &_overflow_list, cur_overflow_list);
1300     } while (cur_overflow_list != observed_overflow_list);
1301   }
1302 }
1303 
1304 bool ParNewGeneration::take_from_overflow_list(ParScanThreadState* par_scan_state) {
1305   bool res;
1306 
1307   if (ParGCUseLocalOverflow) {
1308     res = par_scan_state->take_from_overflow_stack();
1309   } else {
1310     assert(!UseCompressedOops, "Error");
1311     res = take_from_overflow_list_work(par_scan_state);
1312   }
1313   return res;
1314 }
1315 
1316 
1317 // *NOTE*: The overflow list manipulation code here and
1318 // in CMSCollector:: are very similar in shape,
1319 // except that in the CMS case we thread the objects


1322 // to chunking of object arrays and promotion failure
1323 // handling.
1324 // CR 6797058 has been filed to attempt consolidation of
1325 // the common code.
1326 // Because of the common code, if you make any changes in
1327 // the code below, please check the CMS version to see if
1328 // similar changes might be needed.
1329 // See CMSCollector::par_take_from_overflow_list() for
1330 // more extensive documentation comments.
1331 bool ParNewGeneration::take_from_overflow_list_work(ParScanThreadState* par_scan_state) {
1332   ObjToScanQueue* work_q = par_scan_state->work_queue();
1333   // How many to take?
1334   size_t objsFromOverflow = MIN2((size_t)(work_q->max_elems() - work_q->size())/4,
1335                                  (size_t)ParGCDesiredObjsFromOverflowList);
1336 
1337   assert(!UseCompressedOops, "Error");
1338   assert(par_scan_state->overflow_stack() == NULL, "Error");
1339   if (_overflow_list == NULL) return false;
1340 
1341   // Otherwise, there was something there; try claiming the list.
1342   oop prefix = cast_to_oop(Atomic::xchg_ptr(BUSY, &_overflow_list));
1343   // Trim off a prefix of at most objsFromOverflow items
1344   Thread* tid = Thread::current();
1345   size_t spin_count = ParallelGCThreads;
1346   size_t sleep_time_millis = MAX2((size_t)1, objsFromOverflow/100);
1347   for (size_t spin = 0; prefix == BUSY && spin < spin_count; spin++) {
1348     // someone grabbed it before we did ...
1349     // ... we spin for a short while...
1350     os::sleep(tid, sleep_time_millis, false);
1351     if (_overflow_list == NULL) {
1352       // nothing left to take
1353       return false;
1354     } else if (_overflow_list != BUSY) {
1355      // try and grab the prefix
1356      prefix = cast_to_oop(Atomic::xchg_ptr(BUSY, &_overflow_list));
1357     }
1358   }
1359   if (prefix == NULL || prefix == BUSY) {
1360      // Nothing to take or waited long enough
1361      if (prefix == NULL) {
1362        // Write back the NULL in case we overwrote it with BUSY above
1363        // and it is still the same value.
1364        (void) Atomic::cmpxchg_ptr(NULL, &_overflow_list, BUSY);
1365      }
1366      return false;
1367   }
1368   assert(prefix != NULL && prefix != BUSY, "Error");
1369   size_t i = 1;
1370   oop cur = prefix;
1371   while (i < objsFromOverflow && cur->klass_or_null() != NULL) {
1372     i++; cur = cur->list_ptr_from_klass();
1373   }
1374 
1375   // Reattach remaining (suffix) to overflow list
1376   if (cur->klass_or_null() == NULL) {
1377     // Write back the NULL in lieu of the BUSY we wrote
1378     // above and it is still the same value.
1379     if (_overflow_list == BUSY) {
1380       (void) Atomic::cmpxchg_ptr(NULL, &_overflow_list, BUSY);
1381     }
1382   } else {
1383     assert(cur->klass_or_null() != (Klass*)(address)BUSY, "Error");
1384     oop suffix = cur->list_ptr_from_klass();       // suffix will be put back on global list
1385     cur->set_klass_to_list_ptr(NULL);     // break off suffix
1386     // It's possible that the list is still in the empty(busy) state
1387     // we left it in a short while ago; in that case we may be
1388     // able to place back the suffix.
1389     oop observed_overflow_list = _overflow_list;
1390     oop cur_overflow_list = observed_overflow_list;
1391     bool attached = false;
1392     while (observed_overflow_list == BUSY || observed_overflow_list == NULL) {
1393       observed_overflow_list =
1394         (oop) Atomic::cmpxchg_ptr(suffix, &_overflow_list, cur_overflow_list);
1395       if (cur_overflow_list == observed_overflow_list) {
1396         attached = true;
1397         break;
1398       } else cur_overflow_list = observed_overflow_list;
1399     }
1400     if (!attached) {
1401       // Too bad, someone else got in in between; we'll need to do a splice.
1402       // Find the last item of suffix list
1403       oop last = suffix;
1404       while (last->klass_or_null() != NULL) {
1405         last = last->list_ptr_from_klass();
1406       }
1407       // Atomically prepend suffix to current overflow list
1408       observed_overflow_list = _overflow_list;
1409       do {
1410         cur_overflow_list = observed_overflow_list;
1411         if (cur_overflow_list != BUSY) {
1412           // Do the splice ...
1413           last->set_klass_to_list_ptr(cur_overflow_list);
1414         } else { // cur_overflow_list == BUSY
1415           last->set_klass_to_list_ptr(NULL);
1416         }
1417         observed_overflow_list =
1418           (oop)Atomic::cmpxchg_ptr(suffix, &_overflow_list, cur_overflow_list);
1419       } while (cur_overflow_list != observed_overflow_list);
1420     }
1421   }
1422 
1423   // Push objects on prefix list onto this thread's work queue
1424   assert(prefix != NULL && prefix != BUSY, "program logic");
1425   cur = prefix;
1426   ssize_t n = 0;
1427   while (cur != NULL) {
1428     oop obj_to_push = cur->forwardee();
1429     oop next        = cur->list_ptr_from_klass();
1430     cur->set_klass(obj_to_push->klass());
1431     // This may be an array object that is self-forwarded. In that case, the list pointer
1432     // space, cur, is not in the Java heap, but rather in the C-heap and should be freed.
1433     if (!is_in_reserved(cur)) {
1434       // This can become a scaling bottleneck when there is work queue overflow coincident
1435       // with promotion failure.
1436       oopDesc* f = cur;
1437       FREE_C_HEAP_ARRAY(oopDesc, f);
1438     } else if (par_scan_state->should_be_partially_scanned(obj_to_push, cur)) {
1439       assert(arrayOop(cur)->length() == 0, "entire array remaining to be scanned");
1440       obj_to_push = cur;
1441     }
1442     bool ok = work_q->push(obj_to_push);
1443     assert(ok, "Should have succeeded");
1444     cur = next;
1445     n++;




1246 // In case we are using compressed oops, we need to be careful.
1247 // If the object being pushed is an object array, then its length
1248 // field keeps track of the "grey boundary" at which the next
1249 // incremental scan will be done (see ParGCArrayScanChunk).
1250 // When using compressed oops, this length field is kept in the
1251 // lower 32 bits of the erstwhile klass word and cannot be used
1252 // for the overflow chaining pointer (OCP below). As such the OCP
1253 // would itself need to be compressed into the top 32-bits in this
1254 // case. Unfortunately, see below, in the event that we have a
1255 // promotion failure, the node to be pushed on the list can be
1256 // outside of the Java heap, so the heap-based pointer compression
1257 // would not work (we would have potential aliasing between C-heap
1258 // and Java-heap pointers). For this reason, when using compressed
1259 // oops, we simply use a worker-thread-local, non-shared overflow
1260 // list in the form of a growable array, with a slightly different
1261 // overflow stack draining strategy. If/when we start using fat
1262 // stacks here, we can go back to using (fat) pointer chains
1263 // (although some performance comparisons would be useful since
1264 // single global lists have their own performance disadvantages
1265 // as we were made painfully aware not long ago, see 6786503).
1266 #define BUSY ((HeapWord*)(0x1aff1aff))
1267 void ParNewGeneration::push_on_overflow_list(oop from_space_obj, ParScanThreadState* par_scan_state) {
1268   assert(is_in_reserved(from_space_obj), "Should be from this generation");
1269   if (ParGCUseLocalOverflow) {
1270     // In the case of compressed oops, we use a private, not-shared
1271     // overflow stack.
1272     par_scan_state->push_on_overflow_stack(from_space_obj);
1273   } else {
1274     assert(!UseCompressedOops, "Error");
1275     // if the object has been forwarded to itself, then we cannot
1276     // use the klass pointer for the linked list.  Instead we have
1277     // to allocate an oopDesc in the C-Heap and use that for the linked list.
1278     // XXX This is horribly inefficient when a promotion failure occurs
1279     // and should be fixed. XXX FIX ME !!!
1280 #ifndef PRODUCT
1281     Atomic::inc_ptr(&_num_par_pushes);
1282     assert(_num_par_pushes > 0, "Tautology");
1283 #endif
1284     if (from_space_obj->forwardee() == from_space_obj) {
1285       oopDesc* listhead = NEW_C_HEAP_ARRAY(oopDesc, 1, mtGC);
1286       listhead->forward_to(from_space_obj);
1287       from_space_obj = listhead;
1288     }
1289     HeapWord* observed_overflow_list = _overflow_list;
1290     HeapWord* cur_overflow_list;
1291     do {
1292       cur_overflow_list = observed_overflow_list;
1293       if (cur_overflow_list != BUSY) {
1294         from_space_obj->set_klass_to_list_ptr(cast_to_oop<HeapWord*>(cur_overflow_list));
1295       } else {
1296         from_space_obj->set_klass_to_list_ptr(NULL);
1297       }
1298       observed_overflow_list =
1299         (HeapWord*)Atomic::cmpxchg_ptr(cast_from_oop<HeapWord*>(from_space_obj), &_overflow_list, cur_overflow_list);
1300     } while (cur_overflow_list != observed_overflow_list);
1301   }
1302 }
1303 
1304 bool ParNewGeneration::take_from_overflow_list(ParScanThreadState* par_scan_state) {
1305   bool res;
1306 
1307   if (ParGCUseLocalOverflow) {
1308     res = par_scan_state->take_from_overflow_stack();
1309   } else {
1310     assert(!UseCompressedOops, "Error");
1311     res = take_from_overflow_list_work(par_scan_state);
1312   }
1313   return res;
1314 }
1315 
1316 
1317 // *NOTE*: The overflow list manipulation code here and
1318 // in CMSCollector:: are very similar in shape,
1319 // except that in the CMS case we thread the objects


1322 // to chunking of object arrays and promotion failure
1323 // handling.
1324 // CR 6797058 has been filed to attempt consolidation of
1325 // the common code.
1326 // Because of the common code, if you make any changes in
1327 // the code below, please check the CMS version to see if
1328 // similar changes might be needed.
1329 // See CMSCollector::par_take_from_overflow_list() for
1330 // more extensive documentation comments.
1331 bool ParNewGeneration::take_from_overflow_list_work(ParScanThreadState* par_scan_state) {
1332   ObjToScanQueue* work_q = par_scan_state->work_queue();
1333   // How many to take?
1334   size_t objsFromOverflow = MIN2((size_t)(work_q->max_elems() - work_q->size())/4,
1335                                  (size_t)ParGCDesiredObjsFromOverflowList);
1336 
1337   assert(!UseCompressedOops, "Error");
1338   assert(par_scan_state->overflow_stack() == NULL, "Error");
1339   if (_overflow_list == NULL) return false;
1340 
1341   // Otherwise, there was something there; try claiming the list.
1342   HeapWord* prefix = (HeapWord*)Atomic::xchg_ptr(BUSY, &_overflow_list);
1343   // Trim off a prefix of at most objsFromOverflow items
1344   Thread* tid = Thread::current();
1345   size_t spin_count = ParallelGCThreads;
1346   size_t sleep_time_millis = MAX2((size_t)1, objsFromOverflow/100);
1347   for (size_t spin = 0; prefix == BUSY && spin < spin_count; spin++) {
1348     // someone grabbed it before we did ...
1349     // ... we spin for a short while...
1350     os::sleep(tid, sleep_time_millis, false);
1351     if (_overflow_list == NULL) {
1352       // nothing left to take
1353       return false;
1354     } else if (_overflow_list != BUSY) {
1355      // try and grab the prefix
1356       prefix = (HeapWord*)Atomic::xchg_ptr(BUSY, &_overflow_list);
1357     }
1358   }
1359   if (prefix == NULL || prefix == BUSY) {
1360      // Nothing to take or waited long enough
1361      if (prefix == NULL) {
1362        // Write back the NULL in case we overwrote it with BUSY above
1363        // and it is still the same value.
1364        (void) Atomic::cmpxchg_ptr(NULL, &_overflow_list, BUSY);
1365      }
1366      return false;
1367   }
1368   assert(prefix != NULL && prefix != BUSY, "Error");
1369   size_t i = 1;
1370   oop cur = cast_to_oop<HeapWord*>(prefix);
1371   while (i < objsFromOverflow && cur->klass_or_null() != NULL) {
1372     i++; cur = cur->list_ptr_from_klass();
1373   }
1374 
1375   // Reattach remaining (suffix) to overflow list
1376   if (cur->klass_or_null() == NULL) {
1377     // Write back the NULL in lieu of the BUSY we wrote
1378     // above and it is still the same value.
1379     if (_overflow_list == BUSY) {
1380       (void) Atomic::cmpxchg_ptr(NULL, &_overflow_list, BUSY);
1381     }
1382   } else {
1383     assert(cur->klass_or_null() != (Klass*)(address)BUSY, "Error");
1384     oop suffix = cur->list_ptr_from_klass();       // suffix will be put back on global list
1385     cur->set_klass_to_list_ptr(NULL);     // break off suffix
1386     // It's possible that the list is still in the empty(busy) state
1387     // we left it in a short while ago; in that case we may be
1388     // able to place back the suffix.
1389     HeapWord* observed_overflow_list = _overflow_list;
1390     HeapWord* cur_overflow_list = observed_overflow_list;
1391     bool attached = false;
1392     while (observed_overflow_list == BUSY || observed_overflow_list == NULL) {
1393       observed_overflow_list =
1394         (HeapWord*)Atomic::cmpxchg_ptr(suffix, &_overflow_list, cur_overflow_list);
1395       if (cur_overflow_list == observed_overflow_list) {
1396         attached = true;
1397         break;
1398       } else cur_overflow_list = observed_overflow_list;
1399     }
1400     if (!attached) {
1401       // Too bad, someone else got in in between; we'll need to do a splice.
1402       // Find the last item of suffix list
1403       oop last = suffix;
1404       while (last->klass_or_null() != NULL) {
1405         last = last->list_ptr_from_klass();
1406       }
1407       // Atomically prepend suffix to current overflow list
1408       observed_overflow_list = _overflow_list;
1409       do {
1410         cur_overflow_list = observed_overflow_list;
1411         if (cur_overflow_list != BUSY) {
1412           // Do the splice ...
1413           last->set_klass_to_list_ptr(cast_to_oop<HeapWord*>(cur_overflow_list));
1414         } else { // cur_overflow_list == BUSY
1415           last->set_klass_to_list_ptr(NULL);
1416         }
1417         observed_overflow_list =
1418           (HeapWord*)Atomic::cmpxchg_ptr(cast_from_oop<HeapWord*>(suffix), &_overflow_list, cur_overflow_list);
1419       } while (cur_overflow_list != observed_overflow_list);
1420     }
1421   }
1422 
1423   // Push objects on prefix list onto this thread's work queue
1424   assert(prefix != NULL && prefix != BUSY, "program logic");
1425   cur = cast_to_oop<HeapWord*>(prefix);
1426   ssize_t n = 0;
1427   while (cur != NULL) {
1428     oop obj_to_push = cur->forwardee();
1429     oop next        = cur->list_ptr_from_klass();
1430     cur->set_klass(obj_to_push->klass());
1431     // This may be an array object that is self-forwarded. In that case, the list pointer
1432     // space, cur, is not in the Java heap, but rather in the C-heap and should be freed.
1433     if (!is_in_reserved(cur)) {
1434       // This can become a scaling bottleneck when there is work queue overflow coincident
1435       // with promotion failure.
1436       oopDesc* f = cur;
1437       FREE_C_HEAP_ARRAY(oopDesc, f);
1438     } else if (par_scan_state->should_be_partially_scanned(obj_to_push, cur)) {
1439       assert(arrayOop(cur)->length() == 0, "entire array remaining to be scanned");
1440       obj_to_push = cur;
1441     }
1442     bool ok = work_q->push(obj_to_push);
1443     assert(ok, "Should have succeeded");
1444     cur = next;
1445     n++;


< prev index next >