Purge in-memory localStorage areas if the # of areas exceeds the limit

Purge in-memory localStorage areas if the # of areas exceeds the limit

BUG=178980
TEST=manual (verified the memory stops increasing at a certain level)

Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=193585

[kinuko, 2013-03-04 15:26:12]

This patch is apparently not for review, but sending this anyway for discussion.

[michaeln, 2013-03-05 00:04:46]

https://codereview.chromium.org/12398008/diff/1/content/browser/dom_storage/d...
File content/browser/dom_storage/dom_storage_message_filter.cc (right):

https://codereview.chromium.org/12398008/diff/1/content/browser/dom_storage/d...
content/browser/dom_storage/dom_storage_message_filter.cc:128: DCHECK_EQ(0,
connection_dispatching_message_for_);
Since there is an async code path for localstorage.set() to fail, not sure we
need to maintain the total mem usage in each renderer and introduce new sync
IPCs to do that.

if (using too much memory)
  Send(new DOMStorageMsg_AsyncOperationComplete(false));

We could probably define the 'using too much memory' condition out of existence
by purging individual areas from memory, no single area can be too large. Some
upper limit on the number of areas we held in memory might work w/o regard for
how large an area really is. Upon opening the <limit>+1, purge one of them. Say
100 areas max?

[kinuko, 2013-03-06 06:20:15]

(Circling more people)

Updated my rough patch.  In the newer patch we only check the browser-side
in-memory cache size and return false (unsuccessful) to setItem asynchronously.

With this new patch the filldisk.com keeps telling that it's storing data even
after it exceeds the fixed cap (512 MB), but chrome doesn't store anything
actually. (The # of subdomains doesn't increase either)

(On the other hand since this patch only cares about in-memory cache size if the
user repeatedly opens the page /w relaunch it could still eat up the disk)

This is still rough and doesn't contain any GC-ish part but can you take another
look?

Thx,

https://codereview.chromium.org/12398008/diff/1/content/browser/dom_storage/d...
File content/browser/dom_storage/dom_storage_message_filter.cc (right):

https://codereview.chromium.org/12398008/diff/1/content/browser/dom_storage/d...
content/browser/dom_storage/dom_storage_message_filter.cc:128: DCHECK_EQ(0,
connection_dispatching_message_for_);
On 2013/03/05 00:04:46, michaeln wrote:
> Since there is an async code path for localstorage.set() to fail, not sure we
> need to maintain the total mem usage in each renderer and introduce new sync
> IPCs to do that.
> 
> if (using too much memory)
>   Send(new DOMStorageMsg_AsyncOperationComplete(false));

Updated to use the async IPC.

> We could probably define the 'using too much memory' condition out of
existence
> by purging individual areas from memory, no single area can be too large. Some
> upper limit on the number of areas we held in memory might work w/o regard for
> how large an area really is. Upon opening the <limit>+1, purge one of them.
Say
> 100 areas max?

[Mike West, 2013-03-06 13:41:11]

Thanks Kinuko!

https://codereview.chromium.org/12398008/diff/7001/content/browser/dom_storag...
File content/browser/dom_storage/dom_storage_message_filter.cc (right):

https://codereview.chromium.org/12398008/diff/7001/content/browser/dom_storag...
content/browser/dom_storage/dom_storage_message_filter.cc:131: }
This would likely be fairly easy to move to DomStorageHost, as michaeln
suggested on the other patch.

https://codereview.chromium.org/12398008/diff/7001/webkit/dom_storage/dom_sto...
File webkit/dom_storage/dom_storage_context.cc (right):

