The problem here is that EventLogger events reference navigations' timestamps. This is done because "global_id", aka the timestamp, is part of how sessions data is ultimately indexed. Timestamps that are grabbed from WebContents/NavigationEntry and they can change if the page is refreshed, either through F5 or javascript.

If we committed SESSIONS data as soon as we received it, this wouldn't be a problem. But we delay by ~10 seconds to save bandwidth, which leaves a huge window for refreshes to happen.

So we need to ensure that the UserEvents reference navigation timestamps that make it through a Sync commit. When we update sessions data, we can also update a timestamp mapping. This can then be applied to pending and future events to make sure they reference the correct timestamp.

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

commit a58a1f014663671847efd294313b99fe71e1a6bf
Author: skym <skym@chromium.org>
Date: Sat Jul 22 01:33:01 2017

[Sync] Maintain a global_id mapping to update UserEvents that references navigations.

UserEvents are created and reference sessions data by global_id. It is
important that they travel over the wire in this format, as this is how
the sessions data is keyed into Footprints, and the sync server cannot
feasibly perform a persistent read before writing new UserEvents.
Because global_id is forced to be part of the wire interface and
specifics, it is also conveniently part of the interface to the
UserEventService.

However, while this global_id is seemingly sacred to sync, it comes
from simply the timestmap of the navigation entry. And if a page is
reloaded, this value can change. A problem arises when a UserEvent
references a navigation by a global_id that was updated and the old
value is never going to reach the sync server.

To fix we maintain two sets of mappings, one that allows us to map old
global_ids to new global_id, and one that allows us to efficiently look
up uncommitted UserEvents by global_id, so that if we get either a new
global_id or a new UserEvent we can quickly fix the global_id.

BUG= 747621 

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

[modify] https://crrev.com/a58a1f014663671847efd294313b99fe71e1a6bf/chrome/browser/sync/user_event_service_factory.cc
[modify] https://crrev.com/a58a1f014663671847efd294313b99fe71e1a6bf/components/browser_sync/profile_sync_service.cc
[modify] https://crrev.com/a58a1f014663671847efd294313b99fe71e1a6bf/components/browser_sync/profile_sync_service.h
[modify] https://crrev.com/a58a1f014663671847efd294313b99fe71e1a6bf/components/sync/driver/fake_sync_service.cc
[modify] https://crrev.com/a58a1f014663671847efd294313b99fe71e1a6bf/components/sync/driver/fake_sync_service.h
[modify] https://crrev.com/a58a1f014663671847efd294313b99fe71e1a6bf/components/sync/driver/sync_service.h
[modify] https://crrev.com/a58a1f014663671847efd294313b99fe71e1a6bf/components/sync/protocol/session_specifics.proto
[add] https://crrev.com/a58a1f014663671847efd294313b99fe71e1a6bf/components/sync/user_events/global_id_mapper.h
[modify] https://crrev.com/a58a1f014663671847efd294313b99fe71e1a6bf/components/sync/user_events/user_event_service_impl_unittest.cc
[modify] https://crrev.com/a58a1f014663671847efd294313b99fe71e1a6bf/components/sync/user_events/user_event_sync_bridge.cc
[modify] https://crrev.com/a58a1f014663671847efd294313b99fe71e1a6bf/components/sync/user_events/user_event_sync_bridge.h
[modify] https://crrev.com/a58a1f014663671847efd294313b99fe71e1a6bf/components/sync/user_events/user_event_sync_bridge_unittest.cc
[modify] https://crrev.com/a58a1f014663671847efd294313b99fe71e1a6bf/components/sync_sessions/sessions_sync_manager.cc
[modify] https://crrev.com/a58a1f014663671847efd294313b99fe71e1a6bf/components/sync_sessions/sessions_sync_manager.h
[modify] https://crrev.com/a58a1f014663671847efd294313b99fe71e1a6bf/components/sync_sessions/sessions_sync_manager_unittest.cc
[modify] https://crrev.com/a58a1f014663671847efd294313b99fe71e1a6bf/ios/chrome/browser/sync/ios_user_event_service_factory.cc
[modify] https://crrev.com/a58a1f014663671847efd294313b99fe71e1a6bf/tools/metrics/histograms/enums.xml
[modify] https://crrev.com/a58a1f014663671847efd294313b99fe71e1a6bf/tools/metrics/histograms/histograms.xml

I'm really sorry to add a merge request here, I really thought this change landed right before feature freeze. But instead I dropped the ball and it has sat in code review idle for the last 2 weeks.

