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 <inttypes.h>
22#include <stdint.h>
23#include <stdlib.h>
24#include <string.h>
25#include <sys/types.h>
26
27#include <algorithm>  // std::max
28#include <experimental/string_view>
29#include <memory>
30#include <string>  // std::string
31#include <unordered_map>
32
33#include <android-base/stringprintf.h>
34#include <android/log.h>
35#include <log/log_time.h>
36#include <private/android_filesystem_config.h>
37#include <utils/FastStrcmp.h>
38
39#include "LogBufferElement.h"
40#include "LogUtils.h"
41
42#define log_id_for_each(i) \
43    for (log_id_t i = LOG_ID_MIN; (i) < LOG_ID_MAX; (i) = (log_id_t)((i) + 1))
44
45class LogStatistics;
46
47template <typename TKey, typename TEntry>
48class LogHashtable {
49    std::unordered_map<TKey, TEntry> map;
50
51    size_t bucket_size() const {
52        size_t count = 0;
53        for (size_t idx = 0; idx < map.bucket_count(); ++idx) {
54            size_t bucket_size = map.bucket_size(idx);
55            if (bucket_size == 0) bucket_size = 1;
56            count += bucket_size;
57        }
58        float load_factor = map.max_load_factor();
59        if (load_factor < 1.0) return count;
60        return count * load_factor;
61    }
62
63    static const size_t unordered_map_per_entry_overhead = sizeof(void*);
64    static const size_t unordered_map_bucket_overhead = sizeof(void*);
65
66   public:
67    size_t size() const {
68        return map.size();
69    }
70
71    // Estimate unordered_map memory usage.
72    size_t sizeOf() const {
73        return sizeof(*this) +
74               (size() * (sizeof(TEntry) + unordered_map_per_entry_overhead)) +
75               (bucket_size() * sizeof(size_t) + unordered_map_bucket_overhead);
76    }
77
78    typedef typename std::unordered_map<TKey, TEntry>::iterator iterator;
79    typedef
80        typename std::unordered_map<TKey, TEntry>::const_iterator const_iterator;
81
82    std::unique_ptr<const TEntry* []> sort(uid_t uid, pid_t pid,
83                                           size_t len) const {
84        if (!len) {
85            std::unique_ptr<const TEntry* []> sorted(nullptr);
86            return sorted;
87        }
88
89        const TEntry** retval = new const TEntry*[len];
90        memset(retval, 0, sizeof(*retval) * len);
91
92        for (const_iterator it = map.begin(); it != map.end(); ++it) {
93            const TEntry& entry = it->second;
94
95            if ((uid != AID_ROOT) && (uid != entry.getUid())) {
96                continue;
97            }
98            if (pid && entry.getPid() && (pid != entry.getPid())) {
99                continue;
100            }
101
102            size_t sizes = entry.getSizes();
103            ssize_t index = len - 1;
104            while ((!retval[index] || (sizes > retval[index]->getSizes())) &&
105                   (--index >= 0))
106                ;
107            if (++index < (ssize_t)len) {
108                size_t num = len - index - 1;
109                if (num) {
110                    memmove(&retval[index + 1], &retval[index],
111                            num * sizeof(retval[0]));
112                }
113                retval[index] = &entry;
114            }
115        }
116        std::unique_ptr<const TEntry* []> sorted(retval);
117        return sorted;
118    }
119
120    inline iterator add(const TKey& key, const LogBufferElement* element) {
121        iterator it = map.find(key);
122        if (it == map.end()) {
123            it = map.insert(std::make_pair(key, TEntry(element))).first;
124        } else {
125            it->second.add(element);
126        }
127        return it;
128    }
129
130    inline iterator add(TKey key) {
131        iterator it = map.find(key);
132        if (it == map.end()) {
133            it = map.insert(std::make_pair(key, TEntry(key))).first;
134        } else {
135            it->second.add(key);
136        }
137        return it;
138    }
139
140    void subtract(TKey&& key, const LogBufferElement* element) {
141        iterator it = map.find(std::move(key));
142        if ((it != map.end()) && it->second.subtract(element)) {
143            map.erase(it);
144        }
145    }
146
147    void subtract(const TKey& key, const LogBufferElement* element) {
148        iterator it = map.find(key);
149        if ((it != map.end()) && it->second.subtract(element)) {
150            map.erase(it);
151        }
152    }
153
154    inline void drop(TKey key, const LogBufferElement* element) {
155        iterator it = map.find(key);
156        if (it != map.end()) {
157            it->second.drop(element);
158        }
159    }
160
161    inline iterator begin() {
162        return map.begin();
163    }
164    inline const_iterator begin() const {
165        return map.begin();
166    }
167    inline iterator end() {
168        return map.end();
169    }
170    inline const_iterator end() const {
171        return map.end();
172    }
173
174    std::string format(const LogStatistics& stat, uid_t uid, pid_t pid,
175                       const std::string& name = std::string(""),
176                       log_id_t id = LOG_ID_MAX) const {
177        static const size_t maximum_sorted_entries = 32;
178        std::string output;
179        std::unique_ptr<const TEntry* []> sorted =
180            sort(uid, pid, maximum_sorted_entries);
181        if (!sorted.get()) {
182            return output;
183        }
184        bool headerPrinted = false;
185        for (size_t index = 0; index < maximum_sorted_entries; ++index) {
186            const TEntry* entry = sorted[index];
187            if (!entry) {
188                break;
189            }
190            if (entry->getSizes() <= (sorted[0]->getSizes() / 100)) {
191                break;
192            }
193            if (!headerPrinted) {
194                output += "\n\n";
195                output += entry->formatHeader(name, id);
196                headerPrinted = true;
197            }
198            output += entry->format(stat, id);
199        }
200        return output;
201    }
202};
203
204namespace EntryBaseConstants {
205static constexpr size_t pruned_len = 14;
206static constexpr size_t total_len = 80;
207}
208
209struct EntryBase {
210    size_t size;
211
212    EntryBase() : size(0) {
213    }
214    explicit EntryBase(const LogBufferElement* element)
215        : size(element->getMsgLen()) {
216    }
217
218    size_t getSizes() const {
219        return size;
220    }
221
222    inline void add(const LogBufferElement* element) {
223        size += element->getMsgLen();
224    }
225    inline bool subtract(const LogBufferElement* element) {
226        size -= element->getMsgLen();
227        return !size;
228    }
229
230    static std::string formatLine(const std::string& name,
231                                  const std::string& size,
232                                  const std::string& pruned) {
233        ssize_t drop_len =
234            std::max(pruned.length() + 1, EntryBaseConstants::pruned_len);
235        ssize_t size_len =
236            std::max(size.length() + 1, EntryBaseConstants::total_len -
237                                            name.length() - drop_len - 1);
238
239        std::string ret = android::base::StringPrintf(
240            "%s%*s%*s", name.c_str(), (int)size_len, size.c_str(),
241            (int)drop_len, pruned.c_str());
242        // remove any trailing spaces
243        size_t pos = ret.size();
244        size_t len = 0;
245        while (pos && isspace(ret[--pos])) ++len;
246        if (len) ret.erase(pos + 1, len);
247        return ret + "\n";
248    }
249};
250
251struct EntryBaseDropped : public EntryBase {
252    size_t dropped;
253
254    EntryBaseDropped() : dropped(0) {
255    }
256    explicit EntryBaseDropped(const LogBufferElement* element)
257        : EntryBase(element), dropped(element->getDropped()) {
258    }
259
260    size_t getDropped() const {
261        return dropped;
262    }
263
264    inline void add(const LogBufferElement* element) {
265        dropped += element->getDropped();
266        EntryBase::add(element);
267    }
268    inline bool subtract(const LogBufferElement* element) {
269        dropped -= element->getDropped();
270        return EntryBase::subtract(element) && !dropped;
271    }
272    inline void drop(const LogBufferElement* element) {
273        dropped += 1;
274        EntryBase::subtract(element);
275    }
276};
277
278struct UidEntry : public EntryBaseDropped {
279    const uid_t uid;
280    pid_t pid;
281
282    explicit UidEntry(const LogBufferElement* element)
283        : EntryBaseDropped(element),
284          uid(element->getUid()),
285          pid(element->getPid()) {
286    }
287
288    inline const uid_t& getKey() const {
289        return uid;
290    }
291    inline const uid_t& getUid() const {
292        return getKey();
293    }
294    inline const pid_t& getPid() const {
295        return pid;
296    }
297
298    inline void add(const LogBufferElement* element) {
299        if (pid != element->getPid()) {
300            pid = -1;
301        }
302        EntryBaseDropped::add(element);
303    }
304
305    std::string formatHeader(const std::string& name, log_id_t id) const;
306    std::string format(const LogStatistics& stat, log_id_t id) const;
307};
308
309struct PidEntry : public EntryBaseDropped {
310    const pid_t pid;
311    uid_t uid;
312    char* name;
313
314    explicit PidEntry(pid_t pid)
315        : EntryBaseDropped(),
316          pid(pid),
317          uid(android::pidToUid(pid)),
318          name(android::pidToName(pid)) {
319    }
320    explicit PidEntry(const LogBufferElement* element)
321        : EntryBaseDropped(element),
322          pid(element->getPid()),
323          uid(element->getUid()),
324          name(android::pidToName(pid)) {
325    }
326    PidEntry(const PidEntry& element)
327        : EntryBaseDropped(element),
328          pid(element.pid),
329          uid(element.uid),
330          name(element.name ? strdup(element.name) : nullptr) {
331    }
332    ~PidEntry() {
333        free(name);
334    }
335
336    const pid_t& getKey() const {
337        return pid;
338    }
339    const pid_t& getPid() const {
340        return getKey();
341    }
342    const uid_t& getUid() const {
343        return uid;
344    }
345    const char* getName() const {
346        return name;
347    }
348
349    inline void add(pid_t newPid) {
350        if (name && !fastcmp<strncmp>(name, "zygote", 6)) {
351            free(name);
352            name = nullptr;
353        }
354        if (!name) {
355            name = android::pidToName(newPid);
356        }
357    }
358
359    inline void add(const LogBufferElement* element) {
360        uid_t incomingUid = element->getUid();
361        if (getUid() != incomingUid) {
362            uid = incomingUid;
363            free(name);
364            name = android::pidToName(element->getPid());
365        } else {
366            add(element->getPid());
367        }
368        EntryBaseDropped::add(element);
369    }
370
371    std::string formatHeader(const std::string& name, log_id_t id) const;
372    std::string format(const LogStatistics& stat, log_id_t id) const;
373};
374
375struct TidEntry : public EntryBaseDropped {
376    const pid_t tid;
377    pid_t pid;
378    uid_t uid;
379    char* name;
380
381    TidEntry(pid_t tid, pid_t pid)
382        : EntryBaseDropped(),
383          tid(tid),
384          pid(pid),
385          uid(android::pidToUid(tid)),
386          name(android::tidToName(tid)) {
387    }
388    TidEntry(pid_t tid)
389        : EntryBaseDropped(),
390          tid(tid),
391          pid(android::tidToPid(tid)),
392          uid(android::pidToUid(tid)),
393          name(android::tidToName(tid)) {
394    }
395    explicit TidEntry(const LogBufferElement* element)
396        : EntryBaseDropped(element),
397          tid(element->getTid()),
398          pid(element->getPid()),
399          uid(element->getUid()),
400          name(android::tidToName(tid)) {
401    }
402    TidEntry(const TidEntry& element)
403        : EntryBaseDropped(element),
404          tid(element.tid),
405          pid(element.pid),
406          uid(element.uid),
407          name(element.name ? strdup(element.name) : nullptr) {
408    }
409    ~TidEntry() {
410        free(name);
411    }
412
413    const pid_t& getKey() const {
414        return tid;
415    }
416    const pid_t& getTid() const {
417        return getKey();
418    }
419    const pid_t& getPid() const {
420        return pid;
421    }
422    const uid_t& getUid() const {
423        return uid;
424    }
425    const char* getName() const {
426        return name;
427    }
428
429    inline void add(pid_t incomingTid) {
430        if (name && !fastcmp<strncmp>(name, "zygote", 6)) {
431            free(name);
432            name = nullptr;
433        }
434        if (!name) {
435            name = android::tidToName(incomingTid);
436        }
437    }
438
439    inline void add(const LogBufferElement* element) {
440        uid_t incomingUid = element->getUid();
441        pid_t incomingPid = element->getPid();
442        if ((getUid() != incomingUid) || (getPid() != incomingPid)) {
443            uid = incomingUid;
444            pid = incomingPid;
445            free(name);
446            name = android::tidToName(element->getTid());
447        } else {
448            add(element->getTid());
449        }
450        EntryBaseDropped::add(element);
451    }
452
453    std::string formatHeader(const std::string& name, log_id_t id) const;
454    std::string format(const LogStatistics& stat, log_id_t id) const;
455};
456
457struct TagEntry : public EntryBaseDropped {
458    const uint32_t tag;
459    pid_t pid;
460    uid_t uid;
461
462    explicit TagEntry(const LogBufferElement* element)
463        : EntryBaseDropped(element),
464          tag(element->getTag()),
465          pid(element->getPid()),
466          uid(element->getUid()) {
467    }
468
469    const uint32_t& getKey() const {
470        return tag;
471    }
472    const pid_t& getPid() const {
473        return pid;
474    }
475    const uid_t& getUid() const {
476        return uid;
477    }
478    const char* getName() const {
479        return android::tagToName(tag);
480    }
481
482    inline void add(const LogBufferElement* element) {
483        if (uid != element->getUid()) {
484            uid = -1;
485        }
486        if (pid != element->getPid()) {
487            pid = -1;
488        }
489        EntryBaseDropped::add(element);
490    }
491
492    std::string formatHeader(const std::string& name, log_id_t id) const;
493    std::string format(const LogStatistics& stat, log_id_t id) const;
494};
495
496struct TagNameKey {
497    std::string* alloc;
498    std::experimental::string_view name;  // Saves space if const char*
499
500    explicit TagNameKey(const LogBufferElement* element)
501        : alloc(nullptr), name("", strlen("")) {
502        if (element->isBinary()) {
503            uint32_t tag = element->getTag();
504            if (tag) {
505                const char* cp = android::tagToName(tag);
506                if (cp) {
507                    name = std::experimental::string_view(cp, strlen(cp));
508                    return;
509                }
510            }
511            alloc = new std::string(
512                android::base::StringPrintf("[%" PRIu32 "]", tag));
513            if (!alloc) return;
514            name = std::experimental::string_view(alloc->c_str(), alloc->size());
515            return;
516        }
517        const char* msg = element->getMsg();
518        if (!msg) {
519            name = std::experimental::string_view("chatty", strlen("chatty"));
520            return;
521        }
522        ++msg;
523        unsigned short len = element->getMsgLen();
524        len = (len <= 1) ? 0 : strnlen(msg, len - 1);
525        if (!len) {
526            name = std::experimental::string_view("<NULL>", strlen("<NULL>"));
527            return;
528        }
529        alloc = new std::string(msg, len);
530        if (!alloc) return;
531        name = std::experimental::string_view(alloc->c_str(), alloc->size());
532    }
533
534    explicit TagNameKey(TagNameKey&& rval)
535        : alloc(rval.alloc), name(rval.name.data(), rval.name.length()) {
536        rval.alloc = nullptr;
537    }
538
539    explicit TagNameKey(const TagNameKey& rval)
540        : alloc(rval.alloc ? new std::string(*rval.alloc) : nullptr),
541          name(alloc ? alloc->data() : rval.name.data(), rval.name.length()) {
542    }
543
544    ~TagNameKey() {
545        if (alloc) delete alloc;
546    }
547
548    operator const std::experimental::string_view() const {
549        return name;
550    }
551
552    const char* data() const {
553        return name.data();
554    }
555    size_t length() const {
556        return name.length();
557    }
558
559    bool operator==(const TagNameKey& rval) const {
560        if (length() != rval.length()) return false;
561        if (length() == 0) return true;
562        return fastcmp<strncmp>(data(), rval.data(), length()) == 0;
563    }
564    bool operator!=(const TagNameKey& rval) const {
565        return !(*this == rval);
566    }
567
568    size_t getAllocLength() const {
569        return alloc ? alloc->length() + 1 + sizeof(std::string) : 0;
570    }
571};
572
573// Hash for TagNameKey
574template <>
575struct std::hash<TagNameKey>
576    : public std::unary_function<const TagNameKey&, size_t> {
577    size_t operator()(const TagNameKey& __t) const noexcept {
578        if (!__t.length()) return 0;
579        return std::hash<std::experimental::string_view>()(
580            std::experimental::string_view(__t));
581    }
582};
583
584struct TagNameEntry : public EntryBase {
585    pid_t tid;
586    pid_t pid;
587    uid_t uid;
588    TagNameKey name;
589
590    explicit TagNameEntry(const LogBufferElement* element)
591        : EntryBase(element),
592          tid(element->getTid()),
593          pid(element->getPid()),
594          uid(element->getUid()),
595          name(element) {
596    }
597
598    const TagNameKey& getKey() const {
599        return name;
600    }
601    const pid_t& getTid() const {
602        return tid;
603    }
604    const pid_t& getPid() const {
605        return pid;
606    }
607    const uid_t& getUid() const {
608        return uid;
609    }
610    const char* getName() const {
611        return name.data();
612    }
613    size_t getNameAllocLength() const {
614        return name.getAllocLength();
615    }
616
617    inline void add(const LogBufferElement* element) {
618        if (uid != element->getUid()) {
619            uid = -1;
620        }
621        if (pid != element->getPid()) {
622            pid = -1;
623        }
624        if (tid != element->getTid()) {
625            tid = -1;
626        }
627        EntryBase::add(element);
628    }
629
630    std::string formatHeader(const std::string& name, log_id_t id) const;
631    std::string format(const LogStatistics& stat, log_id_t id) const;
632};
633
634template <typename TEntry>
635class LogFindWorst {
636    std::unique_ptr<const TEntry* []> sorted;
637
638   public:
639    explicit LogFindWorst(std::unique_ptr<const TEntry* []>&& sorted)
640        : sorted(std::move(sorted)) {
641    }
642
643    void findWorst(int& worst, size_t& worst_sizes, size_t& second_worst_sizes,
644                   size_t threshold) {
645        if (sorted.get() && sorted[0] && sorted[1]) {
646            worst_sizes = sorted[0]->getSizes();
647            if ((worst_sizes > threshold)
648                // Allow time horizon to extend roughly tenfold, assume
649                // average entry length is 100 characters.
650                && (worst_sizes > (10 * sorted[0]->getDropped()))) {
651                worst = sorted[0]->getKey();
652                second_worst_sizes = sorted[1]->getSizes();
653                if (second_worst_sizes < threshold) {
654                    second_worst_sizes = threshold;
655                }
656            }
657        }
658    }
659
660    void findWorst(int& worst, size_t worst_sizes, size_t& second_worst_sizes) {
661        if (sorted.get() && sorted[0] && sorted[1]) {
662            worst = sorted[0]->getKey();
663            second_worst_sizes =
664                worst_sizes - sorted[0]->getSizes() + sorted[1]->getSizes();
665        }
666    }
667};
668
669// Log Statistics
670class LogStatistics {
671    friend UidEntry;
672
673    size_t mSizes[LOG_ID_MAX];
674    size_t mElements[LOG_ID_MAX];
675    size_t mDroppedElements[LOG_ID_MAX];
676    size_t mSizesTotal[LOG_ID_MAX];
677    size_t mElementsTotal[LOG_ID_MAX];
678    log_time mOldest[LOG_ID_MAX];
679    log_time mNewest[LOG_ID_MAX];
680    log_time mNewestDropped[LOG_ID_MAX];
681    static size_t SizesTotal;
682    bool enable;
683
684    // uid to size list
685    typedef LogHashtable<uid_t, UidEntry> uidTable_t;
686    uidTable_t uidTable[LOG_ID_MAX];
687
688    // pid of system to size list
689    typedef LogHashtable<pid_t, PidEntry> pidSystemTable_t;
690    pidSystemTable_t pidSystemTable[LOG_ID_MAX];
691
692    // pid to uid list
693    typedef LogHashtable<pid_t, PidEntry> pidTable_t;
694    pidTable_t pidTable;
695
696    // tid to uid list
697    typedef LogHashtable<pid_t, TidEntry> tidTable_t;
698    tidTable_t tidTable;
699
700    // tag list
701    typedef LogHashtable<uint32_t, TagEntry> tagTable_t;
702    tagTable_t tagTable;
703
704    // security tag list
705    tagTable_t securityTagTable;
706
707    // global tag list
708    typedef LogHashtable<TagNameKey, TagNameEntry> tagNameTable_t;
709    tagNameTable_t tagNameTable;
710
711    size_t sizeOf() const {
712        size_t size = sizeof(*this) + pidTable.sizeOf() + tidTable.sizeOf() +
713                      tagTable.sizeOf() + securityTagTable.sizeOf() +
714                      tagNameTable.sizeOf() +
715                      (pidTable.size() * sizeof(pidTable_t::iterator)) +
716                      (tagTable.size() * sizeof(tagTable_t::iterator));
717        for (auto it : pidTable) {
718            const char* name = it.second.getName();
719            if (name) size += strlen(name) + 1;
720        }
721        for (auto it : tidTable) {
722            const char* name = it.second.getName();
723            if (name) size += strlen(name) + 1;
724        }
725        for (auto it : tagNameTable) size += it.second.getNameAllocLength();
726        log_id_for_each(id) {
727            size += uidTable[id].sizeOf();
728            size += uidTable[id].size() * sizeof(uidTable_t::iterator);
729            size += pidSystemTable[id].sizeOf();
730            size +=
731                pidSystemTable[id].size() * sizeof(pidSystemTable_t::iterator);
732        }
733        return size;
734    }
735
736   public:
737    LogStatistics();
738
739    void enableStatistics() {
740        enable = true;
741    }
742
743    void addTotal(LogBufferElement* entry);
744    void add(LogBufferElement* entry);
745    void subtract(LogBufferElement* entry);
746    // entry->setDropped(1) must follow this call
747    void drop(LogBufferElement* entry);
748    // Correct for coalescing two entries referencing dropped content
749    void erase(LogBufferElement* element) {
750        log_id_t log_id = element->getLogId();
751        --mElements[log_id];
752        --mDroppedElements[log_id];
753    }
754
755    LogFindWorst<UidEntry> sort(uid_t uid, pid_t pid, size_t len, log_id id) {
756        return LogFindWorst<UidEntry>(uidTable[id].sort(uid, pid, len));
757    }
758    LogFindWorst<PidEntry> sortPids(uid_t uid, pid_t pid, size_t len,
759                                    log_id id) {
760        return LogFindWorst<PidEntry>(pidSystemTable[id].sort(uid, pid, len));
761    }
762    LogFindWorst<TagEntry> sortTags(uid_t uid, pid_t pid, size_t len, log_id) {
763        return LogFindWorst<TagEntry>(tagTable.sort(uid, pid, len));
764    }
765
766    // fast track current value by id only
767    size_t sizes(log_id_t id) const {
768        return mSizes[id];
769    }
770    size_t elements(log_id_t id) const {
771        return mElements[id];
772    }
773    size_t realElements(log_id_t id) const {
774        return mElements[id] - mDroppedElements[id];
775    }
776    size_t sizesTotal(log_id_t id) const {
777        return mSizesTotal[id];
778    }
779    size_t elementsTotal(log_id_t id) const {
780        return mElementsTotal[id];
781    }
782    static size_t sizesTotal() {
783        return SizesTotal;
784    }
785
786    std::string format(uid_t uid, pid_t pid, unsigned int logMask) const;
787
788    // helper (must be locked directly or implicitly by mLogElementsLock)
789    const char* pidToName(pid_t pid) const;
790    uid_t pidToUid(pid_t pid);
791    pid_t tidToPid(pid_t tid);
792    const char* uidToName(uid_t uid) const;
793};
794
795#endif  // _LOGD_LOG_STATISTICS_H__
796