First part to fix Bug 50726 "Save extension list and "winning" prefs from extensions"

The goal of this patch is to ensure that Chrome maintains the order in which extensions apply their preferences between restarts. This may be an issue if two extensions overwrite each others preferences. 

ExtensionPrefs has been extended to store and retrieve an ordered list of extension IDs, that correspond to the precedences of extensions. Extensions that appear further to the end of the list may override settings of extension closer to the beginning of the list. 

ExtensionPrefStore has been extended to use this storage capability and maintain the precedences according to the installation order. Newly installed extensions have a higher precedence than previously installed extensions. Upon restart of Chrome, the precedences are preserved. 

There is currently no code that uses the ExtensionPrefStore except for the unfinished Proxy API. This makes manual testing difficult. 

This is an alternative implementation to issue 4111015, http://codereview.chromium.org/4111015/show

The difference: The datastructure of extension_stack_ has been modified. The key is no longer an |Extension *| but now an extension_id. This enables a simpler approach to achieve deterministic extension precedences.

The extension_stack_ is lazily initialized the first time an extension preference is registered. At that time we put empty dictionaries in the right order onto the extension_stack_ (right order = respecting the precedences). This guarantees the precedence and does not require sorting the extension_stack_ as in CL 4111015.

Advantage of this approach:
- simpler (no sorting)
- simpler to extend so that previously winning prefs can be restored

Disadvantage of this approach:
- comparison of extension ids is more expensive than comparison of pointers, but this should not be performance critical anyway

Contributed by battre@google.com

BUG=50726
TEST=none

[battre (please use the other), 2010-11-03 23:09:16]

Hi Bernhard,

this is an alternative implementation to CL 4111015 with the approach discussed
on GTalk today. Both 4111015 and 4438001 LGTM now, so the question is whether
they LGTY. :-)

4438001 had to change one design decision taken by Pam:
I went from
ExtensionPrefs(Extension* extension, PrefValueMap* values);
to
ExtensionPrefs(const std::string& extension_id, PrefValueMap* values);

This change was necessary for the lazy initialization. By this change we lose
some information (the pointer to the full extension) that is not used in the
current implementation.

After all 4438001 looks better to me.

Best,
Dominic

[Pam (message me for reviews), 2010-11-04 11:58:48]

http://codereview.chromium.org/4438001/diff/8001/9002
File chrome/browser/extensions/extension_pref_store.h (right):

http://codereview.chromium.org/4438001/diff/8001/9002#newcode123
chrome/browser/extensions/extension_pref_store.h:123: ExtensionPrefs(const
std::string& extension_id, PrefValueMap* values);
The problem is that extension IDs are not guaranteed to be unique. They're
unique per profile, but the local-state ExtensionPrefStore watches all profiles.
If two extensions both want to control some machine-wide pref, there could be a
collision.

[Bernhard Bauer, 2010-11-04 16:03:37]

http://codereview.chromium.org/4438001/diff/8001/9001
File chrome/browser/extensions/extension_pref_store.cc (right):

http://codereview.chromium.org/4438001/diff/8001/9001#newcode215
chrome/browser/extensions/extension_pref_store.cc:215: }
Nit: The usual way for these sanity checks is DCHECK(!already_present) << "Error
message"

http://codereview.chromium.org/4438001/diff/8001/9001#newcode233
chrome/browser/extensions/extension_pref_store.cc:233: return;  // we have
initialized this already
LazyInit should only be called if the stack is empty anyway.

http://codereview.chromium.org/4438001/diff/8001/9002
File chrome/browser/extensions/extension_pref_store.h (right):

http://codereview.chromium.org/4438001/diff/8001/9002#newcode123
chrome/browser/extensions/extension_pref_store.h:123: ExtensionPrefs(const
std::string& extension_id, PrefValueMap* values);
On 2010/11/04 11:58:48, Pam wrote:
> The problem is that extension IDs are not guaranteed to be unique. They're
> unique per profile, but the local-state ExtensionPrefStore watches all
profiles.
> If two extensions both want to control some machine-wide pref, there could be
a
> collision.

