LogStatistics.h revision f99a7d602a6fe90058e47d5e6140dfc9b30f7481 
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
309namespace android {
310uid_t pidToUid(pid_t pid);
311}
312
313struct PidEntry : public EntryBaseDropped {
314    const pid_t pid;
315    uid_t uid;
316    char* name;
317
318    explicit PidEntry(pid_t pid)
319        : EntryBaseDropped(),
320          pid(pid),
321          uid(android::pidToUid(pid)),
322          name(android::pidToName(pid)) {
323    }
324    explicit PidEntry(const LogBufferElement* element)
325        : EntryBaseDropped(element),
326          pid(element->getPid()),
327          uid(element->getUid()),
328          name(android::pidToName(pid)) {
329    }
330    PidEntry(const PidEntry& element)
331        : EntryBaseDropped(element),
332          pid(element.pid),
333          uid(element.uid),
334          name(element.name ? strdup(element.name) : nullptr) {
335    }
336    ~PidEntry() {
337        free(name);
338    }
339
340    const pid_t& getKey() const {
341        return pid;
342    }
343    const pid_t& getPid() const {
344        return getKey();
345    }
346    const uid_t& getUid() const {
347        return uid;
348    }
349    const char* getName() const {
350        return name;
351    }
352
353    inline void add(pid_t newPid) {
354        if (name && !fastcmp<strncmp>(name, "zygote", 6)) {
355            free(name);
356            name = nullptr;
357        }
358        if (!name) {
359            name = android::pidToName(newPid);
360        }
361    }
362
363    inline void add(const LogBufferElement* element) {
364        uid_t incomingUid = element->getUid();
365        if (getUid() != incomingUid) {
366            uid = incomingUid;
367            free(name);
368            name = android::pidToName(element->getPid());
369        } else {
370            add(element->getPid());
371        }
372        EntryBaseDropped::add(element);
373    }
374
375    std::string formatHeader(const std::string& name, log_id_t id) const;
376    std::string format(const LogStatistics& stat, log_id_t id) const;
377};
378
379struct TidEntry : public EntryBaseDropped {
380    const pid_t tid;
381    pid_t pid;
382    uid_t uid;
383    char* name;
384
385    TidEntry(pid_t tid, pid_t pid)
386        : EntryBaseDropped(),
387          tid(tid),
388          pid(pid),
389          uid(android::pidToUid(tid)),
390          name(android::tidToName(tid)) {
391    }
392    explicit TidEntry(const LogBufferElement* element)
393        : EntryBaseDropped(element),
394          tid(element->getTid()),
395          pid(element->getPid()),
396          uid(element->getUid()),
397          name(android::tidToName(tid)) {
398    }
399    TidEntry(const TidEntry& element)
400        : EntryBaseDropped(element),
401          tid(element.tid),
402          pid(element.pid),
403          uid(element.uid),
404          name(element.name ? strdup(element.name) : nullptr) {
405    }
406    ~TidEntry() {
407        free(name);
408    }
409
410    const pid_t& getKey() const {
411        return tid;
412    }
413    const pid_t& getTid() const {
414        return getKey();
415    }
416    const pid_t& getPid() const {
417        return pid;
418    }
419    const uid_t& getUid() const {
420        return uid;
421    }
422    const char* getName() const {
423        return name;
424    }
425
426    inline void add(pid_t incomingTid) {
427        if (name && !fastcmp<strncmp>(name, "zygote", 6)) {
428            free(name);
429            name = nullptr;
430        }
431        if (!name) {
432            name = android::tidToName(incomingTid);
433        }
434    }
435
436    inline void add(const LogBufferElement* element) {
437        uid_t incomingUid = element->getUid();
438        pid_t incomingPid = element->getPid();
439        if ((getUid() != incomingUid) || (getPid() != incomingPid)) {
440            uid = incomingUid;
441            pid = incomingPid;
442            free(name);
443            name = android::tidToName(element->getTid());
444        } else {
445            add(element->getTid());
446        }
447        EntryBaseDropped::add(element);
448    }
449
450    std::string formatHeader(const std::string& name, log_id_t id) const;
451    std::string format(const LogStatistics& stat, log_id_t id) const;
452};
453
454struct TagEntry : public EntryBaseDropped {
455    const uint32_t tag;
456    pid_t pid;
457    uid_t uid;
458
459    explicit TagEntry(const LogBufferElement* element)
460        : EntryBaseDropped(element),
461          tag(element->getTag()),
462          pid(element->getPid()),
463          uid(element->getUid()) {
464    }
465
466    const uint32_t& getKey() const {
467        return tag;
468    }
469    const pid_t& getPid() const {
470        return pid;
471    }
472    const uid_t& getUid() const {
473        return uid;
474    }
475    const char* getName() const {
476        return android::tagToName(tag);
477    }
478
479    inline void add(const LogBufferElement* element) {
480        if (uid != element->getUid()) {
481            uid = -1;
482        }
483        if (pid != element->getPid()) {
484            pid = -1;
485        }
486        EntryBaseDropped::add(element);
487    }
488
489    std::string formatHeader(const std::string& name, log_id_t id) const;
490    std::string format(const LogStatistics& stat, log_id_t id) const;
491};
492
493struct TagNameKey {
494    std::string* alloc;
495    std::experimental::string_view name;  // Saves space if const char*
496
497    explicit TagNameKey(const LogBufferElement* element)
498        : alloc(nullptr), name("", strlen("")) {
499        if (element->isBinary()) {
500            uint32_t tag = element->getTag();
501            if (tag) {
502                const char* cp = android::tagToName(tag);
503                if (cp) {
504                    name = std::experimental::string_view(cp, strlen(cp));
505                    return;
506                }
507            }
508            alloc = new std::string(
509                android::base::StringPrintf("[%" PRIu32 "]", tag));
510            if (!alloc) return;
511            name = std::experimental::string_view(alloc->c_str(), alloc->size());
512            return;
513        }
514        const char* msg = element->getMsg();
515        if (!msg) {
516            name = std::experimental::string_view("chatty", strlen("chatty"));
517            return;
518        }
519        ++msg;
520        unsigned short len = element->getMsgLen();
521        len = (len <= 1) ? 0 : strnlen(msg, len - 1);
522        if (!len) {
523            name = std::experimental::string_view("<NULL>", strlen("<NULL>"));
524            return;
525        }
526        alloc = new std::string(msg, len);
527        if (!alloc) return;
528        name = std::experimental::string_view(alloc->c_str(), alloc->size());
529    }
530
531    explicit TagNameKey(TagNameKey&& rval)
532        : alloc(rval.alloc), name(rval.name.data(), rval.name.length()) {
533        rval.alloc = nullptr;
534    }
535
536    explicit TagNameKey(const TagNameKey& rval)
537        : alloc(rval.alloc ? new std::string(*rval.alloc) : nullptr),
538          name(alloc ? alloc->data() : rval.name.data(), rval.name.length()) {
539    }
540
541    ~TagNameKey() {
542        if (alloc) delete alloc;
543    }
544
545    operator const std::experimental::string_view() const {
546        return name;
547    }
548
549    const char* data() const {
550        return name.data();
551    }
552    size_t length() const {
553        return name.length();
554    }
555
556    bool operator==(const TagNameKey& rval) const {
557        if (length() != rval.length()) return false;
558        if (length() == 0) return true;
559        return fastcmp<strncmp>(data(), rval.data(), length()) == 0;
560    }
561    bool operator!=(const TagNameKey& rval) const {
562        return !(*this == rval);
563    }
564
565    size_t getAllocLength() const {
566        return alloc ? alloc->length() + 1 + sizeof(std::string) : 0;
567    }
568};
569
570// Hash for TagNameKey
571template <>
572struct std::hash<TagNameKey>
573    : public std::unary_function<const TagNameKey&, size_t> {
574    size_t operator()(const TagNameKey& __t) const noexcept {
575        if (!__t.length()) return 0;
576        return std::hash<std::experimental::string_view>()(
577            std::experimental::string_view(__t));
578    }
579};
580
581struct TagNameEntry : public EntryBase {
582    pid_t tid;
583    pid_t pid;
584    uid_t uid;
585    TagNameKey name;
586
587    explicit TagNameEntry(const LogBufferElement* element)
588        : EntryBase(element),
589          tid(element->getTid()),
590          pid(element->getPid()),
591          uid(element->getUid()),
592          name(element) {
593    }
594
595    const TagNameKey& getKey() const {
596        return name;
597    }
598    const pid_t& getTid() const {
599        return tid;
600    }
601    const pid_t& getPid() const {
602        return pid;
603    }
604    const uid_t& getUid() const {
605        return uid;
606    }
607    const char* getName() const {
608        return name.data();
609    }
610    size_t getNameAllocLength() const {
611        return name.getAllocLength();
612    }
613
614    inline void add(const LogBufferElement* element) {
615        if (uid != element->getUid()) {
616            uid = -1;
617        }
618        if (pid != element->getPid()) {
619            pid = -1;
620        }
621        if (tid != element->getTid()) {
622            tid = -1;
623        }
624        EntryBase::add(element);
625    }
626
627    std::string formatHeader(const std::string& name, log_id_t id) const;
628    std::string format(const LogStatistics& stat, log_id_t id) const;
629};
630
631template <typename TEntry>
632class LogFindWorst {
633    std::unique_ptr<const TEntry* []> sorted;
634
635   public:
636    explicit LogFindWorst(std::unique_ptr<const TEntry* []>&& sorted)
637        : sorted(std::move(sorted)) {
638    }
639
640    void findWorst(int& worst, size_t& worst_sizes, size_t& second_worst_sizes,
641                   size_t threshold) {
642        if (sorted.get() && sorted[0] && sorted[1]) {
643            worst_sizes = sorted[0]->getSizes();
644            if ((worst_sizes > threshold)
645                // Allow time horizon to extend roughly tenfold, assume
646                // average entry length is 100 characters.
647                && (worst_sizes > (10 * sorted[0]->getDropped()))) {
648                worst = sorted[0]->getKey();
649                second_worst_sizes = sorted[1]->getSizes();
650                if (second_worst_sizes < threshold) {
651                    second_worst_sizes = threshold;
652                }
653            }
654        }
655    }
656
657    void findWorst(int& worst, size_t worst_sizes, size_t& second_worst_sizes) {
658        if (sorted.get() && sorted[0] && sorted[1]) {
659            worst = sorted[0]->getKey();
660            second_worst_sizes =
661                worst_sizes - sorted[0]->getSizes() + sorted[1]->getSizes();
662        }
663    }
664};
665
666// Log Statistics
667class LogStatistics {
668    friend UidEntry;
669
670    size_t mSizes[LOG_ID_MAX];
671    size_t mElements[LOG_ID_MAX];
672    size_t mDroppedElements[LOG_ID_MAX];
673    size_t mSizesTotal[LOG_ID_MAX];
674    size_t mElementsTotal[LOG_ID_MAX];
675    log_time mOldest[LOG_ID_MAX];
676    log_time mNewest[LOG_ID_MAX];
677    log_time mNewestDropped[LOG_ID_MAX];
678    static size_t SizesTotal;
679    bool enable;
680
681    // uid to size list
682    typedef LogHashtable<uid_t, UidEntry> uidTable_t;
683    uidTable_t uidTable[LOG_ID_MAX];
684
685    // pid of system to size list
686    typedef LogHashtable<pid_t, PidEntry> pidSystemTable_t;
687    pidSystemTable_t pidSystemTable[LOG_ID_MAX];
688
689    // pid to uid list
690    typedef LogHashtable<pid_t, PidEntry> pidTable_t;
691    pidTable_t pidTable;
692
693    // tid to uid list
694    typedef LogHashtable<pid_t, TidEntry> tidTable_t;
695    tidTable_t tidTable;
696
697    // tag list
698    typedef LogHashtable<uint32_t, TagEntry> tagTable_t;
699    tagTable_t tagTable;
700
701    // security tag list
702    tagTable_t securityTagTable;
703
704    // global tag list
705    typedef LogHashtable<TagNameKey, TagNameEntry> tagNameTable_t;
706    tagNameTable_t tagNameTable;
707
708    size_t sizeOf() const {
709        size_t size = sizeof(*this) + pidTable.sizeOf() + tidTable.sizeOf() +
710                      tagTable.sizeOf() + securityTagTable.sizeOf() +
711                      tagNameTable.sizeOf() +
712                      (pidTable.size() * sizeof(pidTable_t::iterator)) +
713                      (tagTable.size() * sizeof(tagTable_t::iterator));
714        for (auto it : pidTable) {
715            const char* name = it.second.getName();
716            if (name) size += strlen(name) + 1;
717        }
718        for (auto it : tidTable) {
719            const char* name = it.second.getName();
720            if (name) size += strlen(name) + 1;
721        }
722        for (auto it : tagNameTable) size += it.second.getNameAllocLength();
723        log_id_for_each(id) {
724            size += uidTable[id].sizeOf();
725            size += uidTable[id].size() * sizeof(uidTable_t::iterator);
726            size += pidSystemTable[id].sizeOf();
727            size +=
728                pidSystemTable[id].size() * sizeof(pidSystemTable_t::iterator);
729        }
730        return size;
731    }
732
733   public:
734    LogStatistics();
735
736    void enableStatistics() {
737        enable = true;
738    }
739
740    void addTotal(LogBufferElement* entry);
741    void add(LogBufferElement* entry);
742    void subtract(LogBufferElement* entry);
743    // entry->setDropped(1) must follow this call
744    void drop(LogBufferElement* entry);
745    // Correct for coalescing two entries referencing dropped content
746    void erase(LogBufferElement* element) {
747        log_id_t log_id = element->getLogId();
748        --mElements[log_id];
749        --mDroppedElements[log_id];
750    }
751
752    LogFindWorst<UidEntry> sort(uid_t uid, pid_t pid, size_t len, log_id id) {
753        return LogFindWorst<UidEntry>(uidTable[id].sort(uid, pid, len));
754    }
755    LogFindWorst<PidEntry> sortPids(uid_t uid, pid_t pid, size_t len,
756                                    log_id id) {
757        return LogFindWorst<PidEntry>(pidSystemTable[id].sort(uid, pid, len));
758    }
759    LogFindWorst<TagEntry> sortTags(uid_t uid, pid_t pid, size_t len, log_id) {
760        return LogFindWorst<TagEntry>(tagTable.sort(uid, pid, len));
761    }
762
763    // fast track current value by id only
764    size_t sizes(log_id_t id) const {
765        return mSizes[id];
766    }
767    size_t elements(log_id_t id) const {
768        return mElements[id];
769    }
770    size_t realElements(log_id_t id) const {
771        return mElements[id] - mDroppedElements[id];
772    }
773    size_t sizesTotal(log_id_t id) const {
774        return mSizesTotal[id];
775    }
776    size_t elementsTotal(log_id_t id) const {
777        return mElementsTotal[id];
778    }
779    static size_t sizesTotal() {
780        return SizesTotal;
781    }
782
783    std::string format(uid_t uid, pid_t pid, unsigned int logMask) const;
784
785    // helper (must be locked directly or implicitly by mLogElementsLock)
786    const char* pidToName(pid_t pid) const;
787    uid_t pidToUid(pid_t pid);
788    const char* uidToName(uid_t uid) const;
789};
790
791#endif  // _LOGD_LOG_STATISTICS_H__
792