rev 57974 : [mq]: pop_last

121 // It then sets the "next" value of the old tail to the head of the list being 122 // appended; it is an invariant that the old tail's "next" value is NULL. 123 // But if the old tail is NULL then the queue was empty. In this case the 124 // head of the list being appended is instead stored in the queue head; it is 125 // an invariant that the queue head is NULL in this case. 126 // 127 // This means there is a period between the exchange and the old tail update 128 // where the queue sequence is split into two parts, the list from the queue 129 // head to the old tail, and the list being appended. If there are concurrent 130 // push/append operations, each may introduce another such segment. But they 131 // all eventually get resolved by their respective updates of their old tail's 132 // "next" value. This also means that pop operations must handle a buffer 133 // with a NULL "next" value specially. 134 // 135 // A push operation is just a degenerate append, where the buffer being pushed 136 // is both the head and the tail of the list being appended. 137 void G1DirtyCardQueueSet::Queue::append(BufferNode& first, BufferNode& last) { 138 assert(last.next() == NULL, "precondition"); 139 BufferNode* old_tail = Atomic::xchg(&_tail, &last); 140 if (old_tail == NULL) { // Was empty. 141 assert(Atomic::load(&_head) == NULL, "invariant"); 142 Atomic::store(&_head, &first); 143 } else { 144 assert(old_tail->next() == NULL, "invariant"); 145 old_tail->set_next(&first); 146 } 147 } 148 149 // pop gets the queue head as the candidate result (returning NULL if the 150 // queue head was NULL), and then gets that result node's "next" value. If 151 // that "next" value is NULL and the queue head hasn't changed, then there 152 // is only one element in the accessible part of the list (the sequence from 153 // head to a node with a NULL "next" value). We can't return that element, 154 // because it may be the old tail of a concurrent push/append that has not 155 // yet had its "next" field set to the new tail. So return NULL in this case. 156 // Otherwise, attempt to cmpxchg that "next" value into the queue head, 157 // retrying the whole operation if that fails. This is the "usual" lock-free 158 // pop from the head of a singly linked list, with the additional restriction 159 // on taking the last element. 160 BufferNode* G1DirtyCardQueueSet::Queue::pop() { 161 Thread* current_thread = Thread::current(); 162 while (true) { 163 // Use a critical section per iteration, rather than over the whole 164 // operation. We're not guaranteed to make progress, because of possible 165 // contention on the queue head. Lingering in one CS the whole time could 166 // lead to excessive allocation of buffers, because the CS blocks return 167 // of released buffers to the free list for reuse. 168 GlobalCounter::CriticalSection cs(current_thread); 169 170 BufferNode* result = Atomic::load_acquire(&_head); 171 // Check for empty queue. Only needs to be done on first iteration, 172 // since we never take the last element, but it's messy to make use 173 // of that and we expect one iteration to be the common case. 174 if (result == NULL) return NULL; 175 176 BufferNode* next = Atomic::load_acquire(BufferNode::next_ptr(*result)); 177 if (next != NULL) { 178 next = Atomic::cmpxchg(&_head, result, next); 179 if (next == result) { 180 // Former head successfully taken; it is not the last. 181 assert(Atomic::load(&_tail) != result, "invariant"); 182 assert(result->next() != NULL, "invariant"); 183 result->set_next(NULL); 184 return result; 185 } 186 // cmpxchg failed; try again. 187 } else if (result == Atomic::load_acquire(&_head)) { 188 // If follower of head is NULL and head hasn't changed, then only 189 // the one element is currently accessible. We don't take the last 190 // accessible element, because there may be a concurrent add using it. 191 // The check for unchanged head isn't needed for correctness, but the 192 // retry on change may sometimes let us get a buffer after all. 193 return NULL; 194 } 195 // Head changed; try again. 196 } 197 } 198 199 G1DirtyCardQueueSet::HeadTail G1DirtyCardQueueSet::Queue::take_all() { 200 assert_at_safepoint(); 201 HeadTail result(Atomic::load(&_head), Atomic::load(&_tail)); 202 Atomic::store(&_head, (BufferNode*)NULL); 203 Atomic::store(&_tail, (BufferNode*)NULL); 204 return result; 205 } 206 207 void G1DirtyCardQueueSet::enqueue_completed_buffer(BufferNode* cbn) { 208 assert(cbn != NULL, "precondition"); 209 // Increment _num_cards before adding to queue, so queue removal doesn't 210 // need to deal with _num_cards possibly going negative. 211 size_t new_num_cards = Atomic::add(&_num_cards, buffer_size() - cbn->index()); 212 _completed.push(*cbn); 213 if ((new_num_cards > process_cards_threshold()) && 214 (_primary_refinement_thread != NULL)) { 215 _primary_refinement_thread->activate(); | 121 // It then sets the "next" value of the old tail to the head of the list being 122 // appended; it is an invariant that the old tail's "next" value is NULL. 123 // But if the old tail is NULL then the queue was empty. In this case the 124 // head of the list being appended is instead stored in the queue head; it is 125 // an invariant that the queue head is NULL in this case. 126 // 127 // This means there is a period between the exchange and the old tail update 128 // where the queue sequence is split into two parts, the list from the queue 129 // head to the old tail, and the list being appended. If there are concurrent 130 // push/append operations, each may introduce another such segment. But they 131 // all eventually get resolved by their respective updates of their old tail's 132 // "next" value. This also means that pop operations must handle a buffer 133 // with a NULL "next" value specially. 134 // 135 // A push operation is just a degenerate append, where the buffer being pushed 136 // is both the head and the tail of the list being appended. 137 void G1DirtyCardQueueSet::Queue::append(BufferNode& first, BufferNode& last) { 138 assert(last.next() == NULL, "precondition"); 139 BufferNode* old_tail = Atomic::xchg(&_tail, &last); 140 if (old_tail == NULL) { // Was empty. 141 Atomic::store(&_head, &first); 142 } else { 143 assert(old_tail->next() == NULL, "invariant"); 144 old_tail->set_next(&first); 145 } 146 } 147 148 BufferNode* G1DirtyCardQueueSet::Queue::pop() { 149 Thread* current_thread = Thread::current(); 150 while (true) { 151 // Use a critical section per iteration, rather than over the whole 152 // operation. We're not guaranteed to make progress. Lingering in one 153 // CS could lead to excessive allocation of buffers, because the CS 154 // blocks return of released buffers to the free list for reuse. 155 GlobalCounter::CriticalSection cs(current_thread); 156 157 BufferNode* result = Atomic::load_acquire(&_head); 158 if (result == NULL) return NULL; // Queue is empty. 159 160 BufferNode* next = Atomic::load_acquire(BufferNode::next_ptr(*result)); 161 if (next != NULL) { 162 // The "usual" lock-free pop from the head of a singly linked list. 163 if (result == Atomic::cmpxchg(&_head, result, next)) { 164 // Former head successfully taken; it is not the last. 165 assert(Atomic::load(&_tail) != result, "invariant"); 166 assert(result->next() != NULL, "invariant"); 167 result->set_next(NULL); 168 return result; 169 } 170 // Lost the race; try again. 171 continue; 172 } 173 174 // next is NULL. This case is handled differently from the "usual" 175 // lock-free pop from the head of a singly linked list. 176 177 // If _tail == result then result is the only element in the list. We can 178 // remove it from the list by first setting _tail to NULL and then setting 179 // _head to NULL, the order being important. We set _tail with cmpxchg in 180 // case of a concurrent push/append/pop also changing _tail. If we win 181 // then we've claimed result. 182 if (Atomic::cmpxchg(&_tail, result, (BufferNode*)NULL) == result) { 183 assert(result->next() == NULL, "invariant"); 184 // Now that we've claimed result, also set _head to NULL. But we must 185 // be careful of a concurrent push/append after we NULLed _tail, since 186 // it may have already performed its list-was-empty update of _head, 187 // which we must not overwrite. 188 Atomic::cmpxchg(&_head, result, (BufferNode*)NULL); 189 return result; 190 } 191 192 // If _head != result then we lost the race to take result; try again. 193 if (result != Atomic::load_acquire(&_head)) { 194 continue; 195 } 196 197 // An in-progress concurrent operation interfered with taking the head 198 // element when it was the only element. A concurrent pop may have won 199 // the race to clear the tail but not yet cleared the head. Alternatively, 200 // a concurrent push/append may have changed the tail but not yet linked 201 // result->next(). We cannot take result in either case. We don't just 202 // try again, because we could spin for a long time waiting for that 203 // concurrent operation to finish. In the first case, returning NULL is 204 // fine; we lost the race for the only element to another thread. We 205 // also return NULL for the second case, and let the caller cope. 206 return NULL; 207 } 208 } 209 210 G1DirtyCardQueueSet::HeadTail G1DirtyCardQueueSet::Queue::take_all() { 211 assert_at_safepoint(); 212 HeadTail result(Atomic::load(&_head), Atomic::load(&_tail)); 213 Atomic::store(&_head, (BufferNode*)NULL); 214 Atomic::store(&_tail, (BufferNode*)NULL); 215 return result; 216 } 217 218 void G1DirtyCardQueueSet::enqueue_completed_buffer(BufferNode* cbn) { 219 assert(cbn != NULL, "precondition"); 220 // Increment _num_cards before adding to queue, so queue removal doesn't 221 // need to deal with _num_cards possibly going negative. 222 size_t new_num_cards = Atomic::add(&_num_cards, buffer_size() - cbn->index()); 223 _completed.push(*cbn); 224 if ((new_num_cards > process_cards_threshold()) && 225 (_primary_refinement_thread != NULL)) { 226 _primary_refinement_thread->activate(); |