https://codereview.chromium.org/12398008/diff/7001/webkit/dom_storage/dom_sto...
webkit/dom_storage/dom_storage_context.cc:450: if (total_area_size_ < 0) {
I don't see where you're updating total_area_size_ after this initial call. Am I
blind?

Ah. Now I see. You invalidate the cached size on each write. Would it be
possible to adjust the running total rather than forcing a recalculation on
set/delete/clear? That seems like it would be a significant performance
improvement over this mechanism.

[michaeln, 2013-03-06 23:14:51]

Keeping detailed track of number of bytes per area and recomputing it frequently
seems costly and overkill. We know that no given area uses more than 5M, so with
up to <n> areas in memory we're fine on memory. Avoiding the iteration of all
key/value pairs seems like a win.

And the condition of using 'too much memory' is an artifact of not reclaiming
memory we don't need. Failing operations while in that state seems like the
wrong approach.

I think our first step could be to reclaim memory from areas that are not
actually open by any page. That would effectively prevent the filldisk hackery
from crashing OOM.

To do that, seems like we could use two things...

1) The addition of a function to reclaim those unopen/inactive areas.
2) A trigger to invoke that function.

As for the trigger, what if prior to loading a new new area into memory, we
invoke that function if the number of areas currently loaded into memory exceeds
<n>. And if after doing that we still have more than <n> in memory, we invoke
the existing PurgeMemory function (which will kick most everything out
regardless of open'ness)... and then load the new area into memory.

In the filldisk case, the n+1'th area being created would kick out the first n-1
areas leaving plenty of room in memory.

WDYT?

Of course, then filldisk would succeed in filling the disk entirely :)

[michaeln, 2013-03-06 23:50:19]

Something along these lines maybe?

bool DomStorageHost::ExtractAreaValues(
    int connection_id, ValuesMap* map) {
  map->clear();
  DomStorageArea* area = GetOpenArea(connection_id);
  if (!area) {
    // TODO(michaeln): Fix crbug/134003 and return false here.
    // Until then return true to avoid crashing the renderer
    // for sending a bad message.
    return true;
  }
  if (!area->IsLoadedInMemory()) {
    namespace = GetNamespace(connection_id);;
    if (namespace->CountInMemoryAreas() > kLimit) {
      namespace->PurgeUnopenAreas();
      if (namespace->CountInMemoryAreas() > kLimit)
        namespace->PurgeMemory();
    }
  }
  area->ExtractValues(map);
  return true;
}

[kinuko, 2013-03-07 03:06:12]

(My god, I lost my long reply twice due to invalid XSRF-- makes me cry hard)

Thanks Mike & Michael.  This patch is still meant to be for discussion basis
(feel free to cut a new patch when you can/want to), and I don't like the part
iterating over areas & counting bytes at all either, I'm glad all of you had the
same feeling =)

> 1) The addition of a function to reclaim those unopen/inactive areas.

Reclaim first rather than letting requests fail sounds very reasonable, but I
also fear:
* Can a site like filldisk.com just open all of abusive pages/areas opened?
* As you noted it makes filldisuk successfully fill the entire disk.

Shouldn't we also have some last resort part to just let new requests fail when
some threshold is reached?  Like: if we get too many requests in a short period
of time etc?

> 2) A trigger to invoke that function.

Limiting by # of areas is attractive, but I again have some questions: I guess
most of sites just only store a few bytes, much less than 5M, don't they?  If
that's the case the question is if we could come up with the good reasonable
<n>?  We seem to have some UMAs-- michaell do you probably have some good idea?


On 2013/03/06 23:14:51, michaeln wrote:
> Keeping detailed track of number of bytes per area and recomputing it
frequently
> seems costly and overkill. We know that no given area uses more than 5M, so
with
> up to <n> areas in memory we're fine on memory. Avoiding the iteration of all
> key/value pairs seems like a win.
> 
> And the condition of using 'too much memory' is an artifact of not reclaiming
> memory we don't need. Failing operations while in that state seems like the
> wrong approach.
> 
> I think our first step could be to reclaim memory from areas that are not
> actually open by any page. That would effectively prevent the filldisk hackery
> from crashing OOM.
> 
> To do that, seems like we could use two things...
> 
> 1) The addition of a function to reclaim those unopen/inactive areas.
> 2) A trigger to invoke that function.
> 
> As for the trigger, what if prior to loading a new new area into memory, we
> invoke that function if the number of areas currently loaded into memory
exceeds
> <n>. And if after doing that we still have more than <n> in memory, we invoke
> the existing PurgeMemory function (which will kick most everything out
> regardless of open'ness)... and then load the new area into memory.
> 
> In the filldisk case, the n+1'th area being created would kick out the first
n-1
> areas leaving plenty of room in memory.
> 
> WDYT?
> 
> Of course, then filldisk would succeed in filling the disk entirely :)

