command_buffer: Implement IdAllocator by recording ranges

command_buffer: Implement IdAllocator by recording ranges

Implement IdAllocator by storing complete id ranges of (min,max) in the
map instead of just ids. This should make allocating big amount of ids
scale a bit better.

Store a range by creating a mapping first id -> last id. Upon query of
id existence, find the lowest_bound with the id interested. The hit will
be found at the returned iterator position (range starts at the id) or
the position before (range starts before the id and expands to cover
it).

Changes the allocation results so that even though client has requested
AllocateIdAtOrAbove(high_id_number), the next AllocateId() will allocate
lowest available id (instead of lowest available after
high_id_number). This is why GLES2ImplementationTest::kBuffersStartId
changes.

BUG=344330
Committed: https://crrev.com/04747ceb17fa2d7ed457e59faee01218257d9abb
Cr-Commit-Position: refs/heads/master@{#318663}

[Kimmo Kinnunen, 2014-10-31 13:56:51]

Alternative to https://codereview.chromium.org/684093008/ , if it is preferred
to use more tested std::map implementation instead of custom binary tree
algorithm.

[vmiura, 2015-01-08 19:47:15]

vmiura@chromium.org changed reviewers:
+ dyen@chromium.org, vmiura@chromium.org

[David Yen, 2015-01-15 23:24:59]

On 2014/10/31 13:56:51, Kimmo Kinnunen wrote:
> Alternative to https://codereview.chromium.org/684093008/ , if it is preferred
> to use more tested std::map implementation instead of custom binary tree
> algorithm.

I prefer the std::map one since it contains less code to maintain.

Is this ready to be reviewed? I noticed that the base is different from what is
on the chromium tree. Does it depend on another patch in flight?

[Kimmo Kinnunen, 2015-01-16 13:59:19]

On 2015/01/15 23:24:59, David Yen wrote:
> On 2014/10/31 13:56:51, Kimmo Kinnunen wrote:
> > Alternative to https://codereview.chromium.org/684093008/ , if it is
preferred
> > to use more tested std::map implementation instead of custom binary tree
> > algorithm.
> 
> I prefer the std::map one since it contains less code to maintain.
> 
> Is this ready to be reviewed? I noticed that the base is different from what
is
> on the chromium tree. Does it depend on another patch in flight?

I could rebase it on top of current trunk Chromium beginning of next week..

[Kimmo Kinnunen, 2015-01-19 14:09:02]

> On 2015/01/15 23:24:59, David Yen wrote:
> > Is this ready to be reviewed? I noticed that the base is different from what
> is
> > on the chromium tree. Does it depend on another patch in flight?

This is now ready to be reviewed, please take a look if you have time.

Note: it implements the range allocation functions that are mainly useful for
NV_path_rendering support. Also the patch is mainly useful for that, as current
content, to my tests, does not allocate that many ids.

[vmiura, 2015-02-04 07:31:55]

LGTM.

David I've checked this as thoroughly as I could but please also take a 2nd look
as the details are subtle.

[vmiura, 2015-02-04 07:32:56]

https://codereview.chromium.org/692073002/diff/20001/gpu/command_buffer/commo...
File gpu/command_buffer/common/id_allocator.cc (right):

https://codereview.chromium.org/692073002/diff/20001/gpu/command_buffer/commo...
gpu/command_buffer/common/id_allocator.cc:193: DCHECK(id);
Should we return true if (id == kInvalidResource) instead to match the old
behavior?

[Kimmo Kinnunen, 2015-02-04 08:13:09]

https://codereview.chromium.org/692073002/diff/20001/gpu/command_buffer/commo...
File gpu/command_buffer/common/id_allocator.cc (right):

https://codereview.chromium.org/692073002/diff/20001/gpu/command_buffer/commo...
gpu/command_buffer/common/id_allocator.cc:193: DCHECK(id);
On 2015/02/04 07:32:56, vmiura wrote:
> Should we return true if (id == kInvalidResource) instead to match the old
> behavior?

Whichever way you want..

The suggestion breaks the implicit API, though. As far as implicit means "least
surprise" (no valid id is allocated when allocator is newly created, no valid id
is permanent)
 
Eg: 

for any id:
  Free(id);
  expect(InUse(id) == false)

I think originally I also thought of the case where the usage pattern is:

if (InUse(id)) {
  DoOperationWithId(id);
} else {
  error("id does not exist");
}

For this pattern, check the usage in:
 GLES2Implementation::BeginQueryEXT

