I spend some time digging into this case, and to my mind the eviction does not work as it should.

As I understand, we should remove LN cookies not more than the quota, then LN + MN  not more than the quota, then LN+MN+HN  not more than the quota. Thus, we will not have any issues with too many LN or MN cookies deleted.

For example, this test is just adjusted to the code according to the current implementation.
Round 1 => 10L; round 2 => 11M, 10L; round 3 => none.
    TestPriorityCookieCase(cm.get(), "11HN 10MN 20LN 110MN 20LN 10HN", 20U,
                           109U, 21U, 150U, 0U); - it does not fail and does not preserve the quota

But TestPriorityCookieCase(cm.get(), "11HN 10MN 110MN 20LN 20LN 10HN", 30U,
                           109U, 21U, 150U, 0U); 
will behave differently. It goes like this - Round 1 => 10L; round 2 => 21M; round 3 => none. Having at least 30 LN, at least 50 MN (we can't have at least 70 HN, because we lacked many of them before the eviction).

Shouldn't that be right? After the eviction we should have at least 30 LN, 50 MN and 70 HN according to the quota. 

Right, I believe you've summed up what I was trying to get at in the original comment. Also note that a week ago I put in a comment explaining this issue (and linking here) with a commented out example that would fail in today's code (see the TODO comment at https://code.google.com/p/chromium/codesearch#chromium/src/net/cookies/cookie_monster_unittest.cc&l=602)

We would expect the following test to pass:
// Round 1 => 20L; round 2 => 0; round 3 => 11H
TestPriorityCookieCase(cm.get(), "50LN 131HN", 30U, 0U, 120U, 150U, 0U);

But it fails today, resulting in 19L and 131L for all of the reasons cited above. I think you point out a good example of another test we have that passes "incorrectly" according to the spec.

I have a draft cl to be uploaded with the solution according to my thoughts. I will upload that in a while.

I added you as a reviewer. Please take a look. 

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/fe1fea6df040fff38a3a4567e20a3d5847e83170

commit fe1fea6df040fff38a3a4567e20a3d5847e83170
Author: maksim.sisov <maksim.sisov@intel.com>
Date: Mon Jun 06 16:48:25 2016

Making cookies eviction quotas match spec

According to the section 3 and section 5 in
https://tools.ietf.org/html/draft-west-cookie-priority-
00#section-3, the old cookie monster implementation doesn't
maintain priority quotas correctly.

This CL makes sure there will always be at least 30 low
priority cookies, 50 mid priority and 70 high priority
cookies if there had been enough of them before  the eviction.
Please note, secure cookies are more important than non-secure
per https://tools.ietf.org/html/draft-west-leave-secure-cookies-alone.

A small example: if there are 70 cookies:
37 non-secure low priority and 33 secure low priority
cookies, 37 non-secure cookies are deleted during the first
round and other 3 secure low priority cookies are deleted
during the following round preserving 30 low priority
cookies according to the quota of those specific cookies.
For a bigger example that fully complies with the
implementation, check the unittests.

Before the fix, the unittests were just adjusted to the
behavior of cookies eviction.

For example, if we take the following unittest:
Round 1 => 10L; round 2 => 11M, 10L; round 3 => none.
TestPriorityCookieCase(cm.get(), "11HN 10MN 20LN 110MN 20LN
10HN", 20U,109U, 21U, 150U, 0U);
The problem here was that there were only 40 low priority
cookies, but the quota was not preserved for those cookies.
First, 10 low priority cookies were deleted and then more 10
low priority cookies were deleted leaving only 20 of them,
which was less than the quota (30 low priority cookies).
It happened because the eviction algorithm didn't know how
many cookies of a specific priority were deleted and
it had always started to delete all the cookies from the
beginning of the container removing even those cookies
that shouldn't have been deleted.

After we land this CL, we can have cookies in any order and
high priority cookies will be eventually deleted in order
to avoid excess of high priority cookies by some
applications within the same domain. Thus, after the
eviction algorithm runs, we should have at least 30 low, 50
mid and 70 high priority cookies if we had sufficient
amount of them in the beginning.

BUG= 609550 

Review-Url: https://codereview.chromium.org/1976073002
Cr-Commit-Position: refs/heads/master@{#398049}

[modify] https://crrev.com/fe1fea6df040fff38a3a4567e20a3d5847e83170/net/cookies/cookie_monster.cc
[modify] https://crrev.com/fe1fea6df040fff38a3a4567e20a3d5847e83170/net/cookies/cookie_monster_unittest.cc

Thanks, Maksim, for the hard work on this!

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/b89069d3f1167269aaf9fd117e743858475c3a37

commit b89069d3f1167269aaf9fd117e743858475c3a37
Author: mmenke <mmenke@chromium.org>
Date: Wed Jun 15 18:39:47 2016

Revert of Making cookies eviction quotas match spec (patchset #5 id:180001 of https://codereview.chromium.org/1976073002/ )

Reason for revert:
Experimentally reverting, seems to have possibly caused a perf regression.  See  https://crbug.com/618679 

Original issue's description:
> Making cookies eviction quotas match spec
>
> According to the section 3 and section 5 in
> https://tools.ietf.org/html/draft-west-cookie-priority-
> 00#section-3, the old cookie monster implementation doesn't
> maintain priority quotas correctly.
>
> This CL makes sure there will always be at least 30 low
> priority cookies, 50 mid priority and 70 high priority
> cookies if there had been enough of them before  the eviction.
> Please note, secure cookies are more important than non-secure
> per https://tools.ietf.org/html/draft-west-leave-secure-cookies-alone.
>
> A small example: if there are 70 cookies:
> 37 non-secure low priority and 33 secure low priority
> cookies, 37 non-secure cookies are deleted during the first
> round and other 3 secure low priority cookies are deleted
> during the following round preserving 30 low priority
> cookies according to the quota of those specific cookies.
> For a bigger example that fully complies with the
> implementation, check the unittests.
>
> Before the fix, the unittests were just adjusted to the
> behavior of cookies eviction.
>
> For example, if we take the following unittest:
> Round 1 => 10L; round 2 => 11M, 10L; round 3 => none.
> TestPriorityCookieCase(cm.get(), "11HN 10MN 20LN 110MN 20LN
> 10HN", 20U,109U, 21U, 150U, 0U);
> The problem here was that there were only 40 low priority
> cookies, but the quota was not preserved for those cookies.
> First, 10 low priority cookies were deleted and then more 10
> low priority cookies were deleted leaving only 20 of them,
> which was less than the quota (30 low priority cookies).
> It happened because the eviction algorithm didn't know how
> many cookies of a specific priority were deleted and
> it had always started to delete all the cookies from the
> beginning of the container removing even those cookies
> that shouldn't have been deleted.
>
> After we land this CL, we can have cookies in any order and
> high priority cookies will be eventually deleted in order
> to avoid excess of high priority cookies by some
> applications within the same domain. Thus, after the
> eviction algorithm runs, we should have at least 30 low, 50
> mid and 70 high priority cookies if we had sufficient
> amount of them in the beginning.
>
> BUG= 609550 
>
> Committed: https://crrev.com/fe1fea6df040fff38a3a4567e20a3d5847e83170
> Cr-Commit-Position: refs/heads/master@{#398049}

TBR=jww@chromium.org,mkwst@chromium.org,maksim.sisov@intel.com
# Not skipping CQ checks because original CL landed more than 1 days ago.
BUG= 609550 

Review-Url: https://codereview.chromium.org/2071593002
Cr-Commit-Position: refs/heads/master@{#399971}

[modify] https://crrev.com/b89069d3f1167269aaf9fd117e743858475c3a37/net/cookies/cookie_monster.cc
[modify] https://crrev.com/b89069d3f1167269aaf9fd117e743858475c3a37/net/cookies/cookie_monster_unittest.cc