Prepare FreeList for parallel and concurrent sweeping.

Prepare FreeList for parallel and concurrent sweeping.

BUG=

Committed: https://code.google.com/p/v8/source/detail?r=13198

[Michael Starzinger, 2012-11-22 21:26:24]

Hmm, I am not completely sure what this changes is aiming at. Why do we need two
pointers for the free-list categories? Shouldn't we get by with just one start
pointer as before? Adding the free-list for a new page can be done on top of the
list, and you always grab the whole list in the main thread anyways. But maybe I
am missing something.

[Michael Starzinger, 2012-11-27 13:51:52]

After discussing it offline I see the point of this CL, sorry for the initial
confusion. A few high-level comments.

https://codereview.chromium.org/11348174/diff/2001/src/spaces.cc
File src/spaces.cc (right):

https://codereview.chromium.org/11348174/diff/2001/src/spaces.cc#newcode2196
src/spaces.cc:2196: static intptr_t CountFreeListItemsInList(FreeListCategorie*
categorie,
I think the code would be easier to read if the static helpers would still be
based on the FreeListNode and you would just pass in foo_list_.top into the
static helper. Same applies to the functions below.

https://codereview.chromium.org/11348174/diff/2001/src/spaces.h
File src/spaces.h (right):

https://codereview.chromium.org/11348174/diff/2001/src/spaces.h#newcode1378
src/spaces.h:1378: struct FreeListCategorie {
This should be a proper class with the helper functions as member methods. Also
naming it "FreeListCategory" is better I guess. Also some comments above the
class describing it's purpose would be nice.

https://codereview.chromium.org/11348174/diff/2001/src/spaces.h#newcode1414
src/spaces.h:1414: void Reset(struct FreeListCategorie *categorie);
Move all of these helper functions into FreeListCategory.

[Hannes Payer (out of office), 2012-11-29 13:17:41]

https://codereview.chromium.org/11348174/diff/2001/src/spaces.cc
File src/spaces.cc (right):

https://codereview.chromium.org/11348174/diff/2001/src/spaces.cc#newcode2196
src/spaces.cc:2196: static intptr_t CountFreeListItemsInList(FreeListCategorie*
categorie,
On 2012/11/27 13:51:53, Michael Starzinger wrote:
> I think the code would be easier to read if the static helpers would still be
> based on the FreeListNode and you would just pass in foo_list_.top into the
> static helper. Same applies to the functions below.

Done. Now we just call the method on the given object.

https://codereview.chromium.org/11348174/diff/2001/src/spaces.h
File src/spaces.h (right):

https://codereview.chromium.org/11348174/diff/2001/src/spaces.h#newcode1378
src/spaces.h:1378: struct FreeListCategorie {
On 2012/11/27 13:51:53, Michael Starzinger wrote:
> This should be a proper class with the helper functions as member methods.
Also
> naming it "FreeListCategory" is better I guess. Also some comments above the
> class describing it's purpose would be nice.

Done. I refactored the whole free list implementation.

https://codereview.chromium.org/11348174/diff/2001/src/spaces.h#newcode1414
src/spaces.h:1414: void Reset(struct FreeListCategorie *categorie);
On 2012/11/27 13:51:53, Michael Starzinger wrote:
> Move all of these helper functions into FreeListCategory.

Done.

[Michael Starzinger, 2012-11-29 14:31:20]

I like the new FreeListCategory class much more now. Just a few nits. The
complexity of the two concurrent operation is pretty high though.

https://codereview.chromium.org/11348174/diff/9/src/spaces.cc
File src/spaces.cc (right):

https://codereview.chromium.org/11348174/diff/9/src/spaces.cc#newcode1940
src/spaces.cc:1940: ConcatenateListsConcurrentAdd(FreeListCategory* category) {
Let's break the line after the opening parenthesis.

http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Function_Decla...

https://codereview.chromium.org/11348174/diff/9/src/spaces.cc#newcode1951
src/spaces.cc:1951: }
The adjustment category_end->next to current_top is missing.

https://codereview.chromium.org/11348174/diff/9/src/spaces.cc#newcode1965
src/spaces.cc:1965: ConcatenateListsConcurrentRemove(FreeListCategory* category)
{
Likewise.

https://codereview.chromium.org/11348174/diff/9/src/spaces.cc#newcode1978
src/spaces.cc:1978: category_top = category->top();
This requires the memory model to ensure that we don't reorder load after load.
This doesn't hold on ARM ... so I think we need a memory barrier after reading
category->top.

https://codereview.chromium.org/11348174/diff/9/src/spaces.cc#newcode1988
src/spaces.cc:1988: reinterpret_cast<AtomicWord>(category_end), 0);
Since we don't need the category->end to be in a certain state once our commit
ran through, we should just ignore it completely and let the producer fix it.

https://codereview.chromium.org/11348174/diff/9/src/spaces.cc#newcode2024
src/spaces.cc:2024: }
We need to adjust the end pointer in case you evicted the last elements (or
completely cleared the free list).

https://codereview.chromium.org/11348174/diff/9/src/spaces.cc#newcode2162
src/spaces.cc:2162: *cur = node->next();
We also need to reset the end pointer in case we picked the last entry.

https://codereview.chromium.org/11348174/diff/9/src/spaces.h
File src/spaces.h (right):

https://codereview.chromium.org/11348174/diff/9/src/spaces.h#newcode1428
src/spaces.h:1428: FreeListNode* top() const {
Let's compact the simple accessors a little by using just one line to implement
them and possibly group those that work on the same variable together (by
removing the empty newline between them).

[Hannes Payer (out of office), 2012-11-29 15:55:02]

https://codereview.chromium.org/11348174/diff/9/src/spaces.cc
File src/spaces.cc (right):

https://codereview.chromium.org/11348174/diff/9/src/spaces.cc#newcode1940
src/spaces.cc:1940: ConcatenateListsConcurrentAdd(FreeListCategory* category) {
On 2012/11/29 14:31:20, Michael Starzinger wrote:
> Let's break the line after the opening parenthesis.
> 
>
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Function_Decla...

Done.

https://codereview.chromium.org/11348174/diff/9/src/spaces.cc#newcode1951
src/spaces.cc:1951: }
On 2012/11/29 14:31:20, Michael Starzinger wrote:
> The adjustment category_end->next to current_top is missing.

Done.

https://codereview.chromium.org/11348174/diff/9/src/spaces.cc#newcode1965
src/spaces.cc:1965: ConcatenateListsConcurrentRemove(FreeListCategory* category)
{
On 2012/11/29 14:31:20, Michael Starzinger wrote:
> Likewise.

Done.

https://codereview.chromium.org/11348174/diff/9/src/spaces.cc#newcode1978
src/spaces.cc:1978: category_top = category->top();
On 2012/11/29 14:31:20, Michael Starzinger wrote:
> This requires the memory model to ensure that we don't reorder load after
load.
> This doesn't hold on ARM ... so I think we need a memory barrier after reading
> category->top.

Done.

https://codereview.chromium.org/11348174/diff/9/src/spaces.cc#newcode1988
src/spaces.cc:1988: reinterpret_cast<AtomicWord>(category_end), 0);
On 2012/11/29 14:31:20, Michael Starzinger wrote:
> Since we don't need the category->end to be in a certain state once our commit
> ran through, we should just ignore it completely and let the producer fix it.

Done.

https://codereview.chromium.org/11348174/diff/9/src/spaces.cc#newcode2024
src/spaces.cc:2024: }
On 2012/11/29 14:31:20, Michael Starzinger wrote:
> We need to adjust the end pointer in case you evicted the last elements (or
> completely cleared the free list).

Done.

https://codereview.chromium.org/11348174/diff/9/src/spaces.cc#newcode2162
src/spaces.cc:2162: *cur = node->next();
On 2012/11/29 14:31:20, Michael Starzinger wrote:
> We also need to reset the end pointer in case we picked the last entry.

Done.

https://codereview.chromium.org/11348174/diff/9/src/spaces.h
File src/spaces.h (right):

https://codereview.chromium.org/11348174/diff/9/src/spaces.h#newcode1428
src/spaces.h:1428: FreeListNode* top() const {
On 2012/11/29 14:31:20, Michael Starzinger wrote:
> Let's compact the simple accessors a little by using just one line to
implement
> them and possibly group those that work on the same variable together (by
> removing the empty newline between them).

Done.

[Hannes Payer (out of office), 2012-11-30 10:21:54]

On 2012/11/30 09:53:22, Hannes Payer wrote:

I removed the concurrent FreeList code. I propose to use a lock-based free list
for the first version of the parallel sweeper. After that we can improve.

[Michael Starzinger, 2012-12-11 10:50:41]

LGTM (if one comment is addressed).

Yes, as a first step we should use locking for the parallel sweeper. But lets
keep this a refactoring CL and _remove_ the concurrent code completely (as your
own comment suggests).

https://codereview.chromium.org/11348174/diff/23001/src/spaces.cc
File src/spaces.cc (right):

https://codereview.chromium.org/11348174/diff/23001/src/spaces.cc#newcode1934
src/spaces.cc:1934: ScopedLock lock_source(category->mutex());
This operation is grabbing two mutexes in sequence. This is just inviting a
dead-lock. Since there is no code yet that uses this functionality it is hard to
tell whether there will be a dead-lock or not. Can we please just remove this
concurrent function that is not used yet and land it together with the CL that
actually uses it? This also goes in line with our policy to not keep dead code
in the repository.

[Hannes Payer (out of office), 2012-12-11 17:10:15]

Done.

https://codereview.chromium.org/11348174/diff/23001/src/spaces.cc
File src/spaces.cc (right):

https://codereview.chromium.org/11348174/diff/23001/src/spaces.cc#newcode1934
src/spaces.cc:1934: ScopedLock lock_source(category->mutex());
On 2012/12/11 10:50:41, Michael Starzinger wrote:
> This operation is grabbing two mutexes in sequence. This is just inviting a
> dead-lock. Since there is no code yet that uses this functionality it is hard
to
> tell whether there will be a dead-lock or not. Can we please just remove this
> concurrent function that is not used yet and land it together with the CL that
> actually uses it? This also goes in line with our policy to not keep dead code
> in the repository.

OK, I removed it. The code is not going to deadlock since source and target page
can never change roles in the sweeper algorithm.