Implement circular queues for the C++ version of CPU profiler.

Implement circular queues for the C++ version of CPU profiler.

Circular queues serve as a transport for communicating between
VM, stack sampler and analyzer threads. Logging requirements
for VM and stack sampler are completely different, that's why
I introduced two different versions of CQs.

Committed: http://code.google.com/p/v8/source/detail?r=4159

[Søren Thygesen Gjesse, 2010-03-17 09:28:07]

LGTM

Please consider adding functions to platform.h for atomic operations to make
this explicit. Chromium has some in base/atomicops_*.

http://codereview.chromium.org/1047002/diff/1/3
File src/circular-queue-inl.h (right):

http://codereview.chromium.org/1047002/diff/1/3#newcode88
src/circular-queue-inl.h:88: Thread::SetThreadLocal(producer_key_, enqueue_pos +
kRecordSize);
Is the producer supposed to check for full queue if start of chink does not
contain kClear. The producer should then use an atomic operation for that?

http://codereview.chromium.org/1047002/diff/1/4
File src/circular-queue.cc (right):

http://codereview.chromium.org/1047002/diff/1/4#newcode96
src/circular-queue.cc:96: } else {
ASSERT(cp->dequeue_chunk_poll_pos % kChunkSize == 0)?

Also We are assuming that reading *cp->dequeue_chunk_poll_pos is an atomic
operation, right?

http://codereview.chromium.org/1047002/diff/1/4#newcode114
src/circular-queue.cc:114: cp->dequeue_pos = NULL;
We are assuming that this assignment (*cp->dequeue_chunk_pos = kClear) is an
atomic operation, right?

http://codereview.chromium.org/1047002/diff/1/5
File src/circular-queue.h (right):

http://codereview.chromium.org/1047002/diff/1/5#newcode76
src/circular-queue.h:76: void SetUpProducer();
Please add a comment as to how Enqueue works.

http://codereview.chromium.org/1047002/diff/1/5#newcode81
src/circular-queue.h:81: void SetUpConsumer();
Please add a comment to how StartDequeue/FinishDequeue work together.

http://codereview.chromium.org/1047002/diff/1/5#newcode103
src/circular-queue.h:103: static const Cell kMagic = -1;  // Marks the end of
the buffer.
kMagic -> kLastChunk?

http://codereview.chromium.org/1047002/diff/1/5#newcode104
src/circular-queue.h:104: 
Please use only kXXX names for compile-time constants.

http://codereview.chromium.org/1047002/diff/1/7
File test/cctest/test-circular-queue.cc (right):

http://codereview.chromium.org/1047002/diff/1/7#newcode67
test/cctest/test-circular-queue.cc:67: // Fill up the first chunk.
Please add a comment why these test loops start at 1 and not 0.

http://codereview.chromium.org/1047002/diff/1/7#newcode104
test/cctest/test-circular-queue.cc:104: 
Please add a comment here on what FlushResidualRecords does.

What happens if the producer tries to enqueue after FlushResidualRecords has
been called?

[mnaganov (inactive), 2010-03-17 10:52:57]

I added a typedef for AtomicWord into platform.h

http://codereview.chromium.org/1047002/diff/1/3
File src/circular-queue-inl.h (right):

http://codereview.chromium.org/1047002/diff/1/3#newcode88
src/circular-queue-inl.h:88: Thread::SetThreadLocal(producer_key_, enqueue_pos +
kRecordSize);
On 2010/03/17 09:28:07, Søren Gjesse wrote:
> Is the producer supposed to check for full queue if start of chink does not
> contain kClear. The producer should then use an atomic operation for that?

Producer doesn't check for queue fullness -- as it is stated in
SamplingCircularQueue it just writes over old data.

http://codereview.chromium.org/1047002/diff/1/4
File src/circular-queue.cc (right):

http://codereview.chromium.org/1047002/diff/1/4#newcode96
src/circular-queue.cc:96: } else {
On 2010/03/17 09:28:07, Søren Gjesse wrote:
> ASSERT(cp->dequeue_chunk_poll_pos % kChunkSize == 0)?
>

I think this is redundant, as dequeue_chunk_pos and dequeue_chunk_poll_pos are
always incremented by kChunkSize.
 
> Also We are assuming that reading *cp->dequeue_chunk_poll_pos is an atomic
> operation, right?

I assume that reads and writes of naturally aligned native types are atomic
(that, is no other thread can see a partially written value.) I use 'intptr_t'
type for buffer cells.

More interesting questions are:
 - how can we guarantee, that if a consumer sees !kClear two chunks ahead, it
can assume that the current chunk has been filled up by a producer?
 - and, what if producer had been rolled over the buffer and is now writing to a
chunk from which consumer is currently reading?

As for the first question, I think it is guaranteed by having chunks of
significant sizes. I plan to use 64K chunks. Producer writes sequentally, and we
have a separating chunk between the chunk used by consumer, and the chunk that
it polls.

As for the second question -- this really can result in a corrupted record. But
as I use it for stack samples, it's OK to have it broken, since we never
dereference addresses from stack samples, and only process them as data. But I
really need to add a disclaimer into class description.

http://codereview.chromium.org/1047002/diff/1/4#newcode114
src/circular-queue.cc:114: cp->dequeue_pos = NULL;
On 2010/03/17 09:28:07, Søren Gjesse wrote:
> We are assuming that this assignment (*cp->dequeue_chunk_pos = kClear) is an
> atomic operation, right?

See previous comment.

http://codereview.chromium.org/1047002/diff/1/5
File src/circular-queue.h (right):

http://codereview.chromium.org/1047002/diff/1/5#newcode76
src/circular-queue.h:76: void SetUpProducer();
On 2010/03/17 09:28:07, Søren Gjesse wrote:
> Please add a comment as to how Enqueue works.

Done.

http://codereview.chromium.org/1047002/diff/1/5#newcode81
src/circular-queue.h:81: void SetUpConsumer();
On 2010/03/17 09:28:07, Søren Gjesse wrote:
> Please add a comment to how StartDequeue/FinishDequeue work together.

Done.

http://codereview.chromium.org/1047002/diff/1/5#newcode103
src/circular-queue.h:103: static const Cell kMagic = -1;  // Marks the end of
the buffer.
On 2010/03/17 09:28:07, Søren Gjesse wrote:
> kMagic -> kLastChunk?

kEnd. In the end of the buffer, there is only one cell, not a whole chunk.

http://codereview.chromium.org/1047002/diff/1/5#newcode104
src/circular-queue.h:104: 
On 2010/03/17 09:28:07, Søren Gjesse wrote:
> Please use only kXXX names for compile-time constants.

Fixed. I was in doubt about it.

http://codereview.chromium.org/1047002/diff/1/7
File test/cctest/test-circular-queue.cc (right):

http://codereview.chromium.org/1047002/diff/1/7#newcode67
test/cctest/test-circular-queue.cc:67: // Fill up the first chunk.
On 2010/03/17 09:28:07, Søren Gjesse wrote:
> Please add a comment why these test loops start at 1 and not 0.

I moved reserved values public, and added CHECKs.

http://codereview.chromium.org/1047002/diff/1/7#newcode104
test/cctest/test-circular-queue.cc:104: 
On 2010/03/17 09:28:07, Søren Gjesse wrote:
> Please add a comment here on what FlushResidualRecords does.
> 

Done.

> What happens if the producer tries to enqueue after FlushResidualRecords has
> been called?

Nothing scary. It will enqueue as usual. The only difference is that a consumer
will not wait for next two chunks to be touched by a producer.