(Though the case could perhaps be made that instead of error, one would
frequently want to do "MarkIdUsed"...)

I think currently there's only one call-site. This call-site checks for id == 0.

[Kimmo Kinnunen, 2015-02-04 08:35:34]

On 2015/02/04 08:13:09, Kimmo Kinnunen wrote:
> for any id:
>   Free(id);
>   expect(InUse(id) == false)

Hmm. Maybe the rationale wasn't the best, since probably assert breaks the
assumption too.. 
I can of course enable InUse(0) and add a test for it.

[vmiura, 2015-02-04 16:32:45]

On 2015/02/04 08:35:34, Kimmo Kinnunen wrote:
> On 2015/02/04 08:13:09, Kimmo Kinnunen wrote:
> > for any id:
> >   Free(id);
> >   expect(InUse(id) == false)
> 
> Hmm. Maybe the rationale wasn't the best, since probably assert breaks the
> assumption too.. 
> I can of course enable InUse(0) and add a test for it.

That sounds good to me.

[David Yen, 2015-02-04 22:57:16]

lgtm with nits.

https://codereview.chromium.org/692073002/diff/20001/gpu/command_buffer/commo...
File gpu/command_buffer/common/id_allocator.cc (right):

https://codereview.chromium.org/692073002/diff/20001/gpu/command_buffer/commo...
gpu/command_buffer/common/id_allocator.cc:29: DCHECK(desired_id > 0u);
Nit: Even though 0 is a invalid ID, seems like it would be appropriate to
instead give them 1 or above if they desire 0.

https://codereview.chromium.org/692073002/diff/20001/gpu/command_buffer/commo...
gpu/command_buffer/common/id_allocator.cc:143: if (id) {
Nit: This check no longer seems necessary.

[Kimmo Kinnunen, 2015-02-05 08:28:55]

New patchsets have been uploaded after l-g-t-m from
vmiura@chromium.org,dyen@chromium.org

[Kimmo Kinnunen, 2015-02-05 08:29:33]

https://codereview.chromium.org/692073002/diff/20001/gpu/command_buffer/commo...
File gpu/command_buffer/common/id_allocator.cc (right):

https://codereview.chromium.org/692073002/diff/20001/gpu/command_buffer/commo...
gpu/command_buffer/common/id_allocator.cc:29: DCHECK(desired_id > 0u);
On 2015/02/04 22:57:16, David Yen wrote:
> Nit: Even though 0 is a invalid ID, seems like it would be appropriate to
> instead give them 1 or above if they desire 0.

Done.

https://codereview.chromium.org/692073002/diff/20001/gpu/command_buffer/commo...
gpu/command_buffer/common/id_allocator.cc:143: if (id) {
On 2015/02/04 22:57:16, David Yen wrote:
> Nit: This check no longer seems necessary.

Done.

https://codereview.chromium.org/692073002/diff/20001/gpu/command_buffer/commo...
gpu/command_buffer/common/id_allocator.cc:193: DCHECK(id);
On 2015/02/04 07:32:56, vmiura wrote:
> Should we return true if (id == kInvalidResource) instead to match the old
> behavior?

So I now changed the assert into if(). However, this changes the behavior,
InUse(0) returns always false. To me it seems a bit safer. Hope this is ok?

[vmiura, 2015-02-12 07:24:32]

> > Should we return true if (id == kInvalidResource) instead to match the old
> > behavior?
> 
> So I now changed the assert into if(). However, this changes the behavior,
> InUse(0) returns always false. To me it seems a bit safer. Hope this is ok?

As far as I can tell this is safer.  LGTM.

[Kimmo Kinnunen, 2015-03-02 06:53:06]

The CQ bit was checked by kkinnunen@nvidia.com

[Kimmo Kinnunen, 2015-03-02 06:53:07]

The patchset sent to the CQ was uploaded after l-g-t-m from vmiura@chromium.org,
dyen@chromium.org
Link to the patchset: https://codereview.chromium.org/692073002/#ps60001 (title:
"rebase")

[commit-bot: I haz the power, 2015-03-02 06:53:15]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/692073002/60001

[commit-bot: I haz the power, 2015-03-02 08:02:27]

Committed patchset #4 (id:60001)

[commit-bot: I haz the power, 2015-03-02 08:03:22]

Patchset 4 (id:??) landed as
https://crrev.com/04747ceb17fa2d7ed457e59faee01218257d9abb
Cr-Commit-Position: refs/heads/master@{#318663}