[michaeln, 2013-03-08 21:13:59]

willchan setup a histogram that logs the size of areas in KBytes. There are some
other stats too about time to prime caches by size.
https://uma.googleplex.com/histograms/?dayCount=1&endDate=03-07-2013&version=...

//Size in KBtyes
0	12,297,386	91.81%	91.81%
1	176,551	1.32%	93.13%
2	82,575	0.62%	93.75%
3	49,199	0.37%	94.11%
4	43,504	0.32%	94.44%
5	25,080	0.19%	94.63%
6	19,703	0.15%	94.77%
7	20,687	0.15%	94.93%
8	34,810	0.26%	95.19%
9	26,876	0.20%	95.39%
11	30,656	0.23%	95.62%
13	29,454	0.22%	95.84%
15	27,070	0.20%	96.04%
18	20,279	0.15%	96.19%
21	19,362	0.14%	96.34%
25	20,637	0.15%	96.49%
29	13,507	0.10%	96.59%
34	15,382	0.11%	96.71%
40	12,629	0.09%	96.80%
47	14,942	0.11%	96.91%
55	16,363	0.12%	97.03%
65	26,206	0.20%	97.23%
76	12,261	0.09%	97.32%
89	13,143	0.10%	97.42%
105	10,494	0.08%	97.50%
124	16,693	0.12%	97.62%
146	10,408	0.08%	97.70%
172	12,775	0.10%	97.80%
202	11,756	0.09%	97.88%
238	19,838	0.15%	98.03%
280	18,251	0.14%	98.17%
329	10,788	0.08%	98.25%
387	12,883	0.10%	98.34%
455	11,405	0.09%	98.43%
535	7,811	0.06%	98.49%
630	8,428	0.06%	98.55%
741	12,732	0.10%	98.65%
872	9,952	0.07%	98.72%
1026	10,770	0.08%	98.80%
1207	72,995	0.54%	99.35%
1420	25,925	0.19%	99.54%
1671	12,508	0.09%	99.63%
1966	9,713	0.07%	99.70%
2314	8,315	0.06%	99.77%
2723	8,631	0.06%	99.83%
3204	4,450	0.03%	99.86%
3770	3,449	0.03%	99.89%
4437	14,699	0.11%	100.00%
6144	17	0.00%	100.00%

> As you noted it makes filldisuk successfully fill the entire disk.

Yup, that's the other problem. We've mostly been talking about not runnng OOM.
Two seperate problems.

[kinuko, 2013-03-11 05:08:09]

