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();
|