Add an IO thread index bitmap to disk cache.

Add an IO thread index bitmap to disk cache.

Keep a bitmap on the IO thread tracking which cache entries exist, to allow faster cache misses.

R=rvargas@chromium.org, felipeg@chromium.org, pasko@google.com
BUG=None

[gavinp, 2012-12-19 23:02:45]

Here's a really sketchy hacked up zero latency cache to play with.

Pull this patch down, and follow the instructions to see if it affects your
performance.

[gavinp, 2012-12-20 00:04:00]

Now control groups are more complex:

Control == don't do any fancy stuff with bitmaps.
ControlNOT == sum of all non control histograms

NoCreateControl == control group for NoCreate requests; so none of these could
fastmiss (NoCreate or NoCreateControl)

FastMissControl == control group for fastmiss requests, these can still
NoCreate.

[gavinp, 2012-12-20 16:16:42]

Merge in https://chromiumcodereview.appspot.com/11633020/ for about:flags joy

[gavinp, 2013-01-06 23:09:11]

I've rebased this to trunk, and at Egor's request, made this CL dependent on
https://chromiumcodereview.appspot.com/11633020/ , so you don't see about:flags
stuff mixed in.

I'll narrow this CL to just being the bitmap eventually, so it and the
race-on-create CL can mature together and land in their zero latency glory.

[gavinp, 2013-01-21 09:56:49]

Ricardo, Egor: PTAL.

Just uploaded patch set 12, which narrows this patch to just tracking the bitmap
on the IO thread.

It's missing one feature still: the bitmap is not cleared when a Doom drops an
entry, or a create fails. That requires a bit of cross-thread artifice since
there may be multiple operations in flight simultaneously affecting the same
bitmap entry.

No specific tests are added, but all existing tests pass. Note the subtle issues
around sparse entries: child entries aren't always in the bitmap, but _that's
ok_ since they are only ever opened synchronously from the cache thread anyway.

I find the threading in backend_impl_ fairly subtle: I don't easily understand
which members and methods are used from which thread; perhaps we could split it
into two objects at some point, each one specific to its thread?

Ricardo, what do you think of this direction? Do you have testing suggestions or
refinements? I'd like to hear back from you before circling in to get the
updates logic correct.