The M61 branch _just_ happened, and we really want this change to land for launching issue 705657 in M61. Without this change some portion of events/metrics end up referencing non-existent navigations ids, which basically renders them un-usable.

While this change is very large, it is all going to create a new id mapping mechanism that is only written to by sessions sync logic, and only read from by user events to set the navigation_id. If there were logic bugs, the threat is that we write a worse navigation_id and our metrics become less usable.

Your change meets the bar and is auto-approved for M61. Please go ahead and merge the CL to branch 3163 manually. Please contact milestone owner if you have questions.
Owners: amineer@(Android), cmasso@(iOS), ketakid @(ChromeOS), govind@(Desktop)

For more details visit https://www.chromium.org/issue-tracking/autotriage - Your friendly Sheriffbot

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

commit 3105b147ea6a4178791a717a375c4a4ad57e489c
Author: stkhapugin@chromium.org <stkhapugin@chromium.org>
Date: Mon Jul 24 11:11:08 2017

Revert of "[Sync] Maintain a global_id mapping to update UserEvents that references navigations."

Reverts patch set 6 of https://codereview.chromium.org/2958303002

Reason for revert:
Causes crashes on iOS. See  https://crbug.com/747658 .

TBR=skym@chromium.org,pnoland@chromium.org,holte@chromium.org

Original issue's description:

UserEvents are created and reference sessions data by global_id. It is
important that they travel over the wire in this format, as this is how
the sessions data is keyed into Footprints, and the sync server cannot
feasibly perform a persistent read before writing new UserEvents.
Because global_id is forced to be part of the wire interface and
specifics, it is also conveniently part of the interface to the
UserEventService.

However, while this global_id is seemingly sacred to sync, it comes
from simply the timestmap of the navigation entry. And if a page is
reloaded, this value can change. A problem arises when a UserEvent
references a navigation by a global_id that was updated and the old
value is never going to reach the sync server.

To fix we maintain two sets of mappings, one that allows us to map old
global_ids to new global_id, and one that allows us to efficiently look
up uncommitted UserEvents by global_id, so that if we get either a new
global_id or a new UserEvent we can quickly fix the global_id.

BUG= 747621 