Hm, doesn't that mean that saving the ID of the "winning" extension is not
actually sufficient? What should we use to identify an extension instead?

I think the easiest way to fix this would be just to disallow extensions from
setting local state preferences.

[battre (please use the other), 2010-11-04 21:24:59]

Hi Bernhard,

I have addressed the comments (see below).

Pam did not do a full review but says it is your call whether the CL is good to
commit.

Best regards,

Dominic

http://codereview.chromium.org/4438001/diff/8001/9001
File chrome/browser/extensions/extension_pref_store.cc (right):

http://codereview.chromium.org/4438001/diff/8001/9001#newcode215
chrome/browser/extensions/extension_pref_store.cc:215: }
On 2010/11/04 16:03:37, Bernhard Bauer wrote:
> Nit: The usual way for these sanity checks is DCHECK(!already_present) <<
"Error
> message"

Done.

http://codereview.chromium.org/4438001/diff/8001/9001#newcode233
chrome/browser/extensions/extension_pref_store.cc:233: return;  // we have
initialized this already
On 2010/11/04 16:03:37, Bernhard Bauer wrote:
> LazyInit should only be called if the stack is empty anyway.

Done.

http://codereview.chromium.org/4438001/diff/8001/9002
File chrome/browser/extensions/extension_pref_store.h (right):

http://codereview.chromium.org/4438001/diff/8001/9002#newcode123
chrome/browser/extensions/extension_pref_store.h:123: ExtensionPrefs(const
std::string& extension_id, PrefValueMap* values);
On 2010/11/04 16:03:37, Bernhard Bauer wrote:
> On 2010/11/04 11:58:48, Pam wrote:
> > The problem is that extension IDs are not guaranteed to be unique. They're
> > unique per profile, but the local-state ExtensionPrefStore watches all
> profiles.
> > If two extensions both want to control some machine-wide pref, there could
be
> a
> > collision.
> 
> Hm, doesn't that mean that saving the ID of the "winning" extension is not
> actually sufficient? What should we use to identify an extension instead?
> 
> I think the easiest way to fix this would be just to disallow extensions from
> setting local state preferences.

I have discussed this with Pam and we came to the same conclusion. I have put
this as a TODO into the code. A fix will be done in a separate CL.

[Bernhard Bauer, 2010-11-05 10:51:48]

On 2010/11/04 21:24:59, battre wrote:
> Hi Bernhard,
> 
> I have addressed the comments (see below).
> 
> Pam did not do a full review but says it is your call whether the CL is good
to
> commit.

LGTM, but the patch doesn't apply on trunk anymore. You should rebase it, check
for errors introduced by the merge, and upload the new version, then I'll run it
through the trybots and commit.

[battre (please use the other), 2010-11-05 16:57:05]

Rebased

[Aaron Boodman, 2010-11-06 20:26:26]

I've not really been a part of the conversations here, and I only glanced over
the two CLs, so please forgive me if this is a dumb suggestions, but....

Have you consider simply saving the install date along with the extension prefs
and then modifying any then adding something like GetOverridablePref() to
ExtensionPrefs that returns the matching value from the latest installed
extension?

The creation date seems like valuable information to have in general, and the
implementation seems simpler if it would meet your goals.

[battre (please use the other), 2010-11-09 14:56:26]

Hi Aaron,
thanks for input. I think your suggestion would work as well. I don't see a
clear winner. Tagging the extensions with an installation date is very simple.
Maintaining the order of extensions is slightly more flexible as it allows to
reorder things.
I tend to stick to the current approach (it gets simplified in the next CL).
Thanks,
Dominic

[Aaron Boodman, 2010-11-09 15:10:37]

