Bug 110557 – DatabaseTracker::getMaxSizeForDatabase() can return an erroneously large value

• Component: WebCore Misc.
• Status: RESOLVED FIXED

[Mark Lam]

Currently DatabaseTracker::getMaxSizeForDatabase() estimates the max allowed size for a database based on the following formula:

     maxSize = quota - currentDiskUsage + databaseFileSize;

currentDiskUsage is read from the disk.  If some bug or external factor should be able to cause currentDiskUsage to be greater than quota + databaseFileSize, then maxSize will be negative and be interpreted as an unreasonably large size that far exceeds the quota.  We should fix this by adding some sanity checks to bound the maxSize just in case.

[Mark Lam]

Created attachment 189687 [details]
the fix

[Geoffrey Garen]

Comment on attachment 189687 [details]
the fix

The comment here says that we're guarding against currentUsage > quota + databaseSize. But the code says we're guarding against currentUsage > quota or databaseFileSize > quota or quota - currentUsage + databaseFileSize > quota.

The test case you created showed currentUsage > quota. The most direct way to fix that is:
if (currentUsage > quota)
    currentUsage = quota;

With that check, do any of the other checks add anything?

[Mark Lam]

(In reply to comment #2)
> (From update of attachment 189687 [details])
> The comment here says that we're guarding against currentUsage > quota + databaseSize. But the code says we're guarding against currentUsage > quota or databaseFileSize > quota or quota - currentUsage + databaseFileSize > quota.
> 
> The test case you created showed currentUsage > quota. The most direct way to fix that is:
> if (currentUsage > quota)
>     currentUsage = quota;
> 
> With that check, do any of the other checks add anything?

I'm being paranoid in case databaseFileSize somehow gets larger than quota as well.  So, I cap the maxSize to quota.

If that happens I'm telling the database that I want it to be smaller as opposed to artificially endorsing its greater than quota size.  Whether the sqlite database can shrink to the smaller size or not is a whole separate issue.

With that I can re-write the logic as:

   if (currentUsage > quota)
       currentUsage = quota;
   maxSize = quota - currentUsage + databaseFileSize;
   if (maxSize > quota)
       maxSize = quota;

If you're ok with that, I can go with that.

[Benjamin Poulain]

Comment on attachment 189687 [details]
the fix

View in context: https://bugs.webkit.org/attachment.cgi?id=189687&action=review

Can't you test this?

For example, wouldn't this go to the branch?:
1) Assign a large quota.
2) Create a giant database
3) Reduce the Quota
4) ...
5) Profit!

> Source/WebCore/ChangeLog:10
> +
> +        No new tests.
> +

Maybe add a word of explanation in the ChangeLog.

Why no test?

> Source/WebCore/Modules/webdatabase/DatabaseTracker.cpp:312
> +    // The quota comes from a configuration value while the currentUsage comes
> +    // from a measurement of the real disk usage. Let's consider a situation
> +    // where there is a bug (regardless of the source) where the currentUsage gets
> +    // unreasonably large such that currentUsage > quota + databaseSize. In that
> +    // case, maxSize, computed as (quota - currentUsage + databaseFileSize) will
> +    // be negative and will be misinterpreted as a very large number, thereby
> +    // effectively granting the database permission to grow unboundedly beyond the
> +    // quota.
> +    //
> +    // Hence, we will do some explicit checks here to guard against this, and
> +    // ensure some sanity.

I am really not a fan of this comment. It reads like you have a mysterious bug elsewhere, and instead of finding it, you just added this workaround here.
If you add an explanation here, it should be of the real use case, not a bug (regardless of the source).

[Mark Lam]

(In reply to comment #4)
> (From update of attachment 189687 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=189687&action=review
> 
> Can't you test this?
> 
> For example, wouldn't this go to the branch?:
> 1) Assign a large quota.
> 2) Create a giant database
> 3) Reduce the Quota
> 4) ...
> 5) Profit!

Thanks for your comment.