On 2013/03/08 21:13:59, michaeln wrote:
> willchan setup a histogram that logs the size of areas in KBytes. There are
some
> other stats too about time to prime caches by size.
>
https://uma.googleplex.com/histograms/?dayCount=1&endDate=03-07-2013&version=...
> 
> //Size in KBtyes
> 0	12,297,386	91.81%	91.81%
> 1	176,551	1.32%	93.13%
> 2	82,575	0.62%	93.75%
> 3	49,199	0.37%	94.11%
> 4	43,504	0.32%	94.44%
> 5	25,080	0.19%	94.63%
> 6	19,703	0.15%	94.77%
> 7	20,687	0.15%	94.93%
> 8	34,810	0.26%	95.19%
> 9	26,876	0.20%	95.39%
> 11	30,656	0.23%	95.62%
> 13	29,454	0.22%	95.84%
> 15	27,070	0.20%	96.04%
> 18	20,279	0.15%	96.19%
> 21	19,362	0.14%	96.34%
> 25	20,637	0.15%	96.49%
> 29	13,507	0.10%	96.59%
> 34	15,382	0.11%	96.71%
> 40	12,629	0.09%	96.80%
> 47	14,942	0.11%	96.91%
> 55	16,363	0.12%	97.03%
> 65	26,206	0.20%	97.23%
> 76	12,261	0.09%	97.32%
> 89	13,143	0.10%	97.42%
> 105	10,494	0.08%	97.50%
> 124	16,693	0.12%	97.62%
> 146	10,408	0.08%	97.70%
> 172	12,775	0.10%	97.80%
> 202	11,756	0.09%	97.88%
> 238	19,838	0.15%	98.03%
> 280	18,251	0.14%	98.17%
> 329	10,788	0.08%	98.25%
> 387	12,883	0.10%	98.34%
> 455	11,405	0.09%	98.43%
> 535	7,811	0.06%	98.49%
> 630	8,428	0.06%	98.55%
> 741	12,732	0.10%	98.65%
> 872	9,952	0.07%	98.72%
> 1026	10,770	0.08%	98.80%
> 1207	72,995	0.54%	99.35%
> 1420	25,925	0.19%	99.54%
> 1671	12,508	0.09%	99.63%
> 1966	9,713	0.07%	99.70%
> 2314	8,315	0.06%	99.77%
> 2723	8,631	0.06%	99.83%
> 3204	4,450	0.03%	99.86%
> 3770	3,449	0.03%	99.89%
> 4437	14,699	0.11%	100.00%
> 6144	17	0.00%	100.00%

So most of them are less than 1K?  Should we count differently for such 'small'
areas and bigger areas?

> > As you noted it makes filldisuk successfully fill the entire disk.
> 
> Yup, that's the other problem. We've mostly been talking about not runnng OOM.
> Two seperate problems.

Right, but I'm being afraid that only fixing OOM issue will make the filldisk
(in a real sense) exploit easier.  Do you have some ideas about the other
storage problem?  Given that we don't have plenty of resource to work on this
it'd be nice if we could have some quick (but reasonable) fix(es) to fix both
problems, and I'm wondering if we could use the fact that the site's behavior is
different (very spammy) from normal behavior.

[michaeln, 2013-03-11 21:12:35]

> So most of them are less than 1K?  Should we count differently for such
'small'
> areas and bigger areas?

We're free to make it as elaborate or as simple as we care to.

> Right, but I'm being afraid that only fixing OOM issue will make the filldisk
> (in a real sense) exploit easier.  Do you have some ideas about the other
> storage problem?  Given that we don't have plenty of resource to work on this
> it'd be nice if we could have some quick (but reasonable) fix(es) to fix both
> problems, and I'm wondering if we could use the fact that the site's behavior
is
> different (very spammy) from normal behavior.

A rate limit on the amt of local storage data a renderer can store could thwart
filldisk, but the author could tweek the rate at which it stores to be under the
limit. Do you have something in particular in mind?

I think we have some idea of what a good soln is to the OOM problem, but we
haven't traded ideas about implementing something that reclaims diskspace. Maybe
we get some ideas along those lines first, then decide what to do and when to do
it.

About reclaiming diskspace, we do have the GetLocalStorageUsage() function which
reports filesizes and last modified dates for each origon. Seems like that would
be in the mix. Some food for thought...

* Any time the GetLocalStorageUsage() method is called, we could take that as an
opportunity to automatically reclaim old/unused areas and actually to that prior
to return. The cookies UI invokes this method. We could schedule that method to
be called at other times too (like after N bytes of new localstorage data has
been added).
* As we start feeling disk pressure, (according to the QM), that could trigger
the reclaiming of old/unused localstorage data.

My point of view about this bug is that it's embarrassing but not terribly
critical to fix. I think genuine fixes might not be any more effort than a
'quick fix'.

[kinuko, 2013-04-04 08:29:41]

Reviving this thread... I updated the patch to purge memory when the # of areas
goes beyond the certain level. I think it's along the discussion so far, but I
haven't spent too long time on this and it might be a bit rough.  PTL thanks,

[michaeln, 2013-04-05 23:39:23]

thnx for waking this up, i think this cut at it looks promising

