logd: worst uid record watermark

(cherry pick from commit c892ea3fa80dfd3d35c5a3b8bfdc73e7b85eaede)

Hold on to last worst uid watermark and bypass a spike to O(n*n*x)
(n=samples, x=number of spammers) wrt chatty trimming.

Bug: 23327476
Change-Id: I9f21ce95e969b67e576417a760f75c4d86acf364

logd/LogBuffer.cpp

diff --git a/logd/LogBuffer.cpp b/logd/LogBuffer.cpp
index 85f770a..db3f26c 100644
--- a/logd/LogBuffer.cpp
+++ b/logd/LogBuffer.cpp
@@ -240,7 +240,12 @@
 
 LogBufferElementCollection::iterator LogBuffer::erase(LogBufferElementCollection::iterator it) {
     LogBufferElement *e = *it;
+    log_id_t id = e->getLogId();
+    LogBufferIteratorMap::iterator f = mLastWorstUid[id].find(e->getUid());
 
+    if ((f != mLastWorstUid[id].end()) && (it == f->second)) {
+        mLastWorstUid[id].erase(f);
+    }
     it = mLogElements.erase(it);
     stats.subtract(e);
     delete e;
@@ -399,8 +404,17 @@
 
         bool kick = false;
         bool leading = true;
+        it = mLogElements.begin();
+        if (worst != (uid_t) -1) {
+            LogBufferIteratorMap::iterator f = mLastWorstUid[id].find(worst);
+            if ((f != mLastWorstUid[id].end())
+                    && (f->second != mLogElements.end())) {
+                leading = false;
+                it = f->second;
+            }
+        }
         LogBufferElementLast last;
-        for(it = mLogElements.begin(); it != mLogElements.end();) {
+        while (it != mLogElements.end()) {
             LogBufferElement *e = *it;
 
             if (oldest && (oldest->mStart <= e->getSequence())) {
@@ -450,8 +464,10 @@
                 continue;
             }
 
+            // unmerged drop message
             if (dropped) {
                 last.add(e);
+                mLastWorstUid[id][e->getUid()] = it;
                 ++it;
                 continue;
             }
@@ -496,6 +512,7 @@
                     delete e;
                 } else {
                     last.add(e);
+                    mLastWorstUid[id][e->getUid()] = it;
                     ++it;
                 }
             }

logd/LogBuffer.h

diff --git a/logd/LogBuffer.h b/logd/LogBuffer.h
index 76571c6..e94598c 100644
--- a/logd/LogBuffer.h
+++ b/logd/LogBuffer.h
@@ -40,6 +40,11 @@
     LogStatistics stats;
 
     PruneList mPrune;
+    // watermark of any worst/chatty uid processing
+    typedef std::unordered_map<uid_t,
+                               LogBufferElementCollection::iterator>
+                LogBufferIteratorMap;
+    LogBufferIteratorMap mLastWorstUid[LOG_ID_MAX];
 
     unsigned long mMaxSize[LOG_ID_MAX];