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 d727e9b39f6c8a14708a83f6250d7659ada5b179..e4b743b867bdff171452c5327b6f9d59b574a5eb 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 d4b739e4aff01de0da9ec76cd9550714294ac100..15c4697fa7f754265678203fcb6012a2dec5ec0a 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 f3bed34eecd2777c20a66bf7c51764d8e10bf8ee..a1bd9eb83b56bae5c0160e912f1d7486d921342d 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 5ad3c7b95a3ff34311a3fa9dd9fcd28a00d759db..f430c8d0f78294bfbdf37f56afd18f5dcf945e1c 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 8022243bcc29bc5a028e7e6c108802471f057215..d280c625ab92fd4eb7960678d0ad7c90135327bc 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 14030f9aa75d1e32e5fc5e4618cd3a2703e21973..61e4b58e00f43d0bfa58a066f7e845910efc0fd2 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 50233941c395375e9250e72477219173770b8690..3108c4897b1dd828bf20b21d39c89ec54205fad3 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)