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 <unordered_map>
25 
26 #include <log/log.h>
27 
28 #include "LogBufferElement.h"
29 
30 #define log_id_for_each(i) \
31     for (log_id_t i = LOG_ID_MIN; i < LOG_ID_MAX; i = (log_id_t) (i + 1))
32 
33 template <typename TKey, typename TEntry>
34 class LogHashtable {
35 
36     std::unordered_map<TKey, TEntry> map;
37 
38 public:
39 
40     typedef typename std::unordered_map<TKey, TEntry>::iterator iterator;
41 
sort(size_t n)42     std::unique_ptr<const TEntry *[]> sort(size_t n) {
43         if (!n) {
44             std::unique_ptr<const TEntry *[]> sorted(NULL);
45             return sorted;
46         }
47 
48         const TEntry **retval = new const TEntry* [n];
49         memset(retval, 0, sizeof(*retval) * n);
50 
51         for(iterator it = map.begin(); it != map.end(); ++it) {
52             const TEntry &entry = it->second;
53             size_t s = entry.getSizes();
54             ssize_t i = n - 1;
55             while ((!retval[i] || (s > retval[i]->getSizes())) && (--i >= 0))
56                 ;
57             if (++i < (ssize_t)n) {
58                 size_t b = n - i - 1;
59                 if (b) {
60                     memmove(&retval[i+1], &retval[i], b * sizeof(retval[0]));
61                 }
62                 retval[i] = &entry;
63             }
64         }
65         std::unique_ptr<const TEntry *[]> sorted(retval);
66         return sorted;
67     }
68 
69     // Iteration handler for the sort method output
next(ssize_t index,std::unique_ptr<const TEntry * []> & sorted,size_t n)70     static ssize_t next(ssize_t index, std::unique_ptr<const TEntry *[]> &sorted, size_t n) {
71         ++index;
72         if (!sorted.get() || (index < 0) || (n <= (size_t)index) || !sorted[index]
73          || (sorted[index]->getSizes() <= (sorted[0]->getSizes() / 100))) {
74             return -1;
75         }
76         return index;
77     }
78 
add(TKey key,LogBufferElement * e)79     inline iterator add(TKey key, LogBufferElement *e) {
80         iterator it = map.find(key);
81         if (it == map.end()) {
82             it = map.insert(std::make_pair(key, TEntry(e))).first;
83         } else {
84             it->second.add(e);
85         }
86         return it;
87     }
88 
add(TKey key)89     inline iterator add(TKey key) {
90         iterator it = map.find(key);
91         if (it == map.end()) {
92             it = map.insert(std::make_pair(key, TEntry(key))).first;
93         } else {
94             it->second.add(key);
95         }
96         return it;
97     }
98 
subtract(TKey key,LogBufferElement * e)99     void subtract(TKey key, LogBufferElement *e) {
100         iterator it = map.find(key);
101         if ((it != map.end()) && it->second.subtract(e)) {
102             map.erase(it);
103         }
104     }
105 
drop(TKey key,LogBufferElement * e)106     inline void drop(TKey key, LogBufferElement *e) {
107         iterator it = map.find(key);
108         if (it != map.end()) {
109             it->second.drop(e);
110         }
111     }
112 
begin()113     inline iterator begin() { return map.begin(); }
end()114     inline iterator end() { return map.end(); }
115 
116 };
117 
118 struct EntryBase {
119     size_t size;
120 
EntryBaseEntryBase121     EntryBase():size(0) { }
EntryBaseEntryBase122     EntryBase(LogBufferElement *e):size(e->getMsgLen()) { }
123 
getSizesEntryBase124     size_t getSizes() const { return size; }
125 
addEntryBase126     inline void add(LogBufferElement *e) { size += e->getMsgLen(); }
subtractEntryBase127     inline bool subtract(LogBufferElement *e) { size -= e->getMsgLen(); return !size; }
128 };
129 
130 struct EntryBaseDropped : public EntryBase {
131     size_t dropped;
132 
EntryBaseDroppedEntryBaseDropped133     EntryBaseDropped():dropped(0) { }
EntryBaseDroppedEntryBaseDropped134     EntryBaseDropped(LogBufferElement *e):EntryBase(e),dropped(e->getDropped()){ }
135 
getDroppedEntryBaseDropped136     size_t getDropped() const { return dropped; }
137 
addEntryBaseDropped138     inline void add(LogBufferElement *e) {
139         dropped += e->getDropped();
140         EntryBase::add(e);
141     }
subtractEntryBaseDropped142     inline bool subtract(LogBufferElement *e) {
143         dropped -= e->getDropped();
144         return EntryBase::subtract(e) && !dropped;
145     }
dropEntryBaseDropped146     inline void drop(LogBufferElement *e) {
147         dropped += 1;
148         EntryBase::subtract(e);
149     }
150 };
151 
152 struct UidEntry : public EntryBaseDropped {
153     const uid_t uid;
154 
UidEntryUidEntry155     UidEntry(LogBufferElement *e):EntryBaseDropped(e),uid(e->getUid()) { }
156 
getKeyUidEntry157     inline const uid_t&getKey() const { return uid; }
158 };
159 
160 namespace android {
161 uid_t pidToUid(pid_t pid);
162 }
163 
164 struct PidEntry : public EntryBaseDropped {
165     const pid_t pid;
166     uid_t uid;
167     char *name;
168 
PidEntryPidEntry169     PidEntry(pid_t p):
170         EntryBaseDropped(),
171         pid(p),
172         uid(android::pidToUid(p)),
173         name(android::pidToName(pid)) { }
PidEntryPidEntry174     PidEntry(LogBufferElement *e):
175         EntryBaseDropped(e),
176         pid(e->getPid()),
177         uid(e->getUid()),
178         name(android::pidToName(e->getPid())) { }
PidEntryPidEntry179     PidEntry(const PidEntry &c):
180         EntryBaseDropped(c),
181         pid(c.pid),
182         uid(c.uid),
183         name(c.name ? strdup(c.name) : NULL) { }
~PidEntryPidEntry184     ~PidEntry() { free(name); }
185 
getKeyPidEntry186     const pid_t&getKey() const { return pid; }
getUidPidEntry187     const uid_t&getUid() const { return uid; }
getNamePidEntry188     const char*getName() const { return name; }
189 
addPidEntry190     inline void add(pid_t p) {
191         if (name && !strncmp(name, "zygote", 6)) {
192             free(name);
193             name = NULL;
194         }
195         if (!name) {
196             char *n = android::pidToName(p);
197             if (n) {
198                 name = n;
199             }
200         }
201     }
202 
addPidEntry203     inline void add(LogBufferElement *e) {
204         uid_t u = e->getUid();
205         if (getUid() != u) {
206             uid = u;
207             free(name);
208             name = android::pidToName(e->getPid());
209         } else {
210             add(e->getPid());
211         }
212         EntryBaseDropped::add(e);
213     }
214 };
215 
216 struct TidEntry : public EntryBaseDropped {
217     const pid_t tid;
218     uid_t uid;
219     char *name;
220 
TidEntryTidEntry221     TidEntry(pid_t t):
222         EntryBaseDropped(),
223         tid(t),
224         uid(android::pidToUid(t)),
225         name(android::tidToName(tid)) { }
TidEntryTidEntry226     TidEntry(LogBufferElement *e):
227         EntryBaseDropped(e),
228         tid(e->getTid()),
229         uid(e->getUid()),
230         name(android::tidToName(e->getTid())) { }
TidEntryTidEntry231     TidEntry(const TidEntry &c):
232         EntryBaseDropped(c),
233         tid(c.tid),
234         uid(c.uid),
235         name(c.name ? strdup(c.name) : NULL) { }
~TidEntryTidEntry236     ~TidEntry() { free(name); }
237 
getKeyTidEntry238     const pid_t&getKey() const { return tid; }
getUidTidEntry239     const uid_t&getUid() const { return uid; }
getNameTidEntry240     const char*getName() const { return name; }
241 
addTidEntry242     inline void add(pid_t t) {
243         if (name && !strncmp(name, "zygote", 6)) {
244             free(name);
245             name = NULL;
246         }
247         if (!name) {
248             char *n = android::tidToName(t);
249             if (n) {
250                 name = n;
251             }
252         }
253     }
254 
addTidEntry255     inline void add(LogBufferElement *e) {
256         uid_t u = e->getUid();
257         if (getUid() != u) {
258             uid = u;
259             free(name);
260             name = android::tidToName(e->getTid());
261         } else {
262             add(e->getTid());
263         }
264         EntryBaseDropped::add(e);
265     }
266 };
267 
268 struct TagEntry : public EntryBase {
269     const uint32_t tag;
270     uid_t uid;
271 
TagEntryTagEntry272     TagEntry(LogBufferElement *e):
273         EntryBase(e),
274         tag(e->getTag()),
275         uid(e->getUid()) { }
276 
getKeyTagEntry277     const uint32_t&getKey() const { return tag; }
getUidTagEntry278     const uid_t&getUid() const { return uid; }
getNameTagEntry279     const char*getName() const { return android::tagToName(tag); }
280 
addTagEntry281     inline void add(LogBufferElement *e) {
282         uid_t u = e->getUid();
283         if (uid != u) {
284             uid = -1;
285         }
286         EntryBase::add(e);
287     }
288 };
289 
290 // Log Statistics
291 class LogStatistics {
292     size_t mSizes[LOG_ID_MAX];
293     size_t mElements[LOG_ID_MAX];
294     size_t mSizesTotal[LOG_ID_MAX];
295     size_t mElementsTotal[LOG_ID_MAX];
296     bool enable;
297 
298     // uid to size list
299     typedef LogHashtable<uid_t, UidEntry> uidTable_t;
300     uidTable_t uidTable[LOG_ID_MAX];
301 
302     // pid to uid list
303     typedef LogHashtable<pid_t, PidEntry> pidTable_t;
304     pidTable_t pidTable;
305 
306     // tid to uid list
307     typedef LogHashtable<pid_t, TidEntry> tidTable_t;
308     tidTable_t tidTable;
309 
310     // tag list
311     typedef LogHashtable<uint32_t, TagEntry> tagTable_t;
312     tagTable_t tagTable;
313 
314 public:
315     LogStatistics();
316 
enableStatistics()317     void enableStatistics() { enable = true; }
318 
319     void add(LogBufferElement *entry);
320     void subtract(LogBufferElement *entry);
321     // entry->setDropped(1) must follow this call
322     void drop(LogBufferElement *entry);
323     // Correct for merging two entries referencing dropped content
erase(LogBufferElement * e)324     void erase(LogBufferElement *e) { --mElements[e->getLogId()]; }
325 
sort(size_t n,log_id i)326     std::unique_ptr<const UidEntry *[]> sort(size_t n, log_id i) { return uidTable[i].sort(n); }
327 
328     // fast track current value by id only
sizes(log_id_t id)329     size_t sizes(log_id_t id) const { return mSizes[id]; }
elements(log_id_t id)330     size_t elements(log_id_t id) const { return mElements[id]; }
sizesTotal(log_id_t id)331     size_t sizesTotal(log_id_t id) const { return mSizesTotal[id]; }
elementsTotal(log_id_t id)332     size_t elementsTotal(log_id_t id) const { return mElementsTotal[id]; }
333 
334     // *strp = malloc, balance with free
335     void format(char **strp, uid_t uid, unsigned int logMask);
336 
337     // helper (must be locked directly or implicitly by mLogElementsLock)
338     char *pidToName(pid_t pid);
339     uid_t pidToUid(pid_t pid);
340     char *uidToName(uid_t uid);
341 };
342 
343 #endif // _LOGD_LOG_STATISTICS_H__
344