On Tue, Nov 9, 2010 at 6:56 AM,  <battre@google.com> wrote:
> thanks for input. I think your suggestion would work as well. I don't see a
> clear winner. Tagging the extensions with an installation date is very
> simple.
> Maintaining the order of extensions is slightly more flexible as it allows
> to
> reorder things.
> I tend to stick to the current approach (it gets simplified in the next CL).

I disagree. There is already lots of complexity in this area. If we
can resist adding more that can only be a good thing. If the
created-date approach will work, I'd rather do that for now. Like I
said, storing the created-date is useful no matter what, and fits with
the current design. If we need a more complex solution later, we can
always add it then.

Erik, have you been following this more closely? What do you think?

- a

[battre (please use the other), 2010-11-09 15:50:14]

On 2010/11/09 15:10:37, Aaron Boodman wrote:
> On Tue, Nov 9, 2010 at 6:56 AM,  <mailto:battre@google.com> wrote:
> > thanks for input. I think your suggestion would work as well. I don't see a
> > clear winner. Tagging the extensions with an installation date is very
> > simple.
> > Maintaining the order of extensions is slightly more flexible as it allows
> > to
> > reorder things.
> > I tend to stick to the current approach (it gets simplified in the next CL).
> 
> I disagree. There is already lots of complexity in this area. If we
> can resist adding more that can only be a good thing. If the
> created-date approach will work, I'd rather do that for now. Like I
> said, storing the created-date is useful no matter what, and fits with
> the current design. If we need a more complex solution later, we can
> always add it then.

Ok, let me briefly outline what Pam has implemented and where I was planning to
go with this:

The current ExtensionPrefStore consists of two parts:
1) The first component is a stack of "PrefValueMaps". Each "PrefValueMap" holds
all preferences of an extension in the form of a preference key -> preference
value map. Logically, the effective preferences are a projection of the stack
from top to bottom: For each lookup you could start at the top of the stack and
search for the first extension that contains the key.
2) In order to not require each lookup to traverse the entire stack from top to
bottom, there is a cache that always contains the effective values. Therefore,
inserts are slightly more expensive and complex but lookups are cheaper.

What I have done so far:
Made sure that the order of extensions in the stack is deterministic. In this CL
it is stored in an ordered list of extension IDs (will be replaced, see below).

The next step for a separate CL is:
Currently the ExtensionPrefStore is completely in memory. We need to persist the
winning preferences, e.g. to ensure that proxysettings are available even before
proxy extensions are loaded after a Chrome restart.
For the sake of simplicity, I want to store *all* preferences (not just the
winning ones) in the user's persistent prefstore. According to my current plans,
it should look like this (sorry for my lack of JSON syntax knowledge).

extensionprefs: ( # --> here comes a list of extensions sorted by precendence
 { extensionid: "last_installed_extension_id",
   values: { "key1": "value1", "key2": "value2" }
 },
 { extensionid: "extension_installed_before",
   values: { "key1": "value1" }
 },
 { extensionid: "first_installed_extension",
   values: { "key3": "value3" }
 }
)

In other words, I would like to persist the preferences of extensions in the
order of their precedence. I was planning to maintain the cache for speedups as
currently implemented.

Instead of introducing a date-field, we could simply iterate from the first
extension to the last until we have found a key that we want to lookup. I.e. the
order is already stored in this list of extension preferences. I think this is
even simpler than having a date field. (we can introduce that nevertheless)

I could remove the cache. It would reduce the complexity of the code but comes
at the cost of slower lookups.

What do you think? Or did you argue against having the ExtensionPrefStore at
all?

I have spent some time, figuring out how the PrefStores work. I am planning to
write a document with some illustrating figures some time soon.

Best,
Dominic

[Aaron Boodman, 2010-11-09 22:45:39]