I presume you are hinting at some edge cases where the currentUsage gets so large that it becomes negative for the int64_t values I'm using.  I'm going to change the type of all the quantities to uint64_t.  With a signed int64_t, there is a theoretical possibility of an overflow of currentUsage and databaseFileSize.  In practice, I think that is unrealistic.  Regardless, it is a much stronger position to use unsigned values and not have to deal with the overflow conditions.

If you are trying to hint at something else other than this, please enlighten me.  Thanks.

> > Source/WebCore/ChangeLog:10
> > +
> > +        No new tests.
> > +
> 
> Maybe add a word of explanation in the ChangeLog.
> 
> Why no test?

No test because this is a trivial change, time is limited, and my time is better spent on fixing the real bug (which is not the purpose of this patch ... see below).
 
> > Source/WebCore/Modules/webdatabase/DatabaseTracker.cpp:312
> > +    // The quota comes from a configuration value while the currentUsage comes
> > +    // from a measurement of the real disk usage. Let's consider a situation
> > +    // where there is a bug (regardless of the source) where the currentUsage gets
> > +    // unreasonably large such that currentUsage > quota + databaseSize. In that
> > +    // case, maxSize, computed as (quota - currentUsage + databaseFileSize) will
> > +    // be negative and will be misinterpreted as a very large number, thereby
> > +    // effectively granting the database permission to grow unboundedly beyond the
> > +    // quota.
> > +    //
> > +    // Hence, we will do some explicit checks here to guard against this, and
> > +    // ensure some sanity.
> 
> I am really not a fan of this comment. It reads like you have a mysterious bug elsewhere, and instead of finding it, you just added this workaround here.
> If you add an explanation here, it should be of the real use case, not a bug (regardless of the source).

