Merge tag 'android-6.0.0_r26' into cm-13.0

Android 6.0.0 release 26

Change-Id: I93d1e3767cbacab2b18cff360065c91b9eaf1d96

6 files changed, 134 insertions, 55 deletions

diff --git a/logd/FlushCommand.cpp b/logd/FlushCommand.cpp
index d584925..823a842 100644
--- a/logd/FlushCommand.cpp
+++ b/logd/FlushCommand.cpp
@@ -72,7 +72,7 @@ void FlushCommand::runSocketCommand(SocketClient *client) {
             return;
         }
         entry = new LogTimeEntry(mReader, client, mNonBlock, mTail, mLogMask, mPid, mStart);
-        times.push_back(entry);
+        times.push_front(entry);
     }
 
     client->incRef();
diff --git a/logd/LogBuffer.cpp b/logd/LogBuffer.cpp
index 0f5071b..559fa2e 100644
--- a/logd/LogBuffer.cpp
+++ b/logd/LogBuffer.cpp
@@ -217,29 +217,42 @@ int LogBuffer::log(log_id_t log_id, log_time realtime,
     return len;
 }
 
-// If we're using more than 256K of memory for log entries, prune
-// at least 10% of the log entries.
+// Prune at most 10% of the log entries or 256, whichever is less.
 //
 // mLogElementsLock must be held when this function is called.
 void LogBuffer::maybePrune(log_id_t id) {
     size_t sizes = stats.sizes(id);
-    if (sizes > log_buffer_size(id)) {
-        size_t sizeOver90Percent = sizes - ((log_buffer_size(id) * 9) / 10);
+    unsigned long maxSize = log_buffer_size(id);
+    if (sizes > maxSize) {
+        size_t sizeOver = sizes - ((maxSize * 9) / 10);
         size_t elements = stats.elements(id);
-        unsigned long pruneRows = elements * sizeOver90Percent / sizes;
-        elements /= 10;
-        if (pruneRows <= elements) {
-            pruneRows = elements;
+        size_t minElements = elements / 10;
+        unsigned long pruneRows = elements * sizeOver / sizes;
+        if (pruneRows <= minElements) {
+            pruneRows = minElements;
+        }
+        if (pruneRows > 256) {
+            pruneRows = 256;
         }
         prune(id, pruneRows);
     }
 }
 
-LogBufferElementCollection::iterator LogBuffer::erase(LogBufferElementCollection::iterator it) {
+LogBufferElementCollection::iterator LogBuffer::erase(
+        LogBufferElementCollection::iterator it, bool engageStats) {
     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);
+    if (engageStats) {
+        stats.subtract(e);
+    } else {
+        stats.erase(e);
+    }
     delete e;
 
     return it;
@@ -316,7 +329,51 @@ public:
 
 // prune "pruneRows" of type "id" from the buffer.
 //
+// This garbage collection task is used to expire log entries. It is called to
+// remove all logs (clear), all UID logs (unprivileged clear), or every
+// 256 or 10% of the total logs (whichever is less) to prune the logs.
+//
+// First there is a prep phase where we discover the reader region lock that
+// acts as a backstop to any pruning activity to stop there and go no further.
+//
+// There are three major pruning loops that follow. All expire from the oldest
+// entries. Since there are multiple log buffers, the Android logging facility
+// will appear to drop entries 'in the middle' when looking at multiple log
+// sources and buffers. This effect is slightly more prominent when we prune
+// the worst offender by logging source. Thus the logs slowly loose content
+// and value as you move back in time. This is preferred since chatty sources
+// invariably move the logs value down faster as less chatty sources would be
+// expired in the noise.
+//
+// The first loop performs blacklisting and worst offender pruning. Falling
+// through when there are no notable worst offenders and have not hit the
+// region lock preventing further worst offender pruning. This loop also looks
+// after managing the chatty log entries and merging to help provide
+// statistical basis for blame. The chatty entries are not a notification of
+// how much logs you may have, but instead represent how much logs you would
+// have had in a virtual log buffer that is extended to cover all the in-memory
+// logs without loss. They last much longer than the represented pruned logs
+// since they get multiplied by the gains in the non-chatty log sources.
+//
+// The second loop get complicated because an algorithm of watermarks and
+// history is maintained to reduce the order and keep processing time
+// down to a minimum at scale. These algorithms can be costly in the face
+// of larger log buffers, or severly limited processing time granted to a
+// background task at lowest priority.
+//
+// This second loop does straight-up expiration from the end of the logs
+// (again, remember for the specified log buffer id) but does some whitelist
+// preservation. Thus whitelist is a Hail Mary low priority, blacklists and
+// spam filtration all take priority. This second loop also checks if a region
+// lock is causing us to buffer too much in the logs to help the reader(s),
+// and will tell the slowest reader thread to skip log entries, and if
+// persistent and hits a further threshold, kill the reader thread.
+//
+// The third thread is optional, and only gets hit if there was a whitelist
+// and more needs to be pruned against the backstop of the region lock.
+//
 // mLogElementsLock must be held when this function is called.
+//
 void LogBuffer::prune(log_id_t id, unsigned long pruneRows, uid_t caller_uid) {
     LogTimeEntry *oldest = NULL;
 
@@ -396,8 +453,28 @@ void LogBuffer::prune(log_id_t id, unsigned long pruneRows, uid_t caller_uid) {
 
         bool kick = false;
         bool leading = true;
+        it = mLogElements.begin();
+        // Perform at least one mandatory garbage collection cycle in following
+        // - clear leading chatty tags
+        // - merge chatty tags
+        // - check age-out of preserved logs
+        bool gc = pruneRows <= 1;
+        if (!gc && (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;
+            }
+        }
+        static const timespec too_old = {
+            EXPIRE_HOUR_THRESHOLD * 60 * 60, 0
+        };
+        LogBufferElementCollection::iterator lastt;
+        lastt = mLogElements.end();
+        --lastt;
         LogBufferElementLast last;
-        for(it = mLogElements.begin(); it != mLogElements.end();) {
+        while (it != mLogElements.end()) {
             LogBufferElement *e = *it;
 
             if (oldest && (oldest->mStart <= e->getSequence())) {
@@ -419,9 +496,7 @@ void LogBuffer::prune(log_id_t id, unsigned long pruneRows, uid_t caller_uid) {
 
             // merge any drops
             if (dropped && last.merge(e, dropped)) {
-                it = mLogElements.erase(it);
-                stats.erase(e);
-                delete e;
+                it = erase(it, false);
                 continue;
             }
 
@@ -447,25 +522,24 @@ void LogBuffer::prune(log_id_t id, unsigned long pruneRows, uid_t caller_uid) {
                 continue;
             }
 
+            if ((e->getRealTime() < ((*lastt)->getRealTime() - too_old))
+                    || (e->getRealTime() > (*lastt)->getRealTime())) {
+                break;
+            }
+
+            // unmerged drop message
             if (dropped) {
                 last.add(e);
+                if ((!gc && (e->getUid() == worst))
+                        || (mLastWorstUid[id].find(e->getUid())
+                            == mLastWorstUid[id].end())) {
+                    mLastWorstUid[id][e->getUid()] = it;
+                }
                 ++it;
                 continue;
             }
 
             if (e->getUid() != worst) {
-                if (leading) {
-                    static const timespec too_old = {
-                        EXPIRE_HOUR_THRESHOLD * 60 * 60, 0
-                    };
-                    LogBufferElementCollection::iterator last;
-                    last = mLogElements.end();
-                    --last;
-                    if ((e->getRealTime() < ((*last)->getRealTime() - too_old))
-                            || (e->getRealTime() > (*last)->getRealTime())) {
-                        break;
-                    }
-                }
                 leading = false;
                 last.clear(e);
                 ++it;
@@ -488,11 +562,13 @@ void LogBuffer::prune(log_id_t id, unsigned long pruneRows, uid_t caller_uid) {
                 stats.drop(e);
                 e->setDropped(1);
                 if (last.merge(e, 1)) {
-                    it = mLogElements.erase(it);
-                    stats.erase(e);
-                    delete e;
+                    it = erase(it, false);
                 } else {
                     last.add(e);
+                    if (!gc || (mLastWorstUid[id].find(worst)
+                                == mLastWorstUid[id].end())) {
+                        mLastWorstUid[id][worst] = it;
+                    }
                     ++it;
                 }
             }
diff --git a/logd/LogBuffer.h b/logd/LogBuffer.h
index a13fded..4769a6c 100644
--- a/logd/LogBuffer.h
+++ b/logd/LogBuffer.h
@@ -19,9 +19,10 @@
 
 #include <sys/types.h>
 
+#include <list>
+
 #include <log/log.h>
 #include <sysutils/SocketClient.h>
-#include <utils/List.h>
 
 #include <private/android_filesystem_config.h>
 
@@ -30,7 +31,7 @@
 #include "LogStatistics.h"
 #include "LogWhiteBlackList.h"
 
-typedef android::List<LogBufferElement *> LogBufferElementCollection;
+typedef std::list<LogBufferElement *> LogBufferElementCollection;
 
 class LogBuffer {
     LogBufferElementCollection mLogElements;
@@ -39,6 +40,11 @@ class LogBuffer {
     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];
 
@@ -81,7 +87,8 @@ public:
 private:
     void maybePrune(log_id_t id);
     void prune(log_id_t id, unsigned long pruneRows, uid_t uid = AID_ROOT);
-    LogBufferElementCollection::iterator erase(LogBufferElementCollection::iterator it);
+    LogBufferElementCollection::iterator erase(
+        LogBufferElementCollection::iterator it, bool engageStats = true);
 };
 
 #endif // _LOGD_LOG_BUFFER_H__
diff --git a/logd/LogTimes.h b/logd/LogTimes.h
index 783bce6..39bcdd4 100644
--- a/logd/LogTimes.h
+++ b/logd/LogTimes.h
@@ -20,8 +20,10 @@
 #include <pthread.h>
 #include <time.h>
 #include <sys/types.h>
+
+#include <list>
+
 #include <sysutils/SocketClient.h>
-#include <utils/List.h>
 #include <log/log.h>
 
 class LogReader;
@@ -107,6 +109,6 @@ public:
     static int FilterSecondPass(const LogBufferElement *element, void *me);
 };
 
-typedef android::List<LogTimeEntry *> LastLogTimes;
+typedef std::list<LogTimeEntry *> LastLogTimes;
 
-#endif
+#endif // _LOGD_LOG_TIMES_H__
diff --git a/logd/LogWhiteBlackList.cpp b/logd/LogWhiteBlackList.cpp
index 277b3ca..16dd6d2 100644
--- a/logd/LogWhiteBlackList.cpp
+++ b/logd/LogWhiteBlackList.cpp
@@ -50,18 +50,14 @@ void Prune::format(char **strp) {
 }
 
 PruneList::PruneList() : mWorstUidEnabled(true) {
-    mNaughty.clear();
-    mNice.clear();
 }
 
 PruneList::~PruneList() {
     PruneCollection::iterator it;
     for (it = mNice.begin(); it != mNice.end();) {
-        delete (*it);
         it = mNice.erase(it);
     }
     for (it = mNaughty.begin(); it != mNaughty.end();) {
-        delete (*it);
         it = mNaughty.erase(it);
     }
 }
@@ -70,11 +66,9 @@ int PruneList::init(char *str) {
     mWorstUidEnabled = true;
     PruneCollection::iterator it;
     for (it = mNice.begin(); it != mNice.end();) {
-        delete (*it);
         it = mNice.erase(it);
     }
     for (it = mNaughty.begin(); it != mNaughty.end();) {
-        delete (*it);
         it = mNaughty.erase(it);
     }
 
@@ -142,28 +136,28 @@ int PruneList::init(char *str) {
         // insert sequentially into list
         PruneCollection::iterator it = list->begin();
         while (it != list->end()) {
-            Prune *p = *it;
-            int m = uid - p->mUid;
+            Prune &p = *it;
+            int m = uid - p.mUid;
             if (m == 0) {
-                if (p->mPid == p->pid_all) {
+                if (p.mPid == p.pid_all) {
                     break;
                 }
-                if ((pid == p->pid_all) && (p->mPid != p->pid_all)) {
+                if ((pid == p.pid_all) && (p.mPid != p.pid_all)) {
                     it = list->erase(it);
                     continue;
                 }
-                m = pid - p->mPid;
+                m = pid - p.mPid;
             }
             if (m <= 0) {
                 if (m < 0) {
-                    list->insert(it, new Prune(uid,pid));
+                    list->insert(it, Prune(uid,pid));
                 }
                 break;
             }
             ++it;
         }
         if (it == list->end()) {
-            list->push_back(new Prune(uid,pid));
+            list->push_back(Prune(uid,pid));
         }
         if (!*str) {
             break;
@@ -193,7 +187,7 @@ void PruneList::format(char **strp) {
 
     for (it = mNice.begin(); it != mNice.end(); ++it) {
         char *a = NULL;
-        (*it)->format(&a);
+        (*it).format(&a);
 
         string.appendFormat(fmt, a);
         fmt = nice_format;
@@ -205,7 +199,7 @@ void PruneList::format(char **strp) {
     fmt = naughty_format + (*fmt != ' ');
     for (it = mNaughty.begin(); it != mNaughty.end(); ++it) {
         char *a = NULL;
-        (*it)->format(&a);
+        (*it).format(&a);
 
         string.appendFormat(fmt, a);
         fmt = naughty_format;
@@ -223,7 +217,7 @@ void PruneList::format(char **strp) {
 bool PruneList::naughty(LogBufferElement *element) {
     PruneCollection::iterator it;
     for (it = mNaughty.begin(); it != mNaughty.end(); ++it) {
-        if (!(*it)->cmp(element)) {
+        if (!(*it).cmp(element)) {
             return true;
         }
     }
@@ -233,7 +227,7 @@ bool PruneList::naughty(LogBufferElement *element) {
 bool PruneList::nice(LogBufferElement *element) {
     PruneCollection::iterator it;
     for (it = mNice.begin(); it != mNice.end(); ++it) {
-        if (!(*it)->cmp(element)) {
+        if (!(*it).cmp(element)) {
             return true;
         }
     }
diff --git a/logd/LogWhiteBlackList.h b/logd/LogWhiteBlackList.h
index d0dd0de..99e3d82 100644
--- a/logd/LogWhiteBlackList.h
+++ b/logd/LogWhiteBlackList.h
@@ -19,7 +19,7 @@
 
 #include <sys/types.h>
 
-#include <utils/List.h>
+#include <list>
 
 #include "LogBufferElement.h"
 
@@ -47,7 +47,7 @@ public:
     void format(char **strp);
 };
 
-typedef android::List<Prune *> PruneCollection;
+typedef std::list<Prune> PruneCollection;
 
 class PruneList {
     PruneCollection mNaughty;