Numeric identifiers of events are not guaranteed to be unique
authorcommit-queue@webkit.org <commit-queue@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 14 Feb 2013 21:49:20 +0000 (21:49 +0000)
committercommit-queue@webkit.org <commit-queue@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 14 Feb 2013 21:49:20 +0000 (21:49 +0000)
https://bugs.webkit.org/show_bug.cgi?id=103259

Patch by Cosmin Truta <ctruta@rim.com> on 2013-02-14
Reviewed by Alexey Proskuryakov.

The results of setTimeout, setInterval and navigator.geolocation.watchPosition
are positive integer values extracted from a simple circular sequential number
generator, whose uniqueness can be guaranteed for no more than 2^31 calls to
any of these functions. In order to provide this guarantee beyond this limit,
we repeatedly ask for the next sequential id until we get one that's not used
already.

This solution works instantly under normal circumstances, when there are few
live timeout ids or geolocation ids at any given moment. Handling millions of
live ids will require another solution.

No new tests. Brief tests of uniqueness already exist.
Moreover, reproducing this particular issue would require 2^31 set/clear
function calls, which is prohibitively expensive.

* Modules/geolocation/Geolocation.cpp:
(WebCore::Geolocation::Watchers::add): Rename from Watchers::set; return false if watch id already exists.
(WebCore::Geolocation::watchPosition): Repeat until the new watch id is unique.
* Modules/geolocation/Geolocation.h:
(Watchers): Rename Watchers::set to Watchers::add.
* Modules/geolocation/Geolocation.idl: Rename the argument of Geolocation::clearWatch to WatchID.
* dom/ScriptExecutionContext.cpp:
(WebCore::ScriptExecutionContext::ScriptExecutionContext): Update initialization.
(WebCore::ScriptExecutionContext::circularSequentialID): Rename from newUniqueID; remove FIXME note.
* dom/ScriptExecutionContext.h:
(ScriptExecutionContext): Rename ScriptExecutionContext::newUniqueID to ScriptExecutionContext::circularSequentialID.
(WebCore::ScriptExecutionContext::addTimeout): Return false (do not assert) if timeout id already exists.
* page/DOMTimer.cpp:
(WebCore::DOMTimer::DOMTimer): Repeat until the new timeout id is unique.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@142909 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WebCore/ChangeLog
Source/WebCore/Modules/geolocation/Geolocation.cpp
Source/WebCore/Modules/geolocation/Geolocation.h
Source/WebCore/Modules/geolocation/Geolocation.idl
Source/WebCore/dom/ScriptExecutionContext.cpp
Source/WebCore/dom/ScriptExecutionContext.h
Source/WebCore/page/DOMTimer.cpp

index d727e9b..e4b743b 100644 (file)
@@ -1,3 +1,40 @@
+2013-02-14  Cosmin Truta  <ctruta@rim.com>
+
+        Numeric identifiers of events are not guaranteed to be unique
+        https://bugs.webkit.org/show_bug.cgi?id=103259
+
+        Reviewed by Alexey Proskuryakov.
+
+        The results of setTimeout, setInterval and navigator.geolocation.watchPosition
+        are positive integer values extracted from a simple circular sequential number
+        generator, whose uniqueness can be guaranteed for no more than 2^31 calls to
+        any of these functions. In order to provide this guarantee beyond this limit,
+        we repeatedly ask for the next sequential id until we get one that's not used
+        already.
+
+        This solution works instantly under normal circumstances, when there are few
+        live timeout ids or geolocation ids at any given moment. Handling millions of
+        live ids will require another solution.
+
+        No new tests. Brief tests of uniqueness already exist.
+        Moreover, reproducing this particular issue would require 2^31 set/clear
+        function calls, which is prohibitively expensive.
+
+        * Modules/geolocation/Geolocation.cpp:
+        (WebCore::Geolocation::Watchers::add): Rename from Watchers::set; return false if watch id already exists.
+        (WebCore::Geolocation::watchPosition): Repeat until the new watch id is unique.
+        * Modules/geolocation/Geolocation.h:
+        (Watchers): Rename Watchers::set to Watchers::add.
+        * Modules/geolocation/Geolocation.idl: Rename the argument of Geolocation::clearWatch to WatchID.
+        * dom/ScriptExecutionContext.cpp:
+        (WebCore::ScriptExecutionContext::ScriptExecutionContext): Update initialization.
+        (WebCore::ScriptExecutionContext::circularSequentialID): Rename from newUniqueID; remove FIXME note.
+        * dom/ScriptExecutionContext.h:
+        (ScriptExecutionContext): Rename ScriptExecutionContext::newUniqueID to ScriptExecutionContext::circularSequentialID.
+        (WebCore::ScriptExecutionContext::addTimeout): Return false (do not assert) if timeout id already exists.
+        * page/DOMTimer.cpp:
+        (WebCore::DOMTimer::DOMTimer): Repeat until the new timeout id is unique.
+
 2013-02-14  Sheriff Bot  <webkit.review.bot@gmail.com>
 
         Unreviewed, rolling out r142825.
index d4b739e..15c4697 100644 (file)
@@ -173,13 +173,15 @@ void Geolocation::GeoNotifier::timerFired(Timer<GeoNotifier>*)
     m_geolocation->requestTimedOut(this);
 }
 