On 2010/11/09 15:50:14, battre wrote:
> On 2010/11/09 15:10:37, Aaron Boodman wrote:
> > On Tue, Nov 9, 2010 at 6:56 AM,  <mailto:battre@google.com> wrote:
> > > thanks for input. I think your suggestion would work as well. I don't see
a
> > > clear winner. Tagging the extensions with an installation date is very
> > > simple.
> > > Maintaining the order of extensions is slightly more flexible as it allows
> > > to
> > > reorder things.
> > > I tend to stick to the current approach (it gets simplified in the next
CL).
> > 
> > I disagree. There is already lots of complexity in this area. If we
> > can resist adding more that can only be a good thing. If the
> > created-date approach will work, I'd rather do that for now. Like I
> > said, storing the created-date is useful no matter what, and fits with
> > the current design. If we need a more complex solution later, we can
> > always add it then.
> 
> Ok, let me briefly outline what Pam has implemented and where I was planning
to
> go with this:
> 
> The current ExtensionPrefStore consists of two parts:
> 1) The first component is a stack of "PrefValueMaps". Each "PrefValueMap"
holds
> all preferences of an extension in the form of a preference key -> preference
> value map. Logically, the effective preferences are a projection of the stack
> from top to bottom: For each lookup you could start at the top of the stack
and
> search for the first extension that contains the key.
> 2) In order to not require each lookup to traverse the entire stack from top
to
> bottom, there is a cache that always contains the effective values. Therefore,
> inserts are slightly more expensive and complex but lookups are cheaper.

This seems likely to be premature optimization. I guess in some extravagant
cases, people could have 100 extensions installed, but even then we're talking
about a very small amount of time to iterate them all.

> What I have done so far:
> Made sure that the order of extensions in the stack is deterministic. In this
CL
> it is stored in an ordered list of extension IDs (will be replaced, see
below).
> 
> The next step for a separate CL is:
> Currently the ExtensionPrefStore is completely in memory. We need to persist
the
> winning preferences, e.g. to ensure that proxysettings are available even
before
> proxy extensions are loaded after a Chrome restart.
> For the sake of simplicity, I want to store *all* preferences (not just the
> winning ones) in the user's persistent prefstore. According to my current
plans,
> it should look like this (sorry for my lack of JSON syntax knowledge).
> 
> extensionprefs: ( # --> here comes a list of extensions sorted by precendence
>  { extensionid: "last_installed_extension_id",
>    values: { "key1": "value1", "key2": "value2" }
>  },
>  { extensionid: "extension_installed_before",
>    values: { "key1": "value1" }
>  },
>  { extensionid: "first_installed_extension",
>    values: { "key3": "value3" }
>  }
> )
>
> In other words, I would like to persist the preferences of extensions in the
> order of their precedence. I was planning to maintain the cache for speedups
as
> currently implemented.

How does this relate to the existing ExtensionPrefs class and persisted
preferences in user profile directories. Are you suggesting replacing them?

> Instead of introducing a date-field, we could simply iterate from the first
> extension to the last until we have found a key that we want to lookup. I.e.
the
> order is already stored in this list of extension preferences. I think this is
> even simpler than having a date field. (we can introduce that nevertheless)
> 
> I could remove the cache. It would reduce the complexity of the code but comes
> at the cost of slower lookups.
> 
> What do you think? Or did you argue against having the ExtensionPrefStore at
> all?

I'm concerned about redesigning ExtensionPrefs for a relatively minor use case
and also about adding some parallel classes that do similar things. It doesn't
seem worth the complexity. It's easy and fast to search all installed extensions
and get the latest one installed that has a certain feature.

Maybe I need to see the big picture. Is there a design doc or some mail you can
refer me to?

[Pam (message me for reviews), 2010-11-10 07:42:56]

On Tue, Nov 9, 2010 at 11:45 PM, <aa@chromium.org> wrote:

