Bug 1189829 - Fix quadratic behavior in nsConsoleService. r=erahm, a=sledru
authorNathan Froyd <froydnj@mozilla.com>
Mon, 17 Aug 2015 21:05:48 -0400
changeset 288863 bb1e324928897d6a468acf13191a9785e858df8d
parent 288862 5c614f699e6b60e6864eabdc7bc5e25d40b10d06
child 288864 5894913e42598cd8578958710b3e965409931c72
push id5067
push userraliiev@mozilla.com
push dateMon, 21 Sep 2015 14:04:52 +0000
treeherdermozilla-beta@14221ffe5b2f [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerserahm, sledru
bugs1189829
milestone42.0a2
Bug 1189829 - Fix quadratic behavior in nsConsoleService. r=erahm, a=sledru
xpcom/base/nsConsoleService.cpp
xpcom/base/nsConsoleService.h
--- a/xpcom/base/nsConsoleService.cpp
+++ b/xpcom/base/nsConsoleService.cpp
@@ -50,83 +50,77 @@ NS_IMPL_QUERY_INTERFACE_CI(nsConsoleServ
 NS_IMPL_CI_INTERFACE_GETTER(nsConsoleService, nsIConsoleService, nsIObserver)
 
 static bool sLoggingEnabled = true;
 static bool sLoggingBuffered = true;
 #if defined(ANDROID)
 static bool sLoggingLogcat = true;
 #endif // defined(ANDROID)
 
+nsConsoleService::MessageElement::~MessageElement()
+{
+}
 
 nsConsoleService::nsConsoleService()
-  : mMessages(nullptr)
-  , mCurrent(0)
-  , mFull(false)
+  : mCurrentSize(0)
   , mDeliveringMessage(false)
   , mLock("nsConsoleService.mLock")
 {
   // XXX grab this from a pref!
   // hm, but worry about circularity, bc we want to be able to report
   // prefs errs...
-  mBufferSize = 250;
+  mMaximumSize = 250;
 }
 
 
 void
 nsConsoleService::ClearMessagesForWindowID(const uint64_t innerID)
 {
   MOZ_RELEASE_ASSERT(NS_IsMainThread());
 
-  // Remove the messages related to this window
-  for (uint32_t i = 0; i < mBufferSize && mMessages[i]; i++) {
-    // Only messages implementing nsIScriptError interface exposes the inner window ID
-    nsCOMPtr<nsIScriptError> scriptError = do_QueryInterface(mMessages[i]);
+  for (MessageElement* e = mMessages.getFirst(); e != nullptr; ) {
+    // Only messages implementing nsIScriptError interface expose the
+    // inner window ID.
+    nsCOMPtr<nsIScriptError> scriptError = do_QueryInterface(e->Get());
     if (!scriptError) {
+      e = e->getNext();
       continue;
     }
     uint64_t innerWindowID;
     nsresult rv = scriptError->GetInnerWindowID(&innerWindowID);
     if (NS_FAILED(rv) || innerWindowID != innerID) {
+      e = e->getNext();
       continue;
     }
 
-    // Free this matching message!
-    NS_RELEASE(mMessages[i]);
+    MessageElement* next = e->getNext();
+    e->remove();
+    delete e;
+    mCurrentSize--;
+    MOZ_ASSERT(mCurrentSize < mMaximumSize);
 
-    uint32_t j = i;
-    // Now shift all the following messages
-    // XXXkhuey this is not an efficient way to iterate through an array ...
-    for (; j < mBufferSize - 1 && mMessages[j + 1]; j++) {
-      mMessages[j] = mMessages[j + 1];
-    }
-    // Nullify the current slot
-    mMessages[j] = nullptr;
-    mCurrent = j;
+    e = next;
+  }
+}
 
-    // The array is no longer full
-    mFull = false;
-
-    // Ensure the next iteration handles the messages we just shifted down
-    i--;
+void
+nsConsoleService::ClearMessages()
+{
+  while (!mMessages.isEmpty()) {
+    MessageElement* e = mMessages.popFirst();
+    delete e;
   }
+  mCurrentSize = 0;
 }
 
 nsConsoleService::~nsConsoleService()
 {
   MOZ_RELEASE_ASSERT(NS_IsMainThread());
 
-  uint32_t i = 0;
-  while (i < mBufferSize && mMessages[i]) {
-    NS_RELEASE(mMessages[i]);
-    i++;
-  }
-
-  if (mMessages) {
-    free(mMessages);
-  }
+  ClearMessages();
 }
 
 class AddConsolePrefWatchers : public nsRunnable
 {
 public:
   explicit AddConsolePrefWatchers(nsConsoleService* aConsole) : mConsole(aConsole)
   {
   }
@@ -152,25 +146,16 @@ public:
 
 private:
   nsRefPtr<nsConsoleService> mConsole;
 };
 
 nsresult
 nsConsoleService::Init()
 {
-  mMessages = (nsIConsoleMessage**)
-    moz_xmalloc(mBufferSize * sizeof(nsIConsoleMessage*));
-  if (!mMessages) {
-    return NS_ERROR_OUT_OF_MEMORY;
-  }
-
-  // Array elements should be 0 initially for circular buffer algorithm.
-  memset(mMessages, 0, mBufferSize * sizeof(nsIConsoleMessage*));
-
   NS_DispatchToMainThread(new AddConsolePrefWatchers(this));
 
   return NS_OK;
 }
 
 namespace {
 
 class LogMessageRunnable : public nsRunnable
@@ -236,21 +221,17 @@ nsConsoleService::LogMessageWithMode(nsI
     aMessage->ToString(msg);
     NS_WARNING(nsPrintfCString("Reentrancy error: some client attempted "
       "to display a message to the console while in a console listener. "
       "The following message was discarded: \"%s\"", msg.get()).get());
     return NS_ERROR_FAILURE;
   }
 
   nsRefPtr<LogMessageRunnable> r;
-  nsIConsoleMessage* retiredMessage;
-
-  if (sLoggingBuffered) {
-    NS_ADDREF(aMessage); // early, in case it's same as replaced below.
-  }
+  nsCOMPtr<nsIConsoleMessage> retiredMessage;
 
   /*
    * Lock while updating buffer, and while taking snapshot of
    * listeners array.
    */
   {
     MutexAutoLock lock(mLock);
 
@@ -306,28 +287,26 @@ nsConsoleService::LogMessageWithMode(nsI
       int prefixPos = msg.Find(GetJSLabelPrefix());
       if (prefixPos >= 0) {
         nsDependentCSubstring submsg(msg, prefixPos);
         AddLabel("%s", submsg.BeginReading());
       }
     }
 #endif
 
-    /*
-     * If there's already a message in the slot we're about to replace,
-     * we've wrapped around, and we need to release the old message.  We
-     * save a pointer to it, so we can release below outside the lock.
-     */
-    retiredMessage = mMessages[mCurrent];
-
     if (sLoggingBuffered) {
-      mMessages[mCurrent++] = aMessage;
-      if (mCurrent == mBufferSize) {
-        mCurrent = 0; // wrap around.
-        mFull = true;
+      MessageElement* e = new MessageElement(aMessage);
+      mMessages.insertBack(e);
+      if (mCurrentSize != mMaximumSize) {
+        mCurrentSize++;
+      } else {
+        MessageElement* p = mMessages.popFirst();
+        MOZ_ASSERT(p);
+        retiredMessage = p->forget();
+        delete p;
       }
     }
 
     if (mListeners.Count() > 0) {
       r = new LogMessageRunnable(aMessage, this);
     }
   }
 
@@ -372,65 +351,48 @@ nsConsoleService::LogStringMessage(const
 }
 
 NS_IMETHODIMP
 nsConsoleService::GetMessageArray(uint32_t* aCount,
                                   nsIConsoleMessage*** aMessages)
 {
   MOZ_RELEASE_ASSERT(NS_IsMainThread());
 
-  nsIConsoleMessage** messageArray;
-
-  /*
-   * Lock the whole method, as we don't want anyone mucking with mCurrent or
-   * mFull while we're copying out the buffer.
-   */
   MutexAutoLock lock(mLock);
 
-  if (mCurrent == 0 && !mFull) {
+  if (mMessages.isEmpty()) {
     /*
      * Make a 1-length output array so that nobody gets confused,
      * and return a count of 0.  This should result in a 0-length
      * array object when called from script.
      */
-    messageArray = (nsIConsoleMessage**)
+    nsIConsoleMessage** messageArray = (nsIConsoleMessage**)
       moz_xmalloc(sizeof(nsIConsoleMessage*));
     *messageArray = nullptr;
     *aMessages = messageArray;
     *aCount = 0;
 
     return NS_OK;
   }
 
-  uint32_t resultSize = mFull ? mBufferSize : mCurrent;
-  messageArray =
-    (nsIConsoleMessage**)moz_xmalloc((sizeof(nsIConsoleMessage*))
-                                         * resultSize);
-
-  if (!messageArray) {
-    *aMessages = nullptr;
-    *aCount = 0;
-    return NS_ERROR_FAILURE;
-  }
+  MOZ_ASSERT(mCurrentSize <= mMaximumSize);
+  nsIConsoleMessage** messageArray =
+    static_cast<nsIConsoleMessage**>(moz_xmalloc(sizeof(nsIConsoleMessage*)
+                                                 * mCurrentSize));
 
-  uint32_t i;
-  if (mFull) {
-    for (i = 0; i < mBufferSize; i++) {
-      // if full, fill the buffer starting from mCurrent (which'll be
-      // oldest) wrapping around the buffer to the most recent.
-      messageArray[i] = mMessages[(mCurrent + i) % mBufferSize];
-      NS_ADDREF(messageArray[i]);
-    }
-  } else {
-    for (i = 0; i < mCurrent; i++) {
-      messageArray[i] = mMessages[i];
-      NS_ADDREF(messageArray[i]);
-    }
-  }
-  *aCount = resultSize;
+  uint32_t i = 0;
+  for (MessageElement* e = mMessages.getFirst(); e != nullptr; e = e->getNext()) {
+    nsCOMPtr<nsIConsoleMessage> m = e->Get();
+    m.forget(&messageArray[i]);
+    i++;
+  };
+
+  MOZ_ASSERT(i == mCurrentSize);
+
+  *aCount = i;
   *aMessages = messageArray;
 
   return NS_OK;
 }
 
 NS_IMETHODIMP
 nsConsoleService::RegisterListener(nsIConsoleListener* aListener)
 {
@@ -475,26 +437,17 @@ nsConsoleService::Reset()
 {
   MOZ_RELEASE_ASSERT(NS_IsMainThread());
 
   /*
    * Make sure nobody trips into the buffer while it's being reset
    */
   MutexAutoLock lock(mLock);
 
-  mCurrent = 0;
-  mFull = false;
-
-  /*
-   * Free all messages stored so far (cf. destructor)
-   */
-  for (uint32_t i = 0; i < mBufferSize && mMessages[i]; i++) {
-    NS_RELEASE(mMessages[i]);
-  }
-
+  ClearMessages();
   return NS_OK;
 }
 
 NS_IMETHODIMP
 nsConsoleService::Observe(nsISupports* aSubject, const char* aTopic,
                           const char16_t* aData)
 {
   if (!strcmp(aTopic, NS_XPCOM_SHUTDOWN_OBSERVER_ID)) {
--- a/xpcom/base/nsConsoleService.h
+++ b/xpcom/base/nsConsoleService.h
@@ -55,31 +55,55 @@ public:
   virtual nsresult LogMessageWithMode(nsIConsoleMessage* aMessage,
                                       OutputMode aOutputMode);
 
   typedef nsInterfaceHashtable<nsISupportsHashKey,
                                nsIConsoleListener> ListenerHash;
   void CollectCurrentListeners(nsCOMArray<nsIConsoleListener>& aListeners);
 
 private:
+  class MessageElement : public mozilla::LinkedListElement<MessageElement>
+  {
+  public:
+    explicit MessageElement(nsIConsoleMessage* aMessage) : mMessage(aMessage)
+    {}
+
+    nsIConsoleMessage* Get()
+    {
+      return mMessage.get();
+    }
+
+    already_AddRefed<nsIConsoleMessage> forget()
+    {
+      return mMessage.forget();
+    }
+
+    ~MessageElement();
+
+  private:
+    nsCOMPtr<nsIConsoleMessage> mMessage;
+
+    MessageElement(const MessageElement&) = delete;
+    MessageElement& operator=(const MessageElement&) = delete;
+    MessageElement(MessageElement&&) = delete;
+    MessageElement& operator=(MessageElement&&) = delete;
+  };
+
   ~nsConsoleService();
 
   void ClearMessagesForWindowID(const uint64_t innerID);
+  void ClearMessages();
 
-  // Circular buffer of saved messages
-  nsIConsoleMessage** mMessages;
+  mozilla::LinkedList<MessageElement> mMessages;
 
-  // How big?
-  uint32_t mBufferSize;
+  // The current size of mMessages.
+  uint32_t mCurrentSize;
 
-  // Index of slot in mMessages that'll be filled by *next* log message
-  uint32_t mCurrent;
-
-  // Is the buffer full? (Has mCurrent wrapped around at least once?)
-  bool mFull;
+  // The maximum size of mMessages.
+  uint32_t mMaximumSize;
 
   // Are we currently delivering a console message on the main thread? If
   // so, we suppress incoming messages on the main thread only, to avoid
   // infinite repitition.
   bool mDeliveringMessage;
 
   // Listeners to notify whenever a new message is logged.
   ListenerHash mListeners;