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 <ctype.h>
21 #include <stdlib.h>
22 #include <sys/types.h>
23 
24 #include <algorithm>  // std::max
25 #include <memory>
26 #include <string>  // std::string
27 #include <unordered_map>
28 
29 #include <android-base/stringprintf.h>
30 #include <android/log.h>
31 #include <private/android_filesystem_config.h>
32 
33 #include "LogBufferElement.h"
34 #include "LogUtils.h"
35 
36 #define log_id_for_each(i) \
37     for (log_id_t i = LOG_ID_MIN; (i) < LOG_ID_MAX; (i) = (log_id_t)((i) + 1))
38 
39 class LogStatistics;
40 
41 template <typename TKey, typename TEntry>
42 class LogHashtable {
43     std::unordered_map<TKey, TEntry> map;
44 
bucket_size()45     size_t bucket_size() const {
46         size_t count = 0;
47         for (size_t idx = 0; idx < map.bucket_count(); ++idx) {
48             size_t bucket_size = map.bucket_size(idx);
49             if (bucket_size == 0) bucket_size = 1;
50             count += bucket_size;
51         }
52         float load_factor = map.max_load_factor();
53         if (load_factor < 1.0) return count;
54         return count * load_factor;
55     }
56 
57     static const size_t unordered_map_per_entry_overhead = sizeof(void*);
58     static const size_t unordered_map_bucket_overhead = sizeof(void*);
59 
60    public:
size()61     size_t size() const {
62         return map.size();
63     }
64 
65     // Estimate unordered_map memory usage.
sizeOf()66     size_t sizeOf() const {
67         return sizeof(*this) +
68                (size() * (sizeof(TEntry) + unordered_map_per_entry_overhead)) +
69                (bucket_size() * sizeof(size_t) + unordered_map_bucket_overhead);
70     }
71 
72     typedef typename std::unordered_map<TKey, TEntry>::iterator iterator;
73     typedef
74         typename std::unordered_map<TKey, TEntry>::const_iterator const_iterator;
75 
sort(uid_t uid,pid_t pid,size_t len)76     std::unique_ptr<const TEntry* []> sort(uid_t uid, pid_t pid,
77                                            size_t len) const {
78         if (!len) {
79             std::unique_ptr<const TEntry* []> sorted(NULL);
80             return sorted;
81         }
82 
83         const TEntry** retval = new const TEntry*[len];
84         memset(retval, 0, sizeof(*retval) * len);
85 
86         for (const_iterator it = map.begin(); it != map.end(); ++it) {
87             const TEntry& entry = it->second;
88 
89             if ((uid != AID_ROOT) && (uid != entry.getUid())) {
90                 continue;
91             }
92             if (pid && entry.getPid() && (pid != entry.getPid())) {
93                 continue;
94             }
95 
96             size_t sizes = entry.getSizes();
97             ssize_t index = len - 1;
98             while ((!retval[index] || (sizes > retval[index]->getSizes())) &&
99                    (--index >= 0))
100                 ;
101             if (++index < (ssize_t)len) {
102                 size_t num = len - index - 1;
103                 if (num) {
104                     memmove(&retval[index + 1], &retval[index],
105                             num * sizeof(retval[0]));
106                 }
107                 retval[index] = &entry;
108             }
109         }
110         std::unique_ptr<const TEntry* []> sorted(retval);
111         return sorted;
112     }
113 
add(TKey key,LogBufferElement * element)114     inline iterator add(TKey key, LogBufferElement* element) {
115         iterator it = map.find(key);
116         if (it == map.end()) {
117             it = map.insert(std::make_pair(key, TEntry(element))).first;
118         } else {
119             it->second.add(element);
120         }
121         return it;
122     }
123 
add(TKey key)124     inline iterator add(TKey key) {
125         iterator it = map.find(key);
126         if (it == map.end()) {
127             it = map.insert(std::make_pair(key, TEntry(key))).first;
128         } else {
129             it->second.add(key);
130         }
131         return it;
132     }
133 
subtract(TKey key,LogBufferElement * element)134     void subtract(TKey key, LogBufferElement* element) {
135         iterator it = map.find(key);
136         if ((it != map.end()) && it->second.subtract(element)) {
137             map.erase(it);
138         }
139     }
140 
drop(TKey key,LogBufferElement * element)141     inline void drop(TKey key, LogBufferElement* element) {
142         iterator it = map.find(key);
143         if (it != map.end()) {
144             it->second.drop(element);
145         }
146     }
147 
begin()148     inline iterator begin() {
149         return map.begin();
150     }
begin()151     inline const_iterator begin() const {
152         return map.begin();
153     }
end()154     inline iterator end() {
155         return map.end();
156     }
end()157     inline const_iterator end() const {
158         return map.end();
159     }
160 
161     std::string format(const LogStatistics& stat, uid_t uid, pid_t pid,
162                        const std::string& name = std::string(""),
163                        log_id_t id = LOG_ID_MAX) const {
164         static const size_t maximum_sorted_entries = 32;
165         std::string output;
166         std::unique_ptr<const TEntry* []> sorted =
167             sort(uid, pid, maximum_sorted_entries);
168         if (!sorted.get()) {
169             return output;
170         }
171         bool headerPrinted = false;
172         for (size_t index = 0; index < maximum_sorted_entries; ++index) {
173             const TEntry* entry = sorted[index];
174             if (!entry) {
175                 break;
176             }
177             if (entry->getSizes() <= (sorted[0]->getSizes() / 100)) {
178                 break;
179             }
180             if (!headerPrinted) {
181                 output += "\n\n";
182                 output += entry->formatHeader(name, id);
183                 headerPrinted = true;
184             }
185             output += entry->format(stat, id);
186         }
187         return output;
188     }
189 };
190 
191 namespace EntryBaseConstants {
192 static constexpr size_t pruned_len = 14;
193 static constexpr size_t total_len = 80;
194 }
195 
196 struct EntryBase {
197     size_t size;
198 
EntryBaseEntryBase199     EntryBase() : size(0) {
200     }
EntryBaseEntryBase201     explicit EntryBase(LogBufferElement* element) : size(element->getMsgLen()) {
202     }
203 
getSizesEntryBase204     size_t getSizes() const {
205         return size;
206     }
207 
addEntryBase208     inline void add(LogBufferElement* element) {
209         size += element->getMsgLen();
210     }
subtractEntryBase211     inline bool subtract(LogBufferElement* element) {
212         size -= element->getMsgLen();
213         return !size;
214     }
215 
formatLineEntryBase216     static std::string formatLine(const std::string& name,
217                                   const std::string& size,
218                                   const std::string& pruned) {
219         ssize_t drop_len =
220             std::max(pruned.length() + 1, EntryBaseConstants::pruned_len);
221         ssize_t size_len =
222             std::max(size.length() + 1, EntryBaseConstants::total_len -
223                                             name.length() - drop_len - 1);
224 
225         std::string ret = android::base::StringPrintf(
226             "%s%*s%*s", name.c_str(), (int)size_len, size.c_str(),
227             (int)drop_len, pruned.c_str());
228         // remove any trailing spaces
229         size_t pos = ret.size();
230         size_t len = 0;
231         while (pos && isspace(ret[--pos])) ++len;
232         if (len) ret.erase(pos + 1, len);
233         return ret + "\n";
234     }
235 };
236 
237 struct EntryBaseDropped : public EntryBase {
238     size_t dropped;
239 
EntryBaseDroppedEntryBaseDropped240     EntryBaseDropped() : dropped(0) {
241     }
EntryBaseDroppedEntryBaseDropped242     explicit EntryBaseDropped(LogBufferElement* element)
243         : EntryBase(element), dropped(element->getDropped()) {
244     }
245 
getDroppedEntryBaseDropped246     size_t getDropped() const {
247         return dropped;
248     }
249 
addEntryBaseDropped250     inline void add(LogBufferElement* element) {
251         dropped += element->getDropped();
252         EntryBase::add(element);
253     }
subtractEntryBaseDropped254     inline bool subtract(LogBufferElement* element) {
255         dropped -= element->getDropped();
256         return EntryBase::subtract(element) && !dropped;
257     }
dropEntryBaseDropped258     inline void drop(LogBufferElement* element) {
259         dropped += 1;
260         EntryBase::subtract(element);
261     }
262 };
263 
264 struct UidEntry : public EntryBaseDropped {
265     const uid_t uid;
266     pid_t pid;
267 
UidEntryUidEntry268     explicit UidEntry(LogBufferElement* element)
269         : EntryBaseDropped(element),
270           uid(element->getUid()),
271           pid(element->getPid()) {
272     }
273 
getKeyUidEntry274     inline const uid_t& getKey() const {
275         return uid;
276     }
getUidUidEntry277     inline const uid_t& getUid() const {
278         return getKey();
279     }
getPidUidEntry280     inline const pid_t& getPid() const {
281         return pid;
282     }
283 
addUidEntry284     inline void add(LogBufferElement* element) {
285         if (pid != element->getPid()) {
286             pid = -1;
287         }
288         EntryBaseDropped::add(element);
289     }
290 
291     std::string formatHeader(const std::string& name, log_id_t id) const;
292     std::string format(const LogStatistics& stat, log_id_t id) const;
293 };
294 
295 namespace android {
296 uid_t pidToUid(pid_t pid);
297 }
298 
299 struct PidEntry : public EntryBaseDropped {
300     const pid_t pid;
301     uid_t uid;
302     char* name;
303 
PidEntryPidEntry304     explicit PidEntry(pid_t pid)
305         : EntryBaseDropped(),
306           pid(pid),
307           uid(android::pidToUid(pid)),
308           name(android::pidToName(pid)) {
309     }
PidEntryPidEntry310     explicit PidEntry(LogBufferElement* element)
311         : EntryBaseDropped(element),
312           pid(element->getPid()),
313           uid(element->getUid()),
314           name(android::pidToName(pid)) {
315     }
PidEntryPidEntry316     PidEntry(const PidEntry& element)
317         : EntryBaseDropped(element),
318           pid(element.pid),
319           uid(element.uid),
320           name(element.name ? strdup(element.name) : NULL) {
321     }
~PidEntryPidEntry322     ~PidEntry() {
323         free(name);
324     }
325 
getKeyPidEntry326     const pid_t& getKey() const {
327         return pid;
328     }
getPidPidEntry329     const pid_t& getPid() const {
330         return getKey();
331     }
getUidPidEntry332     const uid_t& getUid() const {
333         return uid;
334     }
getNamePidEntry335     const char* getName() const {
336         return name;
337     }
338 
addPidEntry339     inline void add(pid_t newPid) {
340         if (name && !fastcmp<strncmp>(name, "zygote", 6)) {
341             free(name);
342             name = NULL;
343         }
344         if (!name) {
345             name = android::pidToName(newPid);
346         }
347     }
348 
addPidEntry349     inline void add(LogBufferElement* element) {
350         uid_t incomingUid = element->getUid();
351         if (getUid() != incomingUid) {
352             uid = incomingUid;
353             free(name);
354             name = android::pidToName(element->getPid());
355         } else {
356             add(element->getPid());
357         }
358         EntryBaseDropped::add(element);
359     }
360 
361     std::string formatHeader(const std::string& name, log_id_t id) const;
362     std::string format(const LogStatistics& stat, log_id_t id) const;
363 };
364 
365 struct TidEntry : public EntryBaseDropped {
366     const pid_t tid;
367     pid_t pid;
368     uid_t uid;
369     char* name;
370 
TidEntryTidEntry371     TidEntry(pid_t tid, pid_t pid)
372         : EntryBaseDropped(),
373           tid(tid),
374           pid(pid),
375           uid(android::pidToUid(tid)),
376           name(android::tidToName(tid)) {
377     }
TidEntryTidEntry378     explicit TidEntry(LogBufferElement* element)
379         : EntryBaseDropped(element),
380           tid(element->getTid()),
381           pid(element->getPid()),
382           uid(element->getUid()),
383           name(android::tidToName(tid)) {
384     }
TidEntryTidEntry385     TidEntry(const TidEntry& element)
386         : EntryBaseDropped(element),
387           tid(element.tid),
388           pid(element.pid),
389           uid(element.uid),
390           name(element.name ? strdup(element.name) : NULL) {
391     }
~TidEntryTidEntry392     ~TidEntry() {
393         free(name);
394     }
395 
getKeyTidEntry396     const pid_t& getKey() const {
397         return tid;
398     }
getTidTidEntry399     const pid_t& getTid() const {
400         return getKey();
401     }
getPidTidEntry402     const pid_t& getPid() const {
403         return pid;
404     }
getUidTidEntry405     const uid_t& getUid() const {
406         return uid;
407     }
getNameTidEntry408     const char* getName() const {
409         return name;
410     }
411 
addTidEntry412     inline void add(pid_t incomingTid) {
413         if (name && !fastcmp<strncmp>(name, "zygote", 6)) {
414             free(name);
415             name = NULL;
416         }
417         if (!name) {
418             name = android::tidToName(incomingTid);
419         }
420     }
421 
addTidEntry422     inline void add(LogBufferElement* element) {
423         uid_t incomingUid = element->getUid();
424         pid_t incomingPid = element->getPid();
425         if ((getUid() != incomingUid) || (getPid() != incomingPid)) {
426             uid = incomingUid;
427             pid = incomingPid;
428             free(name);
429             name = android::tidToName(element->getTid());
430         } else {
431             add(element->getTid());
432         }
433         EntryBaseDropped::add(element);
434     }
435 
436     std::string formatHeader(const std::string& name, log_id_t id) const;
437     std::string format(const LogStatistics& stat, log_id_t id) const;
438 };
439 
440 struct TagEntry : public EntryBaseDropped {
441     const uint32_t tag;
442     pid_t pid;
443     uid_t uid;
444 
TagEntryTagEntry445     explicit TagEntry(LogBufferElement* element)
446         : EntryBaseDropped(element),
447           tag(element->getTag()),
448           pid(element->getPid()),
449           uid(element->getUid()) {
450     }
451 
getKeyTagEntry452     const uint32_t& getKey() const {
453         return tag;
454     }
getPidTagEntry455     const pid_t& getPid() const {
456         return pid;
457     }
getUidTagEntry458     const uid_t& getUid() const {
459         return uid;
460     }
getNameTagEntry461     const char* getName() const {
462         return android::tagToName(tag);
463     }
464 
addTagEntry465     inline void add(LogBufferElement* element) {
466         if (uid != element->getUid()) {
467             uid = -1;
468         }
469         if (pid != element->getPid()) {
470             pid = -1;
471         }
472         EntryBaseDropped::add(element);
473     }
474 
475     std::string formatHeader(const std::string& name, log_id_t id) const;
476     std::string format(const LogStatistics& stat, log_id_t id) const;
477 };
478 
479 template <typename TEntry>
480 class LogFindWorst {
481     std::unique_ptr<const TEntry* []> sorted;
482 
483    public:
LogFindWorst(std::unique_ptr<const TEntry * []> && sorted)484     explicit LogFindWorst(std::unique_ptr<const TEntry* []>&& sorted)
485         : sorted(std::move(sorted)) {
486     }
487 
findWorst(int & worst,size_t & worst_sizes,size_t & second_worst_sizes,size_t threshold)488     void findWorst(int& worst, size_t& worst_sizes, size_t& second_worst_sizes,
489                    size_t threshold) {
490         if (sorted.get() && sorted[0] && sorted[1]) {
491             worst_sizes = sorted[0]->getSizes();
492             if ((worst_sizes > threshold)
493                 // Allow time horizon to extend roughly tenfold, assume
494                 // average entry length is 100 characters.
495                 && (worst_sizes > (10 * sorted[0]->getDropped()))) {
496                 worst = sorted[0]->getKey();
497                 second_worst_sizes = sorted[1]->getSizes();
498                 if (second_worst_sizes < threshold) {
499                     second_worst_sizes = threshold;
500                 }
501             }
502         }
503     }
504 
findWorst(int & worst,size_t worst_sizes,size_t & second_worst_sizes)505     void findWorst(int& worst, size_t worst_sizes, size_t& second_worst_sizes) {
506         if (sorted.get() && sorted[0] && sorted[1]) {
507             worst = sorted[0]->getKey();
508             second_worst_sizes =
509                 worst_sizes - sorted[0]->getSizes() + sorted[1]->getSizes();
510         }
511     }
512 };
513 
514 // Log Statistics
515 class LogStatistics {
516     friend UidEntry;
517 
518     size_t mSizes[LOG_ID_MAX];
519     size_t mElements[LOG_ID_MAX];
520     size_t mDroppedElements[LOG_ID_MAX];
521     size_t mSizesTotal[LOG_ID_MAX];
522     size_t mElementsTotal[LOG_ID_MAX];
523     static size_t SizesTotal;
524     bool enable;
525 
526     // uid to size list
527     typedef LogHashtable<uid_t, UidEntry> uidTable_t;
528     uidTable_t uidTable[LOG_ID_MAX];
529 
530     // pid of system to size list
531     typedef LogHashtable<pid_t, PidEntry> pidSystemTable_t;
532     pidSystemTable_t pidSystemTable[LOG_ID_MAX];
533 
534     // pid to uid list
535     typedef LogHashtable<pid_t, PidEntry> pidTable_t;
536     pidTable_t pidTable;
537 
538     // tid to uid list
539     typedef LogHashtable<pid_t, TidEntry> tidTable_t;
540     tidTable_t tidTable;
541 
542     // tag list
543     typedef LogHashtable<uint32_t, TagEntry> tagTable_t;
544     tagTable_t tagTable;
545 
546     // security tag list
547     tagTable_t securityTagTable;
548 
sizeOf()549     size_t sizeOf() const {
550         size_t size = sizeof(*this) + pidTable.sizeOf() + tidTable.sizeOf() +
551                       tagTable.sizeOf() + securityTagTable.sizeOf() +
552                       (pidTable.size() * sizeof(pidTable_t::iterator)) +
553                       (tagTable.size() * sizeof(tagTable_t::iterator));
554         for (auto it : pidTable) {
555             const char* name = it.second.getName();
556             if (name) size += strlen(name) + 1;
557         }
558         for (auto it : tidTable) {
559             const char* name = it.second.getName();
560             if (name) size += strlen(name) + 1;
561         }
562         log_id_for_each(id) {
563             size += uidTable[id].sizeOf();
564             size += uidTable[id].size() * sizeof(uidTable_t::iterator);
565             size += pidSystemTable[id].sizeOf();
566             size +=
567                 pidSystemTable[id].size() * sizeof(pidSystemTable_t::iterator);
568         }
569         return size;
570     }
571 
572    public:
573     LogStatistics();
574 
enableStatistics()575     void enableStatistics() {
576         enable = true;
577     }
578 
579     void add(LogBufferElement* entry);
580     void subtract(LogBufferElement* entry);
581     // entry->setDropped(1) must follow this call
582     void drop(LogBufferElement* entry);
583     // Correct for coalescing two entries referencing dropped content
erase(LogBufferElement * element)584     void erase(LogBufferElement* element) {
585         log_id_t log_id = element->getLogId();
586         --mElements[log_id];
587         --mDroppedElements[log_id];
588     }
589 
sort(uid_t uid,pid_t pid,size_t len,log_id id)590     LogFindWorst<UidEntry> sort(uid_t uid, pid_t pid, size_t len, log_id id) {
591         return LogFindWorst<UidEntry>(uidTable[id].sort(uid, pid, len));
592     }
sortPids(uid_t uid,pid_t pid,size_t len,log_id id)593     LogFindWorst<PidEntry> sortPids(uid_t uid, pid_t pid, size_t len,
594                                     log_id id) {
595         return LogFindWorst<PidEntry>(pidSystemTable[id].sort(uid, pid, len));
596     }
sortTags(uid_t uid,pid_t pid,size_t len,log_id)597     LogFindWorst<TagEntry> sortTags(uid_t uid, pid_t pid, size_t len, log_id) {
598         return LogFindWorst<TagEntry>(tagTable.sort(uid, pid, len));
599     }
600 
601     // fast track current value by id only
sizes(log_id_t id)602     size_t sizes(log_id_t id) const {
603         return mSizes[id];
604     }
elements(log_id_t id)605     size_t elements(log_id_t id) const {
606         return mElements[id];
607     }
realElements(log_id_t id)608     size_t realElements(log_id_t id) const {
609         return mElements[id] - mDroppedElements[id];
610     }
sizesTotal(log_id_t id)611     size_t sizesTotal(log_id_t id) const {
612         return mSizesTotal[id];
613     }
elementsTotal(log_id_t id)614     size_t elementsTotal(log_id_t id) const {
615         return mElementsTotal[id];
616     }
sizesTotal()617     static size_t sizesTotal() {
618         return SizesTotal;
619     }
620 
621     std::string format(uid_t uid, pid_t pid, unsigned int logMask) const;
622 
623     // helper (must be locked directly or implicitly by mLogElementsLock)
624     const char* pidToName(pid_t pid) const;
625     uid_t pidToUid(pid_t pid);
626     const char* uidToName(uid_t uid) const;
627 };
628 
629 #endif  // _LOGD_LOG_STATISTICS_H__
630