722605 - AndroidGraphicBuffer whitelist uses linear search

Status: RESOLVED FIXED

(Firefox for Android Graveyard :: General, defect, P4)

Description

[James Willcox (:snorp) ([e-mail]) (he/him)]

We do a linear search on the whitelist for the device's board name. This could impact startup time if it gets to be too long. We should use a binary search or something similar.

Comment 1

[Doug Turner (:dougt)]

http://mxr.mozilla.org/mozilla-central/source/widget/android/AndroidGraphicBuffer.cpp#484

Does these have to be exact matches?

Comment 2

[James Willcox (:snorp) ([e-mail]) (he/him)]

(In reply to Doug Turner (:dougt) from comment #1)
> http://mxr.mozilla.org/mozilla-central/source/widget/android/
> AndroidGraphicBuffer.cpp#484
> 
> Does these have to be exact matches?

Uh...yeah, that would probably be more correct.

Comment 3

[Kartikaya Gupta (email:[e-mail])]

This bug hasn't moved, so I'm turning it into a mentored bug instead.

Comment 4

[Tim Stullich [:tstullich]]

Is this bug still available to be taken? If so, I would like to work on it if possible.

Comment 5

[Kartikaya Gupta (email:[e-mail])]

Yup. The code that needs to be modified is at http://mxr.mozilla.org/mozilla-central/source/widget/android/AndroidGraphicBuffer.cpp?rev=0f86bf03656b#470. You should start by building Fennec if you haven't done so already; there are instructions at https://wiki.mozilla.org/Mobile/Fennec/Android on how to get set up.

Comment 6

[Tim Stullich [:tstullich]]

Ok, cool. Fennec is being built right now so I have some downtime until it finishes. Maybe I'll get on IRC to get some questions answered in the meantime.

Comment 7

[Tim Stullich [:tstullich]]

I looked into how I could best implement binary search, but I ran into an issue. I cannot come up with a good way to ensure that I search the left or right subarray after I check whether or not the element exists in the mid point. Is there a way to extract the board name from the device so that I can compare it to the board names on the whitelist?

Comment 8

[James Willcox (:snorp) ([e-mail]) (he/him)]

The best thing here would be to use nsTArray and just use BinaryIndexOf() to find the item. No need to reinvent the wheel :)

Comment 9

[Tim Stullich [:tstullich]]

OK, that makes sense. I was not aware nsTArray could be used like that. What are some good resources to learn more about the different Classes/Data Structures that are available? I know there are the documentation pages, but if there's something more "noob" friendly that would be great.

Comment 10

[Tim Stullich [:tstullich]]

(In reply to James Willcox (:snorp) ([e-mail]) from comment #8)
> The best thing here would be to use nsTArray and just use BinaryIndexOf() to
> find the item. No need to reinvent the wheel :)
I think I have come upon a possible solution, although I am not completely sure if it is any good. I constructed an nsTArray with nsAutoString* elements but that feels like an inefficient solution to me since I am manually adding each board name, which takes up too many lines and makes everything really redundant after which I use BinaryIndexOf(). Is there a more elegant solution, that I am not seeing? I have looked through a bunch of the MDN documentation and just can't come up with anything better at the moment.

Comment 11

[Tim Stullich [:tstullich]]

Attachment: Implemented a linear search for the whitelist

Comment 12

[James Willcox (:snorp) ([e-mail]) (he/him)]

Comment on attachment 822617 [details] [diff] [review]
Implemented a linear search for the whitelist

Review of attachment 822617 [details] [diff] [review]:
-----------------------------------------------------------------

Fix the few small issues and then I think we can get this in

::: widget/android/AndroidGraphicBuffer.cpp
@@ +449,5 @@
>    nullptr
>  };
>  
> +// Build whitelist to check for board type.
> +static void _initWhiteList(nsTArray<nsString>& list)

InitWhiteList

@@ +497,5 @@
>      LOG("disallowing board '%s' due to prefs override", boardUtf8.get());
>      return true;
>    }
>  
>    // FIXME: (Bug 722605) use something better than a linear search

You can remove this comment :)

@@ +498,5 @@
>      return true;
>    }
>  
>    // FIXME: (Bug 722605) use something better than a linear search
> +  nsTArray<nsString> sListAllowed;

You should put this list in a static variable so you only have to initialize it once.

@@ +502,5 @@
> +  nsTArray<nsString> sListAllowed;
> +  int i = -1;
> +
> +  _initWhiteList(sListAllowed);
> +  

whitespace

Comment 13

[Tim Stullich [:tstullich]]

Attachment: Small fixes made based on first review.

Comment 14

[James Willcox (:snorp) ([e-mail]) (he/him)]

Comment on attachment 822804 [details] [diff] [review]
Small fixes made based on first review.

Review of attachment 822804 [details] [diff] [review]:
-----------------------------------------------------------------

::: widget/android/AndroidGraphicBuffer.cpp
@@ +486,2 @@
>    int i = -1;
> +  InitWhiteList(sListAllowed);

You only need to do this once now

Comment 15

[Tim Stullich [:tstullich]]

(In reply to James Willcox (:snorp) ([e-mail]) from comment #14)
> Comment on attachment 822804 [details] [diff] [review]
> Small fixes made based on first review.
> 
> Review of attachment 822804 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: widget/android/AndroidGraphicBuffer.cpp
> @@ +486,2 @@
> >    int i = -1;
> > +  InitWhiteList(sListAllowed);
> 
> You only need to do this once now

Oh, my mistake. Do you mean something like this static nsTArray<nsString> sListAllowed = InitWhiteList(sListAllowed); ?

Comment 16

[Tim Stullich [:tstullich]]

Attachment: Fixed static reference issue

Hopefully this changes the static reference issue. If not, I am not certain how else this issue can be resolved and I would need some further feedback.

Comment 17

[Tim Stullich [:tstullich]]

Attachment: The final patch for this bug. Includes all fixes.

Comment 18

[James Willcox (:snorp) ([e-mail]) (he/him)]

Comment on attachment 823496 [details] [diff] [review]
The final patch for this bug. Includes all fixes.

Review of attachment 823496 [details] [diff] [review]:
-----------------------------------------------------------------

Looks good :)

Comment 19

[James Willcox (:snorp) ([e-mail]) (he/him)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/d79efecfad97

Comment 20

[Tim Stullich [:tstullich]]

Attachment: Changed the Size member to Length

Comment 21

[James Willcox (:snorp) ([e-mail]) (he/him)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/ff22189c5513

Comment 22

[Simon Lindholm]

> "omap4sdp"
> "SGH-I897"
> "sgh-i997"
Oughtn't this list be case sensitively sorted?

>  int i = -1;
>  if ((i = sListAllowed.BinaryIndexOf(board)) >= 0) {
This seems to be a silent cast from unsigned to signed, better to keep it unsigned and compare against NoIndex I guess.

Comment 23

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/ff22189c5513

Comment 24

[Simon Lindholm]

> Oughtn't this list be case sensitively sorted?
Ping. Can someone verify that the whitelist still works after this change?

Comment 25

[James Willcox (:snorp) ([e-mail]) (he/him)]

(In reply to Simon Lindholm from comment #24)
> > Oughtn't this list be case sensitively sorted?
> Ping. Can someone verify that the whitelist still works after this change?

I'll look

Comment 26

[Simon Lindholm]

Any update?

Comment 27

[James Willcox (:snorp) ([e-mail]) (he/him)]

(In reply to Simon Lindholm from comment #26)
> Any update?

We don't use this code anywhere, so it hasn't been a priority.