1 /*
2  * Copyright (C) 2014 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef _LOGD_LOG_STATISTICS_H__
18 #define _LOGD_LOG_STATISTICS_H__
19 
20 #include <memory>
21 #include <stdlib.h>
22 #include <sys/types.h>
23 
24 #include <algorithm> // std::max
25 #include <string>    // std::string
26 #include <unordered_map>
27 
28 #include <android-base/stringprintf.h>
29 #include <log/log.h>
30 #include <private/android_filesystem_config.h>
31 
32 #include "LogBufferElement.h"
33 #include "LogUtils.h"
34 
35 #define log_id_for_each(i) \
36     for (log_id_t i = LOG_ID_MIN; i < LOG_ID_MAX; i = (log_id_t) (i + 1))
37 
38 class LogStatistics;
39 
40 template <typename TKey, typename TEntry>
41 class LogHashtable {
42 
43     std::unordered_map<TKey, TEntry> map;
44 
45 public:
46 
47     typedef typename std::unordered_map<TKey, TEntry>::iterator iterator;
48     typedef typename std::unordered_map<TKey, TEntry>::const_iterator const_iterator;
49 
sort(uid_t uid,pid_t pid,size_t len)50     std::unique_ptr<const TEntry *[]> sort(uid_t uid, pid_t pid,
51                                            size_t len) const {
52         if (!len) {
53             std::unique_ptr<const TEntry *[]> sorted(NULL);
54             return sorted;
55         }
56 
57         const TEntry **retval = new const TEntry* [len];
58         memset(retval, 0, sizeof(*retval) * len);
59 
60         for(const_iterator it = map.begin(); it != map.end(); ++it) {
61             const TEntry &entry = it->second;
62 
63             if ((uid != AID_ROOT) && (uid != entry.getUid())) {
64                 continue;
65             }
66             if (pid && entry.getPid() && (pid != entry.getPid())) {
67                 continue;
68             }
69 
70             size_t sizes = entry.getSizes();
71             ssize_t index = len - 1;
72             while ((!retval[index] || (sizes > retval[index]->getSizes()))
73                     && (--index >= 0))
74                 ;
75             if (++index < (ssize_t)len) {
76                 size_t num = len - index - 1;
77                 if (num) {
78                     memmove(&retval[index + 1], &retval[index],
79                             num * sizeof(retval[0]));
80                 }
81                 retval[index] = &entry;
82             }
83         }
84         std::unique_ptr<const TEntry *[]> sorted(retval);
85         return sorted;
86     }
87 
add(TKey key,LogBufferElement * element)88     inline iterator add(TKey key, LogBufferElement *element) {
89         iterator it = map.find(key);
90         if (it == map.end()) {
91             it = map.insert(std::make_pair(key, TEntry(element))).first;
92         } else {
93             it->second.add(element);
94         }
95         return it;
96     }
97 
add(TKey key)98     inline iterator add(TKey key) {
99         iterator it = map.find(key);
100         if (it == map.end()) {
101             it = map.insert(std::make_pair(key, TEntry(key))).first;
102         } else {
103             it->second.add(key);
104         }
105         return it;
106     }
107 
subtract(TKey key,LogBufferElement * element)108     void subtract(TKey key, LogBufferElement *element) {
109         iterator it = map.find(key);
110         if ((it != map.end()) && it->second.subtract(element)) {
111             map.erase(it);
112         }
113     }
114 
drop(TKey key,LogBufferElement * element)115     inline void drop(TKey key, LogBufferElement *element) {
116         iterator it = map.find(key);
117         if (it != map.end()) {
118             it->second.drop(element);
119         }
120     }
121 
begin()122     inline iterator begin() { return map.begin(); }
begin()123     inline const_iterator begin() const { return map.begin(); }
end()124     inline iterator end() { return map.end(); }
end()125     inline const_iterator end() const { return map.end(); }
126 
127     std::string format(
128             const LogStatistics &stat,
129             uid_t uid,
130             pid_t pid,
131             const std::string &name = std::string(""),
132             log_id_t id = LOG_ID_MAX) const {
133         static const size_t maximum_sorted_entries = 32;
134         std::string output;
135         std::unique_ptr<const TEntry *[]> sorted = sort(uid, pid,
136                                                         maximum_sorted_entries);
137         if (!sorted.get()) {
138             return output;
139         }
140         bool headerPrinted = false;
141         for (size_t index = 0; index < maximum_sorted_entries; ++index) {
142             const TEntry *entry = sorted[index];
143             if (!entry) {
144                 break;
145             }
146             if (entry->getSizes() <= (sorted[0]->getSizes() / 100)) {
147                 break;
148             }
149             if (!headerPrinted) {
150                 output += "\n\n";
151                 output += entry->formatHeader(name, id);
152                 headerPrinted = true;
153             }
154             output += entry->format(stat, id);
155         }
156         return output;
157     }
158 };
159 
160 namespace EntryBaseConstants {
161     static constexpr size_t pruned_len = 14;
162     static constexpr size_t total_len = 80;
163 }
164 
165 struct EntryBase {
166     size_t size;
167 
EntryBaseEntryBase168     EntryBase():size(0) { }
EntryBaseEntryBase169     EntryBase(LogBufferElement *element):size(element->getMsgLen()) { }
170 
getSizesEntryBase171     size_t getSizes() const { return size; }
172 
addEntryBase173     inline void add(LogBufferElement *element) { size += element->getMsgLen(); }
subtractEntryBase174     inline bool subtract(LogBufferElement *element) {
175         size -= element->getMsgLen();
176         return !size;
177     }
178 
formatLineEntryBase179     static std::string formatLine(
180             const std::string &name,
181             const std::string &size,
182             const std::string &pruned) {
183         ssize_t drop_len = std::max(pruned.length() + 1,
184                                     EntryBaseConstants::pruned_len);
185         ssize_t size_len = std::max(size.length() + 1,
186                                     EntryBaseConstants::total_len
187                                         - name.length() - drop_len - 1);
188 
189         if (pruned.length()) {
190             return android::base::StringPrintf("%s%*s%*s\n", name.c_str(),
191                                                (int)size_len, size.c_str(),
192                                                (int)drop_len, pruned.c_str());
193         } else {
194             return android::base::StringPrintf("%s%*s\n", name.c_str(),
195                                                (int)size_len, size.c_str());
196         }
197     }
198 };
199 
200 struct EntryBaseDropped : public EntryBase {
201     size_t dropped;
202 
EntryBaseDroppedEntryBaseDropped203     EntryBaseDropped():dropped(0) { }
EntryBaseDroppedEntryBaseDropped204     EntryBaseDropped(LogBufferElement *element):
205             EntryBase(element),
206             dropped(element->getDropped()){
207     }
208 
getDroppedEntryBaseDropped209     size_t getDropped() const { return dropped; }
210 
addEntryBaseDropped211     inline void add(LogBufferElement *element) {
212         dropped += element->getDropped();
213         EntryBase::add(element);
214     }
subtractEntryBaseDropped215     inline bool subtract(LogBufferElement *element) {
216         dropped -= element->getDropped();
217         return EntryBase::subtract(element) && !dropped;
218     }
dropEntryBaseDropped219     inline void drop(LogBufferElement *element) {
220         dropped += 1;
221         EntryBase::subtract(element);
222     }
223 };
224 
225 struct UidEntry : public EntryBaseDropped {
226     const uid_t uid;
227     pid_t pid;
228 
UidEntryUidEntry229     UidEntry(LogBufferElement *element):
230             EntryBaseDropped(element),
231             uid(element->getUid()),
232             pid(element->getPid()) {
233     }
234 
getKeyUidEntry235     inline const uid_t&getKey() const { return uid; }
getUidUidEntry236     inline const uid_t&getUid() const { return getKey(); }
getPidUidEntry237     inline const pid_t&getPid() const { return pid; }
238 
addUidEntry239     inline void add(LogBufferElement *element) {
240         if (pid != element->getPid()) {
241             pid = -1;
242         }
243         EntryBase::add(element);
244     }
245 
246     std::string formatHeader(const std::string &name, log_id_t id) const;
247     std::string format(const LogStatistics &stat, log_id_t id) const;
248 };
249 
250 namespace android {
251 uid_t pidToUid(pid_t pid);
252 }
253 
254 struct PidEntry : public EntryBaseDropped {
255     const pid_t pid;
256     uid_t uid;
257     char *name;
258 
PidEntryPidEntry259     PidEntry(pid_t pid):
260             EntryBaseDropped(),
261             pid(pid),
262             uid(android::pidToUid(pid)),
263             name(android::pidToName(pid)) {
264     }
PidEntryPidEntry265     PidEntry(LogBufferElement *element):
266             EntryBaseDropped(element),
267             pid(element->getPid()),
268             uid(element->getUid()),
269             name(android::pidToName(pid)) {
270     }
PidEntryPidEntry271     PidEntry(const PidEntry &element):
272             EntryBaseDropped(element),
273             pid(element.pid),
274             uid(element.uid),
275             name(element.name ? strdup(element.name) : NULL) {
276     }
~PidEntryPidEntry277     ~PidEntry() { free(name); }
278 
getKeyPidEntry279     const pid_t&getKey() const { return pid; }
getPidPidEntry280     const pid_t&getPid() const { return getKey(); }
getUidPidEntry281     const uid_t&getUid() const { return uid; }
getNamePidEntry282     const char*getName() const { return name; }
283 
addPidEntry284     inline void add(pid_t newPid) {
285         if (name && !fast<strncmp>(name, "zygote", 6)) {
286             free(name);
287             name = NULL;
288         }
289         if (!name) {
290             name = android::pidToName(newPid);
291         }
292     }
293 
addPidEntry294     inline void add(LogBufferElement *element) {
295         uid_t incomingUid = element->getUid();
296         if (getUid() != incomingUid) {
297             uid = incomingUid;
298             free(name);
299             name = android::pidToName(element->getPid());
300         } else {
301             add(element->getPid());
302         }
303         EntryBaseDropped::add(element);
304     }
305 
306     std::string formatHeader(const std::string &name, log_id_t id) const;
307     std::string format(const LogStatistics &stat, log_id_t id) const;
308 };
309 
310 struct TidEntry : public EntryBaseDropped {
311     const pid_t tid;
312     pid_t pid;
313     uid_t uid;
314     char *name;
315 
TidEntryTidEntry316     TidEntry(pid_t tid, pid_t pid):
317             EntryBaseDropped(),
318             tid(tid),
319             pid(pid),
320             uid(android::pidToUid(tid)),
321             name(android::tidToName(tid)) {
322     }
TidEntryTidEntry323     TidEntry(LogBufferElement *element):
324             EntryBaseDropped(element),
325             tid(element->getTid()),
326             pid(element->getPid()),
327             uid(element->getUid()),
328             name(android::tidToName(tid)) {
329     }
TidEntryTidEntry330     TidEntry(const TidEntry &element):
331             EntryBaseDropped(element),
332             tid(element.tid),
333             pid(element.pid),
334             uid(element.uid),
335             name(element.name ? strdup(element.name) : NULL) {
336     }
~TidEntryTidEntry337     ~TidEntry() { free(name); }
338 
getKeyTidEntry339     const pid_t&getKey() const { return tid; }
getTidTidEntry340     const pid_t&getTid() const { return getKey(); }
getPidTidEntry341     const pid_t&getPid() const { return pid; }
getUidTidEntry342     const uid_t&getUid() const { return uid; }
getNameTidEntry343     const char*getName() const { return name; }
344 
addTidEntry345     inline void add(pid_t incomingTid) {
346         if (name && !fast<strncmp>(name, "zygote", 6)) {
347             free(name);
348             name = NULL;
349         }
350         if (!name) {
351             name = android::tidToName(incomingTid);
352         }
353     }
354 
addTidEntry355     inline void add(LogBufferElement *element) {
356         uid_t incomingUid = element->getUid();
357         pid_t incomingPid = element->getPid();
358         if ((getUid() != incomingUid) || (getPid() != incomingPid)) {
359             uid = incomingUid;
360             pid = incomingPid;
361             free(name);
362             name = android::tidToName(element->getTid());
363         } else {
364             add(element->getTid());
365         }
366         EntryBaseDropped::add(element);
367     }
368 
369     std::string formatHeader(const std::string &name, log_id_t id) const;
370     std::string format(const LogStatistics &stat, log_id_t id) const;
371 };
372 
373 struct TagEntry : public EntryBase {
374     const uint32_t tag;
375     pid_t pid;
376     uid_t uid;
377 
TagEntryTagEntry378     TagEntry(LogBufferElement *element):
379             EntryBase(element),
380             tag(element->getTag()),
381             pid(element->getPid()),
382             uid(element->getUid()) {
383     }
384 
getKeyTagEntry385     const uint32_t&getKey() const { return tag; }
getPidTagEntry386     const pid_t&getPid() const { return pid; }
getUidTagEntry387     const uid_t&getUid() const { return uid; }
getNameTagEntry388     const char*getName() const { return android::tagToName(tag); }
389 
addTagEntry390     inline void add(LogBufferElement *element) {
391         if (uid != element->getUid()) {
392             uid = -1;
393         }
394         if (pid != element->getPid()) {
395             pid = -1;
396         }
397         EntryBase::add(element);
398     }
399 
400     std::string formatHeader(const std::string &name, log_id_t id) const;
401     std::string format(const LogStatistics &stat, log_id_t id) const;
402 };
403 
404 // Log Statistics
405 class LogStatistics {
406     friend UidEntry;
407 
408     size_t mSizes[LOG_ID_MAX];
409     size_t mElements[LOG_ID_MAX];
410     size_t mDroppedElements[LOG_ID_MAX];
411     size_t mSizesTotal[LOG_ID_MAX];
412     size_t mElementsTotal[LOG_ID_MAX];
413     bool enable;
414 
415     // uid to size list
416     typedef LogHashtable<uid_t, UidEntry> uidTable_t;
417     uidTable_t uidTable[LOG_ID_MAX];
418 
419     // pid of system to size list
420     typedef LogHashtable<pid_t, PidEntry> pidSystemTable_t;
421     pidSystemTable_t pidSystemTable[LOG_ID_MAX];
422 
423     // pid to uid list
424     typedef LogHashtable<pid_t, PidEntry> pidTable_t;
425     pidTable_t pidTable;
426 
427     // tid to uid list
428     typedef LogHashtable<pid_t, TidEntry> tidTable_t;
429     tidTable_t tidTable;
430 
431     // tag list
432     typedef LogHashtable<uint32_t, TagEntry> tagTable_t;
433     tagTable_t tagTable;
434 
435     // security tag list
436     tagTable_t securityTagTable;
437 
438 public:
439     LogStatistics();
440 
enableStatistics()441     void enableStatistics() { enable = true; }
442 
443     void add(LogBufferElement *entry);
444     void subtract(LogBufferElement *entry);
445     // entry->setDropped(1) must follow this call
446     void drop(LogBufferElement *entry);
447     // Correct for coalescing two entries referencing dropped content
erase(LogBufferElement * element)448     void erase(LogBufferElement *element) {
449         log_id_t log_id = element->getLogId();
450         --mElements[log_id];
451         --mDroppedElements[log_id];
452     }
453 
sort(uid_t uid,pid_t pid,size_t len,log_id id)454     std::unique_ptr<const UidEntry *[]> sort(uid_t uid, pid_t pid,
455                                              size_t len, log_id id) {
456         return uidTable[id].sort(uid, pid, len);
457     }
sort(uid_t uid,pid_t pid,size_t len,log_id id,uid_t)458     std::unique_ptr<const PidEntry *[]> sort(uid_t uid, pid_t pid,
459                                              size_t len, log_id id, uid_t) {
460         return pidSystemTable[id].sort(uid, pid, len);
461     }
462 
463     // fast track current value by id only
sizes(log_id_t id)464     size_t sizes(log_id_t id) const { return mSizes[id]; }
elements(log_id_t id)465     size_t elements(log_id_t id) const { return mElements[id]; }
realElements(log_id_t id)466     size_t realElements(log_id_t id) const {
467         return mElements[id] - mDroppedElements[id];
468     }
sizesTotal(log_id_t id)469     size_t sizesTotal(log_id_t id) const { return mSizesTotal[id]; }
elementsTotal(log_id_t id)470     size_t elementsTotal(log_id_t id) const { return mElementsTotal[id]; }
471 
472     std::string format(uid_t uid, pid_t pid, unsigned int logMask) const;
473 
474     // helper (must be locked directly or implicitly by mLogElementsLock)
475     const char *pidToName(pid_t pid) const;
476     uid_t pidToUid(pid_t pid);
477     const char *uidToName(uid_t uid) const;
478 };
479 
480 #endif // _LOGD_LOG_STATISTICS_H__
481