LogStatistics.h revision 3296291cffd13af13ea9e60a8ac1138101cf8e4c 
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/log.h>
29#include <android-base/stringprintf.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
38class LogStatistics;
39
40template <typename TKey, typename TEntry>
41class LogHashtable {
42
43    std::unordered_map<TKey, TEntry> map;
44
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
60public:
61
62    size_t size() const { return map.size(); }
63
64    // Estimate unordered_map memory usage.
65    size_t sizeOf() const {
66        return sizeof(*this) +
67               (size() * (sizeof(TEntry) + unordered_map_per_entry_overhead)) +
68               (bucket_size() * sizeof(size_t) + unordered_map_bucket_overhead);
69    }
70
71    typedef typename std::unordered_map<TKey, TEntry>::iterator iterator;
72    typedef typename std::unordered_map<TKey, TEntry>::const_iterator const_iterator;
73
74    std::unique_ptr<const TEntry *[]> sort(uid_t uid, pid_t pid,
75                                           size_t len) const {
76        if (!len) {
77            std::unique_ptr<const TEntry *[]> sorted(NULL);
78            return sorted;
79        }
80
81        const TEntry **retval = new const TEntry* [len];
82        memset(retval, 0, sizeof(*retval) * len);
83
84        for(const_iterator it = map.begin(); it != map.end(); ++it) {
85            const TEntry &entry = it->second;
86
87            if ((uid != AID_ROOT) && (uid != entry.getUid())) {
88                continue;
89            }
90            if (pid && entry.getPid() && (pid != entry.getPid())) {
91                continue;
92            }
93
94            size_t sizes = entry.getSizes();
95            ssize_t index = len - 1;
96            while ((!retval[index] || (sizes > retval[index]->getSizes()))
97                    && (--index >= 0))
98                ;
99            if (++index < (ssize_t)len) {
100                size_t num = len - index - 1;
101                if (num) {
102                    memmove(&retval[index + 1], &retval[index],
103                            num * sizeof(retval[0]));
104                }
105                retval[index] = &entry;
106            }
107        }
108        std::unique_ptr<const TEntry *[]> sorted(retval);
109        return sorted;
110    }
111
112    inline iterator add(TKey key, LogBufferElement *element) {
113        iterator it = map.find(key);
114        if (it == map.end()) {
115            it = map.insert(std::make_pair(key, TEntry(element))).first;
116        } else {
117            it->second.add(element);
118        }
119        return it;
120    }
121
122    inline iterator add(TKey key) {
123        iterator it = map.find(key);
124        if (it == map.end()) {
125            it = map.insert(std::make_pair(key, TEntry(key))).first;
126        } else {
127            it->second.add(key);
128        }
129        return it;
130    }
131
132    void subtract(TKey key, LogBufferElement *element) {
133        iterator it = map.find(key);
134        if ((it != map.end()) && it->second.subtract(element)) {
135            map.erase(it);
136        }
137    }
138
139    inline void drop(TKey key, LogBufferElement *element) {
140        iterator it = map.find(key);
141        if (it != map.end()) {
142            it->second.drop(element);
143        }
144    }
145
146    inline iterator begin() { return map.begin(); }
147    inline const_iterator begin() const { return map.begin(); }
148    inline iterator end() { return map.end(); }
149    inline const_iterator end() const { return map.end(); }
150
151    std::string format(
152            const LogStatistics &stat,
153            uid_t uid,
154            pid_t pid,
155            const std::string &name = std::string(""),
156            log_id_t id = LOG_ID_MAX) const {
157        static const size_t maximum_sorted_entries = 32;
158        std::string output;
159        std::unique_ptr<const TEntry *[]> sorted = sort(uid, pid,
160                                                        maximum_sorted_entries);
161        if (!sorted.get()) {
162            return output;
163        }
164        bool headerPrinted = false;
165        for (size_t index = 0; index < maximum_sorted_entries; ++index) {
166            const TEntry *entry = sorted[index];
167            if (!entry) {
168                break;
169            }
170            if (entry->getSizes() <= (sorted[0]->getSizes() / 100)) {
171                break;
172            }
173            if (!headerPrinted) {
174                output += "\n\n";
175                output += entry->formatHeader(name, id);
176                headerPrinted = true;
177            }
178            output += entry->format(stat, id);
179        }
180        return output;
181    }
182
183};
184
185namespace EntryBaseConstants {
186    static constexpr size_t pruned_len = 14;
187    static constexpr size_t total_len = 80;
188}
189
190struct EntryBase {
191    size_t size;
192
193    EntryBase():size(0) { }
194    explicit EntryBase(LogBufferElement *element):size(element->getMsgLen()) { }
195
196    size_t getSizes() const { return size; }
197
198    inline void add(LogBufferElement *element) { size += element->getMsgLen(); }
199    inline bool subtract(LogBufferElement *element) {
200        size -= element->getMsgLen();
201        return !size;
202    }
203
204    static std::string formatLine(
205            const std::string &name,
206            const std::string &size,
207            const std::string &pruned) {
208        ssize_t drop_len = std::max(pruned.length() + 1,
209                                    EntryBaseConstants::pruned_len);
210        ssize_t size_len = std::max(size.length() + 1,
211                                    EntryBaseConstants::total_len
212                                        - name.length() - drop_len - 1);
213
214        if (pruned.length()) {
215            return android::base::StringPrintf("%s%*s%*s\n", name.c_str(),
216                                               (int)size_len, size.c_str(),
217                                               (int)drop_len, pruned.c_str());
218        } else {
219            return android::base::StringPrintf("%s%*s\n", name.c_str(),
220                                               (int)size_len, size.c_str());
221        }
222    }
223};
224
225struct EntryBaseDropped : public EntryBase {
226    size_t dropped;
227
228    EntryBaseDropped():dropped(0) { }
229    explicit EntryBaseDropped(LogBufferElement *element):
230            EntryBase(element),
231            dropped(element->getDropped()) {
232    }
233
234    size_t getDropped() const { return dropped; }
235
236    inline void add(LogBufferElement *element) {
237        dropped += element->getDropped();
238        EntryBase::add(element);
239    }
240    inline bool subtract(LogBufferElement *element) {
241        dropped -= element->getDropped();
242        return EntryBase::subtract(element) && !dropped;
243    }
244    inline void drop(LogBufferElement *element) {
245        dropped += 1;
246        EntryBase::subtract(element);
247    }
248};
249
250struct UidEntry : public EntryBaseDropped {
251    const uid_t uid;
252    pid_t pid;
253
254    explicit UidEntry(LogBufferElement *element):
255            EntryBaseDropped(element),
256            uid(element->getUid()),
257            pid(element->getPid()) {
258    }
259
260    inline const uid_t&getKey() const { return uid; }
261    inline const uid_t&getUid() const { return getKey(); }
262    inline const pid_t&getPid() const { return pid; }
263
264    inline void add(LogBufferElement *element) {
265        if (pid != element->getPid()) {
266            pid = -1;
267        }
268        EntryBaseDropped::add(element);
269    }
270
271    std::string formatHeader(const std::string &name, log_id_t id) const;
272    std::string format(const LogStatistics &stat, log_id_t id) const;
273};
274
275namespace android {
276uid_t pidToUid(pid_t pid);
277}
278
279struct PidEntry : public EntryBaseDropped {
280    const pid_t pid;
281    uid_t uid;
282    char *name;
283
284    explicit PidEntry(pid_t pid):
285            EntryBaseDropped(),
286            pid(pid),
287            uid(android::pidToUid(pid)),
288            name(android::pidToName(pid)) {
289    }
290    explicit PidEntry(LogBufferElement *element):
291            EntryBaseDropped(element),
292            pid(element->getPid()),
293            uid(element->getUid()),
294            name(android::pidToName(pid)) {
295    }
296    PidEntry(const PidEntry &element):
297            EntryBaseDropped(element),
298            pid(element.pid),
299            uid(element.uid),
300            name(element.name ? strdup(element.name) : NULL) {
301    }
302    ~PidEntry() { free(name); }
303
304    const pid_t&getKey() const { return pid; }
305    const pid_t&getPid() const { return getKey(); }
306    const uid_t&getUid() const { return uid; }
307    const char*getName() const { return name; }
308
309    inline void add(pid_t newPid) {
310        if (name && !fastcmp<strncmp>(name, "zygote", 6)) {
311            free(name);
312            name = NULL;
313        }
314        if (!name) {
315            name = android::pidToName(newPid);
316        }
317    }
318
319    inline void add(LogBufferElement *element) {
320        uid_t incomingUid = element->getUid();
321        if (getUid() != incomingUid) {
322            uid = incomingUid;
323            free(name);
324            name = android::pidToName(element->getPid());
325        } else {
326            add(element->getPid());
327        }
328        EntryBaseDropped::add(element);
329    }
330
331    std::string formatHeader(const std::string &name, log_id_t id) const;
332    std::string format(const LogStatistics &stat, log_id_t id) const;
333};
334
335struct TidEntry : public EntryBaseDropped {
336    const pid_t tid;
337    pid_t pid;
338    uid_t uid;
339    char *name;
340
341    TidEntry(pid_t tid, pid_t pid):
342            EntryBaseDropped(),
343            tid(tid),
344            pid(pid),
345            uid(android::pidToUid(tid)),
346            name(android::tidToName(tid)) {
347    }
348    explicit TidEntry(LogBufferElement *element):
349            EntryBaseDropped(element),
350            tid(element->getTid()),
351            pid(element->getPid()),
352            uid(element->getUid()),
353            name(android::tidToName(tid)) {
354    }
355    TidEntry(const TidEntry &element):
356            EntryBaseDropped(element),
357            tid(element.tid),
358            pid(element.pid),
359            uid(element.uid),
360            name(element.name ? strdup(element.name) : NULL) {
361    }
362    ~TidEntry() { free(name); }
363
364    const pid_t&getKey() const { return tid; }
365    const pid_t&getTid() const { return getKey(); }
366    const pid_t&getPid() const { return pid; }
367    const uid_t&getUid() const { return uid; }
368    const char*getName() const { return name; }
369
370    inline void add(pid_t incomingTid) {
371        if (name && !fastcmp<strncmp>(name, "zygote", 6)) {
372            free(name);
373            name = NULL;
374        }
375        if (!name) {
376            name = android::tidToName(incomingTid);
377        }
378    }
379
380    inline void add(LogBufferElement *element) {
381        uid_t incomingUid = element->getUid();
382        pid_t incomingPid = element->getPid();
383        if ((getUid() != incomingUid) || (getPid() != incomingPid)) {
384            uid = incomingUid;
385            pid = incomingPid;
386            free(name);
387            name = android::tidToName(element->getTid());
388        } else {
389            add(element->getTid());
390        }
391        EntryBaseDropped::add(element);
392    }
393
394    std::string formatHeader(const std::string &name, log_id_t id) const;
395    std::string format(const LogStatistics &stat, log_id_t id) const;
396};
397
398struct TagEntry : public EntryBaseDropped {
399    const uint32_t tag;
400    pid_t pid;
401    uid_t uid;
402
403    explicit TagEntry(LogBufferElement *element):
404            EntryBaseDropped(element),
405            tag(element->getTag()),
406            pid(element->getPid()),
407            uid(element->getUid()) {
408    }
409
410    const uint32_t&getKey() const { return tag; }
411    const pid_t&getPid() const { return pid; }
412    const uid_t&getUid() const { return uid; }
413    const char*getName(size_t &len) const { return android::tagToName(&len, tag); }
414
415    inline void add(LogBufferElement *element) {
416        if (uid != element->getUid()) {
417            uid = -1;
418        }
419        if (pid != element->getPid()) {
420            pid = -1;
421        }
422        EntryBaseDropped::add(element);
423    }
424
425    std::string formatHeader(const std::string &name, log_id_t id) const;
426    std::string format(const LogStatistics &stat, log_id_t id) const;
427};
428
429template <typename TEntry>
430class LogFindWorst {
431    std::unique_ptr<const TEntry *[]> sorted;
432
433public:
434
435    explicit LogFindWorst(std::unique_ptr<const TEntry *[]> &&sorted) : sorted(std::move(sorted)) { }
436
437    void findWorst(int &worst,
438                    size_t &worst_sizes, size_t &second_worst_sizes,
439                    size_t threshold) {
440        if (sorted.get() && sorted[0] && sorted[1]) {
441            worst_sizes = sorted[0]->getSizes();
442            if ((worst_sizes > threshold)
443                // Allow time horizon to extend roughly tenfold, assume
444                // average entry length is 100 characters.
445                    && (worst_sizes > (10 * sorted[0]->getDropped()))) {
446                worst = sorted[0]->getKey();
447                second_worst_sizes = sorted[1]->getSizes();
448                if (second_worst_sizes < threshold) {
449                    second_worst_sizes = threshold;
450                }
451            }
452        }
453    }
454
455    void findWorst(int &worst,
456                    size_t worst_sizes, size_t &second_worst_sizes) {
457        if (sorted.get() && sorted[0] && sorted[1]) {
458            worst = sorted[0]->getKey();
459            second_worst_sizes = worst_sizes
460                               - sorted[0]->getSizes()
461                               + sorted[1]->getSizes();
462        }
463    }
464};
465
466// Log Statistics
467class LogStatistics {
468    friend UidEntry;
469
470    size_t mSizes[LOG_ID_MAX];
471    size_t mElements[LOG_ID_MAX];
472    size_t mDroppedElements[LOG_ID_MAX];
473    size_t mSizesTotal[LOG_ID_MAX];
474    size_t mElementsTotal[LOG_ID_MAX];
475    static size_t SizesTotal;
476    bool enable;
477
478    // uid to size list
479    typedef LogHashtable<uid_t, UidEntry> uidTable_t;
480    uidTable_t uidTable[LOG_ID_MAX];
481
482    // pid of system to size list
483    typedef LogHashtable<pid_t, PidEntry> pidSystemTable_t;
484    pidSystemTable_t pidSystemTable[LOG_ID_MAX];
485
486    // pid to uid list
487    typedef LogHashtable<pid_t, PidEntry> pidTable_t;
488    pidTable_t pidTable;
489
490    // tid to uid list
491    typedef LogHashtable<pid_t, TidEntry> tidTable_t;
492    tidTable_t tidTable;
493
494    // tag list
495    typedef LogHashtable<uint32_t, TagEntry> tagTable_t;
496    tagTable_t tagTable;
497
498    // security tag list
499    tagTable_t securityTagTable;
500
501    size_t sizeOf() const {
502        size_t size = sizeof(*this) + pidTable.sizeOf() + tidTable.sizeOf() +
503                      tagTable.sizeOf() + securityTagTable.sizeOf() +
504                      (pidTable.size() * sizeof(pidTable_t::iterator)) +
505                      (tagTable.size() * sizeof(tagTable_t::iterator));
506        for(auto it : pidTable) {
507            const char* name = it.second.getName();
508            if (name) size += strlen(name) + 1;
509        }
510        for(auto it : tidTable) {
511            const char* name = it.second.getName();
512            if (name) size += strlen(name) + 1;
513        }
514        log_id_for_each(id) {
515            size += uidTable[id].sizeOf();
516            size += uidTable[id].size() * sizeof(uidTable_t::iterator);
517            size += pidSystemTable[id].sizeOf();
518            size += pidSystemTable[id].size() * sizeof(pidSystemTable_t::iterator);
519        }
520        return size;
521    }
522
523public:
524
525    LogStatistics();
526
527    void enableStatistics() { enable = true; }
528
529    void add(LogBufferElement *entry);
530    void subtract(LogBufferElement *entry);
531    // entry->setDropped(1) must follow this call
532    void drop(LogBufferElement *entry);
533    // Correct for coalescing two entries referencing dropped content
534    void erase(LogBufferElement *element) {
535        log_id_t log_id = element->getLogId();
536        --mElements[log_id];
537        --mDroppedElements[log_id];
538    }
539
540    LogFindWorst<UidEntry> sort(uid_t uid, pid_t pid, size_t len, log_id id) {
541        return LogFindWorst<UidEntry>(uidTable[id].sort(uid, pid, len));
542    }
543    LogFindWorst<PidEntry> sortPids(uid_t uid, pid_t pid, size_t len, log_id id) {
544        return LogFindWorst<PidEntry>(pidSystemTable[id].sort(uid, pid, len));
545    }
546    LogFindWorst<TagEntry> sortTags(uid_t uid, pid_t pid, size_t len, log_id) {
547        return LogFindWorst<TagEntry>(tagTable.sort(uid, pid, len));
548    }
549
550    // fast track current value by id only
551    size_t sizes(log_id_t id) const { return mSizes[id]; }
552    size_t elements(log_id_t id) const { return mElements[id]; }
553    size_t realElements(log_id_t id) const {
554        return mElements[id] - mDroppedElements[id];
555    }
556    size_t sizesTotal(log_id_t id) const { return mSizesTotal[id]; }
557    size_t elementsTotal(log_id_t id) const { return mElementsTotal[id]; }
558    static size_t sizesTotal() { return SizesTotal; }
559
560    std::string format(uid_t uid, pid_t pid, unsigned int logMask) const;
561
562    // helper (must be locked directly or implicitly by mLogElementsLock)
563    const char *pidToName(pid_t pid) const;
564    uid_t pidToUid(pid_t pid);
565    const char *uidToName(uid_t uid) const;
566};
567
568#endif // _LOGD_LOG_STATISTICS_H__
569