Review-Url: https://codereview.chromium.org/2958303002
Cr-Original-Commit-Position: refs/heads/master@{#488826}
Committed: https://chromium.googlesource.com/chromium/src/+/a58a1f014663671847efd294313b99fe71e1a6bf
Change-Id: I109949b56fa028574b53444285b6f83305367560
Reviewed-on: https://chromium-review.googlesource.com/581689
Reviewed-by: Stepan Khapugin <stkhapugin@chromium.org>
Commit-Queue: Stepan Khapugin <stkhapugin@chromium.org>
Cr-Commit-Position: refs/heads/master@{#488944}
[modify] https://crrev.com/3105b147ea6a4178791a717a375c4a4ad57e489c/chrome/browser/sync/user_event_service_factory.cc
[modify] https://crrev.com/3105b147ea6a4178791a717a375c4a4ad57e489c/components/browser_sync/profile_sync_service.cc
[modify] https://crrev.com/3105b147ea6a4178791a717a375c4a4ad57e489c/components/browser_sync/profile_sync_service.h
[modify] https://crrev.com/3105b147ea6a4178791a717a375c4a4ad57e489c/components/sync/driver/fake_sync_service.cc
[modify] https://crrev.com/3105b147ea6a4178791a717a375c4a4ad57e489c/components/sync/driver/fake_sync_service.h
[modify] https://crrev.com/3105b147ea6a4178791a717a375c4a4ad57e489c/components/sync/driver/sync_service.h
[modify] https://crrev.com/3105b147ea6a4178791a717a375c4a4ad57e489c/components/sync/protocol/session_specifics.proto
[delete] https://crrev.com/6e6a205057c96fc8d21537edf8549750cfb7c798/components/sync/user_events/global_id_mapper.h
[modify] https://crrev.com/3105b147ea6a4178791a717a375c4a4ad57e489c/components/sync/user_events/user_event_service_impl_unittest.cc
[modify] https://crrev.com/3105b147ea6a4178791a717a375c4a4ad57e489c/components/sync/user_events/user_event_sync_bridge.cc
[modify] https://crrev.com/3105b147ea6a4178791a717a375c4a4ad57e489c/components/sync/user_events/user_event_sync_bridge.h
[modify] https://crrev.com/3105b147ea6a4178791a717a375c4a4ad57e489c/components/sync/user_events/user_event_sync_bridge_unittest.cc
[modify] https://crrev.com/3105b147ea6a4178791a717a375c4a4ad57e489c/components/sync_sessions/sessions_sync_manager.cc
[modify] https://crrev.com/3105b147ea6a4178791a717a375c4a4ad57e489c/components/sync_sessions/sessions_sync_manager.h
[modify] https://crrev.com/3105b147ea6a4178791a717a375c4a4ad57e489c/components/sync_sessions/sessions_sync_manager_unittest.cc
[modify] https://crrev.com/3105b147ea6a4178791a717a375c4a4ad57e489c/ios/chrome/browser/sync/ios_user_event_service_factory.cc
[modify] https://crrev.com/3105b147ea6a4178791a717a375c4a4ad57e489c/tools/metrics/histograms/enums.xml
[modify] https://crrev.com/3105b147ea6a4178791a717a375c4a4ad57e489c/tools/metrics/histograms/histograms.xml

Re-opening this bug and assigning to you again Sky, to fix the cause of the revert. Let's re-apply the merge-request label after relanding the CL.

When you first open a new tab, the current tab index seems to be -1. When we ask for the SerializedNavigationEntry at that index, the normal implementation gets the entry, then tries to copy it over. But, if the normal entry is null, it no-ops the copy.

It seems I already had a case for this, where i check the global_id, and if it's 0, I ignore this entry. This happens when we no-op that copy over, and we're left with the default value of 0.

However, on iOS, that check for null and no-op doesn't exist. We just blindly try to copy the data over, and this particular EG test hit that case. It would crash real iOS browsers as well, I believe, when new tabs are opened.

Existing sessions code that calls GetSerializedNavigationAtIndex only goes from 0..GetEntryCount(), which conveniently avoids this -1 index problem. It looks like _some_ of the iOS tab delegate methods do the null check, but not all.

The two main options to fix this are check for a -1 index, or update the delegate methods to check for null. I think the latter is more in line with existing code and patterns. Will have a CL posted shortly with this approach.

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

commit e6d92ec3cd6a7ebfcf98fb396232c4266aa2775e
Author: Sky Malice <skym@chromium.org>
Date: Mon Jul 24 22:36:10 2017

Reland of [Sync] Maintain a global_id mapping to update UserEvents...

Initial CL https://codereview.chromium.org/2958303002/

Adding a null check to IOSChromeSyncedTabDelegate to bring its
behavior more in line with TabContentsSyncedTabDelegate, and fix iOS
EG tests.

TBR=holte@chromium.org

Bug:  747621 
Change-Id: I7385df34c9b1379531957a4146b099ef5c02a3e3
Reviewed-on: https://chromium-review.googlesource.com/583409
Reviewed-by: Sky Malice <skym@chromium.org>
Reviewed-by: Patrick Noland <pnoland@chromium.org>
Commit-Queue: Patrick Noland <pnoland@chromium.org>
Commit-Queue: Sky Malice <skym@chromium.org>
Cr-Commit-Position: refs/heads/master@{#489106}
[modify] https://crrev.com/e6d92ec3cd6a7ebfcf98fb396232c4266aa2775e/chrome/browser/sync/user_event_service_factory.cc
[modify] https://crrev.com/e6d92ec3cd6a7ebfcf98fb396232c4266aa2775e/components/browser_sync/profile_sync_service.cc
[modify] https://crrev.com/e6d92ec3cd6a7ebfcf98fb396232c4266aa2775e/components/browser_sync/profile_sync_service.h
[modify] https://crrev.com/e6d92ec3cd6a7ebfcf98fb396232c4266aa2775e/components/sync/driver/fake_sync_service.cc
[modify] https://crrev.com/e6d92ec3cd6a7ebfcf98fb396232c4266aa2775e/components/sync/driver/fake_sync_service.h
[modify] https://crrev.com/e6d92ec3cd6a7ebfcf98fb396232c4266aa2775e/components/sync/driver/sync_service.h
[modify] https://crrev.com/e6d92ec3cd6a7ebfcf98fb396232c4266aa2775e/components/sync/protocol/session_specifics.proto
[add] https://crrev.com/e6d92ec3cd6a7ebfcf98fb396232c4266aa2775e/components/sync/user_events/global_id_mapper.h
[modify] https://crrev.com/e6d92ec3cd6a7ebfcf98fb396232c4266aa2775e/components/sync/user_events/user_event_service_impl_unittest.cc
[modify] https://crrev.com/e6d92ec3cd6a7ebfcf98fb396232c4266aa2775e/components/sync/user_events/user_event_sync_bridge.cc
[modify] https://crrev.com/e6d92ec3cd6a7ebfcf98fb396232c4266aa2775e/components/sync/user_events/user_event_sync_bridge.h
[modify] https://crrev.com/e6d92ec3cd6a7ebfcf98fb396232c4266aa2775e/components/sync/user_events/user_event_sync_bridge_unittest.cc
[modify] https://crrev.com/e6d92ec3cd6a7ebfcf98fb396232c4266aa2775e/components/sync_sessions/sessions_sync_manager.cc
[modify] https://crrev.com/e6d92ec3cd6a7ebfcf98fb396232c4266aa2775e/components/sync_sessions/sessions_sync_manager.h
[modify] https://crrev.com/e6d92ec3cd6a7ebfcf98fb396232c4266aa2775e/components/sync_sessions/sessions_sync_manager_unittest.cc
[modify] https://crrev.com/e6d92ec3cd6a7ebfcf98fb396232c4266aa2775e/ios/chrome/browser/sync/ios_chrome_synced_tab_delegate.mm
[modify] https://crrev.com/e6d92ec3cd6a7ebfcf98fb396232c4266aa2775e/ios/chrome/browser/sync/ios_user_event_service_factory.cc
[modify] https://crrev.com/e6d92ec3cd6a7ebfcf98fb396232c4266aa2775e/tools/metrics/histograms/enums.xml
[modify] https://crrev.com/e6d92ec3cd6a7ebfcf98fb396232c4266aa2775e/tools/metrics/histograms/histograms.xml

Change landed last night. Planning on letting it bake a couple days before merging.

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

commit b99830cc8f7df9632fc949daa233a78f824de61d
Author: Sky Malice <skym@chromium.org>
Date: Tue Jul 25 21:10:32 2017

[Sync] Fix iterator error in UserEventSyncBridge::HandleGlobalIdChange.

There were two mistakes in the previous code, and together they were
able to cause an infinite loop.

The first, and most egregious, was the iterating from
std::multimap::find() to multimap::end(). The intention was to only
iterate over the pairs with a given key, but instead all pairs were
iterated over with a key equal or greater. This did trigger the
DCHECK when we iterate onto an element with the wrong navigation_id,
but if DCHECKs were not on these events would incorrectly be
processed.

The second, and arguably not a bug if the former was working
correctly, was while this iter loop was happening, which deleted
items, we would call RecordUserEvent which would insert a new pair
into in_flight_nav_linked_events_ which we were iterating over. If
the new element had a key greater than or equal to our current iter
then we would encounter it. And thus we infinitely loop, erasing and
inserting what was essentially the same element over and over.

This fix removes both of these issues. multimap::equal_range() for
the former, and a temp vector for the latter.

Bug:  747621 ,  748600 
Change-Id: I2a48ee1f86c81eec787dfbf293ebabc239f11e5d
Reviewed-on: https://chromium-review.googlesource.com/585332
Reviewed-by: Patrick Noland <pnoland@chromium.org>
Commit-Queue: Sky Malice <skym@chromium.org>
Cr-Commit-Position: refs/heads/master@{#489432}
[modify] https://crrev.com/b99830cc8f7df9632fc949daa233a78f824de61d/components/sync/user_events/user_event_sync_bridge.cc
[modify] https://crrev.com/b99830cc8f7df9632fc949daa233a78f824de61d/components/sync/user_events/user_event_sync_bridge_unittest.cc

See comment #4 for merge rationale, hoping to merge commits from comment #9 and comment #11 on this issue.

This bug requires manual review: Reverts referenced in bugdroid comments after merge request.
Please contact the milestone owner if you have questions.
Owners: amineer@(Android), cmasso@(iOS), ketakid @(ChromeOS), govind@(Desktop)

For more details visit https://www.chromium.org/issue-tracking/autotriage - Your friendly Sheriffbot

Updating the label appropriately to mark this as a bug. Sky details the justification for a merge in c#4.

Please add appropriate OSs. Thank you.

Done!

Unfortunately, found another crash that was introduced by #9 here. Created issue 750295 for this new crash.

Giving up on trying to merge this back to M61, removing labels. We're going to have to try to deal with some of the event timestamps being incorrect and the ramifications of that. Follow up to this will tracked elsewhere.

Thanks for the update Sky. We can follow up on the new crash in Issue 750295.