> On 2010/11/09 15:50:14, battre wrote:
>
>> On 2010/11/09 15:10:37, Aaron Boodman wrote:
>> > On Tue, Nov 9, 2010 at 6:56 AM,  <mailto:battre@google.com> wrote:
>> > > thanks for input. I think your suggestion would work as well. I don't
>> see
>>
> a
>
>> > > clear winner. Tagging the extensions with an installation date is very
>> > > simple.
>> > > Maintaining the order of extensions is slightly more flexible as it
>> allows
>> > > to
>> > > reorder things.
>> > > I tend to stick to the current approach (it gets simplified in the
>> next
>>
> CL).
>
>> >
>> > I disagree. There is already lots of complexity in this area. If we
>> > can resist adding more that can only be a good thing. If the
>> > created-date approach will work, I'd rather do that for now. Like I
>> > said, storing the created-date is useful no matter what, and fits with
>> > the current design. If we need a more complex solution later, we can
>> > always add it then.
>>
>
>  Ok, let me briefly outline what Pam has implemented and where I was
>> planning
>>
> to
>
>> go with this:
>>
>
>  The current ExtensionPrefStore consists of two parts:
>> 1) The first component is a stack of "PrefValueMaps". Each "PrefValueMap"
>>
> holds
>
>> all preferences of an extension in the form of a preference key ->
>> preference
>> value map. Logically, the effective preferences are a projection of the
>> stack
>> from top to bottom: For each lookup you could start at the top of the
>> stack
>>
> and
>
>> search for the first extension that contains the key.
>> 2) In order to not require each lookup to traverse the entire stack from
>> top
>>
> to
>
>> bottom, there is a cache that always contains the effective values.
>> Therefore,
>> inserts are slightly more expensive and complex but lookups are cheaper.
>>
>
> This seems likely to be premature optimization. I guess in some extravagant
> cases, people could have 100 extensions installed, but even then we're
> talking
> about a very small amount of time to iterate them all.


Although it affects performance, this is mainly to fit the API expected by
the PrefValueStore. The latter is designed to access a Dictionary of prefs
from each PrefStore, so the ExtensionPrefStore needs to provide one
containing the current/active/winning values for each pref it stores.

For background, the PrefValueStore coordinates preferences set by a number
of different PrefStores, ensuring that user preferences, command-line
options, prefs set by extensions, prefs set by administrator policy, etc.
override each other with the right priority.


>
>
>  What I have done so far:
>> Made sure that the order of extensions in the stack is deterministic. In
>> this
>>
> CL
>
>> it is stored in an ordered list of extension IDs (will be replaced, see
>>
> below).
>
>  The next step for a separate CL is:
>> Currently the ExtensionPrefStore is completely in memory. We need to
>> persist
>>
> the
>
>> winning preferences, e.g. to ensure that proxysettings are available even
>>
> before
>
>> proxy extensions are loaded after a Chrome restart.
>> For the sake of simplicity, I want to store *all* preferences (not just
>> the
>> winning ones) in the user's persistent prefstore. According to my current
>>
> plans,
>
>> it should look like this (sorry for my lack of JSON syntax knowledge).
>>
>
>  extensionprefs: ( # --> here comes a list of extensions sorted by
>> precendence
>>  { extensionid: "last_installed_extension_id",
>>    values: { "key1": "value1", "key2": "value2" }
>>  },
>>  { extensionid: "extension_installed_before",
>>    values: { "key1": "value1" }
>>  },
>>  { extensionid: "first_installed_extension",
>>    values: { "key3": "value3" }
>>  }
>> )
>>
>
>  In other words, I would like to persist the preferences of extensions in
>> the
>> order of their precedence. I was planning to maintain the cache for
>> speedups
>>
> as
>
>> currently implemented.
>>
>
> How does this relate to the existing ExtensionPrefs class and persisted
> preferences in user profile directories. Are you suggesting replacing them?


There are two different entities here, with confusable names. ExtensionPrefs
are the preferences controlling each extension itself, such as whether it
can run in Incognito. The ExtensionPrefStore holds browser preferences set
by extensions via an extension API.

As Dominic describes, we also need to persist the precedence of those
browser preferences, so it comes up the same on restart. Furthermore, we
need to persist the winning values, so they're available before extensions
have loaded. These can be done either by saving the priority order of any
extensions that set browser preferences and the single winning values, or by
also saving the whole stack of preferences that any extension has set. In
either case, although these are stored in the user profile directory like a
user preference would be, that's only an implementation detail; they're
saved under separate keys from any actual user prefs.