https://codereview.chromium.org/12398008/diff/31001/webkit/dom_storage/dom_st...
File webkit/dom_storage/dom_storage_namespace.cc (right):

https://codereview.chromium.org/12398008/diff/31001/webkit/dom_storage/dom_st...
webkit/dom_storage/dom_storage_namespace.cc:124: while (it != areas_.end()) {
There's a block of code in PurgeMemory that i think needs to be here too. The
conditional call to continue around this comment...
// Leave it alone if changes are pending

The reason is that these area instance will get deleted/unreachable after being
erased from areas_. But there may actually be a commit in flight (to be
performed on the COMMIT sequence). If a new request comes along to access that
same area prior to that commit happening, we'll read stale data on the PRIMARY
sequence. So if there is something in flight, I don't think we want to remove it
from areas_ or drop its cache.


Maybe these two methods could be consolidated

PurgeUnopened() { PurgeHelper(false); }
PurgeMemory() { PurgeHelper(true); }

void PurgeHelper(bool aggressive) {
  ...
  if (aggressive) {
    // Otherwise, we can clear caches and such.
  }
}

https://codereview.chromium.org/12398008/diff/31001/webkit/dom_storage/dom_st...
File webkit/dom_storage/dom_storage_namespace.h (right):

https://codereview.chromium.org/12398008/diff/31001/webkit/dom_storage/dom_st...
webkit/dom_storage/dom_storage_namespace.h:66: unsigned int CountInMemoryAreas()
const { return areas_.size(); }
Unfortunately, I don't think this is an accurate count. There can be 'areas' in
the set that are not loaded into memory (as in after the existing PurgeMemory()
method has been called).

[kinuko, 2013-04-10 07:04:14]

Thanks! Updated the code.

https://codereview.chromium.org/12398008/diff/31001/webkit/dom_storage/dom_st...
File webkit/dom_storage/dom_storage_namespace.cc (right):

https://codereview.chromium.org/12398008/diff/31001/webkit/dom_storage/dom_st...
webkit/dom_storage/dom_storage_namespace.cc:124: while (it != areas_.end()) {
On 2013/04/05 23:39:23, michaeln wrote:
> There's a block of code in PurgeMemory that i think needs to be here too. The
> conditional call to continue around this comment...
> // Leave it alone if changes are pending
> 
> The reason is that these area instance will get deleted/unreachable after
being
> erased from areas_. But there may actually be a commit in flight (to be
> performed on the COMMIT sequence). If a new request comes along to access that
> same area prior to that commit happening, we'll read stale data on the PRIMARY
> sequence. So if there is something in flight, I don't think we want to remove
it
> from areas_ or drop its cache.
> 
> 
> Maybe these two methods could be consolidated
> 
> PurgeUnopened() { PurgeHelper(false); }
> PurgeMemory() { PurgeHelper(true); }
> 
> void PurgeHelper(bool aggressive) {
>   ...
>   if (aggressive) {
>     // Otherwise, we can clear caches and such.
>   }
> }

Sounds good, I consolidated the two methods.

https://codereview.chromium.org/12398008/diff/31001/webkit/dom_storage/dom_st...
File webkit/dom_storage/dom_storage_namespace.h (right):

https://codereview.chromium.org/12398008/diff/31001/webkit/dom_storage/dom_st...
webkit/dom_storage/dom_storage_namespace.h:66: unsigned int CountInMemoryAreas()
const { return areas_.size(); }
On 2013/04/05 23:39:23, michaeln wrote:
> Unfortunately, I don't think this is an accurate count. There can be 'areas'
in
> the set that are not loaded into memory (as in after the existing
PurgeMemory()
> method has been called).

Good point, I changed the code to iterate over areas_ to count up areas who have
in-memory data. (Is there a better way to do this?)

[michaeln, 2013-04-10 21:28:07]

lgtm, thnx for poking at this!

[commit-bot: I haz the power, 2013-04-11 02:45:35]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/kinuko@chromium.org/12398008/85001

[commit-bot: I haz the power, 2013-04-11 06:04:58]

Change committed as 193585