I purposely did not talk about the real bug (not because I didn't know what it is, but) because it is not the intent of this patch to fix the bug.  I am working on the fix for the real bug in a separate effort.  The intent of this patch is to provide a sanity check that enforces the contract of the function DatabaseTracker::getMaxSizeOfDatabase().  My understanding of the contract is that the size of the database should not be allowed to grow to exceed the quota for its domain origin.

Hence, the checks added in my patch ensures that:
1. the estimated allowed growth (i.e. quota - currentUsage) is reasonable (i.e. quota - currentUsage <= quota, i.e. current <= quota).
2. the returned value of "max size of database" is reasonable (i.e. maxSize <= quota).

For realistic values of quota, currentUsage, and databaseFileSize, I believe the logic of the patch is sound.  A realistic value of currentUsage and databaseSize in this case does not include them being so large that they overflow into negative values (though I've not explained why here).  But I agree that it is better to make them unsigned and just avoid even the possibility of complications due to overflow.

Note: "quota" is expected to come from a trusted source and is a sane value (hence, my mentioning "configuration value").  "currentUsage" and "databaseFileSize" is not to be trusted.  If the damage is already done by someone else to get a currentUsage and/or databaseFileSize that is larger than we should allow, it is not the role of DatabaseTracker::getMaxSizeOfDatabase() to fix that (i.e. reduce it, or prevent it) nor does it have any ability to.  The fix for such an issue lies elsewhere.  However, it is the role of DatabaseTracker::getMaxSizeOfDatabase() to compute what it considers to be a sane estimate of the max size of the database in question.  

As for the comment, I intended it to give some context and motivation for why the sanity checks are meaningful.  It is not appropriate to document the specific bug I'm guarding against here just because it happens to be the instance that pointed out that we could use some defensive coding here in DatabaseTracker::getMaxSizeOfDatabase(). That said, I could probably write it better so as to not give the wrong impression that I'm just trying to band-aid a bug here.  I'll look into how I can do that.

[Mark Lam]

(In reply to comment #5)
> > Why no test?
> 
> No test because this is a trivial change, time is limited, and my time is better spent on fixing the real bug (which is not the purpose of this patch ... see below).

Ok, that wasn't an appropriate answer.  Let me provide some more details as to why I'm choosing to not implement a layout test that checks for the specific bug that I'm working on fixing:

1. There are already existing tests that check the quota functionality in general:

    storage/websql/open-database-over-quota.html: tests quota enforcement when opening databases.
    storage/websql/quota-tracking.html: tests quota enforcement when writing records. 

    However, these only tests quota management for the single process scenario.

2. I could be wrong but I don't think we have a test harness for executing multi-process stress tests yet. 

That said, while I don't have a layout test to add, I do have a test that I do run by hand to verify the existence of the error condition (with the help of instrumented logging), and then to verify the fix.


> I purposely did not talk about the real bug (not because I didn't know what it is, but) because it is not the intent of this patch to fix the bug.  I am working on the fix for the real bug in a separate effort.

FYI, the "real" bug that highlighted the need for the sanity check in this patch is at https://bugs.webkit.org/show_bug.cgi?id=110600.  Again, unlike bug 110600, this bug, 110557, is only intended to put in place a sanity check that enforces the contract of DatabaseTracker::getMaxSizeForDatabase().  It is a defensive maneuver to limit the damage that 110600 (and potentially other bugs like it in the future) can cause.

[Geoffrey Garen]

> I purposely did not talk about the real bug....

I have to agree with Ben: There's no way to understand this code without direct explanation of what it fixes.

The bug we're trying to fix is this: If any bug anywhere ever allows an origin to exceed its quota, even by a byte, the origin will thereafter exceed its quota by 2^64. 

> I'm being paranoid in case databaseFileSize somehow gets larger than quota as well.

Paranoia is fear of the unknown. Fear is the mindkiller. Let's not litter our code with fear. Instead, let's document the known things we're trying to fix.

Total disk usage for this origin may be greater than quota. Total disk usage is a superset of this individual database's usage, so checking total disk usage is sufficient. How about this:

unsigned long long quota = quotaForOriginNoLock(origin);
unsigned long long diskUsage = originQuotaManager().diskUsage(origin);
unsigned long long databaseFileSize = SQLiteFileSystem::getDatabaseFileSize(database->fileName());

// A previous error may have allowed the database to exceed its quota. Don't multiply that error through
// integer underflow, or the quota will permanently become 2^64.
if (diskUsage > quota)
    return 0;
ASSERT(databaseFileSize < diskUsage);

return quota - diskUsage + databaseFileSize;

[Mark Lam]

(In reply to comment #7)
> if (diskUsage > quota)
>     return 0;
> ASSERT(databaseFileSize < diskUsage);
> 
> return quota - diskUsage + databaseFileSize;

That won't work.  Here's why: diskUsage comes from OriginUsageManager::diskUsage() which uses a cached value from a stat of the filesystem.  The cached value will remain in use as long as the current process hasn't executed a database action that invalidates it.  On the other hand, databaseFileSize comes from SQLiteFileSystem::getDatabaseFileSize() which is a stat of the database file every time.

So, imagine a scenario where process P1 and P2 both opens a database with the same name.  P1 cached the diskUsage at one time and didn't execute any action that invalidates it till now.  Meanwhile P2 has been busy adding more data to the database file thereby increasing its size.

And then in P1, we get to this code in  getMaxSizeForDatabase().  P1 uses its cached diskUsage (which at one time is greater then databaseFileSize) and fetches the current databaseFileSize (which P2 has been pumping up).  The result the databaseFileSize can be greater than diskUsage.

So, how about we do this instead:

unsigned long long quota = quotaForOriginNoLock(origin);
unsigned long long diskUsage = originQuotaManager().diskUsage(origin);
unsigned long long databaseFileSize = SQLiteFileSystem::getDatabaseFileSize(database->fileName());

// A previous error may have allowed the database to exceed its quota. Don't multiply that error through
// integer underflow, or the quota will permanently become 2^64.
if (diskUsage > quota)
    return 0;
unsigned long long maxSize = quota - diskUsage + databaseFileSize;
if (maxSize > quota)
    return 0;
return maxSize;

[Geoffrey Garen]

> That won't work.  Here's why:

Great! Now we're making progress with specifics.

> So, how about we do this instead:
> 
> unsigned long long quota = quotaForOriginNoLock(origin);
> unsigned long long diskUsage = originQuotaManager().diskUsage(origin);
> unsigned long long databaseFileSize = SQLiteFileSystem::getDatabaseFileSize(database->fileName());
> 
> // A previous error may have allowed the database to exceed its quota. Don't multiply that error through
> // integer underflow, or the quota will permanently become 2^64.
> if (diskUsage > quota)
>     return 0;
> unsigned long long maxSize = quota - diskUsage + databaseFileSize;
> if (maxSize > quota)
>     return 0;
> return maxSize;

I think this would be slightly clearer like so:

// A previous error may have allowed the origin to exceed its quota, or may have allowed this database
// to exceed our cached estimate of the origin. Don't multiply that error through integer underflow, or
// the quota will permanently become 2^64.
unsigned long long maxSize = quota - diskUsage + databaseFileSize;
if (maxSize > quota)
    return 0;
return maxSize;

I updated the comment to mention the two specific errors we're concerned about, and I changed the code not to test for disUsage specifically, since the only real protection we're providing here is against underflow of maxSize.

[Mark Lam]

Created attachment 189821 [details]
Test for opening a randomly named database and consuming storage space.

[Mark Lam]

Created attachment 189822 [details]
updated fix.

[Geoffrey Garen]

Comment on attachment 189822 [details]
updated fix.

r=me

[Mark Lam]

Thanks for the review.  Landed in r143791: <http://trac.webkit.org/changeset/143791>.

[Mark Lam]

<rdar://problem/13260686>

[Mark Lam]

The value returned by DatabaseTracker::getMaxSizeForDatabase() is used to set the SQLite3 database size using a sql command "PRAGMA max_page_count = <size>”.  The SQLite3 documentation on this pragma says, "The maximum page count cannot be reduced below the current database size."

It is undefined what will happen if we set the sqlite max_page_count to 0.  However, further testing shows that having getMaxSizeForDatabase() return a 0 (when a quota breach is detected), proves to be ineffective at stopping runaway database growth.  In contrast, having getMaxSizeForDatabase() return the size of the existing database seems to do the job.

In the interest of time, I’m proposing to not dive into the SQLite3 code at this time to figure out the specifics.  I believe it is reasonable to have getMaxSizeForDatabase() return the current size when the quota limit has been reached, and testing shows that it works so far.  Unless we have more data that say we should do otherwise, I propose going with this solution for the present, and perhaps dig further into the SQLite3 library for details at a later time.

Note: here are some testing data points that guided me to this conclusion:

When the quota limit has been reached, I tried having getMaxSizeForDatabase() return various values:

Value returned  Reason for value           Result
=========  ==========           ====
0                       current approach          Fails to stop growth.
1024                 < sqlite page size         Fails to stop growth.
2048                 < sqlite page size         Fails to stop growth.
2048                 < sqlite page size         Fails to stop growth.
3072                 < sqlite page size         Fails to stop growth.
4096                 1 page                          Growth stops.
actual DB size    return current size       Growth stops.

SQLiteDatabase::setMaximumSize() calculates the max page count (for the pragma) by dividing the new max database size by the page size.  Hence, anything less than 4096 will effectively set a max page count of 0, and that has proven consistently to fail to stop the growth.  While returning the page size 4096 seems to work, that seems like a somewhat arbitrary value to have getMaxSizeForDatabase() return.  The most meaningful return value would be the current database size.

[Mark Lam]

Created attachment 190085 [details]
Patch for returning current database size instead of 0.

[Mark Lam]

Comment on attachment 190085 [details]
Patch for returning current database size instead of 0.

View in context: https://bugs.webkit.org/attachment.cgi?id=190085&action=review

> Source/WebCore/ChangeLog:4
> +        to return the previous database size instead of 0.

That doesn’t read well.  I’ll change this to “Changed DatabaseTracker::getMaxSizeForDatabase() to return the previous database size instead of 0 when the quota limit has been reached.”

[Geoffrey Garen]

Comment on attachment 190085 [details]
Patch for returning current database size instead of 0.

r=me

[Mark Lam]

Thanks for the review.  Landed in r143954: <http://trac.webkit.org/changeset/143954>.