< prev index next >

src/hotspot/share/gc/g1/g1DirtyCardQueue.cpp

Print this page
rev 57974 : [mq]: pop_last

*** 136,200 **** // is both the head and the tail of the list being appended. void G1DirtyCardQueueSet::Queue::append(BufferNode& first, BufferNode& last) { assert(last.next() == NULL, "precondition"); BufferNode* old_tail = Atomic::xchg(&_tail, &last); if (old_tail == NULL) { // Was empty. - assert(Atomic::load(&_head) == NULL, "invariant"); Atomic::store(&_head, &first); } else { assert(old_tail->next() == NULL, "invariant"); old_tail->set_next(&first); } } - // pop gets the queue head as the candidate result (returning NULL if the - // queue head was NULL), and then gets that result node's "next" value. If - // that "next" value is NULL and the queue head hasn't changed, then there - // is only one element in the accessible part of the list (the sequence from - // head to a node with a NULL "next" value). We can't return that element, - // because it may be the old tail of a concurrent push/append that has not - // yet had its "next" field set to the new tail. So return NULL in this case. - // Otherwise, attempt to cmpxchg that "next" value into the queue head, - // retrying the whole operation if that fails. This is the "usual" lock-free - // pop from the head of a singly linked list, with the additional restriction - // on taking the last element. BufferNode* G1DirtyCardQueueSet::Queue::pop() { Thread* current_thread = Thread::current(); while (true) { // Use a critical section per iteration, rather than over the whole ! // operation. We're not guaranteed to make progress, because of possible ! // contention on the queue head. Lingering in one CS the whole time could ! // lead to excessive allocation of buffers, because the CS blocks return ! // of released buffers to the free list for reuse. GlobalCounter::CriticalSection cs(current_thread); BufferNode* result = Atomic::load_acquire(&_head); ! // Check for empty queue. Only needs to be done on first iteration, ! // since we never take the last element, but it's messy to make use ! // of that and we expect one iteration to be the common case. ! if (result == NULL) return NULL; BufferNode* next = Atomic::load_acquire(BufferNode::next_ptr(*result)); if (next != NULL) { ! next = Atomic::cmpxchg(&_head, result, next); ! if (next == result) { // Former head successfully taken; it is not the last. assert(Atomic::load(&_tail) != result, "invariant"); assert(result->next() != NULL, "invariant"); result->set_next(NULL); return result; } ! // cmpxchg failed; try again. ! } else if (result == Atomic::load_acquire(&_head)) { ! // If follower of head is NULL and head hasn't changed, then only ! // the one element is currently accessible. We don't take the last ! // accessible element, because there may be a concurrent add using it. ! // The check for unchanged head isn't needed for correctness, but the ! // retry on change may sometimes let us get a buffer after all. ! return NULL; } ! // Head changed; try again. } } G1DirtyCardQueueSet::HeadTail G1DirtyCardQueueSet::Queue::take_all() { assert_at_safepoint(); --- 136,211 ---- // is both the head and the tail of the list being appended. void G1DirtyCardQueueSet::Queue::append(BufferNode& first, BufferNode& last) { assert(last.next() == NULL, "precondition"); BufferNode* old_tail = Atomic::xchg(&_tail, &last); if (old_tail == NULL) { // Was empty. Atomic::store(&_head, &first); } else { assert(old_tail->next() == NULL, "invariant"); old_tail->set_next(&first); } } BufferNode* G1DirtyCardQueueSet::Queue::pop() { Thread* current_thread = Thread::current(); while (true) { // Use a critical section per iteration, rather than over the whole ! // operation. We're not guaranteed to make progress. Lingering in one ! // CS could lead to excessive allocation of buffers, because the CS ! // blocks return of released buffers to the free list for reuse. GlobalCounter::CriticalSection cs(current_thread); BufferNode* result = Atomic::load_acquire(&_head); ! if (result == NULL) return NULL; // Queue is empty. BufferNode* next = Atomic::load_acquire(BufferNode::next_ptr(*result)); if (next != NULL) { ! // The "usual" lock-free pop from the head of a singly linked list. ! if (result == Atomic::cmpxchg(&_head, result, next)) { // Former head successfully taken; it is not the last. assert(Atomic::load(&_tail) != result, "invariant"); assert(result->next() != NULL, "invariant"); result->set_next(NULL); return result; } ! // Lost the race; try again. ! continue; ! } ! ! // next is NULL. This case is handled differently from the "usual" ! // lock-free pop from the head of a singly linked list. ! ! // If _tail == result then result is the only element in the list. We can ! // remove it from the list by first setting _tail to NULL and then setting ! // _head to NULL, the order being important. We set _tail with cmpxchg in ! // case of a concurrent push/append/pop also changing _tail. If we win ! // then we've claimed result. ! if (Atomic::cmpxchg(&_tail, result, (BufferNode*)NULL) == result) { ! assert(result->next() == NULL, "invariant"); ! // Now that we've claimed result, also set _head to NULL. But we must ! // be careful of a concurrent push/append after we NULLed _tail, since ! // it may have already performed its list-was-empty update of _head, ! // which we must not overwrite. ! Atomic::cmpxchg(&_head, result, (BufferNode*)NULL); ! return result; } ! ! // If _head != result then we lost the race to take result; try again. ! if (result != Atomic::load_acquire(&_head)) { ! continue; ! } ! ! // An in-progress concurrent operation interfered with taking the head ! // element when it was the only element. A concurrent pop may have won ! // the race to clear the tail but not yet cleared the head. Alternatively, ! // a concurrent push/append may have changed the tail but not yet linked ! // result->next(). We cannot take result in either case. We don't just ! // try again, because we could spin for a long time waiting for that ! // concurrent operation to finish. In the first case, returning NULL is ! // fine; we lost the race for the only element to another thread. We ! // also return NULL for the second case, and let the caller cope. ! return NULL; } } G1DirtyCardQueueSet::HeadTail G1DirtyCardQueueSet::Queue::take_all() { assert_at_safepoint();
< prev index next >