- Pam


>
>
>  Instead of introducing a date-field, we could simply iterate from the
>> first
>> extension to the last until we have found a key that we want to lookup.
>> I.e.
>>
> the
>
>> order is already stored in this list of extension preferences. I think
>> this is
>> even simpler than having a date field. (we can introduce that
>> nevertheless)
>>
>
>  I could remove the cache. It would reduce the complexity of the code but
>> comes
>> at the cost of slower lookups.
>>
>
>  What do you think? Or did you argue against having the ExtensionPrefStore
>> at
>> all?
>>
>
> I'm concerned about redesigning ExtensionPrefs for a relatively minor use
> case
> and also about adding some parallel classes that do similar things. It
> doesn't
> seem worth the complexity. It's easy and fast to search all installed
> extensions
> and get the latest one installed that has a certain feature.
>
> Maybe I need to see the big picture. Is there a design doc or some mail you
> can
> refer me to?
>
>
> http://codereview.chromium.org/4438001/
>

[Aaron Boodman, 2010-11-10 17:58:37]

On 2010/11/10 07:42:56, Pam wrote:
> Although it affects performance, this is mainly to fit the API expected by
> the PrefValueStore. The latter is designed to access a Dictionary of prefs
> from each PrefStore, so the ExtensionPrefStore needs to provide one
> containing the current/active/winning values for each pref it stores.
> 
> For background, the PrefValueStore coordinates preferences set by a number
> of different PrefStores, ensuring that user preferences, command-line
> options, prefs set by extensions, prefs set by administrator policy, etc.
> override each other with the right priority.
...
> As Dominic describes, we also need to persist the precedence of those
> browser preferences, so it comes up the same on restart. Furthermore, we
> need to persist the winning values, so they're available before extensions
> have loaded. These can be done either by saving the priority order of any
> extensions that set browser preferences and the single winning values, or by
> also saving the whole stack of preferences that any extension has set. In
> either case, although these are stored in the user profile directory like a
> user preference would be, that's only an implementation detail; they're
> saved under separate keys from any actual user prefs.

I see.

It seems like this is interesting enough to deserve a mini design doc, or just
an email to chromium-dev. Has that happened?

[Erik does not do reviews, 2010-11-12 18:12:21]

+jochen

On Wed, Nov 10, 2010 at 9:58 AM, <aa@chromium.org> wrote:

> On 2010/11/10 07:42:56, Pam wrote:
>
>> Although it affects performance, this is mainly to fit the API expected by
>> the PrefValueStore. The latter is designed to access a Dictionary of prefs
>> from each PrefStore, so the ExtensionPrefStore needs to provide one
>> containing the current/active/winning values for each pref it stores.
>>
>
>  For background, the PrefValueStore coordinates preferences set by a number
>> of different PrefStores, ensuring that user preferences, command-line
>> options, prefs set by extensions, prefs set by administrator policy, etc.
>> override each other with the right priority.
>>
> ...
>
>  As Dominic describes, we also need to persist the precedence of those
>> browser preferences, so it comes up the same on restart. Furthermore, we
>> need to persist the winning values, so they're available before extensions
>> have loaded. These can be done either by saving the priority order of any
>> extensions that set browser preferences and the single winning values, or
>> by
>> also saving the whole stack of preferences that any extension has set. In
>> either case, although these are stored in the user profile directory like
>> a
>> user preference would be, that's only an implementation detail; they're
>> saved under separate keys from any actual user prefs.
>>
>
> I see.
>
> It seems like this is interesting enough to deserve a mini design doc, or
> just
> an email to chromium-dev. Has that happened?
>
>
> http://codereview.chromium.org/4438001/
>

Was chatting with Jochen about this this morning.  He's going to follow up
and see if we can get a design doc put together here.

Erik