-void Geolocation::Watchers::set(int id, PassRefPtr<GeoNotifier> prpNotifier)
+bool Geolocation::Watchers::add(int id, PassRefPtr<GeoNotifier> prpNotifier)
 {
     ASSERT(id > 0);
     RefPtr<GeoNotifier> notifier = prpNotifier;
 
-    m_idToNotifierMap.set(id, notifier.get());
+    if (!m_idToNotifierMap.add(id, notifier.get()).isNewEntry)
+        return false;
     m_notifierToIdMap.set(notifier.release(), id);
+    return true;
 }
 
 Geolocation::GeoNotifier* Geolocation::Watchers::find(int id)
@@ -307,8 +309,11 @@ int Geolocation::watchPosition(PassRefPtr<PositionCallback> successCallback, Pas
     RefPtr<GeoNotifier> notifier = GeoNotifier::create(this, successCallback, errorCallback, options);
     startRequest(notifier.get());
 
-    int watchID = m_scriptExecutionContext->newUniqueID();
-    m_watchers.set(watchID, notifier.release());
+    int watchID;
+    // Keep asking for the next id until we're given one that we don't already have.
+    do {
+        watchID = m_scriptExecutionContext->circularSequentialID();
+    } while (!m_watchers.add(watchID, notifier));
     return watchID;
 }
 
index f3bed34..a1bd9eb 100644 (file)
@@ -112,7 +112,7 @@ private:
 
     class Watchers {
     public:
-        void set(int id, PassRefPtr<GeoNotifier>);
+        bool add(int id, PassRefPtr<GeoNotifier>);
         GeoNotifier* find(int id);
         void remove(int id);
         void remove(GeoNotifier*);
index 5ad3c7b..f430c8d 100644 (file)
@@ -37,6 +37,6 @@
                                 in [Optional] PositionErrorCallback errorCallback,
                                 in [Optional] PositionOptions options);
 
-    void clearWatch(in long watchId);
+    void clearWatch(in long watchID);
 };
 
index 8022243..d280c62 100644 (file)
@@ -103,7 +103,7 @@ void ScriptExecutionContext::AddConsoleMessageTask::performTask(ScriptExecutionC
 ScriptExecutionContext::ScriptExecutionContext()
     : m_iteratingActiveDOMObjects(false)
     , m_inDestructor(false)
-    , m_sequentialID(0)
+    , m_circularSequentialID(0)
     , m_inDispatchErrorEvent(false)
     , m_activeDOMObjectsAreSuspended(false)
     , m_reasonForSuspendingActiveDOMObjects(static_cast<ActiveDOMObject::ReasonForSuspension>(-1))
@@ -349,14 +349,12 @@ bool ScriptExecutionContext::dispatchErrorEvent(const String& errorMessage, int
     return errorEvent->defaultPrevented();
 }
 
-int ScriptExecutionContext::newUniqueID()
+int ScriptExecutionContext::circularSequentialID()
 {
-    ++m_sequentialID;
-    // FIXME: We prevent wraparound from becoming negative with a simple solution which
-    // ensures the result has a correct range, but without fully guaranteeing uniqueness.
-    if (m_sequentialID <= 0)
-        m_sequentialID = 1;
-    return m_sequentialID;
+    ++m_circularSequentialID;
+    if (m_circularSequentialID <= 0)
+        m_circularSequentialID = 1;
+    return m_circularSequentialID;
 }
 
 #if ENABLE(BLOB)
index 14030f9..61e4b58 100644 (file)
@@ -145,10 +145,10 @@ public:
 
     virtual void postTask(PassOwnPtr<Task>) = 0; // Executes the task on context's thread asynchronously.
 
-    // Creates a unique id for setTimeout, setInterval or navigator.geolocation.watchPosition.
-    int newUniqueID();
+    // Gets the next id in a circular sequence from 1 to 2^31-1.
+    int circularSequentialID();
 
-    void addTimeout(int timeoutId, DOMTimer* timer) { ASSERT(!m_timeouts.contains(timeoutId)); m_timeouts.set(timeoutId, timer); }
+    bool addTimeout(int timeoutId, DOMTimer* timer) { return m_timeouts.add(timeoutId, timer).isNewEntry; }
     void removeTimeout(int timeoutId) { m_timeouts.remove(timeoutId); }
     DOMTimer* findTimeout(int timeoutId) { return m_timeouts.get(timeoutId); }
 
@@ -216,7 +216,7 @@ private:
     bool m_iteratingActiveDOMObjects;
     bool m_inDestructor;
 
-    int m_sequentialID;
+    int m_circularSequentialID;
     typedef HashMap<int, DOMTimer*> TimeoutMap;
     TimeoutMap m_timeouts;
 
index 5023394..3108c48 100644 (file)
@@ -54,7 +54,6 @@ static inline bool shouldForwardUserGesture(int interval, int nestingLevel)
 
 DOMTimer::DOMTimer(ScriptExecutionContext* context, PassOwnPtr<ScheduledAction> action, int interval, bool singleShot)
     : SuspendableTimer(context)
-    , m_timeoutId(context->newUniqueID())
     , m_nestingLevel(timerNestingLevel + 1)
     , m_action(action)
     , m_originalInterval(interval)
@@ -62,7 +61,10 @@ DOMTimer::DOMTimer(ScriptExecutionContext* context, PassOwnPtr<ScheduledAction>
     if (shouldForwardUserGesture(interval, m_nestingLevel))
         m_userGestureToken = UserGestureIndicator::currentToken();
 
-    context->addTimeout(m_timeoutId, this);
+    // Keep asking for the next id until we're given one that we don't already have.
+    do {
+        m_timeoutId = context->circularSequentialID();
+    } while (!context->addTimeout(m_timeoutId, this));
 
     double intervalMilliseconds = intervalClampedToMinimum(interval, context->minimumTimerInterval());
     if (singleShot)