[rvargas (doing something else), 2013-01-22 22:31:51]

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
File net/disk_cache/backend_impl.cc (right):

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
net/disk_cache/backend_impl.cc:432: int
BackendImpl::SyncInit(scoped_refptr<base::MessageLoopProxy> async_thread) {
We should be able to do this without sending the message loop around.

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
net/disk_cache/backend_impl.cc:479: if (async_thread) {
restarted_ can be used to avoid doing something more than once.

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
net/disk_cache/backend_impl.cc:488: index_bitmap_has_been_set_.Wait();
A lock doesn't sound so good.

Initialization is protected by the contract :). The caller is not allowed to
issue any command before Init() returns. (aka the completion callback for
creation).

As such, we know that while SyncInit is running (at least when not being
restarted), there won't be any access to members from the IO thread, so this
code can init the bitmap directly.

As for the threading model of the backend, it is pretty simple: everything is
only accessible from the cache thread (after init) with two exceptions:

1. The background queue (for obvious reasons)
2. Shutdown (where we do that dance to make sure that we finish everything, wait
until done etc).

(there may be a race-y access here and there, but confined to low value/uncommon
things (like getting stats)).

Other than that, we actually work when we have only one thread, so there is some
code to detect that scenario (some unit tests) and catch mistakes.

In other words, the bitmap would be a member to be used exclusively from the IO
thread (the first "general purpose" member at that)

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
File net/disk_cache/backend_impl.h (right):

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
net/disk_cache/backend_impl.h:403: std::vector<bool> index_bitmap_;
use disk_cache::Bitmap instead.

[gavinp, 2013-01-22 23:15:47]

Thanks for the review. I will rev this advancing the bitmap corrections on the
IO thread for my next upload. I have some questions about threading practice
below that would really help me while I rev the CL.

Thaanks again!

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
File net/disk_cache/backend_impl.cc (right):

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
net/disk_cache/backend_impl.cc:432: int
BackendImpl::SyncInit(scoped_refptr<base::MessageLoopProxy> async_thread) {
On 2013/01/22 22:31:51, rvargas wrote:
> We should be able to do this without sending the message loop around.

Can you tell me more?

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
net/disk_cache/backend_impl.cc:488: index_bitmap_has_been_set_.Wait();
On 2013/01/22 22:31:51, rvargas wrote:
> A lock doesn't sound so good.
> 
> Initialization is protected by the contract :). The caller is not allowed to
> issue any command before Init() returns. (aka the completion callback for
> creation).
> 
> As such, we know that while SyncInit is running (at least when not being
> restarted), there won't be any access to members from the IO thread, so this
> code can init the bitmap directly.
> 
> As for the threading model of the backend, it is pretty simple: everything is
> only accessible from the cache thread (after init) with two exceptions:
> 
> 1. The background queue (for obvious reasons)
> 2. Shutdown (where we do that dance to make sure that we finish everything,
wait
> until done etc).
> 
> (there may be a race-y access here and there, but confined to low
value/uncommon
> things (like getting stats)).
> 
> Other than that, we actually work when we have only one thread, so there is
some
> code to detect that scenario (some unit tests) and catch mistakes.
> 
> In other words, the bitmap would be a member to be used exclusively from the
IO
> thread (the first "general purpose" member at that)

Yes, I did see that the cache is not used during Init, and so I thought this was
a very safe way to initialize it without risk of deadlock; the more conservative
PostTaskAndReply felt like overkill.

I thought the WaitLock was guaranteeing that both threads would see the same
view of the same object, and avoiding data races. What do you think of that
reasoning?

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
File net/disk_cache/backend_impl.h (right):

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
net/disk_cache/backend_impl.h:403: std::vector<bool> index_bitmap_;
On 2013/01/22 22:31:51, rvargas wrote:
> use disk_cache::Bitmap instead.

Will do!

[rvargas (doing something else), 2013-01-22 23:46:14]

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
File net/disk_cache/backend_impl.cc (right):

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
net/disk_cache/backend_impl.cc:432: int
BackendImpl::SyncInit(scoped_refptr<base::MessageLoopProxy> async_thread) {
On 2013/01/22 23:15:47, gavinp wrote:
> On 2013/01/22 22:31:51, rvargas wrote:
> > We should be able to do this without sending the message loop around.
> 
> Can you tell me more?

It seems like this is used for controlling when to init the bitmap (and
restarted_ will do that), and running stuff on the main thread (like disabling
the bitmap when the cache is actually restarted, todo).

I was overlooking the second case (I was thinking it was just a matter of
routing the call through InFlightBackendIO but that sounds like abusing the
system, even though it knows exactly what to call at any point)

Anyhow, if we need to keep another message loop as part of the backend just to
post tasks the other way around fine... we can just grab it at Init()

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
net/disk_cache/backend_impl.cc:488: index_bitmap_has_been_set_.Wait();
On 2013/01/22 23:15:47, gavinp wrote:
> On 2013/01/22 22:31:51, rvargas wrote:
> > A lock doesn't sound so good.
> > 
> > Initialization is protected by the contract :). The caller is not allowed to
> > issue any command before Init() returns. (aka the completion callback for
> > creation).
> > 
> > As such, we know that while SyncInit is running (at least when not being
> > restarted), there won't be any access to members from the IO thread, so this
> > code can init the bitmap directly.
> > 
> > As for the threading model of the backend, it is pretty simple: everything
is
> > only accessible from the cache thread (after init) with two exceptions:
> > 
> > 1. The background queue (for obvious reasons)
> > 2. Shutdown (where we do that dance to make sure that we finish everything,
> wait
> > until done etc).
> > 
> > (there may be a race-y access here and there, but confined to low
> value/uncommon
> > things (like getting stats)).
> > 
> > Other than that, we actually work when we have only one thread, so there is
> some
> > code to detect that scenario (some unit tests) and catch mistakes.
> > 
> > In other words, the bitmap would be a member to be used exclusively from the
> IO
> > thread (the first "general purpose" member at that)
> 
> Yes, I did see that the cache is not used during Init, and so I thought this
was
> a very safe way to initialize it without risk of deadlock; the more
conservative
> PostTaskAndReply felt like overkill.
> 
> I thought the WaitLock was guaranteeing that both threads would see the same
> view of the same object, and avoiding data races. What do you think of that
> reasoning?

That is correct, assuming that the second thread can move freely to use the data
regardless of the first thread. In this case, you want to make sure the bitmap
is only accessed (init) from the IO thread, but we know that it won't be used
until we return. Data consistency is taken care by PostTask (when we invoke the
callback).

[gavinp, 2013-02-09 16:46:51]

Ricardo,

This should be closer, it's a remediation to your comments. I'm working in the
meantime on catching failed Create operations and clearing the bitmap after Doom
operations that permit it.

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
File net/disk_cache/backend_impl.cc (right):

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
net/disk_cache/backend_impl.cc:432: int
BackendImpl::SyncInit(scoped_refptr<base::MessageLoopProxy> async_thread) {
On 2013/01/22 23:46:14, rvargas wrote:
> On 2013/01/22 23:15:47, gavinp wrote:
> > On 2013/01/22 22:31:51, rvargas wrote:
> > > We should be able to do this without sending the message loop around.
> > 
> > Can you tell me more?
> 
> It seems like this is used for controlling when to init the bitmap (and
> restarted_ will do that), and running stuff on the main thread (like disabling
> the bitmap when the cache is actually restarted, todo).
> 
> I was overlooking the second case (I was thinking it was just a matter of
> routing the call through InFlightBackendIO but that sounds like abusing the
> system, even though it knows exactly what to call at any point)
> 
> Anyhow, if we need to keep another message loop as part of the backend just to
> post tasks the other way around fine... we can just grab it at Init()

Now removed, since we just initialize the bitmap in our first call to SyncInit.

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
net/disk_cache/backend_impl.cc:479: if (async_thread) {
On 2013/01/22 22:31:51, rvargas wrote:
> restarted_ can be used to avoid doing something more than once.

Done.

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
net/disk_cache/backend_impl.cc:488: index_bitmap_has_been_set_.Wait();
On 2013/01/22 23:46:14, rvargas wrote:
> On 2013/01/22 23:15:47, gavinp wrote:
> > On 2013/01/22 22:31:51, rvargas wrote:
> > > A lock doesn't sound so good.
> > > 
> > > Initialization is protected by the contract :). The caller is not allowed
to
> > > issue any command before Init() returns. (aka the completion callback for
> > > creation).
> > > 
> > > As such, we know that while SyncInit is running (at least when not being
> > > restarted), there won't be any access to members from the IO thread, so
this
> > > code can init the bitmap directly.
> > > 
> > > As for the threading model of the backend, it is pretty simple: everything
> is
> > > only accessible from the cache thread (after init) with two exceptions:
> > > 
> > > 1. The background queue (for obvious reasons)
> > > 2. Shutdown (where we do that dance to make sure that we finish
everything,
> > wait
> > > until done etc).
> > > 
> > > (there may be a race-y access here and there, but confined to low
> > value/uncommon
> > > things (like getting stats)).
> > > 
> > > Other than that, we actually work when we have only one thread, so there
is
> > some
> > > code to detect that scenario (some unit tests) and catch mistakes.
> > > 
> > > In other words, the bitmap would be a member to be used exclusively from
the
> > IO
> > > thread (the first "general purpose" member at that)
> > 
> > Yes, I did see that the cache is not used during Init, and so I thought this
> was
> > a very safe way to initialize it without risk of deadlock; the more
> conservative
> > PostTaskAndReply felt like overkill.
> > 
> > I thought the WaitLock was guaranteeing that both threads would see the same
> > view of the same object, and avoiding data races. What do you think of that
> > reasoning?
> 
> That is correct, assuming that the second thread can move freely to use the
data
> regardless of the first thread. In this case, you want to make sure the bitmap
> is only accessed (init) from the IO thread, but we know that it won't be used
> until we return. Data consistency is taken care by PostTask (when we invoke
the
> callback).

Done.

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
File net/disk_cache/backend_impl.h (right):

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
net/disk_cache/backend_impl.h:403: std::vector<bool> index_bitmap_;
On 2013/01/22 22:31:51, rvargas wrote:
> use disk_cache::Bitmap instead.

Can you please tell me more about why this is preferable to the C++ library?

[rvargas (doing something else), 2013-02-12 01:58:33]

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
File net/disk_cache/backend_impl.h (right):

https://codereview.chromium.org/11649028/diff/34001/net/disk_cache/backend_im...
net/disk_cache/backend_impl.h:403: std::vector<bool> index_bitmap_;
On 2013/02/09 16:46:51, gavinp wrote:
> On 2013/01/22 22:31:51, rvargas wrote:
> > use disk_cache::Bitmap instead.
> 
> Can you please tell me more about why this is preferable to the C++ library?

In this particular instance there's probably not that much of a difference
(given that the use pattern is look up one bit, set one bit). But the full
Bitmap class is already linked for this module so it's better to reuse that code
rather than linking another implementation.

https://codereview.chromium.org/11649028/diff/48002/net/disk_cache/backend_im...
File net/disk_cache/backend_impl.cc (right):

https://codereview.chromium.org/11649028/diff/48002/net/disk_cache/backend_im...
net/disk_cache/backend_impl.cc:262: DCHECK_NE(0, bitmap.Size()) << "Call site
should provide default behaviour";
nit: Can we just have the comment in the code (reduce executable size).

https://codereview.chromium.org/11649028/diff/48002/net/disk_cache/backend_im...
net/disk_cache/backend_impl.cc:485: if (!restarted_) {
Maybe we should move this to InitBitmap()

https://codereview.chromium.org/11649028/diff/48002/net/disk_cache/backend_im...
net/disk_cache/backend_impl.cc:492: for (size_t i = 0; i <= mask_; ++i)
nit: int

https://codereview.chromium.org/11649028/diff/48002/net/disk_cache/backend_im...
net/disk_cache/backend_impl.cc:1406: if (index_bitmap_.Size() != 0 &&
!IndexBitmapLookup(index_bitmap_, key)) {
when would Size be 0?

https://codereview.chromium.org/11649028/diff/48002/net/disk_cache/backend_im...
net/disk_cache/backend_impl.cc:1407: VLOG(4) << "BackendImpl::OpenEntry missed
on bitmap";
remove tracing before checking in.

https://codereview.chromium.org/11649028/diff/48002/net/disk_cache/backend_im...
File net/disk_cache/backend_impl.h (right):

https://codereview.chromium.org/11649028/diff/48002/net/disk_cache/backend_im...
net/disk_cache/backend_impl.h:67: // |async_thread| is non null, then |bitmap_|
may be initialized on that
I'm guessing the comment is stale now.

https://codereview.chromium.org/11649028/diff/48002/net/disk_cache/entry_unit...
File net/disk_cache/entry_unittest.cc (right):

https://codereview.chromium.org/11649028/diff/48002/net/disk_cache/entry_unit...
net/disk_cache/entry_unittest.cc:2007: cache_impl_->ClearIndexBitmapForTest();
why is this needed?